0
$\begingroup$

I only see people deal with linear programming by converting it to standard form and solve using simplex algorithm.

My question is why we stay focused on equality constraints rather than inequality ones while tackling linear programming?

$\endgroup$
  • $\begingroup$ We can transform a problem having inequality-constraints to one which only has equality-constraints, except the inequalities that ensure the variables to be non-negative. $\endgroup$ – Peter Jan 22 '19 at 13:39
1
$\begingroup$

Because the proof that the simplex algorithm works relies on having equalities. Any inequalities can be turned into equalities by adding extra variables, so this is no big deal. An interesting point, however, is that the inequalities are still kind of there. We still require $x_i\geq0$ for all $i$. So you can say we only simplified the inequalities, at the cost of adding variables. However, this is still exactly what the simplex algorithm is designed to solve.

$\endgroup$
0
$\begingroup$

The solution is known to occur at a vertex of the domain. The vertices are in a finite number and this is where the search focuses.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.