Modelos de Programación Matemática Programación Lineal

Introducción

Muchas personas clasifican el desarrollo de la Programación Lineal (PL) entre los avances científicos más importantes de mediados del siglo XX. En la actualidad es una herramienta común que ha ahorrado miles o millones de dólares a muchas compañías y negocios, incluyendo industrias medianas en distintos países del mundo. ¿Cuál es la naturaleza de esta notable herramienta y qué tipo de problemas puede manejar? Expresado brevemente, el tipo más común de aplicación abarca el problema general de asignar recursos limitados entre actividades competitivas de la mejor manera posible (es decir, en forma óptima). Este problema de asignación puede surgir cuando deba elegirse el nivel de ciertas actividades que compiten por recursos escasos para realizarlas. La variedad de situaciones a las que se puede aplicar esta descripción es sin duda muy grande, y va desde la asignación de instalaciones productivas a los productos, hasta la asignación de los recursos nacionales a las necesidades de un país; desde la planeación agrícola, hasta el diseño de una terapia de radiación; etc. No obstante, el ingrediente común de todas estas situaciones es la necesidad de asignar recursos a las actividades.
Con frecuencia, seleccionar una alternativa incluye satisfacer varios criterios al mismo tiempo. Por ejemplo, cuando se compra una pieza de pan se tiene el criterio de frescura, tamaño, tipo (blanco, integral u otro), costo y rebanado o sin rebanar. Se puede ir un paso más adelante y dividir estos criterios en dos categorías: restricciones y el objetivo. Las restricciones son las condiciones que debe satisfacer una solución que está bajo consideración. Si más de una alternativa satisface todas las restricciones, el objetivo se usa para seleccionar entre todas las alternativas factibles. Cuando se elige una pieza de pan, pueden quererse 100 gr. de pan blanco rebanado y hecho no antes de ayer. Si varias marcas satisfacen estas restricciones, puede aplicarse el objetivo de un costo mínimo y escoger las más barata.
Existen muchos problemas administrativos que se ajustan a este molde de tratar de minimizar o maximizar un objetivo que está sujeto a una lista de restricciones. Un corredor de inversiones, por ejemplo, trata de maximizar el rendimiento sobre los fondos invertidos pero las posibles inversiones están restringidas por las leyes y las políticas bancarias. Un hospital debe planear que las comidas para los pacientes satisfagan ciertas restricciones sobre sabor, propiedades nutritivas, tipo y variedad, al mismo tiempo que se trata de minimizar el costo. Un fabricante, al planear la producción futura, busca un costo mínimo al mismo tiempo cómo cumplir restricciones sobre la demanda del producto, la capacidad de producción, los inventarios, el nivel de empleados y la tecnología. La PL se ha aplicado con éxito a estos y otros problemas.
La PL es una técnica determinista, no incluye probabilidades y utiliza un modelo matemático para describir el problema. El adjetivo lineal significa que todas las funciones matemáticas del modelo deben ser funciones lineales. En este caso, la palabra programación no se refiere a programación en computadoras; en esencia es un sinónimo de planeación. Así, la PL trata la planeación de las actividades para obtener un resultado óptimo, esto es, el resultado que mejor alcance la meta especificada (según el modelo) entre todas las opciones de solución. Aunque la asignación de recursos a las actividades es la aplicación más frecuente, la PL tiene muchas otras posibilidades. De hecho, cualquier problema cuyo modelo matemático se ajuste al formato general del modelo de PL es un problema de PL.

Forma estándar de los modelos de Programación Lineal

Supóngase que existe cualquier número (digamos m) de recursos limitados de cualquier tipo, que se pueden asignar entre cualquier número (digamos n) de actividades competitivas de cualquier clase. Etiquétense los recursos con números (1, 2, ..., m) al igual que las actividades (1, 2, ..., n). Sea xj (una
In v e s t i g a c i ó n d e O p e r a c i o n e s I n g . C h r i s t i a n B a r r a g á n . 1 0
variable de decisión) el nivel de la actividad j, para j = 1, 2, ..., n, y sea Z la medida de efectividad global seleccionada. Sea cj el incremento que resulta en Z por cada incremento unitario en xj (para j = 1, 2, ..., n). Ahora sea bi la cantidad disponible del recurso i (para i = 1, 2, ..., m). Por último defínase aij como la cantidad de recurso i que consume cada unidad de la actividad j (para i = 1, 2, ..., m y j = 1, 2, ..., n). Se puede formular el modelo matemático para el problema general de asignar recursos a actividades. En particular, este modelo consiste en elegir valores de x1, x2, ..., xn para:
Maximizar Z = c1x1 + c2x2 + ... + cnxn,
sujeto a las restricciones:
a11x1 + a12x2 + ... + a1nxn ≤ b1
a21x1 + a22x2 + ... + a2nxn ≤ b2
am1x1 + am2x2 + ... + amnxn ≤ bm
y
x1 ≥0, x2 ≥0, ..., xn ≥ 0
Ésta se llamará nuestra forma estándar (porque algunos libros de texto adoptan otras formas) para el problema de PL. Cualquier situación cuya formulación matemática se ajuste a este modelo es un problema de PL.
En este momento se puede resumir la terminología que usaremos para los modelos de PL. La función que se desea maximizar, c1x1 + c2x2 + ... + cnxn, se llama función objetivo. Por lo general, se hace referencia a las limitaciones como restricciones. Las primeras m restricciones (aquellas con una función del tipo ai1x1 + ai2x2 + ... + ainxn, que representa el consumo total del recurso i) reciben el nombre de restricciones funcionales. De manera parecida, las restricciones xj ³ 0 se llaman restricciones de no negatividad. Las variables xj son las variables de decisión. Las constantes de entrada, aij, bi, cj, reciben el nombre de parámetros del modelo.

Ejemplos de modelamiento

Problema de Transporte

El problema consiste en decidir cuántas unidades trasladar desde ciertos puntos de origen (plantas, ciudades, etc.) a ciertos puntos de destino (centros de distribución, ciudades, etc..) de modo de minimizar los costos de transporte, dada la oferta y demanda en dichos puntos.
Se suponen conocidos los costos unitarios de transporte, los requerimientos de demanda y la oferta disponible.
Por ejemplo, suponga que una empresa posee dos plantas que elaboran un determinado producto en cantidades de 250 y 450 unidades diarias, respectivamente. Dichas unidades deben ser trasladadas a tres centros de distribución con demandas diarias de 200, 200 y 250 unidades, respectivamente. Los costos de transporte (en $/unidad) son:
C.Dist. 1
C.Dist.2
C.Dist.3
Planta 1
21
25
15
Planta 2
28
13
19
Diagrama:
Variables de decisión:
xij = Unidades transportadas desde la planta i (i=1,2), hasta el centro de distribución j (j=1,2,3)
Función Objetivo:
Minimizar el costo total de transporte dado por la función:
21x11+25x12+15x13+28x21+13x22+19x23
Restricciones del problema:
1) No Negatividad: xij  0
2) Demanda:
CD1 : x11 +x21 = 200
CD2 : x12 +x22 = 200
CD3 : x13 + x23 = 250
3) Oferta :
P1 : x11 + x12 + x13  250
P2 : x21 + x22 + x23  450
Las variables de decisión deben aceptar soluciones como números reales para tener un modelo de P.L.

Sistema de ecuaciones

Sistema de ecuaciones

En las matemáticas, un sistema de ecuaciones es un conjunto de dos o más ecuaciones con varias incógnitas. Una solución para el sistema debe proporcionar un valor para cada incógnita, de manera que en ninguna de las ecuaciones del sistema se llegue a una contradicción. En otras palabras el valor que reemplazamos en las incógnitas debe hacer cumplir la igualdad del sistema.
Las incógnitas se suelen representar utilizando las últimas letras del alfabeto latino, o si son demasiadas, con subíndices.
Sistema general
La forma genérica de un sistema de ecuaciones y incógnitas es la siguiente:
(1)
donde son funciones de las incógnitas. La solución, perteneciente al espacio euclídeo , será tal que el resultado de evaluar cualquier expresión con los valores de dicha solución, verifique la ecuación.
Representación gráfica
Los sistemas de 2 o 3 incógnitas admiten representaciones gráficas cuando las funciones en (1) son continuas a tramos. En cada ecuación se representa como una curva o una superficie curva. La existencia de soluciones en ese caso puede deducirse a partir de la existencia de intersecciones comunes a dichas curvas o superficies curvas.
Clasificación de los sistemas
Un sistema de ecuaciones sobre puede clasificarse de acuerdo con el número de soluciones en:
Sistema incompatible cuando no admite ninguna solución.
Sistema compatible cuando admite alguna solución que a su vez pueden dividirse en:
Sistemas compatibles indeterminados cuando existe un número infinito de soluciones que forman una variedad continua.
Sistemas compatibles determinados cuando admiten un conjunto finito de soluciones, o un conjunto infinito de soluciones aisladas con a lo sumo un número finito de puntos de acumulación.
Sistema lineal
Un sistema como el anterior en que las anteriores ecuaciones son funciones afines. A diferencia del caso general, la solución de los sistemas de ecuaciones lineales son fáciles de encontrar cuando los coeficientes de las ecuaciones son números reales o complejos. También existen medios generales cuando los coeficientes pertenecen a un anillo, aunque la búsqueda de las soluciones en ese caso puede ser un poco más complicada.
Una característica importante de los sistemas lineales de ecuaciones es que admiten la llamada forma matricial. Esa forma permite representar el sistema usando tres matrices, de la siguiente forma:
(2)
La primera es la matriz de coeficientes, donde el término representa al coeficiente que acompaña a la j-ésima incógnita de la ecuación i-ésima. La segunda es la matriz de incógnitas, donde cada término se corresponde con una de las incógnitas que queremos averiguar. Y la tercera matriz es la de términos independientes, donde el cada representa al término independiente de la ecuación i-ésima.
Esta representación matricial facilita el uso de algunos métodos de resolución, como el método de Gauss, en el que, partiendo de la matriz aumentada (matriz de coeficientes a la que se le ha acoplado la matriz de términos independientes), y aplicando transformaciones lineales sobre las ecuaciones, pretendemos llegar a una matriz de este tipo:
Una vez la matriz se ha triangulado, el valor de cada término se corresponderá con el de la incógnita . Si nos encontramos alguna fila del tipo , con , el sistema no tendrá solución.
Existencia de soluciones
El teorema de la función inversa proporciona condiciones suficientes de existencia de solución, de un sistema como (1) con . Si sucede que la función vectorial:
Es diferenciable con continuidad, es decir, es de clase y su jacobiano no se anula en ningún punto entonces existe una única solución del sistema (1). Ya que en ese caso existirá una función inversa, y podremos escribir la solución buscada simplemente como:
Sin embargo, la condición de diferenciabilidad anterior aún siendo condición suficiente, no es una condición necesaria, por lo que existen sistemas de ecuaciones en que las funciones no son diferenciables y sin embargo, existen soluciones. Más aún, en casos en que existe más de una solución si la función es diferenciable entonces el jacobiano se anula en algún punto, pero eso no impide que existan varias soluciones.
En casos de un menor número de ecuaciones que de incógnitas, cuando , entonces el sistema es complatible indeterminado o carece de soluciones. En esos casos, el teorema de la función implícita proporciona condiciones suficientes, aunque no necesarias, para la existencia de soluciones de un modo similar a como el teorema de la función inversa las proporciona en el caso .
Método de Gauss-Jordan:
El método de Gauss-Jordan utiliza operaciones con matrices para resolver sistemas de ecuaciones de n número de variables.
Para aplicar este método solo hay que recordar que cada operación que se realice se aplicara a toda la fila o a toda la columna en su caso. Procedimiento:
Primero se debe tener ya el sistema de ecuaciones que se quiere resolver y que puede ser de n numero de variables por ejemplo:
-3x+3y+2z=1 4x+y-z=2 x-2y+z=3
Y se acomodan los coeficientes y los resultados en una matriz:
El objetivo de este método es tratar de convertir la parte de la matriz donde están los coeficientes de las variables en una matriz identidad que es una matriz con puros 0 y 1 pero los 1 están en diagonal así:
Esto se logra mediante simples operaciones de suma, resta y multiplicación. Entonces, si se quiere convertir la primera matriz en la segunda, se puede observar que el -3 de la primera matriz se tiene que convertir en un 1, según la matriz identidad, así que hay que dividir entre -3, pero como una operación se aplica a toda la fila, entonces toda la primera fila se tiene que dividir entre -3 y queda más o menos así:
Después, como se ve en la matriz identidad, hay que hacer 0 toda la columna debajo del 1, y se hace multiplicando por algo la fila de arriba y sumándola a la fila de abajo, en este caso, si se multiplica por -4 la fila de arriba, la primera multiplicación es -4x1, que sumado a la primera coordenada de la fila de abajo da el 0 que se desea, igualmente, la operación se realiza con toda la fila por lo que a cada posición de la fila de arriba se le multiplica por -4 y se suma con la correspondiente posición de la fila de abajo. La siguiente multiplicación seria -4x-1 y se sumaría con el 1 de abajo. La matriz va quedando de la siguiente manera:
En la imagen de al lado ya se termino de hacer 0 las posiciones que se requieren según lo indica la matriz identidad. (Las R son por Row en ingles)
El siguiente paso para lograr una matriz identidad es obtener el siguiente 1, que en este caso iría en donde está el 5 en la segunda fila. Como ya se trabajo con la primera columna ya no es necesario tomarla en cuenta puesto que se supone que ya está bien. Para lograr un 1, hay que dividir toda la segunda fila (sin tomar en cuenta la primera columna) entre 5 y la matriz queda así:
Después se tienen que hacer 0 los que están arriba y abajo del 1, que en este caso seria, para el que está arriba 1xR2+R1 porque el R1 es un -1 y al sumarse con el 1 que da de la multiplicación de 1xR2 da el 0 que se está buscando. De igual manera para el que está debajo es el mismo procedimiento porque en este ejemplo coincidió que los 2 fueran -1, pero hay que recordar siempre buscar el numero por el cual multiplicar para que a la hora de sumar de un 0.
Una vez que se obtuvieron los 0 solo falta obtener el ultimo 1 según la matriz identidad. Esto se logra dividiendo entre 2 toda la tercera fila ignorando ya los que fueron hechos ceros.
La matriz queda de la siguiente manera:
Por último solo se hacen 0 los que están encima del que acabamos de hacer 1, en este caso multiplicando por 1/3xR3 y sumándola a R1 para hacer el 0 que se necesita, y multiplicando -1/3xR3 y sumándolo a R2 para obtener el ultimo 0:
Como se podrá notar, una matriz identidad siempre es cuadrada y al pasarla a nuestra matriz original sobro la columna donde iban los resultados de cada ecuación, pues bien, esa última columna contiene los valores de las variables que se están buscando y en orden, la de arriba es la primer variable, la de en medio es la segunda y la última es la tercera.

Método Simplex

El Método Simplex publicado por George Dantzig en 1947 consiste en un algoritmo iterativo que secuencialmente a través de iteraciones se va aproximando al óptimo del problema de Programación Lineal en caso de existir esta última.
El Método Simplex hace uso de la propiedad de que la solución óptima de un problema de Programación Lineal se encuentra en un vértice o frontera del dominio de puntos factibles (esto último en casos muy especiales), por lo cual, la búsqueda secuencial del algoritmo se basa en la evaluación progresiva de estos vértices hasta encontrar el óptimo. Cabe destacar que para aplicar el Método Simplex a un modelo lineal, este debe estar en un formato especial conocido como formato estándar el cual definiremos a continuación.

Forma Estándar De Un Modelo De Programación Lineal

Consideremos un modelo de Programación Lineal en su forma estándar, que denotaremos en lo que sigue por:
Min c1x1 + c2x2 + ... + cnxn
sa a11x1 + a12x2 + ... + a1nxn = b1
a21x1 + a22x2 + ... + a2nxn = b2
... ... ...
am1x1 + am2x2 + ... + amnxn = bm
xi >= 0, i = 1, 2, ..., n y m <= n Matricialmente escrito como: Min cTx s.a Ax = b x >= 0
No existe pérdida de generalidad en asumir que un modelo de PL viene dado en su forma estándar:
EJEMPLO
P) Max 9u + 2v + 5z
sa 4u + 3v + 6z <= 50 u + 2v - 3z >= 8
2u - 4v + z = 5
u,v >= 0
z e IR
Siempre es posible llevar un problema de maximización a uno de minimización. Si f(x) es la función objetivo a maximizar y x* es la solución óptima f(x*) >= f(x), para todo x factible. -f(x*) <= - f(x), para todo x factible. En consecuencia: x* es también mínimo de -f(x) Cada restricción del tipo <= puede ser llevada a una ecuación de igualdad usando una (nueva) variable de holgura no negativa, con coeficiente nulo en la función objetivo. Cada restricción del tipo >= puede ser llevada a una ecuación de igualdad usando una (nueva) variable de exceso no negativa, con coeficiente nulo en la función objetivo.
Siempre es posible escribir una variable libre de signo como la diferencia de dos variables no negativas.
Considerando la siguiente notación: u = x1, v = x2, z = x3 - x4, s1 = x5 (holgura), s2 = x6 (exceso), el problema P) puede ser escrito en forma equivalente como:
Min - 9x1 - 2x2 - 5x3 + 5x4 + 0x5 + 0x6
sa: 4x1 + 3x2 + 6x3 - 6x4 + x5 = 50
x1 + 2x2 - 3x3 + 3x4 - x6 = 8
2x1 - 4x2 + x3 - x4 = 5
xi >= 0, i=1,2,3,4,5,6.

Resolución gráfica de problemas

Resolución gráfica de problemas

Consideremos el siguiente problema a resolver gráficamente:
Max z = 3x1 + 5x2
sa: x1 £ 4
3x1 + 2x2 £ 18
x1,x2 ³ 0
En primer lugar, se debe obtener la región de puntos factibles en el plano, obtenida por medio de la intersección de todos los semi - espacios que determinan cada una de las inecuaciones presentes en las restricciones del problema.
Enseguida, con el desplazamiento de las curvas de nivel de la función objetivo en la dirección de crecimiento de la función (que corresponde a la dirección del vector gradiente de la función, z(x1,x2) = (3,5)T), se obtiene la solución óptima del problema en la intersección de las rectas: 2x2 = 12 y 3x1+2x2 = 18 (restricciones activas). Esto es:
x1* = 2 x2* = 6
z* = 3 x1* + 5 x2* = 36
Notar que se pueden dar otras situaciones en la búsqueda de una solución óptima para esta clase de problemas:
1) La solución óptima exista pero haya más de una. En el ejemplo, considere la nueva función objetivo: z = 6x1+4x2.
2) El problema no tenga solución, dada una región de puntos factibles no - acotada. En el ejemplo, reemplace cada desigualdad  por una .
3) El problema no tenga solución, porque no existen puntos factibles. En el ejemplo, suponga que agregamos la restricción: x1  5.