0

I have an interesting question which I need to solve. When we are given linear programing problem and we want to use Simplex method to find the basic feasible and optimal solution of the problem, we need to find some basis, so that we can find basic feasible solution, but if we can't find the basis from the first sight, we need to solve the auxiliary linear program problem with given formulation as: $$\xi = \sum_{i=1}^m p_i → min$$ with constraints: $$\sum_{j=1}^n a_jx_j+p_i = b_i$$ for i = 1,2,...,m and conditions: $x_j>=0$ for j=1,2,...,n; and $p_i>=0$ for i=1,2,...,m where m is the number of rows (constraints), n is the number of columns(variables from original linear problem) and for every i=1,2,...,m the variable $p_i$ is artificial variables (for which we know that if all of them are equal to zero then the original problem has feasible solution, because objective function $\xi$ equals zero. The question is: How do we prove that the auxiliary problem always has optimal (so also feasible) solution? What I know is that we can use the fundamental theorem of linear programming and the formulation of given auxiliary program but how, because it seems that this auxiliary program is not unbounded (because the objective function is bounded from below by zero) and there are still two cases left: if the problem is infeasible or of it has optimal solution at some corner point, and what I just need is to show that this problem is always feasible (so that we automatically know, that tihs problem is always the case of optimal solution). Thanks for help.

Zam
  • 17
  • ...well, how do you always begin solving the auxiliary problem? – Misha Lavrov Oct 05 '23 at 18:16
  • I will create the same simplex table as for the normal case, where I can see the basis , and as usually I am looking for the column with negative cost and the row with lowest ratio so that I will find the pivot, and I will use the equivalent row opertaions and test the optimality – Zam Oct 05 '23 at 18:24
  • and of course we put coefficients of the new objective function (the sum of artificial variables) to the 0th row (the row were we later get the relative costs) – Zam Oct 05 '23 at 18:37
  • 1
    Well, if you can see the basis, then you can see the basic solution, so you know it's feasible! Your simplex table tells you a basic solution – Misha Lavrov Oct 05 '23 at 18:52
  • Okay, so because the artificial variables we added are forming a basis, and because the right side (vector of b) is nonegative and we choose the basic solution (which corresponds to basis formed of the artificial variables columns) and since these are linearly independent, then the determinant of the matrix formed from these basis vectors is nonzero so the matrix is regullar (nonsingular) and so it has eaxtly one solution) is it a good argument ? – Zam Oct 05 '23 at 19:14
  • and because it has a feasible solution the the case of fundamental theorem where the set is infeasible do not take, so the only one left option is the optimal solution – Zam Oct 05 '23 at 19:18

0 Answers0