. "Избор на минималния размер на клетките и максималния възможен брой на пълнеж, изгорелите газове или запаси или нужди (се заличава ред или колона) се избира следващата клетка с минималния размер и т.н.

в) метод Vogel приближение.

За да се запълни всяка клетка трябва да се намери разликата между минималните ставки за всички колони и редове, да ги запишете, съответно, по-долу и в дясно на масата. Сред констатираните разлики в избора на максимум. Редът (или колона), която съответства на тази разлика, клетката е запълнена с минимална скорост. Ако максималната разлика в някои от едни и същи, изберете този, който отговаря на минималната тарифа. Ако минималната скорост е същата за брой клетки в един ред (колона), след запълване на този, който стои в колона (линия) с най-голямата разлика между двете минималните цени.

Обикновено, когато изграждане на програма за подпомагане на тези три метода следното равенство: FB (х) FB (х) Fa (х).

1. Изграждане на план подкрепа за един от методите.

програма Застроена подкрепа трябва да се провери за оптималност, която използва следната теорема.

Теорема. Ако по някаква програма за подкрепа на проблема с транспорта, а има и номера. че

и за всички, това е най-добрият план.

Определение 4. номера и (,) се нарича потенциалните, съответно, доставчиците и потребителите.

по този начин намиране на потенциални доставчици и клиенти, които отговарят на условията на теоремата, ние доказваме оптималността на изградения план. Как да ги намеря? защото броя на заетите клетки, Xij> 0, е равно на п + m-1 (nondegenerate нагоре) на системата (4) с N + м неизвестни съдържа N + М-1 уравнения. Да предположим, че един от най-неизвестните е равен на нула, и последователно се намери стойността на останалата непознатото. След това, за всички налични клетки, Xij = 0, ние се определи броя.

Ако нито един от номерата не е положителен, тогава са изпълнени условията на теоремата, а планът е оптимално. Ако има> 0, тогава планът не е оптимално и трябва да се подобри.

план за подобряване на алгоритъма:

1) сред всички> 0 е избран максимален;

2) за съответните клетки изграждат цикъл конверсия;

3) да нанася на върха на цикъла преобразуване последователно знаците "+" и "-". като се започне с "+" в изходния клетката;

4) между цифрите, стоящи в клетките, маркирани с "-". определи минималната;

5) стойностите стои в "+" - клетки, добавят се на минималния брой и стойностите на заставане в "-" - клетките, този брой се изваждат.

ОПРЕДЕЛЕНИЕ 5. преизчисляване цикъл се нарича прекъсната линия, чиито върхове се намират в клетките, използвани и единици - по редове и колони, при което всеки връх на цикъла може да бъде само две нива.

Така изменен план отново проверява за оптималност, т.е. преход към п. 2.

3. Методът на диференциалната рента

За разлика от метода на потенциалите на която се позовава построена първата съставена от последователно и след това го е подобрена, метод за решаване на проблема с диференциал наеми веднага най-добре се разпределя между потребителите на продуктите и при следващите повторения постепенно намаляване на общия размер на неразпределено доставки.

За определяне на решения на диференциални наем от проблемите с транспорта, като се използва следния алгоритъм:

Във всяка колона, определи минималната и освободи sotvetstvuet-проводящ клетка.

2. Изолираните клетки бяха напълнени с възможно най-много.

3. Тъй като като цяло, това разпределение не отговаря на всички изискват-ING, че за следващите стъпки, за да се намали размера на незадоволени потребности, е необходимо да се направи оценка на доставчиците.

Дефиниция 6. Редовете, съответстващи на доставчиците, изчерпване на запасите, както и нуждите на целевите потребители, които не са изпълнени, са отрицателни.

ОПРЕДЕЛЕНИЕ 7. Lines съответните доставчици запаси не са напълно изчерпани, са положителни.

ОПРЕДЕЛЕНИЕ 8. Линии съответните доставчици изчерпване на складовите наличности и нуждите на потребителите са доволни от избрания имат резултат нула. В този случай, ако втората клетка е изпълнен с стои в колона, свързана с дадена линия на друг попълнено клетка намира в положителната линия, тази линия е нула оценка е положителна. В противен случай - отрицателен.

4. За всяка колонка с избрания курс в отрицателна линия, намирането на разликата между избрания тарифа и най-близката по големина процент изложение в положителна линия.

5. определя минималната сред получава разликата. Този номер се нарича временното наема.

6. Изграждане на нова таблица, тарифите, стоящи в положителни линии са презаписани без промяна, а тарифите пред които са изправени в негативните линии, увеличаването на стойността на междинното наема.

7. Що се отнася до претенция 1.

ЗАБЕЛЕЖКА: а) ако ред или колона е избран повече от една клетка, след което се запълва, предимно тези изолирани клетки, които са единствените в колона или ред;

б) ако е възможно да се разпределят всички доставки, които са оптимални план на проблема с транспортирането.

4. Допълнителни ограничения на транспортния проблем

1. Забранени маршрути.

Ако по някаква причина не е възможно да доставят продуктите от н. Ai в п. Vj. подсказва, че начинът, по тарифата произволно голяма стойност на M, Сий =