ejercicios- metodo simplex

7/16/2019 Ejercicios- Metodo Simplex

1/63

INVESTIGACIN DE OPERACIONES Universidad Ricardo Palma

1


2/63


2


3/63


3

El algoritmo SIMPLEX es un procedimiento general para resolver problemas de

programacin lineal, desarrollado por George Dantzing en el ao 1947.

La implementacin en computadoras personales del mtodo SIMPLEX y susvariantes se han convertido en herramientas tan poderosas que se usan a menudopara resolver problemas de programacin lineal de miles de restricciones y milesde variables y , en ocasiones, problemas bastante ms grandes.

Como hemos visto en el material de trabajo autnomo 2 se trat el tema desolucionar problemas de dos o tres variables, aplicando el mtodo grfico, as

como el anlisis de sensibilidad de sus resultados. Ahora, en el material de trabajoautnomo 3 veremos el mtodo de solucin del SIMPLEX para solucionarproblemas de n variables, tanto para maximizar o minimizar la funcin objetivo,considerando variables positivas, negativas y no restringidas.

Para los modelos de maximizacin se esta considerando el desarrollo de ejerciciosplanteados con variables positivas y variables no restringidas, para el caso de losproblemas con variables negativas se esta planteando un ejercicio bajo el enfoquede minimizacin.

Para los modelos de minimizacin se esta considerando el desarrollo de ejerciciosplanteados con variables positivas y variables negativas, para el caso de losproblemas con variables no restringidas se esta planteando un ejercicio bajo elenfoque de maximizacin.


4/63

4

Los modelos de maximizacin buscan casi siempre obtener la mxima rentabilidad,

la mayor productividad, el mximo cumplimiento del nivel de servicio, el mximocumplimiento de los objetivos, etc y se aplican en la industria , en los sistemas decomercializacin, sistemas financieros, transportes, sistemas de salud, en el sectorde servicios pblicos, etc.

4



5/63


5


6/63


6


7/63


7

Ahora veremos el desarrollo del mtodo SIMPLEX aplicado a un modelo de

maximizacin.Recordemos que el mtodo SIMPLEX se aplica slo a modelos que tienenrestricciones del tipo menor o igual.

Como primer paso debemos aplicar la forma estndar al modelo planteado, lo cualimplica tres condiciones:La primera condicin: que los lado derecho de las restricciones sean constantesmayores o iguales a cero,

en nuestro ejemplo, los lado derecho de las restricciones ya son

constantes positivas.

La segunda condicin: que las inecuaciones sean expresadas en forma deigualdades usando variables de holgura,

en nuestro ejemplo, estamos agregando las variables de holguraS1 y S2 a las dos restricciones.

La tercera condicin: que las variables que participan en el modelo sean mayoreso iguales a cero (es decir que sean variables positivas)

en nuestro ejemplo, todas las variables son positivas.


8/63

Ahora bien, implementamos el tablero inicial del simplex con la estructura de su

forma estndar.

Como se est maximizando, debemos seleccionar el coeficiente del Costo Reducidoms negativo para obtener nuestra columna PIVOT, para nuestro caso correspondeal valor -3 de la columna asociada a la variable X2, y es la variable que ingresa a labase en el siguiente tablero.

8



9/63

Luego obtenemos nuestra columna PIVOT asociada a la variable X2, ya que tiene el

costo reducido ms negativo con el valor -3. La variable X2 es la variable queingresa a la base en el siguiente tablero.

Posteriormente hallamos el ratio del cociente mnimo dividiendo la columna dellado derecho (solucin) entre los valores de los elemento de la columna PIVOT (ladivisin solo se hace para los elementos positivos), el menor ratio de cocientemnimo nos determina la fila PIVOT, para nuestro caso el menor ratio correspondea la variable S1 que tiene como cociente mnimo 3. Esto significa que en el

siguiente tablero debe salir de la base la variable S1 y su lugar debe ser remplazadapor la variable X2.

El elemento de interseccin de la fila y columna PIVOT debe ser uno en el siguientetablero, para ello dividimos la fila de la variable S1 entre 2, ya que el elemento deintercepcin es 2 y colocamos el resultado en el siguiente tablero en la posicin delrengln que le corresponde, y la variable S1 es reemplazada por la variable X2,generalizamos esta operacin para toda la fila.

9



10/63

Ahora bien, mediante operaciones suma fila debemos hacer cannico el vector

columna asociado a la variable X2 en el siguiente tablero, de la siguiente manera:

En el segundo tablero multiplicamos el valor UNO (el cual est resaltado en la filade color rojo) por 3 y luego sumamos el valor -3 de la fila de los coeficientesreducidos en el primer tablero. El resultado es cero y lo colocamos en la mismaposicin pero del segundo tablero, replicamos esta operacin para toda la fila conel valor del coeficiente reducido correspondiente del primer tablero.

10



11/63

Luego, en el segundo tablero multiplicamos el valor UNO (el cual est resaltado

en la fila de color rojo) por ( 1) y luego sumamos el valor 1 de la fila de S2 en elprimer tablero. El resultado es cero y lo colocamos en la misma posicin pero delsegundo tablero, replicamos esta operacin para toda la fila con el valor delcoeficiente correspondiente del primer tablero.

11



12/63

Continuando, como se est maximizando debemos seleccionar el coeficiente del

Costo Reducido ms negativo del segundo tablero para obtener nuestra columnaPIVOT. Para nuestro caso corresponde al valor -1/2 de la columna asociada a lavariable X1, y es la variable que ingresa a la base en el tercer tablero.

Luego, hallamos el ratio del cociente mnimo dividiendo la columna del ladoderecho (solucin) entre los valores de los elementos de la columna PIVOT (ladivisin solo se hace para los elementos positivos). El menor ratio de cocientemnimo nos determina la fila PIVOT, para nuestro caso el menor ratio corresponde

a la variable S2 que tiene como cociente mnimo 10/3. Esto significa que en eltercer tablero debe salir de la base la variable S2 y su lugar debe ser remplazadapor la variable X1.

12



13/63

Ahora bien, el elemento de interseccin de la fila y columna PIVOT debe ser uno en

el siguiente tablero. Para ello dividimos la fila de la variable S1 entre 3/2, ya que elelemento de intercepcin es 3/2 y colocamos el resultado en el tercer tablero en laposicin del rengln que le corresponde, y la variable S2 es reemplazada por lavariable X1, generalizamos esta operacin para toda la fila.

13



14/63

Luego mediante operaciones suma fila debemos hacer cannico el vector columna

asociado a la variable X1 en el tercer tablero, de la siguiente manera:

En el tercer tablero multiplicamos el valor UNO (el cual est resaltado en la filade color rojo) por el valor 1/2 y luego sumamos el valor -1/2 de la fila de loscoeficientes reducidos en el segundo tablero. El resultado es cero y lo colocamosen la misma posicin pero del tercer tablero, replicamos esta operacin para todala fila con el valor del coeficiente reducido correspondiente del segundo tablero.

14



15/63

Luego en el tercer tablero multiplicamos el valor UNO (el cual est resaltado en

la fila de color rojo) por el valor ( 1/2) y luego sumamos el valor 1/2 de la fila deX2 en el segundo tablero. El resultado es cero y lo colocamos en la mismaposicin pero del tercer tablero. Replicamos esta operacin para toda la fila con elvalor del coeficiente correspondiente del segundo tablero.

Luego, vemos que en el tercer tablero ya no existen ms costos reducidosnegativos, entonces se ha llegado a la solucin final.

15



16/63

Finalmente el tercer tablero nos da el tablero ptimo del cual obtenemos el vector

solucin, el cual est compuesto por las variables bsicas (son aquellas variablesque estn en la columna base) las cuales obtienen su resultado de la columnasolucin y las variables no bsicas (aquellas variables que no aparecen en lacolumna base) asumen valor cero por default.

El valor de la funcin objetivo se obtiene del primer valor de la columna solucin.

16



17/63

La solucin final se da en funcin a las variables de decisin:

X1 asume un valor de 10/3 ,

X2 asume un valor de 4/3 , y

La funcin objetivo asume un valor ptimo de 32/3

17



18/63


18


19/63

19

Los modelos de maximizacin con variables no restringidas, buscan modelar

condiciones donde las variables puedan tomar valores positivos negativos, comopor ejemplo la condicin de disponibilidad de horas, donde pueden existir horassobrantes requerirse horas extras, la condicin de disponibilidad de capital,donde puede existir capital sobrante requerirse capital adicional, entre otroscasos; donde el resultado de la funcin objetivo es casi siempre obtener la mximarentabilidad y se aplican en la industria , en los sistemas de comercializacin,sistemas financieros, transportes, sistemas de salud, en el sector de serviciospblicos, etc.

A continuacin mostraremos una formulacin asociado a un modelo matemticodonde se ilustra el uso de variables no restringidas.

19



20/63

INVESTIGACIN OPERACIONAL

20

Ahora veremos el desarrollo del mtodo SIMPLEX aplicado a un modelo de maximizacin con

variables no restringidas.Encontrarn ocasiones en donde el modelo requiere hacer uso de variables que puedan asumirvalores positivos o negativos y ser necesario hacer un reemplazo de variables.

Recordar que el mtodo SIMPLEX se aplica solo a modelos que tienen restricciones del tipo menor oigual.

Como primer paso debemos aplicar la forma estndar al modelo planteado, lo cual implica trescondiciones:La primera condicin : que los lado derecho de las restricciones sean constantes mayores o igualesa cero,

en nuestro ejemplo los lado derecho de las restricciones ya son constantespositivas.

La segunda condicin: que las inecuaciones sean expresadas en forma de igualdades usandovariables de holgura,

en nuestro ejemplo estamos agregando las variables de holgura S1 , S2 y S3 a lastres restricciones.

La tercera condicin: que las variables que participan en el modelo sean mayores o iguales a cero(es decir que sean variables positivas)

en nuestro ejemplo la variable X y Y esta definida como no restringidas, por lo

tanto debemos realizar un cambio de variable,X debe ser igual a X1 X2 , tambin la variable Y debe ser igual a Y1-Y2, y luego

hacemos el reemplazo en todo el modelo en su forma estndar.

20



21/63

Como primer paso implementamos el tablero inicial del simplex con la estructura

de su forma estndar.

Como se esta maximizando debemos seleccionar el coeficiente del Costo Reducidoms negativo para obtener nuestra columna PIVOT, para nuestro caso correspondeal valor -8 de la columna asociada a la variable X2, y es la variable que ingresa a labase en el segundo tablero.

21



22/63

Luego hallamos el ratio del cociente mnimo dividiendo la columna del lado

derecho (solucin) entre los valores de los elemento de la columna PIVOT (ladivisin solo se hace para los elementos positivos), el menor ratio de cocientemnimo nos determina la fila PIVOT, para nuestro caso el menor ratio correspondea la variable S3 que tiene como cociente mnimo 1.

Esto significa que en el segundo tablero debe salir de la base la variable S3 y sulugar debe ser remplazada por la variable X2.

El elemento de interseccin de la fila y columna PIVOT debe ser uno en el siguiente

tablero, para ello dividimos la fila de la variable S3 entre 1, ya que el elemento deintercepcin es 1 y colocamos el resultado en el segundo tablero en la posicin delrengln que le corresponde, y la variable S3 es reemplazada por la variable X2,generalizamos esta operacin para toda la fila.

22



23/63

Mediante operaciones suma fila debemos hacer cannico el vector columna

asociado a la variable X2 en el segundo tablero, de la siguiente manera:

En el segundo tablero multiplicamos el valor UNO (el cul esta resaltado en la filade color rojo) por 8 y luego sumamos el valor ( - 8 ) de la fila de los coeficientesreducidos en el primer tablero, el resultado es cero y lo colocamos en la mismaposicin pero del segundo tablero, replicamos sta operacin para toda la fila conel valor del coeficiente reducido correspondiente del primer tablero.

23



24/63

Luego, en el segundo tablero multiplicamos el valor UNO (el cul esta resaltado

en la fila de color rojo) por 1 y luego sumamos el valor (-1) de la fila de S1 en elprimer tablero, el resultado es cero y lo colocamos en la misma posicin pero delsegundo tablero, replicamos sta operacin para toda la fila con el valor delcoeficiente correspondiente del primer tablero.

24



25/63

En el segundo tablero multiplicamos el valor UNO (el cul esta resaltado en la fila

de color rojo) por 1 y luego sumamos el valor (-1) de la fila de S2 en el primertablero, el resultado es cero y lo colocamos en la misma posicin pero delsegundo tablero, replicamos sta operacin para toda la fila con el valor delcoeficiente correspondiente del primer tablero.

25



26/63

Continuando, como se esta maximizando debemos seleccionar el coeficiente del

Costo Reducido ms negativo del segundo tablero para obtener nuestra columnaPIVOT, para nuestro caso corresponde al valor -7 de la columna asociada a lavariable Y2, y es la variable que ingresa a la base en el tercer tablero.

Luego hallamos el ratio del cociente mnimo dividiendo la columna del ladoderecho (solucin) entre los valores de los elemento de la columna PIVOT (ladivisin solo se hace para los elementos positivos), el menor ratio de cocientemnimo nos determina la fila PIVOT, para nuestro caso el menor ratio corresponde

a la variable S2 que tiene como cociente mnimo 5/3. Esto significa que en el tercertablero debe salir de la base la variable S2 y su lugar debe ser remplazada por lavariable Y2.

El elemento de interseccin de la fila y columna PIVOT debe ser uno en el tercertablero, para ello dividimos la fila de la variable S2 entre 3, ya que el elemento deintercepcin es 3 y colocamos el resultado en el tercer tablero en la posicin delrengln que le corresponde, y la variable S2 es reemplazada por la variable Y2,generalizamos esta operacin para toda la fila.

26



27/63


asociado a la variable Y2 en el tercer tablero, de la siguiente manera:

En el tercer tablero multiplicamos el valor UNO (el cul esta resaltado en la filade color rojo) por 7 y luego sumamos el valor ( - 7 ) de la fila de los coeficientesreducidos en el segundo tablero, el resultado es cero y lo colocamos en la mismaposicin pero del tercer tablero, replicamos sta operacin para toda la fila con elvalor del coeficiente reducido correspondiente del primer tablero.

27



28/63

Luego, en el tercer tablero multiplicamos el valor UNO (el cul esta resaltado en

la fila de color rojo) por 2 y luego sumamos el valor (-2) de la fila de S1 en elsegundo tablero, el resultado es cero y lo colocamos en la misma posicin perodel tercer tablero, replicamos sta operacin para toda la fila con el valor delcoeficiente correspondiente del segundo tablero.

28



29/63

En el tercer tablero multiplicamos el valor UNO (el cual est resaltado en la fila

de color rojo) por 1 y luego sumamos el valor (-1) de la fila de Y2 en el segundotablero. El resultado es cero y lo colocamos en la misma posicin pero del tercertablero, replicamos esta operacin para toda la fila con el valor del coeficientecorrespondiente del segundo tablero.

Luego, vemos que en el tercer tablero ya no existen ms costos reducidosnegativos; entonces, se ha llegado a la solucin final.

29



30/63

El tercer tablero nos da el tablero ptimo del cual obtenemos el vector solucin,

compuesto por las variables bsicas (son aquellas variables que estn en lacolumna base) las cuales obtienen su resultado de la columna solucin y lasvariables no bsicas (aquellas variables que no aparecen en la columna base)asumen valor cero por default.


30



31/63


X asume un valor de 8/3 ,

Y asume un valor de - 5/3 , y

La funcin objetivo asume un valor ptimo de 59/3

31



32/63

HE17 - Seminario de Investigacin

3232



33/63

33

Los modelos de minimizacin buscan casi siempre obtener el mnimo costo, el

menor tiempo de produccin, el menor desperdicio, la menor cantidad de piezasrechazadas, el menor tiempo de entrega, el menor tiempo de espera, etc y seaplican en la industria , en los sistemas de comercializacin, sistemas financieros,transportes, sistemas de salud, en el sector de servicios pblicos, etc.

33



34/63

Una empresa produce harina de tipo I para uso interno y harina tipo II para venta.

El rea de ventas estima que la diferencia entre la harina tipo I y II debe ser a lo mas 6toneladas.

Una tonelada de harina tipo I de uso interno genera un costo de 2 mil soles y requiere unoperario y una tonelada de harina tipo II destinada a la venta genera una ganancia de 3 milsoles y requiere 2 operarios. Se dispone de 4 operarios.

cunto y qu tipo de harina se debe producir para minimizar los costos?


3434



35/63


35


36/63


36

Hemos visto hasta aqu las aplicaciones del modelo SIMPLEX aplicado a problemas

de maximizacin, sin embargo, encontraran ocasiones donde es necesariominimizar la funcin objetivo.

Ahora veremos el desarrollo del mtodo SIMPLEX aplicado a un modelo deminimizacin.Recordar que el mtodo SIMPLEX se aplica solo a modelos que tienen restriccionesdel tipo menor o igual.

Como primer paso debemos aplicar la forma estndar al modelo planteado, lo cualimplica tres condiciones:

La primera condicin : que los lado derecho de las restricciones sean constantesmayores o iguales a cero,en nuestro ejemplo los lado derecho de las restricciones ya son

constantes positivas.

La segunda condicin: que las inecuaciones sean expresadas en forma deigualdades usando variables de holgura,

en nuestro ejemplo estamos agregando las variables de holguraS1 y S2 a las dos restricciones.

La tercera condicin: que las variables que participan en el modelo sean mayores oiguales a cero (es decir que sean variables positivas)en nuestro ejemplo todas las variables son positivas.

36



37/63



Como se esta minimizando debemos seleccionar el coeficiente del Costo Reducidoms positivo para obtener nuestra columna PIVOT, para nuestro caso correspondeal valor 3 de la columna asociada a la variable X2, y es la variable que ingresa a labase en el segundo tablero.

37



38/63



Esto significa que en el segundo tablero debe salir de la base la variable S1 y sulugar debe ser remplazada por la variable X2.


tablero, para ello dividimos la fila de la variable S1 entre 1, ya que el elemento deintercepcin es 1 y colocamos el resultado en el segundo tablero en la posicin delrengln que le corresponde, y la variable S1 es reemplazada por la variable X2,generalizamos esta operacin para toda la fila.

38



39/63


asociado a la variable X2 en el segundo tablero, de la siguiente manera:

En el segundo tablero multiplicamos el valor UNO (el cul esta resaltado en la filade color rojo) por (-3) y luego sumamos el valor 3 de la fila de los coeficientesreducidos en el primer tablero, el resultado es cero y lo colocamos en la mismaposicin pero del segundo tablero, replicamos sta operacin para toda la fila conel valor del coeficiente reducido correspondiente del primer tablero.

39



40/63



Luego vemos que en el segundo tablero ya no existen mas costos reducidospositivos, entonces se ha llegado a la solucin final.

40



41/63

El segundo tablero nos da el tablero ptimo del cual obtenemos el vector solucin,

el cual est compuesto por a) las variables bsicas (son aquellas variables queestn en la columna base) las cuales obtienen su resultado de la columna solucin,y b) las variables no bsicas (aquellas variables que no aparecen en la columnabase) que asumen valor cero por default.


41



42/63


X1 asume un valor de 0 ,

X2 asume un valor de 4 , y

La funcin objetivo asume un valor ptimo de - 12

42



43/63


43


44/63

44

Los modelos de minimizacin con variables negativas, buscan modelar condiciones

donde las variables puedan asumir valores negativos, como por ejemplo lacondicin de cuantificar costos, desembolsos de un flujo de dinero, cuantificarperdidas, capital faltante, inventario faltante, entre otros casos; donde el resultadode la funcin objetivo es casi siempre obtener el menor costo y se aplican en laindustria , en los sistemas de comercializacin, sistemas financieros, transportes,sistemas de salud, en el sector de servicios pblicos, etc.

A continuacin mostraremos una formulacin asociado a un modelo matemtico

donde se ilustra el uso de variables negativas.

44



45/63


45

Ahora veremos el desarrollo del mtodo SIMPLEX aplicado a un modelo de minimizacin con

variable negativa.

Encontrarn ocasiones en donde el modelo requiere hacer uso de variables que puedan asumirvalores negativos y ser necesario hacer un reemplazo de variables.

Recordar que el mtodo SIMPLEX se aplica solo a modelos que tienen restricciones del tipo menor oigual.

Como primer paso debemos aplicar la forma estndar al modelo planteado, lo cual implica trescondiciones:La primera condicin : que los lado derecho de las restricciones sean constantes mayores o iguales

a cero,en nuestro ejemplo los lado derecho de las restricciones ya son constantes

positivas.

La segunda condicin: que las inecuaciones sean expresadas en forma de igualdades usandovariables de holgura,

en nuestro ejemplo estamos agregando las variables de holgura S1 y S2 a las dosrestricciones.

La tercera condicin: que las variables que participan en el modelo sean mayores o iguales a cero(es decir que sean variables positivas)

en nuestro ejemplo la variable Y esta definida como negativa, por lo tantodebemos realizar un cambio de variable,

Y debe ser igual a Y1, y hacemos el reemplazo en todo el modelo en su formaestndar.

45



46/63



Como se esta minimizando debemos seleccionar el coeficiente del Costo Reducidoms positivo para obtener nuestra columna PIVOT, para nuestro caso correspondeal valor 1 de la columna asociada a la variable Y1, y es la variable que ingresa a labase en el segundo tablero.

46



47/63



Esto significa que en el segundo tablero debe salir de la base la variable S2 y sulugar debe ser remplazada por la variable Y1.


tablero, para ello dividimos la fila de la variable S2 entre 1, ya que el elemento deintercepcin es 1 y colocamos el resultado en el segundo tablero en la posicin delrengln que le corresponde, y la variable S2 es reemplazada por la variable Y1,generalizamos esta operacin para toda la fila.

47



48/63


asociado a la variable Y1 en el segundo tablero, de la siguiente manera:

En el segundo tablero multiplicamos el valor UNO (el cul esta resaltado en la filade color rojo) por (-1) y luego sumamos el valor 1 de la fila de los coeficientesreducidos en el primer tablero, el resultado es cero y lo colocamos en la mismaposicin pero del segundo tablero, replicamos sta operacin para toda la fila conel valor del coeficiente reducido correspondiente del primer tablero.

48



49/63



Luego vemos que en el segundo tablero ya no existen mas costos reducidospositivos, entonces se ha llegado a la solucin final.

49



50/63

El segundo tablero, nos da el tablero ptimo del cual obtenemos el vector solucin,

compuesto por las variables bsicas ( son aquellas variables que estn en lacolumna base) las cuales obtienen su resultado de la columna solucin y lasvariables no bsicas (aquellas variables que no aparecen en la columna base)asumen valor cero por defoul .


50



51/63


X asume un valor de 0 ,

Y asume un valor de - 4 , y

La funcin objetivo asume un valor ptimo de - 4

51



52/63


52


53/63


53


54/63


54


55/63


55


56/6356



57/6357



58/6358



59/63


59


60/63


60


61/63


61


62/63


62


63/63


ejercicios- metodo simplex

Documents