UNIVERSIDAD DE SAN CARLOS DE GUATEMALA
Centro Universitario del Norte
Ingeniería en Ciencias y Sistemas
Ing. Marwin Moran Castro
ENTREGA DE LABORATORIO 2
MODELO DEL METODO “ M ”
MODELO DEL METODO “ DOS FASES ”
Cobán, Alta Verapaz, agosto de 2022
INDICE
INDICE .............................................................................................................................................. 2
INTEGRANTES ................................................................................................................................ 3
OBJETIVOS ...................................................................................................................................... 4
MARCO TEORICO ......................................................................................................................... 5
METODO “M” .............................................................................................................................. 5
MÉTODO DE DOS FASES ......................................................................................................... 7
SOLUCIONES A CASOS PROPUESTOS ..................................................................................... 9
MODELO DEL MÉTODO “M” ................................................................................................. 9
MODELO DEL MÉTODO DE DOS FASES ........................................................................... 13
CONCLUSIONES ........................................................................................................................... 18
BIBLIOGRAFIA ............................................................................................................................. 19
INTEGRANTES
Fryda Maryelyza Contreras Catalán - 202040947 - Ing. Industrial
María Guadalupe Yalibat Yoj - 202040140 - Ing. Industrial
Elí Alexander Cacao Chocooj - 202043318 - Ing. Industrial
Diego Alejandro Morales Obregón - 202040187 - Ing. Sistemas
Alvaro Alejandro Pape Gregg - 201743461 - Ing. Industrial
OBJETIVOS
Comprender el método simplex para poder solucionar problemas de una manera
eficaz.
Estudiar la técnica M para comprender las diferentes técnicas y métodos en la
solución de modelos de programación lineal.
Analizar el método de dos fases para comprender la importancia de las variables
artificiales en la solución del problema.
MARCO TEORICO
METODO “M”
El método “M” es usado para resolver problemas donde el origen no forma parte de
la región factible de un problema de programación lineal.
Al utilizar este método se siguen los mismos pasos que en el método simplex, pero antes
tenemos que cambiar la función objetivo para que incluya a las variables artificiales. Estas
variables tendrán que estar multiplicadas por un numero suficientemente grande para que no
se elimine a través de las operaciones, llamado M y que además deberá irse solamente
cuando se sume o reste con otra M.
Los pasos básicos del método M son los siguientes:
1. Exprese el problema en forma estándar transformando las inecuaciones en ecuaciones
introduciendo variables de holgura.
2. Agregue variables no negativas al lado izquierdo de cada una de las ecuaciones
correspondientes a las restricciones de tipo (>=) o (=). Estas variables se denominan
variables artificiales y su adición hace que las restricciones correspondientes.
Esta dificultad se elimina asegurando que las variables sean 0 en la solución final.
Esto se logra asignando una penalización muy grande por unidad a estas variables en
la función objetivo. Tal penalización se designará como –M para problemas de
maximización y +M para problemas de minimización.
3. Utiliza las variables artificiales en la solución básica inicial; sin embargo la función
objetivo de la tabla inicial se prepara adecuadamente para expresarse en términos de
las variables no básicas únicamente. Esto significa que los coeficientes de las
variables artificiales en la función objetivo deben ser 0 un resultado que puede
lograrse sumando múltiplos adecuados de las ecuaciones de restricción al renglón
objetivo.
4. Proceda con los pasos regulares del método simplex.
En pocas palabras la solución final será como si las variables artificiales nunca hubieran
existido en primer lugar. Según lo previsto, se busca que en la aplicación del Método de la
M Grande las variables auxiliares sean no básicas en el óptimo. Si el modelo
de Programación Lineal es infactible la iteración del Método Simplex final incluirá al
menos una variable artificial como básica.
De modo complementario la aplicación de la técnica de la M significa en teoría, que M
tiende a infinito. Sin embargo, al usar la computadora M debe ser finito,
pero suficientemente grande. En específico M debe ser lo bastante grande como para
funcionar como penalización, al mismo tiempo no debe ser tan grande como para perjudicar
la exactitud de los cálculos del Método Simplex, al manipular una mezcla de números muy
grandes y pequeños.
MÉTODO DE DOS FASES
El Método de Dos Fases es una variante del método SIMPLEX y es usado como alternativa
al Método de la Gran M, pues evita el uso de la constante M; este método resuelve el modelo
de programación lineal en dos fases, el cual, como su nombre lo indica, se resuelve por medio
de dos fases o procedimientos, con el fin de encontrar primeramente una solución factible
inicial y después pasar a resolver el modelo a través del método SIMPLEX.
El Método de Dos Fases se aplica cuando luego de llevar un modelo de programación lineal
a su forma estándar no se dispone de una solución básica factible inicial, además las variables
de decisión deben ser reales y mayores a cero.
Conceptos
o Variable artificial: Es un truco matemático donde para convertir inecuaciones ≥ en
ecuaciones tienen como característica que no deben formar parte de la solución, dado
que no presentan recursos, pero ayudan a formar la matriz identidad.
o Solución básica: Son valores de las variables básicas que satisfacen la condición de
no negatividad.
o Variable básica: Son las m variables que tienen una solución única.
o Forma canónica de PL: La forma canónica reconocida y aceptable en la mayoría de
textos debe cumplir los siguientes requisitos:
Función objetivo maximizar
Restricciones del tipo
Condiciones de negatividad para variables
Otra forma para considerarse una forma canónica es cumpliendo los siguientes
requisitos:
Función objetivo maximizar
Restricciones del tipo
Condiciones de no negatividad para variables.
o Forma estándar de PL: El modelo de PL para resolverse necesita ajustarse para
igualdades, lo cual se consigue utilizando tanto variables de holgura como superfluas.
Para le presentación de este modelo se deben cumplir los siguientes requisitos:
Función objetivo para maximizar o minimizar
Restricciones del tipo “=”
Lado derecho de restricciones no negativo
Condiciones de no negatividad para variables
Procedimiento del Método de Dos Fases
Las fases del Método de Dos Fases se describen a continuación:
Fase I:
o Se considera un modelo de programación lineal que se encuentra en su forma
canónica, dicho modelo se debe transformar en su forma ampliada agregando
variables artificiales en las restricciones donde el origen no es una solución
(exactamente como en el Método M).
o A continuación, se determina una solución básica de la ecuación resultante que
siempre minimice la suma de las variables artificiales, independientemente de si la
PL (programación lineal) es de maximización o minimización.
o Se procede a resolver el modelo que se planteo hasta que se de uno de los siguientes
casos: Si el valor mínimo de la suma es positivo, el problema de PL no tiene una
solución factible. De lo contrario, si el valor mínimo es cero se prosiga con la fase II.
Fase II:
En esta segunda fase se utiliza la solución factible de la fase I como una solución factible
básica inicial para el problema original.
o Se eliminan las variables artificiales de las restricciones, pero se conservan los
cambios que se dieron durante la fase I.
A continuación, se debe regresar a la función objetivo original y resolvemos el modelo que
se dieron en las restricciones durante la fase I.
SOLUCIONES A CASOS PROPUESTOS
MODELO DEL MÉTODO “M”
ENUNCIADO
La empresa “Lácteos Florencia” desea hacer la minimización de costos sobre todos los
productos lácteos que se fabrican y distribuyen dentro de su empresa. Tienen tres diferentes
productos y a continuación se presentan los procesos para fabricarlos:
PRODUCTO 1: 2 horas para medicion de leche y 2 horas de moldeado
PRODUCTO 2: 2 horas para medicion de leche y 3 horas de moldeado
PRODUCTO 3: 3 horas para medicion de leche y 1 hora de moldeado
La utilidad de elaboración para cada uno de los productos es de $3, $2 y $4
consecutivamente.
Como nota adicional, se nota que el proceso de medición de leche se puede efectuar como
minimo 15 horas, mientras que el tiempo de moldeado se puede realizar como maximo 12
horas
Concretar la minimización por medio del método M.
ELABORANDO TABLA INICIAL
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝑹𝒆𝒔𝒕𝒓𝒊𝒄𝒄𝒊𝒐𝒏𝒆𝒔
𝒕𝒊𝒆𝒎𝒑𝒐 𝑴𝒆𝒅𝒊𝒄𝒊𝒐𝒏 2 2 3 15
𝒕𝒊𝒆𝒎𝒑𝒐 𝑴𝒐𝒍𝒅𝒆𝒂𝒅𝒐 2 3 1 12
𝒖𝒕𝒊𝒍𝒊𝒅𝒂𝒅 $3 $2 $4
PLANTEANDO LA FUNCION OBJETIVO:
𝑍 = 3𝑥1 + 2𝑥2 + 4𝑥3
PLANTEANDO RESTRICCIONES:
2𝑥1 + 2𝑥2 + 3𝑥3 ≥ 15
2𝑥1 + 3𝑥2 + 𝑥3 ≤ 12
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
APLICANDO FASES DEL METODO M:
Primera fase:
𝑍 = 3𝑥1 + 2𝑥2 + 4𝑥3 + 0𝑠1 + 0𝑠2
2𝑥1 + 2𝑥2 + 3𝑥3 = 15 + 𝑠1
2𝑥1 + 3𝑥2 + 𝑥3 + 𝑠2 = 12
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
Segunda fase:
𝑍 = 3𝑥1 + 2𝑥2 + 4𝑥3 + 0𝑠1 + 0𝑠2 + 𝑀𝑅1
2𝑥1 + 2𝑥2 + 3𝑥3 − 𝑠1 + 𝑅1 = 15
2𝑥1 + 3𝑥2 + 𝑥3 + 𝑠2 = 12
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
Fase tres:
𝑍 − 3𝑥1 − 2𝑥2 − 4𝑥3 − 0𝑠1 − 0𝑠2 − 𝑀𝑅1 = 0
2𝑥1 + 2𝑥2 + 3𝑥3 − 𝑠1 + 𝑅1 = 15
2𝑥1 + 3𝑥2 + 𝑥3 + 𝑠2 = 12
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
PLANTEAMIENTO DE TABLA PARA RESOLUCION:
𝑧 𝑥1 𝑥2 𝑥3 𝑠1 𝑠2 𝑅1 𝑠𝑜𝑙𝑢𝑐𝑖𝑜𝑛
𝑅1 0 2 2 3 −1 0 1 15
𝑠2 0 2 3 1 0 1 0 12
𝑧 1 −3 −2 −4 0 0 −𝑀 0
MODELO DEL MÉTODO DE DOS FASES
Calcular el mínimo beneficio de una empresa que produce tres bienes 𝑥1 , 𝑥2 y 𝑥3 , que se
encuentran sujetos a los siguientes datos:
Característica/Bien 𝒙𝟏 𝒙𝟐 𝒙𝟑 Capacidad mínima
Mano de obra 1 4 2 8
Materias primas 3 2 0 6
Beneficio 2 3 1
*Beneficio en quetzales (Q.)
MÉTODO DE RESOLUCIÓN
Establecer función objetivo:
𝑍 = 2𝑥1 + 3𝑥2 + 𝑥3
Establecer restricciones:
a) Mano de obra
𝑥1 + 4𝑥2 + 2𝑥3 ≥ 8
b) Materias primas
3𝑥1 + 2𝑥2 ≥ 6
PRIMERA FASE
Transformar las inecuaciones como en el método M:
𝑥1 + 4𝑥2 + 2𝑥3 − 𝑠1 + 𝑅1 = 8
3𝑥1 + 2𝑥2 − 𝑠2 + 𝑅2 = 6
Plantear un nuevo problema:
Minimizar (independientemente si el problema original es de minimizar o maximizar):
𝑟 = 𝑅1 + 𝑅2
Igualar a cero la nueva función:
𝑟 − 𝑅1 − 𝑅2 = 0
Organizar en la tabla que ya conocemos:
Variable 𝑥1 𝑥2 𝑥3 𝑠1 𝑠2 𝑅1 𝑅2 Solución
r 0 0 0 0 0 -1 -1 0
𝑅1 1 4 2 -1 0 1 0 8
𝑅2 3 2 0 0 -1 0 1 6
Transformando la fila 1 para volver 𝑅1 y 𝑅2 iguales a cero:
Nueva 𝐹1 = 𝐹1 + 𝐹2 + 𝐹3
Variable 𝑥1 𝑥2 𝑥3 𝑠1 𝑠2 𝑅1 𝑅2 Solución
r 4 6 2 -1 -1 0 0 14
𝑅1 1 4 2 -1 0 1 0 8
𝑅2 3 2 0 0 -1 0 1 6
Una vez realizado esto, procedemos a utilizar el método simplex para resolver la tabla:
encontramos la variable de entrada (la más positiva) en este caso 𝑥2 y la variable de salida
que resulta del cociente mínimo entre las soluciones y los coeficientes de la columna pivote,
en este caso 𝑅1 .
Repitiendo cada uno de los pasos ya conocidos para el método simplex, y luego de dos
iteraciones, la tabla obtenida es:
Variable 𝑥1 𝑥2 𝑥3 𝑠1 𝑠2 𝑅1 𝑅2 Solución
r 0 0 0 0 0 -1 -1 0
𝑥2 0 1 3/5 -3/10 1/10 3/10 -1/10 9/5
𝑥1 1 0 -2/5 1/5 -2/5 -1/5 2/5 4/5
Al observar la tabla, vemos que hemos alcanzado una solución óptima, al no existir valores
positivos para la función r (minimización). Además, la solución de r = 0, lo que indica que
la función original si tiene solución.
SEGUNDA FASE
Habiendo encontrado el tablero óptimo, podemos encontrar las nuevas restricciones sin
considerar los valores de 𝑅1 y 𝑅2 :
Nuevas restricciones:
3 3 1 9
𝑥2 + 𝑥3 − 𝑠1 + 𝑠2 =
5 10 10 5
2 1 2 4
𝑥1 − 𝑥3 + 𝑠1 − 𝑠2 =
5 5 5 5
Retomamos el problema original:
𝑍 = 2𝑥1 + 3𝑥2 + 𝑥3 + 0𝑠1 + 0𝑠2
Igualando a cero:
𝑍 − 2𝑥1 − 3𝑥2 − 𝑥3 − 0𝑠1 − 0𝑠2 = 0
Creamos nuestra tabla (dejando las variables básicas con las que terminamos la fase 1):
Variable 𝑥1 𝑥2 𝑥3 𝑠1 𝑠2 Solución
Z -2 -3 -1 0 0 0
𝑥2 0 1 3/5 -3/10 1/10 9/5
𝑥1 1 0 -2/5 1/5 -2/5 4/5
Transformando para obtener la tabla inicial simplex:
Nueva 𝐹1 = 𝐹1 + 3𝐹2 + 2𝐹3
Variable 𝑥1 𝑥2 𝑥3 𝑠1 𝑠2 Solución
Z 0 0 0 -1/2 -1/2 7
𝑥2 0 1 3/5 -3/10 1/10 9/5
𝑥1 1 0 -2/5 1/5 -2/5 4/5
Al observar la tabla, vemos que hemos alcanzado una solución óptima, al no existir valores
positivos para la función Z (minimización). Entonces, tenemos que:
𝑥1 = 4/5
𝑥2 = 9/5
𝑍=7
Comprobando:
𝑍 = 2𝑥1 + 3𝑥2 + 𝑥3
4 9
(7) = 2 ( ) + 3 ( ) + (0)
5 5
8 27
(7) = ( ) + ( )
5 5
35
7=
5
7=7
R// El beneficio mínimo de la empresa corresponde a Q7.00 y ocurre cuando se producen 4/5
unidades del bien 𝑥1 y 9/5 unidades del bien 𝑥2 .
CONCLUSIONES
Es importante comprender el método simplex debido que se utiliza para resolver
problemas lineales con mayor precisión.
Es esencial estudiar la técnica M, para comprender el porque es una forma derivada
del método simplex y que es usado para resolver problemas donde el origen no forma
parte de la región factible.
Es fundamental analizar la función de las variables artificiales en el método de dos
fases, ya que nos sirve en la solución de la fase 1 y en la fase 2 para la solución del
problema lineal.
BIBLIOGRAFIA
Desconocido. (21 de Mayo de 2015). investigaciondeoperacionesunounivia.wordpress.com.
Obtenido de investigaciondeoperacionesunounivia.wordpress.com:
https://investigaciondeoperacionesunounivia.wordpress.com/2015/05/21/metodo-de-
dos-fases/
Desconocido. (17 de Enero de 2018). sites.google.com. Obtenido de sites.google.com:
https://sites.google.com/site/metodosdeprogramacionlinealdan/metodo-de-las-dos-fases
Desconocido. (21 de Agosto de 2022). mathstools.com. Obtenido de mathstools.com: 08
Erick, C. (18 de Febrero de 2015). Prezi.com. Obtenido de Prezi.com:
https://prezi.com/fqqqryaalhej/tecnica-m/
Francisco. (21 de Marzo de 2016). gestiondeoperaciones.net. Obtenido de
gestiondeoperaciones.net:
https://www.gestiondeoperaciones.net/programacion_lineal/metodo-de-la-m-grande-o-
gran-m-en-programacion-lineal/
