In this lab we want to provide a preview of linear programming. There will be no coding, but rather simple questions to investigate.
Ex. 1 — General questions
General questions:
1. What is linear programming?
2. Provide examples of situations where linear programming is used in practice.
3. What are the standard and slack forms and how good are they to express a linear program?
4. What algorithms exist to solve linear programs? Provide a simple but clear description of the simplex method.
5. What is duality and when could it be applied when running the simplex method?
Ex. 2 — Toy example for the simplex method
1. We are interested in the following linear programming problem P. Minimize −2x1 + 3x2, subject to
−
≤
x1
+ x2
= 7
x1
2x2
4
≥ 0.
x1
a) Rewrite P in standard form.
b) rewrite P in slack form.
2. Apply the simplex method to the following linear problem expressed in slack form by
z = 3x1 + x2 + 2x3
x4 =30 − x1 − x2 − 3x3
x5 =24 − 2x1 − 2x2 − 5x3
x6 =36 − 4x1 − x2 − 2x3.
