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
               
   
   
2
1
1
0
0
0
|
9
   
 
1
1
0
1
0
0
|
6
 
 
0.5
1
0
0
0.5
0
|
5
 
 







 
 
-15
-20
0
0
0
1
|
0
 

 

-R3 + R1 --> R1
-R3 + R2 --> R2
20R3 + R4 --> R4
   
x1
x2
s1
s2
s3
P
   
s1
 
1.5
0
1
0
-0.5
0
|
4
  4/1.5 ~ 2.6
s2
0.5
0
0
1
-0.5
0
|
1
1/0.5 = 2 (smallest)
x2
0.5
1
0
0
0.5
0
|
5
5/0.5 = 10
 







 
 
-5
0
0
0
10
1
|
100
 

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
               
   
   
1.5
0
1
0
-0.5
0
|
4
   
 
1
0
0
2
-1
0
|
2
 
 
0.5
1
0
0
0.5
0
|
5
 
 







 
 
-5
0
0
0
10
1
|
100
 

...and here come the zeros:

-3/2R2 + R1 --> R1
-2R2 + R3 --> R3
5R2 + R4 --> R4
   
x1
x2
s1
s2
s3
P
   
s1
 
0
0
1
-3
-1
0
|
1
   
x1
1
0
0
2
-1
0
|
2
 
x2
0
1
0
-1
1
0
|
4
 
 







 
 
0
0
0
10
5
1
|
110
 

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

x1
x2
x3
s1
s2
P
   
x1
1
2
-1
1
0
0
|
5
   
s2
0
-4
5
-3
1
0
|
7
(only positive)








 
P
0
11
-6
4
0
1
|
20
 

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

         
   
 
1
2
-1
1
0
0
|
5
   
 
0
-0.8
1
-0.6
0.2
0
|
1.4
 
 







 
 
0
11
-6
4
0
1
|
20
 

Next we need to get zeros for the remaining entries in the pivot column:

R2 + R1 --> R1

6 R2 + R3 --> R3

x1
x2
x3
s1
s2
P
   
x1
1
1.2
0
0.4
0.2
0
|
6.4
   
x3
0
-0.8
1
-0.6
0.2
0
|
1.4
 








 
P
0
6.2
0
0.4
1.2
1
|
28.4
 

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.

 
   
x1
x2
x3
s1
s2
P
   
s1  
1000
2000
15000
1
0
0
|
20000
  20000 / 2000 = 10 (smallest)
s2
1
1
1
0
1
0
|
15
15 / 1 = 15
 





|

 
P
-14000
-24000
-18000
0
0
1
|
0
 

1/2000 R1 ---> R1
   
x1
x2
x3
s1
s2
P
   
s1  
1/2
1
3/4
1/2000
0
0
|
10
   
s2
1
1
1
0
1
0
|
15
 
 





|

 
P
-14000
-24000
-18000
0
0
1
|
0
 

-R1 + R,2 ---> R,2
24000 R1 + R3 --> R3
   
x1
x2
x3
s1
s2
P
   
x2  
1/2
1
3/4
1/2000
0
0
|
10
  10 / 0.5 = 20
s2
1/2
0
1/4
-1/2000
1
0
|
5
5 / 0.5 = 10 (smallest)
 





|

 
P
-2000
0
0
12
0
1
|
240000
 

Now it's time for another pivot operation. The first column is the pivot column. The second row is the pivot row. (see above)

2R2 --> 2
   
x1
x2
x3
s1
s2
P
   
x2  
1/2
1
3/4
1/2000
0
0
|
10
   
s2
1
0
1/2
-1/1000
2
0
|
10
 
 





|

 
P
-2000
0
0
12
0
1
|
240000
 

-1/2 R2 + R1 --> R1
2000 R2 + R3 --> R3
   
x1
x2
x3
s1
s2
P
   
x2  
0
1
1/2
1/1000
-1
0
|
5
   
x1
1
0
1/2
-1/1000
2
0
|
10
 
 





|

 
P
0
0
1000
10
4000
1
|
260000
 

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.