EL PROBLEMA DEL DUAL

PASAR DE PRIMAL A DUAL

- Proporciona o simplificar cálculos matemáticos

- Interpretación económica del problema

DUAL: Es la otra cara del problema.

Primer Modelo: Modelo Primal.

Segundo Modelo: Modelo Dual

Pasos para pasar el Modelo Primal a Modelo Dual:

1. La maximización de la función objetivo Z pasa a minimización con función objetivo W.

2. El término independiente del primal (B) pasa como coeficiente de la función objetivo
del dual.
3. La variable decisión del dual se llama Y.
4. La matriz transpuesta de A son los coeficientes para las restricciones del Dual.
5. En el primal la maximización se asocia con <=. En el dual minimización se asocia con
>=.
6. El coeficiente de la función objetivo del primal (C ) para como termino independiente del
dual.

PRIMAL DUAL

TEOREMA 1 MAX Z = CX MIN W = BY

s.a. AX <= B s.a. AtY >= C
X>=0 Y>=0
TEOREMA 2 MIN Z = CX MAX W = BY
s.a. AX >= B s.a. AtY <= C
X>=0 Y>=0
# Restricciones m n
# Variables n m

Ej:

Max Z = 5X1 + 8X2

s.a (1) 3X1+ 2X2 <= 12
(2) 4X1 – 3X2 <= 8
(3) X1 <=10
X1,X2>=0
INTERPRETACION ECONOMICA DUAL:

Yi = Contribución marginal por cada unidad del recurso i $

BiYi = Contribución Total de los recursos
Aij t Yi = Contribución Marginal de los recursos por cada unidad de actividad
S´j = Valor que se deja de ganar si la variable de decisión del primal es no básica.

Para la interpretación del Dual

1. Los coeficientes de la función objetivo de las variables de holgura del Primal, son los
valores en orden ascendente de las variables de decisión del Dual.
2. Los coeficientes de la función objetivo de las variables de decisión del Primal, son los
valores en orden ascendente de las variables de holgura del Dual
EJERCICIO DE APLICACIÓN DEL DUAL
La National Business Machines (NBM) produce y vende dos tipos de equipos de
cómputo o PC: tipo A y tipo B. Cada PC tipo A es vendida con un ingreso de $40 y
cada PC tipo B es vendida con un ingreso de $60. Ambas maquinas son ensambladas y
empacadas para lo cual se tiene la siguiente información:
Operación Hrs PC A Hrs PC B Capacidad
Ensamble hr 3 hr 2 hr 2000 hrs
Empaque hrs 1 hr 2 hr 1000 hrs
Formule el modelo Primal y el modelo dual. Interprete variables primales y variables
duales.

X1= Nro. de PC tipo A a producir y vender

X2= Nro. de PC tipo B a producir y vender

PRIMAL -Xi DUAL - Yj

Max Z=40X1 + 60X2 VHP VDD Min W=2000Y1 +1000Y2 VHD VDP
s.a (1) 3X1 + 2X2 <= 2000 S1 Y1 s.a (1) 3Y1 + Y2 >= 40 S1´ X1
(2) X1 +2X2 <=1000 S2 Y2 (2) 2Y1 +2Y2>=60 S2´ X2
X1,X2 >=0 Y1,Y2>=0
Tabla optima:

PRIMAL Variables de Variables de

decision holgura
VB B X1 X2 S1 S2
X1= 500 1 0 1/2 -1/2
X2= 250 0 1 -1/4 3/4
Z= 35.000 0 0 5 25
W S1´ S2´ Y1 Y2
DUAL Variables de Variables de
holgura decision

Variables primales:
X1*= 500 PC tipo A se deben producir y vender
X2*= 250 PC tipo B se deben producir y vender
S1*= 0 No sobran horas de ensamble
S2*=0 No sobran horas de empaque
Z*= El máximo ingreso es de $35.000

Variables duales:
Y1*=La contribución marginal de 1 hora de ensamble es de $5
Y2*= La contribución marginal de 1 hora de empaque es de $25
S1´*= Se recomienda producir y vender PC tipo A.
S2´*= Se recomienda producir y vender PC tipo B.
W*= La mínima contribución de los recursos es de $35.000
 EL PROBLEMA DEL DUAL

Ej:

Min Z = 3X1 + 4X2

s.a (1) 5X1 + 3X2 >= 10
(2) X1 + X2 = 12
X1,X2>=0

Min Z = 3X1 + 4X2

s.a (1) 5X1 + 3X2 >= 10
(2)` X1 + X2 >= 12
(2)” X1 + X2 <= 12
X1,X2>=0

Min Z = 3X1 + 4X2

s.a (1) 5X1 + 3X2 >= 10
(2)` X1 + X2 >= 12
(2)” - X1 - X2 >= -12
X1,X2>=0

PRIMAL - X DUAL - Y

Min Z = 3X1 + 4X2 VHP VDD Max W = 10Y1 + 12Y2 -12Y3 VHD VDP
s.a (1) 5X1 + 3X2 >= 10 -S1 Y1 s.a(1)5Y1+Y2-Y3<=3 S1` X1
(2) X1 + X2 >= 12 -S2 Y2 (2)3Y1 +Y2-Y3<=4 S2` X2
(3) - X1 - X2 >= -12 -S3 Y3 Y1,Y2,Y3>=0
X1,X2>=0

Ejercicio: La Hilandería Cordillera produce dos tipos de tela, cada una varía en el procesos
de fabricación. La tela de lujo requiere 18 horas de tintura, 9 horas de estampado, 1 hora de
corte y produce una utilidad de $ 400 el metro; la tela estándar necesita 3 horas de tintura, 4
horas de estampado, 12 minutos de corte y produce una utilidad de $ 200 el metro; se
dispone de 800 horas para tintura, 600 horas para estampado y 40 horas de corte cada mes.

- Formule el modelo primal

- Formule el modelo dual
- Interprete las variables del Primal
- Interprete las variables del dual

X1=# metros de tela de lujo a producir

X1=# metros de tela de estándar a producir
 PRIMAL
Max Z= 400X1 + 200X2 VHP VDD
s.a (1) 18X1 + 3X2 <= 800 S1 Y1 horas de tintura
(2) 9X1 + 4X2 <= 600 S2 Y2 horas de estampado
(3) X1 + (1/5) X2<= 40 S3 Y3 horas de corte
X1,X2>=0
DUAL
Min W = 800Y1+600Y2+40Y3 VHD VDP
s.a (1) 18Y1+9Y2 +Y3 >= 400 -S1` X1
(2) 3Y1+4Y2+(1/5)Y3 >= 200 -S2` X2
Y1,Y2,Y3>=0

Tabla optima:

PRIMAL VDP VHP

VB B X1 X2 S1 S2 S3
S1= 350 11 0 1 -0.8 0
X2= 150 2 1 0 0.2 0
S3= 10 0.5 0 0 -0.1 1
Z 30000 50 0 0 50 0
W S1` S2` Y1 Y2 Y3
DUAL VHD VDD

Interpretar variables primales

X1=0. No se producen metros de tela de lujo
X2= Se deben producir 150 metros de tela estándar
S1=350 Sobran 350 horas de tintura
S2=0. No sobran horas de estampado
S3=10. Se dejan de usar 10 horas de corte
Z= La máxima utilidad es de $30000

Interpretar variables duales

Y1=0. No hay contribución marginal de las horas de tintura

Y2=50. La contribución marginal de 1 hora de estampado es de $50
Y3=0. No hay contribución marginal por cada hora de corte.
S1`=50. Se dejan de ganar $50 por cada metro de tela de lujo que se produzca.
S2`=0. Se recomienda producir tela estándar
W= La mínima contribución marginal de los recursos es de $30000.
Una compañía fabrica dos clases de vestidos de lana, el vestido A es de mayor
calidad que el vestido B. La ganancia que se obtiene en uno y otro es de $ 100 y $
20 respectivamente. Cada vestido de tipo A requiere para su elaboración el doble
de tiempo que el tipo B . La compañía tiene una capacidad tal que si solo fabricará
vestidos tipo A haría 200 diarios. El abastecimiento de lana es suficiente para 600
diarios, tanto el tipo A como el B. El vestido tipo A requiere una estola al cuello, el
B requiere 2 estolas y se tienen 400 estolas diarias.

PRIMAL
Max Z = 100 x1 + 20 x2
s.a (1) 1x1 + 0.5x2 <= 200 S1 Y1 unidades de tiempo
(2) x1 + x2 <= 600 S2 Y2 lana para 600 vestidos
(3) x1 + 2x2 <= 400 S3 Y3 disponibilidad estolas
x1,x2 >= 0

Otra formulación de tiempo 2x1 + 1x2 <= 400

DUAL:
Min W = 200Y1+600Y2+400Y3
s.a (1) Y1 +Y2 +Y3 >= 100 S1` X1
(2) 0.5Y1+Y2 +2Y3 >= 20 S2` X2
Y1,Y2,Y3>=0
Tablero Optimo
V.B b x1 x2 S1 S2 S3
x1 200 1 0.5 1 0 0
S2 400 0 0.5 -1 1 0
S3 200 0 1.5 -1 0 1
Z 20.000 0 30 100 0 0
W S1` S2` Y1 Y2 Y3

Variables Primales:
X1= Se deben fabricar 200 vestidos tipo A
X2= No se deben fabricar vestidos tipo B
S1= No sobra tiempo para la producción de vestidos
S2= Sobra lana para 400 vestidos. Se deja de usar lana para 400 vestidos.
S3=Sobran 200 estolas
Z= la máxima utilidad es de $20000

Variables Duales:
Y1= La contribución marginal por cada unidad de tiempo es de $100
Y2= No contribución marginal de la lana para producir vestidos. La contribución
margina de la lana de cada vestido es de $0.
Y3= No hay contribución marginal por cada estola.
S1`= Se recomienda producir vestidos tipo A
S2`= Si se produce un vestido tipo B se dejan de ganar $30
W= La mínima contribución de los recursos es de $20000
 EL PROBLEMA DEL TRANSPORTE
Xij = # de unidades a enviar desde la oferta i hasta la demanda j
Cij = Costo de enviar una unidad desde la oferta i hasta la demanda j

MIN Z(Costos de transporte) = ∑ ∑ Cij Xij

s.a

∑ ∑ Xij <=Oi Oferta i = 1,m

i j
∑ ∑ Xij >=Dj Demanda j =1,n
ji
Xij >= 0 y Entero

Oferta i = 1,m Demanda j= 1,n

1 1

2 2

m n

EL ALGORITMO DEL TRANSPORTE

FASE 0: Preliminares de un problema de transporte

1. Hacer la tabla de costos de transporte

2. Hacer la oferta total igual a la demanda total, creando una oferta o demanda ficticia con la
diferencia inicial. Oferta=Demanda

FASE 1: Encontrar una solución básica factible inicial

Método de vógel:
1. Buscar los dos valores menores de cada fila y columna, y colocar su diferencia delante
dicha fila o columna.
2. Se escoge la mayor de estas diferencias y se entra asignar por dicha fila o columna
3. Se selecciona el menor costo de la fila o columna por la cual se entró y se le asigna lo
máximo que se pueda
4. Se tacha la fila o columna que quede satisfecha. Vuelve al paso 1 y termina el proceso
cuando no haya más que asignar.

CONDICIONES (Que se deben cumplir al final de la FASE 1)

M= # ofertas y n= # demandas

1. Deben existir m+n-1 variables básicas asignadas

2. Xij >= 0 y Entero
3. Las variables asignadas no deben formar ciclos o vueltas
FASE 2: Optimizar la solución inicial que tenemos

Métodos de las variables duales, donde Cij=Ui+Vj+dij

Xij

Cij

Costo básico

dij

C ij
Costo no básico

Cij = Costo de enviar una unidad desde el origen i hasta el destino j

Ui = Coeficiente de la fila i
Vj = Coeficiente de la columna j
dij = Costo marginal o variable dual

1. Tablero de costos básicos (TCB)

Si la actividad se realiza dij = 0, osea Cij = Ui+Vj
1.1 Colocar el valor de cero al coeficiente de la fila o columna donde haya mayor número
de asignaciones.
1.2 Calcular los valores de los coeficientes Ui y Vj con la fórmula Cij = Ui + Vj

2. Tablero de costos no básicos (TCNB)

Encontrar costos marginales para variables no básicas con la fórmula dij= Cij –(Ui+Vj)
2.1 Calcular el dij a partir de los coeficientes Ui y Vj del TCB anterior,
Evaluar el menor dij así:
- Si dij > 0 la solución es óptima y termina el método
- Si dij = 0 la solución es óptima múltiple y termina el método
- Si dij < 0 seguir al paso 3.

3. Hacer una asignación en la celda del dij más negativo, (El costo Cij de dicha celda
se convierte en básico)
3.1 A partir de la nueva asignación se hace una trayectoria vertical u horizontal a través de
los costos básicos.
3.2 Cada esquina en ángulo recto de la trayectoria debe estar en un costo básico
 3.3 Colocar el signo (+) en la nueva celda a asignar, luego dar la vuelta por la trayectoria
colocando signos alternados (-) y (+) en los costos básicos que lo requieran de la
trayectoria (Se debe mantener el equilibrio de cada oferta y cada demanda).
3.4 Se toma la menor cantidad de las celdas negativas, sumándola a las celdas con signo
(+) y restándola a las celdas con signo (-).
Se revisa si cumple con las condiciones de la FASE 1 y se evalúa si esta solución es
óptima a partir del paso 1 de la FASE 2.

Xij

Cij

Costo básico

dij

C ij
Costo no básico

EJERCICIO:
Una compañía tiene huertas de naranjos en A, B y C con una oferta 400, 800 y 600 toneladas
respectivamente. También tiene tres instalaciones fabriles para convertir la fruta de jugo X, Y y Z
con capacidades 600, 1000 y 200 toneladas respectivamente. La fruta debe cosecharse y
transportarse desde las huertas hasta las plantas de los concentrados. Resuelva el programa óptimo
de transporte dados los siguientes costos: ($/ton). Utilice método vogel y variables duales.

Huerta/Plantas X Y Z Oferta i
A $10 5 6 400 ton
B 8 5 9 800
C 12 4 5 600
Demanda j 600 1000 200 1800

Resuelva por el método del transporte e interprete.

Fase 0: Oi =Dj 1800=1800

Z(Costos de transporte) = ∑ ∑ Cij Xij

Z= 400*10 +800*5+ 200*12 + 200*4 +200*5 = $12200 El costo inicial
FASE I: Solución inicial – método Vogel

planta X Y Z Oi
huerta
A 400 400
10 5 6 1 1
B 800 800 0
8 5 9 3
C 200 200 200 600 0
12 4 5 1 1
Dj 0 0 1800
600 1000 200 1800
2 1 1
2 1 1

planta X Y Z
huerta
A X11
10 5 6
B X22
8 5 9
C X31 X32 X33
12 4 5

Método de vógel:
- Buscar los dos valores menores de cada fila y columna, y colocar su diferencia delante
dicha fila o columna.
- Se escoge la mayor de estas diferencias y se entra asignar por dicha fila o columna
- Se selecciona el menor costo de la fila o columna por la cual se entró y se le asigna lo
máximo que se pueda
- Se tacha la fila o columna que quede satisfecha. Vuelve al paso 1 y termina el proceso
cuando no haya más que asignar.

CONDICIONES (Que se deben cumplir al final de la FASE 1)

1. Deben existir m+n-1 variables básicas asignadas m filas= 3 ncolumnas =3
m+n-1 = 3 + 3 -1 = 5 asignaciones = 5 variables basicas

2. Xij >= 0 y Entero 400 800 200 200 200

3. Las variables asignadas no deben formar ciclos o vueltas

planta X Y Z Oi
huerta
A 400 400
10 5 6
B 800 800
8 5 9
C 200 200 200 600
12 4 5
Dj
600 1000 200
FASE 2: Optimizar la solución – Método de las variables duales

Tabla de costos basicos

planta X Y Z Ui
huerta
A 400 U1=-2
10
B 800 U2=1
5
C 200 200 200 U3=0
12 4 5
Vj V1=12 V2=4 V3=5

Costo básico Cij = Ui + Vj

1. Deben existir m+n-1 variables básicas asignadas m filas= 3 columnas =3

m+n-1 = 3 + 3 -1 = 5 asignaciones = 5 variables básicas

2. Xij >= 0 y Entero 400 800 200 200 200

3. Las variables asignadas no deben formar ciclos o vueltas

Tablero de costos no básicos

planta X Y Z Ui
huerta
A 3 3 U1=-2
5 6
B -5 + - U2=1
8 9
C - + U3=0

Vj V1=12 V2=4 V3=5

Costo no básico dij= Cij –(Ui+Vj)

D12= 5 – (-2+4) =3
D13= 6 –(-2+5)=3
D21= 8 – (1+12) = -5
D23=9 –(1+5)= 3

Min dij = -5= d21

Tabla completa

planta X Y Z Ui
huerta
A 400 3 3 U1=-2
10 5 6
B -5 + 800 - U2=1
8 5 9
C 200 - 200 + 200 U3=0
12 4 5
Vj V1=12 V2=4 V3=5

Valor a sumar y restar = mínimo asignado (-) (800,200) = 200

U3=4-(-3) =7

planta X Y Z Ui
huerta
A 400 -2 -2
10 5 6 10
B 200 600 3
8 5 9 8
C 5 400 200
12 4 5 7
Vj 0 -3 -2

D12=5-(10-3) =-2

D13=6-(10-2)=-2

D23=9-(8-2)=+3

D31=12- (7+0)=5

- Mínima cantidad (-) min ( )

planta X Y Z Ui
huerta
A

C
 Vj

dij

C ij
 EL PROBLEMA DEL TRANSPORTE
EJERCICIO:
Una compañía tiene huertas de naranjos en A, B y C con una oferta 400, 800 y 600 toneladas
respectivamente. También tiene tres instalaciones fabriles para convertir la fruta de jugo X, Y y Z
con capacidades 600, 1000 y 200 toneladas respectivamente. La fruta debe cosecharse y
transportarse desde las huertas hasta las plantas de los concentrados. Resuelva el programa óptimo
de transporte dados los siguientes costos: ($/ton). Utilice método vogel y variables duales.

Huerta/Plantas X Y Z Oferta i
A $10 5 6 400 ton
B 8 5 9 800
C 12 4 5 600
Demanda j 600 1000 200 1800

Resuelva por el método del transporte e interprete.

Fase 0: Oi =Dj 1800=1800

Z(Costos de transporte) = ∑ ∑ Cij Xij

Z= 400*10 +800*5+ 200*12 + 200*4 +200*5 = $12200 El costo inicial

FASE I: Solución inicial – método Vogel

planta X Y Z Oi
huerta
A 400 400
10 5 6 1 1
B 800 800 0
8 5 9 3
C 200 200 200 600 0
12 4 5 1 1
Dj 0 0 1800
600 1000 200 1800
2 1 1
2 1 1

planta X Y Z
huerta
A X11
10 5 6
B X22
8 5 9
C X31 X32 X33
12 4 5

Método de vógel:
- Buscar los dos valores menores de cada fila y columna, y colocar su diferencia delante
dicha fila o columna.
- Se escoge la mayor de estas diferencias y se entra asignar por dicha fila o columna
 - Se selecciona el menor costo de la fila o columna por la cual se entró y se le asigna lo
máximo que se pueda
- Se tacha la fila o columna que quede satisfecha. Vuelve al paso 1 y termina el proceso
cuando no haya más que asignar.

CONDICIONES (Que se deben cumplir al final de la FASE 1)

1. Deben existir m+n-1 variables básicas asignadas m filas= 3 ncolumnas =3
m+n-1 = 3 + 3 -1 = 5 asignaciones = 5 variables basicas

2. Xij >= 0 y Entero 400 800 200 200 200

3. Las variables asignadas no deben formar ciclos o vueltas

planta X Y Z Oi
huerta
A 400 400
10 5 6
B 800 800
8 5 9
C 200 200 200 600
12 4 5
Dj
600 1000 200

FASE 2: Optimizar la solución – Método de las variables duales

Tabla de costos basicos

planta X Y Z Ui
huerta
A 400 U1=-2
10
B 800 U2=1
5
C 200 200 200 U3=0
12 4 5
Vj V1=12 V2=4 V3=5

Costo básico Cij = Ui + Vj

1. Deben existir m+n-1 variables básicas asignadas m filas= 3 columnas =3

m+n-1 = 3 + 3 -1 = 5 asignaciones = 5 variables básicas

2. Xij >= 0 y Entero 400 800 200 200 200

3. Las variables asignadas no deben formar ciclos o vueltas

Tablero de costos no básicos

planta X Y Z Ui
huerta
A 3 3 U1=-2
5 6
B -5 + - U2=1
8 9
C - + U3=0

Vj V1=12 V2=4 V3=5

Costo no básico dij= Cij –(Ui+Vj)

D12= 5 – (-2+4) =3
D13= 6 –(-2+5)=3
D21= 8 – (1+12) = -5
D23=9 –(1+5)= 3

Min dij = -5= d21

Tabla completa

planta X Y Z Ui
huerta
A 400 3 3 U1=-2
10 5 6
B -5 + 800 - U2=1
8 5 9
C 200 - 200 + 200 U3=0
12 4 5
Vj V1=12 V2=4 V3=5

Valor a sumar y restar = mínimo asignado (-) (800,200) = 200

U3=4-(-3) =7

planta X Y Z Ui
huerta
A 400 - -2 -2 +
10 5 6 10
B 200 + 600 - 3
8 5 9 8
C 5 400 + 200 -
12 4 5 7
Vj 0 -3 -2
 D12=5-(10-3) =-2
D13=6-(10-2)=-2
D23=9-(8-2)=+3
D31=12- (7+0)=5

- Mínima cantidad (-) min (400,600,200)

planta X Y Z Ui
huerta
A 200 - -2 + 200
10 5 6 0
B 400 + 400 - 5
8 5 9 -2
C 5 600 2
12 4 5 -3
Vj 10 7 6

Cij = Ui + Vj

Costo no básico dij= Cij –(Ui+Vj)

D12=5-(0+7)=-2
D23=9- (-2+6)= 5
D31=12-(-3+10)= 5
D33= 5-(-3+6) =2

- Mínima cantidad (-) min (200,400)

planta X Y Z Ui
huerta
A 2 200 200
10 5 6 5
B 600 200 3
8 5 9 5
C 5 600 0
12 4 5 4
Vj
3 0 1

dij= Cij –(Ui+Vj)

d11= 10-(5+3)=2
d23=9-(5+1)=3
d31=12-(4+3)= 5
d33=5-(4+1)=0
Interpretación:
Desde la huerta A hasta la planta Y se envían 200 Ton.
Desde la huerta A hasta la planta Z se envían 200 Ton.
Desde la huerta B hasta la planta X se envían 600 Ton.
Desde la huerta B hasta la planta Y se envían 200 Ton.
Desde la huerta c hasta la planta Y se envían 600 Ton.
Costo mínimo =200*5+200*6+ 600*8+200*5+600*4 =$10400
EJERCICIO 2:
Una compañía está tratando de programar sus vehículos de arrastre para la próxima semana. La
compañía tiene vehículos de arrastre dispersos en tres ciudades del estado: 40 en Clearwater, 100
en New smyrna y 200 en Orlando. Para la próxima semana deben recoger casas móviles y
trasladarlas desde otras tres ciudades: 50 de Ft Myers, 125 de Monticello y 225 de Miami. Los
costos estimados para mandar un vehículo a cada una de estas ciudades se dan a continuación:
¿Como se deben asignar los tractores para minimizar el costo?

A
DE Ft. Myers Monticello Miami
Clearwater 87 89 91
New Smyma 94 92 88
Orlando 92 89 91

Resolver manualmente y remitir resuelto de manera individual en pdf y escaneado .

A
DE Ft. Myers Monticello Miami Oferta
Clearwater 87 89 91 40
New Smyma 94 92 88 100
Orlando 92 89 91 200
Ficticia 0 0 0 60
Demanda 400
50 125 225 400

Oferta = 40+100+200 = 340

Demanda = 50+125+225 = 400

Demanda = Oferta
400 = 340 +60 ficticias

FASE I Método Vogel. Solución inicial

Ciudad Ft Mo Mi Oi
Ciudad
Cl 40 40 2 2
87 89 91
Ne 100 100 4 4 4
94 92 88
Or 10 65 125 200 2 2 2
92 89 91
60 60 0
Ficticia 0 0 0
Dj 50 125 225 400
400
87 89 88
5 0 3
2 3 3
1. Deben existir m+n-1 variables básicas asignadas m filas= 4 columnas =3
m+n-1 = 4 + 3 -1 = 6 asignaciones = 6 variables básicas

2. Xij >= 0 y Entero 40 100 10 65 125 60

3. Las variables asignadas no deben formar ciclos o vueltas

FASE II: Método de variables duales

Ciudad Ft Mo Mi Ui
Ciudad
Cl 40 5 5
87 89 91 -5
Ne 5 6 100
9294 88 -3
Or 10- 65 + 125
92 89 91 0
-3 + 60 - -2
Ficticia 0 0 0 -89
92 89 91
Vj

dij= Cij –(Ui+Vj)

d41= 0-(-89+92)= -3
d41= 0-(-89+91)= -2

Ciudad Ft Mo Mi Ui
Ciudad
Cl 40 2 2
87 89 91 87
Ne 8 6 100
9294 88 86
Or 3 75 + 125 -
92 89 91 89
10 50 - -2 +
Ficticia 0 0 0 0

Vj 0 0 2

Ciudad Ft Mo Mi Ui
Ciudad
Cl 40 4 4
87 89 91 87
Ne 6 6 100
94 92 88 88
Or 1 125 75
92 89 91 91
10 2 50
Ficticia 0 0 0 0
0 -2 0
Vj
Desde Clearwater hasta Ft. Myers se deben enviar 40 vehiculos

Desde New Smyma hasta Miami se deben enviar 100 vehiculos

Desde Orlando hasta Monticello se deben enviar 125 vehiculos

Desde Orlando hasta Miami se deben enviar 75 vehiculos

El costo mínimo es de= 40*87+100*88+125*89+75*91 =$30230

 EL PROBLEMA DEL TRANSPORTE

1. Una compañía tiene huertas de naranjos en I, II y III con una oferta 60, 45 y
75 toneladas respectivamente. También tiene cuatro instalaciones fabriles
para convertir la fruta de jugo A, B, C y D con capacidades 24, 30, 36 y 45
toneladas respectivamente. La fruta debe cosecharse y transportarse desde
las huertas hasta las plantas de los concentrados. Resuelva el programa
óptimo de transporte dados los siguientes costos: ($/ton).
Huerta/Plantas
A B C D
I. 9 6 15 6
II. 6 9 12 15
III. 12 3 6 9

Demanda
A B C D Oi

I. 9 6 15 6
60
II. 6 9 12 15
45
III. 12 3 6 9
75
24 30 36 45
Dj

Oi = 60+45+75=180
Dj = 24+30+36+45=135

Oi =Dj
180=135 +45
 Demanda
A B C D Fict Oi
15 45
I. $9 $6 $15 $6 0 60 6 0 0 3
45
II. 6 9 12 15 0 45 6
9 30 36
III. $12 $3 $6 $9 0 75 3 3 6 3
180
Dj 24 30 36 45 45 180
3 3 6 3 0
3 3 9 3
3 3 3
3 3

Demanda
A B C D Fict Ui
15 6 12 45 -3
I. $9 $6 $15 $6 0 -3
0+ 12 12 12 45-
II. 6 9 12 15 0 -6
9- 30 36 0 -6+
III. $12 $3 $6 $9 0 0

Vj 12 3 6 9 6

Dij=Cij-(Ui+Vj)

D12= 6 – (-3+3)=6
D13=15-(-3+6)=12
D15=0-(-3+6)=-3
…
D35=0-(0+6)=-6

Minimo dij (-3,-6) minimo(-) (45,9)

 1. M+n-1 =3+5-1= 7 variables básicas

2. Xij>=0 y entero

3. No ciclos

Demanda
A B C D Fict Ui
15 - 0 6 45 -3+
I. $9 $6 $15 $6 0 3
9 + 6 12 6
36 -
II. 6 9 12 15 0 0
6 30 36 6 9
III. $12 $3 $6 $9 0 0

Vj 6 3 6 3 0

D12=6-(3+3)=00
..
D15=0-(3+0)=-3

Minimo (-) (15,36)

Demanda
A B C D Fict Ui
3 3 9 45 15
I. 9 $6 $15 $6 0 0
24 6 6 9 21
II. 6 9 12 15 0 0
6 30 36 3 9
III. $12 $3 $6 $9 0 0

Vj 6 3 6 6 0
Oferta Demanda Cantidad
I D 45 unidades
II A 24
III B 30
III C 36
Costo de envío= 45*6+24*6+30*3+36*6 =$720
 1. Una fábrica de muebles fabrica bibliotecas, escritorios, sillas y camas, para
lo cual tiene una capacidad de producción medida por la cantidad de
materia prima disponible (120 unidad de metal y 420 de madera) y la
disponibilidad de 225 horas de mano de obra. Los requerimientos para cada
tipo de mueble y los beneficios de la venta de cada uno son:
• una biblioteca requiere 3 horas de trabajo, una unidad de metal y 4 de madera,
y da un beneficio de 15$.
• un escritorio requiere dos horas de trabajo, una unidad de metal y 3 de
madera y da un beneficio de 13$.
• una silla requiere una hora de trabajo, una unidad de metal y 3 de madera, y
da un beneficio de 12 $.
• una cama requiere 2 horas de trabajo, una unidad de metal y 4 de madera y
da un beneficio de 14$.

Suponiendo que se puede vender todo lo que se produce, determinar el programa

de producción que maximice el beneficio de la empresa.

VB B X1 X2 X3 X4 S1 S2 S3
X2 30 2 1 1 0 2 0 -1
S2 7.5 -0.5 0 0 0 -0.5 1 0
X4 82.5 -0.5 0 0 1 -1.5 0 1
Z 1.545 $4 0 $1 0 $5 $0 $1
W S1´ S2´ S3´ S4´ Y1 Y2 Y3

PRIMAL
Max Z =15X1+13X2+12X3+14X4
s.a (1) X1 +X2 +X3 +X4 <=120 metal S1 Y1
(2) 4X1 +3X2 +3X3 +4X4<=420 madera S2 Y2
(3) 3X1 +2X2+ X3 +2X4<=225 horas S3 Y3
X1,X2,X3,X4>=0

DUAL min W= 120Y1+420Y2+225Y3

s.a (1) Y1+ 4Y2+ 3Y3 >= 15 X1 S1´

(2) Y1+2Y2+3Y3>= 13 X2 S2´
(3) Y1+3Y2+Y3 >= 12 X3 S3´
(4) Y1+4Y2+2Y3>= 14 X4 S4´
Y1,Y2,Y3>=0

a- Interprete las variables del primal

X1= No se deben producir bibliotecas
X2= Se deben producir 30 escritorios
X3= No se deben producir sillas
X4= Se deben producir 82.5 camas
S1= No sobra recurso metal
S2= Sobran 7,5 unidades de madera
S3= No sobra recurso tiempo en horas
Z= La máxima utilidad es de $1545
 b- Interprete las variables del Dual

Y1= La contribución marginal de cada unidad de metal es de $5

Y2= La contribución marginal de cada unidad de madera es de $0
Y3= La contribución margina de cada hora es de $1
S1`= Por cada biblioteca que se produzca se dejan de ganar $4
S2`= Se recomienda producir escritorios
S3`= Por cada silla que se produzca se dejan de ganar $1.
S4`= Se recomienda producir camas
W= La mínima contribución de los recursos es de $1545
 EL PROBLEMA DEL TRANSPORTE

FASE O: Preliminares de un problema de transporte

1. Hacer la tabla de costos de transporte

2. Hacer la oferta total igual a la demanda total, creando una oferta o demanda ficticia con la
diferencia inicial.

FASE 1: Encontrar una solución básica factible inicial

CONDICIONES (Que se deben cumplir al final de la FASE 1)

1. Deben existir m+n-1 variables básicas asignadas
2. Xij >= 0 y Entero
3. Las variables asignadas no deben formar ciclos o vueltas

Método de vógel:
1. Buscar los dos valores menores de cada fila y columna, y colocar su diferencia delante
dicha fila o columna.
2. Se escoge la mayor de estas diferencias y se entra asignar por dicha fila o columna
3. Se selecciona el menor costo de la fila o columna por la cual se entró y se le asigna lo
máximo que se pueda
4. Se tacha la fila o columna que quede satisfecha. Vuelve al paso 1 y termina el proceso
cuando no haya más que asignar.

FASE 2: Optimizar la solución inicial que tenemos

Métodos de las variables duales, donde Cij=Ui+Vj+dij

Cij = Costo de enviar una unidad desde el origen i hasta el destino j

Ui = Coeficiente de la fila i
Vj = Coeficiente de la columna j
dij = Costo marginal

1. Tablero de costos básicos (TCB)

Si la actividad se realiza dij = 0, osea Cij = Ui+Vj
1.1 Colocar el valor de cero al coeficiente de la fila o columna donde haya mayor número
de asignaciones.
1.2 Calcular los valores de los coeficientes Ui y Vj con la fórmula Cij = Ui + Vj

2. Tablero de costos no básicos (TCNB)

Encontrar costos marginales para variables no básicas con la fórmula dij= Cij –(Ui+Vj)
2.1 Calcular el dij a partir de los coeficientes Ui y Vj del TCB anterior,
Evaluar el menor dij así:
- Si dij > 0 la solución es óptima y termina el método
- Si dij = 0 la solución es óptima múltiple y termina el método
- Si dij < 0 seguir al paso 3.

3. Hacer una asignación en la celda del dij más negativo, (El costo Cij de dicha celda se
convierte en básico)
3.1 A partir de la nueva asignación se hace una trayectoria vertical u horizontal a través de
los costos básicos.
3.2 Cada esquina en ángulo recto de la trayectoria debe estar en un costo básico
3.3 Colocar el signo (+) en la nueva celda a asignar, luego dar la vuelta por la trayectoria
colocando signos alternados (-) y (+) en los costos básicos que lo requieran de la
trayectoria (Se debe mantener el equilibrio de cada oferta y cada demanda).
3.4 Se toma la menor cantidad de las celdas negativas, sumándola a las celdas con signo
(+) y restándola a las celdas con signo (-).
Se revisa si cumple con las condiciones de la FASE 1 y se evalúa si esta solución es
óptima a partir del paso 1 de la FASE 2.
EL PROBLEMA DEL TRANSPORTE

1. Una compañía tiene huertas de naranjos en I, II y III con una oferta 60, 45 y
75 toneladas respectivamente. También tiene cuatro instalaciones fabriles
para convertir la fruta de jugo A, B, C y D con capacidades 24, 30, 36 y 45
toneladas respectivamente. La fruta debe cosecharse y transportarse desde
las huertas hasta las plantas de los concentrados. Resuelva el programa
óptimo de transporte dados los siguientes costos: ($/ton).
Huerta/Plantas
A B C D
I. 9 6 15 6
II. 6 9 12 15
III. 12 3 6 9

Determinar el plan óptimo de transporte

2. Una compañía tiene tres plantas de producción y tres fabricas de alfombras que
requieren la producción de las plantas. Las plantas ofrecen 35, 30 y 45 alfombras
y las tres fabricas demandan 53, 28 y 29 alfombras. Dada la siguiente tabla de
costos de transporte, cual debe ser el programa óptimo.
FABRICAS A B C
PLANTAS
I 2 3 5
II 8 7 10
III 4 6 8

3. Una empresa tiene cinco almacenes desde los cuales puede embarcar al
menudeo. La demanda de latas del producto es de 120, 120, 40 y 20 unidades
respectivamente para las tiendas minoristas A, B, C y D. El Inventario de la
empresa en el almacén 1 es de 20 unidades, en el 2 es de 40, en el 3 es de 60, en
el 4 de 80 y en el almacén 5 de 100 unidades. Determine el programa óptimo de
embarque dada la siguiente tabla de costos de envío:

A B C D
Minoristas
Almacén
1 20 40 10 14
2 26 18 24 16
3 8 30 14 18
4 28 14 2 0
5 6 24 10 38

Una compañía de envía de las instalaciones A, B y C suministra a los distribuidores D, E,

F y G. Las capacidades mensuales son 20, 30 y 50 unidades respectivamente para las
instalaciones. Los requerimientos mensuales de los distribuidores son : 10, 15, 40 y 30
unidades, respectivamente. Los costos unitarios de envío son los siguientes :
Desde/Hasta D E F G
A 10 20 10 0
B 10 18 10 20
C 20 20 30 10

Determinar el plan óptimo de transporte

EL PROBLEMA DEL DUAL E INTERPRETACION ECONOMICA

1. Una compañía fabrica y vende tres líneas de raquetas de tenis A, B y C. El

proceso de manufactura de las raquetas hace que e requieran dos operaciones de
producción. Cada raqueta requiere de 3 horas de tiempo de producción en la
operación 1. En la operación 2 la raqueta A requiere de 2 horas de tiempo de
producción; la raqueta B requiere de 4 horas y la C 5 horas. La Operación 1 tiene
50 horas de tiempo semanal y la operación 2 tiene 80 horas, se ha proyectado que
la demanda de la raqueta A no será de más de 25 por semana. Debido a que las
raquetas B y C son de calidad similar, se ha estimado que la demanda combinada
no será más de 30. La utilidad por unidad para las raquetas A, B y C es de $ 700,
$850 y $800 respectivamente.

a- Formule el modelo de
programación DUAL Max Z = 700X1+850X2+800X3
b- Interprete las variables
del primal S.A. (1) 3X1+ 3X2+ 3X3 <= 50
c- Interprete las variables del Dual (2) 2X1+ 4X2+ 5X3 <= 80
(3) X1 <= 25
(4) X2+ X3 <= 30
X1,X2,X3 >= 0

VB B X1 X2 X3 X4 X5 X6 X7
X2 17 1 1 1 0.3 0 0 0
X5 13 -2 0 1 -1.3 1 0 0
X6 25 0 0 0 0 0 1 0
X7 13 -1 0 0 -0.3 0 0 1
Z 14.167 150 0 50 283 0 0 0

2. Una fábrica de muebles fabrica bibliotecas, escritorios, sillas y camas, para

lo cual tiene una capacidad de producción medida por la cantidad de
materia prima disponible (120 unidad de metal y 420 de madera) y la
disponibilidad de 225 horas de mano de obra. Los requerimientos para cada
tipo de mueble y los beneficios de la venta de cada uno son:
• una biblioteca requiere 3 horas de trabajo, una unidad de metal y 4 de madera,
y da un beneficio de 15$.
• un escritorio requiere dos horas de trabajo, una unidad de metal y 3 de
madera y da un beneficio de 13$.
• una silla requiere una hora de trabajo, una unidad de metal y 3 de madera, y
da un beneficio de 12 $.
• una cama requiere 2 horas de trabajo, una unidad de metal y 4 de madera y
da un beneficio de 14$.

Suponiendo que se puede vender todo lo que se produce, determinar el programa

de producción que maximice el beneficio de la empresa.

VB B X1 X2 X3 X4 S1 S2 S3
X2 30 2 1 1 0 2 0 -1
S2 7.5 -0.5 0 0 0 -0.5 1 0
X4 82.5 -0.5 0 0 1 -1.5 0 1
Z 1.545 4 0 1 0 5 0 1

a- Formule el modelo de programación PRIMAL

b- Formule el modelo de programación DUAL
c- Interprete las variables del primal
d- Interprete las variables del Dual