Universidad del Desarrollo Optimización de Sistemas I
Facultad de Ingeniería Viernes 07 de junio de 2019
SEGUNDO CERTAMEN DE OPTIMIZACIÓN DE SISTEMAS I
Instrucciones
- El certamen es sin apuntes y a libro cerrado.
- Se permite el uso de calculadoras NO GRAFICADORAS.
- El uso de cualquier artefacto electrónico está prohibido.
- La prueba puede ser contestada en un tiempo máximo de 2 horas.
- Se podrán realizar consultas al profesor en voz alta.
Normas de Comportamiento Durante la Evaluación
Durante el desarrollo de esta evaluación se considerará una actitud deshonesta y que amerita sanción por
parte de la Facultad, cualquiera de las siguientes acciones:
1. Ser sorprendido usando, o estar en posesión de cualquier fuente de información no entregada por la
Facultad (textos, apuntes, ayudas de memoria en papel, apuntes en partes del cuerpo, mesas, equipos,
etc.).
2. Estar en posesión durante la evaluación de un equipo electrónico no autorizado (teléfono celular, Tablet,
relojes inteligentes, calculadora no proporcionada por la facultad, reproductores de mp3 y mp4, o
cualquier otro aparato electrónico que pueda almacenar información relacionado con la evaluación), ya
sea encendido o apagado. Todos los equipos antes mencionados deben estar guardados en sus
mochilas o bolsos personales y éstos deben ser dejados en la parte delantera de la sala o donde
dispongan quienes cuidan la evaluación.
3. Ser sorprendido mirando las evaluaciones de otros compañeros.
4. Ser sorprendido interactuando durante el desarrollo de la evaluación con alguno de sus compañeros
(conversando, gesticulando, etc.).
5. Cualquier actitud no descrita en los puntos anteriores y que sea considerada deshonesta por quienes
cuidan la evaluación.
Evite exponerse a situaciones que pueden terminar con sanciones disciplinarias determinadas en el
Reglamento Académico del Alumno de pregrado y el Reglamento de disciplina del Alumno Regular.
Problema 1 (35 puntos)
Según expertos, el cambio climático está produciendo un aumento en la ocurrencia de fenómenos
meteorológicos extremos como los tornados observados recientemente en Concepción y Los Ángeles. Para
hacer frente a esto, la Oficina Nacional de Emergencias (ONEMI) le ha solicitado que proponga un modelo
de optimización que apoye el diseño de una red de albergues en una ciudad.
Para ello, considere que B es el conjunto de barrios en que una ciudad está dividida y L es el conjunto de
ubicaciones potenciales en que se podría habilitar un albergue. En cada barrio i ϵ B viven Pi habitantes, de
los cuales se estima que una fracción fi deberán ser llevados a un albergue en caso de emergencia.
Considere también que en caso de habilitar un albergue en la ubicación j ϵ L su capacidad será de Kj
personas.
El modelo debe decidir la ubicación óptima de los albergues, la cantidad de kits de emergencia que debe
tenerse en cada uno, y la cantidad de personas de cada barrio que deben ser asignadas a cada albergue de
modo de minimizar los costos totales asociados, considerando que todas las personas que podrían requerir
ser llevados a un albergue deben ser asignadas a alguno de ellos. Se sabe que el costo de habilitar un
albergue es CHj y el costo de adquirir y mantener cada kit de emergencia en cada albergue es CEj. Existe
además un costo asociado al traslado de personas a los albergues en caso de emergencia, para lo cual se
sabe que Dij es la distancia (km) entre el barrio i y la ubicación potencial j, y CTij es el costo por kilómetro de
trasladar a una persona desde el barrio i y la ubicación j. Por estándares definidos por la ONEMI, en cada
albergue que se habilite debe tenerse al menos un 10% más de kits de emergencia que personas asignadas
a dicho albergue. Recuerde que no puede asignar personas a albergues que no ha habilitado.
a) Formule un modelo de optimización lineal que represente el problema. (25 puntos)
b) Considere que para cada par de ubicaciones potenciales de albergues existe un parámetro ωjk, que vale
1 si la ubicación j y la ubicación k están a más de 1 kilómetro de distancia y 0 si están a 1 kilómetro de
Profesores: Pablo González Araya - Pablo González Brevis - Cristian Palma Infante
Universidad del Desarrollo Optimización de Sistemas I
Facultad de Ingeniería Viernes 07 de junio de 2019
distancia o menos. Formule la(s) restricción(es) que evite(n) que se habiliten dos albergues que estén a
1 kilómetro o menos de distancia entre ellos. (3 puntos)
c) Modele las siguientes condiciones lógicas: (7 puntos)
i) Se exige que un albergue debe habilitarse en la ubicación potencial L3 o en la L7 (2 puntos)
ii) Si se habilita el albergue L1 y el L2, no se puede habilitar el albergue L3 (2 puntos)
iii) Si se habilita el albergue L3, se debe habilitar el albergue L5 o el L6, no ambos. En caso que no se
habilite el albergue en L3 no hay restricciones sobre la habilitación de L5 y L6. (3 puntos)
Problema 2 (40 puntos)
Considere el siguiente problema de optimización:
min 𝑧 = −10𝑥1 + 5𝑥2
𝑠𝑢𝑗𝑒𝑡𝑜 𝑎:
2𝑥1 − 𝑥2 ≥ 1
5𝑥1 + 2𝑥2 ≤ 79
𝑥1 + 4𝑥2 ≥ 5
𝑥1 , 𝑥2 ≥ 0
a) Formule la forma estandarizada del problema. (2 puntos)
b) Formule el problema artificial. (2 puntos)
c) Considere el siguiente tableau:
Base z0 x1 x2 x3 x4 x5 x6 x7 Solución
z0 1 β ε 0,5 0 -1 -1,5 0 σ
x1 0 γ -0,5 -0,5 0 0 0,5 0 0,5
x4 0 0 4,5 2,5 1 0 -2,5 0 76,5
x7 0 0 μ 0,5 0 -1 -0,5 1 ω
Encuentre los valores faltantes utilizando la relación entre Simplex matricial y Simplex tabular. (12
puntos)
d) Partiendo del tableau anterior resuelva la Fase I. Señale explícitamente la solución óptima encontrada
(valores de las variables básicas y de la función objetivo). (8 puntos)
Considere la solución básica factible 𝑥1 = 1, 𝑥2 = 1, 𝑥4 = 72, 𝑧0 = −5 para el problema original (no el
artificial) y utilice Simplex matricial para responder las siguientes preguntas.
e) ¿Cómo se comporta la función objetivo dado un cambio en las variables no básicas? Explique (4 puntos)
f) ¿Cómo se comportan las variables básicas dado un cambio en las variables no básicas? Explique (4
puntos)
g) Utilizando la información encontrada en las preguntas e) y f) y sin iterar simplex, prediga qué valor tendrá
la función objetivo y las variables básicas con un cambio de base. (8 puntos)
Problema 3 (25 puntos)
Considere que cuenta con la siguiente información sobre un problema de programación lineal que intentó
resolver hace un tiempo, y que hoy, nuevamente, intentará resolver. Como ha pasado tanto tiempo usted no
dispone de un registro acabado del problema. Sin embargo, recuerda perfectamente que: (1) la función
objetivo del problema original era maximizar 40𝑥1 + 60𝑥2 ; (2) todas las restricciones del problema original
eran del tipo menor o igual, excepto por la última restricción que era del tipo mayor o igual; (3) todas las
variables de decisión son no negativas; (4) cuando estandarizó el problema, y empezó a iterar con Simplex,
determinó el punto extremo 𝑥1 = 34, 𝑥2 = 2, 𝑥3 = 0, 𝑥4 = 4, 𝑥5 = 0; (5) que las matrices B y B-1N asociadas a
este punto extremo son:
3⁄ 1⁄
2 1 0 5 5
𝐵 = [ 1 1 1] −1
𝐵 𝑁= −1 ⁄5 −2 ⁄5
1 3 0 −2⁄ 1⁄
[ 5 5]
a) Con la información anterior, determine la forma estándar del problema que intentó resolver. (10 puntos)
b) Determine la solución y el valor óptimo del problema utilizando Simplex matricial. Por cierto, puede utilizar
convenientemente como solución básica factible inicial el punto extremo que recordó. (15 puntos)
Profesores: Pablo González Araya - Pablo González Brevis - Cristian Palma Infante
Universidad del Desarrollo Optimización de Sistemas I
Facultad de Ingeniería Viernes 07 de junio de 2019
PAUTA DE CORRECCIÓN
SEGUNDO CERTAMEN DE OPTIMIZACIÓN DE SISTEMAS I
Problema 1 (35 puntos)
a. 25 puntos
Variable (6ptos)
1 𝑠𝑖 𝑠𝑒 ℎ𝑎𝑏𝑖𝑙𝑖𝑡𝑎 𝑎𝑙𝑏𝑒𝑟𝑔𝑢𝑒 𝑒𝑛 𝑙𝑎 𝑢𝑏𝑖𝑐𝑎𝑐𝑖ó𝑛 𝑗
𝑥𝑗 = {
0 𝑠𝑖 𝑛𝑜
𝑦𝑖𝑗 = 𝑐𝑎𝑛𝑡𝑖𝑑𝑎𝑑 𝑑𝑒 𝑝𝑒𝑟𝑠𝑜𝑛𝑎𝑠 𝑑𝑒𝑙 𝑏𝑎𝑟𝑟𝑖𝑜 𝑖 𝑞𝑢𝑒 𝑠𝑜𝑛 𝑎𝑠𝑖𝑔𝑛𝑎𝑑𝑎𝑠 𝑎𝑙 𝑎𝑙𝑏𝑒𝑟𝑔𝑢𝑒 𝑗
𝑧𝑗 = 𝑐𝑎𝑛𝑡𝑖𝑑𝑎𝑑 𝑑𝑒 𝑘𝑖𝑡𝑠 𝑑𝑒 𝑒𝑚𝑒𝑟𝑔𝑒𝑛𝑐𝑖𝑎 𝑎 𝑡𝑒𝑛𝑒𝑟 𝑒𝑛 𝑒𝑙 𝑎𝑙𝑏𝑒𝑟𝑔𝑢𝑒 𝑗
Función Objetivo (6p, 2p cada término)
𝑀𝑖𝑛 ∑ 𝐶𝐻𝑗 𝑥𝑗 + ∑ 𝐶𝐸𝑗 𝑧𝑗 + ∑ ∑ 𝐷𝑖𝑗 𝐶𝑇𝑖𝑗 𝑦𝑖𝑗
𝑗∈𝐿 𝑗∈𝐿 𝑖∈𝑁 𝑗∈𝐿
Sujeto a
Todas las personas deben ser asignadas a un albergue, 3p]
∑ 𝑦𝑖𝑗 = 𝑓𝑖 𝑃𝑖 ∀𝑖 ∈ 𝑁
𝑗∈𝐿
[capacidad de albergues, 3p capacidad + 3p activación. Pueden estar en ec. separadas]
∑ 𝑦𝑖𝑗 ≤ 𝐾𝑗 𝑥𝑗 ∀𝑗 ∈ 𝐿
𝑖∈𝑁
[cantidad mínima de kits en albergues, 3p]
𝑧𝑗 ≥ 1,1 ∑ 𝑦𝑖𝑗 ∀𝑗 ∈ 𝐿
𝑖∈𝑁
[Naturaleza de las variables, 1p]
𝑥𝑗 ∈ {0,1} ∀𝑗 ∈ 𝐿
𝑧𝑗 ≥ 0 ∀𝑗 ∈ 𝐿
𝑦𝑖𝑗 ≥ 0 ∀𝑖 ∈ 𝑁, 𝑗 ∈ 𝐿
b. 3 puntos
𝑥𝑖 + 𝑥𝑗 ≤ 1 ∀𝑖 ∈ 𝑁, 𝑗 ∈ 𝐿| 𝜔𝑖𝑗 = 0
Otra opción posiblemente más usada será: 𝑥𝑖 + 𝑥𝑗 ≤ 1 + 𝜔𝑖𝑗 ∀𝑖 ∈ 𝑁, 𝑗 ∈ 𝐿
c. 7 puntos
i. (2p) 𝑥𝐿3 + 𝑥𝐿7 = 1
ii. (2p) 𝑥𝐿1 + 𝑥𝐿2 ≤ 2 − 𝑥𝐿3
iii. (3p) 𝑥𝐿3 ≤ 𝑥𝐿5 + 𝑥𝐿6
𝑥𝐿5 + 𝑥𝐿6 ≤ 2 − 𝑥𝐿3
Profesores: Pablo González Araya - Pablo González Brevis - Cristian Palma Infante
Universidad del Desarrollo Optimización de Sistemas I
Facultad de Ingeniería Viernes 07 de junio de 2019
Problema 2 (40 puntos)
a) (2 puntos)
min 𝑧 = −10 𝑥1 + 5 𝑥2
𝑠𝑢𝑗𝑒𝑡𝑜 𝑎:
2 𝑥1 − 𝑥2 − 𝑥3 =1
5𝑥1 + 2𝑥2 + 𝑥4 = 79
𝑥1 + 4𝑥2 − 𝑥5 = 5
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0
b) (2 puntos)
min 𝑤 = 𝑥6 + 𝑥7
𝑠𝑢𝑗𝑒𝑡𝑜 𝑎:
2 𝑥1 − 𝑥2 − 𝑥3 + 𝑥6 =1
5𝑥1 + 2𝑥2 + 𝑥4 = 79
𝑥1 + 4𝑥2 − 𝑥5 + 𝑥7 = 5
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 , 𝑥6 , 𝑥7 ≥ 0
c) (12 puntos)
Base z0 x1 x2 x3 x4 x5 x6 x7 Solución
z0 1 β ε 0,5 0 -1 -1,5 0 σ
x1 0 γ -0,5 -0,5 0 0 0,5 0 0,5
x4 0 0 4,5 2,5 1 0 -2,5 0 76,5
x7 0 0 μ 0,5 0 -1 -0,5 1 ω
i) (2 puntos) Sabemos que el coeficiente en el renglón 0 asociado a una variable básica debe ser
0. Por lo tanto, β = 0.
ii) (2 puntos) De la misma forma, se sabe que el coeficiente del renglón en donde está la variable
básica debe ser 1. Por lo tanto, γ = 1.
iii) (2 puntos) El coeficiente en el renglón 0 asociado a una variable no básica son los coeficientes
reducidos, por lo que debemos calcular −(𝑐𝐵 − 𝑐𝑁 𝐵 −1 𝑁)
2 0 0 0,5 0 0
𝐵 = [5 1 0] 𝐵 −1 = [−2,5 1 0]
1 0 1 −0,5 0 1
-1 -1 0 1
N = 2 0 0 0
4 0 -1 0
𝑐𝐵 = (0, 0, 1) 𝑐𝑁 = (0, 0, 0, 1)
Entonces, −(𝑐𝐵 − 𝑐𝑁 𝐵 −1 𝑁) = (4,5, 0,5, −1, −1,5)
Por lo tanto, ε = 4,5.
iv) (2 puntos) Los coeficientes en los demás renglones asociados a las variables no básicas,
corresponden a las tasas de decrecimiento de las variables básicas respecto de las variables no
básicas, por lo que se debe calcular 𝛼𝑥2 = 𝐵 −1 𝑎2
−0,5
𝛼𝑥2 = [ 4,5 ]
4,5
Por lo tanto, μ = 4,5.
v) (2 puntos) En la columna solución, asociado al renglón 0 se encuentra el valor que toma la
función objetivo. En este caso, se debe calcular 𝑧0 = 𝑐𝐵 𝐵 −1 𝑏. Por lo tanto, σ = 4,5.
vi) (2 puntos) En la columna solución, asociado a los renglones distintos del 0, se encuentran los
valores de 𝑥𝐵 = 𝐵 −1 𝑏. Por lo tanto, ω = 4,5.
Profesores: Pablo González Araya - Pablo González Brevis - Cristian Palma Infante
Universidad del Desarrollo Optimización de Sistemas I
Facultad de Ingeniería Viernes 07 de junio de 2019
d) (8 puntos)
Base z0 x1 x2 x3 x4 x5 x6 x7 Solución
z0 1 0 4,5 0,5 0 -1 -1,5 0 4,5
x1 0 1 -0,5 -0,5 0 0 0,5 0 0,5
x4 0 0 4,5 2,5 1 0 -2,5 0 76,5
x7 0 0 4,5 0,5 0 -1 -0,5 1 4,5
Con la información de este tableau, se determina que entra a la base x2 y sale de ella x7.
El nuevo tableau queda de la siguiente forma:
Base z0 x1 x2 x3 x4 x5 x6 x7 Solución
z0 1 0 0 0 0 0 -1 -1 0
x1 0 1 0 -0,44 0 -0,11 0,44 0,11 1
x4 0 0 0 2 1 1 -2 -1 72
x2 0 0 1 0,11 0 -0,22 -0,11 0,22 1
Estamos en un óptimo pues la función objetivo no puede decrecer más y las variables artificiales ya no
están en la base, por lo que se da término a la Fase I. La función objetivo y las variables básicas toman
los siguientes valores 𝑧0 ∗ = 0, 𝑥1 ∗ = 1, 𝑥2 ∗ = 1, 𝑥4 ∗ = 72.
e) (4 puntos)
Debemos calcular los coeficientes reducidos 𝑐𝐵 − 𝑐𝑁 𝐵 −1 𝑁 con 𝑥𝐵 = (𝑥1 , 𝑥2 , 𝑥4 )
𝑐𝐵 − 𝑐𝑁 𝐵 −1 𝑁 = (−5 0)
Si ingresa x3 a la base, la función objetivo decrece en 5 unidades por cada unidad que crece x 3.
Si ingresa x5 a la base, la función objetivo no sufre ningún cambio.
Por lo tanto, para mejorar la función objetivo, x3 debiera entrar a la base
f) (4 puntos)
Debemos calcular las tasas de cambio de las variables básicas respecto de las variables no básicas. Es
decir:
−0,44 −0,11
𝐵 −1 𝑁 = ( 0,11 −0,22)
2 1
Los datos nos señalan que:
Al crecer x3 en una unidad, x1 crece 0,44 unidades.
Al crecer x3 en una unidad, x2 decrece 0,11 unidades.
Al crecer x3 en una unidad, x4 decrece 2 unidades.
Al crecer x5 en una unidad, x1 crece 0,11 unidades.
Al crecer x5 en una unidad, x2 crece 0,22 unidades.
Al crecer x5 en una unidad, x4 decrece 1 unidades.
g) (8 puntos)
Ya vimos que es x3 la variable que debe entrar a la base. Para saber qué valor tomará la variable x 3 al
entrar a la base, debemos calcular el valor de 𝜃 = min {1⁄0,11 , 72⁄2} = 9
Por lo tanto, x3 toma valor 9 al ingresar a la base.
Sabemos que la función objetivo decrecerá en 5 unidades por cada unidad que crezca x 3. Por lo tanto,
la función objetivo tomará valor −50 = −5 + (−5 ∗ 9). (2 puntos)
Conocemos el efecto de x3 sobre las variables básicas. Por lo tanto:
El nuevo valor de 𝑥1 = 1 + (0,44 ∗ 9) = 5. (2 puntos)
El nuevo valor de 𝑥2 = 1 + (−0,11 ∗ 9) = 0. (2 puntos)
El nuevo valor de 𝑥4 = 72 + (−2 ∗ 9) = 54. (2 puntos)
Profesores: Pablo González Araya - Pablo González Brevis - Cristian Palma Infante
Universidad del Desarrollo Optimización de Sistemas I
Facultad de Ingeniería Viernes 07 de junio de 2019
Problema 3 (25 puntos)
a) (10 puntos)
Con B y con B-1 * N podemos obtener la matriz N:
3⁄ 1⁄
2 1 0 5 5 1 0
𝐵 ∗ 𝐵 −1 ∗ 𝑁 = [1 1 1] −1⁄5 −2⁄5 → 𝑁 = [0 0 ] [2 puntos]
1 3 0 −2 1⁄ 0 −1
[ ⁄5 5]
Mirando la función objetivo original max 𝑧 = 40𝑥1 + 60𝑥2 , se deduce que las variables 𝑥1 y 𝑥2 no pueden
ser variables de holgura ni superávit por cuanto su costo en la función objetivo es distinto de 0.
Por lo demás, se menciona que las restricciones originales son del tipo menor o igual, excepto por la
última restricción que es del tipo mayor o igual. Como la matriz B es de dimensión 3x3, podemos deducir
que hay 3 restricciones, que las dos primeras son del tipo menor o igual, y la última es del tipo mayor
igual. Por lo tanto, se tienen dos variables de holgura asociadas a las dos primeras restricciones (𝑥3 , 𝑥4 )
y 1 variable de superávit asociada a la última restricción (𝑥5 ).
Luego, la primera columna de B está asociada a 𝑥1 , la segunda columna está asociada a 𝑥2 , y la tercera
columna de la matriz B está asociada a 𝑥4 pues estas variables son las que pertenecen a la base en el
punto extremo dado (𝑥1 = 34, 𝑥2 = 2, 𝑥3 = 0, 𝑥4 = 4, 𝑥5 = 0).
Análogamente, la primera columna de N corresponde a 𝑥3 y la segunda a 𝑥5 .
De esta forma, es posible determinar los vectores de coeficientes tecnológicos de cada variable:
2 1 1 0 0
𝑎1 = [1] ; 𝑎2 = [1] ; 𝑎3 = [0] ; 𝑎4 = [1] ; 𝑎5 = [ 0 ] [5 puntos]
1 3 0 0 −1
Falta determinar el vector de recursos b. Para ello, se tiene que 𝑥𝐵 = 𝐵 −1 𝑏 → 𝐵 𝑥𝐵 = 𝐵 𝐵 −1 𝑏 = 𝑏,
entonces:
2 1 0 34 70
[1 1 1] [ 2 ] = [40] [3 puntos]
1 3 0 4 40
En consecuencia, se tiene toda la información para construir el problema en forma estándar. Este
queda:
max 𝑧 = 40𝑥1 + 60𝑥2
𝑠. 𝑎.
2𝑥1 + 𝑥2 + 𝑥3 = 70
𝑥1 + 𝑥2 + 𝑥4 = 40
𝑥1 + 3𝑥2 − 𝑥5 = 40
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0
b) (15 puntos)
Iterando desde el punto (𝑥1 = 34, 𝑥2 = 2, 𝑥3 = 0, 𝑥4 = 4, 𝑥5 = 0), tenemos:
𝑥𝐵 = (𝑥1 𝑥2 𝑥4 ) 𝑥𝑁 = (𝑥3 𝑥5 )
𝐶𝐵 = (40 60 0) 𝐶𝑁 = (0 0)
2 1 0 1 0 70
𝐵 = [ 1 1 1] 𝑁 = [0 0 ] 𝑏 = [40]
1 3 0 0 −1 40
3⁄ −1⁄ 3⁄ 1⁄
5 0 5 5 5 34
−1
𝐵 = −1 ⁄5 0 2⁄5 −1
𝐵 𝑁= −1 ⁄5 −2 ⁄5 𝑥𝐵 = [ 2 ] 𝑧 = 1.480
−2⁄ 1 −1⁄ −2 1⁄ 4
[ 5 5] [ ⁄5 5]
Criterio de Optimalidad:
𝐶𝑁 − 𝐶𝐵 𝐵 −1 𝑁 = (−12 16) Aún no estamos en un óptimo. Debe entrar 𝑥5 a la base. [2 puntos]
Criterio de Factibilidad:
34 4
𝜃 = 𝑚𝑖𝑛 {1 , 1 } = 𝑚𝑖𝑛{170, 20} = 20 Debe salir 𝑥4 de la base. [2 puntos]
⁄5 ⁄5
Profesores: Pablo González Araya - Pablo González Brevis - Cristian Palma Infante
Universidad del Desarrollo Optimización de Sistemas I
Facultad de Ingeniería Viernes 07 de junio de 2019
II° Iteración:
𝑥𝐵 = (𝑥1 𝑥2 𝑥5 ) 𝑥𝑁 = (𝑥3 𝑥4 )
𝐶𝐵 = (40 60 0) 𝐶𝑁 = (0 0)
2 1 0 1 0 70
𝐵 = [1 1 0 ] 𝑁 = [0 1] 𝑏 = [40]
1 3 −1 0 0 40
1 −1 0 1 −1 30
𝐵 −1 = [−1 2 0] 𝐵 −1 𝑁 = [−1 2] 𝑥𝐵 = [10] 𝑧 = 1.800
−2 5 −1 −2 5 20
Criterio de Optimalidad:
𝐶𝑁 − 𝐶𝐵 𝐵 −1 𝑁 = (20 −80) Aún no estamos en un óptimo. Debe entrar 𝑥3 a la base. [2 puntos]
Criterio de Factibilidad:
30
𝜃 = 𝑚𝑖𝑛 { } = 𝑚𝑖𝑛{30} = 30 Debe salir 𝑥1 de la base. [2 puntos]
1
III° Iteración
𝑥𝐵 = (𝑥2 𝑥3 𝑥5 ) 𝑥𝑁 = (𝑥1 𝑥4 )
𝐶𝐵 = (60 0 0) 𝐶𝑁 = (40 0)
1 1 0 2 0 70
𝐵 = [1 0 0 ] 𝑁 = [1 1] 𝑏 = [40]
3 0 −1 1 0 40
0 1 0 1 1 40
𝐵 −1 = [1 −1 0 ] 𝐵 −1 𝑁 = [1 −1] 𝑥𝐵 = [30] 𝑧 = 2.400
0 3 −1 2 3 80
Criterio de Optimalidad:
𝐶𝑁 − 𝐶𝐵 𝐵 −1 𝑁 = (−20 −60) Todos los costos reducidos son negativos. Por lo tanto, estamos
en un óptimo. [2 puntos]
Así, 𝑥1 = 0, 𝑥2 = 40, 𝑥3 = 30, 𝑥4 = 0, 𝑥5 = 80, 𝑧 = 2.400. [5 puntos]
Profesores: Pablo González Araya - Pablo González Brevis - Cristian Palma Infante
