Introduction to Optimization Problem Set 3

Introduction to Optimization Problem Set 3 Problem 1 (2) Reduce the following LP into standard form Minimize s.t. x1 - x1 x1 x1 5 x1 + + + - 2 x2 x2 x2 x2 - 5 x3 + 2x3 + x3 + x3 ≥ = ≥ ≤ -4 5 3 0 x1 ≥ 0, x2 ≤ 0, x3 is unconstrained. Problem 2 - Simplex and Sensitivity Analysis (8) Consider the linear following linear program. Maximize Subject to z = 2x1 + 3 x3 x1 x1 + - 4x3 x3 ≤ ≤ 30 10 xj ≥ 0 (j = 1 and 3). a) Convert the problem into standard form and construct a basic feasible solution at which (x1, x3) = (0,0) b) Solve the LP using the simplex method, starting from the basic feasible solution you found in part a). We ask you to do the pivoting by hand, and please show examples of all your calculations. Error Checking Hint: If you add up the optimal value of z, x1 and x3 you get 58. c) Draw a graphical representation of the problem in terms of the original variables x1 and x3, and indicate the path taken by the simplex algorithm. Error Checking Hint: Your answer should agree with your pivoting in b) d) Use graphical analysis to determine the allowable range to stay optimal for the cost coefficients of x1 and x3 respectively (You are welcome to use some sensitivity calculations to guide you) e) Use graphical analysis to determine the allowable range to stay feasible (that is for the intersection of the two constraints to be optimal) for the right hand side of the constraint “x1 + 4x3 ≤ 30” (You are welcome to use some sensitivity calculations to guide you). Page 1 of 5 Problem 3 - Adapted from Winston, Operations Research (6) Leary Chemical manufactures three chemicals: chemical A, chemical B, and chemical C. These chemicals are produced via two production processes: process 1 and process 2. Running process 1 for an hour costs $4 and yields 3 units of chemical A, 1 unit of chemical B, and 1 unit of chemical C. Running process 2 for an hour costs $1.6 and produces 1 unit of chemical A and 1 unit of chemical B. To meet customer demands, at least 9 units of chemical A, 4 units of chemical B, and 3 units of chemical C must be produced daily. a) Formulate as a linear program whose solution determines a daily production plan for Leary Chemical that minimizes the cost of meeting daily demands. b) Graphically determine a daily production plan that minimizes the cost of meeting Leary Chemical's daily demands. Error checking hint: the digits of the optimal solution value sum up to 10. c) What is range of the cost for process 1 such that the solution for part b remains optimal, assuming all other data stays the same?* d) Suppose that the customer demand for chemical A increases to 9+∆. How high can ∆ be so that your answer from b remains optimal?* For parts c and d, determine your answers using 2-dimensional graphic analysis as done in class; show your graph(s). Problem 4 (5) Consider a linear programming problem in canonical form(depending on F), described in terms of the following initial tableau: Z 1 0 0 0 x1 0 0 0 1 x2 0 1 0 0 x3 0 0 1 0 x4 A D -2 0 x5 3 1 2 -1 x6 B 0 E 2 x7 C 3 -1 1 RHS 0 F 2 3 The entries A,B,C,D,E,F in the tableau are unknown parameters. For each one of the following statements, find the ranges of values of the various parameters that will make the statement true. a) The corresponding basic solution is feasible but we do not have an optimal solution. For now on assume F≥0 b) The corresponding basic solution is feasible and the first simplex iteration indicates that the optimal cost is infinity (unbounded from above). c) The corresponding basic solution is feasible, x6 is a candidate for entering the basis, and when x6 is the entering variable, x3 leaves the basis. Page 2 of 5 d) The corresponding basic solution is feasible, x7 is a candidate for entering the basis, but if it does, the solution and the objective value remain unchanged. What is this called? Problem 5 - Adapted from AMP (7) The tableau given below corresponds to a maximization problem in decision variables xj ≥ 0 (for j = 1, 2 , 3 , 4, 5) z x3 x4 x5 x1 2 a1 -6 3 x2 c -2 a2 a3 x3 0 1 0 0 x4 0 0 1 0 x5 0 0 0 1 RHS 15 4 1 b State conditions on all five unknowns a1, a2 , a3, b, c, such that the following statement are true: a) b) c) d) The current solution is optimal. There are multiple optimal solutions. The problem is unbounded. The problem is infeasible. The current solution is not optimal (assume that b > 0). Indicate the variable that enters the basis, the variable that leaves the basis, and what the total change in profit would be for one iteration of the simplex method (your answer might have t be in terms of a2, a3, b and /or c) . e) The current solution is degenerate and not optimal. Indicate the variable that enters the basis, the variable that leaves the basis, and the total change in profit for one iteration of the simplex method. Hint: It is enough to provide sufficient conditions. For example, for part c, please provide some conditions on b and a3 that will ensure the problem is infeasible. (They do not have to be the most general possible conditions.) Keep in mind in part c that feasibility does not depend at all on c, which is one of the cost coefficients. For each part, you will need to provide conditions on some but not all of the coefficients. Problem 6 (4) Apply the phase I simplex method to find a feasible solution to the problem and then solve the problem to optimality Maximize Subject to Page 3 of 5 z= 2x1 + x2 + x3 x1 – 2x2 + x3 = 2, -x1 + 3x2 + x3 = 1, 2x1 – 3x2 + 4x3 = 7, x1 > 0, x2 > 0, x3 > 0 Please turn in the tableaus from phase I and the following simplex iterations. Hint: In step 6 (see steps in lecture 6) you will notice that the system contains a redundant equation. The corresponding row can be deleted from the tableau before proceeding. Problem 7 (4) A manager of an oil refinery has 8million barrels of crude oil A and 5 million barrels of crude oil B allocated for production during the coming month. These resources can be used to make either gasoline, which sells for $38 per barrel or home heating oil, which sells for $33 per barrel. There are three production processes with the following characteristics: Input Crude A Input Crude B Output gasoline Output heating oil Cost Process 1 3 5 4 3 $51 Process 2 1 1 1 1 $11 Process 3 5 3 3 4 $40 All quantities are in barrels. For example, with the first process, 3 barrels of crude A and 5 barrels of crude B are used to produce 4 barrels of gasoline and 3 barrels of heating oil. The costs in this table refer to variable and allocated overhead costs, and there are no separate cost items for the cost of crudes. a) Formulate a linear programming problem that would help the manager maximize net revenue. b) Solve the problem useing Excel Solver. Error Checking Hint: If you add up the digits of the optimal revenue you get 15. A. Challenging Problem (5) When we developed the simplex method in lecture, we looked at problems of the standard form: Maximize Subject to c’x Ax = b x≥0 That is, we had a maximization problem with a linear objective function, subject to (m) linear equality constraints and non-negativity constraints on all the variables. We now want to develop a simplex pivoting method for problems with upper bounds on the variables as well as non-negativity constraints. (Before continuing, you might want to Page 4 of 5 take a look lecture 5 and read over how we developed the pivoting rule for standard form problems.) Consider a problem of the following form: Maximize Subject to c’x Ax = b u1 ≥ x1 ≥ 0 u2 ≥ x2 ≥ 0 … un ≥ xn ≥ 0 Assume we have been solving this problem with the simplex method, with the additional consideration that we do not allow any variables to be increased beyond their upper bounds. Suppose in the course of solving the problem, we obtain the following tableau, which is feasible (all equality constraints are satisfied, and ui ≥ xi ≥ 0 for all i=1,…,n) but not optimal (some c j < 0 ). (In this tableau, bi - is the current value of the i-th basic variable, a i , j is a number in the tableau, and z is the current value of the objective function.) For simplicity, we have assumed that the first m decision variables are basic and all nonbasic variables are zero; furthermore, assume that c m+1 is the only candidate for entering the basis. How do you determine ∆ - the distance we can move in the direction of improved objective value? (Hint: You need to develop a partially “new” min ratio test, which depends on the values of a i ,m +1 .) Page 5 of 5