UNIDAD 3

Vista previa del material en texto

PROGRAMACIÓN LINEAL
1. ORIGEN DE LA PROGRAMACIÓN LINEAL(PL).-
En los siglos XVII y XVIII, grandes matemáticos como Newton, Leibnitz, Bernouilli y, sobre todo, Lagrange, que tanto habían contribuido al desarrollo del cálculo infinitesimal, se ocuparon de obtener máximos y mínimos condicionados de determinadas funciones. Posteriormente el matemático francés Jean Baptiste Joseph Fourier (1768-1830) fue el primero en intuir, aunque de forma imprecisa, los métodos de lo que actualmente llamamos programación lineal y la potencialidad que de ellos se deriva. Si exceptuamos al matemático Gaspar Monge (1746-1818), quien en 1776 se interesó por problemas de este género, debemos remontarnos al año 1939 para encontrar nuevos estudios relacionados con los métodos de la actual programación lineal. En este año, el matemático ruso Leonidas Vitalyevich Kantarovitch publica una extensa monografía titulada : Métodos matemáticos de organización y planificación de la producción en la que por primera vez se hace corresponder a una extensa gama de problemas una teoría matemática precisa y bien definida llamada, hoy en día, programación lineal . En 1941-1942 se formula por primera vez el problema de transporte, estudiado independientemente por Koopmans y Kantarovitch, razón por la cual se suele conocer con el nombre de problema de Koopmans-Kantarovitch. Tres años más tarde, G. Stigler plantea otro problema particular conocido con el nombre de régimen alimenticio óptimo. En estos años posteriores a la Segunda Guerra Mundial, en Estados Unidos se asumió que la eficaz coordinación de todas las energías y recursos de la nación era un problema de tal complejidad, que su resolución y simplificación pasaba necesariamente por los modelos de optimización que resuelve la programación lineal. Paralelamente a los hechos descritos se desarrollan las técnicas de computación y las computadoras, instrumentos que harían posible la resolución y simplificación de los problemas que se estaban gestando. En 1947, G.B. Dantzig formula, en términos matemáticos muy precisos, el enunciado estándar al que cabe reducir todo problema de programación lineal. Dantzig, junto con una serie de investigadores del United States Departament of Air Force, formarían el grupo que dio en denominarse SCOOP (Scientific Computation of Optimum Programs). Una de las primeras aplicaciones de los estudios del grupo SCOOP fue el puente aéreo de Berlín. Se continuó con infinidad de aplicaciones de tipo preferentemente militar. Hacia 1950 se constituyen, fundamentalmente en Estados Unidos, distintos grupos de estudio para ir desarrollando las diferentes ramificaciones de la programación lineal. Cabe citar, entre otros, Rand Corporation, con Dantzig, Orchard-Hays, Ford, Fulkerson y Gale, el departamento de Matemáticas de la Universidad de Princenton, con Tucker y Kuhn, así como la Escuela de Graduados de Administración Industrial, dependiente del Carnegie Institute of Technology , con Charnes y Cooper. Respecto al método del simplex, que estudiaremos después, señalaremos que su estudio comenzó en el año 1951 y fue desarrollado por Dantzig en el United States Bureau of Standards SEAC COMPUTER, ayudándose de varios modelos de computadora de la firma IBM. Los fundamentos matemáticos de la programación lineal se deben al matemático norteamericano de origen húngaro Janos von Neuman (1903-1957), quien en 1928 publicó su famoso trabajo Teoría de Juegos. En 1947 conjetura la equivalencia de los problemas de programación lineal y la teoría de matrices desarrollada en sus trabajos. La influencia de este respetado matemático, discípulo de David Hilbert en Gotinga y, desde 1930, catedrático de la Universidad de Princenton de Estados Unidos, hace que otros investigadores se interesaran paulatinamente por el desarrollo riguroso de esta disciplina. En 1858 se aplicaron los métodos de la programación lineal a un problema concreto: el cálculo del plan óptimo de transporte de arena de construcción a las  obras de edificación de la ciudad de Moscú. En este problema había 10 puntos de partida y 230 de llegada. El plan óptimo de transporte, calculado con la computadora Strena en 10 días del mes de junio, rebajó un 11% los gastos respecto a los costes previstos.
2. APLICACIÓN DE LA PROGRAMACIÓN LINEAL (PL)
 En infinidad de aplicaciones de la industria, la economía, la estrategia militar, etc.. se presentan situaciones en las que se exige maximizar o minimizar algunas funciones que se encuentran sujetas a determinadas limitaciones, que llamaremos restricciones.
2. APLICACIÓN DE LA PROGRAMACIÓN LINEAL (PL)
2.1. CONCEPTO
Un modelo de PL proporciona un método eficiente para determinar una decisión óptima, (o una estrategia óptima o un plan óptimo) escogida de un gran número de decisiones posibles. La decisión óptima es la que satisface un objetivo de administración, sujeto a varias restricciones. Por ejemplo, una decisión óptima podría ser la decisión que produzca la más alta ó máxima utilidad o el más bajo o mínimo costo.
 
Las características de los problemas propios de los negocios sujetos a solucionarse usando la PL, están bien definidas. Sin embargo, es impresionante el número y la diversidad de problemas que caen dentro de un sistema de PL.
2. APLICACIÓN DE LA PROGRAMACIÓN LINEAL (PL)
2.2. EJEMPLO 1. Problema de Maximización de Utilidades: “Decisiones en Producción”.
La Fábrica de Muebles Tiluchi (FMT) es especialista en la producción de dos clases de comedores muy de moda en Bolivia. Cada comedor requiere de una cantidad de tiempo diferente para la construcción y para la pintura. La FMT desea determinar el número de unidades de cada tipo de comedor a producir diariamente, de tal manera que las utilidades producidas sean máximas.
3. CONSTRUCCIÓN DE MODELOS DE PROGRAMACIÓN LINEAL (PL)
Los Requerimientos o pasos para construir un modelo de PL son:
1° Definir las VARIABLES DE DECISIÓN.
2° Definir la FUNCIÓN OBJETIVO. Debe haber un objetivo(o meta o blanco) que la firma desea alcanzar. Por ejemplo, maximizar las utilidades en dólares, minimizar el costo en dólares, maximizar el potencial de clientes esperados, minimizar el tiempo total, etc.
3° RESTRICCIONES Y DECISIONES. Debe haber cursos alternativos de acción o decisiones, uno de los cuales permite alcanzar el objetivo.
4° LINEALIDAD: FUNCIÓN OBJETIVO (ECUACIÓN) Y RESTRICCIONES (INECUACIONES) DEBEN SER DE 1° GRADO (VARIABLES DE EXPONENTE 1). Debemos estar en capacidad de expresar las decisiones del problema, incorporándolas a la función objetivo y a las restricciones sobre decisiones, usando solamente ecuaciones e inecuaciones lineales (1° Grado; variables de exponente 1). Es decir, debemos estar en capacidad de formular el problema como un modelo de Programación Lineal (PL).
3. CONSTRUCCIÓN DE MODELOS DE PROGRAMACIÓN LINEAL (PL)
3.1. FMT Fábrica de Muebles (TABLA 1)
“PARA DETERMINAR LA MEJOR U ÓPTIMA COMBINACIÓN DE COMEDORES S Y R QUE SE DEBE PRODUCIR DIARIAMENTE, LA FMT TIENE QUE ASIGNAR SUS CAPACIDADES LIMITADAS (RECURSOS ESCASOS) DE LOS DEPARTAMENTOS C Y P DEL MODO QUE PUEDA LOGRAR MEJOR SU OBJETIVO”.
EXPLICACIÓN: Considerando el problema de la FMT del ejemplo1 (2.2) para determinar cuántas unidades de cada comedor fabricar para vender. La FMT produce los tipos de comedor chiquitanos San José (S) y Roboré (R). La FMT logra una utilidad ( = precio neto de venta – costos variables de fabricación ) de         $ 200  y $ 240 de la venta de un comedor (S) y uno (R) , respectivamente. La FMT  ha experimentado una alta demanda de ambos comedores. En consecuencia, el gerente general cree que puede vender todos los comedores que produzca. Los comedores requieren tiempo de proceso en construcción (C) y de pintura (P).  Los requerimientos y capacidades de producción diarios están resumidos en la anterior tabla 1.
Observe que la FMT tiene una capacidad de producción limitada, es decir, los comedores S y R comparten los dos departamentos de producción, construcción (C)  y  pintura (P), cada uno de los cuales tienen capacidades diarias limitadas ypor tanto tienen que ser considerados como recursos escasos.
Cada Comedor tiene que ser procesado en los departamentos de construcción (C)  y pintura (P). Para producir un comedor (S) se requiere de 6 horas de C y 8 horas de P. Para producir un comedor (R)  se requiere de 12 horas de C y 4 horas de P.  Observe además que la FMT tiene una capacidad diaria de 120 horas de C y 64 horas de P. Entonces, para determinar la mejor u óptima combinación de comedores S y R que se debe producir diariamente, la FMT tiene que asignar sus capacidades limitadas (recursos escasos) de los departamentos C y P del modo que pueda lograr mejor su objetivo.
3. CONSTRUCCIÓN DE MODELOS DE PROGRAMACIÓN LINEAL (PL)
3.2. MODELO DE PL PARA LA FMT.
Paso1. DEFINIR LAS VARIABLES DE DECISIÓN (DE LA FMT). Estas son:
XS = Número de comedores San José a producir diariamente. = x
XR = Número de comedores Roboré a producir diariamente. = y
Paso 2. FUNCIÓN OBJETIVO. En segundo lugar, tenemos que definir el objetivo o meta de la FMT en términos de sus variables de decisión. Para hacer esto introducimos el concepto de función objetivo. Esta función muestra la relación existente entre la producción total XS y XR, y la utilidad. Sea Z o U= Utilidad. Entonces:
                      
                      
Por lo tanto,
Paso 3. DEFINIR LAS RESTRICCIONES O LIMITACIONES (DE CAPACIDAD) USANDO LAS VARIABLES DE DECISIÓN  (Xs y XR ).
El tiempo usado por día fabricando los dos productos no puede exceder del tiempo total disponible en el procesamiento en los departamentos C y P. Usando la TABLA 1 observamos que las horas requeridas para construir un comedor S (6 horas para un comedor S) veces el número de S comedores producidos, XS , más las horas requeridas para construir un comedor R (12 horas para un comedor R) veces el número de R comedores producidos, XR , tiene que ser menor o igual que el tiempo disponible en el Departamento de Proceso de Construcción (C). Tenemos:
4. SOLUCIONES A LOS MODELOS DE PROGRAMACIÓN LINEAL (PL)
Usualmente las “GRÁFICAS” no son el mejor método para resolver problemas de PL del mundo real, ya que no podemos dibujar en más de tres dimensiones. Sin embargo, una SOLUCIÓN GRÁFICA para un problema de tres ( o menos ) dimensiones es efectiva para entender mejor la ESTRUCTURA DE LOS MODELOS DE PL. Los gráficos sirven como tremenda ayuda para el entendimiento de la solución óptima de los modelos de PL. Se siguen los siguientes pasos:
4. SOLUCIONES A LOS MODELOS DE PROGRAMACIÓN LINEAL (PL)
4.1. PROCEDIMIENTO GRÁFICO – “MAXIMIZACIÓN”
PASO 1.- Representar gráficamente las restricciones del problema de PL.
PASO 2.- Ubicar todos los puntos de intersección de la Gráficas de las Restricciones.
PASO 3.-  Probar todos los puntos de intersección para observar cuál aporta el máximo beneficio aplicando la propiedad de Optimalidad de los modelos de PL que dice: “Una Solución de máxima utilidad o mínimo costo siempre ocurre en uno de los Vértices del Conjunto de Soluciones FACTIBLES ( intersección de la Gráficas de las Restricciones)”.
4. SOLUCIONES A LOS MODELOS DE PROGRAMACIÓN LINEAL (PL)
4.2. EJEMPLO 1 – PROBLEMA DE PRODUCCIÓN DE LA FMT
 
Para fabricar un comedor S o R completo, ambos centros de producción tienen que ser usados. Esto significa que la combinación óptima de comedores tiene que estar dentro del área sombreada, común a ambas figuras 1 y 2 o restricciones. Esto significa que necesitamos graficar las dos inecuaciones originales, sobre los mismos eje horizontal y vertical ya que deben formar un sistema.
Cualquier punto dentro o en la frontera del área sombreada llamada conjunto solución, no excede a cualquiera de las capacidades de los dos centros de producción o Departamentos. Es decir, el área sombreada, incluyendo su frontera, contiene todos los niveles de producción posibles x e y para comedores S y R que satisfacen cada una de las dos inecuaciones 1 y 2 del sistema.
5. PROBLEMA DE MINIMIZACIÓN
Muchos problemas propios de los negocios requieren la minimización en algunos objetivos en lugar de la maximización. El procedimiento gráfico para la minimización es el mismo de la maximización con una pequeña modificación en el Paso 3. El paso 3 para minimización sería: “Probar todos los vértices para analizar cuál aporta el mínimo costo total!!” 
5. PROBLEMA DE MINIMIZACIÓN
5.1. Ejemplo2: Almacenes Roboré y Compañía(Cía.).
≥≥
El departamento de publicidad de Almacenes Roboré y Cía. (ARC)  tiene que planear para el próximo mes una estrategia de publicidad para el lanzamiento de una línea de televisores a color. Tienen en consideración dos medios diferentes:
* Televisión (TV) →por ejemplo: Canal N°.... /Roboré=?
 *Periódico  (P)  → por ejemplo: Periódico “El Paquió”.......?
 Los estudios de Mercado han mostrado que:
(1) La publicidad por TV llega al 2% de las familias de INGRESOS ALTOS y al 3% de las familias de INGRESOS MEDIOS por comercial en Roboré.
 (2) La publicidad en el periódico llega al 3% de las familias de INGRESOS ALTOS y al 6% de las familias de INGRESOS MEDIOS por anuncio en Roboré.
La publicidad en el periódico tiene un costo de $ 500 por anuncio y la publicidad por TV tiene un costo de $ 2.000 por comercial. La meta de la ARC es obtener al menos una presentación como mínimo al 36% de las familias de ingresos altos y al 60% de las familias de ingresos medios minimizando los costos en publicidad.
PROBLEMA. Asumiendo que una persona que está considerando ambos medios, el anuncio y el comercial como una exposición doble( una exposición mayor que el 100% es posible), construir un modelo de programación lineal para la ARC.
SOLUCIÓN:
Paso 1.- Variables de decisión de la ARC. Sea
 x = Número de anuncios en el periódico.
 y = Número de anuncios comerciales en TV.
Paso 2.- Función objetivo de la ARC. Escoger x, y de tal manera que minimicen los costos totales en publicidad :
minimizar Z = $500 x + $2.000 y. 
Paso 3.- Las restricciones o las metas de la ARC.
(3%) x + (2%) y ≥  36% (Flías. de Ingresos Altos)
(6%) x +(3%) y ≥  60 % (Flías. de Ingresos Medios)
Paso 4.- Restricciones de “no negatividad”
x ≥ 0    ;  y ≥ 0
EL MODELO DE LA ARC
Escoger  x   e  y  de tal manera que minimicen
z = 500 x + 2000 y 
sujeto a las siguientes restricciones sobre x e y :
3 x +2 y  ≥  36
6 x +3 y  ≥  60 
x  ≥  0
y  ≥  0
Pregunta 1.- ¿Un Plan de Publicidad de x = 6 anuncios y  y=6 comerciales podrá satisfacer las metas de exposición de la ARC?
Si x = 6  , y = 6 , ⇒ Reemplazando en la meta (1): 3(6)+2(6) ≥ 36 ⇒ 18+12  ≥   36 ⇒ 30 ≥ 36 es FALSO!!
NO SATISFACE LA META (1)!!
Si x = 6  , y = 6 , ⇒ Reemplazando en la meta (2): 6(6)+3(6)  ≥  60 ⇒ 36+18 ≥  60 ⇒ 54 ≥  60 es FALSO!!
NO SATISFACE LA META (2)!!
Pregunta 2.- ¿Un Plan de Publicidad de x = 8 anuncios y  y = 6 comerciales podrá satisfacer las metas de exposición de la ARC?
Si x = 8  , y = 6 , ⇒ Reemplazando en la meta (1): 3(8)+2(6)36 ⇒ 24+1236 ⇒ 36 36 es VERDADERO!!
SATISFACE LA META (1)!!
Si x = 8  , y = 6 , ⇒ Reemplazando en la meta (2): 6(8)+3(6)60 ⇒ 48+18 60 ⇒ 66 60 es VERDADERO!!
 SATISFACE LA META (2)!!
Pregunta 3.- ¿Cuál es el Plan óptimo para la ARC?
	Vértice
(x ,y)
	Costo de publicidad
z = 500 x + 2.000 y
	A= (x,y) =(12,0)
B= (x,y) =(4,12)
C= (x,y) =(0,20)
	
z= 500 (12) +2000(0) =  $ 6.000
z= 500 (4) +2000(12) =  $ 26.000
z= 500 (0) +2000(20) =  $ 40.000
RESPUESTA.-  EL PLAN DE PUBLICIDAD ÓPTIMO (SOLUCIÓN ÓPTIMA) ES X=12 ANUNCIOS POR PERIÓDICO E y= 0 COMERCIALES POR TV. ESTE PLAN TIENE UN COSTO DE $ 6.000
Si x = 8  , y = 6 , ⇒ Reemplazando en la meta (1): 3(8)+2(6)36 ⇒ 24+1236 ⇒ 36 36 es VERDADERO!!
SATISFACE LA META (1)!!
Si x = 8  , y = 6 , ⇒ Reemplazando en la meta (2): 6(8)+3(6)60 ⇒ 48+18 60 ⇒ 66 60 es VERDADERO!!
 SATISFACE LA META (2)!!
Pregunta 3.- ¿Cuál es el Plan óptimo para la ARC?
	Vértice
(x ,y)
	Costo de publicidad
z = 500 x + 2.000 y
	A= (x,y) =(12,0)
B= (x,y) =(4,12)
C= (x,y) =(0,20)
	z= 500 (12) +2000(0) =  $ 6.000
z= 500 (4) +2000(12) =  $ 26.000
z= 500 (0) +2000(20) =  $ 40.000
RESPUESTA.-  EL PLAN DE PUBLICIDADÓPTIMO (SOLUCIÓN ÓPTIMA) ES X=12 ANUNCIOS POR PERIÓDICO Y Y=0 COMERCIALES POR TV. ESTE PLAN TIENE UN COSTO DE $ 6.000
5. PROBLEMA DE MINIMIZACIÓN
5.2. OTROS PROBLEMAS. EJEMPLO 3
EJEMPLO 3
Un expendio de carnes acostumbra preparar carne para hamburguesa con una combinación de carne molida de res y carne molida de cerdo. La carne de res contiene 80% y 20% de grasa y le cuesta a la tienda 80 centavos por libra. La carne de cerdo contiene 68% de carne y 32% de grasa y cuesta 68 centavo por libra. ¿Qué cantidad de cada tipo de carne debe emplear la tienda por cada libra de carne para hamburguesa si desea minimizar el costo y mantener el contenido de grasa no mayor de 25%?
SOLUCIÓN:
Variables de decisión. Sea
 x = Cantidad de Libras de carne de res.
 y = Cantidad de Libras de carne de cerdo.
Función objetivo. Escoger x, y de tal manera que minimicen el costo total:
minimizar Z = $ 80 x + $ 68 y. 
sujeto a las siguientes restricciones sobre x e y :
20 x +32 y ≤  25
x + y = 1
x  ≥  0
y  ≥ 0
RESOLVIENDO ANALÍTICAMEANTE LA INTERSECCIÓN DE LA INECUACIÓN CON LA RECTA DEL SISTEMA, SE TIENE:
x= 1 - y   → 20 (1-y)+ 32 y = 25
20 - 20 y +32 y = 25
12 y = 5
y = (5/12) ≈ 0,42
x = 1- (5 /12 )=  (7 /12)  ≈   0,58
Si x=( 7/12) , y= (5/12) → z = 80(7/12)+68(5/12) = (225/3) = 75 ctvs.
Respuesta.- ( 7 /12 ) Lbs. de carne de res(60%) y (5 /12)(40%) Lbs. de carne de cerdo.
 
EJEMPLO 4
En una granja se preparan dos clases de piensos (pienso= alimento seco que se dá al ganado), P y Q, mezclando dos productos A y B. Una bolsa de P contiene 8 kg de A y 2 de B, y una bolsa de Q contiene 10 kg de A y 5 de B. Cada bolsa de P se vende a $300 y cada bolsa de Q a $800. Si en la granja hay almacenados 80 kg de A y 25 de  B, ¿cuántas bolsas de cada tipo de pienso deben preparar para obtener los máximos ingresos?
 Solución: 
Si designamos por x al número de bolsas de pienso de clase P y por y el número de bolsas de pienso de clase Q que se han de vender, la función:
 z = 300 x + 800 y representará  la cantidad de pesos obtenidos por la venta de las bolsas,  y por tanto es la que debemos maximizar.
Podemos hacer un pequeño cuadro que nos ayuda a obtener las restricciones:
	Clase de pienso
	N° de bolsas de pienso
	Kg de producto A
	Kg de producto B
	Ingreso por bolsa($)
	P( 1 BOLSA)
	x
	8
	2
	300
	Q(1 BOLSA)
	y
	10
	5
	800
	TOTAL ALMACENADO DE CADA PRODUCTO
      (Kg)
	
	
80
	
25
	
 Por otra parte,  las variables x e y , lógicamente, han de ser no negativas, por tanto:
x  ≥ 0 , y  ≥ 0
Entonces tenemos un conjunto de restricciones expresada como:
8 x +10 y  ≤  80
2 x + 5y  ≤   25
x ≥  0 , y  ≥   0
	Vértice
(x ,y)
	UTILIDAD ( $)
z = 300 x + 800 y
	A= (x,y) =(0,0)
B= (x,y) =(10,0)
C= (x,y) =(7,5;2)
D= (x,y) =(0,5)
	z = 300 (0) +800(0) =  $ 0
z = 300 (10) +800(0) =  $ 3.000
z = 300 (7,5) +800(2) =  $ 3.850
z = 300 (0) +800(5) =  $ 4.000
RESPUESTA.-  PARA OBTENER EL MÁXIMO INGRESO SE DEBE PREPARAR 5 BOLSAS SÓLO DE PIENSO CLASE Q.
EJEMPLO 5
Una campaña para promocionar una marca de productos lácteos se basa en el reparto gratuito de yogures con sabor a limón o a frutilla. Se decide repartir al menos 30.000 yogures. Cada yogur de limón necesita para su elaboración 0,5 gramos de un producto de fermentación y cada yogur de frutilla necesita 0,2 gramos de este mismo producto. Se dispone de 9 kilogramos de este producto para fermentación. El coste de producción de un yogur de limón es de $30 y $20 uno de frutilla. ¿ Cuánto yogures de cada sabor se debe repartir para obtener el mínimo costo ?
Solución:
Sean:    x = Número de yogures de limón.
y = Número de yogures de frutilla.
La función costo es :
min z = 30 x + 20 y
sujeta a:
De número: x + y  ≤30.000
De fermentación: 0,5 x + 0,2 y   ≤  9.000
x  ≥  0
y   ≥ 0
La Solución óptima está en los vértices de la región factible (Polígono ABCD) :
	Vértice
(x ,y)
	Costo de publicidad
z = 30 x + 20 y
	A= (x,y) =(0,45.000)
B= (x,y) =(10.000,20.000)
D= (x,y) =(0,30.000)
	z= 30 (0) +20(45.000) =  $ 900.000
z= 30 (10.000) +20(20.000) =  $ 700.000
z= 30 (0) +20(30.000) =  $ 600.000
RESPUESTA.- Para obtener el mínimo costo se debe repartir sólamente 30.000 yogures de frutilla.