CO250 Quiz 3 (Two phase simplex, geometry of simplex, polyhedron and convexity)
Studied by 0 people
Call Kai
Learn
Practice Test
Spaced Repetition
Match
Flashcards
Knowt Play1/27
There's no tags or description
Looks like no tags are added yet.
Name | Mastery | Learn | Test | Matching | Spaced |
|---|
No study sessions yet.
28 Terms
What is needed in order to form an auxiliary LP?
Non-negativity on the RHS
Need identity in A
What is the key concept of the auxiliary LP?
The auxiliary variables are not in the original LP.
However, if there is a feasible solution of the auxiliary LP, where all auxiliary variables are 0s, the rest of the solution is feasible for the original LP.
What are auxiliary variables?
Variables added in order to add an identity in A.
What do we want auxiliary variables to equal?
We want auxiliary variables to be 0s.
How do we make auxiliary variables equal to 0?
Minimize the sum.
ex. min (x4 + x5) will become max (-x4-x5)
What are the 2 cases for running simplex on the auxiliary LP?
If the optimal value is 0, then all auxiliary variables must have value 0.
Dropping the auxiliary variables gives a feasible solution to the original LP
If the optimal value is negative, the original LP is infeasible.
What are the requirements of the certificate of infeasibility for vector y?
yTA >=0 and yTb <0
What is the certificate of infeasibilty y?
y = AB-TCB
What is the phase 1 of the two-phase simplex?
Run simplex on the auxiliary LP
If the optimal value is <0, then the original LP is infeasible. STOP
If the optimal value is 0, then the original LP is feasible.
What is the phase 2 of the two-phase simplex?
Run simplex on the original LP using BFS from phase 1 (put in canonical form).
What are the 2 results that could happen after phase 2?
Either:
There is an optimal solution
LP is unbounded
What is the consequence of the two-phase simplex?
A linear program has exactly one of the three outcomes:
It is infeasible
It is unbounded
It has an optimal solution
What does tight constraint mean?
Given a point x̄, an inequality constraint is tight if x̄ satisfies the inequality with equality.
What is an extreme point?
In R2, extreme points are feasible points that are intersections of 2 tight constraints.
What is the meaning of basic feasible solutions?
A basic feasible solution corresponds to an extreme point in the feasible region
What causes the moving of one point to another?
Entering/leaving variables.
What is the result of a simplex?
For a LP in SEF, if there is an optimal solution, then there is an extreme point that is optimal.
When does a degenerate iteration happen?
A degenerate iteration happens when there are more than 2 tight constraints for the point, causing an iteration to not move from one point to another.
What is the equation of a hyperplane?
aTx = B
What is a hyperplane?
A hyperplane is the normal vector
What is the equation for the halfspace?
aTx <= B
What is a halfspace?
It is the area on the opposite side of the hyperplane
What is the equation for a polyhedron?
{x∊Rn: Ax<=b}
What is a polyhedron?
A polyhedron is the intersection of halfspaces.
What makes a polyhedron special?
The feasible solution of any LP is a polyhedron.
What is the informal definition of convexity?
A set of points is convex if the line segment connecting any two points in the set is also in the set.
What is the formula used to show that a set is convex?
For any x1, x2∊C, λx1+(1-λ)x2∊C for all λ∊[0, 1].
This is a convex combination