COMP331/557 – Class Test – 2021-Nov-09/10 Class Test. This is worth 15% of your grade. Due date: Wednesday, November 10th, 2021, 12:00 noon, via SAM as a single .pdf file. (https://sam.csc.liv.ac.uk/COMP/Submissions.pl?strModule=COMP331 or https://sam.csc.liv.ac.uk/COMP/Submissions.pl?strModule=COMP557) Photos of handwritten solutions are permitted as long as the submission is a .pdf file. Explain your solutions! The use of linear programming software is not permitted. Task 1 [20 marks] A manufacturer has three machines that each can produce the same product, but they all use different resources for the task: • Machine X uses 0.9 metric tons of iron and 1.5 metric tons of copper to produce 2.5 metric tons of the product. • Machine Y uses 2 metric tons of iron and 0.5 metric tons of nickel to produce 2 metric tons of the product. • Machine Z uses 3 metric tons of copper and 0.1 metric tons of nickel to produce 3 metric tons of the product. The manufacturer has 50 metric tons of iron, 50 metric tons of copper, and 50 metric tons of nickel, and wants to maximise the production of the product. (a) Write down the corresponding linear program in standard form. (b) Introduce slack variables and find an initial feasible primal dictionary to run the primal simplex algorithm, but do not actually run the algorithm! page 1/5 COMP331/557 – Class Test – 2021-Nov-09/10 Task 2 [20 marks] The following figure is a graphical presentation of a linear program in standard form with slack variables x3, x4, x5, and x6. As in the lecture, the darker area of a black line marks the area where xi ≥ 0. The objective function that we want to maximise is ζ = −x1, i.e., we want to find the leftmost point in the feasible region. We use Bland’s rule as the pivoting rule. We start the simplex algorithm with basis (1, 2, 5, 6). Your task is to run the simplex algorithm and analyse its run: list the basis at each pivot step and explain why this pivot step happens. Do not perform any computations, but explain everything geometrically. x1 = 0 x2 = 0 x3 = 0 x4 = 0 x5 = 0x6 = 0 page 2/5 COMP331/557 – Class Test – 2021-Nov-09/10 Task 3 [20 marks] Consider the following linear program: max 5 −4x1 +3x2 −6x3 x4 = 4 −x1 −x2 x5 = 6 −x2 −x3 x6 = 6 −x3 x1, x2, x3, x4, x5, x6 ≥ 0 From this dictionary we see that the basic feasible solution to the basis (4, 5, 6) is (x1, x2, x3, x4, x5, x6) = (0, 0, 0, 4, 6, 6). Perform one pivot step of the simplex algorithm and write down the basic feasible solution after the pivot step. page 3/5 COMP331/557 – Class Test – 2021-Nov-09/10 Task 4 [20 marks] Consider the following linear program: max 4x1 −3x2 +6x3 x1 +x2 ≤ −4 x2 +x3 ≤ −6 x3 ≤ 6 x1, x2, x3 ≥ 0 Write down the linear program that needs to be solved in phase 1 of the two-phase simplex algorithm (not the dual two-phase simplex algorithm, but the first two-phase simplex algorithm we discussed). Then take that linear program and write it in dictionary notation, perform the very first pivot step, and in this way determine the first basic feasible solution for phase 1. Do not solve the linear program! page 4/5 COMP331/557 – Class Test – 2021-Nov-09/10 Task 5 [20 marks] Determine the dual linear program for the following primal linear program: max 12x1 −10x2 subject to −4x1 +3x2 ≤ 10 4x1 −3x2 ≤ 20 x1 +4x2 ≤ 30 x1, x2 ≥ 0 Do not solve the linear program! page 5/5
欢迎咨询51作业君