VE477 Lab 8

Description

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 −2x₁ + 3x₂, subject to

		−		≤
	x1
		+ x2		= 7
x1			2x2		4
				≥ 0.
x1

1. 1. Rewrite P in standard form.

1. 2. rewrite P in slack form.

2. Apply the simplex method to the following linear problem expressed in slack form by

z = 3x₁ + x₂ + 2x₃

x₄ =30 − x₁ − x₂ − 3x₃

x₅ =24 − 2x₁ − 2x₂ − 5x₃

x₆ =36 − 4x₁ − x₂ − 2x₃.