problems in operation research

[This sheet must be completed and attached to the last page of your homework]

ISE 421

Operations Research II

Term 161

Homework #1

Student Name ID# Signature

Homework Guidelines

To receive full credit, you should make sure you follow the following guidelines.

Homework Presentation:

• Every main problem should be answered on a different page.

• You should submit the solutions for the first two problems only.

• All pages of your homework should be in chronological order.

• Your name, and the homework number should be clearly indicated.

Modeling Questions:

• Clearly define all the variables in one group. Then clearly define all the parameters in another group. Then display the final model in the standard style (Objective, Constraints, Restriction on Domain). You can use ABCD, and EVER OLD CARD mnemonic if desired.

ISE-421 HW-1

Problem #1

Suppose that the decision variables of a mathematical programming model are defined as:

xi,j,t := acers of land plot i allocated to crop j in year t

Ct := the funds in SAR donated by the governament at the begining of year t

Rj,t := the revenue generated from crop j in $ at the end of year t

where i = 1, . . . , 47; j = 1, . . . , 9; t = 1, . . . , 10.

Use summation ( ∑

) and enumeration (∀) indexed notation to write expressions for each of the following systems of constraints in terms of these decision variables, and determine how many constraints belong to each system. You need to define additional variables to model the following constraints. Assume $1 = 3.75SAR. In addition assume appropriate information wherever neces- sary.

(a) The acres allocated in each plot i cannot exceed the available acreage (call it Ai) in any year.

(b) At least 1000 total acres must be devoted to corn (corp j = 4) in each year.

(c) At least one-third of the total acreage planted over 10 years must be in soybeans (corp j = 2).

(d) Either rice (corp j = 9) or wheat (corp j = 8) should be planted in a given year.

(e) Grapes (corp j = 7) should be planted in a year, when the current funds from the government and the total revenue from the previous year is greater than or equal to 38000 SAR.

(f) In the odd years (t = 1, 3, . . . , 9) land plot 32 is unusable.

(g) On the same land plot, there should be at least a two years of difference between corn and rice crops plantation.

(h) If soybeans are planted in a land plot, then no other crops should be planted on the same land plot.

(i) Every plot must be used for planting in a given year.

(j) In every year, there should be at least 7 different crops.

1

ISE-421 HW-1

Problem #2

Consider the following IP problem.

maximize :

14 ∗ x1 + 22 ∗ x2 + 12 ∗ x3 + 10 ∗ x4 subject to :

50 ∗ x1 + 70 ∗ x2 + 40 ∗ x3 + 30 ∗ x4 ≤ 100 10 ∗ x1 + 60 ∗ x2 + 50 ∗ x3 + 60 ∗ x4 ≤ 80

6 ∗ x1 + 1 ∗ x2 + 3 ∗ x3 + 7 ∗ x4 ≤ 9 xi ∈ {0, 1} ∀ i = 1, . . . , 4

(a) Write the LP relaxation of the above model.

(b) Get the optimal objective function value of the LP relaxation from Table 1. Is it a lower or an upper bound? Explain.

(c) Is x = [1, 0, 0, 0]T a feasible solution to the above problem. If yes, then obtain its objective function value from Table 1. Is it a lower or an upper bound? Explain.

Solve the above problem using branch & bound method, and build the enumeration tree using the following strategies. You can use the information from Table 1. Note: For every strategy that you pick, you will generate one tree, i.e., one tree for Part (d), one for Part (e) and one for Part (f).

(d) Strategy-1:

• Node Selection: Best First Select the node with the best objective function value.

• Variable Selection: Nearest to integer A fractional variable with fractional value nearest to an integer will be used for branching.

• Branching Direction: Up Select the branch of ≥ side (lower bound is increased.)

(e) Strategy-2:

• Node Selection: Depth First the Best Back Select the most recently created child node to solve. If no child exists, then backtrack to the best bound node available in the entire tree.

• Variable Selection: Lowest fraction A fractional variable with lowest fraction will be used for branching.

• Branching Direction: Down Select the branch of ≤ side (upper bound is decreased.)

(f) Strategy-3:

• Node Selection: Breadth First the Best Next All nodes at one level of the search tree are processed before any node at a deeper level. In a given level, best node should be processed first.

• Variable Selection: Highest fraction A fractional variable with highest fraction will be used for branching.

• Branching Direction: You are free to pick any rule.

2

ISE-421 HW-1

Table 1: Optimal Solutions for All LP Relaxations, # Indicates Unfixed Variables S. No x1 x2 x3 x4 Sol. Obj.

1 # # # # (0.44, 1, 0, 0.26) 30.8 2 # # # 0 (0.33, 1, 0.33, 0) 30.7 3 # # # 1 (0.29, 0.29, 0, 1) 20.3 4 # # 0 # (0.44, 1, 0, 0.26) 30.8 5 # # 0 0 (0.6, 1, 0, 0) 30.4 6 # # 0 1 (0.29, 0.29, 0, 1) 20.3 7 # # 1 # (0.65, 0.39, 1, 0) 29.7 8 # # 1 0 (0.65, 0.39, 1, 0) 29.7 9 # # 1 1 infeasible — 10 # 0 # # (1, 0, 1, 0) 26 11 # 0 # 0 (1, 0, 1, 0) 26 12 # 0 # 1 (0.15, 0, 0.37, 1) 16.5 13 # 0 0 # (1, 0, 0, 0.43) 18.3 14 # 0 0 0 (1, 0, 0, 0) 14 15 # 0 0 1 (0.33, 0, 0, 1) 14.7 16 # 0 1 # (1, 0, 1, 0) 26 17 # 0 1 0 (1, 0, 1, 0) 26 18 # 0 1 1 infeasible — 19 # 1 # # (0.44, 1, 0, 0.26) 30.8 20 # 1 # 0 (0.33, 1, 0.33, 0) 30.7 21 # 1 # 1 infeasible — 22 # 1 0 # (0.44, 1, 0, 0.26) 30.8 23 # 1 0 0 (0.6, 1, 0, 0) 30.4 24 # 1 0 1 infeasible — 25 # 1 1 # infeasible — 26 # 1 1 0 infeasible — 27 # 1 1 1 infeasible — 28 0 # # # (0, 1, 0.4, 0) 26.8 29 0 # # 0 (0, 1, 0.4, 0) 26.8 30 0 # # 1 (0, 0.33, 0, 1) 17.3 31 0 # 0 # (0, 1, 0, 0.33) 25.3 32 0 # 0 0 (0, 1, 0, 0) 22 33 0 # 0 1 (0, 0.33, 0, 1) 17.3 34 0 # 1 # (0, 0.5, 1, 0) 23 35 0 # 1 0 (0, 0.5, 1, 0) 23 36 0 # 1 1 infeasible — 37 0 0 # # (0, 0, 1, 0.5) 17 38 0 0 # 0 (0, 0, 1, 0) 12 39 0 0 # 1 (0, 0, 0.4, 1) 14.8 40 0 0 0 # (0, 0, 0, 1) 10 41 0 0 0 0 (0, 0, 0, 0) 0 42 0 0 0 1 (0, 0, 0, 1) 10 43 0 0 1 # (0, 0, 1, 0.5) 17 44 0 0 1 0 (0, 0, 1, 0) 12 45 0 0 1 1 infeasible — 46 0 1 # # (0, 1, 0.4, 0) 26.8 47 0 1 # 0 (0, 1, 0.4, 0) 26.8 48 0 1 # 1 infeasible — 49 0 1 0 # (0, 1, 0, 0.33) 25.3 50 0 1 0 0 (0, 1, 0, 0) 22 51 0 1 0 1 infeasible — 52 0 1 1 # infeasible — 53 0 1 1 0 infeasible — 54 0 1 1 1 infeasible — 55 1 # # # (1, 0.57, 0, 0.35) 29.9 56 1 # # 0 (1, 0.71, 0, 0) 29.7 57 1 # # 1 infeasible — 58 1 # 0 # (1, 0.57, 0, 0.35) 29.9 59 1 # 0 0 (1, 0.71, 0, 0) 29.7 60 1 # 0 1 infeasible — 61 1 # 1 # (1, 0, 1, 0) 26 62 1 # 1 0 (1, 0, 1, 0) 26 63 1 # 1 1 infeasible — 64 1 0 # # (1, 0, 1, 0) 26 65 1 0 # 0 (1, 0, 1, 0) 26 66 1 0 # 1 infeasible — 67 1 0 0 # (1, 0, 0, 0.43) 18.3 68 1 0 0 0 (1, 0, 0, 0) 14 69 1 0 0 1 infeasible — 70 1 0 1 # (1, 0, 1, 0) 26 71 1 0 1 0 (1, 0, 1, 0) 26 72 1 0 1 1 infeasible — 73 1 1 # # infeasible — 74 1 1 # 0 infeasible — 75 1 1 # 1 infeasible — 76 1 1 0 # infeasible — 77 1 1 0 0 infeasible — 78 1 1 0 1 infeasible — 79 1 1 1 # infeasible — 80 1 1 1 0 infeasible — 81 1 1 1 1 infeasible —

3

ISE-421 HW-1

Practice Problem #P1

Al-Mobile Junoob (AMJ) can build communication tower on any of the 8 available mountains in the central forest. The cost of building tower on any mountain in dollars is given in the following table:

M1 M2 M3 M4 M5 M6 M7 M8 cost 300 500 100 400 200 450 380 200

Based on the time and labor availability, AMJ wants to select only three mountain sites in total, which minimizes the total cost of building the towers. Due the coverage requirements, at least 2 of the first 5 mountains must be selected. Also, towers should not be build on both mountain M3 and M8. In addition to that, a tower can be built on mountain M4 if and only if a tower is built on mountain M1. Write the model clearly in the format learned in the class. You can use ABCD, and EVER OLD CARD mnemonic if desired.

4

ISE-421 HW-1

Practice Problem #P2

Write each of the following expressions as compactly as possible using summation and enumeration symbols.

(a) x1 + 4x2 + 9x3 + 16x4 + 25x5 ≥ 30

(b)

x1,1,1 + x1,1,2 + x1,1,3 + x2,1,1 + x2,1,2 + x2,1,3 ≤ a1 x1,2,1 + x1,2,2 + x1,2,3 + x2,2,1 + x2,2,2 + x2,2,3 ≤ a2

(c)

x1 + x2 + x3 ≥ 1 x2 + x3 + x4 ≥ 1 x3 + x4 + x5 ≥ 1 x4 + x5 + x6 ≥ 1 x5 + x6 + x7 ≥ 1

(d)

x1,1 ≥ 1, x1,2 ≥ 2, x1,3 ≥ 3 x2,1 ≥ 4, x2,2 ≥ 5, x2,3 ≥ 6

(e)

max :

x1 + x2 + x3 + x4

s.t. :

x1 + x2 ≤ 4 x2 + x3 ≤ 4 x3 + x4 ≤ 4 x4 + x5 ≤ 4 x1, x2, x3, x4, x5 ≥ 0

5

ISE-421 HW-1

Practice Problems from the Text Book

Pick the rules for variable selection, branching direction and node selection. Solve the following problem using Branch & Bound method. Use Simplex to solve initial LP. Then use Dual Simplex to solve the further LPs.

max :

3x1 + 2x2

s.t. :

2x1 + 5x2 ≤ 18 4x1 + 2x2 ≤ 18 x1, x2 ≥ 0 and integers

In addition to the above solve the following problems from the text book:

• Problem Set 9.1A (Q. 6, Q. 18) – pages 352-354

• Problem Set 9.1C (Q. 3) – page 362

• Problem Set 9.1D (Q. 8) – page 368

6