Numerical Methods and Optimization

The Simplex Method for Linear Programming 255

can be expressed as x

1

+ x

2

≥ 100, we obtain the following LP:

maximize 15x

1

+25x

2

subject to x

1

+ x

2

≤ 450 (solid color fabric constraint)

x

2

≤ 300 (printed fabric constraint)

4x

1

+5x

2

≤ 2, 000 (budget constraint)

x

1

≤ 350 (demand constraint)

x

1

+ x

2

≥ 100 (manufacturing constraint)

x

1

,x

2

≥ 0 (nonnegativity constraints).

As before, we first convert the LP to the standard form by introducing the

slack variables s

i

,i=1,...,4 for the first four constraints, and an excess

variable e

5

for the fifth constraint.

maximize 15x

1

+25x

2

subject to x

1

+ x

2

+ s

1

= 450

x

2

+ s

2

= 300

4x

1

+5x

2

+ s

3

=2, 000

x

1

+ s

4

= 350

x

1

+ x

2

− e

5

= 100

x

1

,x

2

,s

1

,s

2

,s

3

,s

4

,e ...