Método
Simplex
MÉTODO ALGEBRAICO
Clase 3
Ejercicio
Resolver mediante el método simplex el siguiente problema:
Función Objetivo: Max Z = 3x + 2y
Restricciones:
• 2x + y ≤ 18
• 2x + 3y ≤ 42
• 3x + y ≤ 24
• x ≥ 0, y ≥ 0
Convertir las desigualdades en igualdades:
Se introduce una variable de holgura (Si ) por cada una de las restricciones del tipo ≤, para
convertirlas en igualdades, resultando el sistema de ecuaciones lineales:
• 2x + y + S1 = 18
• 2x + 3y + S2 = 42
• 3x + y + S3 = 24
Igualar la función objetivo a cero
+ Z - 3x - 2y = 0
Escribir la tabla inicial Simplex
En las columnas aparecerán todas las variables básicas del problema y las variables de
holgura/exceso. En las filas se observan, para cada restricción
las variables de holgura con sus coeficientes, igualdades obtenidas, y la última fila con los valores
resultantes de sustituir el valor de cada variable en la función objetivo
Base Variables Variables de
Decisión Holgura R
Z x y S1 S2 S3
1 -3 -2 0 0 0 0
0 2 1 1 0 0 18
18/2 = 9
2. Fila Pivote
0 2 3 0 1 0 42 42/2 = 21
(el mejor de las 0 3 1 0 0 1 24 24/3 = 8
divisiones)
1. Columna Pivote
La mas negativa Convertir el elemento pivote en 1
Base Variables Variables de
Decisión Holgura R
Z x y S1 S2 S3
R1
1 -3 -2 0 0 0 0 +3R4 + R1
R2 0 2 1 1 0 0 18 -2R4 + R2
R3 0 2 3 0 1 0 42 -2R4 + R3
R4 0 1 1/3 0 0 1/3 8
Base Variables Variables de
Decisión Holgura R
Z x y S1 S2 S3
R1
1 0 -1 0 0 1 24
R2 0 0 1/3 1 0 -2/3 2 2/(1/3) = 6
R3 0 0 7/3 0 1 -2/3 26 26/(7/3) = 11.14
R4 0 1 1/3 0 0 1/3 8 8/(1/3) = 24
Base Variables Variables de
Decisión Holgura R
Z x y S1 S2 S3
R1 +R2 + R1
1 0 1 0 0 -1 24
R2 0 0 1/3 1 0 -2/3 2
R3 0 0 7/3 0 1 -2/3 26 -(7/3)R2 + R3
R4 0 1 1/3 0 0 1/3 8 -(1/3)R2 + R4
Base Variables Variables de
Decisión Holgura R
Z x y S1 S2 S3
R1
1 0 0 3 0 -1 30
R2 0 0 1 3 0 -2 6 Número negativo no
R3 0 0 0 -7 1 4 12 12/4 = 3
R4 0 1 0 -1 0 1 6 6/1 = 6
Base Variables Variables de
Decisión Holgura R
Z x y S1 S2 S3
R1 1 0 0 3 0 -1 30 +R3 + R1
R2 0 0 1 3 0 -2 6 +2R3 + R2
R3 0 0 0 -7 1 4 12
R4 0 1 0 -1 0 1 6 -R3 + R4
Base Variables Variables de
Decisión Holgura R
Z x y S1 S2 S3
1 0 0 5/4 ¼ 0 33
0 0 1 -1/2 ½ 0 12 Z = 33 unidades
0 0 0 -7/4 ¼ 1 3 x = 3 unidades
0 1 0 11/4 -¼ 0 3 y = 12 unidades
Ejemplo1
fuente: Modelos de investigación de operaciones para la optimización en la
toma de decisiones (2017) pag. 16. y Pag 22
•Paso 1: Definición del problema.
•Cierta Compañía utiliza dos distintas máquinas para fabricar
dos productos diferentes identificado como A y B. La
fabricación del producto A, requiere utilizar la máquina X media
hora y la máquina Y una hora. Mientras que el producto B,
utiliza cada máquina dos horas. Por especificaciones técnicas,
la máquina X no debe operar mas de 8 horas al día y la
maquina Y, no debe operar mas de 12 horas diarias. Las
ganancias unitarias de los productos A y B son Q20.00 y
Q50.00, respectivamente. La empresa puede vender todas la
unidades que pueda fabricar de los dos productos y su objetivo
es maximizar la ganancia diaria.
Ejemplo 1
fuente: Modelos de investigación de operaciones para la optimización en la toma de decisiones (2017) pag. 16. y Pag 22
Paso 1: Definición del problema.
Cierta Compañía utiliza dos distintas máquinas para fabricar dos productos diferentes identificado como A y B. La
fabricación del producto A, requiere utilizar la máquina X media hora y la máquina Y una hora. Mientras que el producto B,
utiliza cada máquina dos horas. Por especificaciones técnicas, la máquina X no debe operar mas de 8 horas al día y la
maquina Y, no debe operar mas de 12 horas diarias. Las ganancias unitarias de los productos A y B son Q20.00 y Q50.00,
respectivamente. La empresa puede vender todas la unidades que pueda fabricar de los dos productos y su objetivo es
maximizar la ganancia diaria.
Paso 3: Definición de Variables
x1: Cantidad unidades del producto A fabricados diariamente
x2: Cantidad unidades del producto B fabricados diariamente
Paso 4: Función Objetivo Paso 5: Restricciones
Max Z = 20x1 + 50x2
½ x1 + 2x2 ≤ 8
x1 + 2x2 ≤ 12
x1 ≥ 0 y x 2 ≥ 0
Base Variables Variables
Decisión de Holgura R
Z x1 x2 S1 S2
1 -20 -50 0 0 0
R1
0 1/2 2 1 0 8
R2
0 1 2 0 1 12
R3
Base Variables Variables
Decisión de Holgura R
Z x1 x2 S1 S2
1 -20 -50 0 0 0
R1 +5R2 + R1
0 1/4 1 1/2 0 4
R2
0 1 2 0 1 12
R3 -2R2 + R3
Base Variables Variables
Decisión de Holgura R
Z x1 x2 S1 S2
R1 1 -7.5 0 25 0 200
R2 0 ¼ 1 1/2 0 4
R3 0 ½ 0 -1 1 4
Base Variables Variables
Decisión de Holgura R
Z x1 x2 S1 S2
R1 +7.5R3 + R1
1 -7.5 0 25 0 200
R2 -1/4R3 + R2
0 ¼ 1 1/2 0 4
R3 0 1 0 -20 2 8
Base Variables Variables
Decisión de Holgura R
Z x1 x2 S1 S2
R1
1 0 0 10 15 260 Z = 260
R2 0 0 1 1 -1/2 2 x2 = 2
x1 = 2
R3 0 1 0 -2 2 8
Max Z = 20x1 + 50x2
½ x1 + 2x2 ≤ 8 La compañía debe fabricar diariamente 8 unidades
x1 + 2x2 ≤ 12 del producto A y 2 unidades del producto B para
x1 ≥ 0 y x 2 ≥ 0 maximizar su ganancia en Q260.00 al día.
Ejemplo 2
Un gran almacén encarga a un fabricante
pantalones y chaquetas deportivas. El fabricante
dispone para la confección de 750 m de tejido
de algodón y 1000 m de tejido de Poliéster. Cada
pantalón precisa 1 m de algodón y 2 m de
poliéster. Para cada chaqueta, se necesita 1.5 m
de algodón y 1m de Poliéster. El precio del
pantalón se fija en 50 € y el de la chaqueta en
40 €. ¿Qué número de pantalones y chaquetas
debe suministrar el fabricante al almacén para
que éste consiga una venta máxima?
Solución Ejemplo 2.
Definición de Variables
x1: Cantidad unidades de pantalones
Pantalones Chaquetas Disponibilidad x2: Cantidad unidades de chaquetas
Algodón 1 1.5 750 mts. Función Objetivo
Poliéste 2 1 1000 mts. Max Z = 50x1 + 40x2
r
Restricciones
Utilidad 50 40 ---------
x1 + 1.5x2 ≤ 750
2x1 + x2 ≤ 1000
x1 ≥ 0 y x 2 ≥ 0
Base Variables Variables
Decisión de Holgura R
Z x1 x2 S1 S2
R1
1 -50 -40 0 0 0
R2 0 1 1.5 1 0 750
R3 0 2 1 0 1 1000
Base Variables Variables
Decisión de Holgura R
Z x1 x2 S1 S2
R1 +50R3 + R1
1 -50 -40 0 0 0
R2 0 1 1.5 1 0 750 - R 3 + R2
R3 0 1 1/2 0 1/2 500
Base Variables Variables
Decisión de Holgura R
Z x1 x2 S1 S2
R1 1 0 -15 0 25 25000 +15R2 + R1
R2 0 0 1 1 -1/2 250
R3 0 1 ½ 0 ½ 500 -1/2 R2 + R3
Base Variables Variables
Decisión de Holgura R Conclusión: La
Z x1 x2 S1 S2 solución optima es
R1
1 0 0 15 17.5 28750 fabricar 375
R2 pantalones y 250
0 0 1 1 -1/2 250
chaquetas para
R3 0 1 0 -1/2 1/4 375 obtener un beneficio
de 28750 €
Solución PHP Simplex
Ejemplo 3
Paso 1: Definición del problema.
La compañía Sigma fabrica escritorios, sillas y mesas para los cuales ha
establecido que rinden una ganancia de $500, $600 y $300 por unidad
respectivamente. Para la producción de dichos artículos la compañía
cuenta con una disponibilidad semanal de 150 metros de madera, 120
metros de tubo y 200 horas hombre de trabajo. Se sabe que para producir
un escritorio se requiere de 5 metros de madera, 3 metros de tubo y 4
horas hombre; para producir una mesa se requieren 2 metros de madera,
3 metros de tubo y 1 hora hombre; para producir una silla se requiere 3
metros de madera, 4 metros de tubo y 5 horas hombre. Determine cual es
la adecuada producción que maximice las ganancias
Definición de Variables
x1: Cantidad de Escritorios
Producto Escritorio Sillas Mesas Disponibilidad x2: Cantidad de sillas
recursos x3: Cantidad de mesas
Recursos semana.
Madera 5 3 2 150 Función Objetivo
(metros) Max Z = 500x1 + 600x2 + 300x3
Tubos 3 4 3 120
(metros) Restricciones
5x1 + 3x2 + 2x3 ≤ 150
Horas- 4 5 1 200 3x1 + 4x2 + 3x3 ≤ 120
Hombre
4x1 + 5x2 + x3 ≤ 200
Utilidades $500 $600 $300 ---- x1 ≥ 0, x2 ≥ 0 y x3 ≥ 0
Solución PHP SIMPLEX
Ejemplo 4
Un paciente requiere una dieta estricta con
dos alimentos A y B. Cada unidad del
alimento A contiene 120 caloría y 2 gramos
de proteínas. La unidad del alimento B
contiene 100 calorías y 5 gramos de proteína.
La dieta requiere como mínimo 1000 calorías
y 30 gramos de proteínas. Si el precio de
cada unidad del alimento A es de Q60. y de
cada unidad del alimento B es de Q80.
¿Cuántas unidades de cada alimento debe
contener la dieta para que costo sea mínimo?
DUDAS:
• Clase sincrónica.
• Foro del Modulo 1.
• Correo electrónico:
[email protected] Esta foto de Autor desconocido está bajo licencia CC BY-NC-ND
Gracias.
Próxima clase: Método Dual
