METODO DUAL

El concepto de dualidad indica que para cada problema de PL hay una asociación y una relación muy importante con otro problema de programación lineal, llamado precisamente dual.

La relación entre el problema dual y su asociado, es decir el problema original llamado primal, presenta varias utilidades:
Aporta elementos que aumentan sustancialmente la compresión de la PL.
El análisis de dualidad es una herramienta útil en la solución de problemas de PL, por ejemplo: más restricciones que variables.

El problema dual tiene interpretaciones e informaciones importantes que muestran que los análisis marginales están siempre involucrados implícitamente al buscar la solución óptima a un problema de PL.

La forma estándar general del primal se defina como; para maximizar o minimizar.


EJEMPLO:

Z=max 3x+8x2+2x3-4x4

Modelo primario
X1+X2+2X3+3X4<5>
X1+X2 <1>
X3+X4<46




METODO DE VOGUEL

Este metodo es heuristico y suele producir una mejor solucion inicial que los dos metodos antes descritos. De hecho, VAM suele producir una solucion inicial optima, o proxima al nivel optimo.

Los pasos del procedimiento son los siguientes:

Paso1: Evaluese una penalizacion para cada renglon restando el menor elemento del costo del renglon del elemento de costo menor siguiente en el mismo renglon.

Paso2: Identifíquese el renglón o columna con la mayor penalizacion, rompiendo empates en forma arbitraria. Asignese el valor mayor posible a la variable con el costo mas bajo del renglon o columna seleccionado. Ajustese la oferta y la demanda y tachese el renglon o columna satisfecho. Si un renglon o columna se satisfacen al mismo tiempo, solo uno de ellos se tacha y al renglon restante se le asigna una oferta cero.Cualquier renglon o columna con oferta o demanda cero no debe utilizarce para calcular penalizaciones futuras.

Paso 3:
a.-si solo hay un renglón o columna sin tachar, deténgase.
B.-si solo hay un renglón con oferta positiva sin tachar, determínense las variables básicas del renglón a través del método del costo mínimo.
C.-si todos los renglones y columnas sin tachar tienen oferta o demanda cero asignadas, determínese las variables básicas cero a través del método del costo mínimo. Deténgase.
D.-de lo contrario, calcúlense las penalizaciones de los renglones y columnas no tachados y después diríjase al paso 2.
EJEMPLO
R=0
S=1
T=-1
A=6
B=6
C=4
D=4
E=6
F=2
G=5
H=0

SE COLOCAN LOS VALORES RESULTADOS Y SE LE RESTAN ALA PRIMERA TABLA.
LA ÚLTIMA TABLA QUE ASI:


METODO ASIGNACION

Un problema de asignación es un problema de transporte balanceado, en el cual todas las ofertas y todas las demandas son iguales a uno. Se puede resolver eficientemente un problema de asignación m x m mediante el método Húngaro.

Un problema de asignación es un problema de transporte balanceado en el que todas las ofertas y demandas son iguales a 1; así se caracteriza por el conocimiento del costo de asignación de cada punto de oferta a cada punto de demanda. La matriz de costos del problema de asignación se llama: matriz de costos.

Como todas las ofertas y demandas para el problema de asignación son números enteros, todas las variables en la solución óptima deben ser valores enteros.

1.- ESCOGER EL NUMERO MENOR DE LA COLUMNA Y SE LE RESTA A TODA LA COLUMNA

2.- SE COLOCA UNA LINEA DONDE HAYA QUEDADO CERO EN FILAS

3.-EL MENOR DE CADA FILA SE RESTA ENTRE CADA FILA SE ASIGANAN NUMEROS NUEVOS
4.-ENCERRAR CADA CERO DE FILA Y COLUMNA
5.-SE MARCAN LAS FILAS CON CEROS
6.-MARCA COLUMNA QUE TENGA CUADRO TACHE Y FILA QUE NO TENGA CERO
SE CLASIFICA:
A) CRUZADOS POR 2 LINEA (2, 0,3)
B)CRUZADOS POR 1 LINEA(2,6,7,2,5,15,1,11,15)
C)NADA LOS CRUZA(4,13,3,7,5,15,9,2,7,15)
7.- SE ELIGE EL MENOR DE (C) Y SE SUMA A (A)
8.-LOS VAN IGUAL
9.-SE LES RESTA EL MENOR DE (C) A ELLOS MISMOS (C)

10.- EL PROBLEMA TERMINA CUANDO TENEMOS EL MISMO NUMERO CEROS QUE DE FILAS Y COLUMNAS.


Z=4+1+5+3+4=17 Hrs.











METODO ESQUINA NOROESTE

El método de la esquina noroeste comienza con la asignación de la máxima cantidad admisible a través de la oferta y la demanda de la variable x11 (la de la esquina noroeste de la tabla). Después se tacha la columna (renglón) satisfecha, lo que indica que las variables restantes de la columna (renglón) tachada son iguales a cero. Si se satisfacen una columna y un renglón al mismo tiempo, sólo una (una u otro) puede ser tachada. (Esta condición garantiza la ubicación automática de variables básicas cero, si las hay). Después de ajustar las cantidades de oferta y demanda de todos los renglones y columnas no tachados, la cantidad factible máxima se asigna al primer elemento no tachado de la nueva columna (renglón). El proceso se completa cuando se deja sin tachar exactamente un renglón o una columna.


METODO DE TRANSPORTE

El modelo de transporte busca determinar un plan de transporte de una mercancía de varias fuentes a varios destinos. Los datos del modelo son:

1. Nivel de oferta en cada fuente y la cantidad de demanda en cada destino.
2. El costo de transporte unitario de la mercancía a cada destino.

Como solo hay una mercancía un destino puede recibir su demanda de una o más fuentes. El objetivo del modelo es el de determinar la cantidad que se enviará de cada fuente a cada destino, tal que se minimice el costo del transporte total.

La suposición básica del modelo es que el costo del transporte en una ruta es directamente proporcional al numero de unidades transportadas. La definición de “unidad de transporte” variará dependiendo de la “mercancía” que se transporte.

SIMPLEX MINIMIZACIÓN

Si en lugar de maximizar se trata de un problema de minimizar se sigue el mismo proceso, pero cambiando el sentido del criterio, es decir, para entrar en la base se elige la variable cuyo valor, en la fila de la función objetivo, sea el mayor de los positivos y se finalizan las iteraciones cuando todos los coeficientes de la fila de la función objetivo son negativos.

Metodo de las 2 fases:

Se considera

a) minimizacion se resuelve como se aplica en metodo simplex

b)maximisacion se resuelva coo minimizacion para la primera fases;la segunda fase ya es maximizacion.