CO 250 Introduction to Optimization MIDTERM EXAMINATION SPRING TERM 2015

发布时间：2024-06-20

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

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 + 3x4

subjest to

x1 + 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.