Soluciones Gráficas en Programación Lineal
Soluciones Gráficas en Programación Lineal
UNIDAD TEMÁTICA 5
PROGRAMACION LINEAL
a) En : 2 x 3 7 x 2
b) En : 5 2 x 3 x 4
c) En 2: y 6 2 x
Representamos la recta y 2 x 6 y la expresión segmentaria de la recta es :
x y
1
3 6
Debemos elegir el conjunto de puntos que cumplen con la desigualdad
Para ello tomamos como punto testigo al (0;0)
¿(0;0) cumple con y 2 x 6?
Reemplazamos el punto (0;0) en la desigualdad y obtenemos : 0 6 Falso
Entonces pintamos el semiplano que no contiene al (0;0)
PRÁCTICA V 154
ÁLGEBRA (71)
x y 4
d) En 2:
x 2y 6
x y4
x y
Representamos la recta : x y 4 1
4 4
Tomamos como punto testigo al (0;0)
¿(0;0) cumple con x y 4?
Reemplazamos el punto (0;0) en la desigualdad y
nos queda : 0 4 Expresión Verdadera
Se pinta entonces el semiplano que contiene al (0;0)
x 2y 6
x y
Representamos la recta : x 2 y 6 1
6 3
Tomamos como punto testigo al (0;0)
¿(0;0) cumple con x 2 y 6?
Reemplazamos el punto (0;0) en la desigualdad y nos queda : 0 6 Expresión Verdadera
Se pinta entonces el semiplano que contiene al ( 0;0)
PRÁCTICA V 155
ÁLGEBRA (71)
1 x 5 1 x 5
2 y 5
En este caso representamos las rectas : x 1 x 5
e) En :
2
2x y 5
x y
Representamos el borde : 2 x y 5 1
52 5
Tomamos como punto testigo al (0;0) ¿(0;0) cumple con 2 x y 5?
Reemplazamos el punto (0;0) en la desigualdad y nos queda : 0 5 Expresión Falsa
Se pinta entonces el semiplano que no contiene al (0;0)
3 x 2 y 20
x y
Representamos el borde : 3 x 2 y 20 1
20 3 10
Tomamos como punto testigo al (0;0) ¿(0;0) cumple con 3 x 2 y 20?
Reemplazamos el punto (0;0) en la desigualdad y nos queda : 0 20 Expresión Verdadera
Se pinta entonces el semiplano que contiene al (0;0)
Marcamos con negro los vértices de la zona de factibilidad, el polígono ABCDEF, o sea
donde se cumplen simultáneamente todas las inecuaciones
PRÁCTICA V 156
ÁLGEBRA (71)
3x y 6
f) En : 2 x 3 y 12
2
y x
x y
3 x y 6 entonces el borde es 3 x y 6 , la expresión segmentaria es 1
2 6
x y
2 x 3 y 12 entonces el borde es 2 x 3 y 12 , la expresión segmentaria es 1
6 4
y x entonces el borde es y = x
PRÁCTICA V 157
ÁLGEBRA (71)
3 x y 6
x y 5
g) En 2:
x 0
y 0
x y
3 x y 6 entonces el borde es 3 x y 6 , la expresión segmentaria 1
2 6
x y
x y 5 entonces el borde es x y 5 , la expresión segmentaria 1
5 5
x0
La zona queda reducida al primer cuadrante cuando aplicamos:
y0
PRÁCTICA V 158
ÁLGEBRA (71)
ii. Identificar cada uno de los vértices del conjunto de soluciones factibles con letras mayúsculas e indicar sus coordenadas.
iii. Calcular el valor de la función objetivo (Z) en cada vértice del CSF.
iv. En base a los resultados anteriores indicar la solución óptima del modelo (valor de las variables x , y y de la función objetivo (Z)
v. Trazar en el gráfico construido en i) la línea que une todos los puntos de coordenadas ( x; y ) para los cuales la función objetivo toma un
valor constante z k , siendo k el valor óptimo de z hallado en iv).
vi. Darle a k otros valores distintos del óptimo y repetir el procedimiento seguido en v). Sacar conclusiones.
A continuación…
PRÁCTICA V 159
ÁLGEBRA (71)
a) Minimizar: Z x 2 y
x y 3
Sujeta a:
y1
Con x 0; y 0
PRÁCTICA V 160
ÁLGEBRA (71)
PRÁCTICA V 161
ÁLGEBRA (71)
b) Maximizar: Z 2 x 3 y
2 x y 10
Sujeta a:
x 2y 8
Con x 0 ; y 0
PRÁCTICA V 162
ÁLGEBRA (71)
PRÁCTICA V 163
ÁLGEBRA (71)
c) Minimizar: Z 7 x 3 y
3 x y 2
Sujeta a: x y 9
x y 1
Con x 0 ; y 0
k=0 k=3
PRÁCTICA V 164
ÁLGEBRA (71)
k=0 k = 22.00
PRÁCTICA V 165
ÁLGEBRA (71)
e) Maximizar: Z 3 x 6 y
x y 3
Sujeta a: 2 x y 4
x 2 y 12
Con x 0 ; y 0
PRÁCTICA V 166
ÁLGEBRA (71)
f) Maximizar: Z 2 x 4 y
x y 10
Sujeta a: 3 x y 2 Con x 0 ; y 0
x 4y 0
x y 10
( 2; 8 ) es solución del sistema
3 x y 2
k = 0k = 8
Evaluamos la función objetivo en los vértices
Z( 0;0 ) 2.0 4.0 0 Z( 0;0 ) 0 k = 16
k=8
Z( 0; 2 ) 2.0 4.2 8 Z( 0; 2 ) 8
Z( 8; 2 ) 2.8 4.2 8 Z( 8; 2 ) 8
Z( 2;8 ) 2.2 4.8 28 Z( 4; 2 ) 28
PRÁCTICA V 167
ÁLGEBRA (71)
a) La solución óptima que maximice la función objetivo propuesta se encuentre en alguno de los vértices del polígono.
a) Si las condiciones a las cuales está sujeta la función objetivo está dada
por:
4 x y 16
Con x 0 ; y 0
x 2 y 12
PRÁCTICA V 168
ÁLGEBRA (71)
PRÁCTICA V 169
ÁLGEBRA (71)
4) y 5) Construir los sistemas de ecuaciones y la tabla simplex iniciales asociados a los siguientes programas lineales.
Indicar en cada caso cuales son las variables básicas y no básicas y la primera solución factible
a) Maximizar: Z x 2 y
2 x y 8
Sujeta a: Con x 0 ; y 0
2 x 3 y 12
2x y 8
es solución del sistema
2 x 3 y 12
PRÁCTICA V 170
ÁLGEBRA (71)
2x y 8 2. x 1.y 1. S1 0. S 2 8
2 x 3 y 12 2. x 3. y 0. S1 1. S 2 12
Las variables de holgura no aportan nada al valor de la función objetivo, por eso tienen en la expresión de la funcional coeficiente cero
Z x 2.y Z 1.x 2.y 0.S1 0.S2
En la solución óptima estas variables indican la cantidad de recursos disponibles no utilizados. Si valen cero significa que se han utilizado todos los
recursos y se dice que el recurso está saturado.
El método distingue dos tipos de variables: básicas y no básicas
PRÁCTICA V 171
ÁLGEBRA (71)
Ahora se debe elegir una variable de entrada entre las no básicas y una variable de salida entre las básicas
Entre las no básicas x e y elegimos aquella que corresponde a la columna de coeficiente positivo de mayor valor en la fila cj zj
En nuestro caso es “y” luego la variable de entrada es
cj 1 2 0 0 “y”. Pintamos la columna
Entre las básicas S1 o S2 elijo la variable de salida, para eso
ck xk x1(x) x2(y) S1 S2 b calculo los cocientes entre los elementos de la columna b
0 S1 2 1 1 0 8 8/1 = 8 con los respectivos coeficientes de la columna de entrada o
sea “y”
0 S2 2 3 0 1 12 12/3 = 4
Elegimos la fila cuyo cociente positivo es menor o sea en
zj 0 0 0 0 0 nuestro caso la variable de salida es “S2”. Pintamos le fila
correspondiente
cj zj 1 2 0 0
Para transformar la tabla debemos utilizar el método del pivote, el número que resulta de la intersección de la columna y fila elegida es 3
Como el pivote debe ser 1, divido la fila por 3
PRÁCTICA V 172
ÁLGEBRA (71)
Escribimos la fila del pivote y completamos la columna con tantos ceros como sean necesarios.
cj 1 2 0 0 Los restantes números en este caso de la primera fila los calculamos por la
regla del rectángulo
ck xk x1(x) x2(y) S1 S2 b
0 S1 0 Luego calculamos zj y cj zj.
2 y 2/3 1 0 1/3 4
zj
cj zj
PRÁCTICA V 173
ÁLGEBRA (71)
ck xk x1(x) x2(y) S1 S2 b Observando la última fila nos encontramos frente a la solución óptima ya que
0 S1 4/3 0 1 1/3 4 ninguno de los cj zj es positivo, o sea en este punto no es posible
incrementar la utilidad neta. Luego:
2 y 2/3 1 0 1/3 4
zj 4/3 2 0 2/3 Z=8
cj zj 1/3 0 0 2/3 Además de la solución se concluye que del recurso 1: sobran 4 unidades y
( ) ( )
del recurso 2: no sobran unidades o sea el recurso 2 se dice está saturado.
Solución óptima x; y; S1 ; S2 0; 4; 4; 0 Z 8
PRÁCTICA V 174
ÁLGEBRA (71)
b) Maximizar: Z x 1, 5 y
2 x 2 y 160
Sujeta a: x 2 y 120 Con x 0 ; y 0
4 x 2 y 280
Las variables de holgura no aportan nada al valor de la función objetivo, por eso tienen en la expresión de la funcional coeficiente cero
Z x 1,5y Z 1.x 1,5.y 0.S1 0.S2 0.S3
En la solución óptima estas variables indican la cantidad de recursos disponibles no utilizados. Si valen cero significa que se han utilizado todos los
recursos y se dice que el recurso está saturado.
El método distingue dos tipos de variables: básicas y no básicas
PRÁCTICA V 175
ÁLGEBRA (71)
cj 1 1,5 0 0 0
ck xk x1(x) x2(y) S1 S2 S3 b
0 S1 2 2 1 0 0 160 Primera restricción
Segunda
0 S2 1 2 0 1 0 120 restricción
0 S3 4 2 0 0 1 280 Tercera restricción
Valor inicial de la
Zj 2.0 +1.0+4.0 = 0 2.0 + 2.0 +2.0 = 0 1.0 + 0.0 +0.0 = 0 0.0 + 1.0+0.0 = 0 0.0 + 0.0+1.0 = 0 160.0 + 120.0 +280.0 = 0
función objetivo
cj zj 1–0=1 1,5 – 0 = 1,5 0–0=0 0–0=0 0–0=0
En cada paso se trata de transformar una variable no básica en básica tratando de maximizar la función.
Completamos la tabla cj son los coeficientes de la funcional: Z x 1,5y Z 1.x 1,5.y 0.S1 0.S2 0.S3
S1, S2 y S3 son las variables básicas (encabezan columnas de vectores canónicos), x e y son las variables no básicas
Solución básica inicial (x; y; S1; S2; S3)= (0; 0; 160; 120; 280) z = 0
La tabla inicial representa el vértice que se encuentra en el origen. Hemos obtenido el primer vértice de la región de factibilidad V1 = (0; 0)
Ahora se debe elegir una variable de entrada entre las no básicas y una variable de salida entre las básicas
Entre las no básicas x e y elegimos aquella que corresponde a la columna de coeficiente positivo de mayor valor en la fila cj zj
En nuestro caso es “y” luego la variable de entrada es “y”. Pintamos la columna
Entre las básicas S1 o S2 o S3 elijo la variable de salida, para eso calculo los cocientes entre los elementos de la columna b con los respectivos
coeficientes de la columna de entrada o sea “y”
Elegimos la fila cuyo cociente positivo es menor o sea en nuestro caso la variable de salida es “S2”. Pintamos le fila correspondiente.
PRÁCTICA V 176
ÁLGEBRA (71)
Para transformar la tabla debemos utilizar el método del pivote, el número que resulta de la intersección de la columna y fila elegida es 2
Como el pivote debe ser 1, divido la fila por 2
cj 1 1,5 0 0 0
ck xk x1(x) x2(y) S1 S2 S3 b
0 S1 2 2 1 0 0 160 160/2=80
0 S2 1 2 0 1 0 120 120/2=60 VS
0 S3 4 2 0 0 1 280 280/2=140
Zj 0 0 0 0 0 0
cj zj 1 1,5 VE 0 0 0
Se obtiene el pivote y se debe sustituir S2 y en su lugar poner “y” y donde está el coeficiente 0 de S2 poner el 1,5 de la y
Escribimos la fila del pivote y completamos la columna con tantos ceros como sean necesarios.
Los restantes números en este caso de la primera fila los calculamos por la regla del rectángulo
Luego calculamos zj y cj zj.
cj 1 1,5 0 0 0
ck xk x1(x) x2(y) S1 S2 S3 b
0 S1 2 2 1 0 0 160
0 S2 1/2 0 1/2 0 60
0 S3 4 2 0 0 1 280
Zj 0 0 0 0 0 0
cj zj 1 1,5 0 0 0
PRÁCTICA V 177
ÁLGEBRA (71)
Observando la última fila nos encontramos que todavía hay cj zj positivo, o sea no hemos encontrado la solución óptima
Reiniciamos el proceso…
cj 1 1,5 0 0 0
ck xk x1(x) x2(y) S1 S2 S3 b
0 S1 (1) 0 1 1 0 40 40/1=40 VS Variable de entrada: x1(x)
1,5 y 1/2 1 0 1/2 0 60 60/1/2=120 Variable de Salida: S1
0 S3 3 0 0 1 1 160 160/3=53,..
Zj 0,75 1,5 0 0,75 0 90
cj zj 0,25VE 0 0 0,75 0
PRÁCTICA V 179
ÁLGEBRA (71)
c) Maximizar: Z 3 x 3 y
x y4
Sujeta a: x y 4 Con x 0 ; y 0
x y6
Respuesta c): x = 4; S2 = 8; S3 = 2; Z = 12
PRÁCTICA V 180
ÁLGEBRA (71)
x y4 1 . x 1 . y 1 . S1 0 . S 2 0 . S 3 4
Sujeta a: x y 4 1 . x 1 . y 0 . S1 1 . S 2 0 . S 3 4
x y6 1. x 1. y 0. S 0. S 1. S 6
1 2 3
Las variables de holgura no aportan nada al valor de la función objetivo, por eso tienen en la expresión de la funcional coeficiente cero
Z 3x 3.y Z 3.x 3.y 0.S1 0.S2 0.S3
En la solución óptima estas variables indican la cantidad de recursos disponibles no utilizados. Si valen cero significa que se han utilizado todos los
recursos y se dice que el recurso está saturado.
El método distingue dos tipos de variables: básicas y no básicas
PRÁCTICA V 181
ÁLGEBRA (71)
cj 3 3 0 0 0
ck xk x1(x) x2(y) S1 S2 S3 b
0 S1 1 1 1 0 0 4 Primera restricción
0 S2 1 1 0 1 0 4 Segunda restricción
0 S3 1 1 0 0 1 6 Tercera restricción
Valor inicial de la función
Zj 1.0 + (1).0 +1.0 = 0 1.0 + 1.0+1.0 = 0 1.0 + 0.0 + 0.0= 0 0.0 + 1.0 + 0.0= 0 0.0 + 0.0+ 1.0 = 0 4.0 + 4.0 + 6.0 = 0
objetivo
S1, S2 y S3 son las variables básicas (encabezan columnas de vectores canónicos), x e y son las variables no básicas
Solución básica inicial
(x; y; S1; S2)= (0; 0; 4; 4;6) z = 0
La tabla inicial representa el vértice que se encuentra en el origen. Hemos obtenido el primer vértice de la región de factibilidad V1 = (0; 0)
Ahora se debe elegir una variable de entrada entre las no básicas y una variable de salida entre las básicas
Entre las no básicas x e y elegimos aquella que corresponde a la columna de coeficiente positivo de mayor valor en la fila cj zj
Entre las básicas S1, S2 y S3 elijo la variable de salida, para eso calculamos los cocientes entre los elementos de la columna b con los respectivos
coeficientes de la columna de entrada o sea “x”
Elegimos la fila cuyo cociente positivo es menor o sea en nuestro caso la variable de salida es “S1”. Pintamos le fila correspondiente
PRÁCTICA V 182
ÁLGEBRA (71)
Como se puede ver en la tabla no se puede realizar el cociente en la segunda fila; dado que el divisor es negativo o nulo, Si recordamos que el
cociente representa el valor con el que entra en la próxima solución la variable entrante, se advierte claramente que este valor no puede ser negativo.
cj 3 3 0 0 0
ck xk x1(x) x2(y) S1 S2 S3 b
3 x 1 1 1 0 0 4
0 S2 0 0 1 1 0 8
0 S3 0 2 1 0 1 2
zj 3 3 3 0 0 12
cj zj 0 0 3 0 0
PRÁCTICA V 183
ÁLGEBRA (71)
Además de la solución se concluye que del recurso 2: sobran 8 unidades y del recurso 3: sobran 4 unidades y del recurso 1 no sobran unidades o
sea el recurso 1 se dice está saturado.
Hemos encontrado una solución óptima pero para hallar una nueva, dado que por lo anterior sabemos que el problema admite múltiples
soluciones,
Consideramos entonces a x2 “y” como variable entrante, queda después de efectuar los cocientes que S3 es la variable saliente. Ya que los otros
dos cocientes no se pueden realizar por tener divisor negativo
PRÁCTICA V 184
ÁLGEBRA (71)
Multiplicamos la tercera fila por 1/2 para obtener como pivote a 1, luego aplicamos Gauss-Jordan y calculamos posteriormente los Z j y los
C j Z j . La tabla que obtenemos es:
cj 3 3 0 0 0
ck xk x1(x) x2(y) S1 S2 S3 b
3 x 1 1 1 0 0 4
0 S2 0 1 1 1 0 8
-3 S3 0 1/2 0 1/2 1
zj 3 3 3 0 0 12
cj zj 0 0 3 0 0
cj 3 3 0 0 0
ck xk x1(x) x2(y) S1 S2 S3 b
3 x 1 0 3/2 0 1/2 5
0 S2 0 0 3/2 1 1/2 9
3 y 0 1 1/2 0 1/2 1
zj 3 3 3 0 0 12
cj z j 0 0 3 0 0
PRÁCTICA V 185
ÁLGEBRA (71)
En la última solución x es no básica y su indicador es nulo. Sin embargo, si se repitiera el proceso para determinar otras soluciones óptimas, se
volvería a la segunda tabla. Por ello, el procedimiento no ofrece otras soluciones óptimas.
Por lo tanto: las soluciones óptimas múltiples del problema planteado se expresan de la siguiente forma:
PRÁCTICA V 186
ÁLGEBRA (71)
La tabla inicial representa el vértice que se encuentra en el origen. Hemos obtenido el primer vértice de la región de factibilidad V1 = (0; 0)
cj 3 3 0 0 0
ck xk x1(x) x2(y) S1 S2 S3 b
0 S1 1/2 1 0 0 10 10/1=10 VS
0 S2 1 1 0 1 0 15 15/1=15
Se obtiene el pivote y se debe sustituir en
la próxima tabla S1 y en su lugar poner “y” y
0 S3 3/2 1 0 0 1 15 15/1=15
donde está el coeficiente 0 de S2 poner el 3
Zj 0 0 0 0 0 0 de la y
cj zj 3 3 VE 0 0 0
PRÁCTICA V 187
ÁLGEBRA (71)
Como la solución no es óptima dado que hay un indicador positivo debemos continuar con el proceso
cj 3 3 0 0 0
En esta nueva tabla las variables básicas son:
ck xk x1(x) x2(y) S1 S2 S3 b S2 = 7,5, x = 5, y= 7,5 la función Z = 37,5, las variables no
3 y 0 1 3/2 0 1/2 7,5 básicas son: S1 = 0, S3 = 0 y la solución es óptima por tener
0 S2 0 0 3/2 1 1/2 7,5 los indicadores no positivos
3 x 1 0 1 0 1 5
Zj 3 3 3/2 0 3/2 37,5
cj zj 0 0 3/2 0 3/2
PRÁCTICA V 188
ÁLGEBRA (71)
c) ¿Cuánto podría aumentar como máximo c1 manteniendo constante c2 3 sin que sea necesario modificar la solución óptima?
cj c1 3 0 0 0
9 9
ck xk x1(x) x2(y) S1 S2 S3 b c1 0 c1
2 2
3 y 0 1 3/2 0 1/2 7,5
3 3
0 S2 0 0 3/2 1 1/2 7,5 c1 0 c1 a partir de c1 3 c1 1, 5
2 2
c1 x 1 0 1 0 1 5
Zj c1 3 9/2 c1 0 3/2+ c1 37,5
cj zj 0 0 0
d) ¿Cuánto podría aumentar como máximo c 2 manteniendo constante c1 3 sin que sea necesario modificar la solución óptima?
3 3
cj 3 3 0 0 0 c2 3 0 c2 3 c2 2
ck xk x1(x) x2(y) S1 S2 S3 b 2 2
c2 y 0 1 3/2 0 1/2 7,5
3/2 1 1
0 S2 0 0 1 1/2 7,5 c 2 3 0 3 c 2 c2 6
3 x 1 0 1 0 1 5 2 2
Zj 3 c2 3/2c2 3 0 1/2c2 + 3 37,5
cj zj 0 0 3/2 0 3/2
PRÁCTICA V 189
ÁLGEBRA (71)
2 x1 x2 40 2 y1 y2 9
a) Maximizar Z 9 x1 7 x2 sujeta a x1 3 x2 30 Minimizar W 40 y1 30 y2 sujeta a y1 3 y2 7
x 0, x 0 y 0, y 0
1 2 1 2
4 x1 3 x2 36
4 y1 2 y2 1
2 x1 4 x2 40
b) Maximizar Z x1 10 x2 sujeta a Minimizar W 36 y1 40 y2 3 y3 sujeta a 3 y1 4 y2 y3 10
x2 3 y 0, y 0, y 0
x 0, x 0 1 2 3
1 2
x1 2 x2 18
4 x1 3 x2 48
c) Minimizar Z 2 x1 3 x2 sujeta a Maximizar W 18 y1 48 y2 3 y3 sujeta a
x1 3
x 0, x 0
1 2
PRÁCTICA V 190
ÁLGEBRA (71)
2 x1 x2 12
2 y1 y2 y3 30
x1 x2 9
d) Minimizar Z 30 x1 40 x2 sujeta a Maximizar W 12 y1 9 y2 15 y3 sujeta a y1 y2 3 y3 40
x1 3 x2 15 y 0, y 0, y 0
x 0 , x 0 1 2 3
1 2
y1 2 y2 10
x1 3 x 2 4 x 3 5
3 y1 4 y2 12
e) Maximizar Z 10 x1 12 x2 15 x3 sujeta a 2 x1 4 x2 5 x3 6 Minimizar W 5 y1 6 y2 sujeta a
x 0 , x 0 , x 0 4 y1 5 y2 15
1 2 3 y 0, y 0
1 2
PRÁCTICA V 191
ÁLGEBRA (71)
x 3y 3
a) Minimizar: Z 4 x 5 y Sujeta a: 3 x y 3 Con x 0 ; y 0
x y7
Planteamos en primer lugar el problema Dual
Sujeta a: 1 y1 3 y2 1 y3 4 1 y1 3 y2 1 y3 1s1 0 s2 4
3 y1 1 y2 1 y3 5 3 y1 1 y2 1 y3 0 s1 1s2 5
Las variables de holgura no aportan nada al valor de la función objetivo, por eso tienen en la expresión de la funcional coeficiente cero
W 3 y1 + 3 y2 7 y3 W 3 y1 3 y2 7 y3 0 S1 0 S2
PRÁCTICA V 192
ÁLGEBRA (71)
cj 3 3 7 0 0
ck xk y1 y2 y3 S1 S2 b
0 S1 1 3 1 0 4 4/1 = 4 VS
0 S2 3 1 1 0 1 5 5/1 = 5
zj 0 0 0 0 0 0
cj zj 3 3 7VE 0 0
PRÁCTICA V 193
ÁLGEBRA (71)
x 3 y 2 z 10
b) Minimizar: Z 4 x 3 y 2 z Sujeta a: Con x 0 ; y 0 ; z 0
2 x y 2z 8
1 y1 2 y2 4
Maximizar W 10 y1 8 y2 Sujeta a: 3 y1 1 y2 3 Con y1 0 ; y2 0
2 y 2 y 2
1 2
W 10 y1 + 8 y2 W 10 y1 8 y2 0 S1 0 S2 0 S3
1 y1 2 y2 4 1 y1 2 y2 1 S1 0 S 2 0 S 3 4
Sujeta a: 3 y1 1 y2 3 3 y1 1 y2 0 S1 1 S 2 0 S 3 3
2 y 2 y 2 2 y 2 y 0 S 0 S 1S 2
1 2 1 2 1 2 3
cj 10 8 0 0 0
ck xk y1 y2 S1 S2 S3 b
0 S1 1 2 1 0 0 4 4/1 = 4
0 S2 3 1 0 1 0 3 3/3 = 1
0 S3 2 2 0 0 1 2 Dividimos la fila por 2 para obtener pivote 1
2/2 = 1 VS
zj 0 0 0 0 0 0
cj zj 10VE 8 0 0 0
PRÁCTICA V 194
ÁLGEBRA (71)
cj 10 8 0 0 0
ck xk y1 y2 S1 S2 S3 b
0 S1 1 2 1 0 0 4
0 S2 3 1 0 1 0 3
0 S3 1 0 0 1/2 1
zj 0 0 0 0 0 0
cj zj 10VE 8 7 0 0
cj 10 8 0 0 0
Como hemos obtenido una solución óptima dado que los indicadores
ck xk y1 y2 S1 S2 S3 b
son todos no positivos, leemos la solución en está tabla del problema
0 S1 0 1 1 0 1/2 3 primal.
Considerando las respuestas del primal en valor absoluto de los
0 S2 0 2 0 1 3/2 0
indicadores del dual.
10 y1 1 0 0 1/2 1
zj 10 10 0 0 5 10
Solución
cj zj 0 2 0 0 5 correspondiente a la
variable z del
problema original
Solución Solución Solución Solución
correspondiente a la correspondiente a correspondiente a la correspondiente a
variable de holgura S1 la variable de variable x del la variable y del
del problema original holgura S2 del problema original problema original
problema original
PRÁCTICA V 195
ÁLGEBRA (71)
x 2y 5
c) Minimizar: Z 15 x 20 y Sujeta a: 3 x y 6 Con x 0 ; y 0
x 4y 8
Planteamos en primer lugar el problema Dual
Aclaración: llamaremos a la
variable x, x1 y a la variable y, x2
Las variables de holgura no aportan nada al valor de la función objetivo, por eso tienen en la expresión de la funcional coeficiente cero
W 3 y1 + 3 y2 7 y3 W 3 y1 3 y2 7 y3 0 S1 0 S2
Tabla Inicial
cj 5 6 8 0 0
ck xk y1 y2 y3 S1 S2 b
0 S1 1 3 1 1 0 15 15/1 = 15 Convertimos el pivote 4 en 1 dividiendo la fila
por 4
0 S2 2 1 4 0 1 20 20/4 = 5 VS
zj 0 0 0 0 0 0
cj zj 5 6 8VE 0 0
PRÁCTICA V 196
ÁLGEBRA (71)
cj 5 6 8 0 0
ck xk y1 y2 y3 S1 S2 b
0 S1 1 3 1 1 0 15
0 S2 1/2 1/4 0 1/4 5
zj 0 0 0 0 0 0
cj zj 5 6 8 0 0
Segunda Tabla
cj 5 6 8 0 0
ck xk y1 y2 y3 S1 S2 b
0 S1 1/2 11/4 0 1 1/4 10 10/11/4= 40/11 VS
8 y3 1/2 1/4 1 0 1/4 5 5/1/4=20
zj 4 2 8 0 2 40
cj zj 1 4VE 0 0 2
PRÁCTICA V 197
ÁLGEBRA (71)
cj 5 6 8 0 0
ck xk y1 y2 y3 S1 S2 b
0 S1 2/11 0 4/11 1/11 40/11
8 y3 1/2 1/4 1 0 1/4 5
zj 4 2 8 0 2 40
cj zj 1 4 0 0 -2
Tercera Tabla
cj 5 6 8 0 0
ck xk y1 y2 y3 S1 S2 b
6 y2 2/11 0 4/11 1/11 40/11 40/11/5/11=20
8 y3 5/11 0 1 1/11 3/11 45/11 45/11/5/11=9 VS
zj 52/11 6 8 16/11 18/11 600/11
cj zj 3/11VE 0 0 16/10 18/11
cj 5 6 8 0 0
ck xk y1 y2 y3 S1 S2 b
6 y2 2/11 1 0 4/11 1/11 40/11
8 y3 0 11/5 1/5 3/5 9
zj 52/11 6 8 16/11 18/11 600/11
cj zj 3/11VE 0 0 16/10 18/11
PRÁCTICA V 198
ÁLGEBRA (71)
Cuarta tabla
cj 5 6 8 0 0
ck xk y1 y2 y3 S1 S2 b
6 y2 0 1 2/5 2/5 1/5 2
5 y1 0 11/5 1/5 3/5 9
zj 5 6 43/5 7/5 9/5 57 Solución
correspondiente a la
cj zj 0 0 3/5 7/5 9/5 variable y del
problema original
Solución Solución
Solución correspondiente a
correspondiente a la correspondiente a Solución
la variable de correspondiente a la la variable x del
variable de holgura S1 problema original
holgura S2 del variable de holgura S3
del problema original
problema original del problema original
Como hemos obtenido una solución óptima dado que los indicadores son todos no positivos, leemos la solución en está tabla del problema
primal.
Considerando las respuestas del primal en valor absoluto los indicadores del dual.
7 9 3
Solución Optima del primal x1 ; x2 ; S1 ; S 2 ;S 3 ; ;0;0; Z 57
5 5 5
PRÁCTICA V 199
ÁLGEBRA (71)
9) Para preparar una dieta óptima se dispone de dos ingredientes (I1, I2). El análisis químico determinó que contiene tres tipos distintos de
nutrientes por cada kilo, a saber: 4, 7 y 1,5 gramos para I1; 8, 2 y 5 gramos para I2. La empresa consigue en el mercado I1 a $30 el kg y el
I2 a $40 el kg. .Asimismo se determinó el contenido mínimo de nutrientes para que la dieta sea eficaz: 32, 14 y 15 gramos, respectivamente.
I1 I2 Requerimiento Mínimo
Nutriente 1 4 8 32
Nutriente 2 7 2 14
Nutriente 3 15 5 15
Costo $30 $40
4 x 8 y 32
x 0
El planteo es: Minimizar C 30 x 40 y Sujeto a 7 x 2 y 14 con
1,5 x 5 y 15 y 0
PRÁCTICA V 200
ÁLGEBRA (71)
El programa Óptimo corresponde a I1 = 1; I2 = 3,5; el requerimiento mínimo (15 g) del nutriente 3 se cumple con 4g de exceso, dado que:
4.1 8.3, 5 32 32
7.1 2.3, 5 14 14
1, 5.1 5.3, 5 19 15
PRÁCTICA V 201
ÁLGEBRA (71)
b) Si la empresa se ve obligada a incorporar un nuevo nutriente con coeficientes 1,5 y 5 gramos y un requerimiento mínimo de 18 gramos,
determine qué efecto produce en términos de solución óptima
PRÁCTICA V 202
ÁLGEBRA (71)
10) Para la fabricación de dos productos se utilizan tres insumos según los valores consignados en la siguiente matriz:
Producto P1 P2 Disponibilidad
Insumo
I1 5 10 80
I2 40 20 360
I3 10 10 100
Beneficio 2 3
PRÁCTICA V 203
ÁLGEBRA (71)
PRÁCTICA V 204
ÁLGEBRA (71)
c) ¿Las disponibilidades de qué recursos podrían disminuirse sin modificar el beneficio máximo? ¿En cuánto y por qué?
Los recursos 1 y 3 están saturados, porque sus variables de holgura en el óptimo son no básicas y valen cero.
En cambio del segundo recurso hay un exceso de S2 80 , esta es la cantidad del recurso 2 que se puede sacar sin que cambie la
producción, ni el beneficio.
O sea se podría disminuir 80 unidades la disponibilidad del insumo 2 pues no se utilizan en la fabricación (son excedentes).
d) ¿Cuáles son los recursos saturados? ¿Cuánto estaría dispuesto a pagar por una unidad más de ellos? ¿Por qué?
Los recursos saturados hemos dicho son el primero y el tercero, porque S1 S3 0
Observando la última fila de la tabla para el primer insumo es 1/5 y en el tercero es 1/10
e) ¿Podría utilizarse el total de las disponibilidades de los tres insumos? ¿Por qué?
Sabemos que x 8 , y 2 se agotan dos de los tres insumos pero del primero sobran 20 si reemplazamos estos valores en la ecuación del
primer insumo. No existe intersección de las tres rectas.
f) Si el precio de ambos productos varía en igual proporción, ¿se modifica la solución óptima? ¿Cómo y por qué?
La región factible no cambia y si los precios cambian es un factor k el beneficio cambia en ese factor.
No varía la estructura de la solución, sólo el beneficio total. No cambia el polígono de soluciones factibles ni la pendiente de las rectas de
isobeneficio.
PRÁCTICA V 205
ÁLGEBRA (71)
11) Una refinería de petróleo procesa dos tipos de crudo: A y B con la finalidad de producir gas oíl, lubricantes y kerosene. Las demandas de estos
productos son al menos respectivamente 14, 10 y 8 toneladas por día.
El crudo A tiene un rendimiento de 0,2 toneladas de gas oíl, 0,10 toneladas de lubricante y 0,16 toneladas de kerosene por cada tonelada de
petróleo.
Los rendimientos del crudo B son: 0,10 toneladas de gas
oíl, 0,20 toneladas de lubricante y 0,10 toneladas de
kerosene.
Minimizar Z x A xB
0, 2 x A 0,10 x B 14
0,10 x A 0, 20 x B 10
Sujeta a
0,16 x A 0,10 x B 8
x 0, x 0
A B
PRÁCTICA V 206
ÁLGEBRA (71)
c) Asignar dos valores arbitrarios a la capacidad de la refinería y trazar las líneas que muestren todas las mezclas de crudos A y B que se
pueden procesar con la misma capacidad de la planta.
d) Determinar la cantidad de cada crudo a procesar y la capacidad mínima de la planta utilizando el método gráfico.
Las cantidades óptimas a procesar son 60 tn por día de crudo A y 20 tn por día de crudo B, dado que en ese vértice la recta deja al CSF
totalmente por encima de ella. La capacidad mínima de la planta es de 80 tn por día.
e) Trazar en el gráfico del modelo la isolínea que corresponde a la capacidad óptima de la planta. Comparar con las líneas trazadas en c).
Visible en el Gráfico de b)
f) De acuerdo al programa óptimo, ¿habrá excedente de alguno de los tres productos sobre el valor de la demanda? En caso afirmativo
identificar de cuál o cuáles de ellos.
PRÁCTICA V 207
ÁLGEBRA (71)
12) Una empresa que elabora alimento para animales desea introducir en el mercado una mezcla alimenticia para caninos que consiste en paquetes
de galletitas con sabor a hígado y pollo. La composición de las galletitas es tal que cada una con sabor a pollo contienen una unidad de
nutriente A y 4 de nutriente B; las de hígado están compuestas por una unidad de nutriente A y 2 de nutriente B. La empresa ha decidido
envasar por lo menos 15 galletitas con sabor a hígado por paquete y además existen reglamentaciones externas que exigen que cada paquete
de alimento contenga por lo menos 40 unidades de nutriente A y 60 unidades de nutriente B. El costo de cada galletita con sabor a hígado
es 10 centavos y cada una de gusto a pollo cuesta 20 centavos.
a) Formular el modelo que permita optimizar la mezcla de galletitas con ambos gustos en cada paquete. ¿Es un problema de maximización o de
minimización?
Minimizar Z 0, 20. x p 0,10. xh sujeta a
x p xh 40
4 x p 2 xh 60
xh 15
x 0, x 0
p h
PRÁCTICA V 208
ÁLGEBRA (71)
c) Hallar las cantidades óptimas a mezclar de cada tipo de galletitas por el método gráfico.
La mezcla óptima es 0 galletitas con sabor a pollo y 40 con sabor a hígado por paquete. El costo mínimo es $4 por paquete.
PRÁCTICA V 209
ÁLGEBRA (71)
13) Para el estudio del plan de producción a seguir durante el próximo período se dispone de los siguientes datos:
a) Defina el significado concreto de todos los elementos del vector “Producto A”.
Para fabricar una unidad del producto A, se necesita 1 unidad de materia prima, 2 horas hombre y U$S 1000.
b) Demuestre que no existe nivel de producción para el cual se utilicen todas las disponibilidades.
No se intersectan en un punto las tres restricciones. El sistema de ecuaciones resulta incompatible
c) Considere la disponibilidad del recurso 2 como " k " y averigüe (aplicando procedimiento) para qué valores de k el sistema planteado
tendría solución.
x y 200
1 1 200 1 1 200 1 1 200 1 0 50
2x y k
2 1 k 0 1 k 400 0 1 k 400 0 0 k 250
1000 x 2000 y 350.000 1000 2000 350.000 0 1000 150.000 1 0 1 150 0 1 150
F3
1000
PRÁCTICA V 210
ÁLGEBRA (71)
d) Plantee el modelo matemático que describa todas las alternativas posibles de producción y permita detectar la óptima.
Max. Z = 100x + 400y
x y 200
2 x y 260
sujeto a
1000 x 2000 y 350.000
x 0, y 0
e) Resuelva gráficamente.
PRÁCTICA V 211
ÁLGEBRA (71)
cj 100 400 0 0 0
ck xk x1 x2 S1 S2 S3 b
0 S1 1/2 0 1 0 1/2000 25
0 S2 3/2 0 0 1 1/2000 85
400 x2 1/2 1 0 0 1/2000 175
zj 200 400 0 0 0,2 70000
cj z j 100 0 0 0 0,2
cj 100 400 0 0 0
ck xk x1 x2 S1 S2 S3 b
A partir de C2 = 200; ya que es necesario que el indicador de
0 S1 1/2 0 1 0 1/2000 25 x sea negativo para que la solución implique sólo fabricar el
0 S2 3/2 0 0 1 1/2000 85 producto B
c2 x2 1/2 1 0 0 1/2000 175 1 1
zj 1/2c2 c2 0 0 0,2 70000 100 C2 0 100 C2 200 C2 C2 200
2 2
cj z j 1001/2c2 0 0 0 0,2
PRÁCTICA V 212
ÁLGEBRA (71)
h) ¿A qué costo incorporaría unidades adicionales de los recursos? Explique para cada uno de ellos interpretando según este enunciado.
No incorporaría unidades de materia prima, ni de mano de obra por tener sobrantes y estaría dispuesto a pagar un interés hasta del 20
%.
14) Una fábrica de equipos electrónicos construye amplificadores y altoparlantes. Debido a su capacidad puede construir hasta 100 unidades
diarias en total. Una convención le obliga a exportar a otras provincias la mitad de los amplificadores que fabrica y la tercera parte de los
altoparlantes, pero por un problema de transporte no puede exportar más de 40 unidades por día. Cada amplificador deja un beneficio de $50
y cada altoparlante deja $60.
PRÁCTICA V 213
ÁLGEBRA (71)
a)
b)
B( x; y ) 50 x 60 y
x y 40
1
1
sujeta a x y 40
2 3
x; y 0
c) , d) , e)
PRÁCTICA V 214
ÁLGEBRA (71)
x y 100
1
1
g) Nuevo beneficio a partir de los impuestos B( x; y ) 50 x 40 y sujeta a x y 40
2 3
x; y 0
Las nuevas producciones óptimas se obtienen con 40 amplificadores y 60 altoparlantes, y el beneficio máximo será $ 4400
B( x; y ) 50 x 40 y 0. S1 0. S 2
Las variables de holgura no aportan nada al valor de la función objetivo, por eso tienen en la expresión de la función objetivo coeficiente cero
En la solución óptima estas variables indican la cantidad de recursos disponibles no utilizados. Si valen cero significa que se han utilizado todos
los recursos y se dice que el recurso está saturado.
PRÁCTICA V 215
ÁLGEBRA (71)
cj 50 60 0 0
ck xk x1(x) x2(y) S1 S2 b
0 S1 1 1 1 0 100 Primera restricción
0 S2 1/2 1/3 0 1 40 Segunda restricción
Valor inicial de la función
Zj 1.0 +1/2.0=0 1.0 + 1/3.0 = 0 1.0 + 0.0 = 0 0.0 + 1.0= 0 100.0 + 40.0 = 0
objetivo
cj z j 50 – 0 = 50 60 – 0 = 60 0–0=0 0–0=0
S1 y S2 son las variables básicas (encabezan columnas de vectores canónicos), x e y son las variables no básicas
Solución básica inicial (x; y; S1; S2; S3)= (0; 0; 100; 40) B = 0
La tabla inicial representa el vértice que se encuentra en el origen. Hemos obtenido el primer vértice de la región de factibilidad V1 = (0; 0)
PRÁCTICA V 216
ÁLGEBRA (71)
Entre las básicas S1 o S2 elijo la variable de salida, para eso calculo los cocientes entre los elementos de la columna b con los respectivos
coeficientes de la columna de entrada o sea “y”
Elegimos la fila cuyo cociente positivo es menor o sea en nuestro caso la variable de salida es “S1”. Pintamos la fila correspondiente.
Se obtiene el pivote y se debe sustituir S1 y en su lugar poner “y” y donde está el coeficiente 0 de S2 poner el 60 de la y
Escribimos la fila del pivote y completamos la columna con tantos ceros como sean necesarios.
Los restantes números en este caso de la primera fila los calculamos por la regla del rectángulo
Luego calculamos zj y cj zj.
cj 50 60 0 0
ck xk x1(x) x2(y) S1 S2 b
60 y 1 1 1 0 100
0 S2 1/6 0 1/3 1 20/3
Zj 60 60 60 0 6000
cj zj 10 0 60 0
En esta nueva tabla las variables básicas son:
S2 = 20/3, y = 100, la función B = 6000, las variables no básicas son: x = 0, S1= 0
Obtenemos una nueva solución y la misma nos da otro vértice de la región de factibilidad adyacente al anterior: V = (0; 100)
Segunda solución factible (x; y; S1; S2)= (0; 100; 0; 20/3) B= 6000
Esta solución es la óptima ya que observando la última fila no quedan coeficientes positivos.
Por lo tanto el segundo vértice es (0; 100)
Solución óptima ( x ; y ; S1 ; S2 ; S3 ) 0;100;0;20 / 3 B 6000
PRÁCTICA V 217
ÁLGEBRA (71)
15) Se debe formular un alimento que contenga 3 componentes nutritivos básicos en las siguientes cantidades como mínimo:
45 gramos de lípidos
56 gramos de hidratos de carbono
60 gramos de proteínas
Para ello se dispone en el mercado de dos productos cuya composición en los tres componentes nutritivos básicos es la siguiente:
a) Formular el modelo lineal que permita obtener un alimento que cumpla con los requerimientos nutritivos y tenga costo mínimo.
10 x A 5 x B 45
7 x A 7 x B 56
Minimizar Z 6. x A 8. x B sujeta a
5 x A 15 x B 60
x 0, x 0
A B
PRÁCTICA V 218
ÁLGEBRA (71)
c) Calcular el mínimo costo del alimento que cumple los requerimientos nutritivos.
El costo mínimo es $52
PRÁCTICA V 219
ÁLGEBRA (71)
16) Una fábrica de bebidas cuenta con 60000 litros de materia prima con la que produce jugos de dos tipos: A (concentrado) y B (diluido). Los
mismos se envasan en cajas de 24 botellas. En una botella de jugos A se usa 1 litro de materia prima, y en
1
una de jugo B solo de litro de materia prima. La demanda de los productos no es mayor que 2000 cajas
3
de jugo A y 6000 de jugo B. Los precios de cada caja de jugos es $18 los de sabor A y $9 los de sabor B.
a) Plantear el modelo que permita optimizar las producciones de cada tipo de jugo.
x A 2000
x B 6000
Maximizar Z 18 x A 9 xB sujeta a
24 x A 8 x B 60000
x 0, x 0
A B
b) Determinar la relación precios A/B que permita a la fábrica producir más cajas de jugo con sabor A que B.
Para que se vendan más jugos A que B, la función objetivo debe maximizarse en el vértice (2000; 1500) y por lo tanto el valor que se obtenga de Z debe
ser mayor que el alcanzado en el vértice (500; 6000).
pA
Entonces 500pA+6000pB ≤ 2000pA+1500pB , 4500pB ≤ 1500pA luego 3 para que se vendan más unidades del producto A
pB
PRÁCTICA V 220
ÁLGEBRA (71)
17) La siguiente es la tabla simplex final correspondiente a un problema de maximización de programación lineal
cj 20 30 0 0
ck xk x1 x2 S1 S2 b
30 X2 4/5 1 1/5 0 40
0 S2 18/5 0 3/5 1 90
Zj 24 30 6 0
cj zj 4 0 6 0
b) Si existen recursos saturados y/o disponibilidad de cada uno de ellos: s1 0 (Recurso saturado) y s2 90 (disponibilidad sin utilizar)
c) El valor que se pagaría por incorporar una unidad más en cada uno de los sectores: $0 en el sector 2 y $6 en el sector 1
e) Para qué rango de valores de la contribución en el beneficio de x2 sigue siendo óptima la solución hallada: podría disminuir hasta $25 y la
solución óptima hallada seguiría siendo óptima
cj 20 c2 0 0
ck xk x1 x2 S1 S2 b
c2 X2 4/5 1 1/5 0 40
0 S2 18/5 0 3/5 1 90
Zj 4/5 c2 30 6 0
cj zj 20-4/5 c2 0 6 0
PRÁCTICA V 221
ÁLGEBRA (71)
18) La siguiente tabla suministra información sobre la fabricación de dos artículos A y B en los diferentes departamentos
19) Considerar un enunciado clásico de problema de programación lineal: tres líneas de producto y dos restricciones de insumos, según los datos del
siguiente cuadro:
Sabiendo que el total disponible de horas hombre es de 3800 y el horas máquina de 3300 y que la contribución de cada unidad del producto al
beneficio es de $200 para A, $30 para B y $100 para C.
40 x A 40 x B 20 xC 3800 40 x A 40 x B 20 xC 1 S1 0 S 2 3800
Sujeta a: 2 x A 8 x B 4 xC 3300 Sujeta a: 2 x A 8 x B 4 xC 0 S1 1 S 2 3300
x 0; x 0; x 0 x 0; x 0; x 0; x 0; S 0; S 0
A B C A B C C 1 2
PRÁCTICA V 223
ÁLGEBRA (71)
cj 200 30 100 0 0
ck xk x1(x) x2(y) x3(z) S1 S2 b
0 S1 40 40 20 1 0 3800 3800/40 = 95
0 S2 2 8 4 0 1 3300 3300/2= 1650
zj 0 0 0 0 0 0
cj zj 200 30 100 0
cj 200 30 100 0 0
ck xk x1(x) x2(y) x3(z) S1 S2 b
0 S1 1 1/2 1/40 0 95
0 S2 2 8 4 0 1 3300
zj 0 0 0 0 0 0
cj zj 200 30 100 0
cj 200 30 100 0 0
ck xk x1(x) x2(y) x3(z) S1 S2 b
200 x1(x) 1 1 1/2 1/40 0 95
0 S2 0 6 3 1/20 1 3110
zj 200 200 100 5 0 19.000
cj zj 0 170 0 5 Solución óptima ( x ; y ; z; S1 ; S2 ) 95;0;0;3110 B 19.000
PRÁCTICA V 224
ÁLGEBRA (71)
b) Indicar el precio máximo que el empresario estaría dispuesto a pagar por cada hora hombre adicional.
El precio sombra corresponde al indicador en valor absoluto de la variable de holgura correspondiente a las horas hombre, en este caso S2.
En este caso es: $5 por cada hora hombre adicional
PRÁCTICA V 225