Scribd
Cargar
7 vistas2 páginas

Optimización Lineal: Problemas y Soluciones

El documento presenta la formulación de problemas de optimización lineal, incluyendo la formulación de problemas duales y la identificación de vértices óptimos en función de un parámetro desconocido. Se discuten soluciones óptimas para diferentes valores de este parámetro y se analiza la sensibilidad de la solución ante cambios en los recursos disponibles. Además, se aborda la relación entre variables adicionales y la no acotación del problema.

Cargado por

Juan Vega
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
7 vistas2 páginas

Optimización Lineal: Problemas y Soluciones

El documento presenta la formulación de problemas de optimización lineal, incluyendo la formulación de problemas duales y la identificación de vértices óptimos en función de un parámetro desconocido. Se discuten soluciones óptimas para diferentes valores de este parámetro y se analiza la sensibilidad de la solución ante cambios en los recursos disponibles. Además, se aborda la relación entre variables adicionales y la no acotación del problema.

Cargado por

Juan Vega
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

Solución

(a) El problema dual (D) es:


n
X
(D) mı́n λ · W + yi
i=1
s.a λ · wi + y i ≥ v i ∀i ∈ {1, . . . , n}
λ ≥ 0, yi ≥ 0 ∀i ∈ {1, . . . , n}

(b) Es posible omitir la cota superior, puesto que esta viene implı́cita en las restricciones de asignación.
Obteniendo el siguiente problema dual (D) es:
n
X n
X
(D) máx ui + vj
i=1 j=1
s.a ui + vj ≤ cij ∀i, j{1, · · · , n}

Problema 6.4. [Ex 2021-2]


Considere el siguiente modelo de optimización lineal con variables continuas:
(P ) z(α) := mı́n 2x1 + 3x2 + 4x3
s.a x1 + x2 ≥ 2
x2 + x3 ≥ α
x1 , x2 , x3 ≥ 0

donde α ∈ R es un parámetro desconocido y z(α) es su valor óptimo como función de α.

(a) Formule el problema dual de (P ) y llámelo (D).


(b) Determine (como usted estime conveniente) todos los vértices de (D). Luego identifique para qué rango de
valores de α ∈ R es óptimo cada vértice encontrado.
(c) Determine explı́citamente la función valor óptimo z(α) en función de α ∈ R.
(d) Obtenga la solución óptima de (P ) para cada valor entero de α ∈ Z.

Solución

(a) El problema dual (D) es:

(D) máx 2y1 + αy2


s.a y1 ≤ 2
y1 + y2 ≤ 3
y2 ≤ 4
y1 , y2 ≥ 0

73
(b) Los vértices del dominio (D) son:

(0, 0) activa las dos no negatividades, y nunca será solución óptima.


(2, 0) activa la restricción 1 y la no negatividad, será solución óptima para α ≤ 0.
(2, 1) activa la restricción 1 y 2. Será solución óptima para 0 ≤ α ≤ 2.
(0, 3) activa una no negatividad y la segunda restricción. Será solución óptima para α ≥ 2.

(c) Por dualidad fuerte y sabiendo que el óptimo se da en un vértice de (D) para cada valor de α, se obtiene
que: 
4
 si α ≤ 0
z(α) = 4 + α si 0 ≤ α ≤ 2

3·α si α > 2

(d) Utilizando el teorema de holguras complementarias, se obtiene que:

Si α ∈ {0, −1, −2, −3, . . . }, (2, 0, 0) es solución primal óptima.


Si α = 1, (1, 1, 0) es solución primal óptima
Si α = {2, 3, . . . }, (0, α, 0) es solución primal óptima.

Problema 6.5. [I2 2020-2]


Considere el siguiente problema con dos restricciones, la primera para el recurso A (8 unidades) y la segunda para
el recurso B (10 unidades). La solución óptima es (22/5, 0, 6/5, 0):

(P ) máx 2x1 + x2 + 3x3 + x4


s.a x1 + 2x2 + 3x3 + 3x4 ≤ 8 (R1)
2x1 + 4x2 + x3 + 2x4 ≤ 10 (R2)
x1 , x2 , x3 , x4 ≥ 0 (NV)

(a) Asuma que una unidad del recurso A tiene el mismo costo que una del recurso B. Si pudiese aumentar en una
unidad uno de los dos recursos, ¿cuál escogerı́a? ¿Cuál es el valor máximo que estarı́a dispuesto a pagar por
una unidad de dicho recurso?
(b) Si el modelo es modificado, incorporando las variables x5 y x6 , determine la relación de valores entre α y β
para que el problema sea no acotado.
(Pc ) máx 2x1 + x2 + 3x3 + x4 + αx5 + βx6
s.a x1 + 2x2 + 3x3 + 3x4 + 3x5 − 6x6 ≤ 8 (R1)
2x1 + 4x2 + x3 + 2x4 − 2x5 + 4x6 ≤ 10 (R2)
x1 , x2 , x3 , x4 ≥ 0 (NV)
x5 ∈ R
x6 ≤ 0

Solución

(a) Debemos obtener el precio sombra de ambos recursos y elegir el más grande, dado que tendrá un mayor

74

También podría gustarte