Deber 1

1. Considerar el siguiente problema de programación lineal:

Máximo 1000x1+ 1200x2
Sujeto a
8x1 + 4x2≤160
4x1+ 6x2≤120
x1 ≤34
x2 ≤14
x1,x2≥0
Resolver este problema con el algoritmo del simplex (forma tabla).

2. Considerar el siguiente problema de programación lineal:

Max 45x1+ 80x2
Sujeto a
5x1+ 20x2≤400
10x1+ 15x2≤450
x1,x2≥0
Resuelve este problema con el algoritmo del simplex (forma de tabla).

3. Resolver los problemas con el método gráfico

a) Min - 2x1-x2
Sujeto a
x1+ 4x2≤24
x1+ 2x2≤14
2x1-x2≤8
x1-x2≤3
x1,x2 ≥0

b) Máx 45x1+ 80x2

Sujeto a
5x1+ 20x2≤400
10x1+ 15x2≤450
x1,x2≥0
4. Considerar el siguiente problema de programación lineal:
Min -3x1- 6x2
Asunto a
3x1+x2≤48
x["1"]+ 3x2≤48
x1 ,x2≥0

a) Resolver el problema con el método gráfico.

b) Resolver este problema con el algoritmo del simplex (forma tabla).
 1

Deber 2

1. Determinar todas las soluciones básicas realizables para el sistema

2x 1+ 6x 2+ x3+ x 4= 3
6x 1+ 4x 2+ 3x 3+ 6x 4= 2
x j≥ 0 j= 1,2,3,4

2. Considerar el problema de programación lineal

minz= −x1− 2x 2− 3x3+ x 4

Sujeto a
x1+ 2x 2+ 3x 3 = 15
2x 1+ x2+ 5x 3 = 20
x1+ 2x 2 + x3+ x 4 = 10
x j≥ 0,j= 1,2,3,4

En una cierta iteración del simplex, la inversa de la base es

⎡ 5/7− 3/7 0 ⎤
⎢ −1/7 2/7 0 . ⎥
⎢ ⎥
⎢⎣ − 9 / 7 4 / 7 1 ⎥⎦
a) Continuar la resolución de este problema después de haber identificado la tabla del
simplexe asociado a esta base.
b) Supongamos que el término de la derecha de la tercera restricción se haga igual a
8 (es decir, x1+ 2x 2+ x3+ x 4= 8). La solución de base óptima obtenida en a)

¿Es realizable? ¿Cuál es la modificación del valor óptimo de?

¿la función económica?
 2

3. Considerar el siguiente problema de programación lineal

menta= −4x 1−12x 2 − 3x3

Sujeto a
x1 ≤ 100
x2 ≤ 50
x3≤ 150
3x1+ 6x 2+ 2x 3≤ 675
x j≥ 0,j= 1,2,3

Dénotantx4,x5,x6,x7las variables de holgura, la tabla del simplex asociada a la base donde

x4,x5,x6,x7son las variables de base y tienen la forma

Var. base Términos

x1 x2 x3x 4x5x6x7− z derecha

x4 1 0 0 1 0 0 0 0 100

x5 0 1 0 0 1 0 0 0 50

x6 0 0 1 0 0 1 0 0 150

x7 3 6 2 0 0 0 1 0 675
−z -4 -12 -3 0 0 0 0 1 0
Tabla 1

En una cierta iteración del algoritmo del simplex, encontramos la tabla

siguiente

Var. base Términos

x1x 2x3x 4x5x6x7− z derecha

x1 1 0 0 0 –2 –2/3 1/3 0 a4
x2 0 1 0 0 1 0 0 0 50

x4 0 0 0 1 2 2/3 - 1/3 0 75

x3 0 0 1 0 0 1 0 0 150
−z a1a 2a3 0 4 1/3 4/3 1 1150

Tableau 2
 3

a) Especificar la inversa de la base asociada al Cuadro 2. Justificar cómo se puede

leerlo directamente en la Tabla 2.
b) Determinar los valores de ea1 , a 2, a 3, a 4en la Tabla 2.
c) ¿Es óptima la solución en la tabla 2? ¿Por qué?

4. Considerar el siguiente problema de programación lineal

menta= −3x 1− x 2− 3x3

Sujeto a
2x 1+ x2+ x3≤ 2
x1+ 2x2+ 3x3≤ 5
2x 1+ 2x 2+ x3≤ 6
x j≥ 0,j= 1,2,3

Utilicemos las variables de desviación x4,x5,x6para transformar el problema en forma

estándar.
En una iteración del simplex encontramos la siguiente tabla

x1x 2x3x 4x5x6− z

5 1 0 3 -1 0 0f
e0 1 –2 1 0 0 1
–5 0 0 –4 1 1 0 3
d0 0g2 0 1 4

a) Especificar la inversa de la base asociada a esta tabla del simplex.

b) Déterminer les valeurs ded ,e, f, g.
c) ¿Es óptima la solución en esta tabla? ¿Por qué? De lo contrario, continúe la
resolución del problema para identificar una solución óptima.
¿Cuál es el valor más grande?∆ de la cual podemos aumentar el
término derecho de la primera restricción para que la solución óptima
identificada en c) sigue siendo realizable para el nuevo problema así generado, y
cuál es el valor óptimo de este nuevo problema.
Deber 3

1. Resolver los siguientes problemas utilizando primero una fase I

a) minz= –2x1–x2–x3
Sujeto a
2x1+ 3x2 –x3≤9
2x2+x3≥4
x1 +x3= 6
xj≥0,j= 1,2,3

b) minz=x1
Sujeto a
x1- 2x2+x3= 2
–x1+ 3x2+x3= 1
2x1-3x2+ 4x3= 7
xj≥0,j= 1,2,3

c) minz=x1
Sujeto a
x1+x2= 2
- 3x1 - 3x2= 3
xj≥0,j= 1,2

2. Consideremos el sistema de inecuaciones Ax≥b, x≥0, donde b≥0. Transformamos esto

sistema en una forma estándar introduciendo variables de desviación para
obtener el siguiente sistema Ax–y=b, x≥0, y≥0 donde b≥0. Denotemos
bk = máx {byo},
1≤yo≤m

y consideremos la nueva forma estándar obtenida de la anterior en

addicionante lakéelínea a todas las demás líneas después de haber cambiado su signo.
Indicar por qué es suficiente introducir una sola variable artificial para obtener
una solución básica realizable inicial.

Ilustre este procedimiento sobre el siguiente problema

x1+ 2x2+x3≥4
2x1+x2+x3≥5
2x1+ 3x2+ 2x3>=6
xj≥0,j= 1,2,3
Deber4

1. Resolver con la variante del simplex para problemas con variables acotadas:

máx x1 + 3x2- 2x3

Sujeto a
x2- 2x3≤1
2x1+x2+ 2x3≤8
0≤x1≤1, 0≤x2≤3, 0≤x3≤2

2. Resolver con la variante del símplex para problemas con variables acotadas

máx 2x1+ 3x2 – 2x3+ 5x4

Sujeto a
2x1+ 2x2+x3 + 2x4≤5
x1+ 2x2-3x3+ 4x4≤5
0≤xj≤1 ,j=1,2,3,4
Deber5

1. a) Suponiendo que el dual de

mincTx maxbTy
Sujet a Ax≥ b est Sujeto a ATy≤ c
x≥ 0 y≥ 0.

demostrar que el dual de

mincTx maxbTy
Sujet a Ax= b está Sujeto a ATy≤ c.
x≥ 0

b)Demostrar que el dual

maxbTy mincTx
Sujet a ATy≤ c est Sujeto a Ax≥ b
y≥ 0 x≥ 0.

2. Suponga que x*ey* son soluciones óptimas del par de problemas

dual-primal siguiente :

mincTx maxbT y
Sujeto a Ax≥ b Sujeto a ATy≤ c
x≥ 0 y≥ 0.

Supongamos que x es una solución óptima del problema

mincTx
Sujet a Ax≥ b ′
x ≥ 0.

′ ′T
Demostrar que x≥T por*
3. a) Resolver gráficamente el siguiente problema de programación lineal

máx 3 años1+ 4y2

Sujeto a 2 y 1+ y 2≤ 2
y1− 2 y 2≤ 6
3y 1+ 9 y 2≤ 1.

b) Escribir el dual de este problema. Utilizar la teoría de las discrepancias complementarias

pour déterminer une solution optimale de ce problème à partir d’une solution
óptimo de primal que le está asociado.
Deber6

1. Demostrar que ni el siguiente problema, ni su dual poseen solución

realizable :

minx1− 2x 2
Sujeto a x1 − x2≥ 2
− x1+ x2≥ −1

2. Considerar el siguiente problema

maxz= 2x 1− 4x 2
(Primal) Sujeto a x1− x2≤ 1
x1 ,x2≥ 0

a) Escribir el problema dual y resolverlo por observación.

b) Utilizar la teoría de los márgenes complementarios y la solución óptima del

problema dual para determinar una solución óptima del primal.

c) Para qué valores dec1, el coeficiente dex1en la función

¿La solución dual no tiene solución realizable en la economía primal?
Para estos valores dec1, ¿qué sucede con el problema primal?

3. Utilizar el método dual del simplex para resolver el siguiente problema:

mín 3x1+ x2+ x3

Sujeto a x1 + 2x 2 ≥8
3x 1− 2x 2− x3≥ 6
− x1− x2+ 4x 3≥ 2
x1 ,x2,x3≥ 0.
Devoir7

1. Sea el problema

menta= 2x 1+ x 2− 3x 3+ 2x 4
Sujeto a x1+ 3x 2− x 3+ 2x 4≤ 7
− x1− 2x 2+ 4x 3≤ 12
− x1− 4x 2+ 3x 3+ 8x 4≤ 10
x1,x2,x3,x4≥ 0.

Supongamos que la tabla asociada a la solución óptima de este problema es la siguiente:

x1x2x3x4x5x6x7–z
3/10 1 0 4/5 2/5 1/10 0 0 4
-1/10 0 1 2/5 1/5 3/10 0 0 5
1/2 0 0 10 1 – 1/2 1 0 11
7/5 0 0 12/5 1/5 4/5 0 111

¿De qué cantidad hay que modificar el costo?4para que se vuelva ventajoso de
devolver la variablex4¿positivo?

b) Determinar el intervalo de variación [γ1 ,γ2du coûtc2para que la solución actual

residencia óptima.

c) Determinar el intervalo de variación [τ1 ,τ2del término de la derecha de la segunda

restricción para que la solución actual siga siendo viable y óptima.

d) Introducir una nueva variable y en el problema original que tenga 1 como

coeficiente en cada una de las restricciones y un costo unitario igual a -2. Determinar
una solución óptima del problema modificado.

e) Introducir la nueva restricción siguiente en el problema original:

x1 + x 2+ x 3+ x 4≤ 15.
¿El problema modificado tiene una solución factible? Si es así, determine una.
solución óptima del problema modificado.
 2. Sea el problema

menta= x1− 3x 2+ 2x 3
Sujeto a 3x1− x 2+ 2x3≤ 7
− 2x 1+ 4x 2≤ 12
− 4x 1+ 3x 2+ 8x 3≤ 10
x1,x2,x3≥ 0.

La tabla asociada a la solución óptima de este problema es la siguiente:

x1x2x3x4x5 x6–z
1 0 4/5 2/5 1/10 0 0 4
0 1 2/5 1/5 3/10 0 0 5
0 0 10 1 – 1/2 1 0 11
0 0 12/5 1/5 4/5 0 1 11

¿De qué cantidad hay que modificar el costo?3para que se vuelva ventajoso de
devolver la variablex3¿positivo?

b) Determinar el intervalo de variación [γ1,γ2du coûtc6para que la solución actual

morada óptima.

c) Determinar el intervalo de variación [τ1,τ2del término de la derecha del segundo

constraint para que la solución actual permanezca realizable y óptima.

d) Supongamos que el coeficiente33de la variablex3en la tercera restricción

toma el valor 12 en lugar de 8 como en el problema original. Determinar
una solución óptima del problema modificado.

e) Introducir una nueva variable y en el problema original teniendo 1 como

coeficiente en la primera restricción, 1 en la segunda, 9 en la tercera, y
un costo unitario igual a -1. Determinar una solución óptima del problema modificado.

f) Introducir la nueva restricción siguiente en el problema original:

x1+ 3x 2+ x 3≤ 18.
¿El problema modificado tiene una solución viable? Si es así, determinar una
solución óptima del problema modificado.