Assignment 3 Algebraic Simplex Algorithm

CS 6890: Linear and Integer Programming
Assignment 3

Learning Objectives
1. Algebraic Simplex Algorithm
Problem 1 (4 points)
Implement the class MatrixSimplex with the method doSimplex() that
runs the algebraic simplex algorithm presented and analyzed in Lecture 6.
I will not put any constraints on what the internals of your class should be
like, i.e., which member variables and methods it should have.
The class API should allow the client to set the coefficient matrix A,
the vector b, the cost vector c, and the basis matrix B. It does not matter
whether you do it in a constructor or through a set of getters and setters.
Either way is fine with me so long as it is clearly specified in your documentation what needs to be done to run a MatrixSimplex object on an LP
problem.
You do not have to write code that converts an LP problem into standard
form. Do this conversion yourself and then start the algorithm running on
the matrix A that reflects the results of your conversion.
Another requirement is that the output of doSimplex() should display
the final value of z and the values of all the elements of the x vector. For
example, if the LP problem has 4 variables, the output of doSimplex() may
look as follows:
z = 60
1
x0 = 10.5
x1 = 0
x2 = 20.33
x3 = 0.25
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.
Problem 2 (1 point)
Use your implementation of MatrixSimplex.doSimplex() to solve the following LP problem.
• maximize z = 3x1 + x2 subject to
1. x1 + x2 ≥ 3;
2. 3x1 − x2 ≥ −1;
3. x ≤ 2.
Problem 3 (1 point)
Use your implementation MatrixSimplex.doSimplex() to solve this problem from homework 2. Since you are already familiar with the problem, you
can treat it as a great unit test.
Nick’s Furniture, LLC produces two types of wooden chairs - A and B. The
manufacture of chair A requires 2 hours of assembly time and 4 hours of
finishing. Chair B requires 3 hours to assemble and 3 hours to finish. The
company estimates that next week 72 hours will be available for assembly
operations and 108 hours for finishing. The unit profits for chairs A and B
are $10 and $9, respectively. It is also estimated that the maximum demand
for chair B will be 16. Formulate an LP model to answer the question of
what is the optimal product mix for the company next week.
2
Problem 4 (2 points)
Use your implementation of MatrixSimplex.doSimplex() to solve the following problem.
Ted’s Toys decides to manufacture and sell two types of toy airplances -
passenger and cargo. The planes are made out of steel, plastic, and wood
strips. A passenger plane uses 4 ounces of steel, 1 ounce of plastic, and
8 inches of wood strips. A cargo plane uses 5 ounces of steel, 3 ounces of
plastic, and 12 inches of wood strips. The company has available 20 pounds
of steel, 15 pounds of plastic, and 20 feet of wood strips. If the profit per
passenger plane is $3 and the profit per cargo plane is $4. How many of
each type of plane should be made to maximize profit?
Problem 5 (2 points)
Use your implementation of MatrixSimplex.doSimplex() to solve the following problem.
A bakery makes two types of cakes each day: poppy seed and German
chocolate. The profit to the bakery is $2 on each poppy seed cake and $4 on
each German chocolate cake. A poppy seed cake requires 400 grams of flour,
200 grams of butter, and 100 grams of poppy seeds. A German chocolate
cake requires 600 grams of flour, 100 grams of butter, and 150 grams of
chocolate. There are 9600 grams of flour, 2400 grams of butter, 1500 grams
of poppy seeds, and 2100 grams of chocolate. How many cakes of each type
should be made to maximize profit?
In your comments state the answers to the following two questions:
1. When the bakery produces the cakes to yield maximum profit, does
any flour remain unused at the end of the day? How much?
2. When the bakery produces the cakes to yield maximum profit, does
any butter remain unused at the end of the day? How much?
What To Submit
Submit your implementation via Canvas as MatrixSimplex.py/java. If
you code in Python, clearly state if you did it in Py2 or Py3. In Python, all
you need is numpy to do matrix inversion and multiplication, as was shown
3
in class. If you code in JAVA and use a third-party library for these two
operations, please either provide the JAR as part of your submission or state
clearly how the JAR can be downloaded.
Happy Hacking!
4