Solving these problems using the MODI(Modified Distribution Method). Whenever the opportunity costs of all the unallocated cells are zero or negative, you have reached an optimal solution. If all are negative, you have a unique solution. But if you have no positives, but one or more zeros, it means you have a problem with multiple optimal solutions. However, how do you figure out how many optimal solutions to search for - from solving a few problems, I see that you have 2 solutions per zero. Is this correct - i.e. if I have 'n' zeros, I should search for 2n optimal solutions?

asked 17 May '12, 08:55

Gen's gravatar image

accept rate: 0%

First, as soon as you have two optimal solutions, you have an uncountably infinite number. So you want to ask about optimal extreme points.

Second, it's possible for the problem to be degenerate, in which case zero reduced costs may or may not point to the existence of alternative optima. You could wind up with alternative bases for the same optimal solution.


answered 17 May '12, 18:30

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

What's an optimal extreme point?

(17 May '12, 23:11) Gen

The feasible region for a transportation problem is a polyhedron. An extreme point is a corner of the polyhedron (so optimal extreme point = optimal corner). If two corners are optimal, all the points between them are as well. If your polyhedron lives in (Re^d), you need (d) binding constraints (counting bounds on variables as constraints) to define a corner; if you have more than (d) binding constraints, the corner is degenerate.

(18 May '12, 08:26) Paul Rubin ♦♦

let me first give you a hint: if you know linear programming then you could formulate the transportation problem as a linear program. your optimality conditions are LP optimality conditions. then ask your question again, how many optimal basic solutions there could be, depending on the number of zero reduced cost coefficients.


answered 17 May '12, 09:12

Marco%20Luebbecke's gravatar image

Marco Luebbecke ♦
accept rate: 16%

In LPP, there are multiple optimum solutions if one of non-basis vars has a 0 value in the delta-j row. However, even here is there a way to tell how many optimum solutions are there?

(18 May '12, 23:50) Gen

from the number of 0 values you cannot tell. there may be only one optimal extreme point (when the solution is degenerate) or all extreme points could be optimal (when the objective function is constant).

(19 May '12, 06:06) Marco Luebbecke ♦

You can't easily know how many basic optimal solutions there are, but you can write a description of the polyhedron with those solutions as corner points. Start with an optimal basis. Fix nonbasic variables with nonzero reduced costs to their bound values and consolidate the fixed columns on the RHS. The remaining system consists of basic variables (whose reduced costs are zero) and nonbasic variables whose reduced costs are zero. The feasible solutions to that system are all optimal to the original problem. Enumerating the extreme points of that object might be expensive, though.

(20 May '12, 04:32) Matthew Salt... ♦
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 17 May '12, 08:55

Seen: 10,595 times

Last updated: 20 May '12, 04:32

OR-Exchange! Your site for questions, answers, and announcements about operations research.