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]

[pic 17]

Figura 2. Proceso iterativo del Método Simplex

La trayectoria del algoritmo es ABC. Lo que significa que cada iteración del método simplex está asociada a un punto. Además, este método se mueve por los bordes, lo que significa que no se puede ir del punto A al C.[pic 18][pic 19]

Para ver la aplicación del método simplex, se aplicará a un ejemplo tomado de (3).

Reddy Mikks produce pinturas para interiores y exteriores con dos materias primas,  y . La tabla siguiente proporciona los datos básicos del problema.[pic 20][pic 21]

[pic 22]

Una encuesta de mercado indica que la demanda diaria de pintura para interiores no puede exceder la de pintura para exteriores en más de una tonelada. Asimismo, que la demanda diaria máxima de pintura para interiores es de dos toneladas.

Reddy Mikks se propone determinar la (mejor) combinación óptima de pinturas para interiores y exteriores que maximice la utilidad diaria total.

El modelo completo de Reddy Mikks es

Maximizar [pic 23]

Sujeto a

[pic 24]

[pic 25]

[pic 26]

[pic 27]

[pic 28]

Primero hay que convertir las restricciones en ecuaciones con el uso de unas variables denominadas de holgura y exceso. Estas suelen estar representadas por la letra , se suman si la restricción es de signo  y se restan si la restricción es de signo .[pic 29][pic 30][pic 31]

Maximizar [pic 32]

Sujeto a

[pic 33]

[pic 34]

[pic 35]

[pic 36]

[pic 37]

A continuación, se escribe la ecuación objetivo como

[pic 38]

Así, se puede representar la tabla simplex inicial como

[pic 39]

Figura 3. Tabla inicial Simplex

La tabla da la solución inicial que se inicia en el origen , por lo que  se definen como las variables no básicas y  como las variables básicas. La variable objetivo  y las variables básicas aparecen en la columna “Básica”. En la columna “Solución” se dan sus valores; es decir, , , , , . [pic 40][pic 41][pic 42][pic 43][pic 44][pic 45][pic 46][pic 47][pic 48]

La función objetivo puede mejorarse si se incrementa una de sus variables. En la tabla simplex donde la ecuación aparece como  , se selecciona la variable no básica con el coeficiente más negativo en la ecuación objetivo, . Esto se conoce como la condición de optimalidad simplex. La variable  se conoce como la variable de entrada.[pic 49][pic 50][pic 51]

Si  es la variable de entrada, una de las variables básicas actuales debe salir. La mecánica para determinar la variable de salida implica calcular las relaciones del lado derecho de las ecuaciones (columna Solución) con los coeficientes de restricción estrictamente positivos bajo la variable de entrada, , como se muestra [pic 52][pic 53]

...