Question 1006342: Maximize P = 3x + 2y
subject to
2x + y ≤ 18
2x + 3y ≤ 42
3x + y ≤ 24
x ≥ 0, y ≥0
Solve the problem using the simplex method in linear programming.
Answer by Edwin McCravy(20054)   (Show Source):
You can put this solution on YOUR website!
Maximize:
P = 3x + 2y
Subjct to:
2x + y ≤ 18
2x + 3y ≤ 42
3x + y ≤ 24
x ≥ 0, y ≥0
We introduce non-negative slack variables s1, s2, and s3
which are just enough to make the left side of the
inequalities equal to their right sides, and we also
add 0P to the left side which does not change the value.
2x + y + s1 + 0P = 18
2x + 3y + s2 + 0P = 42
3x + y + s3 + 0P = 24
We write the objective function P=3x+2y
as
-3x - 2y + 0s1 + 0s2 + 0s3 + 1P = 0
So we have this system of equations:
2x + y + s1 + 0P = 18
2x + 3y + s2 + 0P = 42
3x + y + s3 + 0P = 24
-3x - 2y + 0s1 + 0s2 + 0s3 + 1P = 0
This is 4 equations in 6 variables, so it has many
solutions, but we want the solution that maximizes
the variable P. We put in all the coefficients of
all the variables, including 0'a and 1's:
2x + 1y + 1s1 + 0s2 + 0s3 + 0P = 18
2x + 3y + 0s1 + 1s2 + 0s3 + 0P = 42
3x + 1y + 0s1 + 0s2 + 1s3 + 0P = 24
------------------------------------
-3x - 2y + 0s1 + 0s2 + 0s3 + 1P = 0
We want to get the bottom equation so that it
will have no negative terms on it so that when
we solve it for P, we will only have subtractions
of non-negative numbers from it, and we can then make
P largest by choosing the subtractions of
non-negative variables to all be 0.
Now we make it into a matrix with partitions
(called the first "tableau"):
x y | s1 s2 s3 | P | k
-------------------------------------
2 1 | 1 0 0 | 0 | 18
2 3 | 0 1 0 | 0 | 42
3 1 | 0 0 1 | 0 | 24
-------------------------------------
-3 -2 | 0 0 0 | 1 | 0
We want to end up with no negative numbers on the
bottom row. We take the most negative number in
the bottom row (these are called "indicators")
and call the column which it's in "the pivot column"
CHOOSE THE PIVOT COLUMN:
We choose the -3 in the column 1 as the most negative
indicator. So column 1 is the pivot column.
CHOOSE THE PIVOT ROW:
To the side, divide each of the positive numbers in the
pivot column INTO the number on the same row in the
rightmost column (headed "k"):
18÷2=9, 42÷2=21, 24÷3=8
We find that the least of these is 8, which was obtained
when we divided the 3 in the pivot column row 3 into the
24 at the far right, so we call row 3 "the pivot row", and we
call the element 3 "the pivot element". So we have a
pivot column, a pivot row and a pivot element.
Now we will do what is called "pivoting" on an element.
1. Divide the pivot row through by the pivot element.
This causes the pivot element to become 1.
2. Multiply the new pivot row by whatever is necessary
so that when it is added to the other rows there will be
0's everywhere else in the pivot column.
x y | s1 s2 s3 | P | k
-------------------------------------
0 1/3 | 1 0 -2/3 | 0 | 2
0 7/3 | 0 1 -2/3 | 0 | 26
1 1/3 | 0 0 1/3 | 0 | 8
-------------------------------------
0 -1 | 0 0 1 | 1 | 24
That's the second tableau. This is not the final
tableau because it has a negative indicator of -1. at the
bottom of column 2. So the pivot column is column 2.
CHOOSE THE PIVOT ROW:
To the side, divide each of the positive numbers in the
pivot column INTO the number on the same row in the
rightmost column (headed "k"):
2÷1/3 = 2×3/1 = 6, 26÷7/3 = 26×3/7 = 78/7
Since 6 is smaller than 78/7, the pivot row is row 1.
The pivot element is the 1 on the second row.
Now we pivot again.
1. Divide the pivot row through by the pivot element.
2. Multiply the pivot row by whatever is necessary
so that when it is added to the other rows there will be
0's everywhere else in the pivot column.
The next tableau is
x y | s1 s2 s3 | P | k
----------------------------------
0 1 | 3 0 -2 | 0 | 6
0 0 | -7 1 4 | 0 | 12
1 0 | -1 0 1 | 0 | 6
----------------------------------
0 0 | 3 0 -1 | 1 | 30
This is not the final tableau because it has a negative
indicator of -1. at the bottom of column 5. So the pivot
column is column 5:
CHOOSE THE PIVOT ROW:
To the side, divide each of the positive numbers in the
pivot column INTO the number on the same row in the
rightmost column (headed "k"):
12÷4=3, 6÷1=6
Since 3 is smaller than 6, the pivot row is row 2.
The pivot element is the 1 on the second row.
Now we pivot again.
1. Divide the pivot row through by the pivot element.
2. Multiply the pivot row by whatever is necessary
so that when it is added to the other rows there will be
0's everywhere else in the pivot column.
The next tableau is
x y | s1 s2 s3 | P | k
-------------------------------------
0 1 |-1/2 1/2 0 | 0 |12
0 0 |-7/4 1/4 1 | 0 | 4
1 0 | 3/4 -1/4 0 | 0 | 3
------------------------------------
0 0 | 5/4 1/4 0 | 1 |33
Now we convert the rows back into equations:
0x + 1y - 1/2s1 + 1/2s2 + 0s3 + 0P = 12
0x + 0y - 7/4s1 + 1/4s2 + 1s3 + 0P = 4
1x + 0y + 3/4s1 - 1/4s2 + 0s3 + 0P = 3
0x + 0y + 5/4s1 + 1/4s2 + 0s3 + 1P = 33
We erase all the 0 terms and 1 coefficients:
y - 1/2s1 + 1/2s2 = 12
-7/4s1 + 1/4s2 + s3 = 4
x + 3/4s1 - 1/4s2 = 3
5/4s1 + 1/4s2 + P = 33
We solve the bottom equation for P
P = 33 - 5/4s1 - 1/4s2
Obviously P takes on its maximum value when nothing is
subtracted from the 33. This will be when s1 and s2 are
both 0. Substituting 0 for s1 and s2 in the above, we
have:
y = 12
s3 = 4
x = 3
---------------------------------------------------------
P = 33
So P has the maximum value of 33 when x=3, y=12, s1=0, s2=0
and s3=4
But we don't mention slack variables when we state our final
answer. So we say:
P has the maximum value of 33 when x=3 and y=12.
Edwin
|
|
|
