关键词 >
MATB61 Linear Programming and Optimization
发布时间：2021-12-11
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Final Exam
MATB61 Linear Programming and Optimization
1. [10 points] A company has contracted for 6 jobs. These jobs can be performed in six of its manufacturing plants. Because of the size of the jobs, it is not feasible to assign more than one job to a particular manufacturing facility. The cost estimates, in thousands of dollars, of performing the jobs in the different manufacturing plants, are summarized
a) Set up the LP problem to make assignments so as to have the total cost is minimized
b) Solve the LP problem.
2. [14 points] Consider the primal problem:
a) Solve the primal problem by big M method.
b) State the dual of the primal problem.
c) Using the principle of complementary slackness and the duality theorem, describe the optimal solutions to the dual problem.
3. [9 points] Solve the LP problem using the cutting plane algorithm.
4. [11 points] Solve the LP problem using the branch and bound algorithm.
5. [8 points] Prove that the intersection of a finite collection of convex sets is convex.
6. [12 points] A game matrix is given by
7. [16 points]
a) Find the dual LP problem of the following LP problem:
b) Column player (CP) has 3 cards with numbers (1, 2, 3). CP selects 1 card and the row player (RP) has two chances to guess the number. IfRP’s first guess is right, RP wins $2. IfRP’s second guess is correct, while the first guess is wrong, RP wins $1. Otherwise, CP wins $3. Write the payoffmatrix. [6 points]
8. [20 points] The M Steel Company has three open-hearth furnaces and five rolling mills. Transportation cost (hundred dollars per ton) for shipping steel from furnaces to rolling mills in the following table.
a) The problem is to devise a shipping schedule that will meet the demand at each mill with the supply available at each furnace and minimize the total shipping cost. [10 points]
Initial tableau by Minimum Cost
b) Case I: Suppose that furnace 2 may provide 10 tons of steel only temperately and the other two
furnaces keep their regular amounts of steel. Set up the initial tableau by Northwest method to minimize the total shipping cost. [4 points]
Initial tableau by Northwest method
c) Case II: Suppose that the shipping link between furnace 3 and mill 5 is limited up to 1 ton temporarily. Set up the initial tableau by Vogel’s method to minimize the total shipping cost of meeting each mill’s demand. [6 points]
Initial tableau by Vogel’s
