代做Math 132A Assignment 2代写C/C++语言
- 首页 >> OS编程Math 132A Assignment 2
1. (This question is to give you more practice in converting a problem into an LP.) You wish to build a house and you have divided the process into a number of tasks, namely:
B: excavation and building the foundation,
F: raising the wooden frame,
E: electrical wiring,
P: indoor plumbing,
D: dry walls and flooring, L: landscaping.
You estimate the duration of each task (in weeks) as:
|
task |
|
B |
F |
E |
P |
D |
L |
|
duration |
3 |
2 |
3 |
4 |
1 |
2 |
|
Some of the tasks can only be started when other tasks are completed. For instance, we can only build the frame once the foundation has been completed. Here are the constraints.
• F can only start after B is completed.
• L can only start after B is completed.
• E can only start after F is completed.
• P can only start after F is completed.
• D can only start after E is completed.
• D can only start after P is completed.
Unless otherwise noted above, the tasks can performed in parallel. For example, here is a feasible schedule with a completion time of 10 weeks. (times are in weeks after start).
|
task |
B |
F |
E |
P |
D |
L |
|
starting time |
0 |
3 |
6 |
5 |
9 |
6 |
|
end time |
3 |
5 |
9 |
9 |
10 |
8 |
The goal is to schedule the tasks such that the entire time to completion is minimized. Formulate this problem as an LP and find the solution using an LP solver. Hint: Let y be the completion time of the last task. Let the other variables denote the start time of the tasks.
2. Consider a public swimming pool that is open from 1pm to 9pm. There are seven people who can be hired as life guards. The following table lists each person’s availability and salary for that time.
|
Lifeguards |
Pedro |
Roman |
Brittany |
Misha |
Yian |
Anasophia |
Ty |
|
Hours Salary |
1-5 30 |
1-3 18 |
4-7 21 |
4-9 38 |
6-9 20 |
5-8 22 |
8-9 9 |
The problem is find a selection of lifeguards so that at all times, at least one lifeguard is working, and to do so as cheaply as possible. Formulate an integer program that will determine the solution to this problem.
3. For the following LP, write down the dual and using the complementary slackness conditions, determine if the given points are optimal.
maximize 3x1 + x2 + 4x3 + x4
subject to x1 + 2x2 + 2x3 + x4 ≤ 4
x1 - x2 + x3 - x4 ≤ -2
x1 , x2 , x3 , x4 ≥ 0.
(a) x* = [0, 1, 0, 2]T
(b) x* = [1, 0, 0, 3]T
4. For the following LP (P), write down the dual (D) and complementary slackness conditions. Using these and the fact that y* = [1, 2, 0, 3]T is optimal for (D), find an optimal solution to (P).
maximize x1 + 5x2 + 3x3 + 6x4 + 6x5
subject to x1 + x3 + 3x4 ≤ 3
x2 + x3 + x4 ≤ 2
2x1 − x3 − x4 + 3x5 ≤ 7
2x2 + x4 + 2x5 ≤ 4
x1 , x2 , x3 , x4 , x5 ≥ 0.