LP

Question 1

Where are vertices of feasible region located

Answer 1

Corner of feasible region polygon

Question 2

Proof why feasible region is a convex set

Answer 2

feasible region is defined by the intersection of half spaces

Question 3

Where do optimal points lie in feasible region

Answer 3

vertex of feasible region

Question 4

When is a vertex a global optima

Answer 4

When its value is “better” than its neighbors

Question 5

[Canonical Form]
Given obj func:
x1 + 6x2 + 10x3

What are its coefficients

Answer 5

1, 6, 10

Question 6

Importance of non-negative constraints

Answer 6

1. Use to find a trivially feasible points
2. Determine feasible region is empty, therefore LP is infeasible

Question 7

Given obj func and constraints:
x1 + 6x2 + 10x3
x1 <= 300
x2 <= 200
x1 + 3x2 + 2x3 <= 1000
What is its constraint matrix A

Answer 7

[[ 1, 0, 0 ], [ 0, 1, 0 ], [ 1, 3, 2 ]]

Question 8

[Converting Linear Algebra to Standard Form]

How to minimize objective function cTx

Answer 8

Multiply by -1, -cTx

Question 9

[Converting Linear Algebra to Standard Form]

Given constraint, how to convert to standard form:
a1​x1​…an​xn​ ≥ b

Answer 9

Need to change to “at most” form
Multiply by -1 to flip inequality:
-a1​x1​…-an​xn​ ≤ b

Question 10

[Converting Linear Algebra to Standard Form]

Given equality constraint, how to convert to standard form:
a1​x1​…an​xn​ = b

Answer 10

Create 2 inequality constraints
a1​x1​…an​xn​ ≤ b, and
a1​x1​… an​xn​ ≥ b
Then flip the second to meet standard form

Question 11

[Converting Linear Algebra to Standard Form]

Why are strict inequalities not allowed in LPs

Answer 11

With strict inequalities, the feasible region would exclude its boundary points

Question 12

[Converting Linear Algebra to Standard Form]

How to handle unconstrained variables (e.g. “x”)

Answer 12

Split it to 2 components, x +& x-, both with non-negative values.

x = x+ - x-

Question 13

Given objective function
min 3x_1 - 2.5x_2 + x_3

Convert c values into standard form

Answer 13

c = [[ -3 ], [ 2.5 ], [ -1 ]]

Question 14

Given objective function
minimize 3x_1 - 2.5x_2 + x_3

Convert c values into standard form

Question 15

Convert constraint to standard form
x2 + x3 >= 300

Answer 15

Negate to reverse inequality
-x2 - x3 <= 300

Question 16

Convert constraint to standard form
0.5x + 7y - 2z = 4

Answer 16

First, split the equality into two inequalities:
0.5x + 7y - 2z ≤ 4
0.5x + 7y - 2z ≥ 4

For the second inequality, multiply by -1 to get the standard “less than or equal to” form:
0.5x + 7y - 2z ≤ 4
-0.5x - 7y + 2z ≤ -4

Question 17

[Geometric View]
Given m constraints and n non-negativity constraints we get _____ constraints

Answer 17

n+m constraints

Question 18

[Geometric View]

Given n+m constraints, where does the feasible region lie

Answer 18

Intersection of n+m half spaces (convex polyhedron)

Question 19

[Geometric View]
Where do vertex lie in feasible region with respect to constraints

Answer 19

n constraints met with equality (=)
m constraints met with inequality (<=)

Question 20

[Geometric View]

Upper bound of vertex neighbors

Answer 20

at most nm neighbors

Question 21

Simplex algorithm

Answer 21

1. Start at x=0
2. Look for neighboring vertex with strictly higher objective value
3. Move to neighbor, repeat 2
4. Else, return x as optimal

Question 22

T/F
Simplex algorithm can move to any point in the feasible region

Answer 22

False

Simplex algorithm walks on vertices (corners)

Question 23

[LP Optimality]
Define infeasible

Answer 23

Feasible region is empty

Question 24

[LP Optimality]
Define unbounded

Answer 24

Objective function can reach infinite optimal value

Question 25

Constraint 1 (x + y <= 1) and constraint 2 (3x + 2y >= 6) yield non-intersecting half spaces. Why is this LP infeasible

Answer 25

It creates 2 non-intersecting half-spaces. No x,y value can meet both constraints

Question 26

Infeasibility is not dependent on objective function. Give a reason why

Answer 26

If you set constraints that create non-intersecting regions, you can never find optimal solution.

Question 27

Unboundedness is specific to the objective function. Give a reason why

Answer 27

Same constraints can produce bounded or unbounded problems depending on which direction the objective function points. Constraints determine the shape of the feasible region, objective function determines whether we can improve indefinitely within that region.

Question 28

Conditions that make LP unbounded (2)

Answer 28

1. Constraints that create an unbounded feasible region (extending to infinity in some direction) 2. An objective function that improves in that same unbounded direction

Question 29

[Infeasible] Steps to detect if LP is infeasible

Answer 29

1. Add new variable z to constraint Ax + z <= b & x >= 0 2. Set new objective function "max z" 3. Solve for z If optimized z is non-negative, original LP is feasible. If z is negative, original LP is infeasible

Question 30

[Infeasible] Why does adding z always satisfy <= b?

Answer 30

Because z is unrestricted, thus we can add a large non-negative number to always meet constraint.

Question 31

[Optimality] Optimum of LP is achieved at a vertex of the feasible except 2 cases Define the two cases

Answer 31

1. Infeasible - Feasible region is empty, ie. no variable values will meet all constraints 2. Unbounded - Given constraints and obj function, there is no bounds to optimization

Question 32

Weak Duality definition

Answer 32

If both primal and dual LPs are feasible, the inequality c^Tx <= b^Ty always holds

Question 33

Weak Duality theorem if obj func of x and y are equal c^Tx = b^Ty

Answer 33

Both x and y are optimal x = optimal max y = optimal min

Question 34

Strong Duality theorem guarantee if primal-dual pairs are feasible and bounded

Answer 34

We can find an optimal max x and min y value that is equal.

Question 35

[Unbounded] If primal linear program (LP) is unbounded , dual LP is ____ If dual is infeasible primal is ______.

Answer 35

Infeasible Infeasible or Unbounded

Question 36

[Weak Duality] If Dual LP is infeasible, then primal is:

Answer 36

Unbounded OR infeasible

Question 37

T/F Given primal-dual pair cTx ≤ bTy, if primal is infeasible then dual can't be infeasible

Answer 37

False Not a bidirectional relationship, both primal and dual can be infeasible. So the implication has only one direction.

Question 38

[Unbounded] Why is just checking if dual LP is unbounded not enough to determine primal is unbounded

Answer 38

If dual is unbounded, primal could be EITHER unbounded or infeasible. We don't know which unless we check primal.

Question 39

2 steps to determine if LP in canonical form is unbounded

Answer 39

1. For primal LP, check feasibility by adding z variable and maximizing z. If solution has non-negative z value, primal is feasible. 2. For dual LP, check feasibility. If dual = infeasible, primal is unbounded (not infeasible since we confirmed it is feasible in step 1)

Question 40

Strong duality definition

Answer 40

If primal and dual LPs are both feasible and bounded, then their optimal solutions are equal: c^Tx = b^Ty (LHS take max, RHS takes min)

Question 41

Difference between weak and strong duality theorem

Answer 41

Weak duality only shows inequality between feasible primal / dual solutions. cTx ≤ bTy Strong duality shows equality between bounded + feasible primal / dual solutions

Question 42

If the original LP is feasible and bounded, then the dual LP is:

Answer 42

also feasible and bounded.

Question 43

The dual of the dual LP is....

Answer 43

primal LP

Question 44

T/F It is impossible for both the original LP and the dual LP to be infeasible.

Answer 44

False

Question 45

T/F Feasibility means there must be only one solution to the LP problem

Answer 45

False. this can mean only one solution, or infinitely many solutions.

Question 46

T/F An infeasible LP can still be bounded

Answer 46

False the discussion of boundedness only makes sense for feasible LPs.

Question 47

[Geometric view] Max number of vertices with n equality constraints and m inequality constraints?

Answer 47

n+m choose n (combinatorial)

Question 48

How to handle converting to duals when some variables are missing

Answer 48

fill in variables with zero cofficients ``` max x1 - 0x2 - 2x3 s.t. x1 - x2 - 0x3 <= 1 0x1 + 2x2 - x3 <= 1 x1, x2, x3 >= 0 min y1 + y2 s.t. y1 >= 1 -y1 + 2y2 >= 0 -y2 >= -2 ```