Operations Research

 Practice

1. Find at least one local optimal solution for the following problem:

You are expected to use both first and second order optimality conditions. What would happen if max is replaced by min ?

2. (10%) Formulate the dual problems associated with the following LP problems:

LP # 1	LP # 2	LP #3

3. Show that if a linear programming problem has exactly one optimal solution, then this solution must be an extreme point of the feasible region. You can assume that the problem is in the standard form .

4. JBM is about to introduce a new personal computer to be called Carrot. Each Carrot will be produced by assembling two components, one called Root the other called Leaves. This task takes 12 days (per unit of Carrot). Before production begins on either Root or Leaves, raw materials must be purchased, a process that takes 6 days. In addition, each unit of Leaves produced must be tested, a process that takes 10 days. The production of each unit of Root and Leaves takes 8 and 7 days respectively. JBM is interested in a critical path analysis for this project. So,

a. Construct the input table for this problem (Activity, Duration, Immediate Predecessors).

b. Draw the network representing this problem.

c. Compute the total and free floats for each activity.

d. Identify the critical path(s) and critical activities.

e. Draw the Gantt Chart for this problem.

 

5. (5%) State the Fundamental Theorem of Linear Programming and then discuss (in no more than 100 words) how it is utilised by the Simplex Method. 

6. Consider the Towers of Hanoi problem in which it takes 2 seconds to move one disc from one peg to another. How long (days) would it take to implement the dynamic programming solution in the case of a problem involving 10 discs ?

7. Write down the dynamic programming functional equation that we used in class to solve the knapsack problem and give the formal definition of f(s) as well as its physical interpretation. Then solve the following knapsack problem using this functional equation.

You are expected to determine the value of z* as well as the optimal values of x1,x2 and x3.

8. Consider the following initial Simplex tableau (Phase 1 of the Two Phase method):

B.V.	Eq. #	x1	x2	x3	x4	x5	x6	R.H.S
x4	1	1	0	0	1	0	0	4
x5	2	0	2	0	0	1	0	12
x6	3	3	2	-1	0	0	1	18
W	W	3	4	-1	0	0	0	30

observing that x5 and x6 are artificial variables, x4 is a slack variable and x3 is a surplus variable. Fill in the missing entries, represented by ?, in the following tableau obtained after a number of pivot operations (still in Phase 1): Briefly explain how you computed the missing entries.

B.V.	Eq. #	x1	x2	x3	x4	x5	x6	R.H.S
x4	1	?	?	?	?	1/3	-1/3	?
x2	2	?	?	?	?	1/2	0	?
x1	3	?	?	?	?	-1/3	1/3	?
W	W	?	?	?	?	?	?	?

 

9. Formulate a linear programming model for the problem involving the identification of the critical activities associated with the project described in Problem 4. Do not compute the optimal solution!

10. A travel office requires different numbers of full-ime employees on different days of the week.

These numbers are as follows:

Day	Number of full -time employees required
Monday	15
Tuesday	11
Wednesday	13
Thursday	17
Friday	12
Saturday	14
Sunday	11

Union rules dictate that each full-time employee must work five consecutive days and then receive two days off and that no part-time employees are allowed. The travel office wants to minimize the total number of full-time employees required to meet the daily requirements and the union rules.

Formulate a linear programming model for this problem. Do not compute the optimal solution!

---

Solution

Comment:

Problems 3 and 5 were designed to distinguish between the good and average students.
1. Find at least one local optimal solution for the following problem:

(1.1)

You are expected to use both first and second order optimality conditions. What would happen if max is replaced by min ? 

Solution:

To simplify the analysis we shall first consider the modified problem

(1.2)

and set

f(x,y,z):= xyz

g(x,y,z):= x2+y2+z2 - 3

so that the Lagrangian function is as follows:

L(x,y,z;l):= f(x,y,z) - lg(x,y,z)= xyz -l(x2+y2+z2 - 3).

Therefore, the first order necessary condition yields the following system of equations:

yz -2lx = 0

xz -2ly = 0

xy -2lz = 0

x2 + y2 + z2 - 3 = 0.

Rearranging the terms in the first three equations, we obtain

yz = 2lx

xz = 2ly

xy = 2lz

so upon multiplying these by x, y and z respectively and adding the the terms on each side we obtain

3xyz = 2l(x2+y2+z2) = 6l (observe that x2 + y2 + z2 =3)

Hence,

2l=xyz.

So the three equations above become:

yz = x2yz

xz = xy2z

xy = xyz2.

Observe that the solutions to this system can be divided into three classes:

1. At least one of the variables is equal to zero.

2. One of the variables is equal to 1, the other two are equal either to 1 or to -1 (both).

3. One of the variables is equal to -1, the other two are equal either to 1 or to -1 (both).

It is obvious by inspection that members of the second class are global maxima. Formally, we can apply the second order sufficient conditions.

So observe that the Hessian matrix of L with respect to (x,y,z) is as follows:

so that for the critical value of l, namely for l*=xyz/2, we have

To check the status of members of the second class, consider the solution x*=y*=z*=1, for which we have

hence, for any vector we have

So clearly the Hessian matrix is neither negative definite nor positive definite on R3. Let us then examine how it behaves on the tangent plane of the equality constraint at (x*,y*,y*). So, consider the set

We conclude then that

for any (a,b,c) in M(x*,y*,z*). Thus, clearly the matrix is negative definite on M(x*,y*,z*). Hence, (x*,y*,z*) is a strict local maximum.

Similarly, for the point x*=1, y*=z*=-1 we obtain:

so that

Similarly, in this case

It follows then that for any (a,b,c) in M(x*,y*,z*) we have

Thus, the Hessian matrix is negative definite on M(x*,y*,z*) and therefore (x*,y*,z*) is a strict local maximum.

It follows therefore that these points are actually global maxima.

If max is replaced by min, we conduct a similar analysis with members of the third class, to ascertain that they are all global minima. So, consider the solution x*=-1, y*=z*=1. We then have

so that

Next examine

So for any (a,b,c) in M(x*,y*,z*) we have

So clearly the Hessian is positive definite at (x*,y*,z*). Therefore, this point is a strict local minimum.

Now, with regard to the relation between (1.1) and (1.2), observe that the objective function in (1.1) is strictly increasing with respect to the objective function in (1.2), hence, subject to the same constraint(s) both problem have the same set of optimal solutions. The variable z in (1.1) is merely 1/3 of the variable z in (1.2).

2. Formulate the dual problems associated with the following LP problems: From the Recipe (Table 7.3 of Lecture Notes):

LP # 1LP # 2LP #3
Primal:	Primal:	Primal:
Dual:	Dual:	Dual:

3. Show that if a linear programming problem has exactly one optimal solution, then this solution must be an extreme point of the feasible region. You can assume that the problem is in the standard form . (This is Theorem 4.4.2 in the Lecture Notes. A complete proof is given on page 4.13.)

4. JBM is about to introduce a new personal computer to be called Carrot. Each Carrot will be produced by assembling two components, one called Root the other called Leaves. This task takes 12 days (per unit of Carrot). Before production begins on either Root or Leaves, raw materials must be purchased, a process that takes 6 days. In addition, each unit of Leaves produced must be tested, a process that takes 10 days. The production of each unit of Root and Leaves takes 8 and 7 days respectively. JBM is interested in a critical path analysis for this project. so

a. Construct the input table for this problem (Activity, Duration, Immediate Predecessors).

b. Draw the network representing this problem.

c. Compute the total and free floats for each job.

d. Identify the critical path(s) and critical activities.

e. Draw the Gantt Chart for this problem.

a. The input data is as follows:

Activity	Duration (days)	Immediate Predecessors
A:= Purchase raw materials	9	--
B:= Produced Root	8	A
C:= Produced Leaves	7	A
D:= Test Leaves	10	C
E:= Assemble Root and Leaves	12	C,D

 

b. The event network is as follows:

c. Total and Free Floats; d. critical activities

We compute the floats after determining the early and late times of the events (nodes). These are given on the following newtwork.

 

The summary of the results for the Events (nodes) and activities are summarised in the following tables:

Node, n	ET(n)	LT(n)
1	0	0
2	9	9
3	16	16
4	26	26
5	38	38

Activity	TF	FF
A	0	0
B	9	9
C	0	0
D	0	0
E	0	0

The critical activities are (A,C,D,E). This is the only critical path.

e. Gantt Chart.

5. State the Fundamental Theorem of Linear Programming and then discuss (in no more than 100 words) its relation to the Simplex Method.

The Fundamental Theorem of Linear Programming is stated and proved in the lecture notes (pp. 4.19-4.20) and its relation to the simplex algorithm is discussed there and elsewhere. I expect the kids to say that the Simplex is focusing on the extreme points of the feasible region, or equivalently the basic feasible solutions.

6. Consider the Towers of Hanoi problem in which it takes 2 seconds to move one disc from one peg to another. How long (days) would it take to implement the dynamic programming solution in the case of a problem involving 10 discs ?

The DP solution to this problem is discussed in the lecture notes (pp. 9.23-9.28). It is also mentioned (in fact, given in the 1993 Exam) that the DP solution requires 2n-1 moves. Thus, for n=10 discs, we shall need 210-1 moves, which in turn will require 211-2 seconds, or (211-2)/(60x60x24) days to complete.

7. Write down the dynamic programming functional equation that we used in class to solve the knapsack problem and give the formal definition of f(s) as well as its physical interpretation. Then solve the following knapsack problem using this functional equation.

You are expected to determine the value of z* as well as the optimal values of x1,x2 and x3.

 

The DP functional equation that we discussed in classs is as follows:

Thus, by definition f(s) is equal to the maximum weight of a knapsack of volume s given the unit weights and volumes specified by the vectors w and v respectively. To use this functional equation we need an item whose volume is equal to 1. If no such (real) item exits, we introduce a dummy item with 1 unit of volume and 0 unit of weight.

Since we also rely on the vector v to consist of positive integers, we multiply the functional constraint by 2 to obtain v=(2,4,3). In our case we have:

n	1	2	3	4
vn	2	4	3	1
wn	6	11	10	0

Solving the functional eqaution for s=0,1,2,...,6, in this order, we obtain.

f(0)=0

f(1)=max {wn+f(1-vn): vn£1}= max {w4+f(1-v4)}=0 (Hence N(1)={4}).

f(2)=max {wn+f(2-vn): vn£2}= max {w1+f(2-v1),w4+f(2-v4)}

= max {6+f(2-2),0+f(2-1)}= max {6+0,0+0}= 6 (Hence N(2)={1}).

f(3)=max {wn+f(3-vn): vn£3}= max {w1+f(3-v1),w3+f(3-v3),w4+f(3-v4)}

= max {6+f(3-2),10+f(3-3),0+f(3-1)} = max {6+0,10+0,0+6}

=10 (Hence N(3)={3}).

f(4)=max {wn+f(4-vn): vn£4} = max {w1+f(4-v1),w2+f(4-v2),w3+f(4- v3),w4+f(4-v4)}

= max {6+f(4-2),11+f(4-4),10+f(4-3),0+f(4-1)}

= max {6+6,11+0,10+0,0+10}

=12 (Hence N(4)={1}).

f(5)=max {wn+f(5-vn): vn£5} = max {w1+f(5-v1),w2+f(5-v2),w3+f(5- v3),w4+f(5-v4)}

= max {6+f(5-2),11+f(5-4),10+f(5-3),0+f(5-1)}

= max {6+10,11+0,10+6,0+12}

=16 (Hence N(5)={1,3}).

f(6)=max {wn+f(6-vn): vn£6} = max {w1+f(6-v1),w2+f(6-v2),w3+f(6- v3),w4+f(6-v4)}

= max {6+f(6-2),11+f(6-4),10+f(6-3),0+f(6-1)}

= max {6+12,11+6,10+10,0+16}

=20 (Hence N(6)={3}).

The recovery procedure yields the following:

s=6

x=(0,0,0,0)

N(6)={3}

x=(0,0,1,0)

s=s-v3=6-3=3

N(3)={3}

x=(0,0,2)

s=s-v3=3-3=0

Stop.

Thus, the optimal solution is x=(0,0,2,0), yielding z*=20 units of weight.

8. Consider the following initial Simplex tableau (Phase 1 of the Two Phase method):

B.V.	Eq. #	x1	x2	x3	x4	x5	x6	R.H.S
x4	1	1	0	0	1	0	0	4
x5	2	0	2	0	0	1	0	12
x6	3	3	2	-1	0	0	1	18
W	W	3	4	-1	0	0	0	0

observing that x5 and x6 are artificial variables, x4 is a slack variable and x3 is a surplus variable. Fill in the missing entries, represented by ?, in the following tableau obtained after a number of pivot operations (still in Phase 1):

B.V.	Eq. #	x1	x2	x3	x4	x5	x6	R.H.S
x4	1	?	?	?	?	1/3	-1/3	?
x2	2	?	?	?	?	1/2	0	?
x1	3	?	?	?	?	-1/3	1/3	?
W	W	?	?	?	?	?	?	?

Briefly explan how the missing entries were computed.

We use "common sense" and the tools that we used in the Revised Simplex Method.

Step 1. Knowing the basic variables we can fill in the missing entries in the associated columns (1,2, and 4):

B.V.	Eq. #	x1	x2	x3	x4	x5	x6	R.H.S
x4	1	0	0	?	1	1/3	-1/3	?
x2	2	0	1	?	0	1/2	0	?
x1	3	1	0	?	0	-1/3	1/3	?
W	W	0	0	?	0	?	?	?

Step 2. Since x3 is a surplus variable associated with the artificial varaible x6 , the updated column of x3 will be the negative of the updated column of x6. Thus, we can fill in this column.

B.V.	Eq. #	x1	x2	x3	x4	x5	x6	R.H.S
x4	1	0	0	1/3	1	1/3	-1/3	?
x2	2	0	1	0	0	1/2	0	?
x1	3	1	0	-1/3	0	-1/3	1/3	?
W	W	0	0	?	0	?	?	?

Step 3. Since Step 3 reconstructed B-1, we can compute the remaining missing entries. We then set

Step 4. For the RHS we have

Hence,

B.V.	Eq. #	x1	x2	x3	x4	x5	x6	R.H.S
x4	1	0	0	1/3	1	1/3	-1/3	2
x2	2	0	1	0	0	1/2	0	6
x1	3	1	0	-1/3	0	-1/3	1/3	2
W	W	0	0	?	0	?	?	?

Step 5. For the remaining reduced costs we have

so for j=3,5,6 we have

Hence,

B.V.	Eq. #	x1	x2	x3	x4	x5	x6	R.H.S
x4	1	0	0	1/3	1	1/3	-1/3	2
x2	2	0	1	0	0	1/2	0	6
x1	3	1	0	-1/3	0	-1/3	1/3	2
W	W	0	0	0	0	-1	-1	?

Step 6. To compute the value of W we note that W=cBRHS, hence W=(0,0,0)(2,6,2)=0. Thus, the complete tableau is as follows:

B.V.	Eq. #	x1	x2	x3	x4	x5	x6	R.H.S
x4	1	0	0	1/3	1	1/3	-1/3	2
x2	2	0	1	0	0	1/2	0	6
x1	3	1	0	-1/3	0	-1/3	1/3	2
W	W	0	0	0	0	-1	-1	0

9. Construct a linear programming formulation for the problem involving the identification of the critical activities asociated with the project described in Problem 6. Do not compute the optimal solution!

Let

xj:= time corresponding to event j,

then by definition we must have for each node j:

xj ³ xi + ti,j , for all ieP(j):= set of immediate predecessors of node j.

Thus, the shortest path subject to the precedence constraints can be obtained as the solution to the following problem:

min x5 - x1

s.t.

x2 >= x1 + 9 (Activity A)

x3 >= x2 + 7 (Activity C)

x4 >= x2 + 8 (Activity B)

x4 >= x3 + 10 (Activity D)

x5 >= x4 + 12 (Activity E)

Naturally, we can set x1=0.

10. A travel office requires different numbers of full time employees on different days of the week. The numbers are shown in the following table:

Day	Number of full -time employees required
Monday	15
Tuesday	11
Wednesday	13
Thursday	17
Friday	12
Saturday	14
Sunday	11

Union rules dictate that each full-time employee must work five consecutive days and then receive two days off and that no part-time employees are allowed. The travel office wants to minimize the total number of full-time employees required to meet the daily requirements and the union rules.

Formulate a linear programming model for this problem. Do not compute the optimal solution.

Let

xj:= number of employees to begin their week on day j, j=0,1,2,3,4,5,6

where 0=Sat, 1=Sun, 2=Mon,..., 6=Fri.

Then the problem is as follows:

where dj denotes the number of full-time employees needed on day j and

.