ETF2480 Final Exam Practice Set
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
ETF2480
Final Exam Practice Set
1. A good starting point for your revision would be all of the tutorial questions.
2. Given the following LP:
subject to 2x1 + 3x2 + 6x3 ≤ 5
x1 + 4x2 + 7x3 = 4
9x1 + 2x2 + 4x3 ≥ 4
x1 ≥ 0
x2 ≤ 0
x3 free
Express the above problem in the following matrix vector form:
maximise cT x
subject to Ax ≤ b
|
Solution: c = (−6, 0, −5), b = (5, 4, −4, −4, 0, 0) |
||
|
−9
「 |
3 4 −4 −2 0 1 |
−7 −4
|
3. Given the following LP:
subject to x1 + 2x2 + 2x3 ≤ 4
3x1 + 4x3 ≤ 8
2x1 + x2 + 4x3 ≤ 8
x1 ,x2 ,x3 ≥ 0
Express the above problem in the following matrix vector form:
maximise cT x
subject to Ax ≤ b
|
1 3 2 A = −1
|
2 0 1 0 −1 0 |
4 0
|
4. Formulate the dual problem of:
maximize 2x1 + x2
subject to x1 + x2 = 2
2x1 − x2 ≥ 3
x1 − x2 ≤ 1
x1 ≥ 0
x2 ∈ R
|
Solution: Let y1 ,y2 ,y3 be the dual variables. minimize 2y1 − 3y2 + y3 (1) subject to y1 − 2y2 + y3 ≥ 2 (2) y1 + y2 − y3 = 1 (3) y1 ∈ R (4) y2 ,y3 ≥ 0 (5) (6) |
5. Explain what is the difference between linear programming, mixed integer programming and integer programming.
|
Solution: Linear programming problem consists of three parts: decisions variables, linear objec- tive function and linear constraints. In linear programming, the decision variables are continuous. In integer programming, the decision variables are restricted to take on integer values. In mixed integer programming, only some decision variables are integers, while the rest are continuous. |
6. Explain what makes a strong integer programming formulation.
|
Solution: The quality of a formulation of an integer programming problem with feasible solution set T, can be judged by the closeness of the feasible set of its linear programming relaxation to the convex hull of T. In particular, consider two formulations A and B of the same integer programming problem. If we denote by PA and PB the feasible sets of the corresponding linear programming relaxations, we consider formulation A to be at least at strong as formulation B if PA ⊂ PB . |
7. Explain what is the difference between exact algorithm and heuristic algorithm in solving integer programming problems.
|
Solution: Exact algorithm is guaranteed to find an optimal solution, but may take an expo- nential number of iterations. Heuristic algorithm provides a sub-optimal solution, without a guarantee on its quality, fast. |
8. The manager of State University’s DED computer wants to be able to access five different files. These files are scattered on 10 disks as shown in the following table:
The amount of storage required by each disk is as follows: disk 1, 3K; disk 2, 5K; disk 3, 1K; disk 4, 2K; disk 5, 1K; disk 6, 4K; disk 7, 3K; disk 8, 1K; disk 9, 2K; disk 10, 2K.
(a) Formulate an IP that determines a set of disks requiring the minimum amount of storage such
that each file is on at least one of the disks. For a given disk, we must either store the entire disk or store none of the disk; we cannot store part of a disk.
(b) Modify your formulation so that if disk 3 or disk 5 is used, then disk 2 must also be used.
|
Solution:
|
9. Five male and five female entertainers are at a dance. The goal of the matchmaker is to match each woman with a man in a way that maximizes the number of people who are matched with compatible mates. The following table describes the compatibility of the entertainers:
Draw a network that makes it possible to represent the problem of maximizing the number of compatible pairings as a maximum-flow problem.
|
|
2022-10-27