X hits on this document

380 views

0 shares

0 downloads

0 comments

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 info
Document views380
Page views380
Page last viewedMon Dec 05 14:58:52 UTC 2016
Pages63
Paragraphs3770
Words30893

Comments