1a questão (2,5 pontos) Considere o problema de otimização linear abaixo:
Min 5𝑥 + 12𝑥 + 9𝑥 + 3𝑥
tal que 𝑥 + 𝑥 + 3𝑥 − 𝑥 ≥ 2
𝑥 + 3𝑥 − 𝑥 + 𝑥 ≥ 1
𝑥 ≥ 0, 𝑥 ≥ 0, 𝑥 ≥ 0, 𝑥 ≥ 0, 𝑥 ≥ 0
a) Escreva a forma dual do problema.
b) Desenhe o domínio viável e o gradiente da função objetivo do problema dual.
c) Determine graficamente o ponto ótimo do problema dual.
d) Encontre a solução do problema original.
视频信息
答案文本
视频字幕
We have a linear programming minimization problem with four variables and two constraints. The objective is to minimize 5x₁ + 12x₂ + 9x₃ + 3x₄, subject to two greater-than-or-equal-to constraints and non-negativity conditions. This is our primal problem that we need to solve using duality theory.
To formulate the dual problem, we use the duality rules. Since our primal is a minimization problem with greater-than-or-equal-to constraints, the dual becomes a maximization problem. We introduce dual variables y₁ and y₂ corresponding to the two primal constraints. The dual objective coefficients are the right-hand sides of primal constraints: 2 and 1. The dual constraints are formed by transposing the primal constraint matrix.
Now we visualize the dual problem graphically. The feasible region is bounded by the constraint inequalities in the first quadrant. The shaded polygon represents all feasible solutions. The gradient vector of the objective function W equals 2y₁ plus y₂ points in direction (2,1), showing the direction of steepest increase. To find the optimal solution, we move in this direction until we reach the boundary of the feasible region.
To find the optimal solution graphically, we evaluate the objective function at each vertex of the feasible region. The vertices are at coordinates (0,0), (0,3), (0.75,3.75), (1.5,3.5), (3.5,1.5), and (3,0). Computing W equals 2y₁ plus y₂ at each vertex, we get values 0, 3, 5.25, 6.5, 8.5, and 6 respectively. The maximum value of 8.5 occurs at point (3.5, 1.5), which is our optimal dual solution.
Using complementary slackness conditions, we find the primal optimal solution. Since both dual variables are positive, both primal constraints are active. The active dual constraints tell us which primal variables are non-zero: x₁ and x₃. Setting x₂ and x₄ to zero, we solve the system: x₁ plus 3x₃ equals 2, and x₁ minus x₃ equals 1. This gives us x₃ equals 0.25 and x₁ equals 1.25. The optimal primal solution is (1.25, 0, 0.25, 0) with objective value 8.5, confirming strong duality.