Section 5-4
(14)
Maximize
|
P = 15x1 + 20x2 |
subject to ...
|
2x1 + x2 ≤ 9 |
x1 + x2 ≤ 6 | |
x1 + 2x2 ≤ 10 | |
x1, x2, ≥ 0 |
There are three problem constraints, so there will be three slack variables. The system looks this way:
2x1
|
+ x2
|
+ s1
|
= 9 | |||
x1
|
+ x2
|
+ s2
|
= 6 | |||
x1
|
+ 2x2
|
+ s3
|
= 10 | |||
-15x1
|
- 20x2
|
+ P
|
= 0 |
Now this system is put into a simplex tableau.
x1
|
x2
|
s1
|
s2
|
s3
|
P
|
||||||
s1
|
2
|
1
|
1
|
0
|
0
|
0
|
|
|
9
|
9/1 = 9 | ||
s2
|
1
|
1
|
0
|
1
|
0
|
0
|
|
|
6
|
6/1 = 6 | ||
s3
|
1
|
2
|
0
|
0
|
1
|
0
|
|
|
10
|
10/2 = 5 (smallest) | ||
|
|
|
|
|
|
|
|
||||
-15
|
-20
|
0
|
0
|
0
|
1
|
|
|
0
|
From this tableau we can read off our starting BFS of x1=0,
x2=0,
s1=9, s2=6, s3=10, P=0.
There are negative indicatiors so we pick the pivot column (blue) and pivot
row (salmon).
Now we must do row operations to turn the pivot entry into a 1 and get 0's elsewhere
in the pivot column.
1/2R3 --> R3 |
|
-R3 + R1 --> R1 -R3 + R2 --> R2 20R3 + R4 --> R4 |
|
There's still a negative indicator, so we choose a new pivot row and pivot
column, illustrated above. Again we must do the row operations to change the
pivot element to a 1 and the remaining elements in the pivot column to 0's.
Here comes the 1 that we want:
2R2 --> R2 |
|
...and here come the zeros:
-3/2R2 + R1 --> R1 -2R2 + R3 --> R3 5R2 + R4 --> R4 |
|
Now there are no more negative indicators, a real cause for celebration! Reading off the final BFS from the tableau, we see that x1=2, x2=4, s1=1, s2=0, s3=0, P=110.
Thus P is maximized at 110 when x1=2 and x2=4,
(20)
Maximize... |
P = 4x1 - 3x2 + 2x3
|
Subject to... |
x1 + 2x2 - x3 ≤ 5
|
3x1 + 2x2 + 2x3
≤
22
|
|
x1, x2, x3 ≥ 0
|
There are two problem constraints, so there will be two slack variables. The system looks this way:
x1
|
+ 2x2
|
- x3
|
+ s1
|
= 5
|
||
3x1
|
+ 2x2
|
+ 2x3
|
+ s2
|
= 22
|
||
-4x1
|
+ 3x2
|
- 2x3
|
+ P
|
= 0
|
Now this system is put into a simplex tableau. The pivot column is blue and
the pivot row is salmon.
x1
|
x2
|
x3
|
s1
|
s2
|
P
|
||||||
s1
|
1
|
2
|
-1
|
1
|
0
|
0
|
|
|
5
|
5/1 = 5 | ||
s2
|
3
|
2
|
2
|
0
|
1
|
0
|
|
|
22
|
22/3 ~7.3 | ||
|
|
|
|
|
|
|
|
||||
P
|
-4
|
3
|
-2
|
0
|
0
|
1
|
|
|
0
|
Luckily, the pivot entry is already 1, so we don't have to multiply the pivot row. We just need to get the remaining entries of the pivot column to be zeros.
-3R1 + R2 --> R2 4R1 + R3 --> R3 |
|
At this point x1 has become basic and s1 has become nonbasic (i.e. zero). You can read off the BFS x1 = 5 , x2 = 0, x3 = 0, s1 = 0, s2 = 7, P = 20.
But there's still a negative indicator (-6) so we have to do another pivot operation. The pivot column is blue again. For the pivot row we have no choice other than row 2, because it contains the only nonnegative entry above the line in the pivot column. The pivot row is shown in salmon.
To start the second poivt operation, we must turn the pivot entry 5 into a 1:
1/5 R2 --> R2 |
|
Next we need to get zeros for the remaining entries in the pivot column:
R2 + R1 --> R1 6 R2 + R3 --> R3 |
|
There. There are no more negative indicators. We read off the following BFS:
x1 = 6.4, x2 = 0, x3
= 1.4, s1 = 0, s2 = 0, P = 28.4
Solution: Maximize P at 28.4 by setting x1 = 6.4, x2 = 0, x3 = 1.4.
(39)
Let x1 = number of daytime ads, x2
= number of primetime ads, and x3 = number of late night ads.
Then the total number of potential customers reached is 14000 x1
+ 24000 x2 + 1800 x3.
The total amount the chain is spending on the ads is 1000 x1
+ 2000 x2 + 1500 x3 dollars.
The TV station says that the total number x1
+ x2 + x3 of ads must not be greater than 15.
Thus we want to maximize the number of potential customers | P = 14000 x1 + 24000 x2 + 1800 x3 |
Subject to ... | 1000 x1 + 2000 x2 + 1500 x3 ≤ 20000 |
x1 + x2 + x3 ≤ 15 | |
x1, x2, x3 ≥ 0 |
There are 2 problem contraints, so there will be 2 slack variables. The system becomes:
1000 x1
|
+ 2000 x2
|
+ 1500 x3
|
+ s1
|
= 20000 | ||
x1
|
+ x2
|
+ x3
|
+ s2
|
= 15 | ||
-14000 x1
|
-24000 x2
|
- 18000 x3
|
+ P
|
= 0 |
Now we set up the simplex tableau. The pivot column is the second column. The pivot row is the first row.
|
1/2000 R1 ---> R1 |
|
-R1 + R,2 ---> R,2 24000 R1 + R3 --> R3 |
|
2R2 --> 2 |
|
-1/2 R2 + R1 --> R1 2000 R2 + R3 --> R3 |
|
Now there are no more negative indicators, so we are done. The potential customer contacts are maximized at P = 260000, when there are 10 daytime ads, 5 primetime ads, and 0 late night ads.
(41) First let's tabulate the data:
colonial
|
split level
|
ranch
|
available
|
|
acres |
0.5
|
0.5
|
1
|
30
|
capital ($) |
60,000
|
60,000
|
80,000
|
3,200,000
|
hours |
4,000
|
3,000
|
4,000
|
18,000
|
profit ($) |
20,000
|
18,000
|
24,000
|
We need to find out how many colonial, split-level, and ranch houses must be constructed to maximize profit. Thus,
Let x1 be number of colonial houses.
Let x2 be number of split-level houses.
Let x3 be number of ranch houses.
Then the profit which we want to maximize is P = 20,000x1 + 18,000x2
+ 24,000x3
Thus we want to maximize
|
P = 20,000x1 + 18,000x2 + 24,000x3 |
subject to ...
|
0.5x1 + 0.5x2 + x3 ≤ 30 |
60,000x1 + 60,000x2 + 80,000x3 ≤ 3,200,000 | |
4,000x1 + 3,000x2 + 4,000x3 ≤ 180,000 | |
x1, x2, x3 ≥ 0 |
Those are some mighty big numbers. There's no harm in dividing some of the lines by 1000, so let's do that to get the revised problem
maximize
|
P = 20x1 + 18x2 + 24x3 |
subject to ...
|
0.5x1 + 0.5x2 + x3 ≤ 30 |
60x1 + 60x2 + 80x3 ≤ 3,200 | |
4x1 + 3x2 + 4x3 ≤180 | |
x1, x2, x3 ≥ 0 |
That looks better. Remember though, P now represents profit in thousands of dollars.
There are three problem contraints, so there will be 3 slack variables. The system becomes:
0.5x1
|
+ 0.5x2
|
+ x3
|
+ s1
|
= 30 | ||
60x1
|
+ 60x2
|
+ 80x3
|
+ s2
|
= 3,200 | ||
4x1
|
+ 3x2
|
+ 4x3
|
+ s3 | = 180 | ||
-20x1
|
-18x2
|
- 24x3
|
+ P
|
= 0 |
Now we set up the simplex tableau.
x1
|
x2
|
x3
|
s1
|
s2
|
s3
|
P
|
||||||
s1
|
0.5
|
0.5
|
1
|
1
|
0
|
0
|
0
|
|
|
30
|
30/1 = 30 (smallest) | ||
s2
|
60
|
60
|
80
|
0
|
1
|
0
|
0
|
|
|
3,200
|
3200/80=40 | ||
s3
|
4
|
3
|
4
|
0
|
0
|
1
|
0
|
|
|
180
|
180/4 = 45 | ||
|
|
|
|
|
|
|
|
|
||||
P
|
-20
|
-18
|
-24
|
0
|
0
|
0
|
1
|
|
|
0
|
The pivot element is already 1. That's good. We just need to get zeros under
the pivot entry.
-80R1 + R2 --> R2
-4R1 + R3 --> R3
24R1 + R4 --> R4
x1
|
x2
|
x3
|
s1
|
s2
|
s3
|
P
|
||||||
x3
|
0.5
|
0.5
|
1
|
1
|
0
|
0
|
0
|
|
|
30
|
30/0.5 = 60 | ||
s2
|
20
|
20
|
0
|
-80
|
1
|
0
|
0
|
|
|
800
|
800/20 = 40 | ||
s3
|
2
|
1
|
0
|
-4
|
0
|
1
|
0
|
|
|
60
|
60/2 = 30 (smallest) | ||
|
|
|
|
|
|
|
|
|
||||
P
|
-8
|
-6
|
0
|
24
|
0
|
0
|
1
|
|
|
720
|
1/2R3 --> R3
0.5
|
0.5
|
1
|
1
|
0
|
0
|
0
|
|
|
30
|
||||
20
|
20
|
0
|
-80
|
1
|
0
|
0
|
|
|
800
|
||||
1
|
0.5
|
0
|
-2
|
0
|
0.5
|
0
|
|
|
30
|
||||
|
|
|
|
|
|
|
|
|
||||
-8
|
-6
|
0
|
24
|
0
|
0
|
1
|
|
|
720
|
-1/2R3 + R1 --> R1
-2R3 + R2 --> R2
8R3 + R4 --> R4
x1
|
x2
|
x3
|
s1
|
s2
|
s3
|
P
|
||||||
x3
|
0
|
0.25
|
1
|
2
|
0
|
-.25
|
0
|
|
|
15
|
15/.25=60 | ||
s2
|
0
|
1
|
0
|
-40
|
1
|
-10
|
0
|
|
|
200
|
200/10=20(smallest) | ||
x1
|
1
|
0.5
|
0
|
-2
|
0
|
0.5
|
0
|
|
|
30
|
30/0.5=60 | ||
|
|
|
|
|
|
|
|
|
||||
P
|
0
|
-2
|
0
|
8
|
0
|
4
|
1
|
|
|
960
|
There's still a negative indicator above, so it's time for another pivot operation.
The pivot row and column are indicated above.
-1/4R2 + R1 --> R1
-1/2R2 + R3 --> R3
2R2 + R4 --> R4
x1
|
x2
|
x3
|
s1
|
s2
|
s3
|
P
|
||||||
x3
|
0
|
0
|
1
|
3
|
-0.25
|
0
|
0
|
|
|
10
|
|||
x2
|
0
|
1
|
0
|
-4
|
1
|
-1
|
0
|
|
|
20
|
|||
x1
|
1
|
0
|
0
|
0
|
-0.5
|
1
|
0
|
|
|
20
|
|||
|
|
|
|
|
|
|
|
|
||||
P
|
0
|
0
|
0
|
0
|
2
|
2
|
1
|
|
|
1000
|
There are no longer any negative indicators, so we can now read off the final solution. There will be a profit of a cool million by building 10 ranch houses, 20 split-levels, and 20 colonial styles. (recall that the P=1000 means the profit is 1000 thousand dollars, i.e. one million dollars.)
Frankly, though, this kind of development is bad for the environment. Instead of building all those houses, the developer should donate his capital to the Sierra Club.