Programación Lineal

Modelo de Transporte
Ejemplo
 MG Auto Company tiene plantas en los Ángeles,
Detroit y Nueva Orleans. Sus centros de
distribución principales están ubicados en Denver
y Miami. Las capacidades de las tres plantas
durante el trimestre próximo son de 1000, 1500
y 1200 automóviles. Las demandas trimestrales en
los dos centros de distribución son de 2300 y
1400 vehículos. El costo del transporte de un
automóvil por tren es aproximadamente de 8
centavos por milla. El diagrama de la distancia
recorrida entre las plantas y los centros de
distribución es el siguiente
 Denver Miami
Los Ángeles 1000 2690
Detroit 1250 1350
Nueva Orleans 1275 850

El diagrama de la distancia del recorrido puede traducirse en

costo por automóvil a razón de 8 centavos por milla recorrida.
Esto produce los costos siguientes (redondeados a números
enteros), que representan a cij del modelo original:

Denver Miami
Los Ángeles 80 215
Detroit 100 108
Nueva Orleans 102 68
Mediante el uso de código numéricos para representar las plantas y centros de
distribución, hacemos que xij represente el número de automóviles
transportados de la fuente i al destino j

Denver Miami
(1) (2)
Los Ángeles (1) 80 215
Detroit (2) 100 108
Nueva Orleans (3) 102 68

Minimizar z = 80x11 + 215x12 + 100x21 + 108x22 + 102x31 + 68x32

Sujeto a
x11 + x12 = 1000
+ x21 + x22 = 1500
+ x31 + x32 = 1200
x11 + x21 + x31 = 2300
+ x12 + x22 + x32 = 1400
xij ≥ 0 , para todas las i y j
 Denver (1) Miami(2)

80 215
Los Ángeles (1) X11 X12 1000

100 108
Detroit (2) X21 X22 1500

102 68
Nueva Orleans (3)
1200
X31 X32

2300 1400
 Denver (1) Miami(2)

80 215 1000
Los Ángeles (1)

1500
Detroit (2) 100 108

1000
Nueva Orleans (3) 102 68

Planta ficticia 0 0 200

2300 1400
 Denver (1) Miami(2) Centro de
distribución
ficticio

Los Ángeles 80 215 0 1000

(1)

Detroit 100 108 0 1500

(2)

Nueva 102 68 0 1200

Orleans (3)

2300 1000 400

 Solución del problema de transporte
Destino
1 2 3 4
Oferta

Fuente 2

Demanda
 Paso 1. Determínese una solución factible
inicial (regla de la esquina Noroeste)
Oferta

5 10

Demanda
 Paso 1. Determínese una solución factible
inicial (regla de la esquina Noroeste)
Oferta

5 10 10

Demanda
5
 Paso 1. Determínese una solución factible
inicial (regla de la esquina Noroeste)
Oferta

5 10 10

5 20

Demanda
5
 Paso 1. Determínese una solución factible
inicial (regla de la esquina Noroeste)
Oferta

5 10 10

5 15 20 5

Demanda
5
 Paso 1. Determínese una solución factible
inicial (regla de la esquina Noroeste)
Oferta

5 10 10

5 15 5 20 5

Demanda
5 5
 Paso 1. Determínese una solución factible
inicial (regla de la esquina Noroeste)
Oferta

5 10 10

5 15 5 20 5

Demanda
5 5
Variables básicas

5 10
X11 X12

5 15 5
X22 X23 X24

5
X34

X11 = 5 X23 = 15
X12 = 10 X24 = 5
X22 = 5 X34 = 5
Paso 2: Determinar la variable que entra, que se
elige entre las variables no básicas. Si todas
cumplen con la condición de optimidad, deténgase,
de lo contrario diríjase al paso 3

Método de multiplicadores

Para variables básicas Para variables no básicas

ui + vj = Cij ui + vj – Cij = δij
Cálculo para variables básicas
X11 → u1 + v1 = C11, → v1 = C11 - u1 =10

X12 → u1 + v2 = C12, → v2 = C12 - u1 = 0

X22 → u2 + v2 = C22, → u2 = C22 – v2 = 7

X23 → u2 + v3 = C23, → v3 = C23 – u2 = 2

X24 → u2 + v4 = C24, → v4 = C24 – u2 = 13

X34 → u3 + v4 = C34, → u3 = C34 – v4 = 5

Cálculo para variables no básicas
X13 → u1 + v3 - C13 = 0 + 2 – 20 = 0

X14 → u1 + v4 - C14 = 0 + 13 – 11 = 2

X21 → u2 + v1 – C21 = 7 + 10 – 12 = 5

X31 → u3 + v1 – C31 = 5 + 10 – 0 = 15

X32 → u3 + v2 – C32 = 5 + 0 – 14 = -9

X33 → u3 + v3 – C33 = 5 + 2 – 16 = -9
 v1 = 10 v2 = 0 v3 = 2 v4 = 13

10 0 20 11
u1 = 0
5 10
-18 2

12 7 9 20
u2 = 7
5 15 5
5

0 14 16 18
u3 = 5
X31 5
15 -9 -9

5 15 15 10

La variable que entra sería la más positiva, en este caso

sería X31
Paso 3. Determínese la variable que sale (mediante el
uso de condición de factibilidad), entre la las
variables de la solución básica actual; después
obténgase la nueva solución básica, regrese al paso 2.

Para el fin de determinar una razón mínima, construimos un ciclo

cerrado para la variable actual que entra.

El ciclo empieza y termina en la variable no básica designada..

Este consta de los segmentos sucesivos horizontales y verticales

(conectados) cuyos puntos extremos deben ser variables básicas,
salvo para los puntos extremos que están asociados con la variable
que entra. Esto significa que todo elemento de esquina del ciclo debe
ser una celda que contenga una variable básica.
 v1 = 10 v2 = 0 v3 = 2 v4 = 13

10 0 20 11
u1 = 0
5 10
-18 2

12 7 9 20
u2 = 7
5 15 5
5

0 14 16 18
u3 = 5
X31 5
15 -9 -9

5 15 15 10
 Colocar un signo de ⊕ y  en las
esquinas correspondientes, colocando
inicialmente ⊕ en la celda donde se ubica
la variable de entrada y posterior a esto
colocar  en la celda siguiente en el
recorrido del ciclo y continuar alternando
ambos símbolos en los vértices del ciclo.
 v1 = 10 v2 = 0 v3 = 2 v4 = 13

 10 ⊕ 0 20 11
u1 = 0
5 10
-18 2

12  7 9 ⊕ 20
u2 = 7
5 15 5
5

⊕ 0 14 16  18
u3 = 5
X31 5
15 -9 -9

5 15 15 10
 Seleccionar el valor más pequeño de los
números que aparecen en el ciclo y
disminuir o aumentar (dependiendo de ⊕
ó ) el valor seleccionado. El número
seleccionado y asociado con , será la
variable que sale de la solución
Como tenemos tres
variables con el
mismo valor, para
este problema
seleccionaremos
X34 como la
variable que sale
REPETIR A PARTIR DEL
PASO 2
 v1 = 10 v2 = 0 v3 = 2 v4 = 13

10 0 20 11
u1 = 0
0 15
-18 2

12 7 9 20
u2 = 7
X21 0 15 10
5

0 14 16 18
u3 = -10
5 -24 -24 -15

5 15 15 10
Variable que entra
 v1 = 10 v2 = 0 v3 = 2 v4 = 13

 10 ⊕ 0 20 11
u1 = 0
0 15
-18 2

⊕ 12  7 9 20
u2 = 7
X21 0 15 10
5

0 14 16 18
u3 = -10
5 -24 -24 -15

5 15 15 10
Como tenemos dos
variables con el
mismo valor, para
este problema
seleccionaremos
X11 como la
variable que sale
REPETIR A PARTIR DEL
PASO 2
 v1 = 5 v2 = 0 v3 = 2 v4 = 13

10 0 20 11
u1 = 0 X14
-5
15
-18 2

12 7 9 20

u2 = 7 0 0 15 10
0 14 16 18

u3 = -5 5 -19 -19 -10

5 15 15 10

Variable que entra

 v1 = 5 v2 = 0 v3 = 2 v4 = 13

10  0 20 ⊕ 11
u1 = 0 15 X14
-5 -18 2

12 ⊕ 7 9  20

u2 = 7 0 0 15 10
0 14 16 18

u3 = -5 5 -19 -19 -10

5 15 15 10
La variable que sale es X24
REPETIR A PARTIR DEL
PASO 2
 v1 = 5 v2 = 0 v3 = 2 v4 = 11

10 0 20 11
u1 = 0 5 10 15
-5 -18

12 7 9 20

u2 = 7 0 10 15 25
-2

0 14 16 18

u3 = -5 5 5
-19 -19 -12

5 15 15 10
Fuente 1 a Destino 2 5 unidades ($0) $ 0.00
Fuente 1 a Destino 4 10 unidades ($11) $ 110.00
Fuente 2 a Destino 1 0 unidades ($12) $ 0.00
Fuente 2 a Destino 2 10 unidades ($7) $ 70.00
Fuente 2 a Destino 3 15 unidades ($9) $ 135.00
Fuente 3 a Destino 1 5 unidades ($0) $ 0.00

$315.00
Ejemplo:
 Tres refinerías con capacidades diarias de 6, 5 y 8 millones de
galones, respectivamente, abastecen a su vez a tres áreas de
distribución con demandas diarias de 4, 8 y 7 millones de galones
respectivamente. La gasolina se transporta a las tres áreas de
distribución a través de una red de oleoductos. El costo de
transporte es de 10 centavos por 1000 galones por milla de
oleoducto. La tabla siguiente muestra la distancia en millas entre las
refinerías y las áreas de distribución. La refinería 1 no esta
conectada al área de distribución 3. Determine el programa de
envíos. óptimo en la red.
AREA DE DISTRIBUCION
1 2 3
1 120 180 ---
REFINERIA 2 300 100 80
3 200 250 120