a1
A2
C21
C22
...
C2n
a2
...
...
...
...
...
...
Am
Cm1
Cm2
...
Cmn
am
b1
b2
...
bn
Таким чином, забезпечується доставка необхідної кількості вантажу до кожного з пунктів призначення, вивезення наявного вантажу з усіх пунктів відправлення, а також виключаються зворотні перевезення. Всяке невід'ємне рішення систем лінійних рівнянь називається планом транспортної задачі. План, при якому цільова функція приймає своє мінімальне значення, називається оптимальним планом транспортної завдання. Якщо в опорному плані число відмінних від нуля компонент одно в точності n + m-1, то план є невиродженим, а якщо менше - то виродженим. [3 c.132-134]
Якщо загальна потреба в вантажі в пунктах призначення дорівнює запасу вантажу в пунктах відправлення, то модель такої транспортної задачі називається закритою. Якщо ж вказане умова не виконується, то модель транспортної задачі називається відкритою. p> У разі перевищення запасу над потребою, вводиться фіктивний (n +1)-й пункт призначення з потребою (формула 2.10) і відповідні тарифи вважаються рівними нулю. Аналогічно, у разі, якщо потреби перевищують кількість запасів, також вводиться фіктивний (m +1)-й пункт відправлення із запасом вантажу і тарифи покладаються рівними нулю (формула 2.11). Цим завдання зводиться до звичайної транспортної задачі, з оптимального плану якої виходить оптимальний план вихідної задачі.
(2.10)
(2.11)
Як і для всякої завдання лінійного програмування, оптимальний план транспортної задачі є і опорним планом. Опорний план є допустимим рішенням ТЗ і використовується в якості початкового базисного рішення при знаходженні оптимального рішення методом потенціалів. Існує чотири методу знаходження опорних планів:
1. метод північно-західного кута;
2. метод мінімального елемента;
3. метод подвійного уподобання;
4. метод штрафів (Фогеля). p> "Якість" опорних планів, отриманих цими методами, різниться: у загальному випадку метод Фогеля дає найкраще рішення (часто оптимальне), а метод північно-західного кута-найгірше.
Всі існуючі методи знаходження опорних планів відрізняються тільки способом вибору клітини для заповнення. Само заповнення відбувається однаково незалежно від використовуваного методу. Слід пам'ятати, що перед знаходженням опорного плану транспор...
