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

Or

reduced cost = MinObjCoeff - CurrObjCoeff

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

Improve this question
$\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

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

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

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