I have a Linear Program with constrains of the form:

$$a_{11}x_1+a_{12}x_2+\ldots\le 0$$

$$a_{21}x_1+a_{22}x_2+\ldots\le 0$$

$$a_{31}x_1+a_{32}x_2+\ldots\le 0$$

My problem is that if I try to implement simplex I have problems in the tableau because every ratio is $0$. How can I face this problem? Is it possible to add a constant say $b$ to every constrain and also to the objective function?

  • 2
    $\begingroup$ I don't see where your problem is. You start with $(0,...,0)$ as a solution. In the objective function, you'll try to increase the variables whose coefficient is positive, and the maximum you will be able to increase them is $0$. So you'll do some pivots, eventually reaching a point where the objective function is expressed only with non-positive coefficients of the variables, thus terminating the algorithm. Isn't it this way that your algorithm works? $\endgroup$ – zarathustra Apr 29 '13 at 14:59
  • $\begingroup$ But whatever move I do since the right size is 0 the objective function remains zero for ever.... For example I select x1 to enter the Basis. I do the usual row operations to the constrains and to the objective. But the objective will remain 0 because the ratio in the constrains will be 0. So I am stuck and I am not able to increase the objective. If it wasn't zero, the ratio would be positive and increase my function. $\endgroup$ – nikosdi Apr 29 '13 at 15:03
  • $\begingroup$ I guess that either you program is unbounded, either it's maximum value is 0. If you make sure that your algorithm deals with unbounded polytopes, there is no harm, right? $\endgroup$ – zarathustra Apr 29 '13 at 15:15
  • $\begingroup$ Thank you for your response.My thought was also that my program was unbounded. I solved it using an online applet and no solution... Then I solved it on maple with simplex and returned me a solution.A solution better than my solution. My coefficients were all negative so I couldn't increase it. And I was stuck in the initial basic feasible solution. In general suppose I want to solve suck a system with the usual tableau the ratio should't be always 0? How the objective can be increased? $\endgroup$ – nikosdi Apr 29 '13 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.