Solución de Problemas de Programación Lineal: Método Simplex

Solución de Problemas de Programación Lineal: Método Simplex

Richard Esmith Gaviria Huanio

Carrera Profesional de Ingeniería de Sistemas, Facultad de Ingeniería de sistemas e Ingeniería Civil, Universidad Nacional de Ucayali

EEIDO14: Investigación de Operaciones I

Dr. Jorge Luis Hilario Rivas

Evaluación Según su Finalidad: Sumativa

Evaluación de Acuerdo A Su Extensión: Parcial

Evaluación Según Quien lo Realiza: Heteroevaluación

Evaluación de Acuerdo al Momento Del Proceso: Continua

EJERCICIO Individual

10 de octubre del 2020^[a]

El método Simplex ^[b]es un enfoque para resolver modelos de programación lineal a mano utilizando variables de holgura, tablas y variables de pivote como un medio para encontrar la solución óptima de un problema de optimización. Un programa lineal es un método para lograr el mejor resultado dada una ecuación máxima o mínima con restricciones lineales. La mayoría de los programas lineales se pueden resolver usando un solucionador en línea como Matlab, pero el método Simplex es una técnica para resolver programas lineales a mano. Para resolver un modelo de programación lineal utilizando el método Simplex son necesario seguir cuidadosamente sus pasos.

El método Simplex se utiliza usualmente para determinar manualmente el valor óptimo de un problema en modelado simplex. El método produce una solución óptima para satisfacer las restricciones dadas y producir un valor zeta máximo. Para usar el método Simplex, un modelo de programación lineal dado debe estar en forma estándar, donde luego se pueden introducir variables de holgura. Usando las variables de tabla y pivote, se puede alcanzar una solución óptima.

Las implementaciones informáticas estándar del método simplex de Dantzig para la programación lineal se basan en formar la inversa de la matriz básica y actualizar la inversa después de cada paso del método. Estas implementaciones tienen malas propiedades de error de redondeo. Este artículo proporciona los antecedentes teóricos para una implementación que se basa en la descomposición método simple se calculada con intercambios de filas, de la matriz básica. La implementación es lenta, pero tiene un buen comportamiento de error de redondeo. La implementación aparece como algoritmo CACM 350.

La mayoría de los problemas de programación lineal del mundo real tienen más de dos variables y, por lo tanto, son demasiado complejos para una solución gráfica. Se puede usar un procedimiento llamado método simplex para encontrar la solución a problemas multivariables. El método simplex es en realidad un algoritmo (o un conjunto de instrucciones) con el que examinamos los puntos de las esquinas de manera metódica hasta llegar a la mejor solución: mayor beneficio o menor costo. Hay programas informáticos y hojas de cálculo disponibles para manejar cálculos simplex para usted. Pero necesitas saber qué hay detrás de escena para poder comprender mejor sus valiosos resultados.

La Esencia del Método Simplex

Terminología:

• Límite de restricciones una línea que forma el límite de lo que es permitido por la correspondiente restricción. (en la figura podemos ver cinco fronteras).
• Soluciones de esquina: son intersecciones de restricción fronteras.
• Soluciones factibles de esquina (Cinco puntos en las esquinas factibles) son soluciones de esquina que se encuentran en la región factible.
•  Estas incluir (0,0), (0,6), (2,6), (4, 3), y (4,0) soluciones inviables de punta de esquina son soluciones de punta que mienten fuera de la región factible.
•  Estas incluir (0,9), (4, 6), (6, 0)
• Procedimiento algebraico.
• Los conceptos subyacentes son geométricos.
• Ejemplo de Revisitar Wyndor.
• Los puntos de intersección son soluciones de puntos de esquina.
• Cinco puntos en las esquinas de la región factible son soluciones.
• Soluciones Cinco puntos en las esquinas factibles y/o adyacentes.
• Compartir un límite de restricción.

Como se observa en el (anexo1)

Preparación para El Modelo Simplex

Forma estándar del problema de programación lineal En preparación para el uso del método Simplex, es necesario expresar el lineal Problema de programación en forma estándar. Para un programa lineal con n variables y restricciones, usaremos la siguiente forma estándar

Para demostrar el método simplex, considere el siguiente modelo de programación lineal:

Este es el modelo para el problema de Leo Coco presentado en la demostración, Método gráfico. Esa demostración describe cómo encontrar la solución óptima gráficamente, como se muestra a la derecha.

Así, la solución óptima es y ahora describiremos cómo el método simplex (un procedimiento algebraico) obtiene esta solución algebraicamente.

Primer paso: convertir las restricciones de desigualdad funcional en restricciones de igualdad:

• Hecho mediante la introducción de variables de holgura
• Forma resultante conocida como forma aumentada
• Ejemplo: la restricción 𝑥1 ≤ 4 es equivalente a 𝑥1 + 𝑥3 = 4 y 𝑥3≥0

Como se observa en el (anexo 3).

El Método Simplex de forma tabular

• Forma de tabla

• Registra solo la información esencial:
• Coeficientes de las variables
• Las constantes tienen que estar en el margen derecho de las ecuaciones
• La base o la  variable básica del problema planteado

Resumen del método simplex

• Inicialización

• Introducir variables de holgura:

El primer paso será introducir variables de holgura, una para cada una de las restricciones (excepto las restricciones de positividad). Estos son simplemente la diferencia entre el lado derecho y el lado izquierdo de una restricción. Por ejemplo, para la primera restricción definimos una variable de holgura x4=14-2x1-x2-x3. En términos de esta nueva variable, la primera restricción es equivalente simplemente a x4 ≥0, la restricción de positividad para x4.

...