IDO

Minimización de Costos y Rutas

XBi=solución básica factible tiene m variables >= 0 y las demás = 0
XBi=es la solución básica factible degenerada si m variables >=0 y al menos una es cero.


Tabla de Minimización



g=C1X1+…+CnXn
SA
A11x1+…+A1nxn<=B1 A21x1+…+A2nxn<=B2 Am1x1+…+Amnxn<=Bn xi>=0 para todas las i

Ejemplo;

Una fábrica tiene plantas en DF, MTY, GDL, VER y TIJ, por otro lado la compañía de empaques tiene plantas en PUE, CEL, DGO, se necesita enviar los empaques a la cia para cumplir con la demanda mensual que se tiene, la cual es:
DF 2000, MTY 400, GDL 500, VER 100, TIJ 200; y la producción minima de empaques es PUE 100, DGO1500, CEL 100; los costos que hay que cubrir estan en la siguiente tabla:


Problema balanceado:

Oferta = Demanda; si o>d, entonces, aumento 1 ficticio que cubre esa demanda, si oMétodo del Costo Mínimo

Ejemplo: se tienen 4 plantas y 3 centros de distribución y hay distintos costos de transportación de las plantas a los centros de distribución, los cuales están en la siguiente tabla en miles de libras



En este método se selecciona la celda con menor costo de todas y se le da el máximo entre la oferta y la demanda; en este caso celda X12 que es igual a 2 se le da el valor de 15, como se cubre la oferta entonces todos los demás valores de ese renglón y esa columna se hacen cero, de ahí se busca el siguiente valor mínimo y se le da el máximo de dem y oferta. X31 valor de 4 y el máximo valor que puede tomar es 10-5 el cual es 5; por lo cual se cancela esa columna pero no el renglón pues todavía no se cubre la oferta.
La siguiente que se toma es la X23 valor 9 la cual toma el valor de 15, se cancela esa columna y luego se toma la X34 18 la cual se toma 5 pues ya se habían tomado 5 de ahí, y finalmente se toma la X24 20 y toma el valor de lo que falta 10.

Por lo tanto el resultado mínimo es:
Z=2*15 + 4*5 + 9*15 + 18*5 + 20*10 = 475


Floyd determinación de la ruta mas corta


Encontrar la ruta mas corta entre cada 2 nodos, distancia esta en millas
arco (3,5) esta desconectado, es decir no existe trafico entre 5 y 3
todos los demas van a ambos lados.


De aquí te toman los valores inf y se cambian por los valores de mínimo, ejemplo, para pasar de 2 a 3 se puede pasar por 1 o por 4 y la menor distancia es hacerlo por 4 entonces la posición inf en matriz Do X23 la cambiamos por la suma de 5+6 ( la distancia de ir de 2 a 3 via 4, y el la matriz So cambiamos X23 que es 3 por 4.
Y asi sucesivamente hasta eliminar todos los inf. Y asi encontramos la mejor forma de ir a casa 2 nodos.