1. Consider the linear program (P1) given below.
(a) Write the dual (D1) of (P1).
(b) Using the KKT conditions, show whether or not the solution x* = [6, 0, 01 is optimal for (P1).
2. A metal foundry is developing a new alloy that needs to have at least 30 percent nickel, between 25 and 40 percent copper, and at most 35 percent zinc. It will form this alloy by blending together several other alloys, (A through E) that are commercially available. These alloys have the following percentages of the metals above:
| Alloy |
A |
B |
|
CD |
E |
| Nickel (%) |
60 |
25 |
45 |
20 |
50 |
| Copper (%) |
10 |
15 |
35 |
50 |
30 |
| Zinc (%) |
30 |
60 |
20 |
30 |
20 |
| Price ($/lb) |
77 |
70 |
87 |
85 |
94 |
Additionally, the supplier of alloy A is also the supplier of alloy C. They want to increase the sales of alloy A and so they agree that, if the foundry uses at least 25% of alloy A in the new alloy, that they will reduce the price of alloy C by $8 per lb.
Formulate a linear program that will determine the blend of alloys that will produce the new alloy for least cost.
You do NOT need to solve this linear program
3. Nowhere Community College is starting a new certificate program. This program will require four 12-hour semesters of study. Since this is a new program, NCC expects the enrollment numbers to start small and then rise quickly and they will need to hire faculty to cover the classes. The projected enrollment for the program over the next 5 years is given in the table below:
|
Year
|
2015
|
2016
|
2017
|
2018
|
2019
|
|
Incoming first-year students
|
50
|
80
|
120
|
200
|
210
|
Students in the program will have to take all lower-level classes in their first year, and 9 hours of upper-level classes in each of their last two semesters, but there is an expectation that 10% of students will drop out after their first year and another 15% will have to stay for a fifth semester to re-take an upper level course. Lower-level classes can be taught by adjunct faculty, but upper-level classes have to be taught by tenure-track faculty.
All classes are 3 credit hours and the maximum size for all classes is 55 students. The college currently has two tenure-track faculty for the program and would like to maintain a ratio of 100 students per tenure-track faculty member. Tenure-track faculty are paid a fixed salary (no matter how many classes they teach), can teach a maximum of 12 hours per semester, and cannot be fired. Adjunct faculty are paid on a per class basis for a maximum of 5 classes per semester. They are only hired on a per semester basis, but if they teach more than 6 hours a semester, they have to be provided with benefits. There is also a limit on the number of qualified adjuncts available. The costs of the faculty are given below:
| Faculty Type |
Annual Cost |
Per Course Cost |
Total Available |
| Tenure-Track |
$45,000 |
-----
|
0 |
| Adjunct (≤ 6 hrs/semester) |
-----
|
$3,500 |
5 |
| Adjunct (> 6 hrs/semester) |
$8,000 |
$3,500 |
15 |
Formulate a linear program that will determine how many of each kind of faculty that Nowhere Community College should hire in each semester so that they can cover all classes at minimum cost.
You do NOT need to solve this linear program
4. Consider the linear program (P4) shown below.
(a) Add slack/surplus variables s1, s2, s3, s4 to constraints 1, 2, 4, & 5 of (P3). Give the matrices A, b, and c for this linear program.
(b) Give the matrices B, B-1, CB, CBB-1, B-1b, and cBB-1B corresponding to the basis
xB = (x1,x2,x3,x4,s3)T.
(c) Using the given basis, state the values of the basic variables and the objective function z.
(d) Starting from the given basis, perform one iteration of the simplex algorithm. On completion of the iteration, give the new basic variable values and the new objective function value.
(e) Is this new basis optimal? Why?