APM261: Quiz 4. The Simplex Method

Quiz 4. The Simplex Method

Enter your name:

Each question has only one correct answer. The results of the quiz do not affect the final marks.

1: Consider a minimization problem with two extreme points x₁ and x₂ and two extreme directions d₁ and d₂. Suppose the objective function z = c x has the following values:

c x₁ = 3, c x₂ = 3, c d₁ = 1, c d₂ = 0

Find a complete set of optimal solutions to the problem.

x = a x₁ + (1 - a) x₂, where 0 <= a <= 1


 x = x₂ + b d₂

, where b >= 0

 x 
= a x₁ + (1 - a) x₂ + b d₂

, where 0 <= a <= 1 and b >= 0


 x = a x₁ + (1 - a) x₂ + 
b₁ d₁ + b₂ d₂

, where

0 <= 
a <= 1

and b₁, b₂ >= 0

2: Identify a wrong entry in the simplex tableau:

	`x₁`	`x₂`	`x₃`	`x₄`
`x₂`	-1	1	-3	0	0
`x₄`	2	0	-5	1	1
`z`	1	-1	0	0	-5

Objective function has negative value
Basic variable x₂ has zero value
Non-basic variable x₃ has zero entry in the objective row
Basic variable x₂ has negative entry in the objective row

3-4: Consider the minimization of

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

subject to the system

x₁ - x₂ + 2 x₃ + x₄ = 3
-x₁ + 3 x₂ + 5 x₃ + x₅ = 1

where all variables are non-negative. Find the missing entries A and B in the simplex tableau:

	`x₁`	`x₂`	`x₃`	`x₄`	`x₅`
`x₁`	1	-1	2	1	0	3
`x₅`	0	2	7	1	1	`A`
`z`	0	-5	8	2	0	`B`

A = 6
A = 4
A = 2
A = 0 B = -6
B = -2
B = 0
B = 2

5: Identify status of the simplex method from the tableau:

	`x₁`	`x₂`	`x₃`	`x₄`
`x₁`	1	-1	0	3	3
`x₃`	0	-2	1	1	4
`z`	0	0	0	0	-1

One more iteration is required
Simplex method terminates: unique optimal solution
Simplex method terminates: alternative optimal solutions
Simplex method terminates: unbounded optimal solutions

Your Results: