Maximize Profits with Duality Theory: Optimal Solution for Standard Form Problem

[pinki82]

Consider a PRoblem in standard form;
Max { Sum of (c_j * x_j) }
Sum of (a_i,j * x_j) <= b_i , i = 1,...,m
x_j >= 0 , j= 1,...,n

Assume that x* = (x*_1,...x*_n ) is an optimal solution to this
problem and that the first constraint is not satisfied at equality
i.e. Sum of (a_1,j * x*_j) < b_1.

Show using Duality Theory, that x* is also an optimal solution for the
problem obtained by deleting the first constraint i.e. the problem
Maximize Sum of (c_j * x_j)

s.t. Sum of (a_i,j * x_j) <= b_i , i= 2,...,m
x_j >= 0

note: Sum of sign has n on the top and j=1 on the bottom
>= means > or equal to..
<= means < or equal to...

any hint or help please.thanks


WORK DONE :

I understnad what the optimal solution is...but not quite sure what
duality theory is..

 

[lippyka]

can you help me out with that too?ANSWER:Duality theory is a way to examine the relationships between different optimization problems. It is based on the idea of duality, which states that two seemingly unrelated problems actually share a strong link. Duality theory can be used to determine whether an optimal solution for one problem is also an optimal solution for another problem. In this case, the two problems are the original problem with the first constraint and the problem obtained by deleting the first constraint. Applying duality theory, we can prove that the x* is an optimal solution for both problems. Let y denote the Lagrange multipliers for the constraints in the original problem. Let y1 denote the Lagrange multiplier for the first constraint, and let y2 denote the Lagrange multipliers for the remaining constraints. Since x* is an optimal solution for the original problem, the following conditions must hold: 1. Sum of (c_j * x*_j) - y1 * (Sum of (a_1,j * x*_j) - b_1) - Sum of (y2_i * (Sum of (a_i,j * x*_j) - b_i)) >= 0 , i= 2,...,m 2. y1, y2_i >= 0, i= 2,...,m We can rewrite the first condition as follows: Sum of (c_j * x*_j) - y1 * (Sum of (a_1,j * x*_j)) - Sum of (y2_i * (Sum of (a_i,j * x*_j))) - (y1 * b_1 + Sum of (y2_i * b_i)) >= 0 Since the first constraint is not satisfied at equality (Sum of (a_1,j * x*_j) < b_1), we have y1 > 0. This implies that the left hand side of the above equation is strictly greater than zero. Therefore, the only way to satisfy the equation is to make the right hand side equal to zero. This can be achieved by setting y1 = 0 and y2_i = 0, i=