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 fucniones que se encuentran sujetas a determinadas limitaciones, que llamaremos restricciones.
Para hacernos una idea más clara de estos supuestos, veamos dos ejemplos:
Ejemplo 1: Problema de máximos.
En una granja se preparan dos clases de piensos, P y Q, mezclando dos productos A y B. Un saco de P contiene 8 kg de A y 2 de B, y un saco de Q contiene 10 kg de A y 5 de B. Cada saco de P se vende a 300 ptas. y cada saco de Q a 800 ptas. Si en la granja hay almacenados 80 kg de A y 25 de B, ¿cuántos sacos de cada tipo de pienso deben preparar para obtener los máximos ingresos?
Ejemplo 2: Problema de mÃÂÂÂnimos.
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 fresa. Se decide repartir al menos 30000 yogures.
Cada yogur de limón necesita para su elaboración 0.5 gramos de un producto de fermentación y cada yogur de fresa 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 pesetas y 20 pesetas uno de fresa.
En los dos ejemplos descritos está claro que tanto la cantidad que deseamos maximizar como la cantidad que deseamos minimizar podemos expresarlas en forma de ecuaciones lineales. Por otra parte, las restricciones que imponen las condiciones de ambos problemas se pueden expresar en forma de inecuaciones lineales.
Tratemos de plantear en términos matemáticos los dos ejemplos anteriores:
1) Si designamos por x al número de sacos de pienso de clase P y por y el número de sacos de pienso de clase Q que se han de vender, la función : Z = 300x + 800y representará la cantidad de pesetas obtenidas por la venta de los sacos, y por tanto es la que debemos maximizar.
Podemos hacer un pequeño cuadro que nos ayude a obtener las restricciones:
| |
Nº |
kg de A |
kg de B |
| P |
x |
8x |
2x |
| Q |
y |
10y |
5y |
| |
|
 80 |
25 |
Por otra parte, las variables x e y, lógicamente, han de ser no negativas, por tanto : x 
0, y 0
Conjunto de restricciones:
| 8x + 10y 80 |
| 2x + 5y 25 |
| x 0, y 0 |
2) Si representamos por x el número de yogures de limón e y al número de yogures de fresa, se tiene que la fución de coste es Z = 30x + 20y.
Por otra parte, las condiciones del problema imponen las siguientes restricciones:
- De número : x + y 80
- De fermentación: 0.5x + 0.2y 9000
- Las variables x e y han de ser, lógicamente, no negativas; es decir: x 0, y 0
Conjunto de restricciones:
| x + y 80 |
| 0.5x + 0.2y 9000 |
| x 0, y 0 |
En definitiva:
|
Se llama programación lineal al conjunto de técnicas matemáticas que pretenden resolver la situación siguiente:
Optimizar (maximizar o minimizar) una función objetivo, función lineal de varias variables, sujeta a:
una serie de restricciones, expresadas por inecuaciones lineales. |
Un problema de programación lineal en dos variables, tiene la siguiente formulación estándar:
puediendo cambiarse maximizar por minimizar, y el sentido de las desigualdades.
En un problema de programación lineal intervienen:
-
La función f(x,y) = ax + by + c llamada función objetivo y que es necesario optimizar. En esa expresión x e y son las variables de decisión, mientras que a, b y c son constantes.
-
Las restricciones que deben ser inecuaciones lineales. Su número depende del problema en cuestión. El carácter de desigualdad viene impuesto por las limitaciones, disponibilidades o necesidades, que son: inferiores a ... ( menores: < o ); como mÃÂÂÂnimo de ... (mayores: > o ) . Tanto si se trata de maximizar como de minimizar, las desigualdades pueden darse en cualquiera de los dos sentidos.
-
Al conjunto de valores de x e y que verifican todas y cada una de las restricciones se lo denomina conjunto (o región ) factible. Todo punto de ese conjunto puede ser solución del problema; todo punto no perteneciente a ese conjunto no puede ser solución. En el apartado siguiente veremos como se determina la región factible.
-
La solución óptima del problema será un par de valores (x0, y0) del conjunto factible que haga que f(x,y) tome el valor máximo o mÃÂÂÂnimo.
En ocasiones utilizaremos las siglas PPL para indicar problema de programación lineal.
METODO GRAFICO
| o Método de las rectas de nivel |
Las rectas de nivel dan los puntos del plano en los que la función objetivo toma el mismo valor.
Si la función objetivo es f(x,y) = ax + by + c, la ecuación de las rectas de nivel es de la forma:
ax + by + c = 0 
ax + by = k
Variando k (o p) se obtienen distintos niveles para esas rectas y, en consecuencia, distintos valores para f(x,y).
En un problema todas las rectas de nivel son paralelas, pues los coeficientes a y b de la recta ax + by = k son los que determinan su pendiente. Por tanto, si k1 es distinto de k2 , las rectas ax + by = k1 y ax + by = k2 son paralelas. Luego, trazada una cualquiera de esas rectas, las demás de obtienen por desplazamientos paralelos a ella.
Si lo que se pretende es resolver un problema de programación lineal, los únicos puntos que interesan son los de la región factible, y las únicas rectas de nivel que importan son aquellas que están en contacto con dicha región. Como el nivel aumenta (o disminuye) desplazando las rectas, el máximo (o el mÃÂÂÂnimo) de f(x,y) se alcanzará en el último (o en el primer) punto de contacto de esas rectas con la región factible.
Veamos ahora como se aplica todo esto a la resolución de un problema de programación lineal :
| Maximizar |
Z = f(x,y) = x + y |
| sujeto a: |
0 x 4 |
| |
0 y 4 |
| |
y x /2 |
1) Representamos la región factible:
- La recta s : x = 4 pasa por el punto (4,0) y es paralela al eje Y. Las soluciones de 0 x 4 son los puntos entre el eje Y y la recta x = 4
- La recta r : y = 4 pasa por el punto (0,4) y es paralela al eje X. Las soluciones de 0 y 4 son los puntos entre el eje X y la recta y = 4
- La recta t : y = x/2 pasa por los puntos (0,0) y (2,1) . Las soluciones de y x /2 son los puntos de su izquierda.
Resolviendo los sistemas correspondientes calculamos los vértices de la región factible:
{ y = x/2 , x = 0 } nos da el vértice O(0,0)
{ x = 4, y = x/2 } nos da el vértice A(4,2)
{ x = 4 , y = 4} nos da el vértice B(4,4)
{ y = 4 , x = 0 } nos da el vértice C(0,4)
2) Representamos las rectas de nivel :
En nuestro caso son rectas de la forma x + y = k . Inicialmente representamos Z = x + y = 0 . Trasladándola hacia la derecha, obtenemos las rectas : x + y = 2, x + y = 4, x + y = 8 , es decir aumenta el nivel.
3) Obtenemos la solución óptima:
Se obtiene en el punto de la región factible que hace máximo k. En nuestro caso esto ocurre en el punto B; es el último punto de contacto de esas rectas con la región factible , para el que k = 8.
| Si hay dos vértices, P y Q, que se encuentran en la misma recta de nivel ,de ecuación ax + by = k .Es evidente que todos los puntos del segmento PQ son de esa recta; por tanto, en todos ellos f(x,y) vale k. Asàpues, la solución óptima es cualquier punto de esa recta; en particular los vértices P y Q. |
ACTIVIDADES RESUELTAS
1) Se considera la región del plano determinada por las inecuaciones:x + 3 y ; 8 x + y ; y x - 3 ; x 0; y 0
a) Dibujar la región del plano que definen, y calcular sus vértices.
b) Hallar el punto de esa región en el que la función F(x,y) = 6x + 4y alcanza el valor máximo y calcular dicho valor.
a ) Hay que dibujar la región factible correspondiente. Para ello vamos a representar las rectas:
x - y = - 3 ; x + y = 8 ; x - y = 3
La región factible es la determinada por los vértices O, A, B, C y D.
Las coordenadas de los vértices son: A(3,0) ; B(5.5, 2.5) ; C(2.5, 5.5) ; D(0,3) y O(0,0)
b) Para determinar dónde la función objetivo F(x,y) = 6x + 4y alcanza su máximo, calculamos los valores que toma en los vértices:
F(A) = 18 ; F(B) = 43 ; F(C) = 37 ; F(D) = 12 ; F(O) = 0.
Luego la función alcanza su máximo en el vértice B y su valor es 43.
2)
Las restricciones pesqueras impuestas por la CEE obligan a cierta empresa a pescar como máximo 2.000 toneladas de merluza y 2.000 toneladas de rape, además, en total, las capturas de estas dos especies no pueden pasar de las 3.000 toneladas. Si el precio de la merluza es de 1.000 ptas/kg y el precio del rape es de 1.500 ptas/kg, ¿qué cantidades debe pescar para obtener el máximo beneficio?
Sean :
x = número de toneladas de merluza
y = número de toneladas de rape
Del enunciado deducimos las restricciones:
- Como máximo 2000 toneladas de merluza: x 2000
- Como máximo 2000 toneladas de rape: y 2000
- Las capturas de estas dos especies no pueden pasar de las 3000 toneladas: x + y 3000
La función objetivo que da el beneficio en miles de pesetas y que hay que maximizar viene dada por:
f(x,y) = 1000x + 1500y
Representando las rectas: x = 2000, y = 2000 , x + y = 3000 correspondientes a las fronteras de las restricciones obtenemos la región factible:
Donde los vértices obtenidos son:
A(2000,0) ; B(2000, 1000) ; C(1000, 2000) , D(0,2000) y O(0,0)
Al sustituir sus coordenadas en la función objetivo f resulta :
f(A) = 2000 millones de ptas. ; f(B) = 3500 millones de pesetas; f(C) = 4000 millones de pesetas ; f(D) = 3000 millones de pesetas y f(O)= 0 ptas.
La función objetivo alcanza su máximo en el vértice C, por lo que las cantidades a pescar son 1000 toneladas de merluza y 2000 toneladas de rape.
3) Dos pinturas A y B tienen ambas dos tipos de pigmentos p y q; A está compuesto de un 30% de p y un 40% de q, B está compuesto de un 50% de p y un 20% de q, siendo el resto incoloro. Se mezclan A y B con las siguientes restricciones:
La cantidad de A es mayor que la de B. Su diferencia no es menor que 10 gramos y no supera los 30 gramos. B no puede superar los 30 gramos ni ser inferior a 10 gramos.
- ¿Qué mezcla contiene la mayor cantidad del pigmento p?
- ¿Qué mezcla hace q mÃÂÂÂnimo?
Sean x e y, respectivamente, los gramos de las pinturas A y B que aparecen en la mezcla. Traduzcamos a inecuaciones las restricciones a las que se han de someter esas cantidades.
- La cantidad de A es mayor que la de B: x > y
- Su diferencia no es menor que 10 gramos y no supera los 30 gramos: 30 x - y 10
- B no puede superar los 30 gramos ni ser inferior a 10 gramos: 30 y 10
Además sabemos que : x 0 , y 0.
Veamos las cantidades de pigmento de cada tipo:
Cantidad de pigmento de tipo p: Fp (x, y) = 0.3x + 0.5y
Cantidad de pigmento de tipo q: Fq (x, y) = 0.4x + 0.2y
La región factible es la que aparece en la imagen del margen.
Sus vértices son A(20,10) , B(40,10), C(60,30) y D(40,30)
a) La mayor cantidad de pigmento p, se produce para 60 gramos de la pintura A y 30 de la B:
Fp (40,30) = 0.3·40 + 0.5·30 = 27 ; Fp (20,10) = 11 ; Fp (40, 10) = 17; Fp (60, 30) = 33
b) La menor cantidad de pigmento q, se produce para 20 gramos de la pintura A y 10 de la B:
Fq (40, 30) = 0.4·40 + 0.2·30 = 22; Fq (20, 10) = 10 ; Fq (40, 10) = 18 ; Fq (60, 30) = 30
METODO SIMPLEX
| Es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución.
Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polÃÂÂÂgono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución.
El método del simplex se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta. |
El método del simplex fue creado en 1947 por el matemático George Dantzig .
El método del simplex se utiliza, sobre todo, para resolver problemas de programación lineal en los que intervienen tres o más variables.
El álgebra matricial y el proceso de eliminación de Gauss-Jordan para resolver un sistema de ecuaciones lineales constituyen la base del método simplex. |
Vamos a resolver mediante el método del simplex el siguiente problema:
| Maximizar |
Z= f(x,y)= 3x + 2y |
| sujeto a: |
2x + y 18 |
| |
2x + 3y 42 |
| |
3x + y 24 |
| |
x0 , y 0 |
Se consideran las siguientes fases:
1. Convertir las desigualdades en igualdades
Se introduce una variable de holgura por cada una de las restricciones, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales:
| 2x + y + h = 18 |
| 2x + 3y + s = 42 |
| 3x +y + d = 24 |
2. Igualar la función objetivo a cero
- 3x - 2y + Z = 0
3. Escribir la tabla inicial simplex
En las columnas aparecerán todas las variables del problema y, en las filas, los coeficientes de las igualdades obtenidas, una fila para cada restricción y la última fila con los coeficientes de la función objetivo:
| Tabla I . Iteración nº 1 |
| Base |
Variable de decisión |
Variable de holgura |
Valores solución |
| |
x |
y |
h |
s |
d |
|
| h |
2 |
1 |
1 |
0 |
0 |
18 |
| s |
2 |
3 |
0 |
1 |
0 |
42 |
| d |
3 |
1 |
0 |
0 |
1 |
24 |
| Z |
-3 |
-2 |
0 |
0 |
0 |
0 |
4. Encontrar la variable de decisión que entra en la base y la variable de holgura que sale de la base
- Para escoger la variable de decisión que entra en la base, nos fijamos en la última fila, la de los coeficientes de la función objetivo y escogemos la variable con el coeficiente negativo mayor (en valor absoluto).
En nuestro caso, la variable x de coeficiente - 3.
Si existiesen dos o más coeficientes iguales que cumplan la condición anterior, entonces se elige uno cualquiera de ellos.
Si en la última fila no existiese ningún coeficiente negativo, significa que se ha alcanzado la solución óptima. Por tanto, lo que va a determinar el final del proceso de aplicación del método del simplex, es que en la última fila no haya elementos negativos.
La columna de la variable que entra en la base se llama columna pivote (En color verde).
- Para encontrar la variable de holgura que tiene que salir de la base, se divide cada término de la última columna (valores solución) por el término correspondiente de la columna pivote, siempre que estos últimos sean mayores que cero. En nuestro caso:
18/2 [=9] , 42/2 [=21] y 24/3 [=8]
Si hubiese algún elemento menor o igual que cero no se hace dicho cociente. En el caso de que todos los elementos fuesen menores o iguales a cero, entonces tendrÃÂÂÂamos una solución no acotada y no se puede seguir.
El término de la columna pivote que en la división anterior dé lugar al menor cociente positivo, el 3, ya 8 es el menor, indica la fila de la variable de holgura que sale de la base, d. Esta fila se llama fila pivote (En color verde).
Si al calcular los cocientes, dos o más son iguales, indica que cualquiera de las variables correspondientes pueden salir de la base.
- En la intersección de la fila pivote y columna pivote tenemos el elemento pivote operacional, 3.
5. Encontrar los coeficientes de la nueva tabla.
Los nuevos coeficientes de x se obtienen dividiendo todos los coeficientes de la fila d por el pivote operacional, 3, que es el que hay que convertir en 1.
A continuación mediante la reducción gaussiana hacemos ceros los restantes términos de su columna, con lo que obtenemos los nuevos coeficientes de las otras filas incluyendo los de la función objetivo Z.
También se puede hacer utilizando el siguiente esquema:
|
Fila del pivote:
Nueva fila del pivote= (Vieja fila del pivote) : (Pivote)
Resto de las filas:
Nueva fila= (Vieja fila) - (Coeficiente de la vieja fila en la columna de la variable entrante) X (Nueva fila del pivote)
Veámoslo con un ejemplo una vez calculada la fila del pivote (fila de x en la Tabla II):
| Vieja fila de s |
2 |
3 |
0 |
1 |
0 |
42 |
| |
- |
- |
- |
- |
- |
- |
| Coeficiente |
2 |
2 |
2 |
2 |
2 |
2 |
| |
x |
x |
x |
x |
x |
x |
| Nueva fila pivote |
1 |
1/3 |
0 |
0 |
1/3 |
8 |
| |
= |
= |
= |
= |
= |
= |
| Nueva fila de s |
0 |
7/3 |
0 |
1 |
-2/3 |
26 | |
| Tabla II . Iteración nº 2 |
| Base |
Variable de decisión |
Variable de holgura |
Valores solución |
| |
x |
y |
h |
s |
d |
|
| h |
0 |
1/3 |
1 |
0 |
-2/3 |
2 |
| s |
0 |
7/3 |
0 |
1 |
-2/3 |
26 |
| x |
1 |
1/3 |
0 |
0 |
1/3 |
8 |
| Z |
0 |
-1 |
0 |
0 |
1 |
24 |
Como en los elementos de la última fila hay uno negativo, -1, significa que no hemos llegado todavÃÂÂÂa a la solución óptima. Hay que repetir el proceso:
- La variable que entra en la base es y, por ser la variable que corresponde al coeficiente -1
- Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote:
2:1/3 [=6] , 26:7/3 [=78/7] y 8:1/3 [=8]
y como el menor cociente positivo es 6, tenemos que la variable de holgura que sale es h.
- El elemento pivote, que ahora hay que hacer 1, es 1/3.
Operando de forma análoga a la anterior obtenemos la tabla:
| Tabla III . Iteración nº 3 |
| Base |
Variable de decisión |
Variable de holgura |
Valores solución |
| |
x |
y |
h |
s |
d |
|
| y |
0 |
1 |
3 |
0 |
-2 |
6 |
| s |
0 |
0 |
-7 |
0 |
|
- TALLER DE PROGRAMACION LINEAL
EL SR CESAR ALVAREZ DECIDE COMPRAR LA FABRICA DE CONCENTRADOS PURINA. EN ESTA FABRICA SE PUEDEN PRODUCIR DOS PRODUCTOS (PRODUCTO 1: CONCENTRADO ADULTO Y PRODUCTO DOS: CONCENTRADO CACHORRO). EXISTE UNA MAQUINA QUE TIENE CAPACIDAD DE 1560 HORAS CON 600 EMPLEADOS QUE SE OCUPAN EN EL MONTAJE Y EMPAQUE. EL PRIMER PRODUCTO (CONCENTRADO ADULTO) NECESITA 2.6 HORAS DE MAQUINA Y 0.8 HORAS DE MONTAJE Y EMPAQUE, MIENTRAS QUE EL PRODUCTO DOS (CONCENTRADO CACHORRO)REQUIERE 2 HORAS DE MAQUINA Y UNA HORA DE MONTAJE Y EMPAQUE. CADA UNIDAD DEL PRODUCTO UNO CONTRIBUYE 2.8 (MILES DE PESOS) Y CADA UNIDAD DEL PRODUCTO DOS CONTRIBUYE 1(MILES). EL SR ALVAREZ QUIERE PRODUCIR PARA GANAR LO MAS POSIBLE Y QUIERE QUE USTED LO ASESORE Y LE DIGA CUANTO DEBE PRODUCIR DE CONCENTRADO PARA ADULTO Y DE CONCENTRADO PARA CACHORRO.
- REALICE LA SOLUCION GRAFICA
- METODO ALGEBRAICO
- METODO SIMPLEX
|
|
Sistemas fisicos y abstractos.
Fisicos: