• Author / Uploaded
• Maria Laura Gonzalez

Citation preview

UNIVERSIDAD DE ORIENTE NÚCLEO ANZOÁTEGUI EXTENSIÓN CENTRO SUR ANACO ESCUELA DE INGENIERÍA Y CIENCIAS APLICADAS DEPARTAMENTO DE INGENIERÍA INDUSTRIAL PROGRAMACION LINEAL - CÓDIGO: 0623223 SECCIÓN: 01 - PERÍODO: III-2018

METODO SIMPLEX DE PROGRAMACIÓN LINEAL

PROFESORA: ING. KEILA SALAS

BACHILLER: GONZÁLEZ M., MARÍA LAURA. C.I.: V-25.434.020. ANACO, ABRIL DE 2019

INTRODUCCIÓN. La Programación Lineal (PL) es una de las técnicas de la investigación de operaciones. Muchos autores consideran que ha sido uno de los más importantes avances científicos del presente siglo y, de hecho, su gran aplicación y la magnitud de todos los problemas que ha resuelto, así lo confirman. Mediante la utilización de la PL se han logrado ahorros millonarios en las organizaciones que la han aplicado. Los orígenes de la PL se remontan hacia la década del 40, cuando el economista Leontief desarrolla el método de análisis insumo-producto. En 1947, Stigler plantea el conocido “problema de la dieta”, el cual trataba de buscar la combinación de alimentos más barata, que permitiera a la persona tener los requerimientos mínimos de proteínas, vitaminas, minerales, carbohidratos, etc. Y es en este mismo año cuando el Dr. George Dantzig concluye su desarrollo del método simplex de solución de problemas de PL. Sin este método la PL nunca hubiera tenido el desarrollo y la aplicación desde 1950 hasta nuestros días. Sin embargo, el método simplex tampoco hubiera sido tan útil sin la valiosa ayuda de los computadoras digitales, los cuales permitieron resolver problemas de gran magnitud rápida y eficientemente (en un estudio realizado por la IBM se concluyó que aproximadamente el 25% del tiempo de computador se dedica a cálculo de PL y sus afines). El método simplex se ha venido aplicando aproximadamente desde 1950 y su utilización actual es extensa, aunque todavía existen problemas de tal magnitud, los cuales son muy difíciles de resolver incluso con las capacidades computacionales que existen actualmente, debido precisamente a su tamaño y al tiempo de computador que se utilizaría en ellos. Uno de estos problemas son los de las compañías aéreas, los de las refinerías de petróleo y los de optimización de cadenas de suministro, los cuales normalmente tienen un alto número de variables y restricciones. Varios procedimientos especiales han sido diseñados para estos problemas, los cuales generalmente descomponen el problema original en una

serie de subproblemas más fáciles de resolver. Igualmente, actualmente existen los denominados algoritmos de punto interior, los cuales compiten con el método simplex en algunos problemas y vienen implementados en el software especializado que resuelve modelos de programación lineal.

TEORÍA DEL MÉTODO SIMPLEX: 1.1. MÉTODO SIMPLEX En

optimización

matemática,

el

término

de

algoritmo

simplex

habitualmente se refiere a un conjunto de métodos muy usados para resol ver problemas, en los cuales se busca un máximo de una función lineal sobre un conjunto. El método simplex (MS) empieza con una función a minimizar y un conjunto de restricciones que normalmente no verifican estas condiciones. En la etapa reguladora se transforma el conjunto de restricciones en otro con términos independientes no negativos, y en la conocida como de iteraciones estándar se persigue conseguir coeficientes no negativos en la función transformada que debe optimizarse, mientras que al mismo tiempo se busca conservar los términos independientes no negativos. Si esto es posible, se obtiene la solución óptima. Si no, el problema es no acotado o no factible de variables que satisfaga un conjunto de inecuaciones lineales. El método simplex se aplica a un PPL en el formato estándar siguiente: Minimizar:

𝑓(𝑥 ) = 𝑐 𝑇 𝑥

(𝑐1 , 𝑐2 , … , 𝑐𝑛 )𝑇 objetivo,

sujeto a

𝐴𝑥 = 𝑏 ; 𝑏 ≥ 0

y

𝑥 ≥ 0.

Donde

𝑐=

es la matriz columna de los coeficientes de la función

𝑥 = (𝑥1 , 𝑥2 , … , 𝑥𝑛 )𝑇

iniciales, y A es una matriz

es el vector columna de las variables

𝑚 × 𝑛

que contiene los coeficientes de las

restricciones. Los teoremas de soluciones básicas, aseguran que la solución óptima de un PPL, si existe, se alcanza en una solución básica factible (un punto extremo). El MS genera una sucesión ordenada de soluciones básicas factibles que progresivamente mejora el valor de la función objetivo. El algoritmo simplex opera en dos fases:  Una etapa de iniciación en la que el conjunto inicial de restricciones de igualdad se transforma en otro equivalente del mismo tipo (restricciones de igualdad), asociado a una solución básica; y los valores de las variables básicas se transforman en valores no

negativos (se obtiene así una solución básica factible). Este proceso se llamará fase de regulación  Una etapa iterativa estándar, en la que los coeficientes de la función objetivo se transforman en valores no negativos y el valor del coste se mejora progresivamente hasta que se obtiene la solución óptima, no se detecta ninguna solución factible, o aparecen soluciones no acotadas. En este proceso iterativo, se calculan distintas soluciones básicas factibles. Para este fin se usa la operación elemental de la pivotación.

1.1.1. EL ALGORITMO SIMPLEX Este algoritmo trabaja con la matriz 𝑼(𝒕) hasta obtener la solución óptima o detectar la falta de puntos factibles o la no acotación. 

Entrada. La tabla inicial, {𝑼(𝟎), 𝒗(𝟎), 𝒘(𝟎), 𝒖(𝟎)} del PPL, conteniendo la función objetivo, y las restricciones del problema.



Salida. La solución del problema de minimización, o un mensaje advirtiendo sobre la no admisibilidad o la falta de acotación.

 ITERACIÓN REGULADORA I.

Iniciación. Si

𝒗(𝟎) ≥ 𝟎, seleccionar la variable entrante 𝒙𝜷 . Si no,

transformar 𝒗(𝟎) para que todos sus elementos sean no negativos. Con este fin, comprobar si existe una columna 𝜷 en 𝑼(𝟎) que verifique una de las dos condiciones

𝒖𝟎 𝒊𝜷 > 𝟎 𝒔𝒊 𝒗𝒊 𝟎 < 𝟎 { 𝟎 ∀𝒊 𝒖 𝒊𝜷 ≥ 𝟎 𝒔𝒊 𝒗𝒊 𝟎 ≥ 𝟎 Si la respuesta es afirmativa, continuar en la búsqueda del pivote. En otro caso, introducir la variable artificial

𝒙𝒏+𝟏 ≥ 𝟎, modificar el valor de la función objetivo,

sumando el término 𝑴𝒙𝒏+𝟏 , donde 𝑴 es una constante positiva grande, sumar el término 𝒙𝒏+𝟏 a todas las variables básicas, y elegir 𝒙𝜷 = 𝒙𝒏+𝟏 .

II.

Búsqueda del Pivote. Encontrar la fila del pivote α usando 𝒗∝ 𝟎 𝒖∝𝜷 𝟎

= 𝒎𝒊𝒏 𝟎

𝒗∝ 𝟎

𝒗𝒊