Programacin lineal

La programacin lineal es un procedimiento o algoritmo matemtico

mediante el cual se resuelve un problema indeterminado, formulado a
travs de un sistema de inecuaciones lineales, optimizando la funcin
objetivo, tambin lineal.
Consiste en optimizar (minimizar o maximizar) una funcin lineal,
denominada funcin objetivo, de tal forma que las variables de dicha
funcin estn sujetas a una serie de restricciones que expresamos mediante
un sistema de inecuaciones lineales.
Historia de la programacin lineal[editar]
El problema de la resolucin de un sistema lineal de inecuaciones se
remonta, al menos, a Joseph Fourier, despus de quien nace el mtodo de
eliminacin de Fourier-Motzkin. La programacin lineal se plantea como
un modelo matemtico desarrollado durante la Segunda Guerra
Mundial para planificar los gastos y los retornos, a fin de reducir los costos
al ejrcito y aumentar las prdidas del enemigo. Se mantuvo en secreto
hasta 1947. En la posguerra, muchas industrias lo usaron en su
planificacin diaria.
Los fundadores de la tcnica son George Dantzig, quien public
el algoritmo simplex, en 1947, John von Neumann, que desarroll la teora
de la dualidad en el mismo ao, y Leonid Kantorvich, un matemtico
ruso, que utiliza tcnicas similares en la economa antes de Dantzig y gan
el premio Nobel en economa en 1975. En 1979, otro matemtico
Cronologa
1

Ao Acontecimiento
1826
Joseph Fourier anticipa la programacin lineal. Carl Friedrich Gauss
resuelve ecuaciones lineales por eliminacin "gaussiana".
1902
Gyula Farkas concibe un mtodo para resolver sistemas de
inecuaciones.
1947
George Dantzig publica el algoritmo simplex y
John von Neumann desarroll la teora de la dualidad.
Se sabe que Leonid Kantorvich tambin formul la teora en forma
independiente.
1984
Narendra Karmarkar introduce el mtodo del punto interior para
resolver
problemas de programacin lineal.
ruso, Leonid Khachiyan, dise el llamadoAlgoritmo del elipsoide, a travs
del cual demostr que el problema de la programacin lineal es resoluble
de manera eficiente, es decir, en tiempo polinomial.
2
Ms tarde, en
1984, Narendra Karmarkar introduce un nuevo mtodo del punto interior
para resolver problemas de programacin lineal, lo que constituira un
enorme avance en los principios tericos y prcticos en el rea.
El ejemplo original de Dantzig de la bsqueda de la mejor asignacin de 70
personas a 70 puestos de trabajo es un ejemplo de la utilidad de la
programacin lineal. La potencia de computacin necesaria para examinar
todas las permutaciones a fin de seleccionar la mejor asignacin es inmensa
(factorial de 70, 70!) ; el nmero de posibles configuraciones excede al
nmero de partculas en el universo. Sin embargo, toma slo un momento
encontrar la solucin ptima mediante el planteamiento del problema como
una programacin lineal y la aplicacin del algoritmo simplex. La teora de
la programacin lineal reduce drsticamente el nmero de posibles
soluciones factibles que deben ser revisadas.
Variables[editar]
Las variables son nmeros reales mayores o iguales a cero.
En caso que se requiera que el valor resultante de las variables sea un
nmero entero, el procedimiento de resolucin se denominaProgramacin
entera.
Restricciones[editar]
Las restricciones pueden ser de la forma:
Tipo 1:
Tipo 2:
Tipo 3:
Donde:
A = valor conocido a ser respetado estrictamente;
B = valor conocido que debe ser respetado o puede ser superado;
C = valor conocido que no debe ser superado;
j = nmero de la ecuacin, variable de 1 a M (nmero total de
restricciones);
a; b; y, c = coeficientes tcnicos conocidos;
X = Incgnitas, de 1 a N;
i = nmero de la incgnita, variable de 1 a N.
En general no hay restricciones en cuanto a los valores de N y M. Puede
ser N = M; N > M; , N < M.
Sin embargo si las restricciones del Tipo 1 son N, el problema puede ser
determinado, y puede no tener sentido una optimizacin.
Los tres tipos de restricciones pueden darse simultneamente en el mismo
problema.
Funcin Objetivo[editar]
La funcin objetivo puede ser:


o

Donde:
= coeficientes son relativamente iguales a cero.
Programacin entera[editar]
En algunos casos se requiere que la solucin ptima se componga de
valores enteros para algunas de las variables. La resolucin de este
problema se obtiene analizando las posibles alternativas de valores enteros
de esas variables en un entorno alrededor de la solucin obtenida
considerando las variables reales. Muchas veces la solucin del programa
lineal truncado esta lejos de ser el ptimo entero, por lo que se hace
necesario usar algn algoritmo para hallar esta solucin de forma exacta. El
ms famoso es el mtodo de 'Ramificar y Acotar' o Branch and Bound por
su nombre en ingls. El mtodo de Ramificar y Acotar parte de la adicin
de nuevas restricciones para cada variable de decisin (acortar) que al ser
evaluado independientemente (ramificar) lleva al ptimo entero.
Aplicaciones[editar]
La programacin lineal constituye un importante campo de la optimizacin
por varias razones, muchos problemas prcticos de la investigacin de
operaciones pueden plantearse como problemas de programacin lineal.
Algunos casos especiales de programacin lineal, tales como los problemas
de flujo de redes y problemas de flujo de mercancas se consideraron en el
desarrollo de las matemticas lo suficientemente importantes como para
generar por si mismos mucha investigacin sobre algoritmos especializados
en su solucin. Una serie de algoritmos diseados para resolver otros tipos
de problemas de optimizacin constituyen casos particulares de la ms
amplia tcnica de la programacin lineal. Histricamente, las ideas de
programacin lineal han inspirado muchos de los conceptos centrales de la
teora de optimizacin tales como la dualidad, la descomposicin y la
importancia de la convexidad y sus generalizaciones. Del mismo modo, la
programacin lineal es muy usada en la microeconoma y la administracin
de empresas, ya sea para aumentar al mximo los ingresos o reducir al
mnimo los costos de un sistema de produccin. Algunos ejemplos son la
mezcla de alimentos, la gestin de inventarios, la cartera y la gestin de las
finanzas, la asignacin de recursos humanos y recursos de mquinas, la
planificacin de campaas de publicidad, etc.
Otros son:
Optimizacin de la combinacin de cifras comerciales en una red lineal
de distribucin de agua.
Aprovechamiento ptimo de los recursos de una cuenca hidrogrfica,
para un ao con afluencias caracterizadas por corresponder a una
determinada frecuencia.
Soporte para toma de decisin en tiempo real, para operacin de un
sistema de obras hidrulicas;
Solucin de problemas de transporte.
Ejemplo[editar]


Este es un caso curioso, con solo 6 variables (un caso real deproblema de
transporte puede tener fcilmente ms de 1.000 variables) en el cual se
aprecia la utilidad de este procedimiento de clculo.
Existen tres minas de carbn cuya produccin diaria es:
La mina "a" produce 40 toneladas de carbn por da;
La mina "b" produce 40 t/da; y,
La mina "c" produce 20 t/da.
En la zona hay dos centrales termoelctricas que consumen:
La central "d" consume 40 t/da de carbn; y,
La central "e" consume 60 t/da
Los costos de mercado, de transporte por tonelada son:
De "a" a "d" = 2 monedas
De "a" a "e" = 11 monedas
De "b" a "d" = 12 monedas
De "b" a "e" = 24 monedas
De "c" a "d" = 13 monedas
De "c" a "e" = 18 monedas
Si se preguntase a los pobladores de la zona cmo organizar el transporte,
tal vez la mayora opinara que debe aprovecharse el precio ofrecido por el
transportista que va de "a" a "d", porque es ms conveniente que los
otros, debido a que es el de ms bajo precio.
En este caso, el costo total del transporte es:
Transporte de 40 t de "a" a "d" = 80 monedas
Transporte de 20 t de "c" a "e" = 360 monedas
Transporte de 40 t de "b" a "e" = 960 monedas
Total 1.400 monedas.
Sin embargo, formulando el problema para ser resuelto por la
programacin lineal se tienen las siguientes ecuaciones:
Restricciones de la produccin:






Restricciones del consumo:




La funcin objetivo ser:

La solucin de costo mnimo de transporte diario resulta ser:
X
b-d
= 40 resultando un costo de 12 x 40 = 480 monedas
X
a-e
= 40 resultando un costo de 11 x 40 = 440 monedas
X
c-e
= 20 resultando un costo de 18 x 20 = 360 monedas
Total 1.280 monedas.
120 monedas menos que antes.
Herramientas para la toma decisiones: La Programacin Lineal
Enviado por fmarrero





Indice

2. Desarrollo
3. Mtodos de solucin
4. Aspectos Fundamentales Del Mtodo Simplex
5. Bibliografa
6. Problemas
1. Introduccin
Mucha gente sita el desarrollo de la programacin lineal entre los avances
cientficos ms importantes de la mitad del siglo XX, y debemos estar de
acuerdo con esta afirmacin si tenemos en cuenta que su impacto desde
1950 ha sido extraordinario. Se han escrito decenas de libros de texto sobre
la materia y los artculos publicados que describen aplicaciones importantes
se cuentan ahora por cientos. De hecho, una proporcin importante de todo
el clculo cientfico que se lleva a cabo en computadoras se dedica al uso
de la programacin lineal y a tcnicas ntimamente relacionadas. (Esta
proporcin se estim en un 25%, en un estudio de la IBM).
Un modelo de programacin lineal proporciona un mtodo eficiente para
determinar una decisin ptima, (o una estrategia ptima o un plan ptimo)
escogida de un gran nmero de decisiones posibles.
En todos los problemas de Programacin Lineal, el objetivo es la
maximacin o minimizacin de alguna cantidad.
2. Desarrollo
Contruccin de los Modelos de Programacin Lineal
De forma obligatoria se deben cumplir los siguientes requerimientos para
construir un modelo de Programacin Lineal.
Requerimiento 1. Funcin objetivo. (F.O).
Debe haber un objetivo (o meta o blanco) que la optimizacin desea
alcanzar.
Requerimiento 2. Restricciones y decisiones.
Debe haber cursos o alternativas de accin o decisiones, uno de los cules
permite alcanzar el objetivo.
Requerimiento 3. La F.O y las restricciones son lineales.
Deben utilizarse solamente ecuaciones lineales o desigualdades lineales.
Modelo standard de Programacin Lineal
Optimizar Z = C1X1+ C1X2 +.+ Cn Xn). Funcin objetivo.
Sujeta a a11X1+ a11X2 +..+ a1nXn) b1
a21X1+ a21X2 +..+ a2nXn) b1
Restricciones
am1X1+ am1X2 +..+ amnXn) bm
Debiendo ser
X1 0, X2 0, .. Xn 0
Donde :
Xj : variables de decisin, j = 1,2.., n.
n : nmero de variables.
m : nmero de restricciones.
aij , bi , cj constantes, i = 1,2.., m.
Pasos para la construccin del modelo
1. Definir las variables de decisin.
2. Definir el objetivo o meta en trminos de las variables de decisin.
3. Definir las restricciones.
4. Restringir todas las variables para que sean no negativas.
Ejemplo: Taller de mantenimiento.
Un taller de mantenimiento fabrica dos tipos de piezas para la reparacin
de equipos fundamentales del proceso productivo. Estas piezas requieren
un cierto tiempo de trabajo en cada una de las tres mquinas que las
procesan. Este tiempo, as como la capacidad disponible (h) y la ganancia
por cada pieza se muestran en el cuadro siguiente:
Mquina Tiempo por Pieza Fondo de
A B Tiempo(h)
I 2 2 160
II 1 2 120
III 4 2 280
Ganancia ($/Pieza) 6 4

Se logra vender todo lo producido y se desea determinar la cantidad de
piezas a fabricar que optimice la ganancia.
Formulando el modelo
X1 : Nmero de piezas del tipo A.
X2 : Nmero de piezas del tipo B.
Optimizando la ganancia (Z).
Max Z = 6X1 + 4X2
Sujeto a las restricciones:
2X1 + 2X2 160 Fondo de tiempo de la mquina 1.
X1 + 2X2 120 Fondo de tiempo de la mquina 2.
4X1 + 2X2 280 Fondo de tiempo de la mquina 3.
Como ninguna variable implicada puede ser negativa.
X1 0; X2 0
3. Mtodos de solucin
El mtodo simplex es un procedimiento iterativo que permite tender
progresivamente hacia la solucin ptima. Es un procedimiento sistemtico
y eficiente para encontrar y probar soluciones situadas en los vrtices de
optimalidad.
El mtodo requiere que las restricciones sean ecuaciones en lugar de
inecuaciones, lo cual se logra aadiendo variables de holgura a cada
inecuacin del modelo, variables que nunca pueden ser negativas y tienen
coeficiente 0 en la funcin objetivo. Para el modelo formulado
anteriormente tenemos:
Z 6X1 4X2 = 0
2X1 + 2X2 + s1 = 160
X1 + 2X2 + s2 = 120
4X1 + 2X2 + s3 = 280
Todas las variables son no negativas.
La solucin bsica inicial se obtiene seleccionando las variables de holgura
como variables bsicas, resultando conveniente disponer los valores como
se muestran en la tabla siguiente:
i VB Z X1 X2 S1 S2 S3 Bi
1 Z 1 - 6 -4 0 0 0 0
2 S1 0 2 2 1 0 0 160
3 S2 0 1 2 0 1 0 120
4 S3 0 4 2 0 0 1 280
Cada ecuacin debe tener una nica variable bsica(VB), con el coeficiente
unidad en la fila correspondiente.
Esta solucin bsica debe ser examinada para observar si puede ser
mejorada. La presencia de coeficientes negativos en la FO indica que la
solucin bsica puede ser mejorada, pues el valor de Z se incrementar.
Cuando no hay coeficientes negativos, significa que la solucin es ptima.
Para encontrar una solucin mejorada es necesario:
Elegir la variable que entra como la de mayor coeficiente negativo (X1)
Elegir la variable que sale como aquella que al ser removida permita que la
variable que entra a la base pueda tener un valor tan grande como sea
posible, sin violar alguna de las restricciones en el modelo. En este caso la
variable S3 deja la base y a su vez X1 se introduce como la nueva variable
bsica.
El elemento pivote es el coeficiente que est en la interseccin de la
columna de la variable que entra y la fila de la variable que sale.
Los valores correspondientes a la nueva fila pivote se obtienen dividiendo
los coeficientes de la fila pivote en la tabla inicial por el elemento pivote.
Las otras filas de la solucin mejorada se calculan por la expresin:
Nueva fila = Fila anterior elemento de la columna pivote(nueva fila
pivote)
As, se obtiene la siguiente tabla:
i VB Z X1 X2 S1 S2 S3 Bi
0 Z 1 0 - 1 0 0 1.5 420
1 S1 0 0 1 1 0 -0.5 20
2 S2 0 0 1.5 0 1 - 0.25 50
3 X1 0 1 0.5 0 0 0.25 70
Como se puede apreciar esta no es an la solucin ptima Por qu?
Iterando nuevamente se obtiene la tabla correspondiente que se muestra a
continuacin:
i VB Z X1 X1 S1 S2 S3 Bi
0 Z 1 0 0 1 0 1 440
1 X2 0 0 1 1 0 - 0.5 20
2 S2 0 0 0 - 1.5 1 0.5 20
3 X1 0 1 0 - 0.5 0 0.5 60
Es esta la solucin ptima? Si lo es determine entonces los valores de las
variables para el ptimo.
Se ha aplicado el algoritmo para el caso del modelo estndard, cuando se
presentan problemas con restricciones o = y el criterio de optimizacin es
mnimo, entonces hay que introducir variables artificiales y se sugiere
convertir el problema en un problema de maximizar.
4. Aspectos Fundamentales Del Mtodo Simplex
1. Encuentra una solucin ptima
2. Es un mtodo de cambio de bases
3. Requiere que la funcin objetivo sea expresada de tal forma que cada
variable bsica tenga como coeficiente 0
4. Requiere que cada variable bsica aparezca en una y solamente una
ecuacin de restriccin.
Dualidad
Asociado a cada problema de Programacin Lineal existe un llamado dual,
de hecho al de Programacin Lineal se le llama primal. La forma general
del problema dual es la siguiente:
Optimizar Z = b1Y1+ b1Y2 +.+ bn Yn). Funcin objetivo.
Sujeta a a11Y1+ a11Y2 +..+ am1Y1) C1
a21Y1+ a22Y2 +..+ am2Y2) C1
. Restricciones
.
a1mY1+ a2mY2 +..+ amnYm) Cn
Para facilitar la comprensin de lo anterior considrese
el diagrama siguiente:
Primal Dual
C1. Cn (1)
a11 b1
(2) (3)
am1 bm
b1. bm (3)
(2) a11. am1 C1
(1)
C2
Variables
X1. Xn
Variables
Y1. Ym
El problema dual tiene las siguientes caractersticas:
El el objetivo de la optimizacin es contrario al del primal.
Las inecuaciones de restriccin son inversas.
La solucin del dual es la misma que la del primal.
Desde el punto de vista econmico, el significado de las variables duales es
de gran inters para los gerentes, ya que representan el valor por unidad de
recurso adicional, lo cul permite tomar decisiones sobre donde invertir
para incrementar las utilidades.
Anlisis de Sensibilidad
El objetivo del anlisis de sensibilidad es determinar la influencia de ciertos
valores en la solucin ptima, que nos permite la interpretacin razonable
de los resultados obtenidos. En muchos casos la informacin lograda por la
aplicacin del anlisis de sensibilidad puede ser ms importante y ms
informativa que simple resultado obtenido en la solucin ptima.
El anlisis deviene del resultado de los cambios en:
Los coeficientes en la funcin objetivo.
Los trminos independientes en las restricciones.
5. Bibliografa
1. Arbonas, M.E. Optimizacin Industrial (I): Distribucin de los recursos.
Coleccin Productica No. 26. Marcombo S.A, 1989.
2. Arbonas, M.E. Optimizacin Industrial (II): Programacin de recursos.
Coleccin Productica No. 29. Marcombo S.A, 1989.
3. Anderson, D.R., Sweeney.J. , Williams,T.A. , Introduccin a los
Modelos Cuantitativos para Administracin. Grupo Editorial
Iberoamrica. 1993.
4. Moskowitz,H. y Wright G.P. Investigacin de Operaciones.
Prentice_Hall Hispanoamericana S.A. 1991.
5. Trujillo,J;Batista,A: Mtodos Econmicos-Matemticos I.Editorial
ISPJAE, Habana,1986.
6. Taha,H: Investigacin de Operaciones.Alfaomega,Mxico,1995.
7. Buffa,E: Operations Management: Problems and
Models. Edicin Revolucionaria,La Habana, 1968.
6. Problemas
1- Una empresa se dedica a la produccin de pinturas para interiores y
exteriores para su distribucin al mayoreo. Se utilizan
dos materiales bsicos, A y B, para producir las pinturas. La disponibilidad
mxima de A es de 6 toneladas diarias; la de B es de 8 toneladas por da.
La necesidad diaria de materia prima por tonelada de pintura para interiores
y exteriores se resumen en la tabla que sigue:
Toneladas de MP por Disponibilidad
tonelada de pintura mxima en toneladas
Exterior Interior
Materia prima A 1 2 6
Materia prima B 2 1 8
El estudio de mercado ha establecido que la demanda diaria de pintura para
interiores no puede ser mayor que la pintura para exteriores en ms de una
tonelada. As mismo, el estudio seala que la demanda mxima de pintura
para interiores est limitada a dos toneladas diarias.
La ganancia por tonelada es de $3000 para la pintura de exteriores y $2000
para la pintura de interiores.
Cunta pintura para exteriores e interiores debe producir la empresa todos
los das para maximizar el ingreso bruto?
2- A una empresa se le ha planteado la tarea de cumplir un contrato de
explotacin de dos productos A y B para el prximo semestre. El contrato
estipula que deben ser entregados como mnimo 2000 unidades de ambos
productos, siendo al menos 800 de B. Los precios de venta son de 50 y 80
pesos por unidad para A y B respectivamente. La empresa cuenta con 3
establecimientos que pueden acometer esa tarea disponiendo los mismos de
550, 800 y 930 horas de tiempo productivo en el semestre respectivamente.
El tiempo de produccin que toma cada producto, en horas, para cada
establecimiento, as como el costo por hora de produccin de cada uno, se
dan en la tabla siguiente:
Productos
Establecimientos A B Costo/hora(pesos/h)
1 0,9 1,3 25
2 1,2 - 20
3 1,0 1,5 22
Para balancear el uso de la fuerza laboral, se desea por la empresa que el %
de capacidad productiva utilizada en los tres establecimientos sea la misma.
Por otra parte para el terminado de los productos se utiliza una materia
prima de importacin de las que disponen 3000 unidades, siendo la norma
unitaria de consumo de una unidad para A y 2 para B.
Plantee el modelo matemtico que permita conocer la forma ms
provechosa de cumplir el contrato.
3- Existen dos centrales cerca de la baha de Nipe: el Nicaragua y el Rafael
Freire, para los cuales se plantea revincular sus dos zonas caeras de modo
que se minimicen los costos de produccin de azcar (incluyendo los
costos de transportacin de caa).
El costo de produccin por arroba de azcar para cada caso se muestra a
continuacin:
Zona Nicaragua Rafael Freire
I 1,25 1,30
II 1,80 1,60
El central Nicaragua debe moler entre un mnimo de 20 millones de arrobas
de caa y un mximo de 30 millones de caa; y el Rafael Freire entre 15 y
25 millones de arrobas de caa.
Las zonas caeras a distribuir son dos: la Zona I con una produccin de
caa estimada en 20 millones de arrobas, y la zona II con 15 millones de
arrobas. No debe quedar caa sin cortar.
En la tabla siguiente se muestran los factores de conversin de arrobas de
caa necesarias para producir una arroba de azcar los cuales varan en
cada central y por zona caera:
Zona Nicaragua R. Freire
I 8,35 9,10
II 8,00 7,70
La meta de produccin para los dos centrales en conjunto es por lo menos
de 57500 arrobas de azcar. Todos los datos del problema corresponden a
una zafra.
4- Una empresa siderrgica produce tres tipos de rollos, cada uno hecho de
una diferente aleacin. El problema consiste en determinar las cantidades
de cada aleacin que debe producirse, dentro de las limitaciones de venta y
de las capacidades de las mquinas, para hacer mximas las ganancias. Los
datos sobre capacidades y otros elementos se presentan en las siguientes
tablas.
Operacin Mquinas Turnos de 8
h/Semana
Tiempo Ocioso en
%
Caja de Recocido 4 21 5
Recocido Continuo 1 20 10
Molinos Continuos 1 12 0
Aleacin Operacin Velocidad Potencial Ventas (T/mes) Ganancia
(T)
1 Caja de
Recocido
28 h/10 T 1250 25
Molinos
Continuos
15 m/min
Recocido
Continuo
6 m/min
Molinos
Continuos
8 m/min
2 Caja de
Recocido
35 h/10 T 250 35
Recocido
Continuo
11 m/min
Molinos
Continuos
6 m/min
3 Recocido
Continuo
5 m/min 1500 40
Molinos
Continuos
6 m/min
Los rollos de cada aleacin son de 122 m de largo y pesan 4 T.4- Una
empresa siderrgica produce 3 tipos de rollos, cada uno hecho de una
diferente aleacin.
5- Un barco tiene 3 bodegas: en la proa, en la popa y en el centro.
Los lmites de capacidad son:
Proa 2000t 100000 metros cbicos
Centro 3000t 135000 metros cbicos
Popa 1500t 30000 metros cbicos
Pueden ser transportadas las cantidades de mercancas que aparecen en la
siguiente tabla. Puede aceptarse el total o una porcin cualquiera de cada
artculo.
Volumen en Ganancia en
Artculo Cantidad en toneladas t/ metro cbico pesos/toneladas
A 6000 60 6
B 4000 50 8
C 2000 25 5
Para preservar el equilibrio del barco, el peso en cada bodega debe ser
proporcional a la capacidad en toneladas. Cmo debe distribuirse la carga
para hacer mxima la ganancia.
6- Una empresa tiene 2 talleres A y B. En ambos se producen los productos
tipo 1 y tipo2 en base a las materias primas M y N. La empresa dispone
diariamente de 10 t de M y 4t de N.
El consumo de M y N por cada producto en cada taller es el siguiente en
Kg:
Taller 1 Taller 2
M N M N
Producto 1 0,7 0,3 Producto 1 0,6 0,4
Producto 2 0,8 0,2 Producto 2 0,9 0,1
La capacidad de produccin del Taller 1 es de 4000 productos 1 o 6000
productos 2 o la combinacin de ambos. El taller 2 puede producir 5000
productos 1 o 7000 productos 2 o la combinacin de ambos.
Deben producirse al menos 4000 productos 1 y la cantidad de productos 2
que se produzcan en ambos talleres debe ser la misma.
El costo de produccin del producto 1 en el taller 1 es de $0,60 y del
producto 2, $0,80 El del taller 2 son un 20% mayores.
Si las capacidades de produccin deben aprovecharse como mnimo a un
90% y a un 85% en cada taller. Plantee el modelo matemtico que
minimice los costos de la empresa.
7- En el combinado del vidrio de la Lisa se producirn en el prximo
perodo 2 modelos de jarrones, uno de cenicero y 2 modelos de vasos de
cristal para el consumo nacional.
En la obtencin de estos productos se combinan dos materias primas (P y
Q), siendo el consumo en Kg para cada producto y el costo de produccin
los que se muestra en la tabla a continuacin:
Jarrones Cenicero Vasos de Cristal
1 2 1 2
P 0,03 0,63 0,07 - -
Q 0,09 0,11 0,05 0,01 0,04
Costo 2 3 1 0,5 1
($/u)
La materia prima Q es de importacin y solo se dispone de 820 Kg en el
perodo y de la materia prima P se recibirn 560 Kg. Todos los productos
pasan por tres procesos: horneado, acabado y envasado de la produccin.
En el Dpto de horneado pueden colocarse en un horno 200 jarrones o 350
ceniceros o 400 vasos o una combinacin factible( este Dpto cuenta con 4
hornos de este tipo en el perodo)
En el Dpto de acabado se le da un tratamiento especial a los modelos de
tipo 2 de jarrones y vasos de cristal, pudiendo atenderse 10 y 20 jarrones y
vasos por hora respectivamente.
En el Dpto de envasado se invierten 3, 2 y 3 minutos en el embalaje de los
jarrones, ceniceros y vasos respectivamente.
Se espera que para el perodo analizado se contar con un fondo de tiempo
de 280 horas para cada uno de estos Departamentos.
Por las caractersticas de la demanda se desea que la cantidad de vasos
producidos sea al menos el doble de la de jarrones y que por cada jarrn del
modelo tipo 1 se produzca un cenicero.
Plantee el modelo m+atemtico que permita obtener la planificacin ptima
de la produccin.
8- La empresa confitera Habana se dedica a la elaboracin de un amplio
surtido de caramelos y bombones, considerndose que existen
cuatro grupos fundamentales de estos productos, los cuales son:
Grupo Precio de venta($/Kg)
1 Caramelos especiales 1,37
2 Caramelos normales 1,23
3 Bombones surtido 5,00
4 Bombones especiales 6,00
La materia prima fundamental de los grupos 1 y2 es azcar refino,
colorante y saborizante y de los grupos 3 y 4, azcar refino, cocoa, altea y
licores.
Los caramelos pueden ser de tres sabores diferentes y los bombones
especiales pueden ser elaborados con dos tipos de licor.
En la tabla siguiente se muestra el insumo( Kg de mat prima/ Kg de
producto), disponibilidades y costo total.
M. PRIMA GRUPO DE PRODUCTOS DISPON(T) COSTO($)
1 2 3 4
azcar refino 0,7 0,6 0,5 0,35 60 18000
colorante 0,2 0,2 - - 2 800
saborizante 1 0,1 0,2 - - 5 500
saborizante 2 0,1 0,2 - - 5 600
saborizante 3 0,1 0,2 - - 4 400
cocoa - - 0,3 0,5 45 27000
altea - - 0,2 0,05 5 700
licores 1 - - - 0,1 4 1200
licores 2 - - - 0,1 3 900
En la produccin intervienen 2 grupos de obreros calificados cuyas
productividades son:
OBREROS PRODUCTIVIDAD(T/H) por SALARIO POR HORA
grupo de producto
1 2 3 4
Obrero A 0,04 0,04 0,05 0,04 0,90
Obrero B 0,015 0,03 0,02 0,04 0,80
Se dispone de 40 obreros de calificacin A y 60 de calificacin B, los
cuales laborarn 24 das al mes durante 8 horas cada da. No existen
restricciones en cuanto al fondo de tiempo productivo disponible de sus
mquinas. Plantee el modelo matemtico que maximice la ganancia.
Categora: Administracin y finanzas
Categora propuesta: Investigacin de Operaciones
Palabras claves
Programacin lineal, Investigacin de Operaciones, Optimizacin, Mtodo
Simplex


Programacin lineal

La programacin lineal estudia las situaciones en las
que se exige maximizar o minimizar funciones que se
encuentran sujetas a determinadas limitaciones, que
llamaremos restricciones.
Funcin objetivo
La programacin lineal consiste en optimizar
(maximizar o minimizar) una funcin objetivo, que es
una funcin lineal de varias variables:
f(x,y) = ax + by.
Restricciones
La funcin objetivo est sujeta a una serie
de restricciones, expresadas por inecuaciones lineales:

a
1
x + b
1
y c
1

a
2
x + b
2
y c
2

... ... ...
a
n
x + b
n
y c
n

Cada desigualdad del sistema de restricciones determina
un semiplano.

Solucin factible
El conjunto interseccin, de todos los semiplanos
formados por las restricciones, determina un recinto, acotado
o no, que recibe el nombre de regin de validez o zona
de soluciones factibles.

Solucin ptima
El conjunto de los vrtices del recinto se denomi na
conjunto de soluciones factibles bsicas y el vrtice donde
se presenta lasolucin ptima se llama solucin mxima (o
mnima segn el caso).

Valor del programa lineal
El valor que toma la funcin objetivo en el vrtice de
solucin ptima se llama valor del programa lineal .


Pasos para resolver un problema de programacin lineal
1. Elegir las incgnitas.
2. Escribir la funcin objetivo en funcin de los datos
del problema.
3. Escribir las restricciones en forma de sistema de
inecuaciones.
4. Averiguar el conjunto de soluciones
factibles representando grficamente las restricciones.
5. Calcular las coordenadas de los vrtices del recinto
de soluciones factibles (si son pocos).
6. Calcular el valor de la funcin objetivo en cada uno
de los vrtices para ver en cul de ellos presenta el valor
mximo o mnimo segn nos pida el problema (hay que
tener en cuenta aqu la posible no existencia de solucin si el
recinto no est acotado).


Ejemplo de programacin lineal
Unos grandes almacenes encargan a un fabricante
pantalones y chaquetas deportivas.
El fabricante dispone para la confeccin de 750 m de
tejido de algodn y 1000 m de tejido de polister. Cada
pantaln precisa 1 m de algodn y 2 m de polister. Para
cada chaqueta se necesitan 1.5 m de algodn y 1 m de
polister.
El precio del pantaln se fija en 50 y el de la chaqueta
en 40 .
Qu nmero de pantalones y chaquetas debe
suministrar el fabricante a los almacenes para que stos
consigan una venta mxima?
1Eleccin de las incgnitas.
x = nmero de pantalones
y = nmero de chaquetas
2Funcin objetivo
f(x,y)= 50x + 40y
3Restricciones
Para escribir las restricciones vamos a ayudarnos de una
tabla:

pantalones chaquetas disponible
algodn 1 1,5 750
polister 2 1 1000
x + 1.5y 750 2x+3y1500
2x + y 1000
Como el nmero de pantalones y chaquetas son nmeros
naturales, tendremos dos restricciones ms:
x 0
y 0
4 Hallar el conjunto de soluciones factibles
Tenemos que representar grficamente las restricciones.
Al ser x 0 e y 0, trabajaremos en el primer
cuadrante.
Representamos las rectas, a partir de sus puntos de corte
con los ejes.

Resolvemos grficamente la inecuacin: 2x +3y 1500,
para ello tomamos un punto del plano, por ejemplo el (0,0).
20 + 30 1 500
Como 0 1 500 entonces el punto (0,0) se encuentra en
el semiplano donde se cumple la desigualdad.
De modo anlogo resolvemos 2x + y 1000.
20 + 0 1 00
La zona de interseccin de las soluciones de las
inecuaciones sera la solucin al sistema de inecuaciones,
que constituye el conjunto de las soluciones factibles.

5 Calcular las coordenadas de los vrtices del recinto de
las soluciones factibles.
La solucin ptima, si es nica, se encuentra en un
vrtice del recinto. stos son las soluciones a los sistemas:
2x + 3y = 1500; x = 0 (0, 500)
2x + y = 1000; y = 0 (500, 0)
2x + 3y =1500; 2x + y = 1000 (375, 250)

6 Calcular el valor de la funcin objetivo
En la funcin objetivo sustituimos cada uno de los
vrtices.
f(x, y) = 50x + 40y
f(0, 500) = 50 0 + 40 500 = 20000
f(500, 0) = 50500 + 400 = 25000
f(375, 250) = 50375 + 40250 = 28750 Mximo
La solucin ptima es fabricar 375 pantalones y 250
chaquetas para obtener un beneficio de 28750 .