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.