1
TECNOLÓGICO NACIONAL DE MÉXICO
INSTITUTO TECNOLÓGICO SUPERIOR
DE ALVARADO - Campus Medellín
INGENIERIA INDUSTRIAL
MATERIA:
INC-1018 Investigación de operaciones I
SEMESTRE - SISTEMA:
4to - Escolarizado
PRODUCTO ACADÉMICO:
Investigación U2
PRESENTA(N):
Valenzuela Meza Cesar (206Z0276)
DOCENTE:
I.I María de los Ángeles Cuervo Vázquez
FECHA:
02/Marzo/2022
2
Índice
INTRODUCCIÓN.............................................................................................................................3
2.3 Procedimiento para resolver problemas con variables artificiales (M grande, doble
fase)..............................................................................................................................................4
2.4 Casos especiales de programación lineal.........................................................................5
2.5. Método dual simplex...........................................................................................................6
CONCLUSIÓN.................................................................................................................................9
FUENTES DE LA INFORMACIÓN.............................................................................................10
3
INTRODUCCIÓN
Todas las personas toman decisiones de manera diaria y rutinaria, más aún
aquellos quienes encabezan alguna empresa; sin embargo, trátese del ámbito que
se trate, tomar una decisión es más complejo de lo que pudiera parecer ya que su
efecto o consecuencia en ocasiones no es la que se espera. El Método Simplex es
una herramienta matemática básica en la toma de decisiones, pero requiere de
entender cada uno de sus pasos y la constancia de practicarlos. Minimizar costos
o maximizar ganancias dependerá de las necesidades de cada empresa o sujeto,
los caminos para tomarlos son infinitos, pero cuando se trata de más de dos
variables, el camino realmente óptimo se encuentra justo en este momento en sus
manos. La razón matemática de esta mejora radica en que el método consiste en
caminar del vértice de un poliedro a un vértice vecino de manera que aumente o
disminuya (según el contexto de la función objetivo, sea maximizar o minimizar),
dado que el número de vértices que presenta un poliedro solución es finito
siempre se hallará solución.
4
2.3 Procedimiento para resolver problemas con variables artificiales (M grande,
doble fase).
Existen problemas de programación lineal que no proporcionan una solución
básica inicial. Esta situación se presenta cuando al menos una de las restricciones
es del tipo (<=) o (=). Para este propósito se desarrollan 2 métodos basados en el
uso de variables artificiales: El método M o de penalización y la técnica de 2 fases.
El método M grande: es una forma derivada del método simplex, usado para
resolver problemas donde el origen no forma parte de la región factible de un
problema de programación lineal.
Para realizar este algoritmo, 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 la operación,
llamado M y que además deberá irse solamente cuando se sume o reste con otra
M.
Para el caso de maximización, tenemos que restar las variables artificiales junto
con sus coeficientes para que estas variables no entren a la base, pero si
minimizamos entonces tendremos que sumar las variables artificiales.
Los pasos básicos:
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
5
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.
El método simple de 2 fases: es una estrategia algorítmica que 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.
Fase 1: Consideramos un problema auxiliar que resulta de agregar tantas
variables auxiliares a las restricciones del problema, de modo de obtener
una solución básica factible. Luego se debe resolver un nuevo problema
que considera como función objetivo la suma de las variables auxiliares
utilizando el Método Simplex. Si el valor óptimo alcanzado al finalizar la
Fase 1 es cero, se debe pasar a la Fase 2. En caso contrario, no existe
solución factible.
Fase 2: Resolver a través del Método Simplex el problema original a partir
de la solución básica factible inicial hallada en la Fase 1.
El cómo resolver problemas de programación lineal entre otros aspectos
serán abordados más adelante pero no quiero despedirte sin antes
recordarte la importancia de conocer los fundamentos del método simplex
abordado en clases anteriores ya que este método es la base de otros
métodos como el analizado en esta ocasión.
2.4 Casos especiales de programación lineal.
El Método Simplex se utiliza mayormente para problemas lineales en los que
intervienen múltiples variables, los cuales no pueden ser resueltos de manera
gráfica pues se haría demasiado complejo. Para ello, este método hace uso de la
propiedad de que la solución óptima de un problema de Programación Lineal se
encuentra en un vértice o frontera del dominio de puntos factibles (esto último en
casos muy especiales), por lo cual, la búsqueda secuencial del algoritmo se basa
en la evaluación progresiva de estos vértices hasta encontrar el óptimo. Cabe
destacar que, para aplicar el Método Simplex a un modelo lineal, este debe estar
en un formato especial conocido como formato estándar. Para la solución de un
6
problema de programación lineal usando el método SIMPLEX el planteamiento
con esta forma toma el nombre de forma canónica y una vez eliminado las
desigualdades entonces se denomina forma estándar.
A continuación, un resumen de los siguientes escenarios:
Infinitas Soluciones Óptimas: Se detecta cuando luego de alcanzar una
solución básica factible óptima, al menos una variable no básica tiene costo
reducido igual a cero.
Problema No Acotado: En las iteraciones del Método Simplex un problema
no acotado se detecta cuando al calcular el criterio de factibilidad o mínimo
cociente que determina la variable que deja la base, todas las entradas en
la columna de la variable no básica entrante son negativas o cero, por
tanto, no existe denominador válido (mayor a cero) que permita determinar
el pivote.
Problema Infactible: Si al finalizar la Fase I del Método Simplex de 2 Fases
el valor de la función objetivo es distinto a cero, entonces el problema lineal
es infactible, es decir, el dominio de soluciones factibles es vacío al existir
restricciones incompatibles.
Solución Óptima Degenerada: Cuando se presenta un empate en el cálculo
de la condición de factibilidad del Método Simplex, al menos una variable
básica será cero en la siguiente iteración, caso en el cual se dice que la
nueva solución es degenerada. Esto implica que el modelo tiene al menos
una restricción redundante.
2.5. Método dual simplex.
Como sabemos, el método simplex es un algoritmo iterativo que iniciando en una
solución básica factible pero no óptima, genera soluciones básicas factibles cada
vez mejores hasta encontrar la solución óptima (sí está existe). Nótese que la
base de su lógica es mantener la factibilidad, mientras busca la optimalidad. Pero
surge la posibilidad de usar otro esquema igualmente iterativo, que, como
contraparte del simplex, comienza en una solución básica óptima, pero no factible
7
y mantiene la inmejorabilidad mientras busca la factibilidad. Con este
procedimiento se llega igualmente a la solución óptima.
El nuevo algoritmo fue desarrollo en 1954 por C. E. Lemke y se conoce con el
nombre de Método Dual-Simplex. A continuación, se presenta su estructura y un
ejemplo para ilustrar su aplicación.
Primero se debe expresar el modelo en formato estándar, agregando las variables
de holgura y de exceso que se requieran.
Enseguida, en las ecuaciones que tengan variables de exceso (resultantes de
restricciones de tipo >), se debe multiplicar por (-1) en ambos lados, para hacer
positivo el coeficiente de la variable de exceso, y formar así un vector unitario que
nos permita tomar esta variable de exceso como una variable básica inicial. sin
necesidad de agregar una variable artificial en esa restricción.
Al hacer lo anterior se logra que debajo de las variables básicas aparezca
una matriz identidad, que es la que el simplex siempre toma como base
inicial.
Obtendremos que los términos del lado derecho de las ecuaciones
multiplicadas por (-1) quedan con signo negativo, lo cual hace que la
solución inicial sea infactible.
Es importante destacar que este proceso es muy útil ya que en muchos
modelos evita la inclusión de variables artificiales en el momento de
transformar un modelo a formato estándar
l algoritmo para resolver un modelo de maximización es el siguiente:
Paso 1: Hallar una solución básica inicial infactible e inmejorable
Escribir el tablero inicial tomando a las variables de holgura y de exceso
como variables básicas iniciales
Paso 2: Prueba de factibilidad
Si todas las variables básicas son no negativas, la actual solución es la
óptima.
8
Si hay al menos una variable básica negativa, seleccionar como variable de
salida, (llamémosla (XB)s), a aquella con el valor más negativo. Los
empates se pueden romper arbitrariamente.
Paso 3: Prueba de inmejorabilidad
Sí en el renglón de la variable básica de salida (XB)s todos los coeficientes
de reemplazo con las variables no básicas son no negativos, la solución del
modelo es óptima ¡limitada. Se termina el proceso.
Si en el renglón de la variable básica de salida (XB)s, hay al menos un
coeficiente de intercambio negativo, se efectúan los cocientes entre el
efecto neto de cada variable no básicas y su correspondiente coeficiente de
intercambio negativo. Es decir, siendo (XB)s la variable de salida se
calculan todos los cocientes.
Se toma como variable de entrada (Llamémosla Xe) a aquella que
corresponda al mínimo de los cocientes del anterior conjunto
Si la variable de entrada es Xe el elemento pivote será el elemento (Se)s
El empate se puede romper arbitrariamente.
Aplicar la operación de pivoteo para generar la nueva tabla, en la cual
aparezca Xe como variable básica en lugar de la variable de salida (XB)s
Repetir el algoritmo a partir del paso 2.
La aplicación del método simplex dual es especialmente útil en el análisis de
sensibilidad. Se usa cuando después de haber obtenido la solución óptima, se
desea agregar una nueva restricción al modelo si la nueva restricción no se
cumple.
En este caso se obtiene que, para los valores óptimos de las variables de
decisión, la solución permanece óptima, pero se convierte en infactible. Surge
entonces la necesidad de aplicar el algoritmo Dual-Simplex para extraer la variable
básica que tiene valor infactible. Cuando estudiemos el tema de análisis de
sensibilidad analizaremos un caso como el citado.
9
CONCLUSIÓN
Si bien el Método Simplex puede ser resuelto de forma algebraica, la forma tabular
es apropiada para todos aquellos que se encuentran en un curso introductorio y
que no necesariamente tengan el conocimiento del uso de matrices o poliedros. La
gran virtud del método simplex es su sencillez, método muy práctico, ya que solo
trabaja con los coeficientes de la función objetivo y de las restricciones. Este
método es muy importante en el área empresarial ya que lo utilizan para obtener
solución a los problemas de las empresas en cuanto a inventario, ganancias y
pérdidas. Este método permite visualizar cuanto se debe vender, cuanto se debe
producir o cuanto se debe comprar según sea el caso para que la empresa
obtenga las ganancias optimas y suficientes para competir en el mercado.
El mercado y la constante competencia piden y exigen personas generadoras de
ideas nuevas, pero justo cada idea requiere decisiones que implican una serie de
recursos de toda índole.
10
FUENTES DE LA INFORMACIÓN
educación, P. (2004). Investigacion de operaciones (Septima edicion ed.). Mexico.
doi:970-26-0498-2
Gestion de operaciones. (s.f.). Recuperado el 02 de MARZO de 2022, de Gestion
de operaciones:
[Link]
especiales-en-la-programacion-lineal-detectados-con-el-metodo-simplex/
inoperaciones. (s.f.). Recuperado el 02 de MARZO de 2022, de inoperaciones:
[Link]
al/Plan%201997-2004/Invoperaciones1/[Link]
investigacion de operaciones. (s.f.). Recuperado el 02 de MARZO de 2022, de
investigacion de operaciones:
[Link]
metodo-de-dos-fases/#:~:text=El%20m%C3%A9todo%20simple%20de
%202,una%20soluci%C3%B3n%20b%C3%A1sica%20factible%20inicial.
Invoperaciones. (s.f.). Recuperado el 02 de MARZO de 2022, de Invoperaciones:
[Link]
simplex/
[Link]. (s.f.). Recuperado el 02 de MARZO de 2022, de [Link]:
[Link]
la-m-grande