3. Linear programming

Question 1

Standard form of a linear program (LP)

Answer 1

• the objective is a minimization
• all the variables are non-negative
• all the constraints are equalities

Question 2

Fig. transform an LP to the standard form

Answer 2

• Multiply maximization objectives by -1 and minimize it
• Add slack variables to ≤ constraints
• Subtract surplus variables from ≥ constraints

Question 3

Simplex method

Answer 3

• visits the extreme points of the feasible solution
• If, in standard form, the problem has m equations in n unknowns (m < n), setting n − m variables to 0 gives a basis of m variables, and defines an extreme point
• At each point, the simplex method moves to a neighboring extreme point by moving one variable into the basis (makes value > 0) and moving one out of the basis (make value 0)
• If no neighbor increases the objective, the optimal solution(s) has been found