Homework

IEE 376 - Operations Research Deterministic Techniques and Applications Ira A. Fulton Schools of Engineering School of Computing, Informatics, and Decision Systems Engineering (CIDSE) Instructor: Jorge A. Sefair ([email protected]) Homework 2, due Monday November 13, 6:00 pm Last update: Saturday 4th November, 2017, 11:18

Rules:

� This homework can be solved in groups of, at most, three students. No exceptions. Collaboration between groups is not allowed. Submit only one report per group. Include the names of all the group members in your report.

� You will receive an additional bonus of 5 points if you submit your whole homework via Blackboard and show that you used no paper (you can type your answers using the software of your choice, or you can handwrite your answers using a tablet, etc.). Submit your report as a single file.

� The report must be self-contained, including code, data, algorithms, and a description of all the steps you followed to reach the answer. There will be no credit for unjustified answers, for instance, if you report numerical results but do not include the .mod and .dat files.

� Although your report must include your code, you also need to submit the .mod and .dat files in Blackboard.

� The homework grade will be penalized in case of late submission. The penalization will be calculated as f(t) = 20

⌈ t−10 60

⌉ , where t is the number of minutes late (t ≥ 0). No bonus will be given to late homeworks.

� There are 110 points available, but the homework will be graded over 100 points.

Problem 1 - Production planning [40 pts]

1. A manufacturing company needs to plan its production and inventory for the following T periods. The company manufactures n products and currently has I0i units of product i in inventory, for i = 1, . . . , n. The expected demand of product i for periods t = 1, . . . , T is denoted by dit. Given the demand and production cost fluctuations, the company can produce more units of any product in any period and store them for future use. However, each unit of product i requires si units of storage space, and incurs in an storage cost of cit if stored in period t, for t = 1, . . . , T . The expected available storage space is ut for each period t = 1, . . . , T within the planning horizon. Furthermore, manufacturing a unit of product i requires hi hours of skilled labor, whose cost per hour fluctuates every period depending on the demand. This labor cost per hour is denoted by `it, for i = 1, . . . , n, and t = 1, . . . , T . Given the existing labor force, the company cannot allocate more than ki hours of labor in any period to manufacture product i. For this problem, suppose that units produced in period t can be used to satisfy the demand of the same period.

(a) (10 pts) Provide a compact linear formulation for this problem (i.e., using ∑

and ∀). Specify the decision variables, constraints, and objective function.

(b) (15 pts) Implement this formulation in AMPL using Gurobi. Use the following parameters. Report a detailed production and inventory plan for each product and each period.

� T : 6

� n: 5

1 IEE 376 JS© ASU

Table 1: dit and I0i

Time Product 1 2 3 4 5 6 I0i

dit 1 120 120 150 180 200 260 15 2 50 70 80 80 60 50 17 3 15 10 5 30 35 45 2 4 300 320 350 380 400 380 25 5 230 235 260 375 230 200 50

Table 2: cit, ut, and si

Time Product 1 2 3 4 5 6 si

cit 1 1.5 1.5 2 2 2 1.5 0.5 2 0.5 0.5 0.75 1 0.75 0.50 1 3 8 8 7 5 5 5 3 4 3.5 3.5 2.5 2 2.5 2.5 0.25 5 1 1 1.5 1.5 1.5 1.5 0.3

ut 50 50 50 60 60 40

Table 3: `it, hi, and ki

Time Product 1 2 3 4 5 6 hi ki

`it 1 8.5 8.5 8.5 8.5 9 9 1 195 2 10.5 10.5 11.75 11.75 11.75 10.50 1.5 100 3 22 22 22 22 25 25 5 180 4 23.5 23.5 22.5 22 22.5 22.5 0.5 200 5 10 10 10.5 10.5 10.5 10.5 0.5 185

(c) (15 pts) Suppose that the demand forecast was inaccurate, and the demand forecast each product in period 6 is now given by Table 4.

Table 4: New demand dit

Time Product 1 2 3 4 5 6

dit 1 120 120 150 180 220 260 2 50 70 80 80 80 80 3 15 10 5 30 55 55 4 300 320 350 380 440 420 5 230 235 260 375 260 230

i. (3 pts) Can you satisfy the new demands with the existing resources? Explain.

ii. (12 pts) Suppose that you are allowed to hire additional skilled labor hours in any period to work in any product at a cost of δit per hour, as specified in Table 5.

2 IEE 376 JS© ASU

Table 5: δit

Time Product 1 2 3 4 5 6

δit 1 10.5 12.5 12.5 24.5 28 28 2 14.5 15.5 15.75 19.75 29.75 29.5 3 26 24 24 26 28 23 4 24.5 24.5 24.5 25 26.5 27.5 5 12 12 14.5 14.5 18.5 18.5

What is the new production plan? What is interesting in this plan? Explain.

Problem 2 - Matrices and Simplex geometry [40 pts]

Consider the following cases of a feasible region described by Ax ≤ b,x ≥ 0.

Case 1: A =

 1 1 2 -1 0 1

 , b =

 4 6 2



Case 2: A =

[ -3 2 1 -1

] , b =

[ 6 1

]

Case 3: A =

[ 1 1 -1 -2

] , b =

[ 5

-12

]

Case 4: A =

[ 0 -1 -1 1 1 1

] , b =

[ -1 5

] 1. (15 pts) Sketch the feasible region for the first three cases. In addition to the sketch, report the

coordinates (in R2) and basis corresponding to the:

� extreme points (if any)

� extreme directions (if any)

2. (10 pts) Using algebra, find all the extreme points and their corresponding basis for Case 4.

3. (10 pts) Using algebra, find the recession cone and use it to find the extreme directions, if any, for the region in Case 4. Are your results expected? Explain.

4. (5 pts) Using your findings from Parts 2 and 3, sketch the feasible region in Case 4.

3 IEE 376 JS© ASU

Problem 3 - Simplex algorithm and initialization methods [30 pts]

Consider the following optimization problems:

(P) max − x1 − x2 + 2x3 + x4

s.t. 2x1 + x2 + x3 + x4 ≥ 6

x1 + 2x2 − 2x3 + x4 ≤ 4

x1, x2, x3, x4 ≥ 0.

(Q) min x1 − x2 + x3 − x4 s.t. x1 + x2 + x3 + x4 ≤ 1

x1 + x2 + x3 + x4 ≥ 3

x2 + x4 − x3 ≤ 2

x1, x2, x3, x4 ≥ 0

Solve these problems using the Simplex method seen in class (i.e., matrix form). Proceed as follows:

1. (10 pts) Find an initial basic feasible solution for problems P and Q using the two-phase method. Illustrate all your steps. For each problem, report the basic variables and the corresponding basis at the end of Phase I. What can you conclude about problem Q?

2. (10 pts) Use the basic feasible solution from Part 1 to solve problem P. For each iteration report:

� Basic and nonbasic variables

� Basis (B)

� Reduced costs

� Direction of movement

� Minimum ratio test

� Entering and leaving variables

3. (10 pts) Use the Big-M approach to solve problem P. Report the same information as in Part 2. What can you conclude about problem P?

4 IEE 376 JS© ASU