Matematicas

FORMA ESTÁNDAR DE UN PROBLEMA

Un problema lineal está en forma estándar si todas las restricciones son igualdades y se conoce una solución factible. En notación matricial, la forma estándar es:

Optimizar z = cx

Con la condición: ax = b

Con: X=> 0

Donde:

X es el vector columna de todas las variables de holgura, superfluas (exceso) y artificiales.

C es el vector renglón de los costos (utilidades) correspondientes.

a es la matriz de coeficientes de las ecuaciones de restricciones.

b es el vector columna de los lados derechos de las ecuaciones de restricciones (vector mano derecha o de disponibilidad de recursos)

SOLUCIÓN BÁSICA INICIAL FACTIBLE – S.B.I.F.

1. Se obtiene una Solución Básica Inicial por medio de la Forma Estándar del modelo, es decir, convertir las desigualdades en igualdades introduciendo variables de holgura (<=) ó variables de exceso (>=).

UNA SOLUCIÓN BÁSICA ES UNA SOLUCIÓN BÁSICA FACTIBLE SÍ Y SÓLO SÍ LAS VARIABLES BÁSICAS TIENEN VALORES NO NEGATIVOS, ES DECIR, MAYORES O IGUALES A CERO (>=).

2. DEBE EXISTIR EN CADA ECUACIÓN UNA VARIABLE CON COEFICIENTE +1 Y QUE NO ESTE EN NINGUNA OTRA RESTRICCIÓN; LAS OTRAS VARIABLES CON COEFICIENTE CERO (0) PARA FORMAR EL CANÓNICO O BASE DEL SISTEMA DE ECUACIONES. SE OBTIENE UNA SOLUCIÓN BÁSICA FACTIBLE INICIAL inicializando n-m variables adecuadas (No Básicas) al nivel de cero.

Donde: n Número de incógnitas

m Número de restricciones o ecuaciones

m < n

La función Objetivo no se tiene en cuenta para determinar el sistema de ecuaciones, aunque hace parte del Canónico.

VARIABLES ARTIFICIALES

Sumar una variable no negativa a primer miembro de cada ecuación o restricción que no tenga variables básicas iniciales evidentes. Esta variable desempeña la misma función que una variable de holgura, al proporcionar una VARIABLE BÁSICA INICIAL para una solución básica inicial.

Las variables artificiales no tienen sentido físico (artificial) y será válido cuando se hace igual a cero cuando se llegue al valor óptimo.

Se utilizan para iniciar la solución y después se hacen cero en la solución final, de lo contrario, la solución resultante será no factible.

MÉTODO DE LA GRAN M

Una variable artificial se agrega a una restricción si ésta no ha cumplido con el punto (2) y debe ser incluida en la Función Objetivo con un coeficiente M negativo (-) muy grande (en caso de maximización) ó un coeficiente M positivo (+) muy grande (en caso de minimización).

LAS VARIABLES ARTIFICIALES SE SUSTITUYEN EN LA FUNCIÓN OBJETIVO.

Las variables artificiales proporcionan las variables Básicas que se necesitan para las ecuaciones que no cumplen con el punto (2) y así poder tener una Solución Básica Factible Inicial.

El motivo de por que el coeficiente de las variables artificiales debe ser un valor muy grande, es para que en una sucesión de pivotes estas variables resulten ser No Básicas (iguales a cero).

Cada vez que una variable artificial es retirada de la base, la columna correspondiente puede ser eliminada también de la tabla.

TÉCNICA DE LAS DOS FASES

FASE I

a. Aumentar variables artificiales para dar una solución básica inicial.

b. Formar una segunda función objetivo que haga la minimización de la suma de las variables artificiales sujeta a las restricciones del problema original modificados por las variables artificiales.

c. Sí el valor mínimo de la nueva función objetivo es igual a cero, es decir, todas las variables artificiales son cero, hay un espacio de Soluciones Factibles, de lo contrario el problema no tiene solución factible.

FASE II

1. Se utiliza la solución básica óptima de la Fase I como la solución inicial para el problema original, eliminando las variables artificiales no básicas y se toman las nuevas ecuaciones dadas en esta fase I.

2. Estas ecuaciones son equivalentes a las de la forma estándar del problema original, antes de que se el sumaran las variables artificiales.

3. Se sustituyen las variables básicas de la Fase I en la función objetivo del problema original.

4. Se verifica la condición de optimidad en el tablero Simplex, con el fin de determinar una Solución Optima.

MÉTODO DUAL SIMPLEX

En el sentido de Maximización, la iteración primal no es óptima cuando se tienen los coeficientes Cj < 0 por lo menos para una variable. Sólo en el óptimo tenemos CJ > 0 pata todas las j.

Desde el punto de vista de la dualidad se tiene CJ < 0 lo que significa que el dual es infactible cuando el primal es no óptimo.

Por otra parte, cuando Cj >= 0 , indica que el dual se vuelve factible, cuando el primal alcanza la optimidad.

Esto significa que se debe trabajar con un nuevo método de solución para programas lineales, que comienza infactible pero óptima (los coeficientes de la función Objetivo son negativos - minimización). El problema Simplex regular empieza factible pero no óptimo.

El nuevo método, llamado Simplex Dual, conservará la optimidad y las iteraciones sucesivas trabajarán para anular la infactibilidad.

Cuando

...