Binary Integer Programming Problem
Uploaded by
ScribdTranslationsBinary Integer Programming Problem
Uploaded by
ScribdTranslationsFP-UNA Department of Basic Sciences Computer Engineering
Integer Linear Programming
Fixed Cost Problem
Extracted from the material of the Federico Santa María Technical University - Chile.
A company is capable of producing three types of garments: t-shirts, shorts and
pants.
The manufacturing of each type of garment requires specialized machinery. The
machinery can be leased at the following costs: US$200, US$150 and
US$100 a month for t-shirts, shorts, and trousers respectively.
The production of each garment requires the amounts of fabric and labor.
indicated in Table 1. Each month there are 150 hours of labor available and
160 meters of fabric. The unit production cost and the selling price of each
the article is shown in Table 1.
Labor Fabric (meters) Variable Cost Price of
hours (US$) sale (US$)
T-shirts 3 4 6 12
Shorts 2 3 4 8
Pants 6 4 8 15
Formulate a mathematical model that allows maximizing the factory's profit.
Solution
Decision variables:
1Number of t-shirts to be produced monthly.
2Number of shorts to produce monthly.
3Quantity of pants to be produced monthly.
Binary variables:
Since the rental cost of the machinery only depends on the garment to be produced,
It would be necessary to quantify the fact of renting or not each machine:
1
= ∀ = 1,2,3
0 case
Ing. Alexis Miguel Ruiz Jara 2020
FP-UNA Department of Basic Sciences Computer Engineering
Activation restriction of binary variables
For the model to work, it must be ensured that:
>1 → =1
=0 → =0
For this, the activation constraints of the variables must be incorporated.
binaries:
1≤ 1 1
2≤ 2 2
3≤ 3 3
The values they are sufficiently large values to be a bound
superior for the value of in the context of the problem. The upper constraint
activate the binary variable since it 0, so that the restriction can be
satisfy the binary variable it must be exactly equal to 1. In the case that
= 0, the binary variable can or cannot be worth 1 without affecting the satisfaction of the
restriction, however, if the binary variable were to be 1 it would be considering the
cost of renting machinery that is not being used.
Since the problem is about maximizing profits, if it is not strictly
it is necessary to quantify a cost, the resolution algorithm would handle doing
that the variable = 0at the optimum. That is to say, if the problem does not require considering
a cost, the resolution algorithm would take care of not using it.
Objective Function
It involves the difference between sales revenue and production costs.
fixed and variable.
BenefitSales Revenue – Variable costs -Fixed costs
( 1+ 8x2+ 15x3- 6x1+
Z =12x ) 4x(2+ 8x3− (200y1+ 150
) years2+ 100y3 )
If we develop , which we want to maximize, would be as follows:
Z = 6x1+ 4x2+ 7x3− 200y
. 1− 150y2− 100y3
Ing. Alexis Miguel Ruiz Jara 2020
FP-UNA Department of Basic Sciences Computer Engineering
Set of structural constraints
Labor availability
There is a maximum availability of labor, which is 150 hours.
3x1+ 2x2+ 6x3≤ 150
.
Availability of fabrics
There is a maximum availability of fabric meters, which is 160.
4x1+ 3x2+ 4x3≤ 160
.
Set of non-negative integer decision variables
∈ ℤ+ ∀ = 1,2,3
Set of binary variables
= { 0,1 } ∀ = 1,2,3
The mathematical model is as follows
Max Z = 6x1+ 4x2+ 7x3− 200y
. 1− 150 years2− 100y3
3x1+ 2x2+ 6x3≤ 150
.
4x1+ 3x2+ 4x3≤ 160
.
1≤ 1 1
2≤ 2 2
3≤ 3 3
∈ ℤ+ ∀ = 1,2,3
= { 0,1 } ∀ = 1,2,3
