Investigacion De Operaciones
Páginas: 4 (759 palabras)
Publicado: 14 de febrero de 2013
7.1. VARIABLES DE HOLGURA
Es el caso más sencillo y se da siempre que tengamos como primera solución
básica la proporcionada por las variables de holgura.
La formulación del problema debe incluirsolamente restricciones del tipo ≤ ,
siempre que los coeficientes de las disponibilidades sean no negativos:
max
s.a.:
Z = c1 x1 + + cn xn
a11 x1 + + a1n xn ≤ b1
am1 x1 + + amn xn ≤ bmxi ≥ 0, i = 1, , n
Introduciendo las variables de holgura para expresar la forma estándar:
max
Z = c1 x1 + + cn xn
s.a.:
H
a11 x1 + + a1n xn + xn +1 = b1
H
am1 x1 + + amn xn+ xn + m = bm
H
xi ≥ 0, i = 1, , n , xn + i ≥ 0, i = 1, , m
Podemos representar este problema en una tabla como la que sigue:
x1
x2
...
xn
H
xn + 1
H
xn + 2
...
H
xn+ m
H
xn + 1
b1
a11
a12
...
a1n
1
0
...
0
H
n+2
b2
a 21
a 22
...
a2 n
0
1
...
0
bm
am1
am 2
...
a mn
0
0
...
1
Z
c1
c2
...
cn
0
0
...
0
x
x
16
H
n+m
7.2. VARIABLES ARTIFICIALES Y COSTES MARGINALES
Consideremos el siguienteejemplo:
max
s.a.:
Z = 5 x1 + 2 x2
6 x1 + x2 ≥ 6
4 x1 + 3x2 ≥ 12
x1 + 2 x2 ≥ 4
x1 , x 2 ≥ 0
Pondremos este problema en forma estándar introduciendo dos tipos de variables
en lasrestricciones lineales de desigualdad:
H
H
H
Variables de holgura: x3 , x4 y x5
Variables artificiales: x6A , x7A y x8A .
Se obtiene el siguiente problema:
max
Z = 5 x1 + 2 x2 − Mx6A − Mx7A − Mx8As.a.:
H
6 x1 + x2 − x3 + x6A = 6
H
4 x1 + 3 x2 − x4 + x7A = 12
H
x1 + 2 x2 − x5 + x8A = 4
H
H
H
x1 , x2 , x3 , x4 , x5 , x6A , x7A , x8A ≥ 0
La tabla correspondiente a este problema esla siguiente:
x1
x6A
x2
H
x3
H
x4
H
x5
x6A
x7A
x8A
6
6
1
-1
0
0
1
0
0
A
7
12
4
3
0
-1
0
0
1
0
A
8
4
1...
Es el caso más sencillo y se da siempre que tengamos como primera solución
básica la proporcionada por las variables de holgura.
La formulación del problema debe incluirsolamente restricciones del tipo ≤ ,
siempre que los coeficientes de las disponibilidades sean no negativos:
max
s.a.:
Z = c1 x1 + + cn xn
a11 x1 + + a1n xn ≤ b1
am1 x1 + + amn xn ≤ bmxi ≥ 0, i = 1, , n
Introduciendo las variables de holgura para expresar la forma estándar:
max
Z = c1 x1 + + cn xn
s.a.:
H
a11 x1 + + a1n xn + xn +1 = b1
H
am1 x1 + + amn xn+ xn + m = bm
H
xi ≥ 0, i = 1, , n , xn + i ≥ 0, i = 1, , m
Podemos representar este problema en una tabla como la que sigue:
x1
x2
...
xn
H
xn + 1
H
xn + 2
...
H
xn+ m
H
xn + 1
b1
a11
a12
...
a1n
1
0
...
0
H
n+2
b2
a 21
a 22
...
a2 n
0
1
...
0
bm
am1
am 2
...
a mn
0
0
...
1
Z
c1
c2
...
cn
0
0
...
0
x
x
16
H
n+m
7.2. VARIABLES ARTIFICIALES Y COSTES MARGINALES
Consideremos el siguienteejemplo:
max
s.a.:
Z = 5 x1 + 2 x2
6 x1 + x2 ≥ 6
4 x1 + 3x2 ≥ 12
x1 + 2 x2 ≥ 4
x1 , x 2 ≥ 0
Pondremos este problema en forma estándar introduciendo dos tipos de variables
en lasrestricciones lineales de desigualdad:
H
H
H
Variables de holgura: x3 , x4 y x5
Variables artificiales: x6A , x7A y x8A .
Se obtiene el siguiente problema:
max
Z = 5 x1 + 2 x2 − Mx6A − Mx7A − Mx8As.a.:
H
6 x1 + x2 − x3 + x6A = 6
H
4 x1 + 3 x2 − x4 + x7A = 12
H
x1 + 2 x2 − x5 + x8A = 4
H
H
H
x1 , x2 , x3 , x4 , x5 , x6A , x7A , x8A ≥ 0
La tabla correspondiente a este problema esla siguiente:
x1
x6A
x2
H
x3
H
x4
H
x5
x6A
x7A
x8A
6
6
1
-1
0
0
1
0
0
A
7
12
4
3
0
-1
0
0
1
0
A
8
4
1...
Leer documento completo
Regístrate para leer el documento completo.