Técnica matemática

Antecedentes.

La primera técnica matemática ampliamente aceptada en el medio de Investigación de Operaciones fue el Método Símplex de Programación Lineal, desarrollado en 1947 por el matemático norteamericano George B. Dantzig. Desde entonces las nuevas técnicas se han desarrollado gracias al esfuerzo y cooperación de las personas interesadas tanto en el área académica como en el área industrial.

El problema de la resolución de un sistema lineal de inecuaciones se remonta, almenos, a Fourier, después de quien nace el método de eliminación de Fourier-Motzkin. La programación lineal se plantea como un modelo matemático desarrollado durante la Segunda Guerra Mundial para planificar los gastos y los retornos, a fin de reducir los costos al ejército y aumentar las pérdidas del enemigo. Se mantuvo en secreto hasta 1947. En la posguerra, muchas industrias lo usaron en su planificación diaria. Los fundadores de la técnica son George Dantzig, quien publicó el algoritmo simplex, en 1947, John von Neumann, que desarrolló la teoría de la dualidad en el mismo año, y Leonid Kantoróvich, un matemático ruso, que utiliza técnicas similares en la economía antes de Dantzig y ganó el premio Nobel en economía en1975. En 1979, otro matemático ruso, Leonid Khachiyan, demostró que el problema de la programación lineal era resoluble en tiempo polinomial. Más tarde, en 1984, Narendra Karmarkar introduce un nuevo método del punto interior para resolver problemas de programación lineal, lo que constituiría un enorme avance en los principios teóricos y prácticos en el área.

Variables de holgura. Aplica para las restricciones del tipo (<=), donde el lado derecho de la desigualdad representa el limite sobre la disponibilidad de un recurso y el lado izquierdo representa la utilización de ese recurso limitado que hacen las variables del modelo. Esto quiere decir que una holgura representa la cantidad disponible del recurso que excede a la utilización que se le da. En la conversión de este tipo de desigualdad se añade una variable de ajuste (Xi o Hi) para convertirla en igualdad. Por ejemplo, tenemos la siguiente restricción: 3X1 + 2X2 <= 6, su equivalente seria, 3X1 + 2X2 + X3 = 6.

Variables de salida

Esta variable es un punto extremo que se encuentra en un criterio conocido como “Condición de factibilidad”, en un modelo, ya sea de optimización o minimización, y se refiere a la variable básica asociada con la mínima razón no negativa con el coeficiente más negativo, si se trata de una maximización, o el coeficiente más positivo, si se trata de una minimización, la cual, en el la tabla de solución siguiente, pasará a ser variable no básica.

Variables básicas Variables no básicas Variable de entrada Variable de salida

A X3, X4, X5, X6 X1, X2 X1 X2

B X3, X4, X5, X1 X6, X2 X2 X3

C X2, X4, X5, X1 X6, X3 X6 X4

D X2, X6, X5, X1 X4, X3 X3 X1

E X2, X6, X5, X3 X4, X1 X4 X2

Variables de entrada

Estas suelen encontrarse en un criterio que se conoce como “Condición de optimalidad”, en un modelo, ya sea de optimización o minimización, y se refiere a la variable no básica en el renglón “z” con el coeficiente más negativo, si se trata de una maximización, o el coeficiente más positivo, si se trata de una minimización, la cual, en el la tabla de solución anterior, a excepción de la primer tabla, esta variable era una variable básica.

METODO DE LA GRAN M:

El proceso para hacer PL “de mal comportamiento” con restricciones (=) y (> =) es permitir que variables artificiales desempeñen el trabajo de holguras en la primera iteración, para después, deshacerlas en forma legitima.

El método de la gran M comienza con la programación lineal en forma de ecuación. Una ecuación i que no tenga holgura se aumenta con una variable artificial Ri, para formar una solución de inicio parecida a la solución básica con todas las holguras. Sin embargo, como las variables artificiales son ajenas al modelo de PL, se usa un mecanismo de retroalimentación en el que el proceso de optimización trata en forma automática de hacer que esas variables tengan nivel cero. Es decir, la solución final será como si las variables artificiales nunca hubieran existido en primer lugar. El resultado deseado se obtiene penalizando las variables artificiales en la función objetivo.

Dado M, un valor positivo suficientemente grande (M ∞)

Coeficiente objetivo de la variable artificial ={█(-M,en problemas de maximizacion@M, en problemas de minimizacion)┤

Al usar esta penalización, el proceso de optimización forzara en forma automática a las variables artificiales para que sean cero (siempre que el problema tenga una solución factible).

Ejemplo:

Min Z = 2X1 + X2 + 3X3

Sujeto a:

3X1 + X2 + 2X3 <= 10

X1 - 2X2 + 3X3 >= 6

2X1 + 3X2 - X3 <= 9

X1 + X2 +2X3 = 7

Convertir al Modelo Estándar:

Cada restricción debe ser convertida de inecuación a una igualdad, agregando variables como se requiera. Con las restricciones de tipo <=, es supremamente fácil. Simplemente se agrega una en cada restricción con coeficiente 1 en la misma restricción y con coeficiente cero en la función objetivo. Por ejemplo:

3X1 + X2 + 2X3 <= 10 queda:

3X1 + X2 + 2X3 + S1 = 10

Se puede leer así: el uso de la primera restricción no puede superar la disponibilidad de 10 unidades, lo que equivale a decir que lo usado mas lo que sobre (s1) es igual a 10. Para las restricciones de tipo mayor o igual, la lógica es la misma, de esta manera decir:

X1 - 2X2 + 3X3 >= 6

...