• resource allocation
• to maximize profit.
• to minimize cost.

In a mixture problem limited resources are combined into products so that the profit from selling those products is at a maximum.
An optimal resource policy:

• is feasible
• gives maximum profit

Example 1: A clothing manufacturer has 60 yards of cloth to make shirts and vests. A shirt requires 3 yards and gives a profit of $5. A vest requires 2 yards and gives a profit of $3.
How many shirts and vests should she make?

Solution:
1.    Make a table to systematically represent the information:
 

	yards of cloth	profit P
shirts (x units)	3	5
vests (y units)	2	3
constraints	60

2.    Vertically interpret the columns to generate the constraint equations and the profit formula:

Constraints:
        x >= 0                        because we make 0 or more shirts,
        y >= 0                        0 or more vests
        3x + 2y <= 60            because x shirts and y vests use 3x +2y yards of cloth and that should be <= 60 yards

Profit:
        P = 5x + 3y                this is what we maximize

3.    Graph the constraint inequalities:

                if  x = 0 then  y<= 30                (0,30)
                if  y = 0 then  x<= 20                (20,0)  are the intercepts of  the line 3x + 20 = 60 with the coordinate axes.

                The inequalties mean that the area is underneath the slanted line, above the x-axis and to the right of the y-axis.

The constraint inequalities define the feasible region, which is the collection of all possible solution choices.
Among all solutions in the feasible region we have to find the one that maximizes the profit.

The Corner Point Principle says, that the maximal profit occurs at a corner point of the feasible region.

Profit computations for the corner points:
 

corner point	profit
(0,0)	0x5 + 0x3 = 0
(0,30)	0x5 + 30x3 = 90
(20,0)	20x5 + 0x3 = 100  *optimal

 here the optimal resource policy means that the lady makes 20 shirts and no vests.

Example 2:

A juice manufacturer sells two fruit beverages.
One gallon of cranapple is made from 3 quarts of cran and 1 quart of apple juice, profit: 3 cents/gallon.
One gallon of appleberry is made from 2 quarts of cran and 2 quarts of apple juice, profit: 4 cents/gallon.
Available today: 200 quarts of cran, 100 quarts of apple.

How many quarts of each mixture should he produce for greatest profit?

Note:
            More constraints, more corners
            More products, more dimensions than two

repeat until no improvement is possible any more

• start at a corner
• evaluate all neighboring corners
• travel next to the neighboring corner that has the greatest gain in profit.

Transportation Problem:  supply is matched to demand so as to minimize the overall transportation cost.

Example:
Three bakeries supply 8, 1, and 2 dozen loaves of bread. They are delivered to three stores:
3 dozen to the first store, 7 dozen to the second and 1 dozen to the third. There are transportation costs involved, as presented in the tableau. Which bakery should supply how many loaves to which store, so as to minimize the overall transportation cost?

 

	Stores:  1	2	3	breads baked
Bakeries:  I	8	9	3	8
II	15	1	12	1
III	1	3	5	2
breads needed	3	7	1	rim values

We would like to fill numbers into the colored fields so that their row sum equals the number of breads baked and the column sum equal the number of breads needed, that also minimizes transportation costs.

Mathematically:
Minimize        8x₁ + 9x₂ + 3x₃ + 15x₄ + 1x₅ + 12x₆ + 1x₇ + 3x₈ + 5x₉
subject to:

x₁ + x₂ + x₃ < = 8
x₄ + x₅ + x₆  <= 1
x₇ + x₈ + x₉  <= 2
x₁ + x₄ + x₇  >= 3
x₂ + x₅ + x₈  >= 7
x₃ + x₆ + x₉  >= 1
x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈, x₉ >= 0

• Northwest Corner Rule: will find an initial solution
• Stepping Stone Method: will improve a solution

• in the north west corner cell of the tableau, enter the smaller of the two rim values from row 1, col 1: say s, (circled cell)
• cross out the row/col that had the rim value s and reduce the other rim value by s
• when a single cell remains, there will be a tie for the rim conditions. Enter this amount.

 

 

	Stores:  1	2	3	breads baked
Bakeries:  I	8            3	9            5	3	8
II	15	1            1	12	1
III	1	3            1	5            1	2
breads needed	3	7	1	rim values

Analysis: the outcome of the Northwest Corner Rule is a feasible solution that does not take into account transportation cost. It may not be optimal.

A cell in the yellow table is described by (row,col), i.e. (I,3).
A circuit is a path through the cells in a tableau, where we are allowed to go left, right, up, or down, that starts and ends at the same place.
In order for a rectangular circuit to be legal, at least two diagonally opposite cells have to be filled.

Example: a legal circuit:  (I,3), (III,3), (III,2), (I,2), (I,3)  (the bold italic cells are diagonally opposite and filled)

The indicator value of a cell C is the cost change associated with increasing or decreasing the amounts shipped in a legal circuit of cells starting at C. It is computed by summing with alternating signs the costs of the cells in the circuit.

Example: the indicator value for the yellow cell (I,3) is  3 - 5  + 3 - 9 = -8

Stepping Stone Method

• start with an initial solution
• if there is a cell with a negative indicator value, ship an additional amount through that cell.

 

	Stores:  1	2	3	breads baked
Bakeries:  I	8            3	9            5-1	3           0+1	8
II	15	1            1	12	1
III	1	3            1+1	5            1-1	2
breads needed	3	7	1	rim values

Note how this preserves the row sums and the column sums.
Shipping x units through (I,3) will decrease the transportation cost by (-8)x, x times the indicator value of (I,3).

Example:

• find a legal circuit involving (III,1)
• compute the indicator value of (III,1)
• ship 2 units through (III,1)