Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have difficulty to understand its output.

Here is the problem:

max 2x + 3y
s.t.
4x + 3y <= 10
3x + 5y < 12
end

I get this output:

 LP OPTIMUM FOUND AT STEP      2

        OBJECTIVE FUNCTION VALUE

        1)      7.454545

  VARIABLE        VALUE          REDUCED COST
         X         1.272727          0.000000
         Y         1.636364          0.000000


       ROW   SLACK OR SURPLUS     DUAL PRICES
        2)         0.000000          0.090909
        3)         0.000000          0.545455

 NO. ITERATIONS=       2


 RANGES IN WHICH THE BASIS IS UNCHANGED:

                           OBJ COEFFICIENT RANGES
 VARIABLE         CURRENT        ALLOWABLE        ALLOWABLE
                   COEF          INCREASE         DECREASE
        X        2.000000         2.000000         0.200000
        Y        3.000000         0.333333         1.500000

                           RIGHTHAND SIDE RANGES
      ROW         CURRENT        ALLOWABLE        ALLOWABLE
                    RHS          INCREASE         DECREASE
        2       10.000000         6.000000         2.800000
        3       12.000000         4.666667         4.500000
  • what do DUAL PRICES mean?
  • what do CURRENT COEF, ALLOWABLE INCREASE, ALLOWABLE DECREASE mean?
  • what is OBJ COEFFICIENT RANGES?
  • what are CURRENT RHS, ALLOWABLE INCREASE , ALLOWABLE DECREASE ?
share|improve this question
add comment

1 Answer

up vote 2 down vote accepted
  1. Dual prices: These tell you how much your optimal objective function value would increase per unit increase in the right-hand side values. For example, your first constraint is $4x + 3y \leq 10$. The corresponding dual price is $0.\overline{09} = 1/11.$ This means that if you were to increase the $10$ on the right-hand side by one unit to $11$, then your optimal objective function value would increase from $7.\overline{45} = 7 \, \frac{5}{11}$ to $7 \, \frac{6}{11}$. The allowable increases and allowable decreases for the right-hand side ranges (see point 4 below) tell you how much you can change the right-hand sides and still have these dual prices remain valid.
  2. Current coefficient, allowable increase, allowable decrease: Right now your optimal solution is $x = \frac{14}{11}$, $y = \frac{18}{11}$ with no slack at all on your two constraints. This defines a basis for your optimal solution. Without going too deeply into the underlying linear algebra or diving into issues of degeneracy, the optimal basis is essentially that $x$ and $y$ are nonzero and there is no slack on the two constraints. In other words, you can find the optimal solution by assuming the inequality constraints are actually equalities and then solving the system to figure out what $x$ and $y$ have to be. The current coefficients for $x$ and $y$ are $2$ and $3$ because your objective function is $2x + 3y$. The allowable increase and allowable decrease tell you how much you could change the $2$ and $3$ without changing the structure of the optimal solution (i.e., this method I just described for finding the optimal solution). For example, the allowable increase and allowable decrease on the $x$ coefficient are $2$ and $0.2$, respectively. This means that you could drop the objective coefficient for $x$ down to $1.8$ or increase it to $4$ without changing the method for finding the optimal solution (i.e., setting the inequalities to equalities and then solving the system for $x$ and $y$). If the objective coefficient on $x$ were to be larger than $4$, then $x$ would become sufficiently valuable in the optimal solution so that the structure of the optimal solution would actually change. (Again, there's some linear algebra going on underneath the hood here.)
  3. Objective coefficient ranges: I pretty much answered this in the previous paragraph.
  4. Current right-hand side, allowable increase, and allowable decrease: The current right-hand side refers to the right-hand side values of the two constraints. Since the two constraints are $4x+3y \leq 10$ and $3x + 5y \leq 12$ these are $10$ and $12$. The allowable increase and allowable decrease refer to the same thing as in the second paragraph but now with respect to the right-hand sides rather than the objective coefficients. For example, since the allowable increase and allowable decrease for the first constraint are $6$ and $2.8$, respectively, you could change the first constraint's right-hand side down to $7.2$ or up to $16$ without changing the structure of the optimal solution (i.e., that it can be found by changing the inequalities to equalities and solving for $x$ and $y$).
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.