Credit image

¿Te gusta el diseño web? ¡Echa un vistazo a la documentación de LenguajeCSS.com!

El método Simplex Revisado

El método Simplex es un algoritmo descubierto por George Dantzig para resolver problemas de programación lineal. Aquí veremos la resolución de la versión computacional, el Simplex Revisado.

El método Simplex es un algoritmo de George Dantzig para resolver problemas de optimización (de la rama de programación lineal).

En este artículo voy a realizar el proceso paso a paso y de forma sencilla, utilizando el método Simplex Revisado, una versión computacional reducida del algoritmo, que puede que a varios compañeros que cursen esta asignatura les venga bien.

Identificar el problema

Es muy importante tener siempre presente con que tipo de problema estamos trabajando: mínimo o máximo (ya volveremos a esto más tarde), que las variables Xi con las que trabajamos son positivas, y que los beneficios no pueden ser negativos.

En este último caso, habría que cambiar de signo a toda la restricción implicada (con beneficio negativo).

Habría que contemplar además, el caso en el que las restricciones sean inecuaciones. Si así fuese, hay que tener presente el añadir la resta de una variable de excedente (inecuación mayor/igual) o añadir la suma de una variable de holgura (inecuación menor/igual), convirtiendo así las inecuaciones en ecuaciones.

Método de las dos fases

Partiendo de un ejemplo inicial (en rojo) vamos a realizar el llamado método de las dos fases.

Añadimos la suma de una variable artificial nueva por cada restricción (en este ejemplo X4 y X5) y reemplazamos la función objetivo por la minimización de la suma de todas las variables artificiales.

A su vez, y para cada una, crearemos una matriz A (la que empezaremos a usar) y una matriz B, que no es más que el valor de los coeficientes de las restricciones, sólo que la función objetivo, se desplaza a la última fila.

Debe notarse que en la matriz B también tiene los coeficientes de las variables artificiales (X4 y X5) en las restricciones.

Tabla inicial

Construiremos una tabla para ir resolviendo el problema, que constará de varias zonas:

  • Columna VB: En la primera columna (Variables Básicas), colocaremos todas las variables artificiales añadidas (en este caso sólo 2: X4 y X5). En la última fila, colocamos -w que representa que estamos en la fase 1.
  • B-1: La inversa de la base, que inicialmente no es más que la matriz identidad.
  • Columna derecha: Quedará siempre una columna vacía, donde se deberá rellenar con ceros, salvo la posición que pertenece a la última fila, que colocaremos un 1.
  • Constantes: Esta columna representa los beneficios asociados a la variable artificial de la restricción donde fue añadida.

Ahora vamos con las dos más peliagudas:

  • -CBt · B-1: Esta zona se el resultado de la multiplicación entre la traspuesta de los coeficientes de la base, en negativo (a la izquierda, en azul) y la inversa de la base de la tabla actual (B-1).
  • Vo: El valor objetivo de la tabla se calcula multiplicando las matrices correspondientes al punto anterior y a las constantes de las variables artificiales de la tabla actual.

Costos relativos

Cada vez que terminemos una iteración de la tabla (como ahora), deberemos calcular los costos relativos para saber si debemos continuar o ya tenemos una solución óptima.

Para calcularlos, multiplicamos la matriz A por la última fila (-w) de la tabla. Esto nos da una matriz con los costos relativos que deben ser:

  • Problema de mínimos: Los valores deben ser positivos (mayores o iguales a 0). Si son negativos, se optará por seleccionar el más negativo (regla de Bland).
  • Problema de máximos: Los valores deben ser negativos (mayores o iguales a 0). Si son positivos, se optará por seleccionar el más alto. Nota: Este problema concreto es de máximos, pero notar que estamos en la fase 1, que se convirtió en un problema de mínimos. Al salir de la fase 1, volverá a ser un problema de máximos de nuevo.

Quizás lo ideal sería realizar la regla lexicográfica para evitar el ciclado, ya que es más eficiente y requiere menos iteraciones. Aún así, en este caso usaremos Bland, ya que se ve más claro.

Variable entrante

Cómo se ve en la imagen anterior, en nuestro ejemplo seleccionamos -5 (de los candidatos -5 y -3), correspondiente a X1, por lo que extraemos de la Matriz A, la columna perteneciente a X1.

Es ahora cuando debemos multiplicar la Tabla actual (T1-1) por esta columna extraída y nos dará la columna pivote (C.P.) a utilizar para obtener la segunda tabla (T2-1).

Variable saliente

Sabemos que la variable entrante es X1, sin embargo, no conocemos cuál es la saliente. Para esto, lo que se hace es dividir los beneficios entre el número de la columna pivote y el valor más pequeño es el que saldrá de la base.

Calcular la siguiente tabla

Para conseguir la siguiente tabla, debemos convertir la columna pivote (C.P.) en la columna indicada en rojo, a su derecha.

Entonces, procederemos como se hace en las eliminaciones por Gauss-Jordan. En nuestro ejemplo, la primera fila se divide entre 3, obteniéndose una fila pivote (no confundir con columna pivote) que utilizaremos para reducir las demás.

La segunda fila se calcularía como: la segunda fila de la tabla T1-1 menos la fila pivote por 2. Idem con la tercera. Volveríamos al paso del cálculo de costos relativos, a una nueva iteración.

Seguiríamos actuando como hasta ahora, hasta que no podamos seleccionar variables entrantes (fila -w igual a 0 0 1), que es cuando concluiría la primera fase y empezaríamos la fase 2.

Fase 2

La nueva tabla T4-1 de la fase 2 será exactamente igual con respecto a las variables que están en la base, la base inversa (B-1), y la columna (0 0 1), pero es importante darse cuenta que volvemos al problema de máximos original, con su función objetivo original y a utilizar la matriz B en lugar de la Matriz A.

La última fila, pasa a convertirse de -w (fase 1) a -z (fase 2) y se pasa a calcular las siguientes zonas:

  • -CBt · B-1: Los valores siguientes (en verde) se calculan nuevamente, aplicando esta fórmula con los nuevos valores, donde CBt es ahora X1 y X3 en la función objetivo original y B-1, que también ha cambiado.
  • Ctes: Hay que actualizar los beneficios realizando la multiplicación de la tabla actual (T4-1) por las constantes del problema original, o sea la columna (12 8 0). Se puede ver también, que el valor objetivo se puede calcular de la forma indicada en azul.

Ahora solo tenemos que volver al paso del cálculo de los costos relativos (¡Ojo! Ahora con la matriz B), y seguir iterando hasta llegar al final.

En nuestro caso, hemos llegado al final porque todos los costos relativos son menores o iguales a cero (problema de máximos) y por lo tanto, se trata de una solución óptima no única para nuestro problema:

  • X1: 4 (está en la base)
  • X2: 0
  • X3: 0 (está en la base)
  • X4: 0
  • X5: 0

Al llegar a una solución óptima, debemos saber que si una de las variables básicas es 0, entonces el problema tiene más de una solución.

Se puede utilizar el siguiente Applet Java (de Timothy J. Wisniewski) para comprobar problemas con el algoritmo Simplex Revisado:

Escrito por Manz, el , en ingenieria. Comentarios recibidos: 22.

22 comentarios de lectores
santoscojones
santoscojones
1

........ Manz, son las 04:05 de la mañana.. me e lanzado y e investigado sobre George Dantzig y el método Simplex, mi mujer me a pillado ojeando la biografía de George y me a dicho: -"Cariño...ven a la cama y déjate de programaciones lineales que no son horas", ¡Que sábia es mi mujer¡¡ P.D.: Genial el post..sigue así macho que arás de mí un hombre, saludos artista¡¡¡

  • 1
Manz
Manz
2

¡Y es que todo tiene su momento y su lugar...!

Jeziel
Jeziel
3

hola!, oye, estudio la universidad en la EBC en la ciudad de México, la carrera de Banca y Finanzas, y vi este método (simplex) que de simple no tiene nada! jejeje ta complicado, pero despues nos enseñaron cómo resolver el mismo problema con un complemento de Excel llamado SOLVER, es muy sencillo de utilizarlo, y rápido!, en verdad lo recomiendo! les ahorrará mucho tiempo, así como reducir a "0" la posibilidad deun error!, saludos, y gracias por este apartado!

cesar avitia pall
cesar avitia pall
4

Pues yo pienso que estas matematicas tan complicadas no tienen un uso aplicable en la vida real. Son aplicables en ejercicios mentales matematicos para gente que le gusta quebrarse la cabeza en mundos virtuales mas no en mundos comunes como los que la humanidad esta dispuesta a manejar. es complicado. Lo malo es que necesito hacerme casi un experto en la materia por mis examenes de Investigacion de operaciones los cuales me da el catedratico doctor Jose Ramon Cuellar de la FIME. que quizas es bueno. pero no me convence de que tan saludable sea estudiar Investigacion de operaciones.

Vynka
Vynka
5

No me aparece el Applet, será por usar el Google Chrome?

  • 1
Vynka
Vynka
6

Y respondiendo a Cesar: Este método se aplica tras convertir un problema real a una expresión matemática como la que se presenta arriba; te debieron explicar algo similar en tu curso. El problema es una representación sobre el papel de una realidad formalizada, en definitiva: de un problema real formalizado.

  • 3
El chaki
El chaki
7

@cesar avitia pall: Pero claro que se ocupa en problemas reales, es para eso que fue creado, lo que pasa es que seguramente no te ha tocado utilizarlo en lo que es tu área de trabajo o simplemente no lo han aplicado, lo que podría ser dificil para algunos es crear la función objetivo y las restricciones que tenga tu problema, pero con la práctica se te hace una tárea sencilla. Lo he ocupado para resolver problemas de optimización de costos, proyectos de inversión, movimientos de equipos, etc. Saludos desde poza rica.

Juan
Juan
8

@Jeziel: Lo que usa excel por debajo, es seguramente el algoritmo del Simplex. Así que tú lo que estás usando es esto precisamente. Es normal que un algoritmo así para problemas grandes no lo hagas manualmente, si no que utilices un programa que lo tenga implementado...

carlos
carlos
9

el metodo simples es para minimizar y maximizar y el metodo de la doble fase es para minimizar. mi pregunta es cuando se que metodo voy a ocupar cuando minimizo.

GUSTAVO
GUSTAVO
10

me parece que esta mal tu simplex dual--------------- era la matriz transpuesta de las variables de restricción......................"fundamento: WHINSTON"

GUSTAVO ayala S
GUSTAVO ayala S
11

soy de Ingenieria Industrial de la "UMSA" de La paz-BOlivia............ y respondiendo a la pregunta de CARLOS............. usas max o min dependiendo de la situacion que quieras estudiar, un ejemplo podria ser (max z si quieres maximizar tu utilidad) ó (min z si quieres reducir tus costos)..................................

  • 1
joss
joss
12

tio yo tambien estudio Ingenieria Imformatica aqui en la ULL y he de decir que esto es un rollaso, aunque se agradece que lo intentes explicar =) un saludo

Cezar
Cezar
13

Hola, en tu tabla T2^-1 creo que tienes un error en el primer elemento de -w que tienes puesto 2/3, creo que es 5/3 por que para elimina -5 necesitas multiplicar 3 por 5/3 para que te de 5 y se lo sumes a -5 y te de 0. Saludos

Steven
Steven
14

Creo que hay un error en la fase I del problema. El error está en T3 ^-1 en la fila correspondiente a la variable básica X1 me da : 4/21 para la primera columna. Se comprueba si se hace x3/3 + x1,sería entonces: ((-1/7)/3) = -1/21 ,que sumandole 1/3 es 4/21 NO 2/7. Saludos.

Manz
Manz
15

@Cezar: En el paso -w de T2 se obtiene la fila pivote (1/3 0 0 4 1) y se multiplica por 5, resultando (5/3 0 0 20 5). Entonces se suma a la -w anterior (-1 -1 1 -20 -5), dando como resultado (2/3 -1 1 0 0). Creo que no hay ningún error en el proceso. @Steven: En el paso X1 de T3 se obtiene la fila pivote (-1/7 3/14 0 0 1) y se divide entre 3, resultando (-1/21 1/14 0 0 1/3). Entonces se suma a la X1 anterior (1/3 0 0 4 -1/3), dando como resultado (2/7 1/14 0 4 0). Creo que tampoco hay ningún error en el proceso. No obstante, pueden confirmar y revisar el problema con un applet del Simplex Revisado, y verán que el resultado es correcto. Saludos

jean claude van d
jean claude van d
16

yo pienso que solo son pajadas este monton de ejercicios que dejan en investigacion de mercado porque cuando uno va a trabajar en una oficina lo menos que uno hace es aplicar metodos simplex mas bien hay que aguantarle al jefe todas sus malacrianzas y pendejadas para poder mantener el puesto de trabajo, no estan de acuerdo?

  • 1
liz
liz
17

explicas el metodo de las dos fases!!! mas nunca el revisado!!! ¬¬

ero-sennin
ero-sennin
18

Tengo un maestro que a la de ahuevo quiere que lo hagamos en la libreta todos las tablas de la doble fase y el simplex ha visto en internet programas online para resolver estos problemas y en un segundo te dan la respuesta. Pero ni pex tengo que hacerla a la antigua por que, si no, no paso mi materia. jajjajajjaj pinches maestros ignorantes de la tecnologia creen que estamos en su epoca...ellos quebrandose la cabeza cuando tienes una solucion rapida fasil y segura a la mano

  • 2
Emmy
Emmy
19

Hola a todos estoy deacuerdo con sus comentarios, yo estoy estudiando en la U llevo la Clase d Investigaciones de Operaciones y me estoy quebraado la cabeza, quisiera que alguien m ayudara comentando alguna pagina mas resumida o mas clara.... exitos.

Fernando
Fernando
20

@cesar avitia pall: Hola Cesar. Soy graduado de Ingeniería Civil Industrial. Te comento que estás equivocado, ya que tiene muchísimas aplicaciones que se utilizan mucho en modelamiento matemático, por ejemplo, para localización óptimas de recursos, plantas, servicios de urgencia, comisarías, etc. También se aplica a modelamiento matemático a un sistema de redes, tales como cañerías, redes del metro, instalaciones de servicio de autobuses, y una infinidad de otras más. El método Simplex Revisado es una forma computacional de resolver este tipo de ejercicios, que permite que la solución se encuentre por computador mucho más rápida (hay métodos conencionales que por computador te puedes demorar días y hasta semanas en obtener una respuesta). Saludos desde Santiago, Chile.

  • 1
max
max
22

@cesar avitia pall: pobre wn se nota que eres ignorante

Publica tu opinión

Si lo deseas, puedes utilizar el siguiente formulario para publicar tu opinión o responder a alguna de las existentes:

Previsualización

Aquí se previsualizará su comentario. Revise que sea correcto antes de publicarlo.