73 220 Lecture14 Soln

Integer Programming: Applications

73-220-F05 Lecture 14 - Solution

1

Homework: Question 1 ●

How can we model this using integer programming concepts? x = 3, 6, 9, 12

2

Solution to Question 1 ●

Use binary variables yi – Need one for each possible x value

●

2 Constraints: – x = 3y1 + 6y2 + 9y3 +12y4 – y1 +y2 +y3 +y4 = 1

●

Alternative way: – – – –

x = 3y y<4 y>1 y = int 3

Homework: Question 2 A food is manufactured by refining raw oils and blending them together. The raw oils come in two categories: •Vegetable oil: •VEG1 •VEG2 •Non-vegetable oil: •OIL1 •OIL2 •OIL3 The prices for buying each oil are given below (in £/tonne) VEG1 VEG2 OIL1 OIL2 OIL3 115 128 132 109 114

4

Homework: Question 2 contd. The final product sells at £180 per tonne. Vegetable oils and non-vegetable oils require different production lines for refining. It is not possible to refine more than 210 tonnes of vegetable oils and more than 260 tonnes of non-vegetable oils. There is no loss of weight in the refining process and the cost of refining may be ignored. There is a technical restriction relating to the hardness of the final product. In the units in which hardness is measured this must lie between 3.5 and 6.2. It is assumed that hardness blends linearly and that the hardness of the raw oils is: VEG1 VEG2 OIL1 OIL2 OIL3 8.8

6.2

1.9

4.3

5.1 5

Homework: Question 2 contd. It is required to determine what to buy and how to blend the raw oils so that the company maximizes its profit. The following extra conditions are imposed on the food manufacture problem stated above as a result of the production process involved: a. the food may never be made up of more than 3 raw oils b. if an oil (vegetable or non-vegetable) is used, at least 30 tonnes of that oil must be used c. if either of VEG1 or VEG2 are used then OIL2 must also be used Formulate an integer programming problem that will help you solve the problem. 6

Solution: Question 2 Decision Variables In order to deal with whether to use an oil or not so let xi = 1 if we use any of oil i (i=1,...,5), 0 otherwise We need to decide how much of each oil to use so let yi be the number of tons of oil of type i used (i=1,...,5) where i=1 corresponds to VEG1, i=2 corresponds to VEG2, i=3 corresponds to OIL1, i=4 corresponds to OIL2 and i=5 corresponds to OIL3 and where yi >=0 i=1,...,5

Constraints •cannot refine more than a certain amount of oil y1 + y2 <= 210 y3 + y4 + y5 <= 260 •hardness of the final product must lie between 3.5 and 6.2 (8.8y1 + 6.2y2 + 1.9y3 + 4.3y4 + 5.1y5)/(y1 + y2 + y3 + y4 + y5) >= 3.5 (8.8y1 + 6.2y2 + 1.9y3 + 4.3y4 + 5.1y5)/(y1 + y2 + y3 + y4 + y5) <= 6.2

7

Solution: Question 2 contd. must relate the amount used (x variables) to the integer variables (y) that specify whether any is used or not y1 <= 210x1 y2 <= 210x2 y3 <= 260x3 y4 <= 260x4 y5 <= 260x5 •the food may never be made up of more than 3 raw oils x1 + x2 + x3 + x4 + x5 <= 3 •if an oil (vegetable or non-vegetable) is used, at least 30 tonnes of that oil must be used yi >= 30xi

i=1,...,5

•if either of VEG1 or VEG2 are used then OIL2 must also be used x4 >= x1 x4 >= x2

8

Solution: Question 2 contd. Objective The objective is to maximize total profit, i.e.

maximize 180(y1 + y2 + y3 + y4 + y5) – 115y1 – 128y2 – 132y3 – 109y4 – 114y5 The assumptions we make in solving this problem using integer programming are: •all data/numbers are accurate •hardness does indeed blend linearly •no loss of weight in refining •can sell all we produce 9

Homework: Question 3 A woman was carrying a basket of eggs to market when a passer-by bumped her. She dropped the basket and all the eggs broke. The passer-by, wishing to pay for her loss, asked, 'How many eggs were in your basket?' 'I don't remember exactly,' the woman replied, 'but I do recall that whether I divided the eggs by 2,3,4,5 or 6 there was always one egg left over. When I took the eggs out in groups of seven, I emptied the basket.' What is the least number of eggs that broke?

10

Solution: Question 3

Decision Variables: n- minimum number of eggs x[i]- integer variables i=1,2,3,4,5,6

Constraints n = 2*x(1)+1 n = 3*x(2)+1 n = 4*x(3)+1 n = 5*x(4)+1 n = 6*x(5)+1 n = 7*x(6) For all(i in 1..6) x(i) is an integer, n is an integer Objective: Minimize n 11

Homework: Question 4 Three men who had a monkey bought a pile of mangoes. At night one of the men came to the pile of mangoes while the others slept and, finding that there was just one more mango than could be exactly divided by three, tossed the extra mango to the monkey and took away one third of the remainder. Then he went back to sleep. Presently another of them awoke and went to the pile of mangoes. He also found just one too many to be divided by three so he tossed the extra one to the monkey, took one third of the remainder, and returned to sleep. After a while the third rose also, and he too gave one mango to the monkey and took away the whole number of mangoes which represented precisely one third of the rest. Next morning the men got up and went to the pile. Again they found just one too many, so they gave one to the monkey and divided the rest evenly. What is the least number of mangoes with which this can be done?

12

Solution: Question 4 Decision Variables X(0): original number of mangos X(i): number of mangos taken by man i; i=1,2,3 X(4): number of mangos left in the morning Objective function: Minimize X(0) Constraints X(0) = 3*X(1) + 1 2*X(1) = 3*X(2) + 1 2*X(2) = 3*X(3) + 1 2*X(3) = 3*X(4) + 1 The logic is amount left over from before(LHS) = 3 times amount taken by person i + 1

13