Linear Algebra and Its Applications · Problem 8.2.10

Linear Programming and Game Theory — Gilbert Strang

Mathematics · simplex-method-entering-leaving

Problem

Suppose we want to minimize cx=x1−x2cx = x_1 - x_2, subject to 2x1−4x2+x3=62x_1 - 4x_2 + x_3 = 6 3x1+6x2−4x2+x4=123x_1 + 6x_2 \phantom{{}-4x_2} + x_4 = 12 (all x1,x2,x3,x4≥0x_1, x_2, x_3, x_4 \geq 0). Starting from x=(0,0,6,12)x = (0, 0, 6, 12), should x1x_1 or x2x_2 be increased from its current value of zero? How far can it be increased until the equations force x3x_3 or x4x_4 down to zero? At that point, what is the new xx?

Related theory

Browse the problem library