feasible regions

Work in Progress

Summary

Extreme points

Concept

Feasible region

  • set of all feasible solutions to an LP

Polyhedron

  • technically polytropes, for generalizing to dimensions
  • region bounded by constraints

polyhedra cannot have “dents” or “holes”

Feasible region of LP is a polyhedron
TODO

Hyperplane

  • set of solutions to a linear equation

Dimension of hyperplanes

one linear constraint removes one degree of freedom

Halfspace

  • set of solutions to a linear inequality

a polyhedron is the intersection of a finite set of halfspaces

Pasted image 20261020221306.png

Translate

translate_hyperplane.png

translate all the elements of a set

Translate of hyperplanes

Translate of halfspaces
TODO
similar to above

Convexity

  • no “dents” and no “holes”

Line through two points

Line segment between two points

  • aka convex combination

Convexity of a set

Intersection remains convex
TODO
Linesegment in A and in B so in A B

Halfspaces are convex

Polyhedra are convex
TODO
P is intersection of halfspaces
halfspaces are convex
intersection of conves is convex

feasible region of LP is convex, which is what makes it relatively easy to solve

Extreme points

  • basically the verticies of the polyhedron

Properly contained

  • point on the line segment that is not the endpoints

Non-extreme points

Convex set may have no extreme points (halfspace)
or infinite extreme points (circle/n-sphere)

Tight constraints

  • constraint that is satisfied with equality

A point is extreme iff it has tight constraints

extreme points have tight constraints

Deficient rank

Extreme points are basic feasible solutions

TODO

Problems with slack variables

  • are isomorphic
  • slack variables do not provide additional information

this allows us to simplify things to “less dimensions” to better visualize the extreme points

Application

SEF to polyhedron form

Extreme points of a LP

(1)(2)(3)x1x2123120fgh

Checking for extreme points

Slack variabls and extreme points

Extra

Helpful aside for proving the extreme point theorem

Generalization for line segment form

Generalization to vector
TODO