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 Phas an optimal solution, then Problem Phas an optimal extreme point solution.
Exercise 2.
Corollary 2.Problem Phas a nite solution if and only if cT d i 0for all i= 1 ; : : : l when d 1; : : : ; d lare the extreme directions of X.
Prove the previous theorem Exercise 3. Let X=fx 2 Rn :Ax b; x 0g and suppose that d 1; : : :
d lare the extreme directions of X(assuming it has any). Show that the problem:
mincT x s:t: Ax b x 0 (1) has a nite optimal solution if (and only if ) cT d j 0 for k= 1 ; : : : ; l . [Hint: Modify the proof above using the Cartheodory characterization theorem.] Exercise 4. Consider the ob jective function:
z(x 1; : : : ; x n) = cT B B 1 b + X j 2J c j cT B B 1 A j xj (2) and the derivative: @ z @ x j= c j cT B B 1 A 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 z j c j 0for all j2 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 a ji 0for all i= 1 ; : : : ; m , andz j c j < 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 pro t, while each deluxe belt nets $5 in pro t. The company wishes to maximize pro t.
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 formbefore you begin.
3.Draw the feasible region and the level curves of the ob jective 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 ob jective function.
Exercise 8. Consider the following L.P problem:
8 > > > > > > < > > > > > > : max z(x 1; x 2) = 5 x 1 + 4 x 2 + 3 x 3 s:t: 2x 1 + 3 x 2 + x 3 120 4 x 1 + x 2 + 2 x 3 11 3 x 1 + 3 x 2 + 2 x 3 8 x 1; x 2; x 3 0 Solve the problem using the matrix equations representation Exercise 9. Consider the problem 8 > > > < > > > : min z(x 1; x 2) = 2 x 1 x 2 s:t: x 1 x 2 + s 1 = 1 2 x 1 + x 2 s 2 = 6 x 1; x 2; s 1; s 2 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 Gri n 2009-2014 and Linear Programming by Va sek Chv atal. W.H. Freeman and Company.
2
