Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Linear Constraints: Basic Solutions

Description

This lecture covers the definition of basic solutions in linear constraints, the conditions for a feasible basic solution, and the equivalence between vertices and feasible basic solutions. The instructor explains the necessary and sufficient conditions for a point to be a vertex of a polyhedron.

In MOOC

Optimization: principles and algorithms - Linear optimization

Official source

Related concepts (23)

Polyhedron

In geometry, a polyhedron (: polyhedra or polyhedrons; ) is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices. A convex polyhedron is a polyhedron that bounds a convex set. Every convex polyhedron can be constructed as the convex hull of its vertices, and for every finite set of points, not all on the same plane, the convex hull is a convex polyhedron. Cubes and pyramids are examples of convex polyhedra. A polyhedron is a 3-dimensional example of a polytope, a more general concept in any number of dimensions.

Dual polyhedron

In geometry, every polyhedron is associated with a second dual structure, where the vertices of one correspond to the faces of the other, and the edges between pairs of vertices of one correspond to the edges between pairs of faces of the other. Such dual figures remain combinatorial or abstract polyhedra, but not all can also be constructed as geometric polyhedra. Starting with any given polyhedron, the dual of its dual is the original polyhedron. Duality preserves the symmetries of a polyhedron.

Goldberg polyhedron

In mathematics, and more specifically in polyhedral combinatorics, a Goldberg polyhedron is a convex polyhedron made from hexagons and pentagons. They were first described in 1937 by Michael Goldberg (1902–1990). They are defined by three properties: each face is either a pentagon or hexagon, exactly three faces meet at each vertex, and they have rotational icosahedral symmetry. They are not necessarily mirror-symmetric; e.g. GP(5,3) and GP(3,5) are enantiomorphs of each other.

Flexible polyhedron

In geometry, a flexible polyhedron is a polyhedral surface without any boundary edges, whose shape can be continuously changed while keeping the shapes of all of its faces unchanged. The Cauchy rigidity theorem shows that in dimension 3 such a polyhedron cannot be convex (this is also true in higher dimensions). The first examples of flexible polyhedra, now called Bricard octahedra, were discovered by . They are self-intersecting surfaces isometric to an octahedron.

Schönhardt polyhedron

In geometry, the Schönhardt polyhedron is the simplest non-convex polyhedron that cannot be triangulated into tetrahedra without adding new vertices. It is named after German mathematician Erich Schönhardt, who described it in 1928. The same polyhedra have also been studied in connection with Cauchy's rigidity theorem as an example where polyhedra with two different shapes have faces of the same shapes. One way of constructing the Schönhardt polyhedron starts with a triangular prism, with two parallel equilateral triangles as its faces.

Related lectures (31)

Linear Constraints and Vertices MOOC: Optimization: principles and algorithms - Linear optimization

Explores the significance of vertices in optimization and outlines a method to identify them using linear algebra.

The transhipment problem: Total unimodularity MOOC: Optimization: principles and algorithms - Network and discrete optimization

Covers the transhipment problem, optimal solutions, and total unimodularity in matrices.

Optimization: Classical Problems

Covers classical optimization problems, brute force algorithms, and integer linear optimization.

Linear constraints, Degeneracy MOOC: Optimization: principles and algorithms - Linear optimization

Covers linear constraints and degeneracy in polyhedrons, focusing on basic solutions and degenerate cases.

Linear Constraints: Polyhedron MOOC: Optimization: principles and algorithms - Linear optimization