Binary Programming Exercises
Uploaded by
ScribdTranslationsBinary Programming Exercises
Uploaded by
ScribdTranslationsInteger Programming
Exercise 1:
A municipality has the money to build five fire stations.
There are six areas that are without this service. It is intended to build the
new stations ensuring that a fire in any of the areas
unprotected can be assisted in less than 30 minutes. It is known that
cost to build the station in each area and the estimated travel time
between one area and another. The following table shows the time (in minutes)
on a trip:
Zone1Zone2Zone3Zone4Zone5 Zone6
Zone1 0 21 40 59 61 42
Zone2 20 0 48 65 41 20
Zone3 41 48 0 28 58 39
Zone4 55 72 30 0 27 48
Zone5 58 39 61 30 0 28
Zone6 41 22 40 50 25 0
Cost 36 42 45 48 54 60
Formulate a linear programming model that allows determining where the stations should be built.
in order to minimize costs. Clearly define variables, objective function
and restrictions.
Solution:
Variables:
Objective function:
Restrictions:
To build the constraints, the places are obtained from the previous table.
feasible to build fire stations to ensure that each area
I stayed less than 30 minutes from at least one of them. For example, for
ensure that at least one station is within 30 minutes of zone 1
It must be built in zone 1 or in zone 2. We build a
table with feasible zones:
.
Feasible construction zones
1 1, 2
2 1,2,6
3 3.4
4 3,4,5
5 4,5,6
6 2,5,6
So the restrictions remain:
Exercise 2
The professor of the subject Fundamentals is preparing the exam.
recovery. The contest includes four questions which will be
copied exactly from the competitions 1 and 2 that have already been completed and
evaluated. The average score obtained in each question of the tests
1 and 2, on a scale of 0.25, are presented in the following table:
Cert1 Cert2
P1 P2 P3 P4 P1 P2 P3 P4
12 10 17 22 19 13 18 15
The professor considers the following conditions for the preparation of the
recoverable contest
The recovery contest must include at least one question about
each competition 1 and 2.
2. Question 1 of contest 1 cannot be included if the
question 1 of the contest 2.
3. Question 2 of contest 1 can only be included if the
question 1 of contest 1 and question 2 of contest 2 is not included.
4. Question 3 of contest 1 can only be included if the
question 4 of the contest 1.
5. Question 4 of contest 1 must be included if it is included if it
Include question 1 from contest 1.
6. Questions 1 and 2 of contest 2 must be included if the
question 3 of the competition 1.
7. Question 4 of contest 2 can only be included if it is not included.
the questions 3 of the assessments 1 and 2.
8. Question 3 of contest 2 cannot be included if the
questions 1 from contests 1 and 2.
Formulate an IP that allows determining the composition of the contest
recoverable that delivers the best expected score. Clearly define variables,
objective function and constraints.
Solution:
Variables:
Objective function:
Restrictions:
1.-
2.-
3.-
4.-
5.
6.-
7.-
8.-
Exercise 3:
A juice factory processes a drink in flavors of melon, peach, and
strawberry
The company estimates that the minimum demand for production would be
12,000 liters of melon juice, 5,000 liters of strawberry juice and 16,000
liters of peach juice. The juice is sold at 600 per liter (regardless)
from melon, peach or strawberry), and for each ton of fruit, 1,000 is obtained.
liters of juice.
For the refinement of the pulp, the company decides to buy the fruit from
farmers with plots near the factory.
Prices and fruit production vary by each farmer in the following way:
Costofthefruit Coostf
LargjeroProduction[Tonelada] $/kilo transport and
MelonDoseorFruitIllaMelonDoseorFruitIlla [$ ]
1 5 7 1 150 70 500 10000
2 6 3 - 120 80 - 4000
3 4 - 2 140 - 550 8000
4 - 6 4 - 70 530 6000
5 2 2 - 180 60 - 7000
Farmer 1 sells all three types of fruits together, does not sell separately.
separated.
If the company buys strawberries from farmer 3 and buys peaches from
farmer 4, then must buy melons from farmer 5.
Farmer 4 does not sell less than 2 tons of each fruit he offers.
A maximum of 40 tons of fruit can be transported.
Peach juice production should not exceed that of juice from
melon by 50%.
The production of melon juice should not exceed that of juice of
strawberry at 80%.
Formulate a mixed integer linear programming model, clearly define
objectives, variables, objective function, and constraints.
Solution
Objective:
Maximize the company's profits while complying with all the
conditions of the problem.
Variables:
5 7 1
6 3
Constants: Pij 4 2 , fruit production and the farmer j.
6 4
2 2
150 70 500
120 80
C ij 140 550 cost of the fruit and the farmer j.
70 530
180 60
10000
4000
CT j 8000 transport cost for each farmer j.
6000
7000
Objective function:
Restrictions:
Maximum production of the farmers.
Demand.
Farmer 1 sells the fruits together.
Obligation to buy from the farmer 5.
Minimum sale quantity of the farmer 4.
Maximum amount to be transported.
Production of melon and peach juice.
Production of melon and strawberry juice.
. Activation of the variable .
Activation of the variable
Nature of the variables.
Exercise 4
Consider the following mixed integer linear programming model:
Table 4.3 presents the optimal solution for all relaxed problems.
possible to obtain (a script in the column corresponding to the variables
y1, y2, and y3 means that the variable is free in the relaxed problem.
1. Solve this problem using the branch and bound technique.
Clearly explain and justify each of the steps.
Solution:
The complete relaxed problem is solved, that is, the value of the
three binary variables. Then we have:
Subproblem 1:
In the solution of subproblem 1, the value of the variable does not satisfy the
binary condition, therefore it branches based on the values that
you can take:
Subproblem 2: Subproblem 1 + ( )
Subproblem 3: Subproblem 1 + ( )
Subproblem 2: Subproblem 3:
Subproblem 3 does not represent a feasible solution for the problem.
original, but as mentioned earlier, the IP solution cannot
It is better than the relaxed IP, as a problem is being solved more.
restrictive that the original relaxation the value of the objective function cannot
be better.
It branches out:
Subproblem 4: Subproblem 1 + ( )+( )
Subproblem 5: Subproblem 1 + ( )+( )
Subproblem 2: Subproblem 3:
