Starting from:

$30

Homework 1 - Intro to Linear Programming and the Simplex Method


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
James Hahn
MATH1101
Homework #1
1. Feasible region is colored in purple below:
I. Corner points = (2, 0) and (0, 4)
P(2, 0) = 5*2 + 2*0 = 10
P(0, 4) = 5*0 + 2*4 = 8
Minimum exists at (0, 4)
Maximum does not exist due to unbounded feasible region
II. Minimize and Maximize P(x, y) = 5x + 2y
Subject to:
x + y – s1 = 2
2x + y – s2 = 4
x, y, s1, s2 ≥ 0
This is a dual problem, so the initial tableau’s transpose acts as the initial simplex
tableau. Also, by Remark 4.1.3, since the feasible region is unbounded and
coefficients of the objective function are positive, there exists a minimum, but no
maximum, so below are the tableaus to solve only the minimization problem.
There exists no maximal solution.
Pivot: pivot column: 2nd
, pivot row: 2nd, pivot element: 1
Basic variables: s1, s2, P
Objective function = 0
No more negative entries in bottom row. The tableau has converged to a
minimum at (0, 4).
Basic variables: x, y, P
Objective function = 8
III. I used Excel’s Solver add-in to solve this problem. Below is the answer report:
Results when solving for the maximum (not found):
Results when solving for the minimum:
2. Feasible region is marked on the graph below:
I. Corner points = (0, 2) and (2, 0) and (5, 0) and (2, 6) and (0, 8)
P(0, 2) = 20
P(2, 0) = 40
P(5, 0) = 100
P(2, 6) = 100
P(0, 8) = 80
There are two corner points with maximum values. Therefore, the solution is the
line connecting both points. So, the solution S = { (x, y) | y = 2x + 10 for 2 ≤ x ≤
5 }.
II. Maximize P(x, y) = 20x + 10y
Subject to:
x + y – s1 + a1 = 2
x + y + s2 = 8
2x + y + s3 = 10
x, y, s1, s2, s3, a1 ≥ 0
Let M = 50 in the initial tableau calculations:
Pivot column: 1st column, Pivot row: 1st row, Pivot element: 1
Pivot column: 3rd column, Pivot row: 3rd row, Pivot element: 2
There are no more negative elements on the last row. We have converged to the
maximum objective function value of 100 at (5, 0).
III. I used Excel’s Solver add-in to solve this problem. Below is the answer report:
Results when solving for the maximum:
3. Feasible region is marked on the graph below:
I. Corner points = (3, 8) and (8, 10) and (12, 2)
P(3, 8) = 140
P(8, 10) = 260
P(12, 2) = 260
There are two coordinates with maximum values. Therefore, the maximal
solution is the line connecting them. So, the solution S = { (x, y) | y = -2x + 26 }.
The minimum solution is located at (3, 8).
II. Maximize and Minimize P(x, y) = 20x + 10y
Subject to:
2x + 3y – s1 + a1 = 30
2x + y + s2 = 26
-2x + 5y + s3 = 34
x, y, s1, s2, s3, a1 ≥ 0
Iterations of the tableaus for the maximization problem (let M = 50):
Pivot column: 2nd column, Pivot row: 3rd row, Pivot element: 5
Pivot column: 1st column, Pivot row: 1st row, Pivot element: 3.2
Pivot column: 3rd column, Pivot row: 2nd row, Pivot element; 0.75
The tableau has converged to a maximum objective function value of 260 at (8,
10).
Iterations of the tableaus for the minimization problem can be found below. We
need to maximize the negative objective function, so maximize -P(x, y) = -20x –
10y :
Pivot column: 2nd column, Pivot row: 3rd row, Pivot element: 5
Pivot column: 1st column, Pivot row: 1st row, Pivot element: 3.2
There are no more negative entries on the last row. We have converged to an
optimal solution for the original minimization problem with objective function
value = -140 = -P(x, y), so P(x, y) = 140 at (3, 8).
III. I used Excel’s Solver add-in to solve this problem. Below are the answer reports:
For the maximization problem:
For the minimization problem:
4. Solving by choosing column 1 as the first pivot column:
Pivot column: 1st column, Pivot row: 2nd row, Pivot element: 1
Pivot column: 2nd column, Pivot row, 1st row, Pivot element: 1
Pivot column: 4th column, Pivot row: 3rd row, Pivot element: 2
We have arrived at a solution of P = 13 at (3, 10).
Solving by choosing column 2 as the first pivot column:
Pivot column: 2nd column, Pivot row: 3rd row, Pivot element: 1
Pivot column: 1st column, Pivot row: 1st row, Pivot element: 2
We have arrived at a solution of P = 13 at (3, 10).
5. The dual problem becomes:
Maximize C(y1, y2) = 20y1 + 30y2
Subject to:
y1 + 2y2 + x1 ≤ 20
y1 + y2 + x2 ≤ 12
5y1 + y2 + x3 ≤ 40
y1, y2, x1, x2, x3 ≥ 0
Pivot column: 2nd column, Pivot row: 1st row, Pivot element: 2
Pivot column: 1st column, Pivot row: 2nd row, Pivot element: 0.5
We have converged to a maximum. The values for the final solution are of x1 = 10, x2 =
10, and x3 = 0 with C = 320. The objective function value is the same as we obtained in
class, C = 320. However, the final solution values are different. In class, we obtained x1
= 5, x2 = 10, and x3 = 0. As such, by changing the first constraint in the dual problem, we
reached different solution parameter values. Lastly, note if we plug x1 = 10, x2 = 10, and
x3 into the original objective function, C = 520, which provides us with an incorrect
minimum as well. This perfectly illustrates the warning described in the notes.