X hits on this document

480 views

0 shares

17 / 63

Transforming a model into standard form by subtracting surplus variables will not work in the simplex method.

Figure A-4 Graph of the fertilizer example

# Simplex Solution of a Minimization Problem

A-17

Standard Form of a Minimization Model Consider the following linear programming model for a farmer purchasing fertilizer:

minimize Z = \$6x1 + 3x2

subject to

o f n i t r o g e n o f p h o s p h a t e 4 x 1 + 3 x 2 Ú 2 4 l b . 2 x 1 + 4 x 2 Ú 1 6 l b .

where

o f S u p e r - g r o f e r t i l i z e r o f C r o p - q u i c k f e r t i l i z e r x 2 = b a g s x 1 = b a Z = farmer’s total cost (\$) of purchasing fertilizer g s

This model is transformed into standard form by subtracting surplus variables from the two Ú constraints as follows:

minimize Z = 6x1 + 3x2 + 0s1 + 0s

2

subject to

x 1 , x 2 , s 1 , s 2 Ú 0 4 x 1 + 3 x 2 - s 2 = 2 4 2 x 1 + 4 x 2 - s 1 = 1 6

The surplus variables represent the extra amount of nitrogen and phosphate that exceeded the minimum requirements specified in the constraints.

However, the simplex method requires that the initial basic feasible solution be at the origin, where x1 = 0 and x2 = 0. Testing these solution values, we have

s 1 = - 1 6 2 ( 0 ) + 4 ( 0 ) - s 1 = 1 6 2 x 1 + 4 x 2 - s 1 = 1 6

The idea of “negative excess pounds of nitrogen” is illogical and violates the nonnegativ- ity restriction of linear programming. The reason the surplus variable does not work is shown in Figure A-4. The solution at the origin is outside the feasible solution space.

x2

12

10

8

A

x 1 = 0 x 2 = 0 s 1 = 1 6

6

4

2

B

C

0

2

4

6

8

10

12

x1

 Document views 480 Page views 480 Page last viewed Tue Jan 17 05:09:14 UTC 2017 Pages 63 Paragraphs 3770 Words 30893