Unit II: Linear Programming

Linear programming (LP) is a mathematical technique of Operations Research.

(IO), effective in decision-making problems under conditions of certainty.

Linear programming is suitable for solving optimization problems when

assume that the relationship between variables is linear.

To ensure the use of this effective tool, we developed a model that responds.
with the highest fidelity possible to the conditions of the problem to which it is intended to give
solution.

The solution found to the problem will be a good approximation to the optimal solution.
This approach will be better to the extent that the model represents the best.
approach to the real conditions of the problem.

The applications of PL are so diverse that they range from agriculture to military.

Mathematical models

Whether in the private or public sector, one of the main functions of a

An administrator is to solve problems mainly through the construction of models.
or model proposals.

The construction of such models is a means that allows managers to analyze

and study problems, as well as examine different alternatives.

The construction of models is not a new idea; the process is used every day, with
frequency in an unconscious manner, in situations of basic problems.

2. Linear Programming Models

a. Characteristics of linear programming problems:

1) An objective function that is going to be Maximized or Minimized.

2) Restrictions that may be limitations or requirements.

Proportionality: the objective function and the constraints must be proportional

at the manufacturing level of each product.

4) Divisibility: It means that fractional assignments of products are possible.

5) Additivity: the contributions of individual products are additive.

6) No negativity of the products: It is not possible to manufacture negative quantities of

they.

[Link]

A general model of PL would be:

Page 1
Decision variables (DV): X1, X2, ..., Xn

FO ===> (Max. or Min.) Z = C1X1 + C2X2+....+ CnXn

subject to the following restrictions (s.a)

a11X1+ a12X2+..... + a1nXn[ , , = ] b1

a21X1+ a22X2+..... + a2nXn[ , , = ] b2
am1X1+ am2X2+.....+ amnXn [ , , = ] bm
x1, x2,...... xn 0

Where:
represent the decision variables on which there are
X1, X2......,Xn
what to decide.
a11 a12....a1n
a21 a22....a2nthey represent the unit requirements for each variable of
decision.
am1am2....amn
they represent the marginal contributions (the input that it provides to the
objective function (OF), each unit of the elements
c1, c2....cn
represented by the decision variables.

b1, b2......bnthey represent the availabilities or the demands

Each of the inequalities and/or equations represents a restriction of the

problem.

They originate from resource limitations (supplies) or from demands.

minimum requirements to be met (standards).

For a limitation constraint we use and for a demand it is used .

The values bj, where j = 1,2,3...,m represent either the maximum availability limit.
of the i-th resource or the minimum required for a certain standard to be met.

Each of the coefficients aijtechnical requirement of the article

represented by the variable X,i y forman la matriz principal del sistema.

The other set of restrictions (Xi 0), they limit the values of the variables of
decisions (VD) to be non-negative.

c. Formulation of models
The first thing we need to do when we have a problem is to build the model of
PL

Let's summarize the steps for building a PL model.

1) Definition of the decision variables (DV).

2) Definition of the objective or goal in terms of its decision variables.
3) FO: Maximize or Minimize.
4) Definition of restrictions: Of limitations or of demands.
5) Restrict all decision variables to be non-negative.

Page 2
 Example 1:
The Masaya Furniture Factory (MFF) specializes in the production of two types.
trendy eateries in Central America: Virginiano and Masaya.

The FMM achieves a profit (net selling price - variable manufacturing costs) of
$200 and $240 of each type respectively.

The FMM has experienced a high demand for both cafeterias, as a result,
The manager believes he can sell all the dining sets he produces.

The dining halls require processing time in the departments of

construction and painting. The requirements and capacities in daily hours are
summarized in the following table:
Type of dining room
Department Virginiano Masaya Capacidad (horas)
Construction 6 12 120
Painting 8 4 64
Unit utility 200 240

The model will then be:

Sean X1number of Virginian type dining tables to produce

X2number of Masaya type dining tables to be produced

FO: (Max.) Z = 200X1+ 240 X2Utilization

s.a
6 X1+ 12 X2 120 (Availability (h / Construction Dept.)
8 X1+ 4 X2 64 ( Availability (h / Painting Dept. )
X1, X2 0

Example 2 (Diet):
A certain nutrient for livestock is made up of a mixture of ingredients 1, 2, and 3.
The ingredients contain proteins, fats, vitamins, and minerals, whose content in
The libra is given in the following table:

Content/qq
Cost
Ingredients Protein Fat Vitamins and (lb)
(lb) (lb) minerals (lb)
1 2 7 2 $12.50
2 5 4 2 $14.00
3 8 2 3 $17.50

The livestock company wants the mixture to contain at least 10 pounds of protein.
minus 5 pounds of fat and at least 4 pounds of vitamins and minerals.

Determine how many pounds of each ingredient should be ordered to prepare the
mix at a minimal cost?

Solution:

VD:Sean Xjamount of pounds to order of ingredient j.

j = 1,2,3

Page 3
FO:==>(Min) Z = 12.5 X1+ 14 X2+ 17.5 X3(Total cost)

s.a:
2 X1+ 5 X2+ 8 X3 10 (pounds of protein)
7 X1+ 4 X2+ 2 X3 5 (pounds of fat)
2 X1+ 2 X2+ 3 X3 4 (pounds of Vitamins and Minerals)
Xj 0

X1, X2, X3,X4 0

Example 3 (COOPERATIVE):
A cooperative has 200 acres of land where it plans to grow beans, rice, and
corn. The expected production is 1800 kg per acre planted with beans, 2100
Kg. per acre planted with rice and 2900 Kg. per acre planted with corn.

To meet internal consumption, at least 12 acres of beans must be planted.

of rice and 20 corn apples.

The cooperative is capable of storing no more than 700,000 Kg.

crops.
Knowing that beans, rice, and corn yield a profit of $1.2, $0.60, and $0.28 per kg.
respectively.

How many apples should be planted of each product so that their profits are
maximums?

Solution:

VD: Sean X1Amount of apples to be planted with beans

X2Number of apples to plant rice
X3Amount of apples to be planted with corn.
(Max.) Z = (1.2)(1800)X1+ (0.6)(2100)X2 + (0.28)(2900)(X3)
Z = 2160 X1+ 1260 X2+ 812 X3

s.a

1800 X1+ 2100 X2+ 2900 X3 700,000 (Storage in Kg.)

X1+ X2+ X3 200 (Planting area in Acres)
X1 12 (Demand in Beans Apples)
X2 16 (Demand in Rice Apples)
X3 20 (Demand in Corn Acres)
Xj 0 ; j = 1,2,3

Example 4 (CARTONISA):
A cardboard box factory has 1125 m2of cardboard and 8 machine hours daily
for its weekly production of 2 types of boxes I and II. It is known that with each meter
cardboard square produces 2 boxes of type I or 5 boxes of type II and the machinery
processes 5 and a half boxes of type II or 4 boxes of type I per hour.

The factory operates 5 days a week and requires 500 boxes monthly.
any type.

The boxes report profits of $4.5 and $5.5 for types I and II boxes.
respectively.

Page 4
Find the optimal weekly production strategy.

Solution:

VD: Sean XjNumber of type j boxes to be produced j = 1,2

FO: (Max.) Z = 4.5 X1+ 5.5 X2Utility

s.a

1 2
X 1 X 2 40 (time in hours / machine)
4 11
X1 X 2 500monthly requirement
1 1
X 1 X 2 1,125(m2of cardboard)
2 5
Xj 0, j = 1,2

Actividad de autoaprendizaje No 1
Resolve each of the following cases that are presented and propose a solution for each one.
among them the linear programming model.

1. (DECEASED ANIMALS INC.)

The company Taxidermy Animals S.A is producing doves and hawks.

dissected. Under the conditions in which the market currently finds itself, it can
Selling hawks and pigeons with profits of $10 and $6 respectively.

The skins for hawks are tougher and take more time to work with than those of the
pigeons. The skin machine can process 8 pigeon skins per minute, but
only 4 hawks. The filling line can fill 6 hawks per minute or
4 doves at the same time.

The hawks are going to a final operation on a beak sharpening machine that
It has a capacity of 3.5 hawks per minute.

How many hawks and doves should be prepared in 8-hour shifts for
maximize profits.

2. (Farm).

A farmer wants to determine the best selection of animals for his farm,
with the aim of maximizing their profits from the sale of such animals at the end of
summer.

You can choose to buy sheep, cattle, or goats.

Each lamb requires 1 acre of pasture and $15 in feed and treatment;
each one costs $25 and can be sold for $60

Each cattle requires 4 apples of pasture, $30 in feed and treatment, costs
$30 and can be sold for $100 each

Page 5
Each goat needs 1/2 apple of pasture, requires $5 in feed and
tratamiento, cuesta $10 y se vende en $20 c/u

The farm has 300 acres available for pasture and the farmer has
$2,500.00 to invest in the purchase and maintenance of the animals.

The farmer wants to have at least 50 sheep, no more than 40 cattle, and exactly 20.
goats.

How many animals of each type does he need to buy and then sell to maximize?
its utilities?

3. (ROLLING S.A).

La Arrolladora S.A, a manufacturer of tires for automobiles, is trying to find the

best way to utilize excess capacity, specifically of 20,000 hours
man.

The company is considering the production of two types of tires: Normal and Radial.

Each normal tire requires 2 man-hours and contributes $16 to the profit.
Each radial tire takes 2.5 man-hours and has a contribution to profit of
$20
The marketing department estimates that up to 6000 tires of that type can be sold.
Normal and at least 3000 tires of the Radial type.

Find the number of tires of each type that the company must produce with the
Objective of maximizing its profits by utilizing man-hours to the fullest.

4. (MACHINE).

A factory produces two types of parts that are used as spare parts for a certain...
agricultural machine. Each of the pieces requires a certain number of hours of
foundry, machining and finishing according to what is shown in the following table:

Parts
Processes A B
Foundry 1 3
Machination 2 4
Finished 2 1

The factory has the resources for each process for the following week:
Fundición:240 h ; Maquinación:370 h y Acabado:370h

Each piece leaves a profit of $100 and $300 respectively from A and B. If the
the factory manager is planning the weekly production, how many pieces of
What type should be produced to maximize profit?

Assuming that for the same problem, the main objective is the maximization of the
production, what would the model be then?

5. (BOMB).

Page 6
Una compañía fábrica y vende dos tipos de bombas hidráulicas:(1) Normal y (2) Extra
large. The manufacturing process associated with the production of pumps involves
tres actividades:ensamblado, pintura y pruebas (control de calidad).

The resource requirements for assembly, painting, and testing of the pumps are
shown in the following table.

MANUFACTURING REQUIREMENT (HOURS):

Type Painted Assembly Test
Normal 3.6 1.6 0.6
Extra Large 4.8 1.8 0.6

The contribution to profits from the sale of a Normal pump is $50 while
The profit from an extra large pump is $75.

There are 4800 hours of assembly time available per week, 1980 hours of
painting time and 900 hours of testing time.

Previous sales experiences indicate that the company can expect to sell
At least 300 regular bombs and at most 180 of the extra large ones per week.

The company would like to determine the amount of each type of pump that it should
to manufacture weekly with the aim of maximizing their profits.

6. (FARMER).

Each bag of an agricultural disinfectant must contain a minimum of 600 grams of the
ingrediente I; 800 gr. del ingrediente II y 600 gr. del ingrediente III.

The disinfectant is produced with two raw materials A and B.

Each Kg. of raw material A contains 200 g. of ingredient I; 200 g. of II and 600
gr. of III; each kg. of raw material B contains 200 gr. of ingredient I; 400 gr. of
II and 100 grams of III.

The cost of raw material A is $7 per kg and raw material B is $2 per

kg. I calculate the quantities of the two raw materials that need to be purchased for
produce each bag of disinfectant at a minimal cost.

7. (Q.2).

Products 1 and 2 are processed on three types of machines, A, B, and C.

Cada unidad del producto 1 requiere 2 horas de la máquina tipo A y 4 horas de la

machine type B and 3 hours on machine type C. Each unit of product 2 requires 2
hours on each of the machines.

The available time on the machines is limited to 800 hours per month.
Type A machine, 1200 monthly hours of machine B and 600 monthly hours of
type C machine.

If each unit of product 1 produces a contribution (selling price minus

direct costs) of 15 pesos and each unit of product 2 produces a contribution
From $24, calculate how much of each item should be produced to maximize utility?

Page 7
Graphic method to solve LP problems

To solve small LP problems, that is, problems with two products or

variables, it is possible to use the graphic method.

Although this process does not work to solve problems that have more than two
variables, is useful to illustrate both the solution process and the characteristics
of an optimal solution or of utility maximization or cost minimization.

Steps

Formulate the problem as a linear programming model.

a. Graph each of the constraints of the problem.
b. Locate all the intersection points of the graph and determine the values of the
variables at the points of intersection.
c. Find which of these intersection points yields the maximum benefit or the minimum.
cost.

Example # 1

The X-ray department of a hospital has two machines, A and B, that can
to be used to develop photographs. The maximum daily processing capacity of these
machines is no more than 80 X-rays for machine A and no more than 100 X-rays
for machine B. The department must plan to process at least 150 radiographs per
The operating costs per X-ray are $4 for machine A and $3 for the
machine B. How many X-rays per day must each machine process to minimize
costs?
a. Solve the problem graphically and analytically.
b. How much are you willing to pay for additional capacity on machine A?

I. Graphical and analytical resolution:

Min Z = 4 x1 + 3 x2

(1) x1 ≤ 80

(2) x2 ≤ 100

(3) x1+x2≥150

To graph the isocost line:

4x1 + 3 x2 = 120 x1 = 0; x2 = 40 y x2 = 0; x1 = 30

Carrying this line parallel until it touches the first point on the graph (point
the closest to the origin is the lowest cost), it is found that the optimal combination is
the corresponding to point (a).

Page 8
To verify that (a) is the mixture that minimizes costs, we replace the values that
take x1 and x2 at points (a), (b), and (c) in Z:

X1 + x2 = 150

X2 = 100

X1 = 50

Z (a) = 4 * 50 + 3 * 100

Z (a) = $ 500

X1 = 80

X2 = 100

Z (b) = 4 * 80 + 3 * 100

Z (b) = $ 620

X1 + x2 = 150

X1 = 80

X2 = 70

Z (b) = 4 * 80 + 3 * 70

Z (b) = $ 530

Page 9
B. How much are you willing to pay for additional capacity in machine A?

I would not pay anything for additional capacity on that machine, since there is capacity.
sufficient (of the 80 X-rays daily that it can process, the optimal mix is to perform
50) - and on the other hand, its operating costs are higher than those of machine B -.

Example #2

An auditing company specializes in preparing settlements and

audits of small businesses. They are interested in knowing how many audits and
Payments can be made monthly to maximize your income. You
It has 800 hours of direct work and 320 hours for review. One
audit on average requires 40 hours of direct work and 10 hours of
review, also contributes an income of 300 dollars. A tax settlement
requires 8 hours of direct work and 5 hours of review, produces a
deposit of 100 dollars. The maximum number of monthly withdrawals available is
60.
OBJECTIVE: Maximize total revenue.
DECISION VARIABLE: Number of audits (X1).
Number of settlements (X2).
RESTRICTIONS: Available direct work time
Available review time
Maximum number of settlements.

Ejercicio 1:Maximizar: Z = 300X1+ 100X2

Subject to: 40X1+ 8x2 800

10X1+ 5X2 320
X2≤ 60
X1,X2 0

Page
10
The optimal solution is always found at one of the vertices of the set
feasible solutions. These values are analyzed in the objective function. The vertex
The best value of the objective function will represent the optimal solution.
Optimal solution:

X1=12 audits
X2= 40 settlements
Z= $7600

Objective Function:
Maximize

Restrictions:

Optimal solution.
y (hectares). The optimal value
is (dollars).

Page
11
Problems without solutions

The system of equations corresponding to the constraints of a problem can

not having points that simultaneously satisfy all the constraints if none of
the points that satisfy one of the restrictions also satisfy another of these. This is
It is generally due to an inadequate approach to the problem. In such cases, it is said
that the problem does not have a feasible solution.

An example like this would be: Restriction

1: 4x + 3y ≥ 15 Constraint
2: 6x + 3y ≤ 12
x, y ≥ 0

There is no feasible region.

Methodological Guide # 2
The following is a series of exercises to be solved and to reinforce the
learning.

Exercise 1: Maximize: Z = 20X1+ 22X2

Subject to: 8X1+ 6X2 48

6X1+ 8X2 48
7X1+ 7X2= 42
X1,X2 0

Exercise 2: Maximize: Z = 80X1+ 60X2

Subject to: X1+ X2= 200

X1 50
X2 80
X1, X2 0

Exercise 3: Minimize: Z = 1.5X1+ 2.0X2

Subject to: 2X1+ 2X2 8

2X1+ 6X1 12
X1, X2 0

Exercise 4: Masaya Furniture Factory

We will observe that the FMM has a limited capacity, that is, the dining rooms
Virginiano and Masaya share the two departments of production and painting, each
one of which has limited daily capabilities and therefore must be
considered as scarce resources.

Each dining room has to be processed in the construction departments and

Painting.

Page
12
To produce a Virginian dining room, 6 hours of construction and 8 hours are required.
of painting.

To produce a Masaya type dining room, it requires 12 hours in construction and 4

hours in painting.

The FMM has a daily capacity of 120 hours in the construction department.
and 64 hours daily in the painting department.

To determine the best or optimal combination of both types of dining rooms that
they have to manufacture with the aim of maximizing utility, the FMM has to allocate
its limited capabilities (scarce resources) of the Construction and departments
Transport in a way that can achieve its goal.

Page
13