Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
MIDTERM EXAMINATION
SPRING TERM 2015
CO 250
Introduction to Optimization
1. [30 points] The CNO textile company produces five kinds of cloth, each with a different composition of fabric (linen, cotton, wool, and silk). The composition of cloth is summarized in the following table, along with the profit the company makes on each type of cloth.
|
Type of cloth |
Profit ($/m2 ) |
Linen (g/m2 ) |
Cotton (g/m2 ) |
Wool (g/m2 ) |
Silk (g/m2 ) |
|
Litton |
5 |
120 |
150 |
− |
− |
|
Cool |
7 |
− |
200 |
75 |
− |
|
Cilk |
10 |
50 |
100 |
− |
20 |
|
Silen |
12 |
100 |
80 |
20 |
50 |
|
Wolk |
25 |
− |
− |
100 |
100 |
The company has an inventory of 75 kg of linen, 120 kg of cotton, 60 kg of wool, and 8 kg of silk. CNO would like to determine how many m2 of each kind of cloth it should produce so as to maximize profit.[15] (a) Formulate the above optimization problem as a linear programming problem.[10] (b) CNO signs a contract with SCS, a garment manufacturer. SCS agrees to buy all the cloth produced by CNO, provided the following requirements are met:(i) At most one of Cilk or Silen is supplied (but not both).(ii) The amounts of Litton and Cool are within 25 m2 of each other
.What additional variables and constraints does CNO need, to get a valid integer programming formulation of these requirements?
[5] (c) Justify the new constraints added in part (b).
2. [15 points] Convert the following linear programming problem over variable vector x ∈ R4 into Standard Equality Form:
min 3x1 − x2 + 3x4subjest tox1 + 4x2 − 7x3 ≤ 5
− 6x1 + 8x3 + 9x4 = 7
− 5x2 − 2x3 + 9x4 ≥ 9
3x1 + 4x2 − x4 ≥ 11
x1 ≥ 0, x2 ≤ 0, x3 ≥ 0
State the correspondence between the original variables and any new variables you introduce, as well as the correspondence between the original objective function and the one in your formulation.
3. [12 points] All subquestions below refer to the following set of constraints of an LP problem
[6] (a) For each of the sets below, determine whether the set is a basis, a feasible basis, or nothing special. Fully justify your claims.
B1 = {1}, B2 = {2, 5}, B3 = {4, 5}.
[6] (b) For each of the vectors below, determine whether the vector is feasible, basic, basic feasible, or nothing special. If it is basic feasible, find some corresponding basis. Fully justify your claims.
y T = ( 12 0 0 -1 0 ) , z T = ( -4 -4 0 0 2 ) , wT = ( 0 0 2 0 0 )
4. [13 points] Write the following LP in its canonical form for the basis B = {2, 4}. The transformation has to be based on the formulae you learned in class (and not on elementary operations). Show all your calculations.
HINT: You may use that
5. [15 points] Consider the following LP
which is already in canonical form with respect to some basis.
[10] (a) Starting with the corresponding basis, perform one iteration of the SIMPLEX METHOD. Show all your calculations. Your final answer should consist of a new feasible basis and the corresponding basic feasible solu- tion.
Clarification: Do not convert the LP into its canonical formw.r.t. the new basis.
[5] (b) Your friend Noco tried to solve the above LP. He claims that he performed 10250 iterations of the SIM- PLEX METHOD, and he observed that the objective function value kept increasing (strictly) in every single step. Without performing any more calculations, explain why Noco must have made a mistake in his calculations.
6. [10 points] Let A ∈ Rm×n , b ∈ Rm , and c ∈ Rn be given. Consider the LP problem:
(P) maxcTx s.t. : Ax ≤ b, x ≥ 0.
Prove the following statements:
[5] (a) “if there exists y ∈ Rm such that AT y ≥ 0, y ≥ 0 and bTy < 0, then (P) is infeasible”
[5] (b) “if (P) has a feasible solution ¯(x) and there exists d ∈ Rn such that Ad ≤ 0, d ≥ 0 and cTd > 0, then (P) is unbounded”
7. [5] (a) Suppose that we transform an LP problem by replacing a free variable xj by the difference (xj(′) − xj(′′))
of two nonnegative variables, and then solve the problem by the Simplex Method, finding an optimal solution. Is it possible for both xj(′) and xj(′′) to have positive values in the optimal solution? Prove your claims.
[5 (Bonus)] (b) The following form of LP problems:
(P) maxcTx s.t. : Ax ≤ b, x ≥ 0
is called Standard Inequa~lity Form. Let A(~) ∈ Rm×n~, b(~) ∈ Rm , 
Rn be given, representing the data for an LP
problem in SEF, call it (P). Show how to convert (P) to Standard Inequality Form (i.e., the form of (P)), where
A ∈ R(m+1)×n , b ∈ Rm+1 , c ∈ Rn. Define A,b,c explicitly, in terms of A,b,c and prove all your claims. Your
transformation should be very easy to compute and should not involve even partially solving the problem.