Operations Research - Linear Programming

Economics Application - Cost Minimization

by

Elmer G. Wiens

Egwald's popular web pages are provided without cost to users.

FormTable =

The Egwald's Coffee Import Decision.

Egwald's Coffee, a purveyor of speciality coffee, imports Yemen Mocha and Ethopian Harrar coffee beans from the Middle East, and Java and Sumatra coffee beans from Indonesia. Egwald has a standing order with coffee merchants for at least one hundred bags (60 kilos per bag) of "green coffee beans" every three months for each single-origin coffee, plus additional coffee beans as required, all at the prevailing prices.

After a secret process of aging, roasting, and blending, Egwald markets this coffee, generically known as Mocha-Java, under the trade name of MoJo Coffee Egwald. Egwald blends the roasted beans according to four formulae. Formula 1 combines 1 part Mocha with 2 parts Java; Formula 2 combines 1 part Mocha with 2 parts Sumatra; Formula 3 combines 1 part Harrar with 2 parts Java; Formula 4 combines 1 part Harrar with 2 parts Sumatra. At the beginning of each quarter of the year, Egwald estimates the demand for MoJo Coffee Egwald, and orders quantities of green coffee beans to replenish inventories based on the prevailing coffee bean prices, taking into consideration the differentials in direct costs associated with processing beans according to each formula.

Egwald's decision involves minimizing the cost of producing MoJo - a least cost formulation problem - subject to expected quarterly demand from coffee lovers for MoJo, the price of green coffee beans, and processing costs for each blend of MoJo coffee.

Define the variables of the problem according to the following table:

 Formula Mocha Harrar Java Sumatra MoJo Blend 1 x1 x5 x9 Blend 2 x2 x7 x10 Blend 3 x3 x6 x11 Blend 4 x4 x8 x12

The first line in the table reads that the formula for blend 1 of MoJo combines Mocha and Java roasted coffee beans; the second line reads that the formula for blend 2 combines Mocha and Sumatra roasted coffee beans; etc.

The second table illustrates Egwald Coffee's quarterly standing default order from each single-origin coffee supplier:

 Mocha x1 + x2 >= 100 Harrar x3 + x4 >= 100 Java x5 + x6 >= 100 Sumatra x7 + x8 >= 100

The third table illustrates quantity balance constraints for each blend. The first row reads that at least x1 sacks of Mocha plus x5 sacks of Java are required to produce x9 sacks of Bend 1 MoJo.

 Blend 1 x1 + x5 - x9 >= 0 Blend 2 x2 + x7 - x10 >= 0 Blend 3 x3 + x6 - x11 >= 0 Blend 4 x4 + x8 - x12 >= 0

The fourth table illustrates the demand constraint for all blends. The sum of all blends of MoJo produced must exceed 1000 sacks of roasted MoJo coffee beans to supply minimum anticipated demand.

 MoJo x9 + x10 + x11 + x12 >= 1000

Egwald Coffee's MoJo formulae combine one unit of Middle East coffee with two units of Indonesian coffee. The fifth table ensures that the appropriate quantity of each bean is used in each blend of MoJo.

 Formula 1 2*x1 - x5 = 0 Formula 2 2*x2 - x7 = 0 Formula 3 2*x3 - x6 = 0 Formula 4 2*x4 - x8 = 0

The sixth table illustrates green coffee bean prices per pound, and per 60 kilo bag (1 kilo = 2.21 lbs).

Green coffee bean prices: \$ per pound.
MochoHarrarJavaSumatra
x1x2x3x4x5x6x7x8
Green coffee bean prices: \$ per sack.
c1c2c3c4c5c6c7c8
165.75165.75152.49152.4992.8292.8299.4599.45

The last table contains the processing costs per pound, and per 60 kilo sack, for each blend of MoJo Coffee.

Processing costs: \$ per pound.
x9x10x11x12
Processing costs: \$ per sack.
c9c10c11c12
14.5910.6111.939.28

Solution Sensitivity Analysis.

To perform a sensitivity analysis of the firms linear programming problem, change the data above, and click "Submit L.P." below. A new web page will display with the firm's data updated with your new data, and the firm's new optimal least cost program. Compare the new results with the results of the current web page.

 Use Original Data: No     Yes

Dual Simplex Solution.

The primal objective of the Egwald's Coffee is to minimize costs, by ordering appropriate amounts of coffee beans. The firm's primal production decision is captured in the firm's Primal Linear Programming Problem, where I multiplied the coefficients of the objective function, in \$ per sack, by -1 to turn the minimization problem into a maximization problem.

Primal Linear Program
Maximize the Objective Function (P)
 P = -165.75 * x1 + -165.75 * x2 + -152.49 * x3 + -152.49 * x4 + -92.82 * x5 + -92.82 * x6 + -99.45 * x7 + -99.45 * x8             + -14.59 * x9 + -10.61 * x10 + -11.93 * x11 + -9.28 * x12

subject to the constraints

 M: 1 * x1 + 1 * x2 + 0 * x3 + 0 * x4 + 0 * x5 + 0 * x6 + 0 * x7 + 0 * x8 + 0 * x9 + 0 * x10 + 0 * x11 + 0 * x12 >= 100 H: 0 * x1 + 0 * x2 + 1 * x3 + 1 * x4 + 0 * x5 + 0 * x6 + 0 * x7 + 0 * x8 + 0 * x9 + 0 * x10 + 0 * x11 + 0 * x12 >= 100 J: 0 * x1 + 0 * x2 + 0 * x3 + 0 * x4 + 1 * x5 + 1 * x6 + 0 * x7 + 0 * x8 + 0 * x9 + 0 * x10 + 0 * x11 + 0 * x12 >= 100 S: 0 * x1 + 0 * x2 + 0 * x3 + 0 * x4 + 0 * x5 + 0 * x6 + 1 * x7 + 1 * x8 + 0 * x9 + 0 * x10 + 0 * x11 + 0 * x12 >= 100 B1: 1 * x1 + 0 * x2 + 0 * x3 + 0 * x4 + 1 * x5 + 0 * x6 + 0 * x7 + 0 * x8 + -1 * x9 + 0 * x10 + 0 * x11 + 0 * x12 >= 0 B2: 0 * x1 + 1 * x2 + 0 * x3 + 0 * x4 + 0 * x5 + 0 * x6 + 1 * x7 + 0 * x8 + 0 * x9 + -1 * x10 + 0 * x11 + 0 * x12 >= 0 B3: 0 * x1 + 0 * x2 + 1 * x3 + 0 * x4 + 0 * x5 + 1 * x6 + 0 * x7 + 0 * x8 + 0 * x9 + 0 * x10 + -1 * x11 + 0 * x12 >= 0 B4: 0 * x1 + 0 * x2 + 0 * x3 + 1 * x4 + 0 * x5 + 0 * x6 + 0 * x7 + 1 * x8 + 0 * x9 + 0 * x10 + 0 * x11 + -1 * x12 >= 0 MJ: 0 * x1 + 0 * x2 + 0 * x3 + 0 * x4 + 0 * x5 + 0 * x6 + 0 * x7 + 0 * x8 + 1 * x9 + 1 * x10 + 1 * x11 + 1 * x12 >= 1000 F1: 2 * x1 + 0 * x2 + 0 * x3 + 0 * x4 + -1 * x5 + 0 * x6 + 0 * x7 + 0 * x8 + 0 * x9 + 0 * x10 + 0 * x11 + 0 * x12 = 0 F2: 0 * x1 + 2 * x2 + 0 * x3 + 0 * x4 + 0 * x5 + 0 * x6 + -1 * x7 + 0 * x8 + 0 * x9 + 0 * x10 + 0 * x11 + 0 * x12 = 0 F3: 0 * x1 + 0 * x2 + 2 * x3 + 0 * x4 + 0 * x5 + -1 * x6 + 0 * x7 + 0 * x8 + 0 * x9 + 0 * x10 + 0 * x11 + 0 * x12 = 0 F4: 0 * x1 + 0 * x2 + 0 * x3 + 2 * x4 + 0 * x5 + 0 * x6 + 0 * x7 + -1 * x8 + 0 * x9 + 0 * x10 + 0 * x11 + 0 * x12 = 0
 x1 >= 0; x2 >= 0; x3 >= 0; x4 >= 0; x5 >= 0; x6 >= 0; x7 >= 0; x8 >= 0; x9 >= 0; x10 >= 0; x11 >= 0; x12 >= 0;

 Using matrix notation this is: Primal Linear Program Maximize the Objective Function (P) P = cT x subject to A x >= b, x >= 0

The standard form for the initial dual simplex tableau is:

 Initial Tableau b A I3 0 -cT O3T

In the dual simplex algorithm, a sequence of tableaux are calculated. A given Tableauk has the form:

 Tableauk ß U B µ tT yT
=
 Tableauk ß U µ Ø

after consolidating the center 2 by 2 block of matrices.

 Phase 0 - drive all artificial variables (associated with = constraints) to zero, i.e. eliminate them from the basis; Phase I - find a tableau with Ø >= 0, i.e. a feasible dual program; Phase II - generate tableaux that decrease the value of µ turning ß >= 0, without dropping back into Phase 0 or I, i.e. find a feasible basic dual program that minimizes the objective function D.

The Tableaux of the Dual Simplex Method.

Phase 0: Drive the artificial variables from the basis.

 Tableau0 b0 x01 x02 x03 x04 x05 x06 x07 x08 x09 x010 x011 x012 s01 s02 s03 s04 s05 s06 s07 s08 s09 s*010 s*011 s*012 s*013 rowsum M0 -100 -1 -1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 -101 H0 -100 0 0 -1 -1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 -101 J0 -100 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 -101 S0 -100 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 -101 B10 0 -1 0 0 0 -1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 B20 0 0 -1 0 0 0 0 -1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 B30 0 0 0 -1 0 0 -1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 B40 0 0 0 0 -1 0 0 0 -1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 MJ0 -1000 0 0 0 0 0 0 0 0 -1 -1 -1 -1 0 0 0 0 0 0 0 0 1 0 0 0 0 -1003 F10 0 -2 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 F20 0 0 -2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 F30 0 0 0 -2 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 F40 0 0 0 0 -2 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 P0 0 165.8 165.8 152.5 152.5 92.8 92.8 99.5 99.5 14.6 10.6 11.9 9.3 0 0 0 0 0 0 0 0 0 0 0 0 0 1067.4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Basis for Tableau0: [s1, s2, s3, s4, s5, s6, s7, s8, s9, s10, s11, s12, s13, ]. Value of Objective Function = 0.

Proceed to the next tableau as follows:

Phase 0: Drive the artificial variables from the basis.

A. In Tableau0:

1. Select an artificial variable in the basis: s*13.

2. Select a nonzero element in row F4 as pivot: x13,4 = -2. The pivot column = 4.

B. To create Tableau1:

3. Compute row F41 = F40 / (-2).

4. Subtract multiples of row F41 from all other rows of Tableau0 so that column x14 = e13 in Tableau1.

 Tableau1 b1 x11 x12 x13 x14 x15 x16 x17 x18 x19 x110 x111 x112 s11 s12 s13 s14 s15 s16 s17 s18 s19 s*110 s*111 s*112 s*113 rowsum M1 -100 -1 -1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 -101 H1 -100 0 0 -1 0 0 0 0 -0.5 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 -0.5 -101 J1 -100 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 -101 S1 -100 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 -101 B11 0 -1 0 0 0 -1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 B21 0 0 -1 0 0 0 0 -1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 B31 0 0 0 -1 0 0 -1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 B41 0 0 0 0 0 0 0 0 -1.5 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 MJ1 -1000 0 0 0 0 0 0 0 0 -1 -1 -1 -1 0 0 0 0 0 0 0 0 1 0 0 0 0 -1003 F11 0 -2 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 F21 0 0 -2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 F31 0 0 0 -2 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 F41 0 0 0 0 1 0 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 P1 0 165.8 165.8 152.5 0 92.8 92.8 99.5 175.7 14.6 10.6 11.9 9.3 0 0 0 0 0 0 0 0 0 0 0 0 76.2 1067.4 -P1 / F31 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Basis for Tableau1: [s1, s2, s3, s4, s5, s6, s7, s8, s9, s10, s11, s12, x4, ]. Value of Objective Function = 0.

Proceed to the next tableau as follows:

Phase 0: Drive the artificial variables from the basis.

A. In Tableau1:

1. Select an artificial variable in the basis: s*12.

2. Select a nonzero element in row F3 as pivot: x12,3 = -2. The pivot column = 3.

B. To create Tableau2:

3. Compute row F32 = F31 / (-2).

4. Subtract multiples of row F32 from all other rows of Tableau1 so that column x23 = e12 in Tableau2.

 Tableau2 b2 x21 x22 x23 x24 x25 x26 x27 x28 x29 x210 x211 x212 s21 s22 s23 s24 s25 s26 s27 s28 s29 s*210 s*211 s*212 s*213 rowsum M2 -100 -1 -1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 -101 H2 -100 0 0 0 0 0 -0.5 0 -0.5 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 -0.5 -0.5 -101 J2 -100 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 -101 S2 -100 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 -101 B12 0 -1 0 0 0 -1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 B22 0 0 -1 0 0 0 0 -1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 B32 0 0 0 0 0 0 -1.5 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 0 B42 0 0 0 0 0 0 0 0 -1.5 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 MJ2 -1000 0 0 0 0 0 0 0 0 -1 -1 -1 -1 0 0 0 0 0 0 0 0 1 0 0 0 0 -1003 F12 0 -2 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 F22 0 0 -2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 F32 0 0 0 1 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 0 F42 0 0 0 0 1 0 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 P2 0 165.8 165.8 0 0 92.8 169.1 99.5 175.7 14.6 10.6 11.9 9.3 0 0 0 0 0 0 0 0 0 0 0 76.2 76.2 1067.4 -P2 / F22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Basis for Tableau2: [s1, s2, s3, s4, s5, s6, s7, s8, s9, s10, s11, x3, x4, ]. Value of Objective Function = 0.

Proceed to the next tableau as follows:

Phase 0: Drive the artificial variables from the basis.

A. In Tableau2:

1. Select an artificial variable in the basis: s*11.

2. Select a nonzero element in row F2 as pivot: x11,2 = -2. The pivot column = 2.

B. To create Tableau3:

3. Compute row F23 = F22 / (-2).

4. Subtract multiples of row F23 from all other rows of Tableau2 so that column x32 = e11 in Tableau3.

 Tableau3 b3 x31 x32 x33 x34 x35 x36 x37 x38 x39 x310 x311 x312 s31 s32 s33 s34 s35 s36 s37 s38 s39 s*310 s*311 s*312 s*313 rowsum M3 -100 -1 0 0 0 0 0 -0.5 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 -0.5 0 0 -101 H3 -100 0 0 0 0 0 -0.5 0 -0.5 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 -0.5 -0.5 -101 J3 -100 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 -101 S3 -100 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 -101 B13 0 -1 0 0 0 -1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 B23 0 0 0 0 0 0 0 -1.5 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 0 0 B33 0 0 0 0 0 0 -1.5 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 0 B43 0 0 0 0 0 0 0 0 -1.5 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 MJ3 -1000 0 0 0 0 0 0 0 0 -1 -1 -1 -1 0 0 0 0 0 0 0 0 1 0 0 0 0 -1003 F13 0 -2 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 F23 0 0 1 0 0 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 0 0 F33 0 0 0 1 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 0 F43 0 0 0 0 1 0 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 P3 0 165.8 0 0 0 92.8 169.1 182.3 175.7 14.6 10.6 11.9 9.3 0 0 0 0 0 0 0 0 0 0 82.9 76.2 76.2 1067.4 -P3 / F13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Basis for Tableau3: [s1, s2, s3, s4, s5, s6, s7, s8, s9, s10, x2, x3, x4, ]. Value of Objective Function = 0.

Proceed to the next tableau as follows:

Phase 0: Drive the artificial variables from the basis.

A. In Tableau3:

1. Select an artificial variable in the basis: s*10.

2. Select a nonzero element in row F1 as pivot: x10,1 = -2. The pivot column = 1.

B. To create Tableau4:

3. Compute row F14 = F13 / (-2).

4. Subtract multiples of row F14 from all other rows of Tableau3 so that column x41 = e10 in Tableau4.

Phase II: Goal: get ß >= 0.

 Tableau4 b4 x41 x42 x43 x44 x45 x46 x47 x48 x49 x410 x411 x412 s41 s42 s43 s44 s45 s46 s47 s48 s49 s*410 s*411 s*412 s*413 rowsum M4 -100 0 0 0 0 -0.5 0 -0.5 0 0 0 0 0 1 0 0 0 0 0 0 0 0 -0.5 -0.5 0 0 -101 H4 -100 0 0 0 0 0 -0.5 0 -0.5 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 -0.5 -0.5 -101 J4 -100 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 -101 S4 -100 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 -101 B14 0 0 0 0 0 -1.5 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 0 0 0 B24 0 0 0 0 0 0 0 -1.5 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 0 0 B34 0 0 0 0 0 0 -1.5 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 0 B44 0 0 0 0 0 0 0 0 -1.5 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 MJ4 -1000 0 0 0 0 0 0 0 0 -1 -1 -1 -1 0 0 0 0 0 0 0 0 1 0 0 0 0 -1003 F14 0 1 0 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 0 0 0 F24 0 0 1 0 0 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 0 0 F34 0 0 0 1 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 0 F44 0 0 0 0 1 0 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 P4 0 0 0 0 0 175.7 169.1 182.3 175.7 14.6 10.6 11.9 9.3 0 0 0 0 0 0 0 0 0 82.9 82.9 76.2 76.2 1067.4 -P4 / MJ4 0 0 0 0 0 0 0 0 0 14.6 10.6 11.9 9.3 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Basis for Tableau4: [s1, s2, s3, s4, s5, s6, s7, s8, s9, x1, x2, x3, x4, ]. Value of Objective Function = 0.

Proceed to the next tableau as follows:

Phase 0: Complete.

Phase I: Complete.

Phase II: Goal: get ß >= 0.

A. In Tableau4:

1. Select a pivot row, row, with b4row < 0: row = 9 associated with b49 = -1000.

2. Compute the ratios -Ø / MJ as per the last row. Discard ratios which are not positive and ratios associated with artificial variables. Select the column with the least positive ratio as the pivot column: col = 12 associated with 9.3. Thus x9,12 = -1 is the pivot; variable s9 will leave the basis; variable x12 will enter the basis.

B. To create Tableau5:

3. Compute row MJ5 = MJ4 / (-1).

3. Subtract multiples of row MJ5 from all other rows of Tableau4 so that column x12 = e9 in Tableau5.

 Tableau5 b5 x51 x52 x53 x54 x55 x56 x57 x58 x59 x510 x511 x512 s51 s52 s53 s54 s55 s56 s57 s58 s59 s*510 s*511 s*512 s*513 rowsum M5 -100 0 0 0 0 -0.5 0 -0.5 0 0 0 0 0 1 0 0 0 0 0 0 0 0 -0.5 -0.5 0 0 -101 H5 -100 0 0 0 0 0 -0.5 0 -0.5 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 -0.5 -0.5 -101 J5 -100 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 -101 S5 -100 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 -101 B15 0 0 0 0 0 -1.5 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 0 0 0 B25 0 0 0 0 0 0 0 -1.5 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 0 0 B35 0 0 0 0 0 0 -1.5 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 0 B45 -1000 0 0 0 0 0 0 0 -1.5 -1 -1 -1 0 0 0 0 0 0 0 0 1 1 0 0 0 -0.5 -1003 MJ5 1000 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 1003 F15 0 1 0 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 0 0 0 F25 0 0 1 0 0 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 0 0 F35 0 0 0 1 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 0 F45 0 0 0 0 1 0 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 P5 -9282 0 0 0 0 175.7 169.1 182.3 175.7 5.3 1.3 2.7 0 0 0 0 0 0 0 0 0 9.3 82.9 82.9 76.2 76.2 -8242.4 -P5 / B45 0 0 0 0 0 0 0 0 117.1 5.3 1.3 2.7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Basis for Tableau5: [s1, s2, s3, s4, s5, s6, s7, s8, x12, x1, x2, x3, x4, ]. Value of Objective Function = -9282.

Proceed to the next tableau as follows:

Phase 0: Complete.

Phase I: Complete.

Phase II: Goal: get ß >= 0.

A. In Tableau5:

1. Select a pivot row, row, with b5row < 0: row = 8 associated with b58 = -1000.

2. Compute the ratios -Ø / B4 as per the last row. Discard ratios which are not positive and ratios associated with artificial variables. Select the column with the least positive ratio as the pivot column: col = 10 associated with 1.3. Thus x8,10 = -1 is the pivot; variable s8 will leave the basis; variable x10 will enter the basis.

B. To create Tableau6:

3. Compute row B46 = B45 / (-1).

3. Subtract multiples of row B46 from all other rows of Tableau5 so that column x10 = e8 in Tableau6.

 Tableau6 b6 x61 x62 x63 x64 x65 x66 x67 x68 x69 x610 x611 x612 s61 s62 s63 s64 s65 s66 s67 s68 s69 s*610 s*611 s*612 s*613 rowsum M6 -100 0 0 0 0 -0.5 0 -0.5 0 0 0 0 0 1 0 0 0 0 0 0 0 0 -0.5 -0.5 0 0 -101 H6 -100 0 0 0 0 0 -0.5 0 -0.5 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 -0.5 -0.5 -101 J6 -100 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 -101 S6 -100 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 -101 B16 0 0 0 0 0 -1.5 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 0 0 0 B26 -1000 0 0 0 0 0 0 -1.5 -1.5 -1 0 -1 0 0 0 0 0 0 1 0 1 1 0 -0.5 0 -0.5 -1003 B36 0 0 0 0 0 0 -1.5 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 0 B46 1000 0 0 0 0 0 0 0 1.5 1 1 1 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0.5 1003 MJ6 0 0 0 0 0 0 0 0 -1.5 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 F16 0 1 0 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 0 0 0 F26 0 0 1 0 0 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 0 0 F36 0 0 0 1 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 0 F46 0 0 0 0 1 0 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 P6 -10608 0 0 0 0 175.7 169.1 182.3 173.7 4 0 1.3 0 0 0 0 0 0 0 0 1.3 10.6 82.9 82.9 76.2 75.6 -9572.4 -P6 / B26 0 0 0 0 0 0 0 121.6 115.8 4 0 1.3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Basis for Tableau6: [s1, s2, s3, s4, s5, s6, s7, x10, x12, x1, x2, x3, x4, ]. Value of Objective Function = -10608.

Proceed to the next tableau as follows:

Phase 0: Complete.

Phase I: Complete.

Phase II: Goal: get ß >= 0.

A. In Tableau6:

1. Select a pivot row, row, with b6row < 0: row = 6 associated with b66 = -1000.

2. Compute the ratios -Ø / B2 as per the last row. Discard ratios which are not positive and ratios associated with artificial variables. Select the column with the least positive ratio as the pivot column: col = 11 associated with 1.3. Thus x6,11 = -1 is the pivot; variable s6 will leave the basis; variable x11 will enter the basis.

B. To create Tableau7:

3. Compute row B27 = B26 / (-1).

3. Subtract multiples of row B27 from all other rows of Tableau6 so that column x11 = e6 in Tableau7.

 Tableau7 b7 x71 x72 x73 x74 x75 x76 x77 x78 x79 x710 x711 x712 s71 s72 s73 s74 s75 s76 s77 s78 s79 s*710 s*711 s*712 s*713 rowsum M7 -100 0 0 0 0 -0.5 0 -0.5 0 0 0 0 0 1 0 0 0 0 0 0 0 0 -0.5 -0.5 0 0 -101 H7 -100 0 0 0 0 0 -0.5 0 -0.5 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 -0.5 -0.5 -101 J7 -100 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 -101 S7 -100 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 -101 B17 0 0 0 0 0 -1.5 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 0 0 0 B27 1000 0 0 0 0 0 0 1.5 1.5 1 0 1 0 0 0 0 0 0 -1 0 -1 -1 0 0.5 0 0.5 1003 B37 -1000 0 0 0 0 0 -1.5 -1.5 -1.5 -1 0 0 0 0 0 0 0 0 1 1 1 1 0 -0.5 -0.5 -0.5 -1003 B47 0 0 0 0 0 0 0 -1.5 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 0 0 MJ7 0 0 0 0 0 0 0 0 -1.5 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 F17 0 1 0 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 0 0 0 F27 0 0 1 0 0 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 0 0 F37 0 0 0 1 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 0 F47 0 0 0 0 1 0 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 P7 -11934 0 0 0 0 175.7 169.1 180.3 171.7 2.7 0 0 0 0 0 0 0 0 1.3 0 2.7 11.9 82.9 82.2 76.2 74.9 -10902.4 -P7 / B37 0 0 0 0 0 0 112.7 120.2 114.5 2.7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Basis for Tableau7: [s1, s2, s3, s4, s5, x11, s7, x10, x12, x1, x2, x3, x4, ]. Value of Objective Function = -11934.

Proceed to the next tableau as follows:

Phase 0: Complete.

Phase I: Complete.

Phase II: Goal: get ß >= 0.

A. In Tableau7:

1. Select a pivot row, row, with b7row < 0: row = 7 associated with b77 = -1000.

2. Compute the ratios -Ø / B3 as per the last row. Discard ratios which are not positive and ratios associated with artificial variables. Select the column with the least positive ratio as the pivot column: col = 9 associated with 2.7. Thus x7,9 = -1 is the pivot; variable s7 will leave the basis; variable x9 will enter the basis.

B. To create Tableau8:

3. Compute row B38 = B37 / (-1).

3. Subtract multiples of row B38 from all other rows of Tableau7 so that column x9 = e7 in Tableau8.

 Tableau8 b8 x81 x82 x83 x84 x85 x86 x87 x88 x89 x810 x811 x812 s81 s82 s83 s84 s85 s86 s87 s88 s89 s*810 s*811 s*812 s*813 rowsum M8 -100 0 0 0 0 -0.5 0 -0.5 0 0 0 0 0 1 0 0 0 0 0 0 0 0 -0.5 -0.5 0 0 -101 H8 -100 0 0 0 0 0 -0.5 0 -0.5 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 -0.5 -0.5 -101 J8 -100 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 -101 S8 -100 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 -101 B18 -1000 0 0 0 0 -1.5 -1.5 -1.5 -1.5 0 0 0 0 0 0 0 0 1 1 1 1 1 -0.5 -0.5 -0.5 -0.5 -1003 B28 0 0 0 0 0 0 -1.5 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 0 B38 1000 0 0 0 0 0 1.5 1.5 1.5 1 0 0 0 0 0 0 0 0 -1 -1 -1 -1 0 0.5 0.5 0.5 1003 B48 0 0 0 0 0 0 0 -1.5 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 0 0 MJ8 0 0 0 0 0 0 0 0 -1.5 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 F18 0 1 0 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 0 0 0 F28 0 0 1 0 0 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 0 0 F38 0 0 0 1 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 0 F48 0 0 0 0 1 0 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 P8 -14586 0 0 0 0 175.7 165.1 176.4 167.7 0 0 0 0 0 0 0 0 0 4 2.7 5.3 14.6 82.9 80.9 74.9 73.6 -13562.3 -P8 / B18 0 0 0 0 0 117.1 110.1 117.6 111.8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Basis for Tableau8: [s1, s2, s3, s4, s5, x11, x9, x10, x12, x1, x2, x3, x4, ]. Value of Objective Function = -14586.

Proceed to the next tableau as follows:

Phase 0: Complete.

Phase I: Complete.

Phase II: Goal: get ß >= 0.

A. In Tableau8:

1. Select a pivot row, row, with b8row < 0: row = 5 associated with b85 = -1000.

2. Compute the ratios -Ø / B1 as per the last row. Discard ratios which are not positive and ratios associated with artificial variables. Select the column with the least positive ratio as the pivot column: col = 6 associated with 110.1. Thus x5,6 = -1.5 is the pivot; variable s5 will leave the basis; variable x6 will enter the basis.

B. To create Tableau9:

3. Compute row B19 = B18 / (-1.5).

3. Subtract multiples of row B19 from all other rows of Tableau8 so that column x6 = e5 in Tableau9.

 Tableau9 b9 x91 x92 x93 x94 x95 x96 x97 x98 x99 x910 x911 x912 s91 s92 s93 s94 s95 s96 s97 s98 s99 s*910 s*911 s*912 s*913 rowsum M9 -100 0 0 0 0 -0.5 0 -0.5 0 0 0 0 0 1 0 0 0 0 0 0 0 0 -0.5 -0.5 0 0 -101 H9 233.3 0 0 0 0 0.5 0 0.5 0 0 0 0 0 0 1 0 0 -0.3 -0.3 -0.3 -0.3 -0.3 0.2 0.2 -0.3 -0.3 233.3 J9 566.7 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 -0.7 -0.7 -0.7 -0.7 -0.7 0.3 0.3 0.3 0.3 567.7 S9 -100 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 -101 B19 666.7 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 -0.7 -0.7 -0.7 -0.7 -0.7 0.3 0.3 0.3 0.3 668.7 B29 1000 0 0 0 0 1.5 0 1.5 1.5 0 0 1 0 0 0 0 0 -1 -1 0 -1 -1 0.5 0.5 0 0.5 1003 B39 0 0 0 0 0 -1.5 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 0 0 0 B49 0 0 0 0 0 0 0 -1.5 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 0 0 MJ9 0 0 0 0 0 0 0 0 -1.5 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 F19 0 1 0 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 0 0 0 F29 0 0 1 0 0 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 0 0 F39 333.3 0 0 1 0 0.5 0 0.5 0.5 0 0 0 0 0 0 0 0 -0.3 -0.3 -0.3 -0.3 -0.3 0.2 0.2 -0.3 0.2 334.3 F49 0 0 0 0 1 0 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 P9 -124644 0 0 0 0 10.6 0 11.3 2.7 0 0 0 0 0 0 0 0 110.1 114 112.7 115.4 124.6 27.8 25.9 19.9 18.6 -123950.5 -P9 / M9 0 0 0 0 0 21.2 0 22.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Basis for Tableau9: [s1, s2, s3, s4, x6, x11, x9, x10, x12, x1, x2, x3, x4, ]. Value of Objective Function = -124644.

Proceed to the next tableau as follows:

Phase 0: Complete.

Phase I: Complete.

Phase II: Goal: get ß >= 0.

A. In Tableau9:

1. Select a pivot row, row, with b9row < 0: row = 1 associated with b91 = -100.

2. Compute the ratios -Ø / M as per the last row. Discard ratios which are not positive and ratios associated with artificial variables. Select the column with the least positive ratio as the pivot column: col = 5 associated with 21.2. Thus x1,5 = -0.5 is the pivot; variable s1 will leave the basis; variable x5 will enter the basis.

B. To create Tableau10:

3. Compute row M10 = M9 / (-0.5).

3. Subtract multiples of row M10 from all other rows of Tableau9 so that column x5 = e1 in Tableau10.

 Tableau10 b10 x101 x102 x103 x104 x105 x106 x107 x108 x109 x1010 x1011 x1012 s101 s102 s103 s104 s105 s106 s107 s108 s109 s*1010 s*1011 s*1012 s*1013 rowsum M10 200 0 0 0 0 1 0 1 0 0 0 0 0 -2 0 0 0 0 0 0 0 0 1 1 0 0 202 H10 133.3 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 -0.3 -0.3 -0.3 -0.3 -0.3 -0.3 -0.3 -0.3 -0.3 132.3 J10 566.7 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 -0.7 -0.7 -0.7 -0.7 -0.7 0.3 0.3 0.3 0.3 567.7 S10 -100 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 -101 B110 466.7 0 0 0 0 0 1 0 1 0 0 0 0 2 0 0 0 -0.7 -0.7 -0.7 -0.7 -0.7 -0.7 -0.7 0.3 0.3 466.7 B210 700 0 0 0 0 0 0 0 1.5 0 0 1 0 3 0 0 0 -1 -1 0 -1 -1 -1 -1 0 0.5 700 B310 300 0 0 0 0 0 0 1.5 0 1 0 0 0 -3 0 0 0 1 0 0 0 0 1 1.5 0 0 303 B410 0 0 0 0 0 0 0 -1.5 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 0 0 MJ10 0 0 0 0 0 0 0 0 -1.5 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 F110 100 1 0 0 0 0 0 0.5 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0.5 0 0 101 F210 0 0 1 0 0 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 0 0 F310 233.3 0 0 1 0 0 0 0 0.5 0 0 0 0 1 0 0 0 -0.3 -0.3 -0.3 -0.3 -0.3 -0.3 -0.3 -0.3 0.2 233.3 F410 0 0 0 0 1 0 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 P10 -126765.6 0 0 0 0 0 0 0.7 2.7 0 0 0 0 21.2 0 0 0 110.1 114 112.7 115.4 124.6 17.2 15.2 19.9 18.6 -126093.3 -P10 / S10 0 0 0 0 0 0 0 0.7 2.7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Basis for Tableau10: [x5, s2, s3, s4, x6, x11, x9, x10, x12, x1, x2, x3, x4, ]. Value of Objective Function = -126765.6.

Proceed to the next tableau as follows:

Phase 0: Complete.

Phase I: Complete.

Phase II: Goal: get ß >= 0.

A. In Tableau10:

1. Select a pivot row, row, with b10row < 0: row = 4 associated with b104 = -100.

2. Compute the ratios -Ø / S as per the last row. Discard ratios which are not positive and ratios associated with artificial variables. Select the column with the least positive ratio as the pivot column: col = 7 associated with 0.7. Thus x4,7 = -1 is the pivot; variable s4 will leave the basis; variable x7 will enter the basis.

B. To create Tableau11:

3. Compute row S11 = S10 / (-1).

3. Subtract multiples of row S11 from all other rows of Tableau10 so that column x7 = e4 in Tableau11.

 Tableau11 b11 x111 x112 x113 x114 x115 x116 x117 x118 x119 x1110 x1111 x1112 s111 s112 s113 s114 s115 s116 s117 s118 s119 s*1110 s*1111 s*1112 s*1113 rowsum M11 100 0 0 0 0 1 0 0 -1 0 0 0 0 -2 0 0 1 0 0 0 0 0 1 1 0 0 101 H11 133.3 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 -0.3 -0.3 -0.3 -0.3 -0.3 -0.3 -0.3 -0.3 -0.3 132.3 J11 466.7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 -0.7 -0.7 -0.7 -0.7 -0.7 0.3 0.3 0.3 0.3 466.7 S11 100 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 101 B111 466.7 0 0 0 0 0 1 0 1 0 0 0 0 2 0 0 0 -0.7 -0.7 -0.7 -0.7 -0.7 -0.7 -0.7 0.3 0.3 466.7 B211 700 0 0 0 0 0 0 0 1.5 0 0 1 0 3 0 0 0 -1 -1 0 -1 -1 -1 -1 0 0.5 700 B311 150 0 0 0 0 0 0 0 -1.5 1 0 0 0 -3 0 0 1.5 1 0 0 0 0 1 1.5 0 0 151.5 B411 150 0 0 0 0 0 0 0 1.5 0 1 0 0 0 0 0 -1.5 0 1 0 0 0 0 -0.5 0 0 151.5 MJ11 0 0 0 0 0 0 0 0 -1.5 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 -0.5 0 F111 50 1 0 0 0 0 0 0 -0.5 0 0 0 0 -1 0 0 0.5 0 0 0 0 0 0 0.5 0 0 50.5 F211 50 0 1 0 0 0 0 0 0.5 0 0 0 0 0 0 0 -0.5 0 0 0 0 0 0 -0.5 0 0 50.5 F311 233.3 0 0 1 0 0 0 0 0.5 0 0 0 0 1 0 0 0 -0.3 -0.3 -0.3 -0.3 -0.3 -0.3 -0.3 -0.3 0.2 233.3 F411 0 0 0 0 1 0 0 0 -0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.5 0 P11 -126831.9 0 0 0 0 0 0 0 2 0 0 0 0 21.2 0 0 0.7 110.1 114 112.7 115.4 124.6 17.2 15.2 19.9 18.6 -126160.3 -P11 / 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Basis for Tableau11: [x5, s2, s3, x7, x6, x11, x9, x10, x12, x1, x2, x3, x4]. Value of Objective Function = -126831.9.

Phase 0: Complete.

Phase I: Complete.

Phase II: Complete.

Primal Solution: [x5, s2, s3, x7, x6, x11, x9, x10, x12, x1, x2, x3, x4] = [100, 133.3, 466.7, 100, 466.7, 700, 150, 150, 0, 50, 50, 233.3, 0];

P = 126831.9.

(Primal x variables not in the basis have a value of 0).

Dual Solution: [yM, yH, yJ, yS, yB1, yB2, yB3, yB4, yMJ, yF1, yF2, yF3, yF4] = [21.2, 0, 0, 0.7, 110.1, 114, 112.7, 115.4, 124.6, 17.2, 15.2, 19.9, 18.6];

D = 126831.9.

Egwald Coffee's Least Cost Import Solution.

Sacks of coffee imported and blends produced.

 Formula Mocha Harrar Java Sumatra MoJo Blend 1 50 100 150 Blend 2 50 100 150 Blend 3 233.33 466.67 700 Blend 4 0 0 0 Total 100 233.33 566.67 100 1000

 Formula Mocha Harrar Java Sumatra MoJo Total Blend 1 8287.5 9282 2187.9 19757.4 Blend 2 8287.5 9945 1591.2 19823.7 Blend 3 35581 43316 8353.8 87250.8 Blend 4 0 0 0 0 Total 16575 35581 52598 9945 12132.9 126831.9

Post Optimality Analysis.

Over what ranges of the values of the coefficients of the model, such as costs ( c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12), or the constraints on inputs and outputs ( bM, bH, bJ, bS, bB1, bB2, bB3, bB4, bMJ, bF1, bF2, bF3, bF4), will the above basic feasible solution remain optimal? By the phrase "remain optimal," I mean that the variables in the basis of the current optimal basic solution remain in the basis of the new optimal basic solution, after the values of the coefficients are altered. As long as the list of variables in each basis is the same, even though the values of the variables may change with the changes in the coefficients of the model, the current basic solution is said to remain optimal.

The primal variables, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, take on the values 50, 50, 233.33, 0, 100, 466.67, 100, 0, 150, 150, 700, 0, with per bag costs of 165.75, 165.75, 152.49, 152.49, 92.82, 92.82, 99.45, 99.45, 14.59, 10.61, 11.93, 9.28, and per pound costs of 1.25, 1.25, 1.15, 1.15, 0.7, 0.7, 0.75, 0.75, 0.11, 0.08, 0.09, 0.07. The basis variables associated with rows (1 to 13) of Tableau11 are the variables ( x5, s2, s3, x7, x6, x11, x9, x10, x12, x1, x2, x3, x4 ) whose associated objective function coefficients are ( 92.82, 0, 0, 99.45, 92.82, 11.93, 14.59, 10.61, 9.28, 165.75, 165.75, 152.49, 152.49).

Objective Function Coefficients - NonBasic Variables

By how much can one decrease the cost (increase the profit) of x8 before this variable will enter the basis of the new basic optimal solution. To determine the entry cost for x8, one computes the opportunity cost of producing one unit of x8 = the increase in costs from producing one unit of x8 = z8, using standard L.P. notation. The value of z8 is calculated by weighting each entry of the column associated with x8 in Tableau11, xi, 8, by the objective function coefficient associated with the row of that entry:

z8 = -92.82 * -1 + 0 * 0 + 0 * 0 + -99.45 * 1 + -92.82 * 1 + -11.93 * 1.5 + -14.59 * -1.5 + -10.61 * 1.5 +
-9.28 * -1.5 + -165.75 * -0.5 + -165.75 * 0.5 + -152.49 * 0.5 + -152.49 * -0.5 = -97.46.

Per bag costs for x8 can decrease from 99.45 to 97.46, and the cost per pound of x8 can decrease from 0.75 to 0.735, before x8 will enter the basis in the new optimal primal solution.

Objective Function Coefficients - Basic Variables

By how much can one increase the cost of variable x5 before a new optimal basic solution is obtained, i.e. the current list of basis variables is replaced by a different list. To determine the basis upset price for x5, one needs to know the increase in costs that result from increasing the value of each nonbasic variable by one unit, i.e. the opportunity cost, zj of producing one unit of each nonbasic variable variable, xj.

One also needs to know by how much the value of each nonbasis variable will increase from a one unit decrease in the basic variable x5, i.e. the trade-off rate x1, j, from row 1 of Tableau11 associated with basis variable x5, between the variable x5 and each nonbasis variable, xj.

Call zcj the difference between zj and the objective function coefficient cj for variable xj, divided by x1, j from Tableau11. (For slack variables, the objective function coefficient is 0.) If zcj > 0, then the nonbasic variable xj is a candidate to replace x5, when the cost of x5 (or equivalently, the objective function coefficient, c5) is increased by zcj. Taking the least positive zcj over all candidate nonbasic variables yields the possible increase in the cost of x5 before this variable leaves the basis of the existing optimal solution, i.e. a different primal or slack variable will be associated with row 1.

For the basic variable x5 associated with row 1 of Tableau11, the candidate nonbasic variables — primal variables xj, or slack variables sj — and their zcj values are given by:

xj: zcj = (zj - cj) / x1, j, or

sj: zcj = (zj - 0) / x1, j.

The zcj values for x5 associated with row 1 of Tablueau11 are:

s4: zc16 = (0.66 - 0) / 1 = 0.66

s10: zc22 = (17.24 - 0) / 1 = 17.24

s11: zc23 = (15.25 - 0) / 1 = 15.25

The least positive zcj is zc16 = 0.66. Consequently, costs per bag for x5 can increase from 92.82 to 93.48, and the costs per pound of x5 can increase from 0.7 to 0.705, before the existing basis is upset. (x5 might possibly be in the basis (possibly as a degenerate variable) of the new optimal primal basic solution).

Similarily, by how much can one increase the cost of variable x7 before a new optimal basic solution is obtained, i.e. the current list of basis variables is replaced by a different list.

The zcj values for x7 associated with row 4 of Tablueau11 are:

x8: zc8 = (-97.46 - -99.45) / 1 = 1.99

The least positive zcj is zc8 = 1.99. Consequently, costs per bag for x7 can increase from 99.45 to 101.44, and the costs per pound of x7 can increase from 0.75 to 0.765, before the existing basis is upset. (x7 might possibly be in the basis (possibly as a degenerate variable) of the new optimal primal basic solution).

Similarily, by how much can one increase the cost of variable x6 before a new optimal basic solution is obtained, i.e. the current list of basis variables is replaced by a different list.

The zcj values for x6 associated with row 5 of Tablueau11 are:

x8: zc8 = (-97.46 - -99.45) / 1 = 1.99

s1: zc13 = (21.22 - 0) / 2 = 10.61

s12: zc24 = (19.89 - 0) / 0.33 = 59.67

s13: zc25 = (18.56 - 0) / 0.33 = 55.69

The least positive zcj is zc8 = 1.99. Consequently, costs per bag for x6 can increase from 92.82 to 94.81, and the costs per pound of x6 can increase from 0.7 to 0.715, before the existing basis is upset. (x6 might possibly be in the basis (possibly as a degenerate variable) of the new optimal primal basic solution).

Similarily, by how much can one increase the cost of variable x11 before a new optimal basic solution is obtained, i.e. the current list of basis variables is replaced by a different list.

The zcj values for x11 associated with row 6 of Tablueau11 are:

x8: zc8 = (-97.46 - -99.45) / 1.5 = 1.33

s1: zc13 = (21.22 - 0) / 3 = 7.07

s13: zc25 = (18.56 - 0) / 0.5 = 37.13

The least positive zcj is zc8 = 1.33. Consequently, costs per bag for x11 can increase from 11.93 to 13.26, and the costs per pound of x11 can increase from 0.09 to 0.1, before the existing basis is upset. (x11 might possibly be in the basis (possibly as a degenerate variable) of the new optimal primal basic solution).

Similarily, by how much can one increase the cost of variable x9 before a new optimal basic solution is obtained, i.e. the current list of basis variables is replaced by a different list.

The zcj values for x9 associated with row 7 of Tablueau11 are:

s4: zc16 = (0.66 - 0) / 1.5 = 0.44

s5: zc17 = (110.06 - 0) / 1 = 110.06

s10: zc22 = (17.24 - 0) / 1 = 17.24

s11: zc23 = (15.25 - 0) / 1.5 = 10.17

The least positive zcj is zc16 = 0.44. Consequently, costs per bag for x9 can increase from 14.59 to 15.03, and the costs per pound of x9 can increase from 0.11 to 0.113, before the existing basis is upset. (x9 might possibly be in the basis (possibly as a degenerate variable) of the new optimal primal basic solution).

Similarily, by how much can one increase the cost of variable x10 before a new optimal basic solution is obtained, i.e. the current list of basis variables is replaced by a different list.

The zcj values for x10 associated with row 8 of Tablueau11 are:

x8: zc8 = (-97.46 - -99.45) / 1.5 = 1.33

s6: zc18 = (114.04 - 0) / 1 = 114.04

The least positive zcj is zc8 = 1.33. Consequently, costs per bag for x10 can increase from 10.61 to 11.93, and the costs per pound of x10 can increase from 0.08 to 0.09, before the existing basis is upset. (x10 might possibly be in the basis (possibly as a degenerate variable) of the new optimal primal basic solution).

The basic variable x12 is degenerate. No analysis is available here.

Similarily, by how much can one increase the cost of variable x1 before a new optimal basic solution is obtained, i.e. the current list of basis variables is replaced by a different list.

The zcj values for x1 associated with row 10 of Tablueau11 are:

s4: zc16 = (0.66 - 0) / 0.5 = 1.33

s11: zc23 = (15.25 - 0) / 0.5 = 30.5

The least positive zcj is zc16 = 1.33. Consequently, costs per bag for x1 can increase from 165.75 to 167.08, and the costs per pound of x1 can increase from 1.25 to 1.26, before the existing basis is upset. (x1 might possibly be in the basis (possibly as a degenerate variable) of the new optimal primal basic solution).

Similarily, by how much can one increase the cost of variable x2 before a new optimal basic solution is obtained, i.e. the current list of basis variables is replaced by a different list.

The zcj values for x2 associated with row 11 of Tablueau11 are:

x8: zc8 = (-97.46 - -99.45) / 0.5 = 3.98

The least positive zcj is zc8 = 3.98. Consequently, costs per bag for x2 can increase from 165.75 to 169.73, and the costs per pound of x2 can increase from 1.25 to 1.28, before the existing basis is upset. (x2 might possibly be in the basis (possibly as a degenerate variable) of the new optimal primal basic solution).

Similarily, by how much can one increase the cost of variable x3 before a new optimal basic solution is obtained, i.e. the current list of basis variables is replaced by a different list.

The zcj values for x3 associated with row 12 of Tablueau11 are:

x8: zc8 = (-97.46 - -99.45) / 0.5 = 3.98

s1: zc13 = (21.22 - 0) / 1 = 21.22

s13: zc25 = (18.56 - 0) / 0.17 = 111.38

The least positive zcj is zc8 = 3.98. Consequently, costs per bag for x3 can increase from 152.49 to 156.47, and the costs per pound of x3 can increase from 1.15 to 1.18, before the existing basis is upset. (x3 might possibly be in the basis (possibly as a degenerate variable) of the new optimal primal basic solution).

The basic variable x4 is degenerate. No analysis is available here.

If you change the data on the form in the sensitivity analysis section above and click "Submit L.P.", this web page will display the tableaux for the new optimal solution. Continue this process until you convince yourself of the validity of the postoptimality analysis.

Economic Interpretation of the Dual Solution.

The firm's dual problem is to determine the costs, denoted by yM, yH, yJ, yS, and yMJ per minimum number of sacks of Mocha, Harrar, Java, Sumatra, and MoJo required, maximizing the total value of coffee beans priced at these shadow costs, yet remain within the costs per sack of for each variable, x1 to x12, valued at each shadow price. The firm's dual production decision is captured in the firm's Dual Linear Programming Problem.

Dual Linear Program
Maximize the Objective Function (D)
 D = 100 * yM + 100 * yH + 100 * yJ + 100 * yS + 0 * yB1 + 0 * yB2 + 0 * yB3 + 0 * yB4 + 1000 * yMJ + 0 * yF1 + 0 * yF2 + 0 * yF3 + 0 * yF4
subject to:
 x1: 1 * yM + 0 * yH + 0 * yJ + 0 * yS + 1 * yB1 + 0 * yB2 + 0 * yB3 + 0 * yB4 + 0 * yMJ + 2 * yF1 + 0 * yF2 + 0 * yF3 + 0 * yF4 <= 165.75 x2: 1 * yM + 0 * yH + 0 * yJ + 0 * yS + 0 * yB1 + 1 * yB2 + 0 * yB3 + 0 * yB4 + 0 * yMJ + 0 * yF1 + 2 * yF2 + 0 * yF3 + 0 * yF4 <= 165.75 x3: 0 * yM + 1 * yH + 0 * yJ + 0 * yS + 0 * yB1 + 0 * yB2 + 1 * yB3 + 0 * yB4 + 0 * yMJ + 0 * yF1 + 0 * yF2 + 2 * yF3 + 0 * yF4 <= 152.49 x4: 0 * yM + 1 * yH + 0 * yJ + 0 * yS + 0 * yB1 + 0 * yB2 + 0 * yB3 + 1 * yB4 + 0 * yMJ + 0 * yF1 + 0 * yF2 + 0 * yF3 + 2 * yF4 <= 152.49 x5: 0 * yM + 0 * yH + 1 * yJ + 0 * yS + 1 * yB1 + 0 * yB2 + 0 * yB3 + 0 * yB4 + 0 * yMJ + -1 * yF1 + 0 * yF2 + 0 * yF3 + 0 * yF4 <= 92.82 x6: 0 * yM + 0 * yH + 1 * yJ + 0 * yS + 0 * yB1 + 0 * yB2 + 1 * yB3 + 0 * yB4 + 0 * yMJ + 0 * yF1 + 0 * yF2 + -1 * yF3 + 0 * yF4 <= 92.82 x7: 0 * yM + 0 * yH + 0 * yJ + 1 * yS + 0 * yB1 + 1 * yB2 + 0 * yB3 + 0 * yB4 + 0 * yMJ + 0 * yF1 + -1 * yF2 + 0 * yF3 + 0 * yF4 <= 99.45 x8: 0 * yM + 0 * yH + 0 * yJ + 1 * yS + 0 * yB1 + 0 * yB2 + 0 * yB3 + 1 * yB4 + 0 * yMJ + 0 * yF1 + 0 * yF2 + 0 * yF3 + -1 * yF4 <= 99.45 x9: 0 * yM + 0 * yH + 0 * yJ + 0 * yS + -1 * yB1 + 0 * yB2 + 0 * yB3 + 0 * yB4 + 1 * yMJ + 0 * yF1 + 0 * yF2 + 0 * yF3 + 0 * yF4 <= 14.59 x10: 0 * yM + 0 * yH + 0 * yJ + 0 * yS + 0 * yB1 + -1 * yB2 + 0 * yB3 + 0 * yB4 + 1 * yMJ + 0 * yF1 + 0 * yF2 + 0 * yF3 + 0 * yF4 <= 10.61 x11: 0 * yM + 0 * yH + 0 * yJ + 0 * yS + 0 * yB1 + 0 * yB2 + -1 * yB3 + 0 * yB4 + 1 * yMJ + 0 * yF1 + 0 * yF2 + 0 * yF3 + 0 * yF4 <= 11.93 x12: 0 * yM + 0 * yH + 0 * yJ + 0 * yS + 0 * yB1 + 0 * yB2 + 0 * yB3 + -1 * yB4 + 1 * yMJ + 0 * yF1 + 0 * yF2 + 0 * yF3 + 0 * yF4 <= 9.28
yL >= 0; yK >= 0; yM >= 0
Using matrix notation this is:
Dual Linear Program
Maximize the Objective Function (D)
D = bT y subject to
yT A <= cT, y >= 0
The solution to this minimization problem is:

Dual Solution: [yM, yH, yJ, yS, yB1, yB2, yB3, yB4, yMJ, yF1, yF2, yF3, yF4] = [21.2, 0, 0, 0.7, 110.1, 114, 112.7, 115.4, 124.6, 17.2, 15.2, 19.9, 18.6];

D = 126831.9.

End of the Linear Programming Dual Simplex Method

Linear Programming References.

• Sposito, Vincent. Linear and Nonlinear Programming. Ames, Iowa: Iowa UP, 1975.
• Restrepo, Rodrigo A. Theory of Games and Programming: Mathematics Lecture Notes. Vancouver: University of B.C., 1967.
• Restrepo, Rodrigo A. Linear Programming and Complementarity. Vancouver: University of B.C., 1994.
• Taha, Hamdy A. Operations Research: An Introduction. 2nd ed. New York: MacMillan, 1976.
• Wu, Nesa, and Richard Coppins. Linear Programming and Extensions. New York: McGraw-Hill, 1981.