37242 Optimisation in Quantitative

Management

Assignment

Students can do this Assignment either individually or in group. The

number of students in a group cannot exceed four.

QUESTION 1

This question is based on the material in the pdf file Pineapple Canners

that has been emailed to you.

You must

? formulate a linear programming problem that determines the optimal

production plan for the Pineapple Canners;

? solve this linear program using LINGO;

? present the results of your work as a written report.

The written report must

? clearly describe each variable and each constraint;

? present the entire linear programming formulation;

? present the LINGO code which was used to solve the linear program;

? present the LINGO printouts with the results;

? present the optimal production plan.

The LINGO code (the linear program in LINGO) must

? use sections SETS and DATA;

? use the commands @FOR and @SUM.

1

QUESTION 2

This question is based on the material in the section 5.5.2 The Big-M

Method in S.G. Nash and A. Sofer, Linear and Nonlinear Programming.

McGraw-Hill, 1996. A copy of this section has been emailed to you as the

pdf file Nash and Sofer Linear and Nonlinear Programming.

? Study the section 5.5.2 The Big-M Method in S.G. Nash and A. Sofer,

Linear and Nonlinear Programming. McGraw-Hill, 1996.

? Using the Big-M Method, solve the linear programming problem

min ?4x1 ? 5x2 + 3x3

subject to

x1 + 2x2 + x3 = 10

x1 ? x2 ≥ 6

x1 + 3x2 + x3 ≤ 14

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.

Show your working.

QUESTION 3

Let A be an m×n matrix of rank m, m < n, and b ∈ Em.

and z and w be the optimal values of the objective functions of the linear

programs

min xn

subject to

Ax = b

x ≥ 0

and

max xn

subject to

Ax = b

x ≥ 0

respectively. Prove that for any a ∈ [z, w] there exists

x ∈ {y : Ay = b, y ≥ 0, y ∈ En}

such that xn = a.

2

QUESTION 4

Consider the linear programming problem

After introducing slack variables x3 and x4, the simplex method produced

the following final tableau

(a) Find d, e, f, g, h, k, and w. Show your working.

(b) Find c1, c2, b1, b2, a1,1, a1,2, a2,1, a2,2. Show your working.

QUESTION 5

Consider the linear program

min c

T x

subject to

Ax ≤ b

x ≥ 0

where c ∈ En is a nonzero vector, b ∈ Em, m < n, and A is m × n matrix of

rank m. Prove that if

Ax

0 < b and x

0 > 0,

then x

0

cannot be an optimal solution.

3

QUESTION 6

Consider the linear programming problem

min c

T x

subject to Ax = b

x ≥ 0

where A is an m × n matrix of rank m, m < n, b ∈ Em, c ∈ En. Suppose

that in the optimal basic feasible solution, obtained according to the Phase

I of the two-phase method, all basic variables are non-artificial variables.

(a) What is the value of the objective function for this solution? Justify

your answer.

(b) What is the reduced cost of each basic variable in this solution? Justify

your answer.

(c) What is the reduced cost of each artificial variable for this solution?

Justify your answer.

(d) What is the reduced cost of each non-artificial nonbasic variable in this

solution? Justify your answer.

QUESTION 7

Consider the linear programming problem

(a) Prove that the feasible region of this linear program has no extreme

points.

(b) Convert this linear program into an equivalent linear programming

problem in standard form.

(c) Show that the feasible region of the linear program obtained in (b) has

extreme points.

4

版权所有：留学生程序辅导网 2019 All Rights Reserved 联系方式：QQ:99515681 电子信箱：99515681@qq.com

免责声明：本站部分内容从网络整理而来，只供参考！如有版权问题可联系本站删除。