Unidad 1 semana 2 sección 2

Dr. José A. Castillo Montes

 Programación Lineal

• La P.L. es una técnica matemática de

optimización que permite la administración
racional de recursos ( humanos, materiales
George Dantzing y económicos) a diversas actividades de la
organización .

• Es una herramienta para resolver

Russell Ackoff problemas de decisión , tanto las
condiciones como el objetivo se presentan
por medio de funciones lineales
denominado modelo de P.L.

West Churchman
APLICACIONES DE LA PROGRAMACIÓN LINEAL

1. Las instituciones financieras usan la P.L.

para resolver problemas relacionados con
presupuesto y planeación.

2. Las empresas industriales, lo usan para

determinar la mezcla de alimentos y productos
químicos.

3. En la mercadotecnia, se emplea para

seleccionar los medios de publicidad y los
canales de distribución para la comercialización
de los productos.
4. En la agricultura: Los agricultores deben localizar
áreas de plantación sujetas a varias restricciones
como subsidios del gobierno, disponibilidad de capital
y de mano de obra, riego, transporte y uso de
equipamiento

2. Planificación de las redes de telecomunicaciones:

Los modelos lineales se han usado para minimizar el
costo total de la expansión e instalación de la red.
Las compañías de telecomunicaciones están
obligadas a modernizarse y a expandir continuamente
sus redes para poder satisfacer la demanda siempre
creciente de clientes., etc.
 Formulación del modelo de PROGRAMACION
LINEAL
• Un modelo de programación lineal esta
compuesto de lo siguiente:
* Un conjunto de variables de decisión
* Una función objetivo
* Un conjunto de restricciones

1. Variables de decisión. Son las incógnitas del

problema, es decir se trata de aquello que
necesitamos decidir: qué y cuánto hacer de las
diversas acciones o productos.
2. Función objetivo. Función matemática que
relaciona las variables de decisión que
representan el objetivo que se desea alcanzar.
Esta función puede ser:
• Maximizar (Max): aumentar utilidades, ingresos
por ventas., etc
• Minimizar (Min): reducir costos, tiempo de
finalización de un trabajo, mermas, riesgo de una
operación bursátil, etc.
3. Restricciones: Constituido por el conjunto de
desigualdades (<, > ) debido a recursos limitados,
ya sean éstos materias primas, mano de obra o
condiciones del mercado.

4. Condición de no negatividad: establece que

las variables de decisión siempre deben ser
positivas.
MODELO GENERAL DE PROGRAMACIÓN LINEAL

(Maxim o Mini) Z= C1X1+ C2X2 +...+ Cn-1Xn-1+ CnXn

Sujeto a:
a11X1 + a12X2 + ... . . . + a1nXn (< = > ) b1

a21X1 + a22X2 + ... . . . + a2nXn (< = > ) b2

: :
ai1X1 + ai2X2 + ... . . . + ainXn (< = > ) bi
: :
am1X1 + am2X2 + ... . . . + amnXn (< = > ) bm

Xj >= 0 ( j = 1,2,3, . . . , n ; i = 1, 2, 3, . . ., m )
 ESTRUCTURA DEL MODELO DE P.L.
n
Optimizar Z =
c x
j 1
j j

a x
Sujeta a:
ij j  bi i  1, 2,......, m
j 1
x j  0 j  1, 2,......., n
Z =valor de la medida global de efectividad
Xj = nivel de la actividad j (para j = 1,2,...,n)
Cj = incremento enx Zj que j  1, 2,.......,
0 resulta n
al aumentar una unidad
en el nivel de la actividad j
bi = cantidad de recurso i disponible para asignar a las
actividades (para i = 1,2,...,m)
aij = cantidad del recurso i consumido por cada unidad de la
actividad j
solución del modelo de programación
lineal

SOLUCIÓN OPTIMA

1. Las decisiones factibles que llevan la mayor

solución o contribución total de las
ganancias, se le conoce como solución
optima.

2. La función objetivo debe maximIzarse sobre

el conjunto de soluciones factibles, es decir
las decisiones que satisfacen todas las
restricciones.
MÉTODO GRÁFICO
El método gráfico se emplea para resolver
problemas que presentan sólo 2 variables de
decisión. El procedimiento consiste en trazar
las ecuaciones de las restricciones en un eje
de coordenadas X1, X2 para tratar de identificar
el área de soluciones factibles que cumplen
con todas las restricciones.
Procedimiento para la Solución Gráfica de problemas de
P.L. con dos variables de decisión

Para realizar la gráfica es necesario tomar en

cuenta las siguientes recomendaciones:

1.Preparar una gráfica para cada restricción que

muestre las soluciones que satisfagan la
restricción.

2.Determinar la región factible identificando las

soluciones que satisfacen simultáneamente todas
las restricciones.

3.Trazar la línea de la función objetivo que

muestren los valores de las variables de decisión.
Región factible : conjunto de puntos extremos o
vértices que satisfacen todas las restricciones del
modelo.
Solución óptima : Es el punto de la RF, donde se
obtiene el mejor valor para la función objetivo
Problema de maximización

Solución optima
Problema de Minimización

Solución optima
 Caso 1- problema de Maximización.
Un fabricante está tratando de decidir las cantidades de
producción para dos artículos: mesas y sillas. Se cuenta
con 96 unidades de material y con 72 horas de mano de
obra. Cada mesa requiere 12 unidades de material y 6
horas de mano de obra. Por otra parte, las sillas utilizan
8 unidades de material cada una y requieren 12 horas
de mano de obra por silla. El margen de beneficio para
las mesas es de S/. 90 por unidad y para las sillas: S/.
75 por unidad. El fabricante prometió construir por lo
menos dos mesas. Se pide Formular el problema
mediante un modelo de P.L. y encontrar la solución
optima.
 organización de la información

Producción Artículos Requerimiento

Mesas Sillas
P1 12 8 96
P2 6 12 72
P3 1 0 2
Utilidad 90 75
SOLUCIÓN DEL MODELO

1) Formulación del Problema

Definiendo las Variables de decisión:

x1= número de mesas producidas

x2= número de sillas producidas

Restricciones lineales
12x1+ 8x2≤96 (restricción de material)
6x1+ 12x2≤72 (restricción de mano de obra)
x1≥2 (restricción de promesa del fabricante)
x1≥0, x2≥0 (restricciones de no negatividad)
Función objetivo ( Maximizar los beneficios
totales)
Maximizar Z = 90x1+ 75x2

Modelo matemático en su forma canónica

Maximizar Z = 90x1+ 75x2
Sujeto a:

12x1+ 8x2≤96
6x1+ 12x2≤72
x1≥2
x1≥0, x2≥0
 Se dibuja sobre la gráfica las
X2
restricciones de no negatividad

(0,0) X1
 De la restricción I, de su forma
canónica, lo convertimos en su 12x1+ 8x2= 96
forma estándar y tendremos:
12x1+ 8x2≤96 X1 X2
0 12
x2 8 0
Restricción I

(0;12

restricción de material

(8;0) x1
 Graficamos ahora la Restricción II

6x1+ 12x2= 72
X1 X2
0 6
12 0
x2

Restricción II
restricción de mano de obra
(0;6)

(12;0) x1
 Graficando la Restricción III
x1≥2

x2
Restricción III

restricción de promesa del

fabricante

(2; 0) x1
 R1 R3

R2
D

A B
Calculando el punto (C) donde se interceptan las dos
restricciones:
Resolviendo simultáneamente las dos ecuaciones y multiplicando la
ecuación II por -2, para despejar la variable X2, tendremos:

12X1 + 8X2 = 96 (R1)

(-2) (6X1 + 12X2 = 72) (R2)

12X1 + 8X2 = 96
-12X1 – 24X2 = -144
-16X2 = - 48
X2 =3
Luego: en la ecuación I resulta: 12X1 + 8(3) =96
12X1 =96 – 24
12X1 = 72, despejando resulta: X1 = 6
Pc(X1,X2) = PC(6,3)
Entonces: Zc = 90(6) + 75(3)
ZC = 765

Por lo tanto la solución optima esta en el punto C

(Por ser un problema de maximización)
Aquí la Z se vuelve el mayor posible.
X1 =6
X2 =3
ZC = S/. 765

Así podemos concluir que las soluciones que mejor resuelven el

problema y evidentemente la optima se encuentra en el punto
extremo C (6;3). Esto significa, que es necesario producir 6
mesas y 3 sillas para obtener un beneficio total de S/. 765.
En síntesis, podemos evaluar cada uno de las
coordenadas

Puntos Coordenadas Valor de Z

factibles Z=90x1+75x2
A (2; 0) 180
B (8; 0) 720
C (6; 3) 765
D (2; 5) 555
 En el punto C, se
encuentra entre R1
y R2
Solución Optima

D (2;5)

C
(6:3)

RSF

A (2;0) B (8;0)
 Caso 2 : Minimización
Suponga que un cliente planea comprar ciertos tipos de
alimentos carne y pescado. Ambos pueden proveer unidades
de nutrientes para su mínimo requerimiento durante un
periodo determinado y que se indica en la siguiente tabla:

Tipo de Unidades de Mínimo de

nutriente nutrientes unidades
1Kg. Carne 1 Kg. requeridas
Pescado
A 1 3 9
B 2 2 10
C 4 2 12
Precio por S/. 18 S/. 22
unidad

¿Cuántos kilos de carne y de pescado deberá comprar para obtener

los mínimos requerimientos de nutrientes al mínimo costo?
SOLUCIÓN DEL MODELO

1) Formulación del Problema

Definiendo las Variables de decisión:

x1= cantidad de kilos de carne de res

x2= cantidad de kilos de pescado

Restricciones lineales
1x1+ 3x2 ≥ 9 ( nutriente tipo A) R1
2x1+ 2x2 ≥ 10 (nutriente tipo B ) R2
4x1 + 2x2 ≥ 12 (nutriente tipo C) R3
x1≥0, x2≥0 (restricciones de no negatividad)
Función objetivo ( Minimizar los costos totales)
Minimizar Z* = 18x1+ 22x2

Modelo de P.L. en su forma canónica

Minimizar Z* = 18x1+ 22x2

Sujeto a:

1x1+ 3x2 ≥ 9 ( nutriente tipo A) R1

2x1+ 2x2 ≥ 10 (nutriente tipo B ) R2
4x1 + 2x2 ≥ 12 (nutriente tipo C) R3
x1≥0, x2≥0 (restricciones de no negatividad)
 Se dibuja sobre la gráfica las restricciones
X2 de no negatividad

(0,0) X1
De la restricción I, de su forma canónica, lo
convertimos en su forma estándar y
tendremos: 1x1+ 3x2 = 9
1x1+ 3x2 ≥ 9 ( nutriente tipo A) R1
X1 X2
X2 0 3
9 0

(0,3)

X1
(9,0)
Graficamos ahora la Restricción II

2x1+ 2x2 = 10 (nutriente tipo B ) R2 X1 X2

0 5
X2
5 0

(0,5)

X1
(5,0)
Graficamos ahora la Restricción III
4x1 + 2x2 = 12 (nutriente tipo C) R3 X1 X2
0 6
3 0

(6,0)

(3,0)
 2. Grafico para un problema de minimización

A
Calculando el punto (B) donde se interceptan las restricciones R1 y
R2: Resolviendo simultáneamente las dos ecuaciones y
multiplicando la ecuación I por -2, para despejar la variable X2,
tendremos:

(-2) ( 1X1 + 3X2 = 9 ) (R1)

2X1 + 2X2 = 10 (R2)

-2X1 - 6X2 = -18

2X1 + 2X2 = 10
- 4X2 =-8
X2 =2
Luego: en la ecuación II resulta: 2X1 + 2(2) =10
2X1 =10 – 4
2X1 = 6, despejando resulta: X1 = 3
 PB(X1,X2) = PB(3;2)
Entonces: ZB = 18(3) + 22(2)
ZB = 98.00

Veamos ahora el punto testigo C, donde se realiza la intersección

de las restricciones R2 y R3: Resolviendo ambas ecuaciones
simultáneamente, tendremos:

2x1+ 2x2 = 10 (R2)

4x1 + 2x2 = 12 (R3)
Para despejar X1, multiplicamos la ecuación (R2) por (-1)

(-1) (2x1+ 2x2 = 10 )

4x1 + 2x2 = 12

-2X1 – 2X2 = - 10
4x1 + 2x2 = 12
2X1 = 2
X1 =1
Luego: en la ecuación (R3) resulta: 4X1 + 2(2) =12
4(1) + 2X2 = 12

4 + 2X2 = 12 2X2 = 12 - 4, despejando resulta: X2 = 4

PC(X1,X2) = PC (1;4)
Entonces: ZC = 18(1) + 22(4)
ZC = 106.00
• Evaluando cada punto del conjunto convexo

Puntos Coordenadas Valor de Z=

factibles 18X1+22X2
A ZA = ( 9 ; 0 ) 162
B ZB = ( 3 ; 2 ) 98
C ZC = ( 1 ; 4 ) 106
D ZD = ( 0 ; 6 ) 132
Por lo tanto la solución optima esta en el punto testigo
B (por ser un problema de Minimización )

Por tanto el valor de Z* se vuelve el menor posible.

X1 = 3
X2 = 2
ZB = S/. 98.00

Como vemos, el punto B (3;2)es el mínimo, o sea

tenemos utilizar 3 kilogramos de carne y 2
kilogramos de pescado, para lograr el mínimo
costo permisible
D
(0;6)

El punto B se
RSF encuentra entre R1
C (1;4) y R2

Solución optima

B (3;2)

A
(9;0)
Resolución mediante el programa LINDO
LINDO(Linear, Interactive, and Discrete ptimizer)

LP OPTIMUM FOUND AT STEP 2

OBJECTIVE FUNCTION VALUE

1) 98.00000

VARIABLE VALUE REDUCED COST

X1 3.000000 0.000000
X2 2.000000 0.000000

ROW SLACK OR SURPLUS DUAL PRICES

2) 0.000000 -2.000000
3) 0.000000 -8.000000
4) 4.000000 0.000000

NO. ITERATIONS= 2
 Otro ejemplo:

Max Z = 2x1 − x2
s.a.: x1 − x2 ≤ 2
5x1 − 2x2 ≤ 16
x1, x2 ≥ 0

R1: x1 − x2 = 2
si x1 = 0 x2 = −2;
si x2 = 0 x1 = 2
P (X1;X2) = P(2; -2)

R2: 5x1 − 2x2 = 16

si x1 = 0 x2 = −8;
si x2 = 0 x1 = 16/5=3.2
P(X1;X2) = P(3.2; -8)
1. La recta paralela a 2x1−x2 = 0 que pasa por (1, 0) toma el
valor
Z = 2(1) − 0 = 2.

Luego la solución óptima es el punto A, que se obtiene

empleando ecuaciones simultaneas y multiplicando por -2 la
ecuación (R1), resulta:
R1: (-2)( x1 − x2 = 2)
R2: 5X1 – 2X2=16
Obtendremos
x1 = 4, x2 = 2.

2. Queda demostrado que la función objetivo:

Z = 2x1 − x2, alcanzara una solución factible
Z = 2(4) + 1(2)= 8−2 = 6. Aunque se observa que la región
factible es no acotada
Teorema:
La Función objetivo alcanza su máximo o mínimo en un punto
extremo de un conjunto convexo

Tipos de soluciones
En los problemas de programación lineal con dos
variables pueden darse varios tipos de soluciones
óptimas:
• Solución factible: cualquier punto situado en la
región factible
• Solución básica: se encuentra en la
intersección de rectas en los ejes coordenadas
• Solución básica factible: solución básica que
pertenece a la R.F.
• Solución básica factible degenerada: es la
solución básica factible en la que uno o
mas variables toman el valor cero.
• Solución básica no degenerada: si todas las
variables básicas son positivos.
• Solución múltiple (infinitas soluciones).
• Solución no acotada (ausencia de solución),
cuando la función objetivo no tiene valores
extremos, pues la región factible es no
acotada.
• Solución no factible, cuando no existe
región factible por falta de puntos
comunes en el sistema de inecuaciones.
• Solución degenerada, si en un solo
punto (que se dice degenerado)
coinciden tres o más de las rectas que
limitan la región factible
Solución no acotada

Solución múltiple
Solución infactible
 Actividad de aprendizaje :
Instrucciones:
¿Qué vas a hacer? . Con la finalidad de reforzar los
conocimientos adquiridos a lo largo de esta sesión realiza
lo siguiente:

1.Utilizar la guía de practica 1, para formular y resolver

mediante el uso de la programación lineal
2. Formar grupos de tres alumnos para formular y
resolver, por el método gráfico, el problema de la guía
de practica.
3. Desarrollar los problemas 5 al 8 (guía de practica 1)
en una hoja y colocar los nombres de las personas
que conforman el grupo. Se dará 45 minutos de
tiempo para terminarlo, luego del cuál el docente
procederá a verificar el procedimiento y resultados.
Bibliografía recomendada

1.Handy Taha: Investigación de Operaciones -

Capitulo 2: Introducción a la programación lineal,
pág. 11 al 18

2. Hillier – Liberman : investigación de operaciones

–capitulo 3: introducción a la programación lineal,
pág. 31 al 44

Recursos de internet
Muchos pequeños ejemplos de aplicación de la PL a modelos y su
resolución: http://www.ms.ic.ac.uk/jeb/or/lp.html
Programa LINDO: http://www.lindo.com/table/downloadt.html