1
$\begingroup$

According to some tables in the book Operations Research by Hamdy Taha(7th edition), it seems that for a variable whose optimal value is zero, reduced cost can be evaluated by the following formulas:

reduced cost = MaxObjCoeff - CurrObjCoeff (for max problems)

and

reduced cost = MinObjCoeff - CurrObjCoeff (for min problems)

I should note that the interval [MinObjCoeff, MaxObjCoeff] is the optimality range of CurrObjCoeff in the graphical sensitivity analysis.

I wonder if these formulas always work? Could anyone explain this for me please?

$\endgroup$
3
  • 1
    $\begingroup$ The reduced cost can be calculated as $C_j-Z_j = C_j-C_bB^{-1}a_j$. Where $C_j$ is the current objective coefficient and $C_b$ is the objective coefficient in the basic matrix. Now, for any non-basic variables, it might be positive or negative, depending on the direction of the objective function. For example, in the minimization problem, to move a variable into the basic, it needs to have the negative reduced cost and vice versa. Would you please, say what you mean by Max or Min object coefficients? $\endgroup$
    – A.Omidi
    Aug 28, 2022 at 11:09
  • $\begingroup$ @A.Omidi The interval [MinObjCoeff, MaxObjCoeff] is the optimality range of CurrObjCoeff. $\endgroup$
    – user10291
    Aug 29, 2022 at 9:29
  • $\begingroup$ Are you sure you got those formulas correct? Given the order of subtraction, your first formula (max - current) implies a nonnegative reduced cost and your second formula implies a nonpositive reduced cost. A positive reduced cost for a nonbasic variable implies a minimization problem and a negative reduced cost implies a maximization problem, so line 1 must be for a min problem and line 2 for a max problem ... but having an upper (lower) limit on the objective coefficient of a nonbasic variable occurs in a max (min) problem, which is backwards from what you have. $\endgroup$
    – prubin
    Nov 17, 2022 at 17:24

1 Answer 1

1
$\begingroup$

As I understand suppose $z= 6x+2y-1$ then max of z would be at $x,y=(6,0)$ for x bounded by $[0,6]$ and $y=[0,3]$. Imagine z is the negative sloping line or contour in x-y plane. Slope of contour z is -3. What's the minimum amt by which coeff of y to be increased to make value of $y>0$ and increase max value of z? In other words how much slope needs to be reduced to make y a basic variable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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