C++: Einführung und professionelle Programmierung by Ulrich Breymann

Show description

Then there exists x* such that X* > 0 and Ax* > b. 49) we find that x* + x > 0 and A(x* + x) > 6. So x* + x is feasible for (P). We can not have b^y > 0, because this would lead to the contradiction 0 0 and A^y < 0. Hence we have b^y < 0. 50) this implies c^x < 0. But then we have for any positive A that x* + Xx is feasible for (P) and c"^(x* + Xx) = c"^x* + Xc^x, showing that the objective value goes to minus infinity if A grows to infinity. Thus we have shown that (P) is either infeasible or unbounded, and hence (P) has no optimal solution.

A popular approach in textbooks to this theory is constructive. It is based on the Simplex Method. While solving a problem by this method, at each iterative step the method generates so^ The first duality results in LO were obtained in a nonconstructive way. They can be derived from some variants of Farkas' lemma [75], or from more general separation theorems for convex sets. , Osborne [229] and Saigal [249]. An alternative approach is based on direct inductive proofs of theorems of Farkas, Weyl and Minkowski and derives the duality results for LO as a corollary of these theorems.

6) is the zero vector, this system is homogeneous: whenever {y^x^n) solves t h e system then \{y^x^n) also solves t h e system, for any positive A. 5). 6) has n = 0. 5) cannot have a solution in t h a t case. Evidently, we can work with t h e second system without loss of information about the solution set of t h e first system. 7) n where we omitted the size indices of the zero blocks, we have reduced the problem of finding optimal solutions for (P) and {D) with vanishing duality gap to finding a solution of the inequality system Mz > 0, z > 0, n>{).