Solemne I - Optimización

Docente: Francisco Avilés Martínez

Nombre Estudiante:

Rut:

Puntaje:

Tiempo: 90 minutos Fecha: Jueves 08 de Septiembre de 2022

Instrucciones Generales:

La interpretación de cada problema es parte de la evaluación.

No se responderán dudas o consultas.
Escriba sus respuestas ordenadas. Se permite el uso de lápiz mina.
No se permite pedir prestado ni intercambiar ningún tipo de material de trabajo.
Se permite el uso de calculadora científica no programable.
Queda prohibido el uso del teléfono celular o dispositivos similares.
La evaluación se calificará con exigencia del 60 %. Con 59 puntos obtiene un 3.95.
Cualquier intento o evidencia de copia se calificará con nota 1.0, y se derivará a
los involucrados a los procesos institucionales correspondientes.

Compromiso de Honor

Como miembro de la comunidad de la Facultad de Ingeniería y Tecnología de la Universidad San

Sebastián, me comprometo a cumplir las normativas que la rigen y a respetar los principios de la
honestidad, justicia, respeto y responsabilidad. Asimismo, me comprometo a actuar con rectitud
y honestidad en las relaciones con los demás integrantes de la comunidad y en la realización de
todo trabajo, particularmente en aquellas actividades vinculadas a la docencia y el aprendizaje. En
particular, desde el momento que se inicie esta evaluación, me comprometo a NO realizar ningún
acto que tienda a viciarla. De no cumplir tal compromiso, acataré las medidas de sanción que se
me apliquen, según lo establecido en el Artículo 29 del Reglamento de Docencia de Pregrado de la
Universidad San Sebastián.

Firma estudiante
Problema 1 (34 pts)
CAP realiza la fabricación de dos tipo de aceros de aleación especial (A1 y A2 ), los cuales poseen
costos de fabricación de $8000/ton y $6000/ton, respectivamente. El proceso de producción posee
una etapa de acondicionamiento y otra de laminado, las cuales cuentan con una cantidad mínima
de horas que se deben ocupar. Las horas que se requieren para procesar cada ton de cada tipo de
producto, así como las horas de trabajo que debe cumplir cada etapa, se muestran a continuación:

Proceso A1 (h/ton) A2 (h/ton) Disponibilidad (h)

Acondicionamiento 4 2 68
Laminado 2 3 76

Preguntas
a) Proponga un modelo de optimización lineal que represente la situación planteada, considerando
que la cantidad de acero que se debe fabricar de cada tipo es la misma. (10 pts)

Solución:

Objetivo: Minimizar los costos de producción cumpliendo con la utilización mínima de las máqui-
nas. (1 pts)

Variables:

x1 : Cantidad de acero de baja alta calidad. (0.5 pts)

x2 : Cantidad de acero de alta calidad. (0.5 pts)

Modelo:

M in : 8000x1 + 6000x2 (1)

(1 pts)S.a : 4x1 + 2x2 ≥ 68 (2)
(1 pts) 2x1 + 3x2 ≥ 76 (3)
(1 pts) x1 = x2 (4)
(1 pts) x1 , x2 ≥ 0(1 pts) (5)

(1) Minimiza los costos relacionados a utilizar al menos el mínimo de horas requeridas por cada
máquina. Restrcciones (2) y (3) inidcan que se debe cumplir al menos con el mínimo de horas de
uso de cada máquina, mientras que (4) indica que la cantidad producida de cada acero debe ser la
misma. Finalmente (5) indica el dominio de las variables de solución. (3 pts)

b) Resuelva gráficamente el problema planteado en el apartado a). Debe señalar la región factible,
los puntos esquinas, y la solución óptima del problema. (17 pts)

1
Gráfico completo (5 pts) La solución factible del problema corresponde a la recta coloreada en ver-
de (2 pt). Si bien el problema no está acotado, al tratarse de una minimización podemos encontrar
un único punto esquina que es la solución óptima al problema. De esta forma x1 = 15,2, x2 = 15,2.
(5 pts).

Finalmente, la compañía debe producir 15.2 toneladas de acero de alta calidad y 15.2 de baja cali-
dad, obteniendo costos por un total de $212800 (5 pts).

Nota: La asignación del puntaje contempla los desarrollo intermedio.

c) Debido a acuerdos con el Departamento de control de Calidad, CAP debe producir más de 10
toneladas diarias de Acero tipo 1, ni más de 20 toneladas diarias de Acero Tipo 2.

Agregue dichas restricciones al gráfico presentado en el apartado b). (4 pts)

2pts cada reta

2
¿Cómo afecta a la solución obtenida en el apartado b) las restricciones sugeridas?. Explique
adecuadamente (no resuelva). (3 pts) Respuesta: El agregar las rectas al gráfico, la solución
no cambia, por lo que x1 = 15,2, x2 = 15,2. (3 pts)

3
Problema 2 (30 pts)
Cotrisa es una empresa comercializadora de trigo, la cual cuenta con tres almacenes en donde guarda
el trigo que se cosecha entre Enero y Febrero. Durante el resto del año, la empresa se encarga de
la venta y envío de trigo a 4 clientes. Los costos promedios de envío por tonelada ($/ton), las
demandas promedio anual de cada cliente (ton/año), así como la disponibilidad anual máxima de
cada almacén (ton/año), se resume a continuación:

Costos de envío Cliente 1 Cliente 2 Cliente 3 Cliente 4 Capacidad

Almacén 1 13 29 10 10 844
Almacén 2 10 21 27 17 889
Almacén 3 18 28 40 35 900
Demanda 54 72 53 59 -

La empresa desea estimar la cantidad de trigo que enviará anualmente a cada cliente desde cada
almacén, con el fin de minimizar los costos de transporte anual.

Preguntas
a) Proponga un modelo de optimización lineal que permita estimar la cantidad de trigo que enviará
anualmente a cada cliente desde cada almacén. (25 pts)

Objetivo: Minimizar los costos de transporte anual. (1 pt)

Variables: 6 pts

x11 : Cantidad total de trigo enviada desde el almacén 1 al cliente 1.

x12 : Cantidad total de trigo enviada desde el almacén 1 al cliente 2.

x13 : Cantidad total de trigo enviada desde el almacén 1 al cliente 3.

x14 : Cantidad total de trigo enviada desde el almacén 1 al cliente 4.

x21 : Cantidad total de trigo enviada desde el almacén 2 al cliente 1.

x22 : Cantidad total de trigo enviada desde el almacén 2 al cliente 2.

x23 : Cantidad total de trigo enviada desde el almacén 2 al cliente 3.

x24 : Cantidad total de trigo enviada desde el almacén 2 al cliente 4.

x31 : Cantidad total de trigo enviada desde el almacén 3 al cliente 1.

x32 : Cantidad total de trigo enviada desde el almacén 3 al cliente 2.

x33 : Cantidad total de trigo enviada desde el almacén 3 al cliente 3.

x34 : Cantidad total de trigo enviada desde el almacén 3 al cliente 4.

4
Modelo: (15 pts)

M in : 13x11 + 29x12 + 10x13 + 10x14 + ... + 18x31 + 28x32 + 40x33 + 35x34 (6)
s.a : x11 + x21 + x31 = 54 (7)
x12 + x22 + x32 = 72 (8)
x13 + x23 + x33 = 53 (9)
x14 + x24 + x34 = 59 (10)
x11 + x12 + x13 + x14 ≤ 844 (11)
x21 + x22 + x23 + x24 ≤ 889 (12)
x31 + x32 + x33 + x34 ≤ 900 (13)
x11 , x12 , ..., x34 ≥ 0 (14)

(6) Minimiza los costos de transporte. Restricciones (7)-(10) asegura que se atienda la totalidad de
la demanda, mientras que (11)-(13) evita que se supere la capacidad de cada almacén. Finalmente
(14) corresponden a l dominio de las variables. (4 pts)

b) ¿Es posible resolver este problema mediante método gráfico?, ¿Por qué?. (5 pts)

Respuesta: No es posible resolver el problema mediante método gráfico. Esto se debe a que dicho
método permite resolver problemas hasta tres variables (R3 ), en cambio, el problema propuesto
cuenta con doce variables (R12 ). (5 pts)

5
Problema 3 (36 pts).
Considere el siguiente problema de programación lineal:

M in z = 2x1 + 4x2 + 3x3 (15)

S.a : 2x1 + x2 + 3x3 ≤ 14 (16)
2x1 + 3x2 + 3x3 = 12 (17)
x1 + 3x2 + 2x3 ≥ 4 (18)
x1 , x2 , x3 ≥ 0 (19)

a. Plantee el problema de programación lineal en su forma estándar. (4 pts)

M in z − 2x1 − 4x2 − 3x3 − M r1 − M r2 = 0 (20)

S.a : 2x1 + x2 + 3x3 + h1 = 14 (21)
2x1 + 3x2 + 3x3 + r2 = 12 (22)
x1 + 3x2 + 2x3 + r3 − e3 = 4 (23)
x1 , x2 , x3 , r2 , r3 , e3 , h1 ≥ 0 (24)

b. Realice una iteración por el método de Big M. (8 pts)

Acomodando el sistema dado, la primera tabla apta para iterar nos queda de la siguiente
forma: (4 pts)

Luego de realizar las operaciones por filas y columnas, obtenemos la siguiente tabla: (4 pts)

6
c. Considerando la solución encontrada en el ítem anterior, ¿Cuáles son los valores de las varia-
bles básicas y no básicas encontradas?. ¿Cual es el valor de la solución actual, es factible, y
en tal caso, es óptima? (8 pts)
Acá podemos notar que la solución aún no es óptima. (2 pts) Actualmente las variables que
están en la base serían s1 = h1 = 38/3, A1 = r2 = 8, x2 = 4/3 (2 pts), obteniendo una
solución infactible de −8M + 16/3 (2 pts). Notar que la solución no es factible ya que existen
variables artificiales formando parte de la base. Las variables básicas son x1 , e3 , x3 , r3 = 0
(2 pts).
d. Plantee el problema dual asociado al modelo de programación lineal original. (7 pts)

Sean y1 , y2 , y3 las variables duales del problema, tenemos (7 pts):

M ax w = 14y1 + 12y2 + 4y3 (25)
S.a : 2y1 + 2y2 + y3 ≤ 2 (26)
y1 + 3y2 + 3y3 ≤ 4 (27)
3y1 + 3y2 + 2y2 ≤ 3 (28)
y1 ≤ 0, y2 ∈ R, y3 ≥ 0 (29)

e. En base al informe de sensibilidad que se presenta a continuación, responda las siguientes

preguntas:

7
Identifique los intervalos de factibilidad y optimalidad. ¿Que sucede si se realizan varia-
ciones fuera de dichos intervalos?. Explique cada caso. (6 pts)

Definiendo a δ1 , δ2 , δ3 como las variaciones aplicadas a R1 , R2, R3, tenemos que para
mantener la factibilidad de la soluciones encontrada, el lado derecho de cada restricción
puede variar de uno a la vez en δ1 ∈ [−2, ∞+ ], δ2 ∈ [−4, 2], δ3 ∈ [∞− , 2[. Variaciones
fuera de dichos intervalos generarán que la solución deje de ser factible. (3 pts)

Definiendo a α1 , α2 , α3 , α4 como las variaciones aplicadas a los coeficientes de las va-

riables x1 , x2 , x3 en la función objetivo, los coeficientes pueden variar de uno a la vez en
α1 ∈ [∞− , 0], α2 ∈] − 1, ∞+ ], α3 ∈]0, ∞+ ], manteniendo la optimalidad de la solución.
Variaciones fuera de dichos intervalos generarán que la solución deje de ser óptima. (3
pts)

En el óptimo, ¿Cuál es el valor de las variables duales asociadas a la pregunta b?. (3 pts)

Los valores de las variables duales son: y1 = 0, y2 = 1, y3 = 0. (3 pts)