Integer Programming: Applications
73-220 Lecture 14
1
Agenda ●
Review of last class. – Introduction to IP – LP relaxation – Basics of binary decision variables
Discuss the four homework problems given in the last lecture. ● Next Class ●
2
Homework: Question 1 ●
How can we model this using integer programming concepts? x = 3, 6, 9, 12
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
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?
7
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?
8
Next Class ●
Do more questions from Chapter 8.
●
Binary decision variables in IP models
YOU LEARN DECISION ANALYSIS BY DOING DECISION ANALYSIS!! 9