Extreme Points and Vertex of Polyhedron ↵
x ∈ P is an extreme point of P if
x ̸= λ · y + (1 − λ) · z for all y, z ∈ P \ {x}, 0 ≤ λ ≤ 1,
i. e., x is not a convex combination of two other points in P.
x ∈ P is a vertex of P if
there is some c ∈ R n such that c T · x < cT · y for all y ∈ P \ {x},
i. e., x is the unique optimal solution to the LP min{c T · z | z ∈ P}.
Maxiumum subset (x) of Linear Indepedent Vectors
Amount of Matrices -1 = Dimension(x) ~
Max no. Linearly Indepedent Vectors in space = x
Try combination [Top Left + Row(i++)] → [Elements =! Col (Diagonal)] until sum /= 0\
Meaning Linearly Indepedent Vectors (Non-Singular).
M−1
[(x)(x)(x)(x) | (1)(0)(0)(0)]
[(x)(x)(x)(x) | (0)(1)(0)(0)]
[(x)(x)(x)(x) | (0)(0)(1)(0)]
[(x)(x)(x)(x) | (0)(0)(0)(1)]
1st(x) → 2nd correspondent(1) for operations.
Rx → Rx (+) (-) (x) Ry
Col++ until matches right side
Primal Solution
If ! (A · x = b) then convert to standard form.
Ax = b
(A−1)Ax = (A−1)b
Ix (Identity) = (A−1)b
x = (A−1)b → Xb [Basic (!0)] = (B−1)b
~ (B−1)b ~
4 x 4 [Matrix] 4 x 1 [Vector]
4 x 1
[(x)(x)(x)(x) | (y)]
[(x)(x)(x)(x) | (y)]
[(x)(x)(x)(x) | (y)]
[(x)(x)(x)(x) | (y)]
Primal → x(0, 0, x, x, x, x)
Tableau Approach of Simplex Method
If there is a (-) value as a minimization problem then improvement iteration continues:
Left Side is (0, 0, 0, x, x ,x) therefore Non-Basic.
Choose 1 Column and Swap Rows
Blands Rule → Which Non-Basic will become Basic, Which Basic will become Basic
Lowest Subscript [x1]
Constraint Rows (L / R) → [x1 ≤ (L / R)]
Minimum that satisfies conditions is Pivot
Correspond to [1] Column