0

Let us say that we have a linear program $P=\{ \min C^tx \mid Ax=b,x\geq0\}$
Assume that $(P)$ has an optimal solution. Write a system of linear equations and inequalities $(P_1)$ such that any feasible solution to $(P_1)$ gives us an optimal solution to $(P)$.

What I thought: I just added the complementary slackness condition along with the dual constraints to the primal constraints and solve it, as it will satisfy:

1.Primal feasibility
2.Dual feasibility
3.Complementary slackness
Hence will get the optimal solution as a feasible solution to the Linear program
but Later I noticed that if I include complementary slackness the constraints are non-linear. So any suggestion?

Kuzja
  • 450
  • 4
  • 12
onlymath
  • 158
  • 10
  • If you have primal and dual feasibility then complementary slackness is equivalent to the statement that primal and dual objective values are equal. – Michal Adamaszek Nov 14 '19 at 11:27
  • but for optimallity dont we need the complementery slackness. – onlymath Nov 14 '19 at 11:36
  • 1
    https://math.stackexchange.com/questions/3370732/finding-an-optimal-solution-to-a-linear-program-among-solutions-of-another – Kuifje Nov 14 '19 at 12:56

0 Answers0