1
$\begingroup$

I'm new in this Stack exchange,a friend of mine and I are using the lindo, to solve this LP problem:

$$ \begin{align*} \max z= 18x_{11}+18x_{12}+20x_{21}+20x_{22}-6x_{41}-10x_{51}-4x_{61}-4x_{42}-10x_{52}-7x_{62} \\ \textrm{Subject to:} \\ x_{41}+x_{51}+x_{61}&\leq 200 \\ x_{41}-0.2x_{11}-0.3x_{21}&\geq 0 \\ x_{51}-0.3x_{11}-0.4x_{21}&\geq 0 \\ x_{61}-0.1x_{11}-0.1x_{21}&\geq 0 \\ x_{41}-0.6x_{11}-0.8x_{21}+x_{51}+x_{61}+x_{42}+x_{52}+x_{62}&\leq 200 \\ x_{41}+x_{42}-0.2x_{11}-0.2x_{12}-0.3x_{21}-0.3x_{22}&\geq 0 \\ x_{51}+x_{52}-0.3x_{11}-0.4x_{21}-0.3x_{12}-0.4x_{22}&\geq 0 \\ x_{62}+x_{61}-0.1x_{11}-0.1x_{21}-0.1x_{12}-0.1x_{22}&\geq 0 \\ x_{11}&\geq 5 \\ x_{21}&\geq 8 \\ x_{12}&\geq 5 \\ x_{22}&\geq 8 \\ \end{align*} $$

And we were able to solve it as you can see by the following:


LP OPTIMUM FOUND AT STEP 13

    OBJECTIVE FUNCTION VALUE  1)      11312.53



VARIABLE        VALUE          REDUCED COST
   X11       322.666656          0.000000
   X12       322.666656          0.000000
   X21         8.000000          0.000000
   X22         8.000000          0.000000
   X41        66.933334          0.000000
   X51       100.000000          0.000000
   X61        33.066666          0.000000
   X42        66.933334          0.000000
   X52       100.000000          0.000000
   X62        33.066666          0.000000


   ROW   SLACK OR SURPLUS     DUAL PRICES
    2)         0.000000         34.333332
    3)         0.000000         -0.333333
    4)         0.000000        -34.333332
    5)         0.000000        -31.333334
    6)         0.000000         22.500000
    7)         0.000000        -26.500000
    8)         0.000000        -32.500000
    9)         0.000000        -29.500000
   10)       317.666656          0.000000
   11)         0.000000         -2.866667
   12)       317.666656          0.000000
   13)         0.000000         -3.900000

Our dual problem : ##

$$ \begin{align*} \min z= 200y_{2}+200y_{6}+5y_{10}+8y_{11}+5y_{12}+8y_{13} \\ \textrm{Subject to:} \\ -0.2y_{3}-0.3y_{4}-0.1y_{5}-0.6y_{6}-0.2y_{7}-0.3y_{8}-0.1y_{9}+y_{10}&\geq 18 \\ -0.2y_{7}-0.3y_{8}-0.1y_{9}+y_{12}&\geq 18 \\ -0.3y_{3}-0.4y_{4}-0.1y_{5}-0.8y_{6}-0.3y_{7}-0.4y_{8}-0.1y_{9}+y_{11}&\geq 20 \\ -0.3y_{7}-0.4y_{8}-0.1y_{9}+y_{13}&\geq 20 \\ y_{2}+y_{3}+y_{6}+y_{7}&\geq -6 \\ y_{2}+y_{4}+y_{6}+y_{8}&\geq -10 \\ y_{2}+y_{5}+y_{6}+y_{9}&\geq -4 \\ y_{6}+y_{7}&\geq -4 \\ y_{6}+y_{8}&\geq -10 \\ y_{6}+y_{9}&\geq -7 \\ y_{2}&\geq 0 \\ y_{3}&\leq 0 \\ y_{4}&\leq 0 \\ y_{5}&\leq 0 \\ y_{6}&\geq 0 \\ y_{7}&\leq 0 \\ y_{8}&\leq 0 \\ y_{9}&\leq 0 \\ y_{10}&\leq 0 \\ y_{11}&\leq 0 \\ y_{12}&\leq 0 \\ y_{13}&\leq 0 \end{align*} $$

Once we are running it on the lindo solver, we are getting the answer that our problem is infeasible. The primal and the dual solutions have the same value. Is this possible?

Do we need to redefine our dual problem to make it feasible?

$\endgroup$
  • $\begingroup$ The dual problem is not correctly formulated. Bear in mind $\leq$ and $\geq$ are not the same. Make it consistent. $\endgroup$ – Jane Maths Jan 6 '17 at 12:30
  • $\begingroup$ Hey Jane, thanks for the quick respone. I overviewd the signs in this case and at similar examples again, but i couldn't find whats wrong . Can you please go into details? $\endgroup$ – Itai Meirovitz Jan 6 '17 at 15:00

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.