INVESTIGACION DE OPERACIONES METODO SIMPLEX

DANIELA FAJARDO LONDOÑO
ELIANA YISELA ARANGO ORTIZ

El método del simplex fue
creado en 1947 por el
matemático
George
Dantzig .El método del
simplex se utiliza, sobre
todo,
para
resolver
problemas de programación
lineal en los que intervienen
tres
o
más
variables.

El método Simplex es un método secuencial de
optimización, es un procedimiento iterativo que
permite ir mejorando la solución acada paso.
El proceso concluye cuando no es posible
seguir mejorando más dicha solución.

Aunque es una forma muy larga y tediosa para la solución de
un problema, esta muestra paso a paso todo el procedimiento
y nos ayuda a  entender la lógica de los algoritmos
Forma tabular del método simplex.
En este método solo se muestran o se incluyen los datos
necesarios como los coeficientes de lasvariables, los valores
del lado derecho de las ecuaciones, y las variables básicas; en
este método se hace las operaciones necesarias para que la
primera fila quede sin nueros negativos y para hacer que la
tabla quede en forma gaussiana. Para esto existen dos
métodos; el método de la “M”  o el método de fases.

EJEMPLO
Se explicara siguiendo el ejemplo de la W. Glass.
Paso inicial: Se eligen comovariables no básicas a x1 y x2, por lo tanto
se igualan a cero.
El sistema de ecuaciones es:
(1) x1 +x3 = 4
(2) 2x2 +x4 = 12
(3) 3x1
+2x2
+x5 = 18
con x1 = 0 y x2 = 0, de esta manera x3 = 4, x4 = 12, x5 = 18
(corresponde a la BF inicial).
Prueba de optimalidad: la función objetivo es Z = 3x1
+5x2, de manera que Z = 0 para la BF inicial. No es optima porque al
aumentar el valor de cualquier variable nobásica (x1 o x2), el valor de Z
aumenta.

Iteración 1: determinación de la dirección de movimiento (paso 1 de
una iteración): Se
debe elegir entre las variables no básicas, cual debe aumentar su valor.
Como la función
objetivo es Z = 3x1+5x2, la tasa de mejoramiento de x2, es mayor, por
lo que se elige a esta para aumentar su valor. Se la denomina variable
básica entrante.
Iteración 1:Determinación de donde detenerse (paso 2): esto nos dice
cuanto aumentar
la variable básica entrante x2 antes de detenerse
(1) x1
+x3
=4
(2)
2x2 +x4
= 12
(3)3x1+2x2
+x5 = 18
Con
x1 = 0
x3 = 4
x4 = 12 - 2x2
x5 = 18 - 2x2

lo que buscamos es cuanto puede crecer x2 sin violar restricciones
de no negatividad, así:
x3 = 4 ≥ 0
x4 = 12 - 2x2 ≥ 0
x5 = 18 - 2x2 ≥ 0

no hay cota superior sobre x2
x2≤ 12/2 = 6 (cocientemínimo)
x2≤ 18/2 = 9

Iteración 1: Solución (paso3)
El propósito de este paso es convertir el sistema de ecuaciones a
una forma más
conveniente para llevar a cabo la prueba de optimalidad. El
sistema de ecuaciones que
tenemos es:
(0) Z - 3x1- 5x2
=0
(1)
x1
+x3
=4
(2)
2x2 +x4
= 12
(3) 3x1 +2x2
+x5 = 18

(2*) x2 +1/2 x4 = 6

Consiste en agregar una “M” a cada variable artificial que se
agregapor las restricciones de igualdad; la “M” representa u
valor muy grande.
≤ se agrega una variable de holgura para convertirla en
igualdad.
≥ se agrega una variable superávit para convertirla en igualdad,
además de esta variable, requiere una variable artificial.
= se le agrega una variable artificial ( )

EJERCICIO
1. Pasar a la forma Estándar el Modelo Matemático
2. Agregar variable artificialdonde no hay variable de holgura
3.Penalizar las variables artificiales en la función objetivo asignando coeficiente
positivo muy grande "M" (minimizar = +M, maximizar= -M)
4.Quitar las "m" de la columna artificial, ya teniendo solución inicial
5.Se aplica el Método Simplex
Maximizar z= 3x1 + 5x2
x1 ≤ 4
2x2 ≤ 12
3x1+2x2=18
x1, x2 ≥ 0
*La función objetivo se debe penalizar con -M, por ser maximizacióny para
hacer z=0 por lo tanto:
z= 3x1 + 5x2 -M, entonces: z-3x1-5x2+M= 0
x1 + H1 = 4
2x2 +H2 = 12
3x1 + 2x2 + A1 = 18

El método simplex origina revisado consiste en darle tratamiento
matricial al método simplex original.
El método simplex revisado utiliza únicamente:
 Los coeficientes de las variables no básicas en el renglón (0).
Los coeficientes de la variable básica entrante en las...