Question

In: Advanced Math

Prove that if the primal minimisation problem is unbounded then the dual maximisation problem is infeasible.

  1. Prove that if the primal minimisation problem is unbounded then the dual maximisation

    problem is infeasible.

Solutions

Expert Solution

Suppose this is not the case, so that the dual maximization problem

is feasible, but the primal minimization problem

is unbounded.

Fix a feasible solution to the dual problem. Then , so that for all we have

Since the primal problem is unbounded, for every there is such that and . But then, from we get

However, recall that is a fixed vector, and is a fixed feasible solution to the dual. Therefore, is a real constant. Thus, the above shows that for every we have , a constant; this is absurd.

Therefore, the dual problem must be infeasible.

Colby Messinger answered 1 year ago
Next > < Previous

Related Solutions

Write the dual maximization problem, and then solve both the primal and dual problems with the...
Write the dual maximization problem, and then solve both the primal and dual problems with the simplex method. (For the dual problem, use x1, x2, and x3 as the variables and f as the function.) Minimize g = 6y1 + 28y2 subject to 2y1 + y2 ≥ 14 y1 + 3y2 ≥ 14 y1 + 4y2 ≥ 17 . primal g = primal y1 = primal y2 = dual f = dual x1 = dual x2 = dual x3 =
Determine whether the following linear optimization problem is infeasible, unbounded, or has multiple optimal solutions. Draw...
Determine whether the following linear optimization problem is infeasible, unbounded, or has multiple optimal solutions. Draw a graph and explain your conclusion. Maximize 20x + 50y Subject to -3x + 4y < 120 2x + 3y > 180 x, y > 0
Determine whether the following linear optimization problem is infeasible, unbounded, or has multiple optimal solutions. Draw...
Determine whether the following linear optimization problem is infeasible, unbounded, or has multiple optimal solutions. Draw a graph and explain your conclusion. Maximize 20x + 50y Subject to -3x + 4y < 120 2x + 3y > 180 x, y > 0
Use the simplex method to determine whether the following LOP is optimal, unbounded, or infeasible. Maximize...
Use the simplex method to determine whether the following LOP is optimal, unbounded, or infeasible. Maximize z = x1 − x2 Subject to 2x1 − x2 = −5 x1 − 2x2 ≤ 3 −x1 + x2 ≤ −1 and x1 ≥ 0.
Find the dual problem for each of the following primal problems. a): min z=6x1+8x2 st: 3x1+x2>=4...
Find the dual problem for each of the following primal problems. a): min z=6x1+8x2 st: 3x1+x2>=4 5x1+2x2>=7 x1,x2>=0 b): max z=8x1+3x2-2x3 st: x1-6x2+x3>=2 5x1+7x2-2x3=-4 x1<=0,x2<=0,x3 unrestricted
Prove that the dual space of l^1 is l^infinity
Prove that the dual space of l^1 is l^infinity
Prove the trace of an n x n matrix is an element of the dual space...
Prove the trace of an n x n matrix is an element of the dual space of all n x n matrices.
A primal maximization problem is given. Maximize f = 60x1 + 30x2 subject to 3x1 +...
A primal maximization problem is given. Maximize f = 60x1 + 30x2 subject to 3x1 + 2x2 ≤ 150 x1 + x2 ≤ 70 . (a) Form the dual minimization problem. (Use y1 and y2 as the variables and g as the function.) Minimize g =     subject to    ≥ 60    ≥ 30 y1, y2 ≥ 0 . (b) Solve both the primal and dual problems with the simplex method. primal     x1 = primal     x2 = primal     f =...
A primal maximization problem is given. Maximize f = 20x1 + 10x2 subject to 3x1 +...
A primal maximization problem is given. Maximize f = 20x1 + 10x2 subject to 3x1 + 2x2 ≤ 90 x1 + x2 ≤ 40 . (a) Form the dual minimization problem. (Use y1 and y2 as the variables and g as the function.) Minimize g = subject to = (b) Solve both the primal and dual problems with the simplex method. primal     x1 = primal     x2 = primal     f = dual     y1 = dual     y2 = dual     g =
Prove If C is a binary self-dual  code, show that every codeword has even weight. Furthermore, prove...
Prove If C is a binary self-dual  code, show that every codeword has even weight. Furthermore, prove if each row of the generator matrix of C has weight divisible by 4, then so does every codeword.
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT