Contenido• Variables de Holgura
• Variables de Exceso
• Forma estándar
• Forma matricial
• Variables básicas y no básicas
• Forma Base
• Solución Básica
• Solución Básica Factible
• Variable de entrada y de salida
Variable de HolguraCuando se tiene una restricción en forma
𝑎11𝑥1 + 𝑎12𝑥2 +⋯+ 𝑎1𝑛𝑥𝑛 ≤ 𝑏1
Se convierte en igualdad sumando una variable llamada de holgura:
𝑎11𝑥1 + 𝑎12𝑥2 +⋯+ 𝑎1𝑛𝑥𝑛 + 𝑠1 = 𝑏1
Representa la cantidad que falta para llegar a la igualdad y debe ser ≥ 0.
Ejemplo:
4𝑥1 + 6𝑥2 ≤100
Se vuelve igualdad:4𝑥1 + 6𝑥2 + 𝑠1 = 100
Variable de ExcesoCuando se tiene una restricción en forma
𝑎11𝑥1 + 𝑎12𝑥2 +⋯+ 𝑎1𝑛𝑥𝑛 ≥ 𝑏1
Se convierte en igualdad restando una variable llamada de exceso:
𝑎11𝑥1 + 𝑎12𝑥2 +⋯+ 𝑎1𝑛𝑥𝑛 − 𝑠1 = 𝑏1
Representa la cantidad que se sobrepasa la igualdad y debe ser ≥ 0.
Ejemplo:
4𝑥1 + 6𝑥2 ≥100
Se vuelve igualdad:4𝑥1 + 6𝑥2 − 𝑠1 = 100
Forma Estándar
Ejemplo:
Se agregan variables de
holgura
Se agregan variables de
exceso
Forma Estándar
Cuando todas las restricciones del modelo original se convierten en igualdad se llama forma estándar
𝑀𝑎𝑥 𝑍 = 2𝑥1 + 5𝑥24𝑥1 + 2𝑥2 ≤ 105𝑥1 + 𝑥2 ≥ 15𝑥1, 𝑥2 ≥ 0
Modelo original
𝑀𝑎𝑥 𝑍 = 2𝑥1 + 5𝑥24𝑥1 + 2𝑥2 + 𝑠1 = 105𝑥1 + 𝑥2 − 𝑠2 = 15𝑥1, 𝑥2, 𝑠1, 𝑠2 ≥ 0
Forma estándar
Estas
variables
no
aparecen
en la fo
Forma matricialEl modelo en forma matricial es:
0
,1
1
j
ij
n
j
ij
n
j
jj
x
miibxa
xCZMax
Max z=cxAx≤bx≥0
c: vector de coeficientes de costo
A: matriz de coeficientes tecnológicos
b: vector de recursosx: vector de variables
Forma matricialEl modelo en forma matricial en forma estándar es:
0
, 1
1
j
iij
n
j
ij
n
j
jj
x
miibsxa
xCZMax Max z=(c,0)𝑥𝑠
(A, I)𝑥𝑠
=b𝑥𝑠
≥0
𝑀𝑎𝑥 𝑍 = 2𝑥1 + 3𝑥2𝑥1 + 𝑥2 + 𝑠1 = 12−2𝑥1 + 𝑥2 + 𝑠2 = 0𝑥1 + 3𝑥2 + 𝑠3 = 30𝑥1, 𝑥2, 𝑠1, 𝑠2, 𝑠3 ≥ 0
Ejemplo:
Max z= (2 3 0 0 0)
𝑥1𝑥2𝑠1𝑠2𝑠3
1 1 1 0 0−2 1 0 1 01 3 0 0 1
𝑥1𝑥2𝑠1𝑠2𝑠3
=12030
𝑥1𝑥2𝑠1𝑠2𝑠3
≥0
Variables básicas y no básicasSi un modelo tiene n variables y m restricciones donde n ≥ m, para encontrar un solución se deben darle valores de cero a n-m variables y resolver el sistema que será cuadrado mxm.
Variables básicas
Se tendrán m variables básicas
Son las que se utilizan para resolver el sistema de
ecuaciones. Generalmente son mayores iguales a 0
Variables no básicas
Se tendrán n-m variables no básicas
Son variables que valen 0 en una solución del
problema.
Variables básicas y no básicasEjemplo:
𝑀𝑎𝑥 𝑍 = 2𝑥1 + 3𝑥2𝑥1 + 𝑥2 ≤ 12−2𝑥1 + 𝑥2 ≤ 0𝑥1 + 3𝑥2 ≤ 30𝑥1, 𝑥2 ≥ 0
Modelo original
𝑀𝑎𝑥 𝑍 = 2𝑥1 + 3𝑥2𝑥1 + 𝑥2 + 𝑠1 = 12−2𝑥1 + 𝑥2 + 𝑠2 = 0𝑥1 + 3𝑥2 + 𝑠3 = 30𝑥1, 𝑥2, 𝑠1, 𝑠2, 𝑠3 ≥ 0
Forma Estándar
Variables básicas y no básicasEjemplo:
𝑀𝑎𝑥 𝑍 = 2𝑥1 + 3𝑥2𝑥1 + 𝑥2 + 𝑠1 = 12−2𝑥1 + 𝑥2 + 𝑠2 = 0𝑥1 + 3𝑥2 + 𝑠3 = 30𝑥1, 𝑥2, 𝑠1, 𝑠2, 𝑠3 ≥ 0
Forma Estándar
Este problema tiene 5 (n) variables y tres (m) restricciones. Por tanto tendrá n-m v. no básicas (con valor de cero) y m variables básicas. 2 no básicas y 3 básicas
Analicemos
los puntos
extremos en
rojo
La gráfica es:
Variables básicas y no básicasEjemplo:𝑀𝑎𝑥 𝑍 = 2𝑥1 + 3𝑥2𝑥1 + 𝑥2 + 𝑠1 = 12−2𝑥1 + 𝑥2 + 𝑠2 = 0𝑥1 + 3𝑥2 + 𝑠3 = 30𝑥1, 𝑥2, 𝑠1, 𝑠2, 𝑠3 ≥ 0
Punto 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 z
O 0 0 12 0 30 0
A 0 12 0 -12 -6 36
B 12 0 0 12 18 24
C 4 8 0 0 10 32
D 3 9 0 -3 0 33
E 30/7 60/7 -6/7 0 0 240/7
F 0 10 2 -10 0 30
g 30 0 -18 60 0 60
Variables básicas y no básicas
Punto 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 z V. B. V. No B.
O 0 0 12 0 30 0 s1, s2, s3 x1, x2
A 0 12 0 -12 -6 36 x2, s2, s3 x1, s1
B 12 0 0 12 18 24 x1, s2, s3 x2,s1
C 4 8 0 0 10 32 x1, x2, s3 s2,s1
D 3 9 0 -3 0 33 x1, x2, s2 s3, s1
E 30/7 60/7 -6/7 0 0 240/7 x1, x2, s1 s3, s2
F 0 10 2 -10 0 30 s2, x2, s1 s3,x1
G 30 0 -18 60 0 60 s2, x1, s1 s3, x2
Para identificar en cada solución las variables básicas y no básicas se consideran los valores.
Variables básicas y no básicasPara el punto O se puede observar que hay tres valores iguales a cero, y que hay una variable básica que vale 0 (S2) a esta variable se le llama variable degenerada y por tanto la solución es degenerada.
Gráficamente indica
que más de dos rectas
pasan por el mismo
punto
Forma BaseCuando se eliminan las variables no básicas(valen cero) en una solución queda un sistema:
𝐵𝑥𝐵 = 𝑏donde B se conoce como la matriz base de m x m.
La matriz base debe ser
linealmente
independiente, es
decir, que su
determinante es ≠0 y su
inversa existe 𝐵−1
𝑥𝐵 es vector columna de
variables básicas con m
componentes. Se busca 𝑥𝐵:
𝐵𝑥𝐵 = 𝑏𝐵−1𝐵𝑥𝐵 = 𝐵−1𝑏𝑥𝐵 = 𝐵−1𝑏
Para encontrar z será:Z=𝑐𝐵𝑥𝐵
donde 𝑐𝐵 es un vector renglón con los
coeficientes de las variables básicas de 𝑥𝐵
Forma BaseEjemplo:
Supongamos la solución O (origen) y forma matricial:
Max z= (2 3 0 0 0)
𝑥1𝑥2𝑠1𝑠2𝑠3
1 1 1 0 0−2 1 0 1 01 3 0 0 1
𝑥1𝑥2𝑠1𝑠2𝑠3
=12030
𝑥1𝑥2𝑠1𝑠2𝑠3
≥0
Para tener B, eliminamos 𝑥1, 𝑥2(variables no básicas) de la forma
matricial, B y 𝑥𝐵 son:
B= 1 0 00 1 00 0 1
𝑥𝐵 =
𝑠1𝑠2𝑠3
Forma BaseEjemplo:
Sabemos que 𝑐𝐵 = 0 0 0 de la fo en la
forma matricial de las variables básicas.
Para encontrar z será:
z=𝑐𝐵𝑥𝐵
z= 0 0 012030
=0
Para encontrar 𝑥𝐵 = 𝐵−1𝑏:
En este caso 𝐵−1 es muy sencillo ya que B es la matriz identidad por tanto lainversa sigue siendo la identidad. Para otra solución será necesario encontrar lamatriz inversa para encontrar la solución.
𝐵−1= 1 0 00 1 00 0 1
𝑥𝐵 =1 0 00 1 00 0 1
12030
=12030
Solución BásicaUna solución es básica si cumple con tener al menos n-m variables igual a cero.
En este caso
todos los puntos
de intersección
ya sea entre
rectas o con los
ejes son
soluciones
básicas
gráficamente.
No es necesario
que las variables
sean mayores
iguales a cero.
Solución Básica FactibleUna solución básica factible es una solución básica con todas las variables mayores iguales a 0.
Gráficamente
se esta
hablando de
los puntos
extremos de la
región factible
Tendrá al menos n-m
variables igual a cero y
todas serán mayores
iguales a cero
Solución Básica Factible
Punto 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 z Factible No
Factible
O 0 0 12 0 30 0
A 0 12 0 -12 -6 36
B 12 0 0 12 18 24
C 4 8 0 0 10 32
D 3 9 0 -3 0 33
E 30/7 60/7 -6/7 0 0 240/7
F 0 10 2 -10 0 30
G 30 0 -18 60 0 60
Ejemplo: Todas las soluciones son básicas. Sin embargo unas son factibles y las otras no(no es factible cuando hay valores negativos):
Variable de Entrada y Salida
Variable de entrada
• Una variable no básica en una solución factible
• En la siguiente solución factible adyacente es variable básica.
Variable de salida
• Una variable básica en una solución factible.
• En la siguiente solución factible adyacente es no básica.
Variable de Entrada y Salida
Ejemplo: Si nos quedamos con las soluciones básicas factibles:
Punto 𝒙𝟏 𝒙𝟐 𝒔𝟏 𝒔𝟐 𝒔𝟑 z V. B. V. No
B.
O 0 0 12 0 30 0 s1, x2, s3 x1, s2
B 12 0 0 12 18 24 x1, s2, s3 s1,x2
C 4 8 0 0 10 32 x1, x2, s3 s1,s2
Punto V. E. V. S.
O x1 s1
B x2 s2
Referencias
Hadley, G., Linear programming, Addison Wesley, E.U.A., 1988
Hillier y Lieberman, Investigación de operaciones, McGraw Hill,
México, 2002
Moskowitz y Wright, Investigación de operaciones, Prentice Hall,
México, 1985
Prawda, W., Métodos y modelos de ínvestigación de operaciones,
Vol. 1 Modelos determinísticos, Limusa, México, 1991
Simonnard, M., Programación lineal, Paraninfo, México, 1978
Taha, H., Investigación de operaciones, una introducción, Pearson,
México, 1998
Bazaraa y Jarvis, Programación lineal y flujo en redes, Limusa,
México, 1998
Mckeown, D., Modelos cuantitativos para administración,
Iberoamérica, México, 1995
Winston, W., Investigación de Operaciones, Thomson, México, 2005
Top Related