PROGRAMACIÓN LINEAL
1. INTRODUCCIÓN
2. DEFINICIÓN DE PROGRAMACIÓN LINEAL
3. ETAPAS EN LA FORMULACIÓN DE UN PROGRAMA LINEAL
4. MÉTODOS DE RESOLUCIÓN
4.1. MÉTODO ANALÍTICO
4.2. MÉTODO GRÁFICO
1. INTRODUCCIÓN
A) Indica la región del plano que representa cada una de las siguientes inecuaciones:
A1) x>0
A2) x<0
A3) y>0
A4) y<0
B) Resuelve el siguiente sistema de inecuaciones:
LA SOLUCIÓN DE UN SISTEMA DE INECUACIONES SE LE LLAMA TAMBIÉN
REGIÓN FACTIBLE
C) Dibuja las regiones factibles de los siguientes sistemas:
SIN SOLUCIÓN
TIPOS DE SOLUCIONES O REGIONES FACTIBLES:
1) SOLUCIÓN ACOTADA: siempre será una región convexa, es decir para
dos puntos cualesquiera de dicha región, el segmento que los une
está contenido todo él en su interior.
CONVEXA NO CONVEXA CONVEXA NO CONVEXA
2) SOLUCIÓN NO ACOTADA
3) NO POSEE SOLUCIÓN
2. DEFINICIÓN DE PROGRAMACIÓN LINEAL
Es un conjunto de técnicas que pretende OPTIMIZAR (maximizar o minimizar)
una función lineal de dos variables llamada FUNCIÓN OBJETIVO sujeta a una
serie de restricciones expresadas por medio de inecuaciones lineales.
En cada programa lineal aparecen:
- dos variables
- restricciones (sistema de inecuaciones)
- función objetivo (función que hay que optimizar)
- región factible (solución del sistema de inecuaciones)
- solución óptima
3. ETAPAS EN LA FORMULACIÓN DE UN PROGRAMA LINEAL
1º RECOGER LA INFORMACIÓN
2º DETERMINAR LAS DOS VARIABLES
3º ESCRIBIR LAS RESTRICCIONES
4º EXPRESAR ANALÍTICAMENTE LA FUNCIÓN OBJETIVO
4. MÉTODOS DE RESOLUCIÓN
4.1. MÉTODO ANALÍTICO
Pasos a seguir:
1º Formular el problema
2º Dibujar la región factible y calcular los vértices de dicha región
resolviendo los sistemas de ecuaciones correspondientes.
3º Calcular el valor de la función objetivo en cada uno de los vértices
de la región factible y determinar el que la optimiza, que será la
solución.
4.2. MÉTODO GRÁFICO
Pasos a seguir:
1º Formular el problema
2º Dibujar la región factible y calcular los vértices de dicha región
resolviendo los sistemas de ecuaciones correspondientes.
3º Representar la función de beneficio nulo , f(x,y)=0
que será una recta que pasa por el origen de coordenadas.
4º Recorrer la región factible con las líneas de nivel, que son rectas
paralelas a la recta de beneficio nulo.
5º De todas estas líneas buscar la que da lugar al valor óptimo de
la función objetivo y pasará por un vértice de la región factible.
6º Discusión de la solución óptima pudiéndonos encontrar con uno
de los siguientes casos:
EJEMPLO
Una fábrica produce frigoríficos con un congelador o con dos congeladores. Los de un
congelador necesitan tres horas de montaje y tres horas de acabado y los de dos conge-
ladores necesitan tres horas de montaje y el doble de estas horas de acabado. El máximo
número de horas diarias que dispone la empresa es de 120 en montaje y 180 en acabado
debido a las limitaciones de los trabajadores.
El beneficio es de 300 euros por cada frigorífico con un congelador y 400 euros por cada
uno con dos congeladores. Plantea el programa lineal para que la empresa obtenga
máximo beneficio diario.
1º
Frigoríficos con un congelador: 3 horas de montaje y 3 horas de acabado.
Frigoríficos con dos congeladores: 3 horas de montaje y 6 horas de acabado.
Máximo número de horas de montaje: 120 h
Máximo número de horas de acabado: 180 h
Beneficios:
Frigorífico con un congelador: 300 €
Frigorífico con dos congeladores: 400 €
2º Variables:
x = número de frigoríficos con un congelador
y = número de frigoríficos con dos congeladores
3º RESTRICCIONES
4º FUNCIÓN OBJETIVO
Maximizar:
REGIÓN FACTIBLE
.
B .
C
A
. . D
A(0,0) B(0,30) C(4,28) D(40/3 , 0)
VALOR DE LA FUNCIÓN OBJETIVO EN LOS VÉRTICES
A(0,0) B(0,30) C(4,28) D(40/3 , 0)
Solución:
Se obtendrá el máximo beneficio con
4 frigoríficos de un congelador
28 frigoríficos de dos congeladores
MÉTODO GRÁFICO
.
B .
C
A
. .D
A(0,0) B(0,30) C(4,28) D(40/3 , 0)
Un tren de mercancías puede arrastrar, como máximo, 27 vagones. En cierto viaje
transporta coches y motocicletas. Para coches debe dedicar un mínimo de 12 vagones y
para motocicletas no menos de la mitad que dedica a los coches. Si los ingresos de la
compañía ferroviaria son de 540 € por vagón de coches y 360 € por vagón de
motocicletas, calcular cómo se deben distribuir los vagones para que el beneficio de un
transporte de coches y motocicletas sea máximo y cuánto vale dicho beneficio
Solución
x nº de vagones dedicados a coches
y nº de vagones dedicados a motocicletas
La función objetivo es f(x, y)= 540x +360y
Las restricciones vienen dadas por:
Los vértices que se obtienen en este caso son: A(12, 6), B(18, 9) y C(12, 15)
La región factible que resulta está coloreada en la figura:
También se ha dibujado la recta f(x, y)=0 (en
rojo) y se observa que el punto más alejado
(dentro de la región factible) es el B y sería por
tanto la solución gráfica del problema.
Lo comprobamos por el método analítico, es decir calculando los valores de la función
objetivo en los vértices.
f(A)= 540.12+360.6=8640
f(B)=540.18+360.9=12960 este es el beneficio máximo pedido
f(C)=540.12+360.15=11880
Luego 18 vagones para coches y 9 para motocicletas.
Un fabricante produce en dos talleres tres modelos distintos de archivadores, el A, el B y
el C. Se ha comprometido a entregar 12 archivadores del modelo A, 8 del B y 24 del C. Al
fabricante le cuesta 720 € al día el funcionamiento del primer taller y 960 € el del
segundo. El primer taller produce diariamente 4 archivadores del modelo A, 2 del B y 4 del
C, mientras que el segundo produce 2, 2 y 12 archivadores, respectivamente ¿Cuántos
días debe trabajar cada taller para, cumpliendo el contrato, conseguir reducir al máximo
los costes de funcionamiento?. ¿Cuál es el valor de dicho coste? ¿Quedaría algún
excedente de algún producto en los talleres? En caso afirmativo, determinar cuánto.
Solución
Llamamos x = nº de días que trabaja el primer taller
y al nº que trabaja el segundo taller
La función objetivo es C(x)= 720x+ 960y
Las restricciones
nº días A B C coste
Taller 1 x 4x 2x 4x 720x
Taller 2 y 2y 2y 12y 960y
12 8 24
Los vértices son (0, 6), (2, 2), (3, 1) y (6, 0)
Usando el método gráfico se comprueba que el
primer vértice que se encuentra es el (3,1) y
por tanto la solución del problema.
Lo vamos a comprobar usando el método analítico, es decir calculando el
valor de la función objetivo en cada uno de los vértices para ver en cuál se
obtiene el mínimo coste.
C(0, 6)=5760, C(2, 2)=3360, C(3, 1)=3120 y C(6, 0)=4320
Por tanto se tiene que trabajar 3 días en el primer taller y 1 día en el
segundo taller
El valor de dicho coste es 3120 euros y queda un excedente de 2
archivadores de tipo A.
