INVESTIGACIÓN

OPERATIVA
UNIDAD 2:
Modelos de Programación Lineal

SEMANA 3 – SESIÓN 1:

• Formulación de problemas de programación lineal.

• Definición de variables, Función objetivo,
restricciones y condición de no-negatividad.
• Método Gráfico: Solución de problemas de
programación lineal de dos variables.
• Representación gráfica, área solución, solución
óptima.
 LOGROSDELAPRENDIZAJE
Logro general de aprendizaje de la Asignatura
Logro de aprendizaje de la Unidad 2
Al finalizar la asignatura, los
alumnos aplican herramientas Logro de la Semana 2
de investigación operativa en Al finalizar la unidad los
las áreas administrativa, alumnos aplican modelos de
comercial, logística, proyectos programación lineal en Al finalizar la semana los
y producción desde un diversas áreas de las ciencias alumnos solucionan problemas
enfoque cuantitativo que les administrativas. de programación lineal de dos
permita tomar decisiones variables por el método
gerenciales. gráfico, método de
maximización y minimización.

2
Introducción
La programación lineal es un método de solución de
problemas desarrollado para ayudar a los gerentes a tomar
decisiones.
Consideremos las siguientes aplicaciones típicas:
- Un fabricante quiere elaborar un programa de producción y
una política de inventario que satisfaga la demanda de
ventas en periodos futuros. En términos ideales, el
programa y la política permitirán a la empresa satisfacer la
demanda y al mismo tiempo minimizar los costos totales de
producción de inventario.
- Un analista financiero debe seleccionar un portafolio entre
diversas alternativas de acciones e inversiones. Al analista le
gustaría establecer el portafolio que maximice el
rendimiento de la inversión.
Introducción
- Un gerente de marketing quiere determinar como asignar
mejor un presupuesto de publicidad fijo entre medio de
publicidad alternos como la radio, la televisión, el periódico
y las revistas. Al gerente le gustaría determinar la
combinación de medios que maximice la efectividad de la
publicidad.
- Una empresa tiene almacenes en varias ubicaciones. Dadas
las demandas especificas de los clientes, ala empresa le
gustaría determinar cuanto debe enviar cada almacén a
cada cliente, de modo que los costos del transporte local se
minimice.
Introducción
En todos los problemas de programación lineal, el objetivo
es la maximización o minimización de alguna cantidad.

Pero debemos saber que todos los problemas de

programación lineal tienen una segunda propiedad: las
limitaciones o restricciones.
Ejemplo
Gepetto S.L., manufactura muñecos y trenes de madera.
Cada muñeco:
• Produce un beneficio neto de 3 €.
• Requiere 2 horas de trabajo de acabado.
• Requiere 1 hora de trabajo de carpinteria.
Cada tren:
• Produce un beneficio neto de 2 €.
• Requiere 1 hora de trabajo de acabado.
• Requiere 1 hora trabajo de carpinteria.
Cada semana Gepetto puede disponer de:
•Todo el material que necesite.
• Solamente 100 horas de acabado.
•Solamente 80 horas de carpinteria.
También:
• La demanda de trenes puede ser cualquiera (sin límite).
• La demanda de muñecos es como mucho 40.

Gepetto quiere maximizar sus beneficios.

¿Cuántos muñecos y cuántos trenes debe fabricar?

6
Este problema es un ejemplo típico de un problema de programación lineal (PPL).

Variables de Función Objetivo. En cualquier Restricciones

Decisión PPL, la decisión a tomar es Son desigualdades que
como maximizar (normalmente el limitan los posibles
x = nº de muñecos beneficio) o minimizar (el coste) valores de las variables
producidos a la de alguna función de las de decisión.
semana variables de decisión. Esta En este problema las
y = nº de trenes función a maximizar o minimizar restricciones vienen
producidos a la se llama función objetivo. dadas por la
semana disponibilidad de horas
El objetivo de Gepetto es de acabado y carpintería
elegir valores de x e y para y por la demanda de
maximizar 3x + 2y. Usaremos muñecos.
También suele haber
la variable z para denotar el restricciones de signo o
valor de la función objetivo. La no negatividad:
función objetivo de Gepetto es: x≥0
y≥0

Max z = 3x + 2y
7
 Restricciones
Cuando x e y crecen, la función objetivo de Gepetto también crece.
Pero no puede crecer indefinidamente porque, para Gepetto, los
valores de x e y están limitados por las siguientes tres restricciones:
Restricción 1: no más de 100 horas de tiempo de acabado pueden ser usadas.
Restricción 2: no más de 80 horas de tiempo de carpinteria pueden ser usadas.
Restricción 3: limitación de demanda, no deben fabricarse más de 40 muñecos.

Estas tres restricciones pueden expresarse matematicamente

por las siguientes desigualdades:

Restricción 1: 2 x + y ≤ 100
Restricción 2: x + y ≤ 80

Restricción 3: x ≤ 40

Además, tenemos las restricciones de signo: x ≥ 0 e y ≥ 0

8
 Formulación matemática del PPL
Variables de Decisión x = nº de muñecos producidos a la semana
y = nº de trenes producidos a la semana

Muñeco Tren

Beneficio 3 2 Max z = 3x + 2y (función objetivo)

Acabado 2 1 ≤ 100 2 x + y ≤ 100 (acabado)

Carpintería 1 1 ≤ 80 x + y ≤ 80 (carpinteria)

Demanda ≤ 40 x ≤ 40 (demanda muñecos)

x ≥0 (restricción de signo)

y ≥0 (restricción de signo)
 Formulación matemática del PPL

Para el problema de Gepetto, combinando las restricciones de

signo x ≥ 0 e y ≥ 0 con la función objetivo y las restricciones,
tenemos el siguiente modelo de optimización:

Max z = 3x + 2y (función objetivo)

Sujeto a (s.a:)
2 x + y ≤ 100 (restricción de acabado)

x + y ≤ 80 (restricción de carpinteria)

x ≤ 40 (restricción de demanda de muñecos)

x ≥0 (restricción de signo)

y ≥0 (restricción de signo)

10
 Región factible

La región factible de un PPL es el conjunto de todos los puntos

que satisfacen todas las restricciones. Es la región del plano
delimitada por el sistema de desigualdades que forman las
restricciones.

x = 40 e y = 20 está en la región Restricciones de Gepetto

factible porque satisfacen todas 2x + y ≤ 100 (restricción finalizado)
las restricciones de Gepetto. x + y ≤ 80 (restricción carpintería)

Sin embargo, x = 15, y = 70 no x ≤ 40 (restricción demanda)

está en la región factible porque x ≥0 (restricción signo)
este punto no satisface la y ≥0 (restricción signo)
restricción de carpinteria
[15 + 70 > 80].

11
 Solución óptima
Se puede demostrar
Para un problema de maximización, una solución
que la solución
óptima es un punto en la región factible en el cual
óptima de un PPL
la función objetivo tiene un valor máximo. Para un
está siempre en la
problema de minimización, una solución óptima es
frontera de la región
un punto en la región factible en el cual la función
factible, en un
objetivo tiene un valor mínimo.
La mayoría de PPL tienen solamente una solución vértice (si la
óptima. Sin embargo, algunos PPL no tienen solución es única) o
solución óptima, y otros PPL tienen un número en un segmento
infinito de soluciones. entre dos vértices
contiguos (si hay
Más adelante veremos que la solución del PPL de infinitas soluciones)
Gepetto es x = 20 e y = 60. Esta solución da un
valor de la función objetivo de:
Cuando decimos que x = 20 e y = 60 es la solución óptima,
z = 3x + 2y = 3·20 + 2·60 = 180 €
estamos diciendo que, en ningún punto en la región factible, la
función objetivo tiene un valor (beneficio) superior a 180.

12
 Representación Gráfica de las restricciones
Y
Cualquier PPL con sólo dos
variables puede resolverse
100
gráficamente. 2x + y = 100

Por ejemplo, para representar 80

gráficamente la primera
restricción, 2x + y ≤ 100 :
60
Dibujamos la recta 2x + y = 100

Elegimos el semiplano que 40

cumple la desigualdad: el
punto (0, 0) la cumple
(2·0 + 0 ≤ 100), 20

así que tomamos el

semiplano que lo contiene.
20 40 60 80 X

13
 Dibujar la región factible

Puesto que el PPL de Gepetto tiene dos variables, se puede resolver

gráficamente. La región factible es el conjunto de todos los puntos
que satisfacen las restricciones:

2 x + y ≤ 100 (restricción de acabado)

x + y ≤ 80 (restricción de carpintería)
x ≤ 40 (restricción de demanda)
x ≥0 (restricción de signo)
y ≥0 (restricción de signo)

Vamos a dibujar la región factible que satisface estas restricciones.

14
 Dibujar la región factible
Y

100
2x + y = 100
Restricciones
2 x + y ≤ 100
80
x + y ≤ 80

x ≤ 40
60
x ≥0
y ≥0
40

Teniendo en
cuenta las 20
restricciones de
signo (x ≥ 0, y ≥ 0),
nos queda: 20 40 60 80 X

15
 Dibujar la región factible
Y

100

Restricciones 80

2 x + y ≤ 100

x + y ≤ 80 60 x + y = 80
x ≤ 40
x ≥0 40

y ≥0

20

20 40 60 80 X

16
 Dibujar la región factible
Y

100

Restricciones 80
x = 40
2 x + y ≤ 100

x + y ≤ 80 60

x ≤ 40
x ≥0 40

y ≥0

20

20 40 60 80 X

17
 Dibujar la región factible
Y
La intersección
de todos estos
semiplanos 100
2x + y = 100
(restricciones)
nos da la región
80
factible x = 40

60

x + y = 80
40

Región
20 Factible

20 40 60 80 X

18
 Vértices de la región factible
Y Restricciones
La región factible (al 2 x + y ≤ 100
estar limitada por
x + y ≤ 80
rectas) es un polígono. 100
2x + y = 100
En esta caso, el x ≤ 40
polígono ABCDE. x ≥0
80 E x = 40
Como la solución y ≥0
óptima está en alguno
D
de los vértices (A, B, C, 60

D o E) de la región
x + y = 80
factible, calculamos 40
esos vértices.
Región
20 Factible C

B
A 20 40 60 80 X

19
 Vértices de la región factible
Y
Los vértices de la región factible
son intersecciones de dos
rectas. El punto D es la 100
intersección de las rectas 2x + y = 100

2x + y = 100 x = 40
80 E(0, 80)
x + y = 80
La solución del sistema x = 20,
D (20, 60)
y = 60 nos da el punto D. 60

B es solución de
40
x = 40
y=0
Región
C es solución de C(40, 20)
20 Factible
x = 40 x + y = 80

2x + y = 100 B(40, 0)
E es solución de A(0, 0) 20 40 60 80 X
x + y = 80
20
 Resolución gráfica
Y
Max z = 3x + 2y

Para hallar la 100

solución óptima,
(0, 80)
dibujamos las 80
rectas en las
cuales los puntos (20, 60)
tienen el mismo 60

valor de z.
La figura muestra 40

estas lineas para

Región
z = 0, z = 100, y z (40, 20)
20 Factible
= 180
(40, 0)
(0, 0) 20 40 60 80 X
z = 180
z=0 z = 100 18
 Resolución gráfica Y

Max z = 3x + 2y
100

La última recta de (0, 80)

80
z que interseca
(toca) la región (20, 60)
factible indica la 60

solución óptima
para el PPL. Para 40
el problema de
Gepetto, esto Región
(40, 20)
ocurre en el 20 Factible
punto D (x = 20, y
(40, 0)
= 60, z = 180).
(0, 0) 20 40 60 80 X
z = 180
z=0 z = 100
22
 Resolución analítica
Y
Max z = 3x + 2y
También podemos encontrar la 100
solución óptima calculando el
valor de z en los vértices de la
80
(0, 80)
región factible.
Vértice z = 3x + 2y (20, 60)
(0, 0) z = 3·0+2·0 = 0 60

(40, 0) z = 3·40+2·0 = 120

(40, 20) z = 3·40+2·20 = 160 40
(20, 60) z = 3·20+2·60 = 180
(0, 80) z = 3·0+2·80 = 160 Región
Factible (40, 20)
20
La solución óptima es:
x = 20 muñecos (40, 0)
y = 60 trenes
(0, 0) 20 40 60 80 X
z = 180 € de beneficio

23
Hemos identificado la región factible para
el problema de Gepetto y buscado la
solución óptima, la cual era el punto en la
región factible con el mayor valor posible
de z.

24
Recuerda que:

• La región factible en cualquier PPL

está limitada por segmentos (es un
polígono, acotado o no).

• La región factible de cualquier PPL

tiene solamente un número finito de
vértices.

• Cualquier PPL que tenga solución

óptima tiene un vértice que es óptimo.

25
Ejemplo de maximización
Darizza es una empresa pequeña que fabrica una variedad
de productos químicos. En un proceso de producción
particular se utilizan tres materias primas para elaborar dos
productos: un aditivo para combustible y una base para
solvente. El aditivo se vende a las compañías petroleras y se
utiliza en la producción de gasolina y otros combustibles. La
base para solvente se vende a una variedad de compañías
de productos químicos y se usa en artículos de limpieza
para el hogar y la industria.
Ejemplo de maximización
Las tres materias primas se mezclan para formar el aditivo
para combustible y la base para solvente, como en la tabla,
en la que se muestra que una tonelada de aditivo para
combustible es una mezcla de 0.4 ton de material 1 y 0.6
ton de material 3. mientras que una tonelada de base
solvente es una mezcla de 0.5 ton de material 1, 0.2 ton de
material 2 y 0.3 ton de material 3.

Producto
Aditivo para Base para solvente
combustible
Material 1 0.4 0.5
Material 2 0.2
Material 3 0.6 0.3
Ejemplo de maximización
La producción de Darizza esta restringida por una
disponibilidad limitada de las tres materias primas. Cuenta
con las siguientes cantidades de materia prima:
* Debido al deterioro y a la naturaleza del proceso de
producción, los materiales que no se utilizan en la
producción actual son inútiles y deben desecharse.

Material Cantidad disponible para

producción
Material 1 20 ton
Material 2 5 ton
Material 3 21 ton
Ejemplo de maximización
El departamento de contabilidad analizo las cifras de
producción, asigno todos los costos relevantes y determino
precios para ambos productos que generarías una
contribución a las utilidades de $40 por cada tonelada de
aditivo para combustible producido y $30 por cada
tonelada producida de base para solvente.

Con ayuda de la programación lineal determinar la cantidad

de toneladas de aditivo para combustible y de base
solvente a producir con el fin de maximizar la contribución
total a las utilidades.
Formulación del problema
Darizza quiere determinar cuanto de cada producto debe
fabricar para maximizar la contribución total a las
utilidades.

El numero de toneladas disponibles de los tres materiales

que se requiere para fabricar los dos productos delimitan la
cantidad de toneladas de cada producto que pueden
elaborarse.
Este problema es un ejemplo típico de un problema de programación lineal (PPL).

Variables de Función Objetivo. En cualquier Restricciones

Decisión PPL, la decisión a tomar es 3 restricciones limitan
(insumos como maximizar (normalmente el la producción:
del beneficio) o minimizar (el coste) - Restricción 1, ton de
problema) de alguna función de las material 1 debe ser
variables de decisión. Esta menor o igual a 20
F = ton de aditivo función a maximizar o minimizar - Restricción 2, ton de
para se llama función objetivo. material 2 debe ser
combustible menor o igual a 5
S = ton de base de El objetivo de Darizza es - Restricción 3, ton de
solvente maximizar la contribución total material 3 debe ser
a las utilidades: menor o igual a 21

Contribución total a las utilidades

Max 40F + 30 S

3
1
 Restricciones
Las toneladas de material utilizadas no debe superar es decir debe
ser menor o igual a las toneladas de material disponibles:

Restricción 1: no más de 20 ton de material 1 disponibles.

Restricción 2: no más de 5 ton de material 2 disponible.
Restricción 3: no mas de 21 ton disponibles de material 3.

Estas tres restricciones pueden expresarse matematicamente

por las siguientes desigualdades:

Restricción 1: 0.4F + 0.5S ≤ 20

Restricción 2: 0.2S ≤ 5

Restricción 3: 0.6F + 0.3S ≤ 21

Además, tenemos las restricciones de signo: F ≥ 0 e S ≥ 0

o de no negatividad
3
2
 Formulación matemática del PPL

Para el problema de Darizza, combinando las restricciones de

signo F ≥ 0 e S ≥ 0 con la función objetivo y las restricciones,
tenemos el siguiente modelo de optimización:

Max = 40F + 30S (función objetivo)

Sujeto a (s.a:)
0.4F + 0.5S ≤ 20 (material 1)
0.2S ≤5 (material 2)

0.6F + 0.3S ≤ 21 (material 3)

F ≥0 (restricción de signo)

S ≥0 (restricción de signo)

33
 Representación Gráfica de las restricciones
Y
Cualquier PPL con sólo dos
variables puede resolverse
100
gráficamente. 2x + y = 100

Por ejemplo, para representar 80

gráficamente la primera
restricción, 0.4F + 0.5S ≤ 20 :
60
Dibujamos la recta 0.4F +
0.5S= 20
40
Elegimos el semiplano que
cumple la desigualdad: el
punto (0, 0) la cumple 20

(0.4*0 + 0.5 *0 ≤ 20),

así que tomamos el
semiplano que lo contiene. 20 40 60 80 X

34
 Dibujar la región factible

Puesto que el PPL de Darizza tiene dos variables, se puede resolver

gráficamente. La región factible es el conjunto de todos los puntos
que satisfacen las restricciones:

0.4F+0.5S ≤ 20 (restricción de acabado)

0.2S ≤ 5 (restricción de carpintería)
0.6F + 0.3S ≤ 21(restricción de demanda)
F ≥0 (restricción de signo)
S ≥0 (restricción de signo)

Vamos a dibujar la región factible que satisface estas restricciones.

35
 Dibujar la región factible
Y

100
0.4F+0.5S= 20
Restricciones
0.4F+0.5S ≤ 20
80
0.2S ≤ 5

0.6F+0.3S≤ 2 1
60
F ≥0
S ≥0
40

Teniendo en
cuenta las 20
restricciones de
signo (x ≥ 0, y ≥ 0),
nos queda: 20 40 60 80 X

38
Que aprendimos hoy …
Conclusiones
- En la programación lineal podemos utilizar el método
gráfico para identificar la mejor opción que cumpla con la
condición de maximización de los valores buscados para
una situación dada.
- Es importante identificar algunos datos importantes
como cuales son las restricciones, cual es la función
objetivo.
- La función objetivo y las restricciones ayudan en la
construcción de la solución deseada.
 Complementos para el logro del
aprendizaje de la Semana3
Teoría
Revisar el marco teórico del archivo: LECTURAUNIDAD 2ANDERSON
Libro: Métodos Cuantitativos para los Negocios (David Anderson),
páginas 235 al 270.

Práctica
Resolver los problemas del archivo: LECTURAUNIDAD 2ANDERSON
Libro: Métodos Cuantitativos para los Negocios (DavidAnderson),
páginas 270 al 294.

41