Unidad III:

PROGRAMACIN
LINEAL
PROGRAMACIN LINEAL : se formula
siguiendo el planteamiento general:
Smbolos empleados
en Programacin Lineal
aij = coeficiente de variable j (columna) en la i-
sima ecuacin de restriccin (fila)
A = matriz con los elementos aij
b = vector valor de las restricciones, con los
elementos bi
cj = coeficientes de la variable j en la Funcin
objetivo
m = nmero de restricciones
n = nmero de variables
PROGRAMACIN LINEAL
Punto extremo: Un punto es extremo si cualquier
segmento de la regin factible que contiene al
punto tiene a ste al final del segmento. Tambin
es conocido como vrtice.
El mejor vrtice debe ser el valor ptimo de la
funcin objetivo! Si el problema tiene solucin
ptima sta debe de estar en un vrtice; si tiene
mltiples soluciones ptimas al menos dos deben
de estar en punto extremos.
Es un problema de optimizacin
convexa; luego,
un ptimo local es un ptimo
global!
Resolucin: Algoritmo SIMPLEX
Resolucin: Algoritmo SIMPLEX
El Simplex Usa el concepto de Punto Esquina
(Corner Point) como base del mtodo eficiente
que proporciona la solucin
Queremos convertir esta
formulacin general a un
sistema de ecuaciones
lineales
Formulacin estndar de
Formulacin estndar de
P.L
P.L
.
.
(1)
(2)
(3)
definiciones fundamentales
definiciones fundamentales
a a) ) Una Una SOLUCION POSIBLE SOLUCION POSIBLE al problema de al problema de P.L P.L. es un vector x . es un vector x
= (x1 x2 ... = (x1 x2 ... xn xn) el cual satisface las condiciones (2) y (3). ) el cual satisface las condiciones (2) y (3).
b) Una b) Una SOLUCION BASICA SOLUCION BASICA para (2) es una solucin obtenida al para (2) es una solucin obtenida al
hacer (n hacer (n- -m) variables igual a cero y resolver por las m variables m) variables igual a cero y resolver por las m variables
restantes (siempre que el determinante de los coeficientes de restantes (siempre que el determinante de los coeficientes de
estas m variables no sea nulo). Las m variables se llaman estas m variables no sea nulo). Las m variables se llaman
variables bsicas. variables bsicas.
c) Una c) Una SOLUCION POSIBLE BASICA SOLUCION POSIBLE BASICA es una solucin bsica es una solucin bsica
que tambin satisface (3); esto es, todas las variables bsicas que tambin satisface (3); esto es, todas las variables bsicas
son no negativas. son no negativas.
d) Una d) Una SOLUCION POSIBLE BASICA NO DEGENERADA SOLUCION POSIBLE BASICA NO DEGENERADA es una es una
solucin posible bsica con exactamente solucin posible bsica con exactamente xi xi positivas, es decir, positivas, es decir,
todas las variables bsicas son positivas. todas las variables bsicas son positivas.
e) Una e) Una SOLUCION POSIBLE OPTIMA SOLUCION POSIBLE OPTIMA es una solucin que es una solucin que
tambin cumple con la (1). tambin cumple con la (1).
PROGRAMACIN LINEAL
El Simplex: Encontrando una solucin para
un conj. de ecuaciones no cuadrado
Para un mejor ordenamiento del
Para un mejor ordenamiento del
procedimiento de cmputo, se coloca el
procedimiento de cmputo, se coloca el
problema en forma tabular:
problema en forma tabular:
}
. indpdte
trmino
holgura de variables reales variables ) bsica (solucion
bsico conjunto
4 4 4 4 4 8 4 4 4 4 4 7 6 4 4 4 4 4 8 4 4 4 4 4 7 6 48 47 6
C
b
x
b
x
1
x
2
.. x
n
x
n+1
x
n+2
x
n+n
b
i
C
j
Solucin

j
SUPONEMOS FORMA ESTANDAR MAXIMIZAR
SUPONEMOS FORMA ESTANDAR MAXIMIZAR

x
x
b
b
representa a las variables base del sistema.
representa a las variables base del sistema.

c
c
b
b
coeficientes de la funcin objetivo
coeficientes de la funcin objetivo
correspondientes a esas variables base.
correspondientes a esas variables base.

c
c
j
j
coeficientes de la funcin objetivo o funcional
coeficientes de la funcin objetivo o funcional

segunda fila debajo del cuadro: se coloca la

segunda fila debajo del cuadro: se coloca la
posible solucin
posible solucin

Para saber si la sol. es ptima:

Para saber si la sol. es ptima:
valor
valor
j
j
donde
donde
j
j
=
=
Cj
Cj
-
-


aij
aij
Cb
Cb

Si
Si
j
j
> 0, la solucin
> 0, la solucin
no es ptima
no es ptima
:
:
Entra
Entra
a la
a la
solucin la variable con
solucin la variable con
j
j
mximo y
mximo y
sale
sale
la
la
variable con un valor de
variable con un valor de
b
b
i
i
/
/
a
a
ie
ie
mnimo (el
mnimo (el
subndice e indica entrante).
subndice e indica entrante).
Procedimiento del
Procedimiento del
Simplex
Simplex
1).- Convertir las desigualdades en igualdades introduciendo las variables
suplementarias o de holgura o slack no negativas apropiadas y disponer el
problema completo en forma tabular, segn lo indicado.
2).- Extraer una solucin posible e insertarla, como segunda fila debajo del
cuadro. Una solucin posible obvia es aquella que incluye solamente las
variables con vectores unitarios, siendo la solucin el valor de bi de la fila
donde aparece el nico valor no nulo de la columna. Estas variables que
constituyen la solucin se denominan conjunto bsico y se anotan en las
dos columnas a la izquierda del cuadro.
3).- Se prueba si la solucin es ptima, calculando para cada variable que no
forma parte de la solucin el j = cj - zj = cj - aij - cb
Si para todo j, el valor de j 0, la solucin es ptima y el mtodo Simplex
termina. Si algn j es positivo, la solucin NO es ptima.
4).- En el ltimo caso, se selecciona para entrar en la solucin a la variable con j
mximo. Esto se debe a que la funcin objetivo aumenta dndole valor al xj en
estudio.
La variable que debe abandonar la solucin es la que posea un valor de bi /aie
mnimo, para asegurar variables no negativas. Ese valor debe ser positivo y
finito.
5).- La tabla se modifica ahora de modo que el vector unitario de la variable de
salida queda en la variable entrante. Se encuentran los restantes coeficientes
segn Gauss-Jordan:
6).- Se vuelve a la etapa 3) y se contina hasta obtener una solucin ptima.
Ejemplo completo
Ejemplo completo
Problema Original:
Problema Original:
Max
Max
(6 x1 + 4 x2)
(6 x1 + 4 x2)
s.a.:
s.a.:
2 x1 + 4 x2
2 x1 + 4 x2

14
14
6 x1 + 3 x2
6 x1 + 3 x2

11
11
x1
x1

0
0
x2
x2

0
0
Etapa 1:
Etapa 1:
Max
Max
(6 x1 + 4 x2)
(6 x1 + 4 x2)
s.a.: 2 x1 + 4 x2 + x3 = 14
s.a.: 2 x1 + 4 x2 + x3 = 14
6 x1 + 3 x2 + x4 = 11
6 x1 + 3 x2 + x4 = 11
x1
x1

0
0
x2
x2

0
0
6 6 ) 0 . 6 0 . 2 ( 6
2 1, = i
1 = j
x Para 1 1 1 = = + =

4 4 ) 0 . 3 0 . 4 ( 4
2 1, = i
2 = j
x Para 2 2 2 = = + =

Etapa 2:
Solucin posible: variables con vectores unitarios (14, 11)
Etapa 3:
Clculo de los
j
, para j = 1, 2 (3 y 4 forman la solucin
j
= 0)
j = c
j
- a
ij
- c
bi
como
j
> 0 la
solucin no es
ptima
C
b
x
b
x
1
x
2
x
3
x
4
b
i
0 x
3
2 4 1 0 14
0 x
4
6 3 0 1 11
C
j
6 4 0 0
Solucin 0 0 14 11

j
6 4
Etapa 4:
Etapa 4:
Entra en la solucin x
Entra en la solucin x1 1
por tener el mayor
por tener el mayor
j
j
.
.
Debe abandonarla la variable que posee el
Debe abandonarla la variable que posee el
mnimo valor de
mnimo valor de
de
de
b
bi i
/
/
a
aie ie
.
.
En este caso e = 1
En este caso e = 1
(entra x
(entra x1 1
)
)
i = 1
i = 1

b
b1 1
/a
/a11 11
= 14/2 = 7 (corresponde a x
= 14/2 = 7 (corresponde a x3 3
porque el valor unitario est en i = 1)
porque el valor unitario est en i = 1)
i = 2
i = 2

b
b2 2
/a
/a21 21
= 11/6 = 1.83 (corresponde a x
= 11/6 = 1.83 (corresponde a x4 4
porque el valor unitario est en i = 2)
porque el valor unitario est en i = 2)
Vemos que el valor mnimo corresponde a x
Vemos que el valor mnimo corresponde a x4 4
,
,
por lo que debe abandonar la solucin
por lo que debe abandonar la solucin
.
.
Debemos calcular los coeficientes de x2, x4 y b tomando un elemento
pivote en el valor anterior de x1, por ejemplo 6.
Para la fila del pivote: aij / pivote
Para las restantes filas, si el pivote es el elemento akl,
por ejemplo:
kl
il kj
ij ij
a
.a a
- a ' a =
3
6
2.3
- 4
a
.a a
- a ' a
21
22 11
12 12
= = =
3 / 1
6
2.1
- 0
a
.a a
- a ' a
21
24 11
14 14
= = =
3 / 31
6
2.11
- 4 1
a
.b a
- b ' b
21
2 11
1
= = =
Etapa 5:
Etapa 5:
Modificacin de la tabla
Modificacin de la tabla
En nuestro caso:
Etapa 5:
Etapa 5:
Modificacin de la tabla (cont.)
Modificacin de la tabla (cont.)
C
b
x
b
x
1
x
2
x
3
x
4
b
i
0 x
3
0 3 1 -1/3 31/3

6 x
1
1 1/2 0 1/6 11/6
C
j
6 4 0 0
Solucin
11/6 0 31/3 0

j
0 1 0 -1

Etapa 6:
Etapa 6:
Repeticin
Repeticin
Solucin posible: x1 = 11/6; x3 = 31/3
VERIFICAR si la solucin es ptima; si no lo es, repetir el
procedimiento
DUALIDAD
DUALIDAD

Asociado con cada problema de programacin lineal
Asociado con cada problema de programacin lineal
(PRIMAL), existe un problema de optimizacin
(PRIMAL), existe un problema de optimizacin
correspondiente llamado el
correspondiente llamado el
problema dual
problema dual
.
.

La solucin ptima de cualquiera de los dos
La solucin ptima de cualquiera de los dos
problemas revela informacin de la solucin ptima
problemas revela informacin de la solucin ptima
del otro
del otro
(
(Max Max C = C = min min B puede demostrarse mediante teorema) B puede demostrarse mediante teorema)

Las variables del problema dual se pueden interpretar
Las variables del problema dual se pueden interpretar
como precios asociados a las restricciones del
como precios asociados a las restricciones del
problema original (primal), y mediante esta asociacin
problema original (primal), y mediante esta asociacin
se puede proporcionar una caracterizacin
se puede proporcionar una caracterizacin
econmicamente significativa al dual cuando haya tal
econmicamente significativa al dual cuando haya tal
caracterizacin
caracterizacin
para el primal
para el primal. .
Formulacin:
Formulacin:
Primal
Primal
Dual
Dual
Min
Min
C.
C.
X
X
max
max
b .
b .
Y
Y
s.a
s.a
s.a
s.a
A
A
.
.
X
X


b
b
A .Y C
A .Y C
X
X
0
0
Y 0
Y 0
T
T T
T
Los costos marginales son (
Los costos marginales son (
c
cj j

z
zj j
); y en el ptimo
); y en el ptimo
c
cj j

z
zj j
0.
0.
Vamos a llamarlos en este ultimo caso:
Vamos a llamarlos en este ultimo caso:
c
ck k

z
zk k
para el problema primal
para el problema primal
-
-
(
(
b
bk k

z
zk k
) para el problema dual
) para el problema dual
Tenemos que los costos marginales del problema primal
Tenemos que los costos marginales del problema primal
dan la solucin al problema dual y viceversa. Por lo tanto:
dan la solucin al problema dual y viceversa. Por lo tanto:
c
ck k

z
zk k
=
=
-
-
y
y k k
o lo que es igual,
o lo que es igual,
z
zk k
-
-
c
ck k
= y
= y k k
y
y k k
0
0

-
-

k k
= y
= y k k
-
-
b
bk k
+
+
z
zk k
= x
= x k k
x
x k k
0
0
S
Si i
=
=
y
yi i
EJEMPLO:
Interpretacin econmica de los
Interpretacin econmica de los
problemas primal
problemas primal

dual
dual
Max C
Max CT T
.X
.X
s.a
s.a
. A.X b
. A.X b
X 0
X 0
Donde los
Donde los
a
aij ij
representan el nmero de
representan el nmero de
unidades del recurso i requeridas para
unidades del recurso i requeridas para
producir una unidad del producto j; las
producir una unidad del producto j; las
bi
bi
representan el nmero mximo de unidades
representan el nmero mximo de unidades
del recurso i disponibles, y las
del recurso i disponibles, y las
c
cj j
representan
representan
el valor (utilidad) por unidad de producto j.
el valor (utilidad) por unidad de producto j.
El problema dual correspondiente es:
El problema dual correspondiente es:
min
min
b
bT T
.Y
.Y
s.a.
s.a.
A
AT T
.y
.y
C
CT T
Y 0
Y 0
( ) ( ) ( ) ? y i insumo =
i

j producto
.
j producto
i insumo valor
y
i
0 y
i

i = 1, 2, ......, m

El problema primal
El problema primal
:
:
Dada una unidad de valor
Dada una unidad de valor
para cada producto
para cada producto
c
cj j
y dado un lmite superior
y dado un lmite superior
para la disponibilidad de cada insumo
para la disponibilidad de cada insumo
b
bi i
Cuntas unidades de cada producto
Cuntas unidades de cada producto
x
xj j
deben
deben
ser producidas para maximizar el valor del
ser producidas para maximizar el valor del
producto total?
producto total?

El problema dual
El problema dual
:
:
con una disponibilidad dada
con una disponibilidad dada
de cada insumo
de cada insumo
b
bi i
y un lmite inferior al valor
y un lmite inferior al valor
unitario para cada producto
unitario para cada producto
c
cj j
. Qu valores
. Qu valores
unitarios deberan ser asignados a cada insumo
unitarios deberan ser asignados a cada insumo
y
yi i
con objeto de minimizar el valor del insumo
con objeto de minimizar el valor del insumo
total?
total?

Las variables
Las variables
y
yi i
reciben varios nombres, por
reciben varios nombres, por
ejemplo, precios contables, precios ficticios o
ejemplo, precios contables, precios ficticios o
precios virtuales.
precios virtuales.

Si
Si

Si
Si
= 0;
= 0;
yi
yi
* = 0
* = 0

recursos i sobrantes, no se
recursos i sobrantes, no se
quieren comprar ms unidades, porque su ingreso
quieren comprar ms unidades, porque su ingreso
marginal es cero y se producirn prdidas.
marginal es cero y se producirn prdidas.

Si
Si

Si
Si
0;
0;
yi
yi
* 0
* 0

la empresa aumentara las

la empresa aumentara las
unidades de sus recursos i siempre que su costo fuera
unidades de sus recursos i siempre que su costo fuera
inferior al ingreso unitario que de ella se obtiene
inferior al ingreso unitario que de ella se obtiene
Esto se hara hasta el instante en que el aumento de
Esto se hara hasta el instante en que el aumento de
recursos diera lugar a un cambio en el programa optimo.
recursos diera lugar a un cambio en el programa optimo.
El incremento de beneficio sera:
El incremento de beneficio sera:

B
B
= (
= (
yi
yi
-
-
ci
ci
).(incremento del recurso i)
).(incremento del recurso i)

Primal
Primal
muestra como se genera el ingreso
muestra como se genera el ingreso
empresarial a partir de uso de factores limitado.
empresarial a partir de uso de factores limitado.

Dual
Dual
muestra cmo se distribuye el ingreso en
muestra cmo se distribuye el ingreso en
un mercado de competencia perfecta, para retribuir los
un mercado de competencia perfecta, para retribuir los
citados recursos
citados recursos
.
.
Anlisis de sensibilidad
Anlisis de sensibilidad
La metodologa, cualquiera sea la variacin
La metodologa, cualquiera sea la variacin
propuesta, puede resumirse as:
propuesta, puede resumirse as:

Dada una solucin ptima, determinar en

Dada una solucin ptima, determinar en
que rangos del o los parmetros
que rangos del o los parmetros
escogidos la misma contina siendo
escogidos la misma contina siendo
ptima.
ptima.

Cul es, fuera de esos rangos, la

Cul es, fuera de esos rangos, la
solucin ptima que corresponde?.
solucin ptima que corresponde?.
1.
1.
-
-
Variaciones en los
Variaciones en los
coeficientes de la Funcin
coeficientes de la Funcin
Objetivo (
Objetivo (
c
c
j
j
)
)

No habr una nueva solucin ptima mientras que
No habr una nueva solucin ptima mientras que
se siga
se siga
cumpliendo
cumpliendo
:
:
j = cj
j = cj

zj = cj
zj = cj

0
0

j = m+1, n (
j = m+1, n (
1)
1)

Se puede calcular cul es el intervalo de variacin admisible
Se puede calcular cul es el intervalo de variacin admisible
de un grupo determinado
de un grupo determinado
c
ck k
(k = 1, ., n) sin ms que
(k = 1, ., n) sin ms que
sustituirlo por (c
sustituirlo por (ck k
+ c
+ ck k
) en el grupo de ecuaciones (
) en el grupo de ecuaciones (
1)
1)
.
.

Se dan dos situaciones:
Se dan dos situaciones:
ck
ck
acompaa a una variable bsica
acompaa a una variable bsica
(est en el ptimo) o no
(est en el ptimo) o no

=
m
1 i
b ik
.c a
a) Si
a) Si
c
c
k
k
acompaa a variable en la solucin
acompaa a variable en la solucin

j
j
= c
= c
j
j

[
[
c
c
1
1
.a
.a
1j
1j
+ c
+ c
2
2
.a
.a
2j
2j
+ +
+ +
(
(
cb
cb
i
i
+ c
+ c
b
b
i
i
) .a
) .a
ij
ij
+ ...... + cb
+ ...... + cb
n
n
.a
.a
nj
nj
]
]

0
0

j = m+1, .., n (
j = m+1, .., n (
2)
2)
De all, los valores
De all, los valores
max
max
y
y
min
min
de la variacin
de la variacin
c
ck k
y el intervalo correspondiente:
y el intervalo correspondiente:
c
c
k
k
+ c
+ c
k
k
,min
,min

c
c
k
k

c
c
k
k
+ c
+ c
k
k
,max
,max
b) Si
b) Si
c
ck k
no acompaa a un proceso incluido en
no acompaa a un proceso incluido en
la solucin
la solucin

k k
= (c
= (ck k
+ c
+ ck k
)
)
-
-

0
0

k
k

j = m+1, .., n (
j = m+1, .., n (
3)
3)
Si un cambio en algn o algunos ck hace que algn j fuere
positivo (caso de max Z) habra que proceder a una
postoptimizacion a partir de la tabla que proporcionaba el
ptimo en el problema primitivo: en la ella habra que
sustituir ck por su nuevo valor y transformar los
correspondientes valores de rendimientos indirectos y/o
marginales que hubieran cambiado con ck. A partir de esta
nueva situacin, continuaramos iterando hasta llegar a la
nueva solucin ptima.

=
m
1 i
i ik
.c a
2.
2.
-
-
Variaciones en los trminos
Variaciones en los trminos
independientes
independientes
b
b
i
i

Un cambio en
Un cambio en
b
bi i
no da lugar a otra solucin
no da lugar a otra solucin
si se cumple la no negatividad de variables
si se cumple la no negatividad de variables

[
[
x1*, x2*,. ., xm*
x1*, x2*,. ., xm*
]
]T T
=
=
inv
inv
[
[
a
a
ij
ij
]
]
.
.
[
[
b
b
1
1
, b
, b
2
2
, , b
, , b
m
m
]
]T T
=
=
inv
inv
[
[
A
A
]
]
.
.
[
[
b
b
1
1
, b
, b
2
2
, , b
, , b
m
m
]
]T T
Por lo tanto: sustituir
Por lo tanto: sustituir
b
b
i
i
por (
por (
b
b
i
i
+ b
+ b
i
i
) y hacer
) y hacer
que la expresin sea
que la expresin sea

0
0

[
[
x
x1 1
*, x
*, x2 2
*, ., x
*, ., xm m
*
*
]
]T T
=
=
[
[
A
A
]
]
(
(- -1 1
)
)
.
.
[
[
b
b
1
1
, b
, b
2
2
, , b
, , b
i
i
+
+
b
b
i
i
,...., b
,...., b
m
m
]
]T T

0
0
bi + bi, min bi bi + bi, max
EL PROBLEMA DE TRANSPORTE
EL PROBLEMA DE TRANSPORTE

Este tipo de problema aparece toda vez

Este tipo de problema aparece toda vez
que un determinado artculo es requerido
que un determinado artculo es requerido
desde diversos puntos (destinos) y tal
desde diversos puntos (destinos) y tal
artculo est disponible en distintos lugares
artculo est disponible en distintos lugares
(orgenes). Existe un costo por unidad
(orgenes). Existe un costo por unidad
transportada desde un origen cualquiera
transportada desde un origen cualquiera
hacia cualquier destino y el objetivo es
hacia cualquier destino y el objetivo es
cumplir con los requerimientos al
cumplir con los requerimientos al
menor
menor
costo total de transporte.
costo total de transporte.
El problema es un caso simplificado de programacin lineal
El problema es un caso simplificado de programacin lineal
(donde el conjunto de variables era formado por las
(donde el conjunto de variables era formado por las
xj
xj
y las
y las
Si y las restricciones dbiles haban sido transformadas en
Si y las restricciones dbiles haban sido transformadas en
fuertes). Aqu tambin el ptimo deber encontrarse en
fuertes). Aqu tambin el ptimo deber encontrarse en
una solucin posible bsica, es decir:
una solucin posible bsica, es decir:

todas las variables no negativas
todas las variables no negativas

(m x n)
(m x n)

(n + m
(n + m

1) = (m
1) = (m

1).(n
1).(n

1) variables del
1) variables del
conjunto de las x
conjunto de las xij ij
debern anularse.
debern anularse.

Deben existir, pues,
Deben existir, pues,
n + m
n + m

1 variables bsicas
1 variables bsicas
del total
del total
de n x m variables. Diremos que estamos frente a una
de n x m variables. Diremos que estamos frente a una
solucin independiente cuando, del conjunto de variables,
solucin independiente cuando, del conjunto de variables,
solo n + m
solo n + m

1 de ellas tiene valor no negativo y el resto

1 de ellas tiene valor no negativo y el resto
sean nulas.
sean nulas.

A cada una de las

A cada una de las
x
xij ij
la llamaremos asignacin.
la llamaremos asignacin.

La solucin independiente no es sino una

La solucin independiente no es sino una
solucin posible bsica del problema de
solucin posible bsica del problema de
transporte.
transporte.

El ptimo deber encontrarse en una solucin

El ptimo deber encontrarse en una solucin
independiente y la forma de encontrarlo consta de
independiente y la forma de encontrarlo consta de
tres etapas.
tres etapas.
a.
a.
-
-
Encontrar una solucin independiente
Encontrar una solucin independiente
b.
b.
-
-
Comprobar si la solucin es ptima. Si no
Comprobar si la solucin es ptima. Si no
serlo,
serlo,
c.
c.
-
-
Modificar la solucin encontrada y volver a
Modificar la solucin encontrada y volver a
la etapa b).
la etapa b).
-
-
Ejemplo:
Ejemplo:
Supongamos que 3 clientes, B
Supongamos que 3 clientes, B1 1
, B
, B2 2
, B
, B3 3
piden a una
piden a una
empresa maderera 6, 9 y 5 vagones de lea
empresa maderera 6, 9 y 5 vagones de lea
respectivamente. La empresa posee 2 aserraderos A
respectivamente. La empresa posee 2 aserraderos A1 1
y
y
A
A2 2
en condiciones de satisfacer el pedido con una
en condiciones de satisfacer el pedido con una
disponibilidad de 10 vagones cada uno.
disponibilidad de 10 vagones cada uno.
Los costos de transporte (en miles de pesos por vagn)
Los costos de transporte (en miles de pesos por vagn)
desde los orgenes a los destinos son:
desde los orgenes a los destinos son:
B
1
B
2
B
3
A
1
12 9 10
A
2
8 10 7
PROBLEMA DE ASIGNACION
Caso particular en donde las variables pueden ser Si-
No (1 -0)
El ejemplo tpico es el de asignar trabajadores a una
determinada tarea (un trabajador puede hacer una
sola tarea y viceversa), con un mnimo tiempo o costo