Actividad de aprendizaje eje 2
Gerencia De Proyectos De Ingeniería
Alumnos
Cristian Bustos Ramos
Juan Rodriguez Tapiero
Daniel Fandino Martines
Profesor
Omar Antonio Bustos Amaya
Fundación Universitaria Del Área Andina Virtual
Facultad De Ingenierías Y Ciencias Básicas,
Programa de Ingeniería de Sistemas
Octubre de 2024
1. INTRODUCCIÓN.
Abordar la resolución del problema de programación lineal utilizando dos métodos: el
método de la gran M y el método de dos fases.
El propósito de este taller es explorar y aplicar estos dos métodos y analizar el proceso de
solución, y comparar los resultados obtenidos con cada enfoque.
2. OBJETIVO
Aplicar los métodos de la gran M y de las dos fases para encontrar la solución óptima de un
problema de programación lineal.
Objetivos Específicos
● Desarrollar un modelo matemático que represente el problema.
● Resolver el problema mediante ambos métodos de optimización.
● Comparar los resultados obtenidos y discutir las diferencias en el proceso de solución.
3. Descripción del problema.
Se nos plantea un problema de programación lineal con el objetivo de maximizar la
función objetivo:
Maximizar
Z = 6x1 + 8x2 + 4x3
Sujeto a:
x1 + 4x2 + 2x3 ≥ 25
3x1 + 2x2 + x3 ≤ 30
x1 + x2 + 5x3 = 18
x1 ≥ 0; x2 ≥ 0; x3 ≥0
Este problema será resuelto mediante el método de la gran M y el método de dos fases.
Desarrollo Juan Pablo Rodriguez
Desarrollo del ejercicio por el método de la gran M .
𝑧 = 6𝑥1 + 8𝑥2 + 4𝑥3
𝑥1 + 4𝑥2 + 2𝑥3≥25
3𝑥1 + 2𝑥2 + 𝑥3≤30
𝑥1 + 𝑥2 + 5𝑥3 = 18
𝑥1≥0; 𝑥2 ;≥0𝑥3; ≥0
Primera restricción 𝑥1 + 4𝑥2 + 2𝑥3≥25
Res: 𝑥1 + 4𝑥2 + 2𝑥3 − 𝑆1 + 𝐴1 = 25
Segunda restricción 3𝑥1 + 2𝑥2 + 𝑥3≤30
Res: 3𝑥1 + 2𝑥2 + 𝑥3 + 𝑠2 = 30
Tercera restricción 𝑥1 + 𝑥2 + 5𝑥3 = 18
Res: 𝑥1 + 𝑥2 + 5𝑥3 + 𝐴3 = 18
𝑍 = 6𝑥1 + 8𝑥2 + 4𝑥3 − 𝑀 • 𝐴1 − 𝑀𝐴2
Construcción de la tabla
Variables Básicas 𝑥1 𝑥2 𝑥3 𝑠1 𝑠2 𝐴1 𝐴2 RHS
𝐴1 1 4 2 -1 0 1 0 25
𝑠2 3 2 1 0 1 0 -1 30
𝐴3 1 1 5 0 0 0 0 18
𝑍 -6 -8 -4 0 0 -M -M 0
4. Desarrollo del ejercicio por el método de las dos fases.
𝑅 = 𝐴1 + 𝐴3
Variables Básicas 𝑥1 𝑥2 𝑥3 𝑠1 𝑠2 𝐴1 𝐴3 RHS
𝐴2 1 4 2 -1 0 1 0 25
𝑆2 3 2 -1 0 1 0 0 30
𝐴3 1 1 5 0 0 0 1 18
𝑍 -1 -5 -7 0 0 -1 -1 0
𝑍 = 6𝑥1 + 8𝑥2 + 4𝑥3
Desarrollo Cristian Bustos
Método de la gran M
Maximizar: Z=6x1+8x2+4x3
Sujeto a:
x1 + 4x2 + 2x3 ≥ 25
3x1 + 2x2 + x3 ≤ 30
x1 + x2 + 5x3 = 18
x1 ≥ 0; x2 ≥ 0; x3 ≥0
Se convierten las restricciones a igualdades
x1+4x2+2x3 - s1 +M1 = 25 3x1+2x2+3x+s2= 30 x1 +x2+ 5 x3 = 18
Z= 6x1+ 8x2+4x3 -M(M1)
W=M1
Z=6x1+8x2+4x3-M (M1)
Base x1 x2 x3 s1 M1 S2 RHS
M1 1 4 2 -1 1 0 25
S2 3 2 1 0 0 1 30
1 1 5 0 0 0 18
Z -6-M -8-4M -4-2M M -M 0 0
Método de las dos fases:
Fase 1: Se minimiza la suma de las variables artificiales
W=M1
Base x1 x2 x3 s1 M1 S2 RHS
M1 1 4 2 -1 1 0 25
S2 3 2 1 0 0 1 30
1 1 5 0 0 0 18
W -1 -4 -2 1 -1 0 0
Fase 2: Se maximiza la función objetivo usando la solución de Fase 1
Z= 6x1+8x2+4x3
Base x1 x2 x3 s1 M1 S2 RHS
s1 1 4 2 -1 1 0 25
s2 3 2 1 0 0 1 30
1 1 5 0 0 0 18
Z -6 -8 -4 0 0 0 0
Desarrollo Daniel Steven Fandiño M
Función objetivo: Maximizar Z=3x1+4x2Z = 3x_1 + 4x_2Z=3x1+4x2
Restricciones:
1. 2x1+x2≤82x_1 + x_2 \leq 82x1+x2≤8
2. x1+3x2≤12x_1 + 3x_2 \leq 12x1+3x2≤12
3. x1≥0x_1 \geq 0x1≥0
4. x2≥0x_2 \geq 0x2≥0
Método de la Gran M
1. Se Convierten las restricciones
● Añadimos las variables de holgura s1s_1s1y s2s_2s2para convertir las desigualdades en
igualdades:
2x1+x2+s1=8
2x_1 + x_2 + s_1 = 8
2x1+x2+s1=8
x1+3x2+s2=12
x_1 + 3x_2 + s_2 = 12
x1+3x2+s2=12
● Las variables de holgura s1y s2s_2sson ≥0.
2. Formulación de la nueva función objetivo
Si hubiera variables artificiales, añadiremos penalizaciones. Aquí no las necesitamos, así que
podemos trabajar directamente con la función objetivo:
Maximizar Z=3x1+4x2+0s1+0s2
Base S X1 X2 S1 S2 Soluciones
S1 2 1 1 0 8
S2 1 3 0 1 12
Z -3 -4 0 0 0
1. Fase 1
Si tienes variables artificiales, planteas una nueva función objetivo que minimiza la suma de esas
variables. Supongamos que tenemos variables artificiales a1a_1a1y a2a_2a2:
● Para convertir las restricciones en igualdades con variables artificiales, tendrías:
2x1+x2+s1+a1=8
2x_1 + x_2 + s_1 + a_1 = 82
x1+x2+s1+a1=8
x1+3x2+s2+a2=12
x_1 + 3x_2 + s_2 + a_2 = 12x1+3x2+s2+a2=12
La función objetivo para la fase 1 sería:
Minimizar W=a1+a2
{Minimizar } W = a1 + a2
Minimizar W=a1+a2
Identificamos la variable de entrada y observamos la fila Z
Los coeficientes son:
-3 para x1y -4 para x2.
Determinar la variable de la salida
Encontramos la variable de salida para esto tenemos que calcular la razón minina
solución y coeficiente de la variable que entra
Para S1:8/1=8
Para S2: 12/3=4
Esta variable de salida es S2 por que la razón tiene un mínimo de 4
Pivotar en 𝑥2 en la fila de 𝑠2 :
El valor de pivot es 3
(coeficiente de 𝑥2en la fila de 𝑠2).
Realizar las operaciones de fila para hacer que el coeficiente de 𝑥2
en las otras filas se
Método de Dos Fases
1. Fase 1
Si tienes variables artificiales, planteas una nueva función objetivo que minimiza la suma de esas
variables. Supongamos que tenemos variables artificiales a1a_1a1y a2a_2a2:
● Para convertir las restricciones en igualdades con variables artificiales, tendrías:
2x1+x2+s1+a1=8
2x_1 + x_2 + s_1 + a_1 = 8
2x1+x2+s1+a1=8
x1+3x2+s2+a2=12
x_1 + 3x_2 + s_2 + a_2 = 12
x1+3x2+s2+a2=12
La función objetivo para la fase 1 sería:
Minimizar W=a1+a2
2. Se crea la tabla inicial
Bases X1 X2 S1 S2 A1 A2 Solución
s1 2 1 1 0 1 0 8
s2 1 3 0 1 0 1 12
w 0 0 0 0 -1 -1 0
Continuar con la optimización hasta que el resultado sea W=0W = 0W=0.
CONCLUSIONES
Ambos métodos deben llegar a la misma solución óptima, aunque pueden seguir caminos
distintos para lograrlo. Trabajar en grupo facilitó la identificación y corrección de errores,
haciendo el proceso más sencillo que si se hubiera trabajado de manera individual. Discutir las
respuestas con los compañeros también enriqueció el proceso de aprendizaje y clarificó el
material..
5. REFERENCIAS
Moncayo-Martínez, L. A., & Muñoz, D. F. (2018). Un sistema de apoyo para la enseñanza del
método simplex y su implementación en computadora.
https://www.scielo.cl/scielo.php?pid=S0718-50062018000600029&script=sci_arttext
Cantú Cuéllar, R. (1996). Programación no lineal (Doctoral dissertation, Universidad Autónoma de Nuevo
León) Retrieved October 27, 2024, from
http://chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://eprints.uanl.mx/393/1/10800724
05.PDF
