Page 265 -

SPECIAL CASES 245

b. For a minimization problem, convert the problem to an equivalent maximization problem by
multiplying the objective function by 1.
Step 3: Set up the standard form of the linear programme by adding appropriate slack and surplus
variables.
Step 4: Set up the tableau form of the linear programme to obtain an initial basic feasible
solution. All linear programmes must be set up this way before the initial simplex
tableau can be obtained.
Step 5: Set up the initial simplex tableau to keep track of the calculations required by the Simplex
method.
Step 6: Choose the non-basic variable with the largest c j – z j to bring into the basis. The column
associated with that variable is the pivot column.
Step 7: Choose as the pivot row that row with the smallest ratio of b i /a i for a ij > 0
This ratio is used to determine which variable will leave the basis when variable
j enters the basis. This ratio also indicates how many units of variable j can be introduced
into solution before the basic variable in the ith row equals zero.
Step 8: Perform the necessary elementary row operations to convert the pivot column to a unit column.
a. Divide each element in the pivot row by the pivot element. The result is a new pivot row containing a 1
in the pivot column.
b. Obtain zeroes in all other positions of the pivot column by adding or subtracting an
appropriatemultipleofthenewpivot row.
Step 9: Test for optimality. If c j – z j 0 for all columns, we have the optimal solution.

If not, return to step 6.

l A number of special cases can occur involving: infeasibility, unbounded problems, alternative optimal
solutions and degeneracy.

WORKED EXAMPLE

he Fresh Juice Company (FJC) is a small cooperative in South Africa that produces a range of locally
T produced fresh fruit juices for local retail stores. FJC is currently planning its next production of its grape
juices for tomorrow. It produces three different grape juice products: Sweet Grape, Regular Grape and Dry
Grape. Each of the products is produced by mixing two different types of local grape juice and natural
flavourings. The relevant data for the three products are as follows:

Sweet Grape Regular Grape Dry Grape Availability
Profit contribution, Rand 1 1.2 2
Grade A grapes - kilos 1 2 150 kilos
Grade B grapes - kilos 1 2 150 kilos
Natural flavourings - kilos 2 1 80 kilos
Labour hours 2 3 1 225 hours

So, for example, a litre of Sweet Grape will bring a profit contribution of 1R and require one kilo of Grade A
grapes, one kilo of Grade B grapes, two kilos of natural flavourings and require two hours of labour. FJC has
bought 150 kilos of each grade of grape, has 80 kilos of natural flavourings in stock and anticipates it will have
225 labour hours available for the next production batch. In addition it is contracted to supply at least 25 litres
of Sweet Grape to a local cafe´. How much of the three products should the company produce?

Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.