ORIE 5380, CS 5727: Optimization Methods Homework Assignment 7 Due November 6, 12:00pm Please submit a single PDF document formatted to print and show all your work clearly. Feel free to scan and submit handwritten work. Do not spend too much time on wordprocessing your answers. Question 1 Find the dual of the following linear program. You may use any technique you wish, including the sensible/unusual/bizarre method. max − 2x1 + 3x2 + 8x3 st 2x1 + x3 + 5x4 ≤ 4 − 7x1 + x2 − x4 ≥ 3 5x1 − 7x3 = −2 x1 free, x2 ≤ 0, x3 ≥ 0, x4 ≥ 0. Question 2 Consider the linear program max 2x1 + 3x2 st 3x1 + 2x2 ≤ 210 x1 + 2x2 ≤ 120 x1 ≤ 60 x1, x2 ≥ 0. (a) Write the dual of this linear program. (b) By inspection, give three feasible solutions to the primal problem and compute the objective value of the primal problem at these three feasible solutions. Similarly, by inspection, give three feasible solutions to the dual problem and compute the objective value of the dual problem at these three feasible solutions. How does the objective value of the dual at the feasible solutions compare to the objective value of the primal at the feasible solutions? (c) Use the simplex method to obtain the optimal solution to the primal problem above. (d) Consider the dual problem you wrote in Part a. Use the simplex method to obtain the optimal solution this dual problem. (Hint: You may need to use the phase-1 linear program to obtain a feasible solution to the dual problem. Also, since we are minimizing the objective function in the dual problem, we need to choose the variable with the most negative objective function row coefficient as the entering variable.) 1 c© 2020, Shane Henderson (e) Consider the solutions that the simplex method visited in Part c. Give a plot where the x-axis shows the iteration number and the y-axis shows the objective value obtained at each iteration. Similarly, consider the solutions that the simplex visited visited in Part d after finding a feasible solution to the dual problem by using the phase-1 linear program. On the same chart, show the objective values for the dual problem that you obtain at each iteration. Verify that the objective values that you obtain for the dual problem are always greater than or equal to the objective values that you obtain for the primal problem, but the optimal objective values of the primal and dual problems are the same. (f) Use the last system of equations that the simplex method reached in Part c to determine the optimal solution to the dual problem. Don’t use your solution from Part d. 2 c© 2020, Shane Henderson
欢迎咨询51作业君
