Metodo SIMPLEX por minimizaciòn

Minimizar Z= 3m + 4n - 8ñ

3m – 4n ≤ 12
M + 2n + ñ ≥ 4
4m – 2n +5ñ ≤ 20

M ≥ 0, n ≥ 0, ñ ≥ 0

Como es un problema de minimización recordemos que tenemos que maximizar la función objetivo quedando así

-3m – 4n + 8ñ + Z = 0

Las inecuaciones las hacemos igualdades

3m – 4n = 12
m + 2n + ñ = 4
4m – 2n +5ñ = 20

Ahora tenemos que hacer nuestra tabla 1 y aplicaremos el mismo procedimiento del método SIMPLEX para maximizarlo


Ahora de la tabla tomaremos el MAYOR POSITIVO en este caso es el 8 y ya encontramos nuestra columna pivote.

Posteriormente dividimos 28/5 = 4 4/1 = 4 12/0 = 0, y tenemos que tomar el numero menor de estas divisiones en este caso tenemos dos, cuatros podemos tomar cualquiera

Y ya encontramos nuestro pivote operacional en este caso es 1, ahora tenemos que dividir toda esa fila entre este 1 para poder resolver la siguiente tabla



Ahora la ñ ya paso a la base

El problema se termina aquí porque ya nos quedaron puros negativos y ceros en nuestra PO que era nuestro objetivo

3m – 4n ≤ 12
3(0) – 4 (0) ≤ 12
0 ≤ 12 Si cumple

m + 2n + ñ ≥ 4
0 + 2(0) + ¼ ≥ 4
¼ ≥ 4 No cumple

4m – 2n + 5ñ ≤ 20
4 (0) – 2 (0) + 5 (1/4) ≤ 20
1.25 ≤= 20 Si cumple

3m + 4n – 8ñ
Z = 3 (0) + 4(0) – 8 (1/4)
Z = 2

Metodo de la M

Este método empieza con la PL en la forma estándar Para cualquier ecuación i que no tiene una holgura, aumentamos una variable artificial R. Entonces esta variable se convierte en parte de la solución básica inicial. Debido a que es una variable artificial al modelo de PL se le asigna una penalidad en la función objetivo, para obligarlas aun nivel cero en una iteración del algoritmo SIMPLEX

Debido a que M es un valor positivo suficientemente grande, la variable R1 se penaliza en la función objetivo utilizando —MR, en el caso de la maximización, y +RM, en la minimización. Debido a esta penalidad El proceso de optimización lógicamente tratara de impulsar R1, al nivel cero

Minimice Z= 4X1 + X2

La forma estándar se obtiene restando un superávit X3 en la segunda restricción y añadiendo una holgura X en la tercera restricción. Por tanto obtenemos

La primera y segunda ecuación no tiene variables que desempeñen el papel de holguras. Por consiguiente, utilizamos las variables R1 y R2 en estas dos ecuaciones y las penalizamos en la función objetivo con MR1 + MR2. La PL resultante se da como


En el modelo modificado, ahora podemos utilizar R1, R2 y X4 como la solución básica factible inicial como lo demuestra la siguiente tabla simplex

Antes de proceder con los cálculos del método simplex, necesitamos hacer que el renglón -Z sea consistente con el resto de la tabla simplex. De manera específica, el valor de z asociado con la solución básica inicial R1 = 5, R2 6, y X4 = 4 debe ser 3M + 6M + O = 9M en vez de O, como se muestra en el lado derecho del renglón -Z. Esta inconsistencia se debe al hecho de que R, y R2 tienen coeficientes no cero (-M, -M) en e! renglón -Z Estas inconsistencias se eliminan sustituyendo R1 y R2 en el renglón -Z, utilizando las ecuaciones apropiadas de restricción.

En particular, observe los elementos “1” realzados en el renglón -R1 y en el renglón -R2. Multiplicando cada uno de los renglones –R1 y de los renglones -R2 por M y añadiendo la suma al renglón -Z, efectivamente se sustituirá a R1 y R2 en el renglón objetivo. Podemos resumir este paso como

Nuevo renglón Z= Antiguo renglón Z + M x (Renglón R1) + M x (Renglón R2)
Esto se aplica como

Por lo tanto la nueva tabla simplex se convierte en

2 TABLAS



La solución óptima es:

X1= 2/5; X2= 9/5; X3= 13/5; Z = 17/5

Gauss-Jordan

Con el método Gauss-Jordan se efectúa un cimblo de base empleando raciones de cálculo:
1. Ecuación pivote:
nueva ecuación pivote = ecuación pivote ÷ elemento pivote

2. Las demás ecuaciones, incluyendo Z
nueva ecuación = (ecuación anterior)+ Coeficiente de la columna entrante *nueva ecuación pivote

Estos dos tipos de operaciones de cálculo necesariamente generan la nueva solución básica, al sustituir la variable entrante en todos los renglones, excepto en la ecuación pivote.

Al aplicar los cálculos del tipo 1 a a tabla anterior, dividimos la ecuación .5, entre el elemento pivote 2. Como x toma el lugar de y, en la columna básica, los cálculos del tipo 1 cambiarán la tabla inicial como se muestra a continuación.

Nótese que la columna “solucíón” da el nuevo valor de x5 (= 4), que es igual a la razón mínima de la condición de factibilidad.
Para completar la tabla, realizamos los siguientes cálculos de tipo 2.

Las siguientes operaciones de Gauss-jordan producirán la nueva tabla:
(i) Nueva ecuación pivote (s,) = ecuación s1 anterior ÷ (3/2).
(u) Nueva ecuación z = ecuación z anterior — (—1/2) y nueva ecuación pivote.
(iii) Nueva ec. - cc. x anterior — (1/2) y nueva ec. pivote.
(iv) Nueva cc. .y = cc s anterior — (3/2) y nueva cc. pivote.
(y) Nueva cc. s4 = cc. s anterior — (1) y nueva ec. pivote.

La solución da como resultado x6 34 y x, 14 (punto Gen la figura 3-2). El valor de ¿ha aumentado de 12 en la tabla anterior a 124. El incremento (124 — 12) = 2/3 es el resultado de que x1 aumente de 0 a 4/3, donde cada incremento de una unidad contribuye en 1/2 a la función objetivo. Por lo tanto, el incremento total en a es igual a (4/3) x (t/2) = 2/3.
La última tabla es óptima porque ninguna de tas variables no básicas tiene un coeficiente negativo en la función z. Esto completa tos cálculos del método símplex.

Metodo SIMPLEX primal

El método símplex primal parte de una solución básica factible (punto extremo) y se continúa iterando a través de soluciones básicas factibles sucesivas hasta alcanzar el óptimo. La figura 3-1 ilustra la aplicación de este proceso al modelo Reddy Mikks. El proceso comienza en el origen extremo (punto A) y se mueve a lo largo del borde AB del espacio de soluciones hasta el punto extremo adyacente B (iteración 1). De 5B se mueve a lo largo del borde BC hasta el punto extremo adyacente C (iteración
2), que es el óptimo. Obsérvese que el procedimiento no es capaz de cortar a través del espacio de soluciones (por ejemplo, de A a C) sino que siempre debe moverse a lo largo de bordes entre puntos extremos adyacentes.

¿Cómo se expresa algebraicamente el procedimiento iterativo indicado antes? Todo foque tenemos que hacer es mostrar cómo se identifican los puntos extremos, tales como el A, B y C, sin utilizar la gráfica de] espacio de soluciones. Consideremos el modelo Reddy Mikks dado enseguida en su forma estándar:
Maximizar Z= 3x5 + 2x1 + Os3 + 0.s + Os, + 054

sujeto a

El modelo tiene m = 4 ecuaciones y n = 6 variables. De esta manera, el número de variables no básicas (nulas) debe ser igual a 6 — 4 = 2. Si escogemos e, O y x, = O como las variables no básicas, inmediatamente, y sin ningún cálculo, obtenemos la solución básica factibles1 = 6, .s5 = 8, s3 = 1 54 = 2 (el punto origen A en la figura 3-1). Esta solución básica representa la solución inicial (o iteración) del método símplex. El valor objetivo correspondiente se determina expresando la función objetivo en la siguiente forma (a la que nos referiremos como la ecuación z):
8 — 3X — 2.r1 = O

Puesto que x5 y x1 en A son cero, el valor asociado de z lo da automáticamente el segundo miembro de la ecuación anterior (= O). La fácil determinación algebraica de la solución básica inicial en el modelo Reddy Mikks se debe a que:
1. Cada ecuación tiene una variable de holgura.
2. Los segundos miembros de las restricciones son no negativos.

La primera propiedad garantiza que el número de holguras es igual al número de ecuaciones. Así, las variables restantes pueden usarse como variables no básicas (cero). Como por la segunda propiedad los segundos miembros de las ecuaciones son no negativos, la solución básica resultante es automáticamente factible, como se necesita en el método simplex primal.

El siguiente paso lógico a la identificación de la solución inicial, es investigar el desplazamiento a una nueva solución básica. Desde el punto de vista de la optimización, nos interesa pasar a otra solución básica, sólo si podemos discernir mejoras en el valor de la función objetivo. Primero, téngase en cuenta que una nueva solución básica se asegura sólo al hacer básica, por lo menos, una de las variables actuales no básicas (cero). En el método símplex se hace el cambio de las variables no básicas, una a la vez, Intuitivamente, tal variable no básica puede llevarse a a solución sólo si mejora el valor de la función objetivo, En términos del modelo Reddy Mikks, .r y x son no básicas (= O) en A. Observando la ecuación z objetivo
z—3x—2x, O

constatamos que un incremento unitario de x aumentará a z en 3 y, un incremento unitario dex1, acrecentará a z en 2. Puesto que se trata de una maximización, cualquiera de las dos variables puede mejorar el valor objetivo. Sin embargo, para generar una regla no ambigua de cálculo, el método simplex utiliza un procedimiento heuristico; osca, en el caso de una maximización, la variable no básica seleccionada es aquella con el coeficiente más negativo en la ecuación z objetivo. Utilizando tal procedimiento heurístico, se espera (pero no se garantiza), que el método símplex produzca los ‘saltos” máximos en el valor objetivo al pasar de una iteración a otra, alcanzando así el óptimo en el menor número de iteraciones. La aplicación de esta condición al modelo Reddy Mikks da como resultado considerar a como la variable que entra, o variable entrante.

Condición de optimidad: La variable entrante en una maximización (en una minimización) es la variable no básica, con el coeficiente más negativo (más positivo) en la ecuación z objetivo. Un empate puede romperse arbitrariamente. El óptimo se alcanza cuando todos los coeficientes no básicos en a ecuación z son no negativos (no positivos).

Condición de factibilidad: tanto en problemas de maximización como de minimización, la variable saliente es la variable básica actual, con la menor intersección (razón mínima con denominador estrictamente positivo) en la dirección de la variable entrante. Un empate se rompe arbitrariamente.

Estamos listos para enunciar los pasos iterativos formales del método símplex primal:
Paso O: Usando la forma estándar (con los segundos miembros no negativos), determine una solución inicial básica factible.
Paso 1: Seleccione una variable entrante entre las variables actuales no básicas, usando la condición de optimidad.
Paso 2: Seleccione la variable saliente entre las variables actuales básicas, usando la condición de factibilidad.
Paso 3: Determine los valores de las nuevas variables básicas, haciendo a la variable entrante básica y a la variable saliente no básica. Vuelva al paso 1.

Ejemplo 3.3-1
Usaremos el modelo Reddy Mikks para explicar los detalles de cálculo del método simplex primal. Esto exigirá expresar el problema en la forma estándar Una manera conveniente de resumir las ecuaciones es por medio de la siguiente tabla:
Esta tabla corresponde a la solución básica inicial del modelo. La información en la

Tabla se lee de la siguiente manera. La columna “básica” identifica las variables básicas actuales y’, s,, y, y y4, cuyos valores se dan en la columna “solución”. Esto supone implícitamente que las variables no básicas y5 y y, (aquellas no presentes en la columna “básica”) tienen valor cero. El valor correspondiente de la función objetivo es Z = 3 x O + 2 x o + Ox 6 + Ox $ + Ox 1 + Ox 2 = O, como se muestra en la columna solución.
Al aplicar la condición de optimidad, tiene el coeficiente más negativo en la ecuación a y por ello, se escoge como la variable entrante. La condición de factibilidad muestra que .5 corresponde a la menor intersección, por lo que deberá salir de la solución.
Después de identificar las variables entrantes y salientes, necesitamos determinar la nueva solución básica que debe incluir ahora a y,, y5, y, y 54 Esto se logra aplicando el método de eliminación de Causs-1ordan. El método comienza identificando la columna debajo de la variable entrante y5 como la columna entrante o de entrada. El renglón asociado con la variable saliente se denominará ecuación pivote, y el elemento en la intersección de la columna de entrada y la ecuación pivote se denominará elemento pivote. La siguiente tabla resume estas definiciones:

Soluciones basicas

Consideremos el modelo estándar de PL con m ecuaciones y n incógnitas. Una solución básica asociada se determina haciendo n-m variables iguales a cero y luego, resolviendo las ni ecuaciones con las restantes ro variables, siempre que la solución resultante exista y sea única. Para ilustrar esto, consideremos el siguiente sistema de ecuaciones: /

2x + x2 + 4x, + x4 = 2
x1 + 2x, + 1V3 + x4 = 3

En este ejemplo tenemos ni = 2 y n = 4. Entonces, una solución básica está asociada con n — ni 4 — 2 2 variables nulas, Esto significa que el conjunto de ecuaciones dado tiene n!/Íni! (o — ni) = 4!/2!21 = 6 posibles soluciones básicas, Decimos soluciones básicas “posibles” porque algunas combinaciones pueden no conducir en absoluto a soluciones básicas. Por ejemplo, considérese la combinación donde x y x4 se hacen igual a cero. En este caso el sistema se reduce a

2x, + 4x, = 2
x1 + 2x, = 3

Las dos ecuaciones son inconsistentes y, por consiguiente, no existe una solución. 1_a conclusión es que x, y x, no pueden constituir una solución básica y por ello, no corresponden a un punto extremo.
En forma alternativa, consideremos el caso donde x3 y x4 se hacen igual a cero. Esto da las ecuaciones
2x + x, = 2
x1 + 2x, = 3


La solución única correspondiente (x 1/3, x2 4/3), junto con .r, O y x4 = O, define una solución básica y, por lo tanto, un punto extremo del espacio de soluciones de la PL.

En la PL, nos referimos a las n — m variables que se hacen iguales a cero como variables no básicas y, a las no variables restantes como variables básicas (por supuesto, siempre que exista una solución única). Se dice que una solución básica es factible si todos los valores de su solución son no negativos. Un ejemplo de este caso es la solución factible básica (x1 = 1/3, y5 = 4/3, x, O, a4 = O). Para ilustrar el caso de una solución básica infactible, consideremos la combinación donde las variables no básicas son x1 O y x3 = O. Las ecuaciones anteriores dan

4x, + x4 = 2
2x, + .v4 = 3

La solución básica correspondiente es (.r, — /2, a4 4), que es infactible porque x, es negativa.

En la resolución del problema de PL, nos interesarán las soluciones básicas, tanto factibles como infactibles. Específicamente veremos que todas las iteraciones del método símplex primal siempre están asociadas sólo con soluciones básicas factibles. Por otra parte,. el método símplex dual trata con soluciones básicas infactibles hasta la última iteración, donde la solución básica asociada debe ser factible. En esencia, el método símplex primal sólo trata con puntos extremos, en tanto que en el método símplex dual todas las iteraciones, excepto la última, están asociadas con puntos extremos infactibles. Al final, ambos métodos dan soluciones básicas factibles como lo estipula la condición de no negatividad del modelo de PL.

CREACION DEL METODO SIMPLEX

En esta sección presentamos los detalles del método símplex. Comenzamos con la elaboración de la forma estándar necesaria para representar el espacio de soluciones de la PL, por medio de un Sistema de ecuaciones simultáneas. El resto de la exposición muestra cómo se determinan selectivamente las soluciones básicas sucesivas, con el fin de alcanzar el punto de solución óptima en un número finito de iteraciones.

Conforme se estudie el resto de este capitulo, el lector se relacionará con dos variantes del método símplex: los algoritmos del método símplex primal y los del símplex dual. En apariencia los dos métodos parecen ser diferentes. Esto no es el caso y, de hecho, lo fundamental de los dos algoritmos se basa en la idea que los puntos extremos del espacio de soluciones son completamente identificables por las soluciones básicas del modelo de PL. Básicamente, los dos algoritmos parecen ser diferentes porque están diseñados para sacar ventaja de la estructuración inicial especial del modelo de PL. Este punto se enfatizará conforme presentemos los detalles de los dos procedimientos.

FORMA ESTANDAR DEL MODELO DE PL
Un modelo de PL puede incluir restricciones de los tipos <-, = y >- Además, las variables pueden ser no negativas o irrestrictas (no restringidas) en signo. Para desarrollar un método de solución general, el problema de programación lineal debe ponerse en un formato común, al que llamamos la forma estándar. Las propiedades de la forma de PL estándar son

1. Todas las restricciones son ecuaciones (con los segundos miembros no negativos, si el modelo se resuelve por medio del método símplex primal)
2. Todas las variables son no negativas.
3. La función objetivo puede ser la maximización o la minimización.

Como se explicará después, la segunda propiedad que exige que todas las variables sean no negativas, es crucial en el desarrollo de los métodos símplex (primal y dual).
Ahora demostremos cómo se puede poner cualquier modelo de PL en el formato estándar.

A. Restricciones
1. Una restricción del tipo <- (>-) puede convertirse en una ecuación mediante la suma de una variable de holgura a (o restando una variable de exceso de) el primer miembro de la restricción.
Por ejemplo, en la restricción
x1 + 2x2 <- 6

Metodo Simplex

El método gráfico demuestra que la PL óptima está siempre asociada con un punto extremo o de esquina, del espacio de soluciones. Esta idea conduce precisamente a la creación del método simplex. Básicamente, lo que hace el método simplex es trasladar la definición geométrica del punto extremo a una definición algebraica. Durante la presentación del método simplex, deberá tenerse en mente este detalle.

¿Cómo identifica el método simplex los puntos extremos en forma algebraica? Como paso inicial, el método simplex necesita que cada una de las restricciones esté en una forma estándar especial, en la que todas las restricciones se expresan como ecuaciones, mediante la adición de variables de holgura o de exceso, según sea necesario. Este tipo de conversión conduce normalmente a un conjunto de ecuaciones simultáneas donde el número de variables excede al número de ecuaciones, lo que generalmente significa que las ecuaciones dan un número infinito de puntos solución (compárese con el espacio de soluciones gráficas). Los puntos extremos de este espacio pueden identificarse algebraicamente por medio de las soluciones básicas del sistema de ecuaciones simultáneas. De acuerdo con la teoría del álgebra lineal, una solución básica se obtiene igualando a cero las variables necesarias con el fin de igualar el número total de variables y el número total de ecuaciones para que la solución sea única, y luego se resuelve el sistema con las variables restantes. Fundamentalmente, la transición del procedimiento gráfico al algebraico se basa en la validez de la siguiente relación importante:

puntos extremos = soluciones básicas

Al no tener un espacio de soluciones gráficas que nos guie hacia el punto óptimo, necesitamos un procedimiento que identifique en forma inteligente las soluciones básicas promisorias. Lo que hace el método simplex, es identificar una solución inicial y luego moverse sistemáticamente a otras soluciones básicas que tengan el potencial de mejorar el valor de la función objetivo. Finalmente, la solución básica correspondiente a la óptima será identificada, con lo que termina el proceso de cálculo. En efecto, el método símplex es un procedimiento de cálculo iterativo donde cada iteración está asociada con una solución básica.
La determinación de una solución básica en el método símplex, implica detalles tediosos de cálculo. Tales detalles no deben distraernos de la idea fundamental del método: generar soluciones básicas sucesivas, de manera que nos conduzcan al punto
- extremo óptimo. Todos los detalles de cálculo son secundarios a esta idea básica, y así es como debemos tratarlos.