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.

• Prueba de optimalidad

• Óptimo si y solo si cada coeficiente en la fila 0 es no negativo

El método simplex es un procedimiento algebraico ya que cada iteración debe tener al menos una solución en un sistema de ecuaciones para conseguir una nueva solución ideal, que se le aplica la prueba de optimalidad. Lo que tiene es una interpretación geométrica útil para la interpretación. En el caso de necesitar grafica se utilizan métodos geométricos.

• Iterar (si es necesario) para obtener la siguiente solución

• Determinar la entrada y salida de variables básicas.
• Prueba de relación mínima

Una Comparación de la Forma Tabular y Algebraica se Observa en el (anexo 2).

Ruptura de Empates en el Método Simplex

• Empate para la variable básica entrante

• La decisión puede tomarse arbitrariamente.

• Empate para la variable básica saliente

• Importa teóricamente, pero rara vez en la práctica.
• Elija arbitrariamente.

• Condición de no dejar la variable básica

• Z es ilimitado.
• Señala que se ha cometido mal la interpretación.

• Varias soluciones óptimas

• El método simplex se detiene después de encontrar una solución método simplex óptima.
• A menudo existen otras soluciones óptimas y serían opciones significativas.
• Existe un método para detectar y encontrar otras soluciones óptimas de método simplex.

Adaptación de Otras Formas de Modelo

• Ajustes del método simplex

• Necesario cuando el problema no está en forma estándar.
• Realizado durante el paso de inicialización.

• Técnica variable artificial

• Variable ficticia introducida en cada restricción que necesita una.
• Se convierte en la variable básica inicial de esa ecuación.

• Tipos de formularios no estándar.

• Restricciones de igualdad.
• Lados derechos negativos.
• Restricciones funcionales en forma mayor o igual a.
• Minimizar Z.

• No hay soluciones viables

• La construcción de una solución factible artificial puede conducir a una solución óptima falsa.
• La técnica de variable artificial proporciona una forma de indicar si este es el caso.

• Se permite que las variables sean negativas

• Ejemplo: el valor negativo indica una disminución en la tasa de producción.
• Los valores negativos pueden tener un límite o ningún límite.

Análisis Posóptimo

• Re optimización

• Alternativa para volver a resolver el problema con pequeños cambios.
• Implica deducir cómo los cambios en el modelo se trasladan al cuadro final simplex.
• Solución óptima para el modelo revisado:

• Estará mucho más cerca de la solución óptima anterior que dé una solución óptima inicial construida de la manera habitual.

• Precio sombra

• Mide el recurso opcional del problema planteado marginando los errores
• La tasa a la que Z aumentaría si pudiera disponerse de más recursos
• Dado por el coeficiente de la i- enésima variable de holgura en la fila 0 del cuadro simplex final.

• Análisis de sensibilidad

• Finalidad: identificar los parámetros sensibles:

• Estos deben estimarse con especial cuidado.

• Se puede hacer gráficamente si solo hay dos variables.
• Puede realizarse en Microsoft Excel.

• Programación lineal paramétrica

• Estudio de cómo cambia la solución óptima cuando muchos de los parámetros cambian simultáneamente en algún rango.
• Se utiliza para la investigación de compensaciones en los valores de los parámetros.

Implementación por Computadora

• Método simplex ideal para su ejecución en una computadora.
• Código de computadora para el método simplex.

• Ampliamente disponible para todos los sistemas modernos.
• Sigue el método simplex revisado.

• Factor principal que determina el tiempo de solución.

• Número de restricciones funcionales.

• Regla de oro: el número de iteraciones necesarias es igual al doble del número de restricciones funcionales.

Enfoque del Punto Interior para Resolver Problemas de Programación Lineal         

• Alternativa al método simplex desarrollado en la década de 1980

• Mucho más complicado

• Utiliza un enfoque iterativo que comienza con una solución de prueba factible

• Las soluciones de prueba son puntos interiores

• Dentro del límite de la región factible

• Ventaja: los problemas grandes no requieren muchas más iteraciones que los problemas pequeños

• Desventaja

• Capacidad limitada para realizar un análisis postoptimal.

• Enfoque: cambiar al método simplex.

Como se observa en el (anexo4).^[c]

CONCLUSIONES

• Método simplex

• Enfoque eficiente y confiable para resolver problemas de programación lineal.
• Procedimiento algebraico.
• Realiza análisis postoptimal de manera eficiente.
• Pasa de la solución óptima actual a una mejor solución óptima.
• Mejor realizado por computadora, excepto para los problemas más simples.^[d]

Anexos

[pic 1]

 (Anexo 1).

[pic 2]

(Anexo 2).

...