Homework 1 - Intro to Linear Programming and the Simplex Method

Name: Instructor: JP Wheeler/Grader:
Homework 1 - Intro to Linear Programming and the Simplex Method
Math 1101 - An Introduction to Optimization

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 artificial 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.
1.
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 finding 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.
2.
MaximizeP(x, y) = 20x + 10y
Subject to x + y ≥ 2
x + y ≤ 8
2x + y ≤ 10
x, y ≥ 0
1
3.
Maximize and minimizeP(x, y) = 20x + 10y
Subject to 2x + 3y ≥ 30
2x + y ≤ 26
− 2x + 5y ≤ 34
x, y ≥ 0
4. In this problem, there is a tie for the choice of the first pivot column. When you do
your work using the simplex method use the method twice to solve the problem two
different ways; first by choosing column 1 as the first pivot column and then for your
second solution effort, solve by choosing column 2 as the first 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 first constraint
2y1 + 4y2 ≤ 40. (1)
Replace this constraint by its simplified 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 different 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