Assignment 4 Tableau Simplex Algorithm

CS 6890: Linear and Integer Programming
Assignment 4

Learning Objectives
1. Tableau Simplex Algorithm
2. Duality and Sensitivity
Problem 1 (4 points)
Implement the class TableauSimplex with the method doSimplex() that
runs the tableau simplex algorithm presented and analyzed in Lectures 7 and
8. You may either implement the tableau format presented in Lecture 7 or
the tableau format presented in Lecture 8. For the sake of standardization,
name all your variables, even the slack and surplus ones, as x followed by
an integer. You can start your enumeration either from 0 or from 1. Be
consistent.
Your implementation of doSimplex() should print out the final tableau.
Below is one of the sample outputs that my implementation produces. As
I said in class, my implementation uses the simplified tableau presented in
Lecture 8 and uses ratios instead of floats. The abbreviation in the last
colum stands for basic solution. I start my variable indices with 1.
x1 x2 x3 x4 x5 x6 bs
x4 -10/1 0/1 0/1 1/1 1/2 -2/3 25/1
x2 2/1 1/1 0/1 0/1 1/10 -1/30 2/1
x3 0/1 0/1 1/1 0/1 -5/1 10/3 50/1
z 750/1 0/1 0/1 0/1 5/1 40/3 1450/1
1
When you solve the problems below with your algorithm, state clearly in
your comments what each x is. For example, x1 is the number of hundreds
of grams of apples, x2 is the number of hunderds of grams of oranges, and
x3 is the number of hundreds of grams of bananas.
Problem 2 (1 point)
Use your implementation Tableau.doSimplex() to solve this problem.
Rick is a farmer who owns a 2000-acre farm and plans to plant some combination of two crops, A and B. Crop A requires 1 person-day of labor and
$90 of capital for each acre planted. Crop B requires 2 person-days and $60
of capital for each acre planted. Crop A produces $170 in revenue per acre,
and crop B produces $190 in revenue per acre. Rick has $150,000 of capital
and 3000 person-days of labor available for the year. How many acres of
each crop should he plant to maximize the total revenue?
Use your tableau solution to answer the following questions. State your
answers as comments to your code.
1. If Rick has 100 more person-days available, how will his annual revenue
be affected?
2. If Rick has $100 more available in capital, how will his annual revenue
be affected?
3. Which resource is more valuable, time or capital?
Problem 3 (2 points)
Use your implementation of TableauSimplex.doSimplex() to solve the
following problem.
Murphy’s Muffin Shop makes both large and small bran muffins, using dough
and bran. Each large muffin uses 4 ounces of dough and 2 ounces of bran,
and each small muffin uses 1 ounce of dough and 1 ounce of bran. There
are 300 ounces of dough and 160 ounces of bran available each day, and the
2
profit per muffin is $.25 for a large muffin and $.10 for a small muffin. How
many muffins of each size should be made each day to maximize profits?
Run your solution with different values for dough and bran ounces to answer
the following questions and state your answers as comments to your code.
1. Suppose Murphy’s Muffin Shop keeps the number of ounces of bran at
160 and decides to increase the number of ounces of dough, at what
point (i.e., the number of ounces of dough) the profit stops rising?
2. Suppose Murphy’s Muffin Shop keeps the number of ounces of dough
at 300 and decides to increase the number of ounces of bran, at what
point (i.e., the number of ounces of bran) the profit stops rising?
Problem 4 (2 points)
Use your implementation of TableauSimplex.doSimplex() to solve the
following problem.
Ann would like to meet more of her nutritional needs from fresh fruits. In
particular, she would like to get 250 milligrams of calcium, 500 milligrams
of phosphorous, and 9 milligrams of iron by eating fresh apples, oranges,
and bananas. The nutritional content of these foods is given in the table
below. As Ann is very conscious of the number of calories she consumes,
she would like to meet her nutritional goals while consuming as few calories
as possible. Find a combination of fruits to satisfy her requirement.
Fruit Calories per 100g Calcium Phosphorous Iron
Apple 60 10 10 0.3
Orange 50 40 20 0.2
Banana 90 60 30 0.6
The numbers in the last three columns are milligrams of nutrient per 100g
of food.
What To Submit
Submit your implementation via Canvas as TableauSimplex.py/java. Remember to state your answers as comments to your code. You can put all
your answers at the beginning of your code file.
Happy Hacking!
3