Two files of mathematics questions.

Homework 5

NICO MATH 484

Topics: Simplex method II due: 2-20-2017

February 22, 2017

Exercise 1. Give an example to illustrate the following theorem:

Theorem 1. If Problem P has an optimal solution, then Problem P has an optimal extreme point solution.

Exercise 2.

Corollary 2. Problem P has a finite solution if and only if cT di ≤ 0 for all i = 1, . . . l when d1, . . . , dl are the extreme directions of X.

Prove the previous theorem

Exercise 3. Let X = {x ∈ Rn : Ax ≤ b, x ≥ 0} and suppose that d1, . . . dl are the extreme directions of X (assuming it has any). Show that the problem:

min cT x

s.t. Ax ≤ b x ≥ 0

(1)

has a finite optimal solution if (and only if) cT dj ≥ 0 for k = 1, . . . , l. [Hint: Modify the proof above using the Cartheodory characterization theorem.]

Exercise 4. Consider the objective function:

z(x1, . . . , xn) = c T BB

−1b + ∑ j∈J

( cj −cTBB

−1A·j ) xj (2)

and the derivative: ∂z

∂xj = cj −cTBB

−1A·j (3)

Give an L.P examples in R2 to illustrate what happens for positive derivatives and negative derivatives.

Exercise 5.

1

Theorem 3. If zj − cj ≥ 0 for all j ∈J , then the current basic feasible solution is optimal. Prove and give an example of the previous theorem

Exercise 6.

Theorem 4. In a maximization problem, if aji ≤ 0 for all i = 1, . . . , m, and zj −cj < 0, then the linear programming problem is unbounded.

Prove and give an example of the previous theorem

Exercise 7. Assume that a leather company manufactures two types of belts: regular and deluxe. Each belt requires 1 square yard of leather. A regular belt requires 1 hour of skilled labor to produce, while a deluxe belt requires 2 hours of labor. The leather company receives 40 square yards of leather each week and a total of 60 hours of skilled labor is available. Each regular belt nets $3 in profit, while each deluxe belt nets $5 in profit. The company wishes to maximize profit.

1. Ignoring the divisibility issues, construct a linear programming problem whose solution will determine the number of each type of belt the company should produce.

2. Use the simplex algorithm to solve the problem you stated above remembering to convert the problem to standard form before you begin.

3. Draw the feasible region and the level curves of the objective function. Verify that the optimal solution you obtained through the simplex method is the point at which the level curves no longer intersect the feasible region in the direction following the gradient of the objective function.

Exercise 8. Consider the following L.P problem: 

max z(x1, x2) = 5x1 + 4x2 + 3x3

s.t. 2x1 + 3x2 + x3 ≤ 120 4x1 + x2 + 2x3 ≤ 11 3x1 + 3x2 + 2x3 ≤ 8

x1, x2, x3 ≥ 0

Solve the problem using the matrix equations representation

Exercise 9. Consider the problem 

min z(x1, x2) = 2x1 −x2 s.t. x1 −x2 + s1 = 1

2x1 + x2 −s2 = 6 x1, x2, s1, s2 ≥ 0

Show that the minimization problem has an unbounded feasible solution. Find an extreme direction for this set.

This homework is based on the book: Linear Programming: Penn State Math 484 Lecture Notes Version 1.8.3 by Christopher Griffin 2009-2014 and Linear Programming by Vašek Chvátal. W.H. Freeman and Company.

2