PROGRAMACION LINEAL: METODO SIMPLEX
Un modelo de Programación Lineal (PL) considera que las variables de decisión tienen un comportamiento lineal, tanto en la función objetivo como restricciones del problema. En este sentido, la Programación Lineal es una de las herramientas más utilizadas en la Investigación Operativa debido a que por su naturaleza se facilitan los cálculos y en general permite una buena aproximación de la realidad.
Los Modelos Matemáticos se dividen básicamente en Modelos Determistas (MD) o Modelos Estocásticos (ME). En el primer caso (MD) se considera que los parámetros asociados al modelo son conocidos con certeza absoluta, a diferencia de los Modelos Estocásticos, donde la totalidad o un subconjunto de los parámetros tienen una distribución de probabilidad asociada. Los cursos introductorios a la Investigación Operativa generalmente se enfocan sólo en Modelos Determistas.
METODO SIMPLEX
El método simplex está basado fundamentalmente en este concepto. Careciendo de la ventaja visual asociada con la representación gráfica del espacio de soluciones, el método simplex emplea un proceso iterativo que principia en un punto extremo factible, normalmente el origen, y se desplaza sistemáticamente de un punto extremo factible a otro, hasta que se llega por último al punto óptimo.
Existen reglas que rigen la selección del siguiente punto extremo del método simplex:
1. El siguiente punto extremo debe ser adyacente al actual.
2. La solución no puede regresar nunca a un punto extremo considerado con la anterioridad.
El algoritmo simplex da inicio en el origen, que suele llamarse solución inicial. Después se desplaza a un punto extremo adyacente. La elección específica de uno a otro punto depende de los coeficientes de la función objetivo hasta encontrar el punto óptimo.
Al aplicar la condición de optimidad a la tabla inicial seleccionamos a Xi como la variable que entra. En este punto la variable que sale debe ser una de las variables artificiales.
Los pasos del algoritmo simplex son:
1. Determinar una solución básica factible inicial.
2. Prueba de optimidad: determinar si la solución básica factible inicial es óptima y sólo si todos los coeficientes de la ecuación son no negativos ( >= 0 ). Si es así, el proceso termina; de otra manera se lleva a cabo otra interacción para obtener la nueva solución básica factible inicial.
3. Condición de factibilidad.- Para todos los problemas de maximización y minimización, variable que sale es la variable básica que tiene la razón más pequeña (positiva). Una coincidencia se anula arbitrariamente.
4. Seleccionar las variables de holgura como las variables básicas de inicio.
5. Selecciona una variable que entra de entre las variables no básicas actuales que, cuando se incrementan arriba de cero, pueden mejorar el valor de la función objetivo. Si no existe la solución básica es la óptima, si existe pasar al paso siguiente.
6. Realizar el paso iterativo.
a) Se determina la variable básica entrante mediante la elección de la variable con el coeficiente negativo que tiene el valor mayor valor absoluto en la ecuación. Se enmarca la columna correspondiente a este coeficiente y se le da el nombre de columna pivote.
b) Se determina la variable básica que sale; para esta, se toma cada coeficiente positivo (>0) de la columna enmarcada, se divide el lado derecho de cada renglón entre estos coeficientes, se identifica la ecuación con el menor cociente y se selecciona la variable básica para esta ecuación.
c) Se determina la nueva solución básica factible construyendo una nueva tabla en la forma apropiada de eliminación de Gauss, abajo de la que se tiene. Para cambiar el coeficiente de la nueva variable básica en el renglón pivote a 1, se divide todo el renglón entre el número pivote, entonces
renglón pivote nuevo = renglón pivote antiguo
número pivote
número pivote
para completar la primera iteración es necesario seguir usando la eliminación de Gauss para obtener coeficientes de 0 para la nueva variable básica Xj en los otros renglones, para realizar este cambio se utiliza la siguiente fórmula:
renglón nuevo = renglón antiguo - ( coeficiente de la columna pivote X renglón pivote nuevo)
cuando el coeficiente es negativo se utiliza la fórmula:
renglón nuevo = renglón antiguo + (coeficiente de la columna pivote X renglón pivote nuevo)
TEMATICA:
El método consiste en partir de un vértice del conjunto de soluciones, o solución inicial y determinar si es óptima. Si no lo es, se pasa a partir de él a otro vértice adyacente (es decir, que difiera del anterior en el hecho de que una coordenada no nula del primero se anule en el segundo y viceversa), por un criterio semejante al del gradiente, en el que mejore el valor de la función objetivo o función económica, repitiéndose esta operación hasta que no sea posible mejorar la función objetivo, en cuyo caso ya se ha alcanzado el óptimo.
El número de iteraciones es finito y, según los casos, se encuentra entre n y 2n.
Programación lineal con variables enteras y binarias
En muchos casos la naturaleza de las variables que constituyen un programa lineal y las unidades en que vienen medidas exigen que estas variables tomen valores enteros, ejemplo: Número de vehículos, personas, productos, máquinas, etc.
En tal caso una aproximación para resolver el problema consiste en tratarlo sin tener en cuenta el carácter entero de las variables. Si la solución obtenida por la aplicación del método SIMPLEX resultara entera habríamos terminado con el problema.
Si no es así, una alternativa es redondear la solución, comprobando que el punto así obtenido es realmente una solución, es decir, satisface al conjunto de restricciones, o bien tomar de cada variable su parte entera, realizando la misma comprobación.
Cuando los valores de la variable son de magnitud considerable, estas alternativas garantizan una excelente aproximación al punto óptimo. Cuando los valores de las variables son pequeños el redondeo puede estar lejos de la solución óptima, Así, que tenga cuidado.
Hay varios métodos para abordar la solución de un programa lineal con variables enteras. El mas conocido es el de “Formas enteras de Gomory o métodos de los hiperplanos de corte” que, básicamente, consiste en introducir restricciones adicionales que sólo pueden satisfacer las soluciones enteras y que reducen paulatinamente el conjunto inicial de soluciones. Su solución conduce a cálculos muy laboriosos, que ahora se resuelven en el computador.
Otra consideración que se debe tener en cuenta es que se pueden usar variables binarias, esto es, que sólo puede tomar valores de 0 y 1, en un modelo de programación lineal. Esto se usa generalmente en los problemas de asignación.
TABLA SIMPLEX
como se capturaría la solución básica factible inicial en el siguiente ejemplo:
sea:
Maximizar Z = 2X1+4X2
sujeto a:
sujeto a:
2X1+ X2<= 230
X1+ 2X2<= 250
X2<= 120
todas las X1,X2>=0
X1+ 2X2<= 250
X2<= 120
todas las X1,X2>=0
Seleccione la variable que entra y la variable que sale de la base:
Entra X2 y sale S3, se desarrolla la nueva tabla solución y se continua el proceso iterativo hasta encontrar la solución optima si es que está existe.
Tabla Optima:
Solución: Z = $500
fabricando
X1=10
X2=120
Sobrante de
S1 = 90
Tipo de solución: Optima Múltiple
fabricando
X1=10
X2=120
Sobrante de
S1 = 90
Tipo de solución: Optima Múltiple
SOLUCIONES DE MAXIMIZACION SIMPLEX
La mejor manera de aprender el método simplex es resolviendo problemas de programación lineal Para esto realicemos el siguiente ejercicio.
Una fábrica productora de embalajes plásticos, elabora dos tipos de containers de 3.750 c.c. y 4.000 c.c. Los datos de producción se presentan en la tabla adjunta. La persona encargada del termo-formado no puede trabajar más de 40 horas a la semana y los recursos económicos de la fábrica no permiten inversiones mayores de US$1.000 de materiales por semana ¿cuántos containers de cada tipo debería fabricar la industria, para obtener la utilidad máxima?
TIPO DE TRABAJO POR COSTO POR UTILIDAD POR CONTAINER ,CONTAINER, CONTAINER, CONTAINER
3750 (A) 6 HORAS $200 $240 4000 (B) 5 HORAS $100 $160
PASO 1: Establezca el modelo:
Cómo es posible que haya más de dos variables, es usual representarlas como X1 X2 X3, etc.
Variables independientes
X1: Cantidad de container tipo A
X2: Cantidad de container tipo B
Restricciones
C1: 6X1 + 5X2 Restricción de tiempo
C2: 200X1 + 100X2 Restricción de dinero
C3: X1
C4: X2
Función objetivo:
Z= 240X1 + 160X2 (Z es la utilidad)
PASO 2: Convierta las desigualdades de restricciones en ecuaciones
6X1+5X2=40
Observe que si el número total de horas es menor que 40, implica que algunas horas no se aprovecharon, esto significa que C1 se podría escribir como:
C1=6X1+5X2+S1=40
S1 corresponde a la cantidad de horas no utilizadas, S1
S1 se denomina variable de holgura, de holgura debido a que establece el período libre entre las horas empleadas (pueden ser menos de 40) y las horas disponibles (exactamente 40). El introducir la variable de holgura convierte las desigualdades de restricción en ecuaciones, lo que implica que se puedan utilizar matrices y el método de Gauss Jordán para resolver el problema.
C2:200X1 + 100X2
C2:200X1 + 100X2+S2
Nuevamente S2 es una variable de holgura que establece el dinero no utilizado, S2 . S2 determina la cantidad no empleada de dinero (menor a US$1.000) y el dinero disponible (igual a US$1.000)
Las restricciones C3:X1 y C4: X2 son condiciones de no negatividad.
PASO 3: Reescriba la función objetivo con todas las variables en el lado izquierdo
Z = 240X1 + 160X2
-240X1 - 160X2+ Z =0
Incluyendo las variables de holgura
-240X1–160X2+0S1+0S2+Z=0
C1:6X1+5X2+S1=40
C2:200X1+100X2+S2=1.000
Recuerde que S1= horas no utilizadas S2= dinero no utilizado
PASO 4: Plantee una matriz a partir de las restricciones y de la función objetivo reescritas.
C1 = 6X1 + 5X2 + S1 + 0S2 + 0Z =40
C2=200X1 + 100X2 + 0S1 + S2 + 0Z =1000
Función objetivo –240X1 - 160X2 + 0S1 + 0S2 + Z = 0
El método símplex requiere el examen de una serie de matrices. Recuerde que en el método gráfico se requería que examináramos una serie de puntos. En forma análoga el método símplex (cada matriz) nos proporciona un punto esquina de la región de soluciones factibles, sin necesidad de graficar la región.
Una última matriz símplex nos proporcionará el punto esquina óptimo (la solución al problema).
PASO 5: Determine la solución posible correspondiente a la matriz.
La solución factible se determina aplicando un método semejante al de Gauss-Jordan, utilizando como siempre un pivote (1) para obtener una matriz en la forma escalonada reducida por renglón.
El valor de la variable que encabeza cada una de las columnas se obtiene leyendo hacia abajo la columna, volteando en 1 y deteniéndose al final del renglón.
La matriz símplex inicial (1) no está en forma escalonada reducida por renglón . Las columnas S1 , S2 y Z si están en forma escalonada reducida, luego utilizando el esquema anterior.
F =
Observe que S1=40
S2=1000
Z=0
Y consideremos, inicialmente X1=0 X2=0
Luego una solución factible corresponde a la matriz
(X1 X2 S1 S2) = (0,0,40,1000) con Z=0
Lo anterior es una solución factible por que si X1 e X2=0 se satisfacen las cuatro restricciones.
Esta solución factible implica: que no se fabricaría el container tipo A y B, dispondríamos de 40 horas no trabajadas y US$1.000 no gastados, luego no habría utilidad.
Si este ejercicio se resolviera por método gráfico, (es pertinente que usted realice el ejercicio) el (0,0) corresponde a un punto de esquina. El método símplex localiza los demás puntos de esquina hasta que encontremos el óptimo.
El método de Gauss-Jordan y el método símplex
Cuando se soluciona un sistema por el método de Gauss-Jordan no proporciona ninguna solución hasta que se obtiene la matriz final de Gauss-Jordan.
El método símplex, por el contrario proporciona una serie de soluciones posibles, una por cada matriz.
Cada solución posible sería un punto esquina de la región de posibles soluciones. Si se estuviese manejando el método gráfico.
Ahora apliquemos el método símplex para solucionar el problema.
Variables independientes
X1= Cantidad de container
Tipo A
X2= Cantidad de container
Tipo B
Variables de holgura
S1= Horas no empleadas
S2= Dinero no utilizado
Restricciones:
C1:6X1+5X2+S1=40 Restricción de tiempo
C2:200X1+100X2+S2+1000 Restricción de dinero
Función objetivo
-240X1 - 160X2 + 0S1 + 0S2 + 1Z = 0
La primera matriz símplex es la siguiente
Una posible solución era (X1,X2,S1,S2) = (0,0,40,1000) Z=0 pero no es la solución máxima.
El procedimiento que usaremos es igual al método de Gauss-Jordan excepto por la ubicación del punto pivote.
PIVOTES POR EL MÉTODO SÍMPLEX
PASO 1: Ubique el último renglón en la matriz anterior,( es la función objetivo). Escoja la entrada más negativa en ese renglón. La columna que contiene esa entrada será la columna pivote.
Columna pivote
PASO 2: Divida la última entrada en cada renglón de restricción por la correspondiente entrada de la columna pivote. El renglón que de el menor cociente no negativo es el renglón pivote.
Columna pivote
PASO 3: Elija como pivote la entrada del renglón y la columna pivote
PIVOTE RENGLÓN PIVOTE
Columna Pivote
El valor de 200 es el pivote. Haremos las operaciones de renglón, en forma similar que lo haríamos por el método de Gauss-Jordan.
Cada matriz símplex, nos proporciona un punto esquina de la región de soluciones posibles; la matriz final símplex nos proporcionará el punto esquina óptimo.
La matriz anterior nos proporciona un punto de esquina, por que las columnas X1,S1 y Z sólo contienen unos y ceros.
Observe que X1=5 S1=10 Z=1.200 mientras que X2,S2 son cero (por qué?)
Por favor interprete esta solución:
La pregunta que podríamos formular es si éste punto esquina es el óptimo. Desafortunadamente la respuesta a la pregunta anterior se responde con otra pregunta ¿Es posible emplear pivotes nuevamente? Sí, si el último renglón contiene entradas negativas, en caso contrario no se requiere pivote y la solución posible que corresponde a la matriz es la máxima.
Columna Pivote
El menor cociente no negativo es 5, renglón 1
Ahora preguntémonos ¿Es posible emplear más pivotes? No, el último renglón contiene entradas no negativas. Esta es nuestra última matriz y la solución correspondiente a esta matriz es el punto esquina óptimo.
(X1,X2,S1,S2) = (2.5 , 5 , 0.0) con Z=1.400
APLICACIONES
1. Problema de la Dieta: Consiste en determinar una dieta de manera eficiente, a partir de un conjunto dado de alimentos, de modo de satisfacer requerimientos nutricionales. La cantidad de alimentos a considerar, sus características nutricionales y los costos de éstos, permiten obtener diferentes variantes de este tipo de modelos. Por ejemplo:
Leche (lt) | Legumbre (1 porción) | Naranjas (unidad) | Requerimientos Nutricionales | |
Niacina | 3,2 | 4,9 | 0,8 | 13 |
Tiamina | 1,12 | 1,3 | 0,19 | 15 |
Vitamina C | 32 | 0 | 93 | 45 |
Costo | 2 | 0,2 | 0,25 |
- Variables de Decisión:
- X1: Litros de Leche utilizados en la Dieta
- X2: Porciones de Legumbres utilizadas en la Dieta
- X3: Unidades de Naranjas utilizadas en la Dieta
Restricciones: Satisfacer los requerimientos nutricionales
- Niacina: 3,2X1 + 4,9X2 + 0,8X3 >= 13
- Tiamina: 1,12X1 + 1,3X2 + 0,19X3 >=15
- Vitamina C: 32X1 + 0X2 + 93X3 >= 45
- No Negatividad: X1>=0; X2>=0; X3>=0
EJERCICIOS
1. Disponemos de 210.000 euros para invertir en bolsa. Nos recomiendan dos tipos de acciones. Las del tipo A, que rinden el 10% y las del tipo B, que rinden el 8%. Decidimos invertir un máximo de 130.000 euros en las del tipo A y como mínimo 60.000 en las del tipo B. Además queremos que la inversión en las del tipo A sea menor que el doble de la inversión en B. ¿Cuál tiene que ser la distribución de la inversión para obtener el máximo interés anual?
Solución
Es un problema de programación lineal.
Llamamos x a la cantidad que invertimos en acciones de tipo A
Llamamos y a la cantidad que invertimos en acciones de tipo B
inversión | rendimiento | |
Tipo A | x | 0,1x |
Tipo B | y | 0,08y |
210000 0,1x+0,08y
Condiciones que deben cumplirse (restricciones):
R1 
R2 
R3 
R4 
Dibujamos las rectas auxiliares asociadas a las restricciones para conseguir la región factible (conjunto de puntos que cumplen esas condiciones)
r1 r2 (paralela a OY) r3(paralela a OX) r4
x | y | x | y | x | y | x | y | |||
0 | 210000 | 130000 | 0 | 0 | 60000 | 0 | 0 | |||
210000 | 0 | 130000 | 65000 |
La región factible es la pintada de amarillo, de vértices A, B, C, D y E
A(0, 60000), B(120000, 60000), C(130000, 65000), D(130000, 80000) y E(0, 210000)
La función objetivo es;
F(x, y)= 0,1x+0,08y
Si dibujamos la curva F(x, y) =0 (en rojo) y la desplazamos se puede comprobar gráficamente que el vértice mas alejado es el D, y por tanto es la solución óptima.
Comprobarlo analíticamente (es decir comprobar que el valor máximo de la función objetivo, F, se alcanza en el vértice D)
2. En una pastelería se hacen dos tipos de tartas: Vienesa y Real. Cada tarta Vienesa necesita un cuarto de relleno por cada Kg. de bizcocho y produce un beneficio de 250 Pts, mientras que una tarta Real necesita medio Kg. de relleno por cada Kg. de bizcocho y produce 400 Ptas. de beneficio. En la pastelería se pueden hacer diariamente hasta 150 Kg. de bizcocho y 50 Kg. de relleno, aunque por problemas de maquinaria no pueden hacer mas de 125 tartas de cada tipo. ¿Cuántas tartas Vienesas y cuantas Reales deben vender al día para que sea máximo el beneficio?
Solución
En primer lugar hacemos una tabla para organizar los datos:
Tipo | Nº | Bizcocho | Relleno | Beneficio |
T. Vienesa | x | 1.x | 0,250x | 250x |
T. Real | y | 1.y | 0,500y | 400y |
150 | 50 |
Función objetivo (hay que obtener su máximo): f(x, y)=250x+ 400y
Sujeta a las siguientes condiciones (restricciones del problema):
Consideramos las rectas auxiliares a las restricciones y dibujamos la región factible:
Para 0.25x+0.50y=50, ó x + 2y=200
x | Y |
0 | 100 |
200 | 0 |
Para x + y =150
x | Y |
0 | 150 |
150 | 0 |
La otras dos son paralelas a los ejes
Al eje OY x=125
Al eje Ox y =125
Y las otras restricciones (x e y mayor o igual a cero) nos indican que las soluciones deben estar en el primer cuadrante
La región factible la hemos coloreado de amarillo:
Encontremos los vértices:
El O(0,0), el A(125, 0) y el D(0, 100) se encuentran directamente (son las intersecciones con los ejes coordenados)
Se observa que la restricción y
es redundante (es decir “sobra”)
es redundante (es decir “sobra”)Resolviendo el sistema:
, por reducción obtenemos y=50, x=100Otro vértice es el punto C(100, 50)
Y el último vértice que nos falta se obtiene resolviendo el sistema:
X+y=150
X=125
Cuya solución es: X=125, Y=25 B(125, 25)
Los vértices de la región son O(0,0), A(125,0), B(125,25) y C(100,50) y D(0,100),
Si dibujamos el vector de dirección de la función objetivo f(x, y)=250x+ 400y
Haciendo 250x+ 400y =0, y=-(250/400)x=-125x/200
Haciendo 250x+ 400y =0, y=-(250/400)x=-125x/200
x | Y |
0 | 0 |
200 | -125 |
Se ve gráficamente que la solución es el punto (100, 50), ya que es el vértice mas alejado (el último que nos encontramos al desplazar la rectas 250x+400y=0 )
Lo comprobamos con el método analítico, es decir usando el teorema que dice que si existe solución única debe hallarse en uno de los vértices
La unción objetivo era: f(x, y)=250x+400y, sustituyendo en los vértices obtenemos
f(125,0)=31.250
f(125,25)=31.250+10.000=41.250
f(100,50)=25.000+20.000=45.000
f(0,100)=40.000
El máximo beneficio es 45.000 y se obtiene en el punto (100, 50)
Conclusión: se tienen que vender 100 tartas vienesas y 50 tartas reales.
3. Una escuela prepara una excursión para 400 alumnos. La empresa de transporte tiene 8 autocares de 40 plazas y 10 autocares de 50 plazas, pero solo dispone de 9 conductores. El alquiler de un autocar grande cuesta 80 euros y el de uno pequeño, 60 euros. Calcular cuantos de cada tipo hay que utilizar para que la excursión resulte lo mas económica posible para la escuela.
Solución
Es un problema de programación lineal, en este caso lo que queremos es hacer mínima la función objetivo.
Llamamos x al nº de autocares de 40 plazas e y al nº de autocares de 50 plazas que alquila la escuela.
Entonces se tiene x 
, y
, yComo sólo hay 9 conductores se verifica que: x +y 
Como tienen que caber 400 alumnos se debe de verificar:
40x +50y 
, que simplificada quedaría 4 x +5y 
, que simplificada quedaría 4 x +5y Por lo tanto las restricciones que nos van a permitir calcular la región factible (conjunto de puntos solución donde se cumplen todas las condiciones) son
La función objetivo es F(x, y)= 60x+ 80y
Dibujamos las rectas auxiliares,
r1 r2 r3 r4
x | y | x | y | x | y | x | y | |
8 | 0 | 0 | 10 | 0 | 9 | 0 | 8 | |
0 | 9 | 10 | 0 | |||||
Así como la de que corresponde a F(x, y)=0 que se dibuja en rojo.
Teniendo en cuenta las restricciones ( la de R4 es la parte de arriba y que la R3 es la parte de abajo), se encuentra la región factible. En el dibujo es la parte amarilla.
Los vértices son (0, 8), (0, 9) y el (5, 4), este último es el punto de intersección de las rectas r3 y r4
por reducción 
restando ambas ecuaciones se tiene x =5 y sustituyendo en la 1ª ecuación, y =4
Resolviendo gráficamente se llega a que el punto (5, 4) es la solución del problema. La solución óptima .
Comprobarlo sustituyendo en F(x, y) todos los vértices y que este es el que da menor valor (método analítico).
4. Una compañía posee dos minas: la mina A produce cada día 1 tonelada de hierro de alta calidad, 3 toneladas de calidad media y 5 de baja calidad. La mina B produce cada día 2 toneladas de cada una de las tres calidades. La compañía necesita al menos 80 toneladas de mineral de alta calidad, 160 toneladas de calidad media y 200 de baja calidad. Sabiendo que el coste diario de la operación es de 2000 euros en cada mina ¿cuántos días debe trabajar cada mina para que el coste sea mínimo?.
Solución
Organizamos los datos en una tabla:
días | Alta calidad | Calidad media | Baja calidad | Coste diario | |
Mina A | x | 1x | 3x | 5x | 2000x |
Mina B | y | 2y | 2y | 2y | 2000y |
80 | 160 | 200 |
La función objetivo C(x, y)=2000x + 2000y
Las restricciones son: 
La región factible la obtenemos dibujando las rectas auxiliares: r1 
x + 2y=80, r2 3x + 2y= 160 y r35x + 2y=200 en el primer cuadrante y considerando la región no acotada que determina el sistema de restricciones:
x + 2y=80, r2 3x + 2y= 160 y r35x + 2y=200 en el primer cuadrante y considerando la región no acotada que determina el sistema de restricciones: 
Los vértices son los puntos A(0, 100), B(20, 50), C(40, 20), D(80, 0), que se encuentran al resolver el sistema que determinan dos a dos las rectas auxiliares y (y que estén dentro de la región factible).
r1 
r2 
que nos da el punto (40, 20) (comprobarlo)
r2 que nos da el punto (40, 20) (comprobarlo)r2 r3 
que nos da el punto (20, 50)
r3 que nos da el punto (20, 50)r1 r3 no hace falta calcularlo pues queda fuera de la región factible.
r3 no hace falta calcularlo pues queda fuera de la región factible.En la gráfica se aprecia que el primer punto que se alcanza al desplazar la recta C(x, y)=0 es el (40, 20). Luego la solución es trabajar 40 días en la mina A y 20 en la B. (método gráfico)
Lo comprobamos aplicando el método analítico:
C(0, 100)=2000.100=200000
C(20, 50)=2000.20+2000.50=40000 + 100000= 140000
C(40, 20)= 2000. 40+2000.20=80000 + 40000= 120000 coste mínimo
C(80, 0)= 2000.80 =160000
5. Se va a organizar una planta de un taller de automóviles donde van a trabajar electricistas y mecánicos. Por necesidades de mercado, es necesario que haya mayor o igual número de mecánicos que de electricistas y que el número de mecánicos no supere al doble que el de electricistas. En total hay disponibles 30 electricistas y 20 mecánicos. El beneficio de la empresa por jornada es de 250 euros por electricista y 200 euros por mecánico. ¿Cuántos trabajadores de cada clase deben elegirse para obtener el máximo beneficio y cual es este?
Sea x = nº electricistas
y = nº mecánicos
La función objetivo
f (x, y)=250x+ 200y , las restricciones 
La región factible sería para estas restricciones:
Se aprecia gráficamente (línea en rojo) que la solución óptima está en el punto (20, 20).
Por tanto:
20 electricistas y 20 mecánicos dan el máximo beneficio, y este es 9000 euros, ya que f(x, y) =250.20+200.20=9000
6. Para recorrer un determinado trayecto, una compañía aérea desea ofertar, a lo sumo, 5000 plazas de dos tipos: T(turista) y P(primera). La ganancia correspondiente a cada plaza de tipo T es de 30 euros, mientras que la ganancia del tipo P es de 40 euros.
El número de plazas tipo T no puede exceder de 4500 y el del tipo P, debe ser, como máximo, la tercera parte de las del tipo T que se oferten.
Calcular cuántas tienen que ofertarse de cada clase para que las ganancias sean máximas.
Solución
Sea x el nº que se ofertan de tipo T, y el nº que se ofertan de tipo P.
nº | Ganancia | |
Turista | x | 30x |
Primera | y | 40y |
Total | 5000 | 30x +40y |
La función objetivo es:
f(x, y)=30x +40y
Las restricciones:
La región factible:
Los vértices, A(0, 5000), B(3750, 1250), C(4500, 500) y D(4500, 0) (comprueba el punto B resolviendo el sistema correspondiente)
El método gráfico nos da que el punto solución es el B (3750, 1250)
VIDEO DEL METODO SIMPLEX
