INVESTIGACIÓN DE OPERACIONES: UNIDAD 3

UNIDAD 3: MÉTODO SIMPLEX

3.1 SOLUCIÓN GRAFICA

3.2 SOLUCIÓN TABULAR

3.3 VARIABLES DE HOLGURA Y ARTIFICIAL

EL MÉTODO SIMPLEX: Transición del método grafico al método Simplex

Como ya vimos el método gráfico indica que la solución óptima, de un programa lineal, siempre está asociada a un punto esquina del espacio de soluciones factibles. Este resultado es la clave del Método Simplex algebraico, y en general para resolver cualquier modelo de programación lineal.

La transición de la solución del punto esquina geométrico, hasta el método simplex, implica un procedimiento de computo que determina en forma algebraica los puntos esquinas. Esto se logra convirtiendo primero a todas las restricciones del modelo, de desigualdades a ecuaciones (el modelo en forma estándar), para luego manipular esas ecuaciones en forma sistemática.

Una propiedad general del método Simplex es que resuelve la programación lineal en iteraciones. Cada iteración desplaza la solución a un nuevo punto esquina, que tiene potencial de mejorar el valor de la función objetivo. El proceso termina cuando ya no se pueden tener mejoras. El método simplex implica cálculos voluminosos y tediosos, lo que hace que la computadora sea una herramienta esencial para resolver los problemas de programación lineal. Por consiguiente las reglas computacionales del método simplex se adaptan para facilitar el cálculo.

Transición de la solución gráfica a la solución algebraica.

Las ideas contenidas en la solución gráfica, de un modelo de programación lineal, son la base para desarrollar el método algebraico simplex. El siguiente esquema muestra el paralelismo entre los dos métodos.

Método Grafico

Método Algebraico.

1. Se grafíca todas las restricciones, incluyendo las de no negatividad.

2. El espacio de soluciones consiste en una infinidad de puntos factibles.

3. Identifica puntos factibles de esquina del espacio de soluciones.

4. Los candidatos a la solución óptima corresponden a una cantidad finita de puntos de esquina.

5. Se usa la función objetivo para determinar el punto esquina óptimo entre todos los candidatos.

1. Se representa el espacio de soluciones con m ecuación y n variables, y restringe a todas las variables a valores no negativos; m≤n. (forma estándar del modelo)

2. El sistema tiene infinidad de soluciones factibles.

3. Determina las soluciones básicas factibles de las ecuaciones.

4. Los candidatos a solución óptima corresponden a una cantidad finita de soluciones básicas factibles.

5. Se usa la función objetivo para determinar la solución básica factible óptima, entre todas las candidatas.

En el método gráfico, el espacio de soluciones se delimita con los ¨semis-espacios¨ que representan las restricciones y en el método simplex, el espacio de soluciones se representa con m ecuaciones lineales simultaneas y n variables no negativas.

En la representación algebraica, la cantidad m de ecuaciones siempre es menor, o igual a la cantidad de variables n.

Si m = n y las ecuaciones son consistentes, el sistema solo tiene una solución (Solución Única); pero si m<n (esto representa la mayor parte de los programas lineales), entonces el sistema de ecuaciones producirá una infinidad de soluciones.

Ya establecimos como se representa el espacio de soluciones de un programa lineal, en forma algebraica, entonces, las candidatas para la solución óptima, que son los puntos esquinas, se determinan con las ecuaciones lineales simultáneas como sigue:

En un conjunto de mxn ecuaciones, m<n se iguala a cero n-m variables, y a continuación se despejan las n variables restantes, de las m ecuaciones; la solución resultante, si es única, debe corresponder a un punto esquina del espacio de soluciones. En el siguiente ejemplo desarrollaremos el procedimiento.

Ejemplo:

Se tiene el siguiente programa lineal con dos variables:

Maximizar: X₀= 2X₁+ 3X₂

Sujeto a:

2X₁+ X₂≤ 4

X₁+ 2X₂≤ 5

X₁ y X₂≥ 0

Algebraicamente el espacio de soluciones de la programación lineal se representa como:

Maximizar: X₀ = 2X₁+ 3X₂

Sujeto a:

2X₁+ X₂+ S₁= 4

X₁+ 2X₂+ S₂= 5

X₁, X₂, S₁ y S₂≥0 (Modelo en forma estándar)

Su solución gráfica es:

El sistema tiene m=2 ecuaciones y n=4 variables. Así, según la regla que establecimos antes, se puede determinar algebraicamente los puntos esquina, igualando a cero n-m variables y resolviendo las ecuaciones para determinar las m=2 variables restantes.

n-m = 4 – 2 = 2; (2 variables igualadas a cero).

Por ejemplo:

Si X₁= 0 y X₂= 0 (Punto A), el sistema produce la solución:

2X_{1 +} X2+ S₁ = 4 S₁= 4

X₁+ 2X₂+ S₂= 5 S₂=5

Otro punto es: S₁ = 0 y S₂= 0 (punto C), el sistema produce la solución:

Como: 2X1+ X₂+ S₁ = 4 y X₁+ 2X₂+ S₂= 5

Entonces: 2X₁+ X₂= 4 ec. 1 y X₁+ 2X_{2 =} 5 ec. 2

Multiplicamos la ecuación 1 por -2 y la sumamos con la ecuación 2:

-4X₁- 2X₂= -8

X₁+ 2X₂= 5

-3X₁ = -3; entonces: X1 = -3/-3 = 1; X₁ = 1

Ahora sustituimos X₁ = 1 en cualquiera de las dos ecuaciones y obtenemos el valor de X₂: (1)+ 2X_{2 =} 5 ; 2X₂ = 5-1; 2X₂ = 4; X₂ = 4/2; X₂ = 2

Si evaluamos la función objetivo tenemos: X₀ = 2(1)+ 3(2) = 8; X₀ = 8

De la misma forma se procede con los 4 puntos esquina restantes.

Establecer cuáles son la n-m variables que se deberán igualar a cero, para obtener determinado punto esquina sin el método gráfico, es sumamente difícil.

Sin embargo esto no impide que se enumeren todos los puntos esquinas del espacio de soluciones. Solo hay que tener en cuenta todas las combinaciones posibles, en las que n-m variable se igualan a cero, y resolver las ecuaciones resultantes. Una vez resueltos los sistemas resultantes, para cada punto esquina, la solución óptima es el punto esquina factible algebraico que produce el mejor valor objetivo.

En el ejemplo que estamos analizando tenemos el combinatorio:

C⁴₂= 4! = 4! = 4x3x2! = 6

2! (4-2) 2! 2! 2! 2!

Que indica que son seis combinaciones de dos variables no básicas (iguales a cero) estas corresponden a los puntos esquina geométricos A, B, C, D, E, F.

Al examinar la gráfica podemos localizar los que se pudieran llamar puntos esquina, “autenticas” que son A, B, C y D (que se encuentran en el área de soluciones factibles). Sin embargo E y F también son puntos esquina, pero son no factibles.

Para hacer una transición completa, hacia la solución algebraica necesitamos indicar los puntos esquina por sus nombres algebraicos. En forma específica la n-m variable que se igualan a cero se llaman variables no básicas.

Si las m variables restantes tienen una solución única, se llaman variables básicas, y su solución (al resolver las m ecuaciones) se llama solución básica.

El Método Simplex: Calculo del Algoritmo Simplex.

Como ya dijimos, el método simplex usa un procedimiento inteligente de búsqueda, diseñado para llegar al punto esquina óptimo en forma eficiente. El algoritmo simplex aumenta el valor de las variables una por una, hasta llegar al punto óptimo. El método Simplex proporciona una regla definida, para determinar que variable aumentar, esto para facilitar el desarrollo de un programa de computo.

En forma específica como se está maximizando, la variable no básica que tenga el coeficiente positivo más grande, en la función objetivo, es la que se selecciona para aumentar primero.

Téngase en cuenta que solo se trata de una regla fácil que, de acuerdo con la experiencia, generalmente conduce a la menor cantidad de iteraciones. En la terminología del método Simplex X₁y S₁en el punto A se llama variable de entrada y de salida respectivamente.

Detalles de cálculo del algoritmo Simplex.

Los detalles de cálculo de una iteración Simplex, que incluye las reglas para determinar las variables de entrada y de salida, así como para determinar los cálculos cuando se llega a la solución óptima, los veremos utilizando el modelo de Comex, ya conocido.

En la forma estándar (de ecuaciones) el modelo Comex se representa así:

Maximizar: Z = 5 X₁+ 4 X₂+ 0S₁+ 0S₂+0S₃+ 0S₄

Sujeto a: 6 X₁+ 4 X₂+ S₁ = 24

X₁+ 2 X₂ +S₂ = 6

- X₁+ X₂ +S₃= 1

X₂ +S₄= 2

X₁, X_2, S_1, S_2, S₃ y S₄≥0

Ya sabemos que S_1, S_2, S₃ y S₄ representa las holguras asociadas a las restricciones respectivas. Luego expresaremos la función objetivo así:

Z - 5X₁– 4X₂ + 0S₁+ 0S₂+0S₃+ 0S₄= 0

De esta forma la tabla inicial del Simplex se expresa así:

Tabla 1: Tabla de inicio Simplex

Básica	Z	X₁	X₂	S₁	S₂	S₃	S₄	Solución.
Z	1	-5	-4	0	0	0	0	0	Renglón Z
S₁	0	6	4	1	0	0	0	24	Renglón S₁
S₂	0	1	2	0	1	0	0	6	Renglón S₂
S₃	0	-1	1	0	0	1	0	1	Renglón S₃
S₄	0	0	1	0	0	0	1	2	Renglón S₄

Como X_{1 =}0 y X₂ = 0 (Se inicia en el origen por ser no básicas), sin más cálculos, de la tabla se determina que:

S₁= 24 S₂= 6 S₃= 1 S₄= 2 y Z = 0 ; (X_{1 =}0 y X₂ = 0)

Esta solución se muestra en la tabla con la lista de las variables básicas, en la columna básica de la izquierda, y sus valores en la columna solución de la derecha.

Esto define el punto esquina actual especificando las variables básicas y sus valores. Así como el valor de la función objetivo Z. Recuerden que las variables no básicas, las que no aparecen en la columna básica, siempre son iguales a cero.

Ya dijimos que para determinar las variables de entrada a la solución básica (para la siguiente iteración), se selecciona la variable no básica con mayor coeficiente positivo en la función Objetivo (cuando es de maximizar). Esta regla se basa en la función objetivo original Z=5X₁ + 4X₂.

Como la tabla Simplex expresa la función objetivo en la forma Z - 5X₁ - 4X₂= 0, la variable de entrada es X_1,porque tiene el coeficiente más negativo en la función objetivo (y es de maximización).

Si todos los coeficientes de la función objetivo fueran ≥ 0, no sería posible mejorar Z y eso indicaría que se habría llegado al óptimo.

Para determinar la variable de salida, en forma directa con la tabla, se calculan las iteraciones, o coordenadas (X₁) al origen, de todas las restricciones con la dirección no negativa del eje X₁(por ser X₁ la variable de entrada). Esas iteraciones son las razones del lado derecho de las ecuaciones (columna solución), entre los coeficientes de las restricciones correspondientes, abajo de la variable de entrada X₁,como se muestra en la siguiente tabla:

Tabla 2: Definición de Variable de Salida

Básicas	Entrada X₁	Solución	Razón o iteración
S₁	6	24	X₁= 24/6 = 4	Mínimo
S₂	1	6	X₁= 6/1 = 6
S₃	-1	1	X₁= 1/-1 = -1	Ignorar.
S₄	0	2	X₁= 2/0 =∞ (indefinido)	Ignorar.

La razón no negativa mínima corresponde a S₁ básica, lo que indica que es la variable que tiene que salir (variable de salida). Esto indica que tomara el valor de cero, en la nueva iteración.

El valor de la variable de entrada X₁en la nueva solución (iteración) es igual a la razón mínima: X₁= 4 (compárelo con el punto B de la gráfica). El aumento correspondiente a Z es $5 x 4 = $20.00.

El resultado del intercambio de variables de entrada y de salida es que el nuevo punto se define así:

Variable no básicas (= 0), (S_1, X₂) ; Variables básicas (X₁, S₂, S_3,S₄)

Ahora se deben manipular las ecuaciones de la última tabla, de modo que la columna básica y la columna solución identifiquen la nueva solución. El proceso se llama operaciones de renglón (o fila) de Gauss – Jordan.

Nuevamente veamos la tabla de inicio y asociémosla a la columna Pivote y al reglón Pivote con las variables de entrada y de salida respectivamente. A la intercesión de la columna Pivote y el renglón Pivote se le llama Pivote o elemento Pivote.

Entra Tabla 3: Renglón Pivote, Columna Pivote y Elemento Pivote

Básica	Z	X₁	X₂	S₁	S₂	S₃	S₄	Solución
Z	1	-5	-4	0	0	0	0	0
S₁	0	6	4	1	0	0	0	24	Renglón Pivote
S₂	0	1	2	0	1	0	0	6
S₃	0	-1	1	0	0	1	0	1
S₄	0	0	1	0	0	0	1	2
		Columna Pivote	Elemento Pivote.

Para nuestra nueva tabla Simplex, y como producto de los cálculos con Gauss y Jordan tenemos que:

1. Renglón Pivote:

Nuevo renglón Pivote= Renglón Pivote Actual / Elemento Pivote.

2. Todos los demás renglones (incluyendo Z)

Nuevo Renglón: Renglón Actual – (su coeficiente en la columna Pivote)(Renglón Pivote Nuevo).

Tabla 4: Primera iteración

Básica	Z	X₁	X₂	S₁	S₂	S₃	S₄	Solución
Z	1	0	-2/3	5/6	0	0	0	20
X₁	0	1	2/3	1/6	0	0	0	4
S₂	0	0	4/3	-1/6	1	0	0	2
S₃	0	0	5/3	1/6	0	1	0	5
S₄	0	0	1	0	0	0	1	2

Puede notarse que la nueva tabla presenta las mismas características de la tabla anterior, por lo tanto, la nueva columna solución muestra la solución, para cada una de las variables básicas (Columnas básicas).

Entonces: X₁ = 4; S₂= 2; S₃ = 5 y S₄= 2. El Nuevo valor objetivo es: Z= 20

Z = 5(4)+ 4(0)+ 0(0)+ 0(2)+0(5)+ 0(2) = 20

Este acontecimiento de la tabla es producto de las operaciones de fila (renglón) de Gauss y Jordán.

En base a la última tabla, vamos a definir las nuevas variables de entrada y salida.

Como: Z= 2/3 X₂– 5/6 S₁ + 20 o (Z- 2/3 X₂+ 5/6 S₁= 20)

Entra Columna Pivote.

Básica

X₁

X₂

S₁

S₂

S₃

S₄

Solución

-2/3

5/6

X₁

2/3

1/6

Renglón Pivote.

S₂

4/3

-1/6

S₃

5/3

1/6

S₄

Elemento Pivote.

Entonces: La nueva variable de entrada es: X₂.Ahora para la variable de salida, generamos la tabla de razones (intersecciones):

Tabla 5: Definición de Variable de Salida

Básicas	Entrada X₂	Solución	Razón o iteración
X₁	2/3	4	X₂= 4 / (2/3) = 6
S₂	4/3	2	X₂= 2 / (4/3) = 3/2	Mínimo
S₃	5/3	5	X₂= 5 / (5/3) = 3
S₄	1	2	X₂= 2 / 1 = 2

La variable de salida es S₂, y nuestra nueva tabla simplex, queda así:

Tabla 6: Segunda Iteración/Solución óptima

Básica	Z	X₁	X₂	S₁	S₂	S₃	S₄	Solución
Z	1	0	0	3/4	1/2	0	0	21
X₁	0	1	0	1/4	-1/2	0	0	3
X₂	0	0	1	-1/8	3/4	0	0	3/2
S₃	0	0	0	3/8	-5/4	1	0	5/2
S₄	0	0	0	1/8	-3/4	0	1	1/2

Como ninguno de los coeficientes del renglón, son negativos, esta última tabla es Óptima.

De la última tabla concluimos que:

X₁ = 3 Hay que producir 3 toneladas diarias de Pintura externa.

X₂=3/2 Hay que producir 1.5 toneladas diarias de Pintura interna.

Z= 21 La utilidad diaria es de $21,000.00

Los valores de S₁ y S₂ es Cero y S₃=5/2 y S₄= ½

La tabla Simplex muestra una gran cantidad de información adicional que comprende:

1. El estado de los recursos.

2. El valor por unidad de los recursos (precios duales).

3. Todos los datos necesarios para efectuar un análisis de sensibilidad.

Estado de los recursos: un recurso se llama escaso si las actividades (variables) del modelo la usan por completo, en caso contrario se dice que es abundante. Esta información se obtiene en la tabla óptima, revisando el valor de la variable de holgura asociada con la restricción que representa al recurso. Si la variable de holgura es cero, el recurso se usa por completo, y el recurso es escaso. Una holgura positiva indica que el recurso es abundante.

Si revisamos la tabla óptima del ejemplo Comex, tenemos:

Recursos	Variables de Holgura	Estado o condición
Mat. Prima M1	S₁ =0	Escasa.
Mat. Prima M2	S₂= 0	Escasa.
Límite de Demanda 1	S₃ =5/2	Abundante.
Límite de Demanda 2	S₄ = ½	Abundante.

Tabla 7: Estado de los Recursos

El estado de los recursos indica que está garantizado un aumento en la disponibilidad de las materias primas M1 y M2, porque las dos son escasas. La cantidad del aumento se establece mediante el análisis de sensibilidad que veremos más adelante.

En una minimización la selección de la variable de salida es igual que en el caso de maximización. Para la variable de entrada, en el caso de minimización, se selecciona la variable no básica con el coeficiente más positivo de la función objetivo (renglón Z) y se llega de Z mínimo (Optimo) cuando todos los coeficientes del renglón Z son no positivos.

Las reglas para definir las variables de entrada y de salida se llaman condiciones de Optimalidad y de Factibilidad.

Resumen del Método Simplex:

Hasta ahora nos hemos ocupado en maximización. El problema de minimización, la condición de Optimalidad requiere seleccionar la variable de entrada, como la variable no básica, con el coeficiente objetivo, más positivo en la ecuación objetivo (renglón Z), la regla es aptamente opuesta al caso de maximización. En cuanto a la condición de factibilidad para seleccionar la variable de salida la regla no cambia.

Condición de Optimalidad.

La variable de entrada en un problema de maximización (o minimización), es la variable no básica con el coeficiente más negativo (positivo), en el renglón Z los vínculos se rompen arbitrariamente. El óptimo se alcanza en la iteración en la cual los coeficientes, en el renglón Z son no negativos (o no positivos).

Condición de Factibilidad:

Tanto en problema de maximización y minimización la variable de salida, es la variable básica, asociada con la razón mínima no negativa con el denominador estrictamente positivo. Los vínculos se rompen arbitrariamente (dos razones mínimas iguales).

Los pasos del Método Simplex son:

1. Determine la solución factible básica inicial.

2. Seleccione una variable de entrada, utilizando la condición de Optimalidad. Deténgase si no hay variable de entrada. La última condición es óptima. De otro modo prosiga con el paso 3.

3. Seleccione una variable de salida utilizando una condición de factibilidad.

4. Aplique los pasos de Gauss – Jordán, para determinar la solución básica y vaya al paso 2

MÉTODO M: Solución Artificial de Inicio.

Como puede observarse el Método Simplex lo hemos utilizado en un modelo de programación lineal donde todas las restricciones son de la forma ≤, con el lado derecho no negativo. Esto ofrece una cómoda solución básica factible de inicio con todas las holguras. Los modelos donde hay restricciones del tipo ≥ o = no ofrece esta solución básica de inicio. A estos modelos se les llama programas lineales de mal comportamiento.

El procedimiento para iniciar la resolución de estos programas lineales (con restricciones ≥ e =) permite que variables artificiales desempeñen el trabajo de holguras, en la primera iteración, para después en alguna iteración posterior, desecharla de forma legítima. Para ello se puede hacer uso de dos métodos muy relacionados entre sí, el método M y el método de dos fases.

El Método M o Método de Penalización:

Comienza con la programación lineal en forma de ecuación (forma estándar).

Una ecuación i, que no tenga una holgura positiva, se aumenta con una variable artificial R_i, para formar una solución de inicio parecida a la solución básica con todas las holguras. Sin embargo como las variables artificiales son ajenas al modelo de programación lineal, se usa un mecanismo de retroalimentación en el que el proceso de optimización trata de forma automática de hacer que esas variables tengan nivel cero.

Esto significa que al final, la solución será como si las variables artificiales nunca hubiesen existido. El resultado deseado, se obtiene penalizando las variables artificiales en la función objetivo.

Dado M, un valor positivo suficientemente grande, (matemáticamente M ∞) el coeficiente objetivo de una variable artificial, representa una penalización adecuada si:

Coeficiente Objetivo de la variable artificial

Al usar esta penalización, el proceso de optimización forzara en forma automática a las variables artificiales para que sean cero (siempre que el problema tenga una solución factible)

Ejemplo:

Minimizar: X0 = 4X₁ + X₂

Sujeto a: 3X₁ + X₂= 3

4X₁ + 3X₂ ≥ 6

X₁+ 2X₂≤ 4

X₁y X₂≥ 0

Modelo en forma Estándar:

Minimizar: X0 = 4X₁ + X₂

Sujeto a: 3X₁ + X₂= 3

4X₁ + 3X₂ - S₁ = 6

X₁+ 2X₂+S₂= 4

X_1,X_2,S₁y S₂≥ 0

Debido a que existen restricciones ≥ e =, el modelo se transforma en:

Minimizar: X0 = 4X₁ + X₂+ MR₁+ MR₂

Sujeto a: 3X₁ + X₂+ R₁= 3

4X₁ + 3X₂ – S₁ + R₂= 6

X₁+ 2X₂+ S₂ = 4

X_1,X_2,S_1,S_2,R₁y R₂≥ 0

Como m= 3 ecuaciones y n= 6 variables;

Entonces: n-m = 6-3 = 3 variables no básicas.

X0 = 4X₁ + X₂+ MR₁+ MR₂ se transforma en: X0 - 4X₁ - X₂- MR₁- MR₂= 0

Y se tiene la tabla:

Tabla 1: Tabla de inicio (no simplex)

Básicas	X₁	X₂	S₁	R₁	R₂	S₂	Solución
X0	-4	-1	0	-M	-M	0	0
R₁	3	1	0	1	0	0	3
R₂	4	3	-1	0	1	0	6
S₂	1	2	0	0	0	1	4

Debido a que esta solución presenta inconsistencia en la columna solución con el renglón z, (X0 = 4X₁ + X₂+ MR₁+ MR₂ X0 = 4(0)+ (0)+ M(3)+ M(6) = 9M) deberá transformarse el renglón z, haciendo uso de la fórmula:

Nuevo Renglón X0= Renglón anterior X0 + (M_X Renglón R₁+ M_X Renglón R₂)

Entra

Tabla 2: Tabla de inicio simplex

Básicas	X₁	X₂	S₁	R₁	R₂	S₂	Solución
X0	(-4 + 7M)	(-1 + 4M)	-M	0	0	0	9M
R₁	3	1	0	1	0	0	3
R₂	4	3	-1	0	1	0	6
S₂	1	2	0	0	0	1	4

Solución básica:

R₁ = 3 ; R₂ = 6 ; S₂ = 4 ; X₁ = 0 ; X₂ = 0 y S₁= 0 ; con Z = 9M

Variable de salida:

Tabla 3: Definición de Variable de Salida

Básicas	V. Entrada X₁	Solución	Razón o iteración
R₁	3	3	X₁ = 3/3 = 1	Mínimo
R₂	4	6	X₁ = 6/4 = 3/2
S₂	1	4	X₁ = 4/1 = 4

Entra X₁y Sale R₁Elemento Pivote = 3

Entra

Tabla 4: Segunda iteración

Básicas	X₁	X₂	S₁	R₁	R₂	S₂	Solución
X0	0	(1+5M)/3	-M	(4-7M)/3	0	0	(4+2M)
X₁	1	1/3	0	1/3	0	0	1
R₂	0	5/3	-1	-4/3	1	0	2
S₂	0	5/3	0	-1/3	0	1	3

Solución básica:

X₁ = 1 ; R₂ = 2 ; S₂ = 3 ; R₁ = 0 ; X₂ = 0 y S₁= 0 ; con Z = 4+2M

Variable de salida:

Tabla 5: Definición de Variable de Salida

Básicas	V. Entrada X₂	Solución	Razón o iteración
X₁	1/3	1	X₂ = 1/(1/3) = 3
R₂	5/3	2	X₂ =2/(5/3) = 6/5	Mínimo
S₂	5/3	3	X₂ =3/(5/3) = 9/5

Entra

Tabla 6: Tercera iteración

Básicas	X₁	X₂	S₁	R₁	R₂	S₂	Solución
X0	0	0	1/5	(8/5) - M	(-1/5) - M	0	18/5
X₁	1	0	1/5	3/5	-1/5	0	3/5
X₂	0	1	-3/5	-4/5	3/5	0	6/5
S₂	0	0	1	1	-1	1	1

Solución básica:

X₁ = 3/5 ; X₂ = 6/5 ; S₂ = 1 ; R₁ = 0 ; R₂ = 0 y S₁= 0 ; con Z = 18/5

Variable de salida:

Tabla 7: Definición de Variable de Salida

Básicas	V. Entrada S₁	Solución	Razón o iteración
X₁	1/5	3/5	S₁ = (3/5)/(1/5) = 3
X₂	-3/5	6/5	S₁ =(-3/5)/(6/5) = -1/2	Ignorar
S₂	1	1	S₁ =1/1 = 1	Mínimo

Tabla 8: Cuarta iteración (Tabla Óptima)

Básicas	X₁	X₂	S₁	R₁	R₂	S₂	Solución
X0	0	0	0	(7/5) - M	- M	-1/5	17/5
X₁	1	0	0	2/5	0	-1/5	2/5
X₂	0	1	0	-1/5	0	3/5	9/5
S₁	0	0	1	1	-1	1	1

Solución Óptima: X₁ = 2/5 ; X₂ = 9/5 ; S₁ = 1 ; R₁ = 0 ; R₂ = 0 y S₂= 0

Con X0 _óptimo= 17/5

Observe que las variables artificiales R₁ y R₂ salen de la solución básica en las iteraciones primera y segunda. Esto resulta consistente con el concepto de penalizar las variables artificiales en la función objetivo.

Acerca del método M se puede hacer dos observaciones:

1. El uso de la penalización M podrá no forzar la variable artificial hasta el nivel cero en la iteración Simplex final, si el problema de programación lineal no tiene una solución factible (es decir, si las restricciones no son consistentes). En este caso, la iteración simplex final incluirá cuando menos una variable artificial a un nivel positivo.

2. La aplicación de la técnica M implica, teóricamente, que M ∞. Sin embargo, al usar la computadora M debe ser finito pero suficientemente grande. ¿Qué tan grande es ¨suficientemente grande¨? Es una pregunta abierta.

En forma específica, 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 simplex, al manipular una mezcla de números muy grandes o muy pequeños.

UNIDAD 3

No hay comentarios:

Publicar un comentario

HISTORIA

Denunciar abuso