6.Asm-soluciones Metodo Simplex en Pl

UNIVERSIDAD NACIONAL “SANTIAGO ANTUNEZ DE MAYOLO”FACULTAD DE INGENIERIA DE MINAS, GEOLOGIA Y METALURGIA

ESCUELA ACADEMICO PROFESIONAL DE INGENIERIA DE MINAS

ANALISIS DE SISTEMAS MINEROS

SOLUCIONES – METODO SIMPLEX EN Programacion lineal

MSc.ING° GUSTAVO BOJORQUEZ HUERTA

AGOSTO 2013

METODO SIMPLEX.

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

Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución factible.

Interpretación Geométrica del Método Simplex

CONSIDERACIONES GENERALES DEL METODO

Se realiza un tabulado inicial, considerando las función objetivo y las restricciones establecidas en la matematización del problema, para lo cual se establecen las columnas y las líneas del tabulado de acuerdo a las variables de decisión y a las variable de holgura, en caso de restricciones del tipo (≤), o variables de excedencia cuando las restricciones se establecen como (≥). En forma general un tabulado tendrá la siguiente configuración.

Establecemos en forma general la matematización de un problema.

Max Zj = C1X1 + C2X2 + …. Cj Xn + 0S1 + 0S2 +….. 0Sn

Sujeto a:

c11X1 + c12X2 +…. + c1nXn + S1 ≤ V1

c21X1 + c22X2 +…. + c2nXn + S2 ≤ V2

. . . . .

cn1X1 + cn2X2 +…. + cnnXn + Sn ≤ Vn

Donde:

Zj = Valor iterativo de la función objetivo

C1, C2, …. Cj = Coeficientes en la Función Objetivo

X1, X2, … Xn = Variables de decisión.

c11, c12, … c1n

c21, c22, … c2n

. . . = Coeficientes en las restricciones

cn1, cn2, … cnn

S1, S2, … S3 = Variables de holgura

V1, V2, … V3 = Valores de las inecuaciones

Cj Mezcla de Productos

cantidad C1

x1

C2

x2

Cn

xn

0S1

0S2

0Sn

Variables de contribución por

unidad

0 S1 V1 c11 c12 c1n 1 0 0

0 S2 V2 c21 c22 c2n 0 1 0 coeficientes

0 Sn Vn cn1 cn2 cnn 0 0 1

Matriz del Sistema

Matriz de Identidad

Zj 0 0 0 0 0 0 0Contribución perdida por unidad

Cj - Zj C1-0 C2-0 Cn-0 0 0 0Contribución neta por unidad

TABULADO GENERAL

ETAPAS PARA LA APLICACIÓN DEL METODO SIMPLEX

1. SELECCIÓN DE LA COLUMNA DE VALOR POSITIVO MAS ALTO.

Se calculan los valores para el reglón final de la tabla simplex, esto es, el reglón Cj - Zj y se selecciona la columna que tenga el máximo valor positivo para Cj – Zj. Si no quedan más valores positivos en el reglón Cj – Zj, es decir, si sólo quedan valores cero o negativo, la contribución total está al máximo. Los pasos iterativos están terminados.

2. DETERMINACION DEL REGLON DESPLAZADO.

El reglón remplazado (antiguo) se determina dividiendo los valores de la columna de cantidades en la tabla simplex para cada reglón entre los elementos interseccionales de la columna óptima (seleccionada en el paso anterior). El reglón que tenga la cantidad positiva mas pequeña se selecciona como el reglón por remplazar.

3. CALCULO DE VALORES PARA EL REGLÓN SUBSTITUTO.

En la siguiente tabla se calculan valores para el reglón substituto (nuevo); este reglón toma el lugar del reglón desplazado (antiguo) de la tabla anterior. Los nuevos valores para el reglón substituto se calculan dividiendo cada valor del reglón reemplazado (antiguo) entre el elemento interseccional (pivot) del mismo reglón. La variable de la columna de mezcla de productos del nuevo reglón también tienen que cambiarse por la encontrada en la columna óptima utilizando el paso anterior.

4. CALCULO DE NUEVOS VALORES PARA LOS REGLONES RESTANTES.

Se calculan los nuevos valores para todos los reglones restantes de la tabla iniciada en el paso anterior. La fórmula para calcular estos nuevos valores de reglón, que no sea para los reglones Zj y Cj – Zj, es:

Elemento anterior

en el reglón

restante

-

Elemento interseccio

nal anterior

del reglón restante

Nuevo elemento

correspondiente en el

reglón substituto

x =

Nuevo valor

para el reglón

restante

Mientras permanecen sin cambio las variables de la columna mezcla de productos. Se calculan los últimos dos reglones (Zj y Cj – Zj). El procedimiento iterativo regresa y comienza un nuevo ciclo en el paso 1, con el fin de determinar si hay necesidad de desarrollar otra tabla

Utilizaremos el ejemplo del método gráfico para solucionarlo mediante el método simplex.

Maximizar Z = 10 x1 + 12 x2

Sujeto a:

2 x1 + 3 x2 ≤ 1,500 (Area 1)

3 x1 + 2 x2 ≤ 1,500 (Area 2)

x1 + x2 ≤ 600 (Area 3)

x1 ≥ 0

x2 ≥ 0

El primer paso para poder realizar la aplicación del método simplex, es convertir las desigualdades en ecuaciones para las tres áreas establecidas. Esto se logra sumando variables de holgura para cada área, esto es, sumando a una desigualdad una variable que reemplace al tiempo no utilizado en el área, por lo tanto tendremos:

S1 = Tiempo no utilizado en el área 1.



Es necesario incidir que las variables de holgura son positivas, debido a que las restricciones son desigualdades del tipo menor o igual que (≤ ), en caso contrario, es decir, si la desigualdad sería mayor o igual que (≥) sería necesario introducir variables de excedencia.

Las variables de holgura explicitadas en forma de ecuaciones toman la siguiente determinación:

S1 = 1,500 – 2x1 – 3x2

S2 = 1,500 – 3x1 – 2x2

S3 = 600 – x1 – x2

La matematización de esta programación lineal se establece del modo siguiente:

Maximizar Z = 10 x1 + 12 x2 + 0S1 + 0S2 + 0S3

Sujeto a:

1,500 = 2x1 + 3x2 + S1 + 0S2 + 0S3

1,500 = 3x1 + 2x2 + 0S1 + S2 + 0S3

600 = x1 + x2 + 0S1 + 0S2 + S3

El método simplex establece que todas las variables deben aparecer en todas las ecuaciones, las variables que no afectan a una ecuación se escriben con coeficiente cero (0).

Por lo señalado en el acápite anterior la función objetivo muestra a las variables de holgura S1, S2 y S3, con coeficientes cero (0), así mismo la ecuación para el área 1, muestra coeficientes cero (0) para el tiempo de holgura en las áreas 2 y 3.

Al manejo de las ecuaciones en el problema, puede ordenarse en forma tabular, a este ordenamiento se le denomina tableau, de modo que se establezca una visión matricial de los coeficientes para dar aplicación al álgebra matricial y el proceso de eliminación de Gauss-Jordan para resolver un sistema de ecuaciones lineales. Consignamos el Tablea 1 del modo siguiente:


cantidad 10x1

12x2

0S1

0S2

0S3


unidad

0 S1 1,500 2 3 1 0 0

0 S2 1,500 3 2 0 1 0 coeficientes

0 S3 600 1 1 0 0 1

Matriz del Sistema

Matriz de Identidad

Zj 0 0 0 0 0 0Contribución perdida por unidad

Cj - Zj 10 12 0 0 0Contribución neta por unidad

TABLEA I

ANALISIS DEL TABLEAU 1

1.La columna 1 (Cj), viene a ser el aporte por unidad para las variables de holgura (S1, S2 y S3), esto significa que en el momento inicial la contribución (aporte) unitario de estas variables es de cero (0), es decir que no se desarrollan actividades en las áreas de procesamiento de los productos en discusión (ónix y mármol).

2. Los valores de S1, S2 y S3, deben ser aquellos que generan las ecuaciones, es decir 1,500, 1,500 y 600 respectivamente (ubicadas en la tercera columna del tableau).

3. La solución inicial será igual a cero, ya que no se esta procesando ninguno de los productos (ónix, mármol)

Esto queda establecido en la fila Zj y en la columna tres (cantidad), ya que: 0x1,500+0x1,500+0x600=0

4.La matriz del sistema contiene a los coeficientes de las variables del producto real en este primer tableau. Esto es que en la primera fila y en la cuarta columna (x1), el coeficiente 2 establece que si quisiéramos llevar una unidad del producto ónix a la solución, tendríamos que ceder 2 horas de S1 en el Area 1. Es decir, toma 2 horas hacer el producto ónix en el Area 1. Así mismo, el coeficiente 3 de la columna x2, primera fila, indica que el proceso de una unidad del producto mármol necesitaría que se utilizaran 3 horas en el Area 1, lo que se tiene en los coeficientes de la matriz del sistema es la taza de sustitución.

5. La matriz identidad representa en el primer tableau simplex a los coeficientes de las variables de holgura, que se han sumado a las inecuaciones originales para convertirlos en ecuaciones. Esto debido a que todas las ecuaciones deben contener todas las variables, pero con coeficientes cero para que no afecte a la ecuación. Haciendo hincapié al coeficiente de la columna S1, en la primera fila, el valor 1 indica que para disponer de una hora de S1, sería necesario ceder una de las 1,500 hora de la solución inicial. El valor cero (0) de la columna S2 en la primera fila, indica que disponer de una hora en el Area 2 para otros fines no tiene efecto alguno sobre S1 (tiempo de holgura del Area 1). El mismo análisis se usa para la columna S3.

6. Se aplica el mismo razonamiento para para las dos siguientes filas (S2 y S3) del tableau 1, ya que ese están tratando con valores de sustitución.

7. Las dos últimas filas del tableau simplex se usan para determinar si se puede o no mejorar la solución. La evaluación de la última fila (Cj-Zj), es el primer paso en el método simplex.

8. La fila Zj, se determina a través de los valores de los coeficientes contenidos en las filas que se encuentran por encima de esta fila (Zj), esto es, en la caso de la columna cantidad el valor Zj=0, que representa una solución inicial de contribución cero para la empresa, tal como se calculo anteriormente. Por ejemplo si se desea procesar 1 m3 de ónix, los coeficientes (2, 3 y 1)

de la matriz del sistema, nos dice que se deben ceder 2 horas de S1, el tiempo no usado del Area 1, 3 horas de S2, el tiempo no usado del Area 2, y 1 hora de S3, el tiempo no usado en el Area 3. Como el tiempo de holgura tiene un valor de cero (0), no puede haber reducción de la contribución. El cálculo del valor de la contribución que se pierde al adicionar una unidad del producto ónix al proceso es de:

Número de horas de S1, cedidas:

2 x 0 (Contribución por unidad de S1) = 0





Contribución Total cedida 0

Determinación de los Tableaus siguientes

Para establecer los siguientes tableaus del método simplex se realizan los siguientes pasos:

Paso 1.- Selección de la columna de valor Positivo mas Alto. La evaluación de la última fila del tableau inicial es el primer paso a seguir en nuestro procedimiento esto se aplica cuando el problema que se presenta es la maximización.

El análisis de las cifras de la fila Cj – Zj, determina que el máximo valor posible es de 12. Un valor positivo indica que puede hacerse una mayor contribución por parte de la empresa. Un valor negativo indica la cantidad por la cual decrece la contribución si se llevara a la solución una unidad de la variable para esa columna. Como columna óptima se selecciona la cantidad positiva mas grande de la última fila, es decir 12 por unidad para el producto x2 ya que se quiere maximizar la contribución total. Cuando no quedan más valores positivos en la fila Cj – Zj y los valores son cero o negativos en problemas de maximización la contribución esta en su máximo valor.


cantidad 10x1

12x2

0S1

0S2

0S3


unidad

0 S1 1,500 2 3 1 0 0

0 S2 1,500 3 2 0 1 0 coeficientes

0 S3 600 1 1 0 0 1

Matriz del Sistema

Matriz de Identidad



TABLEA ICOLUMNA ENTRANTE

MAYOR VALOR

Paso 2.- Determinar la fila (antigua) reemplazada.- Una vez que se elaboró el tableau simplex inicial y que se ha seleccionado (primer paso) la variable (columna óptima) que contribuye el máximo por unidad (12 por unidad del producto mármol), el siguiente paso es determinar cual variable debe reemplazarse. La inspección de la columna óptima (12 para el producto mármol) indica que debe agregarse la variable x2 a la mezcla de productos reemplazando la fila S1, S2 ó S3. Para determinar cual variable será la que se reemplace, divida el valor de la columna de cantidad entre el coeficiente correspondiente de la columna óptima. Seleccione la fila asociada con el cociente positivo menor como la fila a reemplazar. Como la empresa desearía producir la máxima cantidad, pero tiene que tomarse en consideración las restricciones del problema, Las unidades posibles se calculan del modo siguiente:

Fila S1: 1,500 – tiempo no usado/se requieren 3 horas por unidad del producto mármol = 500 unidades del producto mármol.

Fila S2: 1,500 – tiempo no usado/se requieren 2 horas por unidad del producto mármol = 750 unidades del producto mármol.

Fila S3: 600 – tiempo no usado/se requiere 1 hora por unidad del producto mármol = 600 unidades del producto mármol.

Con base en estos cálculos para el mármol se reemplazará la fila S1, en el segundo tableau por 500 unidades del producto x2, a esto se le llama la fila reemplazada.

Paso 3. Calcular el Valor para la Fila (nueva) Reemplazante.- La primera fila a determinar en el segundo tableau es la nueva fila x2 (fila reemplazante) para la fila S1 (fila reemplazada). La fila x2, se calcula dividiendo cada valor de la fila reemplazada (S1) entre el elemento pivot (3) de la misma fila.

Los resultados de la nueva fila serán:


cantidad 10x1

12x2

0S1

0S2

0S3


unidad

0 S1 1500 2 3 1 0 0

0 S2 1500 3 2 0 1 0 coeficientes

0 S3 600 1 1 0 0 1

Matriz del Sistema

Matriz de Identidad



TABLEA IFILA REEMPLAZADA Elemento pivote

Fila x2: 1,500/3 = 500 (columna de cantidad).

Columna x1: 2/3 = 2/3

Columna x2: 3/3 = 1

Columna S1: 1/3 = 1/3

Columna S2: 0/3 = 0

Columna S3: 0/3 = 0.

Paso 4.- Cálculo de los Nuevos Valores para las filas restantes.

Para calcular los nuevos valores de las filas restantes (S2 y S3), se aplica la siguiente fórmulas:

Elemento anterior en la fila restante

-

Elemento interseccio

nal anterior de la fila restante

Nuevo elemento

correspondiente en la fila

reemplazante

x =

Nuevo valor

para la fila

restante


cantidad 10x1

12x2

0S1

0S2

0S3


unidad

0 x2 500 2/3 1 1/3 0 0

0 S2 1500 3 2 0 1 0 coeficientes

0 S3 600 1 1 0 0 1

Matriz del Sistema

Matriz de Identidad



TABLEA I

Los nuevos valores de las filas S2 y S3, se calculan del modo siguiente:

Fila S2:

1,500 – (2 x 500) = 500

3 – (2 x 2/3) = 1 2/3

2 – (2 x 1) = 0

0 – (2 x 1/3) = - 2/3

1 – (2 x 0) = 1

0 – (2 x 0) = 0

Fila S3:

600 – (1 x 500) = 100

1 – (1 x 2/3) = 1/3

1 – (1 x 1) = 0

0 – (1 x 1/3) = - 1/3

0 – (1 x 0) = 0

1 – (1 x 0) = 1


cantidad 10x1

12x2

0S1

0S2

0S3


unidad

12 x2 500 2/3 1 1/3 0 0

0 S2 500 1 2/3 0 -2/3 1 0 coeficientes

0 S3 100 1/3 0 -1/3 0 1

Matriz del Sistema

Matriz de Identidad

Zj 6,000 8 12 4 0 0Contribución perdida por unidad

Cj - Zj 2 0 -4 0 0Contribución neta por unidad

TABLEA I - MODIFICADO

El procedimiento para calcular las dos últimas filas del Tableau II, se realizan del modo siguiente:

Zj (contribución total) = 12(500) + 0(500) + 0(100) = 6,000

Zj para x1 = 12(2/3) + 0(1 2/3) + 0(1/3) = 8

Zj para x2 = 12(1) + 0(0) + 0(0) = 12

Zj para S1 = 12(1/3) + 0(-2/3) + 0(-1/3) = 4

Zj para S2 = 12(0) + 0(1) + 0(0) = 0

Zj para S3 = 12(0) + 0(0) + 0(0) = 0

El cálculo para la fila Cj – Zj, son:

x1 (variable): 10 Cj(contri./unidad) – 8 Zj(contri. pérdida/unidad = 2 Cj – Zj (contri. neta por unidad)

x2: 12 – 12 = 0

S1 : 0 – 4 = -4

S2 : 0 – 0 = 0

S3 : 0 – 0 = 0

CjMezcla de Productos Cantidad

10x1

12x2

0S1

0S2

0S3

12 x2 500 2/3 1 1/3 0 0

Fila reemplazante0 S2 500 1 2/3 0 -2/3 1 0

Fila remanente con nuevos valores0 S3 100 1/3 0 -1/3 0 1

Fila remanente con nuevos valoresZj 6,000 8 12 4 0 0

Cj - Zj 2 0 -4 0 0

TABLEAU II

La existencia de un valor positivo en la última fila de la columna x1, predispone que existe una contribución general disponible para la empresa, por lo tanto, se hace necesario realizar un tercer tableau que mejore al anterior.

Para la determinación del tableau III, se sigue un procedimiento similar al anterior (tableau II). Para esto determinamos la columna óptima. Por lo tanto la columna x1 es la que guarda este lineamiento por cuanto presenta un valor positivo igual a 2. Para determinar la fila reemplazada, para lo cual los valores de la columna de cantidad se dividen entre los valores interseccionales correspondientes de la columna óptima, del modo siguiente:

Fila x2: 500/(2/3) = 750

Fila S2: 500/(1 2/3) = 300

Fila S3: 100/(1/3) = 300.

Los cálculos muestran una degeneración , ya que existen dos filas con el mismo valor, en este caso utilizaremos la fila S3.

CjMezcla de Productos Cantidad

10x1

12x2

0S1

0S2

0S3

12 x2 300 0 1 1 0 -2

Fila remanente con nuevos valores0 S2 0 0 0 1 1 -5

Fila remanente con nuevos valores0 x1 300 1 0 -1 0 3

Fila reemplazanteZj 6,600 10 12 2 0 6

Cj - Zj 0 0 -2 0 -6

TABLEAU III

La nueva fila reemplazante del tableau 3, se calcula dividiendo cada número de la fila reemplazante entre el valor interseccional de la fila reemplazada, esto es:

100/(1/3) = 300; (1/3)/(1/3) 0 = 1; 0/(1/3) = 0; (-1/3)/(1/3) = -1;

0/(1/3) = 0; 1/(1/3) = 3.

El tercer tableau terminado indica que los valores de la fila Cj – Zj son cero o negativos por lo tanto se da por terminado el proceso de optimización.

Es necesario verificar que los valores obtenidos cumplen con los requerimientos establecidos, para lo cual volvemos a las inecuaciones originales y se calculan los valores para verificar si guardan los lineamientos establecios:

2x1 + 3x2 ≤ 1,500

3x1 + 2x2 ≤ 1,500

x1 + x2 ≤ 600

Sustituyendo los valores adecuados para x1 y x2 en las inecuaciones anteriores, los resultados indican que están dentro de las restricciones del problema.

2(300) + 3(300) ≤ 1,500

600 + 900 ≤ 1,500

1,500 = 1,500

3(300) + 2(300) ≤ 1,500

900 + 600 ≤ 1,500

1,500 = 1,500

(300) + (300) ≤ 600

600 = 600

EJEMPLO N° 02 – APLICACIÓN DEL METODO SIMPLEX

Maximizar Z= f(x,y)= 3x + 2y

sujeto a: 2x + y ≤ 18

2x + 3y ≤ 42

3x + y ≤ 24

x ≥ 0 , y ≥ 0

Se consideran los siguientes pasos:

1. Convertir las desigualdades en igualdades

Se introduce una variable de holgura por cada una de las restricciones, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales:

2x + y + h = 18

2x + 3y + s = 42

3x + y + d = 24

2. Igualar la función objetivo a cero

- 3x - 2y + Z = 0

3. Escribir la tabla inicial simplex

En las columnas aparecerán todas las variables del problema y, en las filas, los coeficientes de las igualdades obtenidas, una fila para cada restricción y la última fila con los coeficientes de la función objetivo:

Tabla I . Iteración nº 1

Base Variable de decisión Variable de holguraValores solución

x y h s d

h 2 1 1 0 0 18

s 2 3 0 1 0 42

d 3 1 0 0 1 24

Z -3 -2 0 0 0 0

4. Encontrar la variable de decisión que entra en la base y la variable de holgura que sale de la base

A. Para escoger la variable de decisión que entra en la base, nos fijamos en la última fila, la de los coeficientes de la función objetivo y escogemos la variable con el coeficiente negativo mayor (en valor absoluto).

En nuestro caso, la variable x de coeficiente - 3.

Si existiesen dos o más coeficientes iguales que cumplan la condición anterior, entonces se elige cualquiera de ellos.

Si en la última fila no existiese ningún coeficiente negativo, significa que se ha alcanzado la solución óptima. Por tanto, lo que va a determinar el final del proceso de aplicación del método del simplex, es que en la última fila no haya elementos negativos.

La columna de la variable que entra en la base se llama columna pivote (En color azulado).

B. Para encontrar la variable de holgura que tiene que salir de la base, se divide cada término de la última columna (valores solución) por el término correspondiente de la columna pivote, siempre que estos últimos sean mayores que cero. En nuestro caso:

18/2 [=9] , 42/2 [=21] y 24/3 [=8]

Si hubiese algún elemento menor o igual que cero no se hace dicho cociente. En el caso de que todos los elementos fuesen menores o iguales a cero, entonces tendríamos una solución no acotada y no se puede seguir.

La fila que en la división anterior dé lugar al menor cociente positivo, que es la fila 3, ya que 8 es el menor, indica la fila de la variable de holgura que sale de la base, d. Esta fila se llama fila pivote (En color azulado).

Si al calcular los cocientes, dos o más son iguales, indica que cualquiera de las variables correspondientes puede salir de la base.

C. En la intersección de la fila pivote y columna pivote tenemos el elemento pivote operacional, 3.

5. Encontrar los coeficientes de la nueva tabla.

Los nuevos coeficientes de x se obtienen dividiendo todos los coeficientes de la fila d por el pivote operacional, 3, que es el que hay que convertir en 1.

A continuación mediante la reducción gaussiana hacemos ceros los restantes términos de su columna, con lo que obtenemos los nuevos coeficientes de las otras filas incluyendo los de la función objetivo Z.

También se puede hacer utilizando el siguiente esquema:

Fila del pivote:

Nueva fila del pivote= (Vieja fila del pivote) : (Pivote)

Resto de las filas:

Nueva fila= (Vieja fila) - (Coeficiente de la vieja fila en la columna de la variable entrante) x (Nueva fila del pivote)

Veamos con un ejemplo una vez calculada la fila del pivote (fila x en la tabla 2):

VIEJA FILA DE

S

COEFICIENTE

NUEVA FILA PIVOTE

NUEVA FILA DE S

2 - 2 x 1 = 03 - 2 x 1/3 = 7/30 - 2 x 0 = 01 - 2 x 0 = 10 - 2 x 1/3 = -2/3

42 - 2 x 8 = 26

Tabla II . Iteración nº 2

BaseVariable de

decisiónVariable de holgura

Valores solución

x y h s d

h 0 1/3 1 0 -2/3 2

s 0 7/3 0 1 -2/3 26

x 1 1/3 0 0 1/3 8

Z 0 -1 0 0 1 24

Como en los elementos de la última fila hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso:

A. La variable que entra en la base es y, por ser la variable que corresponde al coeficiente -1.

B. Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote:

2:1/3[=6], 26:7/3[=78/7] y 8:1/3 [=8] y como el menor cociente positivo es 6, tenemos que la

variable de holgura que sale es h. C. El elemento pivote, que ahora hay que hacer 1, es 1/3. Operando de forma análoga a la anterior obtenemos la

tabla:

Tabla III . Iteración nº 3

BaseVariable de


Valores solución

x y h s d

y 0 1 3 0 -2 6

s 0 0 -7 0 4 12

x 1 0 -1 0 1 6

Z 0 0 3 0 -1 30

Como en los elementos de la última fila hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso:

A. La variable que entra en la base es d, por ser la variable que corresponde al coeficiente -1

B. Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote:

6/(-2) [=-3] , 12/4 [=3], y 6:1 [=6]

y como el menor cociente positivo es 3, tenemos que la variable de holgura que sale es s.

C. El elemento pivote, que ahora hay que hacer 1, es 4.

Obtenemos la siguiente tabla:

Tabla IV . Final del proceso

BaseVariable de


Valores solución

x y h s d

y 0 1 -1/2 0 0 12

d 0 0 -7/4 0 1 3

x 1 0 -3/4 0 0 3

Z 0 0 5/4 0 0 33

Como todos los coeficientes de la fila de la función objetivo son positivos, hemos llegado a la solución óptima.

Los solución óptima viene dada por el valor de Z en la columna de los valores solución, en nuestro caso: 33. En la misma columna se puede observar el vértice donde se alcanza este valor, observando las filas correspondientes a las variables de decisión que han entrado en la base: D(3,12).

Interpretación Geométrica del Método Simplex

Las sucesivas tablas que hemos construido van proporcionando el valor de la función objetivo en los distintos vértices, ajustándose, a la vez, los coeficientes de las variables iniciales y de holgura.

En la primera iteración (Tabla I) han permanecido todos los coeficientes iguales, se ha calculado el valor de la función objetivo en el vértice A(0,0), siendo este 0.

A continuación se desplaza por la arista AB, calculando el valor de Z, hasta llegar a B. Este paso aporta la Tabla II.

En esta segunda iteración se ha calculado el valor que corresponde al vértice B(8,0): Z=f(8,0) = 24

Sigue por la arista BC, hasta llegar a C, donde se para y despliega los datos de la Tabla III.

En esta tercera iteración se ha calculado el valor que corresponde al vértice C(6,6) : Z=f(6,6)=30.

Continua haciendo cálculos a través de la arista CD, hasta llegar al vértice D. Los datos que se reflejan son los de la Tabla IV.

Concluye con esta tabla, advirtiendo que ha terminado (antes ha comprobado que la solución no mejora al desplazarse por la arista DE).

El valor máximo de la función objetivo es 33, y corresponde a: x = 3 e y = 12 (vértice D).

Si calculas el valor de la función objetivo en el vértice E(0,14), su valor es de 28 que no supera el valor 33, anteriormente calculado.

Problema de Minimización Aplicando el Método Simplex

Si en lugar de maximizar se trata de un problema de minimizar se sigue el mismo proceso, pero cambiando el sentido del criterio, es decir, para entrar en la base se elige la variable cuyo valor, en la fila de la función objetivo, sea el mayor de los positivos y se finalizan las iteraciones cuando todos los coeficientes de la fila de la función objetivo son negativos .La siguiente programación lineal matematiza la minimización de costos, que se plantea del modo siguiente:

Minimizar Z = 5x1 + 6x2 + 7x3

Sujeto a:

x1 + x2 + x3 = 1,000

x1 ≤ 300

x2 ≥ 150

x3 ≥ 200

Donde:

x1 = Cantidad del elemento metálico 1.



Siguiendo con los lineamientos establecidos en el caso de maximización, el primer paso será crear las ecuaciones de las inecuaciones existente.

1. Para la primera restricción , las variables x1, x2 y x3, pueden ser iguales a cero (0), pero para poder tener una influencia sobre la metodología simplex se le asigna una variables denominada variable artificial (A1) , al cual se le asigna un costo bastante alto que lo denominaremos M, la ecuación resultante viene a ser: x1 + x2 + x3 + A1 = 1,000. La variable artificial es un artificio de cálculo que se utiliza en ecuaciones o en inecuaciones cuando las restricciones son del tipo mayor o igual que, no siendo necesarias su uso en inecuaciones del tipo menor o igual que.

2. Para la segunda restricción, x1 ≤ 300, es necesario añadir una variable de holgura (S1), por lo tanto la inecuación se convierte en la ecuación x1 + S1 = 300.

3. Las dos últimas restricciones se convierten en ecuaciones restándoles variables de holgura negativas o variables excedentes, determinándose las ecuaciones:

x2 – S2 = 150

x3 – S3 = 200

4. Como deben considerarse variables artificiales en estas dos últimas ecuaciones las ecuaciones finales serían las siguientes:

x2 – S2 + A2 = 150

x3 – S3 + A3 = 200

5. Establecemos la función objetivo para lo cual es necesario aplicar la norma que establece que todas las variables intervinientes deben estar presentes en la ecuación de minimización del costo. Para lo cual se establece que las variables de holgura (S1, S2 y S3) deben tener un coeficiente igual a cero (0), mientras que las variables artificiales (A1, A2 y A3) deben tener un coeficiente que supuestamente es un valor bastante alto y que lo representaremos por M, lo mismo se predispone en las restricciones pero en este caso las variables artificiales tendrán un coeficiente igual a cero (0).

6. La matematización de la programación lineal en discusión, queda determinada del modo siguiente:

Función Objetivo:Minimizar Z = 5x1 + 6x2 +7x3 + MA1 + 0S1 + 0S2 + MA2 + 0S3 + MA3 (minimización de costos).

Sujeto a:

x1 + x2 + x3 +A1 + 0S1 + 0S2+ 0A2 + 0 S3 + 0A3 = 1,000

x1 + 0x2 + 0x3 + 0A1 + S1 + 0S2+ 0A2 + 0S3 + 0A3 = 300

0x1 + x2 + 0x3 + 0A1 + 0S1 - S2 + A2 + 0 S3 + 0A3 = 150

0x1 + 0x2 + x3 + 0A1 + 0S1 + 0S2+ 0A2 - S3 + A3 = 200

7. En el primer tablea únicamente se seleccionan como variables de la mezcla de los productos A1, S1, A2 y A3, esto debido a que las variables A1, A2, y A3 permiten mantener en equilibrio las primeras ecuaciones y lo mismo sucede con la variable de holgura S1. Esto debido a que las variables artificiales antes manifestadas que por tener un costo muy alto, no estarán presentes en la solución final, lo mismo sucede con la variable de holgura S1.


Cantid 5x1

6x2

7x3

MA1

0S1

0S2

MA2

0S3

MA3

M A1 1,000 1 1 1 1 0 0 0 0 0

0 S1 300 1 0 0 0 1 0 0 0 0

M A2 150 0 1 0 0 0 -1 1 0 0

M A3 200 0 0 1 0 0 0 0 -1 1

Zj 1,350M M 2M 2M M 0 -M M -M M

Cj - Zj 5-M 6-2M 7-2M 0 0 M 0 M 0

TABLEA I

Columna Pívot (elementos interseccionales)

Fila Pívot (fila reemplazada)


Cantid 5x1

6x2

7x3

MA1

0S1

0S2

MA2

0S3

MA3

M A1 850 1 0 1 1 0 1 -1 0 0

0 S1 300 1 0 0 0 1 0 0 0 0

6 x2 150 0 1 0 0 0 -1 1 0 0

M A3 200 0 0 1 0 0 0 0 -1 1

Zj 1,050M+ 900 M 6 2M M 0 M-6 -M+6 -M M

Cj - Zj 5-M 0 7-2M 0 0 -M+6 2M-6 M 0

TABLEA II




Cantid 5x1

6x2

7x3

MA1

0S1

0S2

MA2

0S3

MA3

M A1 650 1 0 0 1 0 1 -1 1 -1

0 S1 300 1 0 0 0 1 0 0 0 0

6 x2 150 0 1 0 0 0 -1 1 0 0

7 x3 200 0 0 0 0 0 0 0 -1 1

Zj 650M+ 2300 M 6 M M 0 M-6 -M+6 M-7 -M+7

Cj - Zj -M+5 0 0 0 0 -M+6 2M-6 -M+7 2M-7

TABLEA II




Cantid 5x1

6x2

7x3

MA1

0S1

0S2

MA2

0S3

MA3

M A1 350 0 0 0 1 -1 1 -1 1 -1

5 x1 300 1 0 0 0 1 0 0 0 0

6 x2 150 0 1 0 0 0 -1 1 0 0

7 x3 200 0 0 1 0 0 0 0 -1 1

Zj 350M+ 3800 5 6 7 M -M+5 M-6 -M+6 M-7 -M+7

Cj - Zj 0 0 0 0 M-5 -M+6 2M-6 -M+7 2M-7

TABLEA III




Cantid 5x1

6x2

7x3

MA1

0S1

0S2

MA2

0S3

MA3

0 S2 350 0 0 0 1 -1 1 -1 1 -1

5 x1 300 1 0 0 0 1 0 0 0 0

6 x2 500 0 1 0 1 -1 0 0 1 -1

7 x3 200 0 0 1 0 0 0 0 -1 1

Zj 5,900 5 6 7 6 -1 0 0 -1 1

Cj - Zj 0 0 0 M-6 1 0 M 1 M-1

TABLEA III

Documents

6.Asm-soluciones Metodo Simplex en Pl