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

thesis help NZ
54

Are you looking for thesis help in New Zealand? We are here to help you, we provide thesis help NZservices at a very low price. You can hire our experts to visit the website nzassignmenthelp.com. Here our experts help you to write your thesis 100% accurately at a very reasonable price.

Assignment Help
57

Assignment Help has been on this stage for many years now to provide UAE assignment help services to students in various courses which are exclusively available on Greatassignmenthelper.com. Students looking for UAE assignment help can always rely on our experts as being proficient, they also guide you through learning the subject. https://greatassignmenthelper.com/ae/

Assignment Help
60

Need help with writing a term paper? Malaysia Assignment Help in term paper writing help to all University and College learners of Malaysia. No matter where you reside in Malaysia, you can seek term homework help from our professional writers.

QQi assignment help
61

Are you worried about your carrier and you don't have enough time to complete the assignment. don't worry you should take QQi assignment help. We have well experienced writer who having years of expericence in assignment service. Our assignment writer ensures you to deliver your assignment on time at cheap price.

johnny santiago
62

If you are in an urgent need of reliable and reasonably priced Psychology assignment help, you just have to connect with our experts at Help in Homework via our website helpinhomework.org and hand over your tedious assignment to them. Our experts will proficiently research, diligently write, and systematically structure your Psychology assignment ensuring strict compliance with the rules you share. Your assignment will certainly fetch you the perfect A grade and make you the star of your class, that too, at a very affordable rate. You don’t have to worry anymore about your assignments as you have Help in Homework at your beck and call.

cipd assignment help
63

Anyone faces problems in completing their cipd assignments, so don’t get stressed, take cipd assignment help from our top website by hiring our experts and get your cipd assignment done on time at a low price. Our experts are available 24*7 for you.

Assignment help
64

If your college started a competition and you want the best essay writer, then choose Malaysiaassignmenthelp.com. We provide you with best-in-class essay writers and are ready to assist you 24*7. Check us out at:- do my essay.

Nelson Lima
65

If you are management, nursing student if you and your friend don’t have knowledge thesis. then you should take thesis writing service in Irelande from qqi assignments. QQi assignment is most trusted assignment company of Ireland. Company have well educated writers who write your thesis on schedule which is free form any kind of mistakes.

 dramatic irony
66

There are three types of irony 1 is verbal irony, 2 is situational and 3 is dramatic irony learn 5 most effect dramatic irony in assignment reveal a character's feeling, add humor, create empathy, grab the reader's attention and allow the unknown character.

Assignment Help
70

This is an excellent piece of writing. At long last, something new and intriguing to read. Laying such a foundation without professional assistance is difficult. Contact assignment help service gives perfect assignment work to professionals and students worldwide if you want to achieve the same level of success. Coursework Help Research Paper Writer Proofreading Service Presentation Maker Project Management Assignment Help Cheap essay writing service Dissertation writing service

Assignment Help
72

When you are looking for an assignment help writing service in Singapore. Great Assignment Help is the online assignment help service provider for you. We are best known for delivering quality assignment writing services to students without having to break the lines.

Dissertation writing
73

Nowadays students don't have time and they don't want to read many books so they find it difficult to write a well-structured and researched dissertation. Don't worry you can take help from student assignment help UK. We provide Dissertation assistance online help by certified and experienced experts from top universities they deliver Dissertation writing help uk at a very cheap price with 100% guarantee and 24*7 assistance.

Assignment helpers
74

Doing assignments is like moving a mountain of trouble. It takes a lot of effort to think assemble and jot down all your ideas on a piece of paper. It really is a troublesome experience when it comes to assignments and the deadlines are very close. This is the place where greatassignmenthelper.com. Our assignment helpers make sure to do all to your good. Several Students have benifitted from this service.

gourideb
77

Thank you for another excellent article. Where else could anybody get that kind of info in such an ideal way of writing? I’ve a presentation next week, and I am on the look for such information. english stories

cipd assignment writ
79

 If you are running out of ideas/thoughts and are having difficulty completing your cipd assignment and are looking for cipd assignment writing help in dubai, uaeassignmentshelp.com has a wonderful team of expert writers available. Here, your job is completed on schedule, and our services are available 24 hours a day, seven days a week.

Adele Hansley
81

Thanks for sharing, Sample assignment is the best assignment experts that provides CHC33015 Assessment Answers. Due to many different reasons, such as less time, subject knowledge etc, university students find it complex to craft their assignments on time.

Coursework Help
85

Are you looking for someone to do your nursing assignment help UK? We have a dedicated team of qualified experts that provide the best help with assignments to boost your grades. Get free consultancy now with our experts and boost your grades to achieve your desired results in your academics.

Buy Essay Uk
86

There is no issue buying essays online for your academics you just ask for help to boost your grades, so buy essay online from assignment editors pro that provides the best consultancy to students and academic professionals.

masonethan
87

coursework help is a good solution which is better and free for your research work. Coursework is one of the many forms of academic papers that college and university students must produce. To write a dissertation, students usually have to conduct independent research on a particular topic, presenting both a theoretical background and their own scientific findings. The main difficulty in writing a dissertation is the need to present an in-depth analysis of a topic that is relevant and needs investigation. Also, it is essential to follow the topic accurately and develop informative independent research on it. It means that you have to develop a coherent and consistent work that combines your theoretical knowledge and practical skills. so always choose the best online Coursework.

singaporetranslators
90

If you want to compile the quality of your academic translation you can rely on the Singapore translators. They have a team of Doctorate or Masters’ degree holders who have great experience in the profession of translating and writing. By getting help from them you can easily get Singapore translation services for various kinds of documents like legal, medical, business, academic at very reasonable prices.

andrew symond
91

Choose proofreading services when you have no one to ask your concerns while studying at Singapore universities. Students can connect with professional academic writers using online assignment writing services and discuss their concerns even staying at home. You don’t need to make any physical contact with anyone when you have the option of online services.

andrew symond
92

Choose proofreading services when you have no one to ask your concerns while studying at Singapore universities. Students can connect with professional academic writers using online assignment writing services and discuss their concerns even staying at home. You don’t need to make any physical contact with anyone when you have the option of online services.

QQi Assignments
96

Lots of workload of essay or dissertation assignments, looking for help in completing your assignments in ireland then hire qqi assignments ireland help you in completing your assignment and gives you original content at affordable prices with the help of our top notch experts.

evajames
97

Writing computer programs is an extreme subject. Dialects like C++, Java, Python, ASP.Net, Database and more make this course extremely intricate. The arrangement of codes and system are not every some tea. That is the explanation, numerous understudies search for an expert Programming Help who will compose programming assignments for their sake.

ghfhgfh
99

In a passage from Adam Smith’s book “inquiry on the cause and nature of wealth of nations” he felt that society operated on the mechanism that everyone yearns to get wealthy and must therefore exchange his produce with those who value it. https://theologyassignmenthelp.com/ https://essaybaron.com/ https://computerscienceassignmenthelp.com https://capstoneprojecthelponline.com/ https://articlewriterhub.com/ https://contentwriterforhirehub.com/ https://contentwritingservicesonline.com/ https://freelancewriterforhireonline.com/ https://ghostwriterforhireonline.com/ https://writemyassignmentsforme.com/

stevensmithau
100

Today, it is not uncommon to see students who are struggling with their essay writing assignments. They may not have the time to devote to their studies and they may also lack the necessary skillset. Essay writing services are here to help these students overcome this issue. Essay writing services provide a wide range of academic assistance for all levels of education, from high school through postgraduate programs.

1 2 3

Publica tu opinión