0
$\begingroup$

How to prove a linear program that is feasible and bounded is maximised at one of the basic feasible solution?

$\endgroup$
  • $\begingroup$ If you have 2 variables this is easy. How many variables do you have? I guess you should change the wording of the question to something like "How to prove that a given feasible solution to maximize the objective function is one of the maximum solutions". $\endgroup$ – NoChance Sep 16 '19 at 10:32
1
$\begingroup$

See for example the textbook Linear Programming by V. Chvatal. Chvatal proves this theorem constructively. The simplex method with an appropriate anti-cycling pivot selection rule (e.g. lexicographic or Bland's rule) terminates in one of three states (1) the LP has an optimal basic feasible solution (BFS), (2) the LP is unbounded, or (3) the LP is infeasible (this is detected in phase I.)

$\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.