MIS 208 SPRING 2015
(due 13:15 on Monday, 6 April 2015, in class at 101)
Reading Assignment: Please read section Duality and Sensitivity Analysis of the text book
Winston. You will be responsible on that section in the exam.
Question 1: Two different products, P1 and P2 can be manufactured by one or both of two different
machines, M1 and M2. The unit processing time of either product on either machine is the same.
The daily capacity of machine M1 is 200 units (of either P1 or P2, or a mixture of both) and the
daily capacity of machine M2 is 250 units. The shop supervisor wants to balance the production
schedule of the two machines such that the total number of units produced on one ...view middle of the document...
a) Formulate the problem as a linear program and find the optimal solution by using appropriate
Simplex Methods that you have seen in the class
b) From the optimum solution determine the status of each resource.
Question 3: The following tableau represents a specific simplex iteration. All variables are
nonnegative. The tableau is not optimal for either a maximization or a minimization problem. Thus,
when a non-basic variable enters the solution it can either increase or decrease z or leave it
unchanged, depending on the parameters of the entering non-basic variable.
(a) Categorize the variables as basic and non-basic and provide the current values of all the
(b) Assuming that the problem is of the maximization type, identify the non-basic variables
that have the potential to improve the value of z. If each such variable enters the basic
solution, determine the associated leaving variable, if any, and the associated change in z.
Do not use the Gauss-Jordan row operations.
(c) Repeat part (b) assuming that the problem is of the minimization type.
(d) Which non-basic variable(s) will not cause a change in the value of z when selected to
enter the solution?
Solve the problem using graphical method. Clearly indicate the iso-profit lines and the improving
direction. Compute an optimal solution and the optimal value.
Question 7: Find the dual of the following LP.
Question 8: Consider the following LP.
Graphically solve the dual of this LP. Then use complementary slackness to solve the max problem.