Homework 1 – Intro to Linear Programming and the Simplex Method Solution



Submit the following problems at the beginning of class Friday, September 14. Your work is expected to be clear and legible. Additionally, attach this sheet to the front of your work.

Instructions For questions 1-3, do each of the following:

I. Solve the following linear programming problems by graphing the feasible region then evaluating the objective function at each corner point. \Solve” means state the optimal value of the objective function and all points in the feasible region at which this optimal value occurs. II. Solve each problem a second time using the Simplex Method clearly stating the model after the introduction of slack, surplus, and arti cial variables. You may use a calculator or computer to do the row operations, but write down the obtained simplex tableau after each iteration of the method. At each iteration identify the pivot element. III. Check your work using a software package of your choice (Solver, Matlab, etc.). Print and submit your answer screen and please make clear what software you have used.


Maximize and minimizeP (x; y) = 5x + 2y

Subject to x + y 2

2x + y 4

x; y 0

For this question only (that is, Question 1), when nding the minimum and using the Simplex method (part II above), at each iteration state which variables are basic and which are nonbasic. Also, at each iteration state the value of the objective function.


MaximizeP (x; y) = 20x + 10y

Subject to x + y 2

x + y 8

2x + y 10

x; y 0



Maximize and minimizeP (x; y) = 20x + 10y

Subject to 2x + 3y 30

2x + y 26

2x + 5y 34

x; y 0

  1. In this problem, there is a tie for the choice of the rst pivot column. When you do your work using the simplex method use the method twice to solve the problem two di erent ways; rst by choosing column 1 as the rst pivot column and then for your second solution e ort, solve by choosing column 2 as the rst pivot column. You may use a computer or calculator to perform the Simplex Method, but do write down the results of each iteration.

Maximize P (x; y) = x + y

Subject to 2x + y 16

x 6

y 10

x; y 0

5. In Example 2 in class, we used the dual to solve

Minimize C(x1; x2; x3) = 40x1 + 12x2 + 40x3

Subject to 2x1 + x2 + 5x3 20

4x1 + x2 + x3 30

x1; x2; x3 0

The dual problem has as its rst constraint

2y1 + 4y2 40:


Replace this constraint by its simpli ed version

y1 + 2y2 20 (2)

then proceed with the Simplex Method. Compare your answer with the one obtained in class and explain what causes the di erent answer. Follow the instructions in II from questions 1-3. [Note: the purpose of this question is to illustrate Warning 4.3.2 on page 47 of the notes.]

Page 2

error: Content is protected !!