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.

¡Ojo! Hago directos en Twitch sobre desarrollo web, ¿Te apuntas? ManzDev

ingenieria
138

Escrito por

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

simplex revisado partes identificar

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.

simplex planteamiento problema

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.
simplex revisado tabla inicial

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.

simplex revisado costos relativos

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.

simplex revisado saliente

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.

simplex revisado siguiente tabla calculo

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.

simplex revisado costos relativos

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.

simplex revisado iteración 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.

simplex revisado fase 2

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:

RELACIONADOS Google Webmaster trolls RELACIONADOS Aún no puedo creer que tengas algo que ver con ese tío RELACIONADOS Introducción a las expresiones regulares
x Google Webmaster trolls
Manz

138 comentarios

1 2 3

Network Assignment h
102

The assignment seasons are on and troublesome weeks lie ahead. greatassignmenthelper.com is here for your help. The Network Assignment Help is ready to aid those who need it. I had a fantastic experience working with them, hope you like their work as well. They do all assignments on a very short notice and at very pocket friendly cost. Giving them my assignment was like getting assured of an A+ after my submission.

qqi assignments
103

Scary deadlines are close but assignments work is still not completed, don’t worry, and just hire qqi assignments Ireland services to get professional assignment writers and get your assignments completed with 100% plagiarism-free and unique content. We provide you services like Essay writing service, dissertation writing, write my essay, and many more. So, hurry up and visit the website qqi assignments for hiring our services.

Essay Writer
105

If you are looking for a Cheap Essay Writer, you can get that only at Best Assignment Experts. We know that other assignment delivery sites charge extra high prices for their services.

Benefit Of Decision
107

Thanks for your good post. Are you looking for management assignment help online? Get business planning and management assignments from top experts at the highest quality.

qqi assignments
109

If you are stuck in your assignments and looking for someone who helps you in completing your assignments, then hire qqi assignments services. We have a professional team of writers that provide you 100% original assignment content at very lower prices and provide you services like Essay Writing, Thesis Writing, Write my assignment and many more.

Exppress
111

Nice, What an Excellent post. Exppress Car Wash is offering you a very potential car wash franchise business. It can be set up with automatic equipment on a very busy road. If owning one’s own business is your dream then, we offer an opportunity to achieve the benefits of business ownership.

sanjupawar
113

Follow for some trending topics which has been going viral in India. Also know which are the best youtube videos in India. In quest to know what are the trending topics in india? Get all the latest topics here and know which trends are going viral here. viral news

Exppress Car Wash
114

Thanks for sharing this informative information with us. To get India-based automatic Car Detailing services just make contact with Express Car Wash which is providing relevant car wash services with the latest techniques and offering car wash franchise opportunities to the customers in Noida, Delhi NCR in India.

drago wark
115

maths is very intresting subject .but some childrens don`t like math.so,for make it intresting we can play games with our childrens which is related to maths subject. follow VPN for PUBG Mobile this side for know about games more and more.

Yatherm Scientific
118

Thanks for sharing this informative information with us. Let’s now talk about ultra-low temperature freezer as this is also a refrigerator but what makes it unique is the lowest temperature it can go to keep the goods inside safe.

IT Assignment Help
122

In today’s world people are very much stucked in their personal works, same is happening with the students that’s why we have strated the services of the IT Assignment Help. Connect with us to avail this premium offer.

Economics Assignment
123

Economics assignment helper can help you with all your assignment-related woes. You may get economics quiz assistance online, as well as assignments, exams, and midterms. Not only economics as the subject but all the three subcategories of economics that are microeconomics, macroeconomics, and managerial economics, are also grasped by our experts who have multiple years of experience. Plagiarism-free content written by assignment experts is guaranteed to give you the highest grades; this is our promise to you. We also have a very flexible policy if you choose to examine. But rest assured that our service is sure to leave you satisfied.

Kaylee Brown
124

Economics assignment helper can help you with all your assignment-related woes. You may get economics quiz assistance online, as well as assignments, exams, and midterms. Not only economics as the subject but all the three subcategories of economics that are microeconomics, macroeconomics, and managerial economics, are also grasped by our experts who have multiple years of experience. Plagiarism-free content written by assignment experts is guaranteed to give you the highest grades; this is our promise to you. We also have a very flexible policy if you choose to examine. But rest assured that our service is sure to leave you satisfied.

custom CBD boxes
125

We Take Every Single Business Deal Seriously! Our deals related to CBD Packaging Boxes are no joke for us. We can assure every business when they choose us, they will only benefit. We aim at increasing the sales in a way the business gets maximum return and demand of products.

internet modeling
127

BMS Models is one of the most experienced, competent, cutting-edge modeling agencies in the world. Our models specialize in related niches such as Anime Cosplay, Fitness, Online Gaming, and more! Join us today!

live cam girls
129

Get connected with live cam girls worldwide for live adult cam chat here at MyCamCandy. MyCamCandy.com is the fastest growing online community where you can meet models for free adult cam chat or video chat 24/7 on private cams.

andrew symond
132

Singapore Assignment Help provides the best cheap university assignment help . Here you will get assignment help from our experts and assist you in all the stages either online or by email based before the agreed deadlines. Our experts will do your assignment and give you assignment help that will cover all your requirements given during the assignment submission.

Assignment Helper
134

If you are feeling overloaded with the regular assignment topics and deadline is lurking over your head then gets Assignment Helper. Whatever, be the reason you have to look for the professional writer to guide you for completing the answers on time.

Alen Steward
137

Get the best computer science homework help and accelerate your process of learning and scoring in college. The experts are highly qualified and have in-depth knowledge of the subject. They provide plagiarism free and timely guidance for all college tasks. The work is always to the point.

1 2 3

Publica tu opinión