Chapter 29, Problem 1P

(a)

Program Plan Intro

To Show if there is an algorithm for linear programming, then it can used to solve a linear-inequality feasibility problem. The number of variables and constraints that are in the linear-programming problem should be polynomial in n and m .

Explanation of Solution

The linear inequalities that are required to satisfy be the set of constraints in the linear program. Let the function to be maximized, be a constant. Linear programs solver will fail to detect the feasible solution if the linear constraints are not feasible. Suppose linear programming solver returns the solution, thenthose linear constraints are feasible.

(b)

Program Plan Intro

To Show if there is an algorithm for the linear-inequality feasibility problem, then it can be used to solve a linear-programming problem. The number of variables, linearinequalities, variable and constraint used in linear-inequality feasibility problem must be polynomial in n and m .

Explanation of Solution

To solve the linear program in standard form with some particulars such as A, b, c. That is, to maximize the equation

  ${\displaystyle \sum _{j=1}^n{c}_j}{x}_j$ subject to Ax <=b -(1)

such that all entries of x vector are non-negative. Consider the dual program, in order to minimize the equation below:

  ${\displaystyle \sum _{i=1}^{m}bi}yi$ -(2)

SubjecttoA^TY = T such that all entries in the y vector are nonzero. By Corollary 29.9 mentioned in the question, if x and y are feasible solutions to their respective problems, and if their objective functions are equal, then, the x and y optimal solutions and their objective functions should be equal. This can be achieved as, let c_k be some nonzero entry in thec vector. If there are no nonzero entries, then the function to optimize is just the zero function, and it is exactly a feasibility question. Then, add the two linear inequalities (1) and (2) to get the equation below:

  $x_k=\frac{1}{c_k}\left({\displaystyle \sum _{i=1}^m{b}_i{y}_i-}{\displaystyle \sum _{j=1}^n{c}_j{x}_j}\right)$

-(3)

The values the variables take, their objective functions will be equal. Lastly use these with the inequalities that are already present. Therefore, the constraints will be as follows:

Ax = b

A^Ty = c

  $x_k\le \frac{1}{c_k}\left({\displaystyle \sum _{i=1}^m{b}_i{y}_i-}{\displaystyle \sum _{j=1}^n{c}_j{x}_j}\right)$

  $x_k\ge \frac{1}{c_k}\left({\displaystyle \sum _{i=1}^m{b}_i{y}_i-}{\displaystyle \sum _{j=1}^n{c}_j{x}_j}\right)$

  $x_{1,}{x}_{2,}{x}_{3,}\mathrm{..........},x_{n,}{y}_1,y_{2,}\mathrm{.............},y_m\ge 0$ .

The number of variables equal to n + m and a number of constraints equal to 2 + 2n + 2m , both are polynomial in n and m . So any assignment of variables that satisfy all of constraints will be a feasible solution to the problem and its dual and the respective objective functions take the same value therefore it is an optimal solution the original problem and its dual So the linear inequality feasibility solver returns a satisfying assignment.

If there is optimal solution x , an optimal solution for the dual can be obtained such that it makes the objective functions equal by theorem 29.10 mentioned in the above question. This guarantees that the two constraints added such that that the objectives of the original problem and the dual problem should be equal do not cause to change the optimal solution to the linear program.