UNIVERSIDAD DE MANAGUA
Al más alto nivel
Programación Lineal
Encuentro #3
Tema: Introducción a la programación lineal
Prof.: MSc. Julio Rito Vargas A. Grupos: CCEE y ADMVA /2016
Objetivos:
Obtener las soluciones factibles en un problema de programación lineal, resuelto por
método gráfico.
Reconocer si un problema de programación lineal dado, tiene una única solución,
múltiples soluciones o no tiene solución.
Utilizar el método gráfico para obtener la solución óptima de problemas de
programación lineal de dos variables.
Desarrollo:
Región factible:
La solución de un problema de programación lineal, en el supuesto de que exista, debe
estar en la región determinada por las distintas desigualdades. Esta recibe el nombre
de región factible, y puede ser cerrada (acotada) o abierta (no acotada).
Ejemplo de región factible cerrada o acotada:
¿Cuál es la región factible del sistema?
x-y ≥ 0
x≤5
Julio Rito Vargas Pág. 1
Ejemplo de región factible abierta o no acotada:
¿Cuál es la región factible del sistema?
2x+7y≥20
8x+2y≥16 x+y≥5
Solución óptima:
Si la región factible es cerrada la Si la región factible es abierta, puede
solución óptima está en un vértice haber solución única (en un vértice),
del polígono (cuando es única) o infinitas soluciones (todo un lado) o no
todo un lado del polígono (infinitas tener solución.
soluciones).
Julio Rito Vargas Pág. 2
Número de soluciones de un problema de programación lineal
Para un problema de minimización
Para un problema de maximización
Julio Rito Vargas Pág. 3
Ejemplo de PL con infinitas soluciones:
Consideremos el siguiente modelo matemático:
Maximizar z= x + y
Sujeto a:
x+y≤3
x+y≤2
x-y≥1
x≥ 0
y≥ 0
Su solución por método gráfico es:
(1.5,0.5)
Todo el segmento que va de (1.5, 0.5) hasta (2,0) señalado por la flecha es
solución óptima del problema lineal. Como usted sabe sobre un segmento
hay infinitos puntos y cada punto se representa por un par ordenado, por lo
tanto concluimos que el problema lineal resuelto tiene infinitas soluciones
infinitas de las cuales (1.5, 0.5) y (2,0) son dos de ellas.
Ejemplo de PL sin solución óptima:
Consideremos el siguiente modelo matemático:
Max Z = 3x1 + 2x2
sujeta a: 1/40x1 + 1/60x2 ≤ 1
1/50x1 + 1/50x2 ≤ 1
x1 ≥ 30
x2 ≤ 20
x1 ≥ 0, x2 ≥ 0
Julio Rito Vargas Pág. 4
Su solución por método gráfico es:
1/40X1 +1/60X2 ≤1 X1≥0
1/50X1 +1/50X2 ≤1
X2≥0
Puede observar en el gráfico que no hay región factible (no hay
polígono) por tanto no hay soluciones factibles por lo tanto no hay
solución óptima. Entonces estamos frente a un problema no
factible.
Ejemplo de PL con una solución óptima:
Planeación de una campaña publicitaria: Una compañía fabrica productos de limpieza para uso
domésticos. Este es un mercado muy competitivo y la compañía lucha en forma constante para
aumentar su porcentaje en el mercado. La administración decidió llevar a cabo una importante
campaña de publicidad que se enfocará en los siguientes tres productos claves:
Un quitamanchas para prelavado en aerosol.
Un nuevo detergente líquido para ropa.
Un polvo detergente para ropa con mercado establecido.
Esta campaña utilizará Televisión (TV) y Periódicos (P). Se desarrolló un comercial para aparecer
a nivel nacional que anunciará el detergente líquido para ayudar a establecer este nuevo
producto. La publicidad en periódicos promoverá los tres productos e incluirá cupones de
descuentos que los consumidores pueden usar para comprar el producto a precios reducidos.
La administración ha establecidos metas mínimas para la campaña:
1. El quitamanchas debe captar 3% adicional de su mercado.
2. El nuevo detergente líquido debe captar el 18% del mercado de detergente para ropa.
3. Un 4% de este mismo mercado debe ser captado por el detergente en polvo.
Julio Rito Vargas Pág. 5
La tabla siguiente muestra los aumentos estimados en las participaciones en estos mercados
por cada anuncio de publicidad en los medios respectivos. La razón para el -1% para el
detergente en polvo en la columna de televisión es que el comercial de TV que anuncia el nuevo
detergente líquido le quitará algunas ventas al detergente en polvo. La última fila de la tabla
muestra el costo por unidad de publicidad para medio.
El objetivo de la administración es determinar cuanta publicidad hacer en cada medio para
cumplir las metas de participación de mercado a un costo total mínimo.
Aumento en porcentajes de mercado por unidad de publicidad
Producto Televisión Periódico Incremento mínimo requerido
Quitamanchas 0% 1% 3%
Detergente 3% 2% 18%
líquido
Detergente en -1% 4% 4%
polvo
Costo unitario $1000 $2000
Solución:
Paso 1: Definición del problema.
Objetivo: Minimizar los costos totales de publicidad
Restricciones:
Dos medios de publicidad: TV y P
Costo unitario de cada anuncio: TV →$1000; P→$2000
Productos a publicitar:
Quitamanchas (A)
Detergente líquido (B)
Detergente en polvo (C)
Aumento de porcentaje de mercado por unidad de publicidad y medios
Quitamanchas → P =1%
Detergente líquido → TV=3% y P=2%
Detergente en polvo → TV=-1% y P=4%
Incremento mínimo requerido de mercado
Quitamanchas → 3%
Detergente líquido → 18%
Detergente en polvo → 4%
Julio Rito Vargas Pág. 6
Necesitamos saber cuántos anuncios en TV y P deben planificarse para alcanzar los objetivos de
la administración.
Llamaremos X1: cantidad de anuncios en TV
X2: cantidad de anuncios en Periódicos.
Paso 2: Construcción del modelo matemático lineal
Min Z= 1000X1 + 2000X2
Sujeto a:
1%X2 ≥ 3%
3%X1 + 2%X2 ≥ 18%
-1%X1 + 4%X2 ≥ 4%
X1 ≥ 0
X2 ≥ 0
Paso 3: Obtener una solución
La solución por método gráfico es la siguiente:
X2≥3
3X1+2X2≥18
Puede apreciarse que hay solución única: debe planificarse 4 anuncios en la TV y 3
anuncios en el P para lograr los aumentos mínimos propuestos, lo que representará un
gasto de $10,000 en publicidad.
Julio Rito Vargas Pág. 7
ACTIVIDAD PARA REAFIRMACIÓN EN EL AULA:
1. Un comerciante de frutas necesita 16 cajas de naranjas, 5 de bananos y 20 de manzanas.
Dos mayoristas pueden suministrarle para satisfacer sus necesidades, pero solo venden
la fruta en contenedores completos. El mayorista A envía en cada contender 8 cajas de
naranjas, 1 caja de bananos y 2 cajas manzanas. El mayorista B envía en cada contender
2 cajas de naranjas, 1 caja de bananos y 7 cajas manzanas. Se sabe que el mayorista A
se encuentra a 150 km de distancia y el mayorista B se encuentra a 300 km de distancia.
Calcular cuántos contenedores habrá de comprar a cada mayorista, con el objetivo de
ahorrar tiempo y dinero, reduciendo al mínimo lo solicitado.
2. Una compañía de auditores se especializa en preparar liquidaciones y auditorías de
empresas pequeñas. Tienen interés en saber cuántas auditorías y liquidaciones
pueden realizar mensualmente para maximizar sus ingresos. Se dispone de 800
horas de trabajo directo y 320 horas para revisión. Una auditoría en promedio
requiere de 40 horas de trabajo directo y 10 horas de revisión, además aporta un
ingreso de 300 dls. Una liquidación de impuesto requiere de 8 horas de trabajo
directo y de 5 horas de revisión, produce un ingreso de 100 dls. El máximo de
liquidaciones mensuales disponibles es de 60.
Julio Rito Vargas Pág. 8
ACTIVIDAD EXTRACLASE:
1. Una empresa vitivinícola ha adquirido recientemente un terreno de 110 hectáreas.
Debido a la calidad del sol y el excelente clima de la región, se puede vender toda la
producción de uvas Sauvignon Blanc y Chardonay. Se desea conocer cuánto plantar
de cada variedad en las 110 hectáreas, dado los costos, beneficios netos y
requerimientos de mano de obra según los datos que se muestran a continuación
Se posee un presupuesto de US$10.000 y una disponibilidad de 1.200 días hombre
durante el horizonte de planificación. Formule y resuelva gráficamente un modelo
de Programación Lineal para este problema. Detalle claramente el dominio de
soluciones factibles y el procedimiento utilizado para encontrar la solución óptima y
valor óptimo.
Julio Rito Vargas Pág. 9
