PROGRAMACIÓN LINEAL
INTRODUCCIÓN.
En los siglos XVII y XVIII, matemáticos como Newton, Leibnitz, Bernoulli y Lagrange, resuelven problemas que guardan alguna relación con la programación lineal, obtienen máximos y mínimos condicionados de ciertas funciones
El origen de la actual programación lineal lo podemos situar en los comienzos de la década de los 40, cuando aparecen los primeros trabajos sobre métodos matemáticos de organización y planificación de la producción.
A mediados de 1948, durante la guerra fría, la URSS bloqueó las comunicaciones desde las zonas alemanas en poder de los aliados hasta la ciudad de Berlín. Para romper dicho bloqueo los aliados utilizaron el suministro aéreo. En la planificación de estos suministros se utilizó la programación lineal
Planteamientos clásicos de programación lineal son
• El problema de la dieta: Se trata de determinar en qué cantidades hay que mezclar diferentes piensos para que un animal reciba la alimentación adecuada con un coste mínimo.
• El problema del transporte: Organizar el reparto de mercancías con un coste mínimo de tiempo, de dinero y de riesgo.
• Problemas de beneficios: Organizar ventas o inversiones con el fin de obtener máximos beneficios.
• Problema del viajante: Se trata de organizar las etapas de un viaje con el propósito de minimizar el recorrido
INECUACIONES
Inecuaciones lineales con una variable.
Una inecuación es una desigualdad entre dos expresiones algebraicas. Por ejemplo:
85 x
32
53 xx
Resolver una inecuación consiste en determinar los valores de la incógnita para los que se cumple la desigualdad.
Para resolverla, aislamos la incógnita en uno de los miembros de la inecuación, teniendo en cuenta las propiedades de las desigualdades
Ejemplo:
• Μultiplicamos por 4:
• Agrupamos términos
• Despejamos:
834
32
x
x
321232 xx
1035 x
2
7x
La representación gráfica de la solución sería_
2
7,
Inecuaciones lineales con dos variables.
Son desigualdades algebraicas que se pueden escribir de alguna de estas formas:
cbyax cbyax
cbyax cbyax
Las soluciones gráficas son:
Ejemplo 3 yx
Sistemas de inecuaciones lineales con dos incógnitas.
Estos sistemas están formados por dos o más inecuaciones de la forma:
cbyax
Para su resolución aplicamos el siguiente procedimiento:
• A cada una de las rectas frontera del semiplano solución le ponemos un nombre, r, s, t,.. tanto en la ecuación como en el dibujo, para que sepamos en cada momento a que recta nos estamos refiriendo.
• Resolvemos cada inecuación y las representamos en los mismos ejes coordenados.
• La solución es la zona del plano que verifica todas las inecuaciones del sistema.
Ejemplo: Calcula la solución del sistema de inecuaciones lineales con dos incógnitas:
1832
102
yx
yx
Resolvemos 102 yx
Resolvemos 1832 yx
La solución del sistema es la región coloreada
PROGRAMACIÓN
LINEAL
Definición y ejemplos
La programación lineal es un conjunto de técnicas matemáticas para la resolución de problemas de planificación económica o social. Generalmente se pretende optimizar una función (función objetivo) para obtener los máximos beneficios o los mínimos costes empleando unos recursos limitados, representados por unas restricciones en forma de inecuaciones lineales.
FUNCIÓN OBJETIVO
Se trata de la función que queremos
optimizar(Hallar su máximo o
su mínimo)
RESTRICCIONES
Expresadas en forma de
inecuaciones
SOLUCIÓN
Punto donde la función alcanza su valor máximo
o mínimo, cumpliendo las restricciones.
Ejemplo 1
Una fábrica de bombones tiene almacenados 500 Kg. de chocolate, 100 Kg. de almendras y 85 Kg. de frutas. Produce dos tipos de cajas, la de tipo A contiene 3 Kg de chocolate, 1 Kg. de almendras y 1 Kg. de frutas, la de tipo B contiene, 2 Kg. de chocolate, 1,5 Kg. de almendras y 1 Kg. de frutas. Los precios de las cajas de tipo A y B son 7 € y 8 €., respectivamente. ¿Cuántas cajas se deben fabricar de cada tipo para maximizar su venta?
Ejemplo 2
Un grupo local posee dos emisoras de radio, una de FM y otro de AM. La emisora de FM emite diariamente 12 horas de música rock, 6 de música clásica y 5 de información general. La emisora de AM emite diariamente, 5 horas de música rock, 8 de música clásica y 10 de información general. Cada día que emite la emisora de FM le cuesta al grupo 3000 €. y cada día que emite la de AM 2000 €. Sabiendo que tienen enlatadas 120 horas de música rock, 180 horas de música clásica y 100 de información general. ¿Cuántos días deberá emitir con ese material cada una de las dos emisoras para que el coste sea mínimo?
Planteamiento del problema
El primer paso es determinar la función objetivo que representaremos como:
yxyxf ),(
yxz
A continuación expresamos las restricciones en forma de desigualdad. En la mayoría de los casos es recomendable la construcción de una tabla de la siguiente forma:
o En la cabecera horizontal escribimos las etiquetas correspondientes a los conceptos variables y disponibles.
o En la siguiente fila escribimos la etiqueta variables y ponemos las dos variables:
o Las filas siguientes corresponden a las restricciones, casi siempre, cada fila da origen a una inecuación.
o En la última fila escribimos el concepto a optimizar, la función objetivo y si se trata de maximizar o minimizar.
La tabla correspondiente al Ejemplo 1 sería:
Tipo A Tipo B Disponibles
Variables x (cajas tipo A) y (cajas tipo B)
Chocolate 3x 2y 500
Almendras x 1,5y 100
Frutas x y 85
Ingresos 7x 8y Maxim.yxz 87
Las restricciones las obtenemos, casi directamente, de la segunda, tercera y cuarta fila:
85
1005,1
50023
yx
yx
yx
Además, en este caso es evidente que:
0 e 0 yx
La tabla correspondiente al Ejemplo 2 sería:
FM AM Disponibles
Variables x (días de FM) y (días de AM)
Rock 12x 5y 120
Clásica 6x 8y 180
Información 5x 10y 100
Costes 3000x 2000y Minim.310)23( yxz
Las restricciones en este caso serían:
100105
18086
120512
yx
yx
yx
Y como en el ejemplo anterior:
.
0 e 0 yx
Método analítico para el cálculo de soluciones
En primer lugar debemos resolver el sistema de inecuaciones surgido al expresar algebraicamente las restricciones del problema. La solución de este sistema nos proporciona una región del plano que llamaremos región factible, en la que se encuentra la solución del problema.
Ejemplo 1
Se puede demostrar que la función objetivo z, alcanza su valor máximo y mínimo en alguno de los vértices de la región factible. Por tanto, el siguiente paso será determinar los vértices de dicha región. Al sustituir las coordenadas de los vértices en la función objetivo, veremos para cuál o cuáles de ellos alcanza el valor óptimo.
Los vértices son:
1005,1
0:
yx
xR )
5,1100
,0(R
85
0:
yx
yS )0,85(S
1005,1
85:
yx
yxQ )30,55(Q
Sustituimos ahora las coordenadas de los vértices en la función z:
59508857)(
625308557)(
3,5335,1
100807)(
Sz
Qz
Rz
Como podemos ver el máximo beneficio se alcanza en el punto Q. Se deben fabricar 55 cajas del tipo A y 30 del tipo B.
Las restricciones en este caso serían:
100105
18086
120512
yx
yx
yx
Y como en el ejemplo anterior:
.
0 e 0 yx
Ejemplo 2
Los vértices son:
100105
0:
yx
xR )10,0(R
120512
0:
yx
yS )0,10(S
100105
120512:
yx
yxQ )
19120
,19140
(Q
Sustituimos ahora las coordenadas de los vértices en la función z:
3000002000103000)(
9,3473619120
200019140
3000)(
2000010200003000)(
Sz
Qz
Rz
Como podemos ver el máximo beneficio se alcanza en el punto R.
Método gráfico para el cálculo de soluciones
Seguimos el siguiente proceso:
• Se dibuja el recinto limitado por las restricciones del problema, es decir, la región factible.
• Dibujamos la recta 0byax
• Trazamos rectas paralelas a este vector que pasen por cada uno de los vértices del recinto:
• Observamos cuál de las rectas trazadas tiene mayor (o menor) ordenada en el origen. El vértice correspondiente a esa recta nos proporciona la solución del problema.
Si aplicamos este procedimiento al Ejemplo 1 tendremos como vector director )7,8(v
Solución en el vértice Q
Dada la función objetivo:
• Si b>0 : el máximo corresponde al vértice cuya recta de nivel tiene mayor ordenada en el origen, el mínimo al de menor ordenada en el origen.
• Si b<0 : el máximo corresponde al vértice cuya recta de nivel tiene menor ordenada en el origen, el mínimo al de mayor ordenada en el origen.
byaxz
El método gráfico nos permite ver fácilmente el número de soluciones que puede tener un problema de programación lineal. Supongamos que queremos maximizar la función z, siendo v=(-b,a) su vector director asociado, se pueden presentar los siguientes casos:
Planteamiento general. Tipos de soluciones
En todo problema de programación lineal se trata de optimizar (maximizar o minimizar) una función objetivo (z) de la forma:
nn xaxaxaz .......2211
Sujeta a unas restricciones representadas por un sistema de inecuaciones lineales
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
.....
.....
.....
2211
22222121
11212111
Cualquier conjunto de valores que satisfagan el sistema se llama solución factible. Una solución factible que haga máxima o mínima la función objetivo se llama solución óptima. El valor que toma z en la solución óptima es la solución del programa lineal.
Tipos de soluciones:
• Solución única: El sistema tiene una única solución. Ninguna de las rectas que representan las restricciones es paralela al vector director de la función objetivo.
• Solución múltiple: El problema tiene infinitas soluciones. En este caso el vector director de la función objetivo es paralelo a una de las restricciones.
• Solución no acotada: El problema carece de solución al no existir límite para el valor de la función objetivo debido a que la región factible no está acotada.
• Solución no factible: No tiene solución debido a que la región factible es vacía.
• Solución degenerada: Cuando representamos las restricciones, normalmente en un punto no coinciden más de dos rectas. Si en un punto coinciden más de dos rectas de las que constituyen los límites de la región factible, decimos que es un punto degenerado. Si la solución del programa lineal se encuentra en ese punto tenemos una solución degenerada