Solución de Problemas de programación Lineal

Resumen.

En este trabajo se investigó el Método Simplex, Método Grafico, Modelo de Transporte o Asignación, Método de Vogel y el Modelo Húngaro, y se estudió su aplicación mediante ejemplos. Se pudo observar que estos métodos y modelos tienen un gran campo de aplicación y su desarrollo no requiere de complejos cálculos sino de numerosas iteraciones.

Palabras Claves: Programación Lineal, Método, Modelo, Solución Óptima.

1. Introducción

Programación lineal es una técnica matemática que tiene por finalidad determinar soluciones óptimas para problemas en los que se requiera utilizar recursos disponibles para lograr un objetivo. (1)  Es un modelo matemático que establece la asignación fija de recursos satisfaciendo las condiciones y restricciones establecidas. (2) Esta técnica tiene varios campos de aplicación desde las ciencias sociales, hasta la agricultura, transporte e industria. Además la programación lineal es la base para el desarrollo de otros algoritmos utilizados en la solución de problemas de investigación de operaciones. (3)

Existen varios métodos para solucionar los problemas de programación lineal, el presente trabajo se centrara en exponer el Método Simplex, Método Grafico, Modelo de Transporte o Asignación, Método de Vogel y el Modelo Húngaro.

2. Objetivos

Investigar y comprender distintos métodos para la solución de problemas de programación lineal y su aplicación en la industria.        

3. Desarrollo del trabajo

3.1. Solución de problemas de programación lineal

Los problemas de programación  lineal por lo general tienen la siguiente estructura:

1. Objetivo a alcanzar (beneficio máximo, coste mínimo, etc.).
2. Numerosas variables (horas hombre, precio, número de unidades).
3. Interacción entre variables
4. Presencia de restricciones (por ejemplo, se pude especificar un número mínimo de unidades producidas, aun sin tener en cuenta el beneficio.

De forma tal que la programación lineal se asocia a situaciones complejas, variables que se interrelacionan, restricciones que son contradictorias al objetivo principal del problema, además del objetivo principal que suele ser la optimización de algún criterio de efectividad del sistema. (1)

Para solucionar problemas de programación lineal se procede de la siguiente manera

• Comprensión del problema, es importante comprender e identificar el objetivo principal.
• Definición de las variables, representar las variables que formaran parte del modelo matemático.
• Formulación de la función objetivo, definir el objetivo que se quiere lograr mediante una formulación matemática.
• Planteamiento de las restricciones, debido a la presencia de actividades competitivas, es necesario que se formulen condiciones con las que se debe cumplir para resolver el problema.

La definición de variables, la formulación de la función objetivo y el planteamiento de restricciones, no obedecen a un orden especifico de ejecución, sin embargo debe tenerse en cuenta q las restricciones, así como, la función objetivo deben ser de tipo lineal. (2)

3.2. Método grafico

El método grafico es una alternativa a la solución de problemas que presentan dos variables de decisión. Estos problemas se resuelven al  representar gráficamente cada una de las restricciones en un eje de coordenadas, la intersección del conjunto de restricciones da como resultado un polígono, el mismo que se identifica como el área de soluciones factibles o conjunto solución, encontrándose la solución óptima del problema en uno de los vértices de dicho polígono. (4)

Los problemas de programación lineal se resuelven por método grafico de la siguiente manera:

• Primero se definen las variables, se determinan las restricciones y se establece la función objetivo.
• Se grafican las desigualdades del conjunto de restricciones. La zona delimitada por las restricciones es el conjunto solución.
• Desplazar la función objetivo paralelamente a la dirección de optimización hasta el punto  antes que la recta proyectada abandone el área de soluciones factibles, y solo en el caso en que la línea imaginaria no corte esta zona se ha encontrado el punto de la solución óptima. Para encontrar el valor de las variables se recurre a la ecuación de ecuaciones lineales. (1) (4)

Ejemplo.

Variables: x1, x2

Restricciones:  [pic 1]

                     [pic 2]

                     [pic 3]

Función objetivo:  [pic 4]

[pic 5]

Figura 1. Solución de problemas de programación lineal por el método gráfico.

Dada las ecuaciones de las restricciones se calcula los valores para las variables en dicho punto.

 [pic 6]

         [pic 7]

[pic 8]

 [pic 9]

---------------------------------------

                     [pic 10]

[pic 11]

[pic 12]

3.3. Método Simplex

El método simplex es un método iterativo de solución de problemas de programación lineal que permite resolver modelos complejos sin restricción en el número de variables. (4)

La naturaleza iterativa del método simplex no permite el incremento simultáneo de las variables. En cambio, incrementa una a la vez. En la figura se puede apreciar el espacio de soluciones para un problema particular con una función de optimización . El método simplex incrementará la variable que tenga el mejor grado de mejora a , en este caso . La figura muestra que se debe incrementar hasta llegar al punto B. En la siguiente iteración se debe incrementar  hasta llegar a C. (3)[pic 13][pic 14][pic 15][pic 16]

...