Metodo Simplex Solucion Artificial

Vista previa del material en texto

Investigación
Operativa
Método Simplex: Solución Artificial de 
Inicio:
 Método Penal o de la M Grande
 Método de Dos Fases
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
Investigación
Operativa
Solución Artificial de Inicio:
 Método Penal o de la M Grande
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
Método Penal o de la M grande: Variable Ficticia µ (W o A)
• Cuando en el sistema de inecuaciones de restricción, alguna de las inecuaciones tiene una 
desigualdad del tipo ≥, se tiene que la V. de H. asociada a esa ecuación tiene un coeficiente unitario 
negativo (-1) en la tabla inicial, lo que la elimina de conformar una SBF.
• Cuando alguno de las variables del vértice en estudio es negativa (-) indica que dicho vértice no 
pertenece al convexo.
• La variable µ adicionada “no tiene significado físico” dentro del problema y la SBF no
representa vértice real del convexo.
Para solucionar este problema se hace un artificio algebraico: se crea una variable “ficticia” µ con
coeficiente “+1” en la ecuación (la fila) necesaria para conformar una submatriz unidad dentro de
la matriz A [m x n].
Ing. Carlos Martin
Método Penal o de la M grande: Concepto de Penalidad
• La variable µ, tanto por razones algebraicas, como de significado físico, no puede 
integrar la solución óptima real debiéndose buscar que la misma salga
posteriormente de la base y permanezca fuera de ella, respetando, no obstante, 
todas las reglas del simplex.
• Esto puede realizarse definiendo para la variable adicional ficticia µ un coeficiente de 
beneficio |M| en el funcional arbitrariamente grande en valor absoluto, y de signo 
opuesto al objetivo del problema: 
• Consecuentemente, mientras la variable ficticia µ permanezca en la base, su 
coeficiente M intervendrá en el cálculo del funcional, dando para éste un resultado 
indeseado (este es el concepto de penalidad: penalizamos a la variable artificial µ en 
el funcional).
• “No siempre es necesario la introducción de V. ficticia”: El problema que ocasiona el 
signo (-) en las V. de H. se puede resolver por medio de las variables originales del 
problema  dentro de la matriz de coeficiente se puede hallar una submatriz 
cuadrada con la configuración DE UNA MATRIZ UNIDAD.
• Es por ello que no constituye una regla fija la inclusión de una variable artificial (µ) 
en las ecuaciones formadas a partir de relaciones de “≥” o “=”.
Ing. Carlos Martin
Método Penal o de la M grande
Al final del proceso de calculo, hay tres posibilidades:
a) Que la variable artificial no aparezca en la última tabla del
simplex, lo que indica que el problema tiene solución.
b) Que la variable artificial aparezca en la última tabla del
simplex con un valor igual a cero, esto significa que el problema
tiene solución y la solución es degenerada.
c) Que la variable artificial aparezca en la última tabla del
simplex, lo que indica que el problema no tiene solución.
Ing. Carlos Martin
Método Penal o de la M grande: Caso de Incompatibilidad
Cuando la solución optima del problema contiene una o mas
variables artificiales (i), se esta en presencia de un caso de
incompatibilidad entre las restricciones planteadas. No existe
solución.
El origen debe buscarse en el conjunto de las restricciones del
problema, quienes son las que definen la no existencia de posibles
soluciones.
Por lo tanto, si se ha llegado a una solución óptima y en la base
correspondiente hay alguna variable artificial, el óptimo se ha
alcanzado mediante una solución no perteneciente al recinto
convexo (el recinto no existe).
Además como el funcional óptimo está asociado a |M|, siendo |M|
un valor arbitrariamente grande, situación que se opone al objetivo
del problema.
Ing. Carlos Martin
SOLUCION ARTIFICIAL DE INICIO: METODO PENAL
 El origen de coordenadas (solución trivial), no es un punto extremo del convexo.
Ing. Carlos Martin
 Dentro del conjunto de coeficientes, no puede hallarse una submatriz 
cuadrada Identidad
 No contamos con una SFB inicial
Solución en el Punto Cero:
La costumbre de comenzar 
en el origen, parte del 
hecho de ser el caso más 
sencillo de las soluciones 
posibles
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Se agrega la variable artificial µ1 con coeficiente +1
Ing. Carlos Martin
Ing. Carlos Martin
 En la columna B están los valores independientes del sistema de 
ecuaciones, es decir, las limitaciones. 
 En el resto de las columnas a la derecha de B, los coeficientes 
tecnológicos de las variables.
 Los valores que están en la fila superior del cuadro representan los 
beneficios unitarios. Para las variables de holgura serán nulos, puesto 
que sus productos no se venderán.
 La columna (X) indica las variables x que concretan la primera solución. 
 La columna beneficio C contiene, para cada variable de la columna X, el 
valor del beneficio por unidad.
EXPLICACIONES DE LA TABLA
Ing. Carlos Martin
El valor del Funcional Z lo obtenemos sumando los productos del elemento 
de cada fila de la columna B por el respectivo valor de la fila de la columna 
C. El el valor de Z será:
Z = 0 . 6 + (- M) . 6 + 0 . 10 = - 6 M
Los Zj los obtenemos sumando los productos del elemento de cada fila de 
la columna que estamos calculando por el respectivo valor de la fila de la 
columna C. Para el caso de la columna A1, el valor Z1 será:
Z1 = 0 . 1 + (- M) . 3 + 0 . 1 = - 3 M
La fila Zj – Cj se calcula restando, para cada columna, al valor de, ZJ
correspondiente, el valor CJ que encontramos en la parte superior del 
cuadro, para esa columna. Así, tenemos:
Z1 – C1 = (- 3 M) – (11) = - 3 M - 11
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Transformación de los coeficientes de la tabla
 Paso 1: Completar numéricamente la fila de la variable que entra.
Transformación de los elementos de la fila de la variable que 
entra: Dividir todos los elementos por el pivote
 Paso 2: Completar con ceros y unos las columnas de las variables 
básicas.
Ing. Carlos Martin
Transformación de los coeficientes de la tabla
 Paso 3: Completar numéricamente el resto de las filas.
Valores numéricos de la primer fila:
6 – (6 . 1) / 3 = 4 ; 1 – (1 . 2) /3 = 1/3 ; 0 – [1 . (-1)]/3 = 1/3 ; 0 – (1 . 1) / 3 = - 1/3
Valores numéricos de la tercera fila:
10 – (6 . 1) / 3 = 8 ; 2 – (1 . 2) /3 = 4/3 ; 0 – [1 . (-1)]/3 = 1/3 ; 0 – (1 . 1) / 3 = - 1/3
Ing. Carlos Martin
Ing. Carlos Martin
Análisis de Factibilidad
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Como vemos, la 
variable artificial µ1=0,
no aparece en la tabla 
optima del simplex, 
lo que indica que el 
problema tiene solución.
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Investigación
Operativa
Ejemplo para convertir un PL de Forma 
Equivalente a Estándar aplicando las 
reglas, añadiendo variables de exceso, 
holgura y artificiales
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
Convertir un PL de Forma Equivalente a Estándar
Pasamos el problema a la forma estándar, aplicando las reglas; añadiendo variables de 
exceso, holgura, y artificiales según corresponda.
 Por medio de la regla 1, la función objetivo queda:
Máx h = - Z = - 3 X1 + 4 X2 – X3
 Como la restricción 1 es del tipo '≥' se agrega la variable de exceso X4 (-1) y la variable
artificial µ1 (+1)
 Como la restricción 2 es del tipo '=' se agrega la variable artificial µ2 (+1)
0,5 X1 -2 X2 - 1 X4 + 1 µ1 = 3
1 X2 - 1 X3 + 1 µ2 = 4
Ing. Carlos Martin
Ing. Carlos Martin
Investigación
Operativa
Solución Artificial de Inicio:
• Método de Dos Fases
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
• Cuando no se dispone fácilmente de una solución básica
factible, se puede utilizar el método simplex de dos fases
como una alternativa para el método de la M Grande.
•En el método simplex de dos fases, añadimos variables
artificiales a las mismas restricciones como en el método de
la M Grande.
• Después encontramos una sbf para el PL original,
resolviendo el PL Fase l donde la función objetivo es
simplemente minimizar la suma de todas las variables
artificiales.
• Al terminar la Fase I, volvemos a introducir la función
objetivo del PL original, y determinamos la solución óptima
para el PL original.
Ing. Carlos Martin
Para tener en cuenta:
• Al igual que en el método de la M Grande, podremos omitir la 
columna, correspondiente a cualquier variable artificial, de 
cuadros futuros, tan pronto como la variable artificial salga de 
la base. 
• Se puede demostrar que el método de la M Grande y la Fase I 
del método simplex de dos fases, usan la misma secuencia de 
pivoteos. 
• La mayoría de los paquetes para computadoras usan el método 
de dos fases para encontrar una sbf. 
Esto se debe a que M, siendo un número grande, puede causar 
errores de redondeo y otras dificultades computacionales. 
El método de dos fases no introduce números grandes en la 
función objetivo, y de esta manera evita este problema. 
Ing. Carlos Martin
Obsérvese que los Pasos 1-3 del método simplex de dos fases 
son idénticos a los Pasos 1-3 del método de la M Grande.
• Paso 1 Modifique las restricciones de tal manera que el lado 
derecho de cada restricción sea no negativo. 
Esto requiere que se multiplique por -1 cada restricción con 
un lado derecho negativo.
• Paso 1' Identifique cada restricción que es ahora (después 
del Paso 1) una igualdad o una desigualdad ≥ .
En el Paso 3, añadiremos una variable artificial a cada una de 
estas restricciones.
• Paso 2 Transforme cada restricción que sea desigualdad a la 
forma estándar.
Esto implica que si la restricción i es una restricción , 
añadiremos una variable de holgura S¡, y si la restricción i es 
una restricción ≥, restaremos una variable de excedente e¡.
Ing. Carlos Martin
• Paso 3 Si ( después de completar el Paso 1') la 
restricción i es una desigualdad ≥ o una igualdad, añada 
una variable artificial a¡ a la restricción i. 
También añada la restricción de signo ai ≥ 0.
• Paso 4 Por el momento, ignore la función objetivo del 
PL original. 
En su lugar, resuelva un PL cuya función objetivo es 
min w' = (la suma de todas las variables artificiales). 
Esto se llama el PL Fase l. 
La solución del PL Fase I hará las variables artificiales 
necesariamente iguales a cero. 
Ing. Carlos Martin
• Ya que cada a¡ ≥ 0, la solución del PL Fase I corresponded a 
una de los tres casos siguientes: 
• Caso 1 El óptimo valor de w‘ es mayor que cero. 
En este caso, el PL original no tiene una solución factible.
• Caso 2 El valor óptimo de w‘ es igual a cero, y no hay 
variables artificiales en la base óptima de la Fase l. 
En este caso, omitimos todas las columnas que 
corresponden a las variables artificiales, en el cuadro óptimo 
de la Fase l. 
Ahora combinamos la función objetivo original con las 
restricciones del cuadro óptimo de la Fase l. 
Esto produce el PL Fase II. 
La solución óptima del PL Fase II, es la solución óptima para 
el PL original.
Ing. Carlos Martin
• Caso 3 El óptimo valor de w' es igual a cero, y por lo menos 
una variable artificial está en la base óptima de la Fase l. 
En este caso, podemos encontrar la solución óptima para el 
PL original, si al final de la Fase I, omitimos, del cuadro 
óptimo de la Fase I, todas las variables artificiales no básicas 
y cualquier variable del problema original con un coeficiente 
negativo en el renglón 0 del cuadro óptimo de la Fase l. 
Ing. Carlos Martin
Investigación
Operativa
Método de Las Dos Fases
Caso II (w' = 0)
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
Ejemplo:
Min Z = 2X1 + X2 + 3X3 
Sujeto a: 3X1 + X2 + 2X3 <= 10
X1 - 2X2 + 3X3 >= 6
2X1 + 3X2 - X3 <= 9 
X 1 + X2 + 2X3 = 7 
C.N.N (Condición de No Negatividad)
1. Convertir las desigualdades en igualdades: En resumen el modelo queda de la siguiente 
manera:
Min Z = 2X1 + X2 + 3X3 + 0S1 + 0S2 + A1 + 0S3 + A2 
Sujeto a:
3X1+ X2 + 2X3 + S1 = 10
X1 - 2X2 + 3X3 - S2 + A1 = 6
2X1+ 3X2 - X3 + S3 = 9 
X1+ X2 + 2X3 + A2 = 7 
C.N.N (Condición de No Negatividad)
Ing. Carlos Martin
Método de las Dos Fases: Fase 1
Ing. Carlos Martin
Método de las Dos Fases: Fase 1
Ing. Carlos Martin
Método de las Dos Fases: Fase 2
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Investigación
Operativa
Método de Las Dos Fases
Caso I (w'  0)
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
Después de completar los Pasos 1-4 del método simplex de dos 
fases, obtenemos el siguiente problema de Fase I: 
De este conjunto de ecuaciones, vemos que la sbf inicial para la Fase I es 
s1=4, a2 = 36, y a3 = 10. 
Ing. Carlos Martin
Como las variables básicas a2 y a3 se presentan en la función objetivo de la 
Fase I, hay que eliminarlas del renglón 0 de la Fase l. 
Para lograr esto, sumamos los renglones 2 y 3 al renglón 0: 
Como ninguna variable en el renglón tiene un coeficiente positivo, se trata de un 
cuadro óptimo de la Fase I.
Como el valor óptimo de w‘ = 6 (> 0), el PL original no tiene una solución factible.
Ing. Carlos Martin
Investigación
Operativa
Método de Las Dos Fases
Caso III (w' = 0)
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
MÉTODO DE LAS DOS FASES: CASO III (El óptimo valor de w' =
0 , y por lo menos una variable artificial está en la base óptima de
la Fase I.)
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
BIBLIOGRAFIA
 Prawda Witenberg J. “Métodos y Modelos de Investigación de 
Operaciones – Vol. 1 Modelos Determinísticos”. Editorial Limusa. 
©1999
 Taha Hamdy A. “Investigación de Operaciones”. Editorial Alfa 
Omega. ©1998
 Winston Wayne L.. “Investigación de Operaciones. Editorial. 
Grupo Editorial Iberoamericana. ©2005
 Hillier Frederick S. “Introducción a la Investigación de 
Operaciones. Editorial. Mc Graw Hill. ©2001
 Eppen G.D. “Investigacion de Operaciones En la Ciencia 
Administrativa. Editorial Prentice. ©2000
 Mathur-Solow – Investigación de Operaciones – Ed. Prentice Hall 
1996.
 MARIN, Isidoro. “Investigación Operativa”. UBA. Centro de 
Estudiantes Universidad Nacional de Buenos Aires. © 1970
Ing. Carlos Martin
Preguntas
Ing. Carlos Martin
Investigación
Operativa
Muchas Gracias
Profesor: Ing. Carlos A. Martin
E-mail: ing_carlos_martin@hotmail.com
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR