This is about Vogel's Approximation Method in Transportation Problems. Whenever a particular allocation fully satisfies the row or columns supply or demand, you cross out the row/column fully because it will not take part in the remaining allocations.

Sometimes a particular allocation can satisty both the row's supply and the column's demand - if the row's remaining supply & column's remaining demand at that point is the same. In this case, most books cross out both the row and column. However, the book by 'Hamdy Taha' says that you should cross out one or the other but not both. I tried solving a few problems either way, but it doesn't seem make a difference. Is there an example where it could make a difference?

asked 17 May '12, 08:50

Gen's gravatar image

Gen
172310
accept rate: 0%


I believe that you give the answer yourself: "Whenever a particular allocation fully satisfies the row or columns supply or demand [...] it will not take part in the remaining allocations." So, in terms of solutions quality (objective function value) this cannot make a difference.

edit: removed my comment about different allocations.

link

answered 17 May '12, 09:18

Marco%20Luebbecke's gravatar image

Marco Luebbecke ♦
3.4k1615
accept rate: 16%

edited 17 May '12, 11:11

I am not able to figure out how crossing out just one or both will lead to different allocations. I tried it out in a few problems and I got the same allocations.

(17 May '12, 10:19) Gen
4

Crossing out or not crossing out a cell with an allocation of zero won't change allocations. It does matter, though, because when you transition to the transportation simplex phase II, you need a set of cells that forms a basis. That is, n+m-1 cells such that every row and every column has a basic cell and only basic cells carry flow. A basic cell can carry zero flow, but it together with the others must satisfy the structural requirements for a basis.

(17 May '12, 15:06) Matthew Salt... ♦

What is transportation simplex phase 2? I don't use simplex here at all.

How I solve this problem is - First obtain a basic feasible solution (Vogel's App Method) - Use Modified Distribution Method(MODI) to refine the solution from a feasible solution to an optimal solution.

So will crossing out one or both make a difference here?

(17 May '12, 23:10) Gen
Your answer
toggle preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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

Tags:

×9

Asked: 17 May '12, 08:50

Seen: 4,341 times

Last updated: 17 May '12, 23:10

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