Introducción a la programación lineal.

He empezado a estudiar un poco de optimización lineal y me ha parecido un tema bastante interesante, sobretodo el método SIMPLEX.

En esta entrada voy a tratar de explicar la estructura de un problema de programación lineal y los tipos de soluciones que existen.

Pero antes de eso tenemos que hablar de los conjuntos convexos puesto que son unas de las bases de álgebra que hay que conocer para poder comprender los problemas programación lineal.

• Conjuntos convexos:

• Combinación lineal convexa:

SI tenemos los puntos P1, P2, ... , Ph de un espacio afín de dimensión m, se dirá que el punto P es una combinación lineal convexa de ello si existen h escalares λ1, λ2, ... , λh tales que:

• Segmento:

Un segmento de extremos P1 y P2 es el conjunto de todas las combinaciones lineales convexas de los puntos P1 y P2.

• Conjuntos convexos:

Un conjunto C es convexo si y sólo si para cualquier pareja de puntos P1 y P2, de C, cualquier combinación lineal convexa de éstos es también un punto de C. Es decir, un conjunto es convexo si contiene al segmento que une cualquier pareja de puntos de éste.

Gráficamente y en una espacio afín de dimensión 2 (el plano) quedaría así:

• Vértice:

Un punto P de un conjunto C es un vértice si no puede expresarse como combinación lineal convexa de otros dos puntos cualesquiera de C distintos de P.

• Máximo de una función lineal:

Toda función lineal definida sobre un conjunto convexo tomará sus valores máximo o mínimo sobre los vértices de dicho conjunto. Si alguno de estos valores extremos se alcanza en más de un vértice entonces toma ese mismo valor en toda combinación lineal convexa de los vértices.

• Problema de programación lineal:

Lo que se quiere hacer en un problema de programación lineal es optimizar una función lineal z que tiene una serie de restricciones, y sean igualdades o desigualdades de tipo lineal.

Si planteamos el problema sería de esta forma:

La función z se denomina función objetivo.

Resolver este problema consisten en obtener los valores de todas las variables xi que optimizan z satisfaciendo las restricciones. Las restricciones del tipo =< suelen representar limitaciones de recursos mientras que las de tipo => suelen ser condiciones técnicas. Vamos a suponer que las restricciones son independientes, es decir, no hay condiciones redundantes.

• Variables de holgura:

Variables que se introducen para convertir las restricciones que sean desigualdades en igualdades.

Si las utilizamos y transformamos las restricciones quedan así:

La variable de holgura x_(m+1) debe ser major o igual a cero y el coeficiente en la función objetivo debe ser c_(m+1)=0.

En las restricciones del tipo =< las variables de holgura significa la cantidad de recurso no utilizado, en las otras restricciones son el exceso con el que se satisfacen las condiciones.

• Planteamiento general del problema:

En forma matricial el problema con las variables de holgura quedaría:

x=(x1, x2, ... , xm): es el vector de las variables, incluidas las de holgura.
c=(c1, c2, ... , cm): es el vector de costes. Las componente de este vector que estén asociadas a las variables de holgura serán 0.

A: es una matriz de dimensión n x m ( n restricciones y m variables totales).

b: es un vector de n componentes, todas ellas mayores o iguales que 0.

• Variables ficticias:

Son variables que se introducen en las restricciones para facilitar el hallazgo de una solución básica inicial del problema. Al introducir las variables ficticias podemos conseguir que aparezca dentro de la matriz de restricciones la submatriz identidad de orden n, que nos permitirá encontrar una solución básica.

Las variables ficticias se incluirán en la función objetivo con un coeficiente K si es un mínimo y -K si es un máximo, donde K es un número superior que cualquiera de los que intervienen en le proceso.

•  Soluciones del problema:

El conjunto de soluciones posibles de nuestro problema de programación lineal es un conjunto convexo.

Una solución posible es todo vector x que satisface el conjunto de restricciones.

Se dice que una solución posible es básica si no hay más de n componentes (número de restricciones) que son positivas. Si el número de componentes es n, entonces la solución es básica  no degenerada.

Si una solución proporciona el máximo o mínimo de la función objetivo entonces se dice que la solución es óptima. Siempre corresponderá a un vértice del conjunto de soluciones y es una solución básica.