[ Pobierz całość w formacie PDF ]
reason for this is that there is no convenient feasible solution to begin the simplex method.
Note that the solution represented by the initial tableau above,
x1, x2, x3, s1, s2, s3 0, 0, 0, 50, 36, 10 ,
558 CHAPTER 9 LINEAR PROGRAMMING
is not a feasible solution because the values of the two surplus variables are negative. In fact,
the values x1 x2 x3 0 do not even satisfy the constraint equations. In order to elim-
inate the surplus variables from the current solution, trial and error is used. That is, in an
effort to find a feasible solution, arbitrarily choose new entering variables. For instance, in
this tableau, it seems reasonable to select x3 as the entering variable. After pivoting, the new
simplex tableau becomes the following.
Basic
x1 x2 x3 s1 s2 s3 b Variables
1 1 0 1 0 1 40 s1
!
2 1 0 0 1 0 36 s2 ! Departing
1 0 1 0 0 1 10 x3
1 1 0 0 0 2 20
!
Entering
The current solution x1, x2, x3, s1, s2, s3 0, 0, 10, 40, 36, 0 is still not feasible, so
choose x2 as the entering variable and pivot to obtain the following simplex tableau.
Basic
x1 x2 x3 s1 s2 s3 b Variables
!
1 0 0 1 1 1 4 s1 ! Departing
2 1 0 0 1 0 36 x2
1 0 1 0 0 1 10 x3
3 0 0 0 1 2 56
!
Entering
At this point, the following feasible solution is finally obtained.
x1, x2, x3, s1, s2, s3 0, 36, 10, 4, 0, 0
From here on, you can apply the simplex method as usual. Note that the entering variable
here is s3 because its column has the most negative entry in the bottom row. After pivoting
one more time, you obtain the following final simplex tableau.
Basic
x1 x2 x3 s1 s2 s3 b Variables
1 0 0 1 1 1 4 s3
2 1 0 0 1 0 36 x2
0 0 1 1 1 0 14 x3
1 0 0 2 1 0 64
SECTION 9.5 THE SIMPLEX METHOD: MIXED CONSTRAINTS 559
Note that this tableau is final because it represents a feasible solution and there are no
negative entries in the bottom row. So, you can conclude that the maximum value of the
objective function is
z 64 Maximum value
and this occurs when
x1 0, x2 36, and x3 14.
EXAMPLE 1 A Maximization Problem with Mixed Constraints
Find the maximum value of
z 3x1 2x2 4x3 Objective function
subject to the constraints
3x1 2x2 5x3 d" 18
4x1 2x2 3x3 d" 16 Constraints
2x1 x2 x3 e" 4
where x1 e" 0, x2 e" 0, and x3 e" 0.
Solution To begin, add a slack variable to each of the first two inequalities and subtract a surplus vari-
able from the third inequality to produce the following initial simplex tableau.
Basic
x1 x2 x3 s1 s2 s3 b Variables
3 2 5 1 0 0 18 s1
4 2 3 0 1 0 16 s2
!
2 1 1 0 0 1 4 s3 ! Departing
3 2 4 0 0 0 0
!
Entering
As it stands, this tableau does not represent a feasible solution (because the value of s3 is
negative). So, s3 should be the departing variable. There are no real guidelines as to which
variable should enter the solution, but by trial and error, you will discover that using x2 as
the entering variable produces the following tableau (which does represent a feasible
solution).
Basic
x1 x2 x3 s1 s2 s3 b Variables
!
1 0 3 1 0 2 10 s1 ! Departing
0 0 1 0 1 2 8 s2
2 1 1 0 0 1 4 x2
1 0 2 0 0 2 8
560 CHAPTER 9 LINEAR PROGRAMMING
Now, because this simplex tableau does represent a feasible solution, you can proceed as
usual, choosing the most negative entry in the bottom row to be the entering variable. (In
this case, there is a tie, so arbitrarily choose x3 to be the entering variable.)
Basic
x1 x2 x3 s1 s2 s3 b Variables
!
1 0 3 1 0 2 10 s1 ! Departing
0 0 1 0 1 2 8 s2
2 1 1 0 0 1 4 x2
1 0 2 0 0 2 8
!
Entering
Basic
x1 x2 x3 s1 s2 s3 b Variables
1 0 11 02 10 x3
3 3 3 3
1
!
0 0 1 14 14 s2 ! Departing
3 3 3 3
7
1 0 1 0 5 2 x2
3 3 3 3
1
0 02 0 2 44
3 3 3 3
!
Entering
Basic
x1 x2 x3 s1 s2 s3 b Variables
1
1 0 1 1 0 1 x3
2 2 2
1 7
0 0 1 3 1 s3
4 4 4 2
11
1 0 3 5 013 x2
4 4 4 2
1
0 01 1 0 17
2 2 2
So, the maximum value of the objective function is
z 17
and this occurs when
13
x1 0, x2 , and x3 1.
2
Mixed Constraints and Minimization
In Section 9.4, the solution of minimization problems in standard form was discussed.
Minimization problems that are not in standard form are more difficult to solve. One tech-
nique that can be used is to change a mixed-constraint minimization problem to a mixed-
constraint maximization problem by multiplying each coefficient in the objective function
by 1. This technique is demonstrated in the following example.
SECTION 9.5 THE SIMPLEX METHOD: MIXED CONSTRAINTS 561
EXAMPLE 2 A Minimization Problem with Mixed Constraints
Find the minimum value of
w 4x1 2x2 x3 Objective function
subject to the constraints
2x1 3x2 4x3 d" 14
3x1 x2 5x3 e" 4 Constraints
x1 4x2 3x3 e" 6
where x1 e" 0, x2 e" 0, and x3 e" 0.
Solution First, rewrite the objective function by multiplying each of its coefficients by 1, as
follows.
z 4x1 2x2 x3 Revised objective function
Maximizing this revised objective function is equivalent to minimizing the original
objective function. Next, add a slack variable to the first inequality and subtract surplus
variables from the second and third inequalities to produce the following initial simplex
tableau.
Basic
x1 x2 x3 s1 s2 s3 b Variables
2 3 4 1 0 0 14 s1
!
3 1 5 0 1 0 4 s2 ! Departing
1 4 3 0 0 1 6 s3
4 2 1 0 0 0 0
!
Entering
Note that the bottom row has the negatives of the coefficients of the revised objective func-
tion. Another way of looking at this is that for minimization problems (in nonstandard
form), the bottom row of the initial simplex consists of the coefficients of the original
objective function.
As with maximization problems with mixed constraints, this initial simplex tableau does
not represent a feasible solution. By trial and error, you will discover that you can choose
x2 as the entering variable and s2 as the departing variable. After pivoting, you obtain the
following tableau.
Basic
x1 x2 x3 s1 s2 s3 b Variables
7 0 11 1 3 0 2 s1
3 1 5 0 1 0 4 x2
11 0 17 0 4 1 10 s3
2 0 9 0 2 0 8
562 CHAPTER 9 LINEAR PROGRAMMING
From this tableau, you can see that the choice of x2 as the entering variable was a good one.
All you need to do to transform the tableau into one that represents a feasible solution is to
multiply the third row by 1, as follows.
Basic
x1 x2 x3 s1 s2 s3 b Variables
7 0 11 1 3 0 2 s1
3 1 5 0 1 0 4 x2
!
11 0 17 0 4 1 10 s3 ! Departing
2 0 9 0 2 0 8
!
Entering
Now that you have obtained a simplex tableau that represents a feasible solution, continue
with the standard pivoting operations as follows.
Basic
x1 x2 x3 s1 s2 s3 b Variables
2 7 11 144
0 0 117 17 17 s1
17
4 3 5
!
17 1 0 0 17 18 x2 ! Departing
17 17
11 4 1
0 1 0 17 17 10 x3
17 17
65 2 9
0 0 0 17 17 46
17 17
!
Entering
Basic
x1 x2 x3 s1 s2 s3 b Variables
2 4
7 0 1 0 6 s1
3 3 3
4 17 0 0 1 5 6 s2
3 3 3
1 4
1 0 0 1 2 x3
3 3 3
11 2 1
0 0 0 2
3 3 3
Finally, you can conclude that the maximization value of the revised objective function is
z 2, and so the minimum value of the original objective function is
w 2
(the negative of the entry in the lower-right corner), and this occurs when
x1 0, x2 0, and x3 2.
SECTION 9.5 THE SIMPLEX METHOD: MIXED CONSTRAINTS 563
Applications
[ Pobierz całość w formacie PDF ]