овпці і рядки далі не розглядаються. p> В· Якщо не всі споживачі задоволені і не всі постачальники витратили товари, повернення до п.1, в іншому випадку задача вирішена. В
1.2.3 Метод потенціалів
Найбільш простим методом ТЗ є метод потенціалів. Потенціалами називаються умовні числа U i , V j , приписані певним чином кожному постачальнику і споживачу.
Теорема (умови оптимального плану): Сума потенціалів постачальника і споживача дорівнює тарифної ставкою для зайнятих клітин; сума потенціалів постачальника і споживача не перевищує тарифну ставку для вільних клітин
В В В
Опорний план має бути НЕ виродженим (r = m + n-1 - невироджений план)
Алгоритм рішення:
1. Будуємо початкові плани методом північно-західного кута і методом найменшої вартості з них вибираємо кращий
2. Знаходимо потенціали постачальника і споживача, користуючись першою умовою оптимальності плану U i + V j ij
3. Перевіряємо другий умова оптимальності плану для вільних клітин
В В
Якщо воно виконано, то план оптимальний, якщо ні то покращуємо план.
4. Поліпшення плану:
a. При не виконанні другої умови в клітку заносимо порушення з знаком плюс. Такі клітини називаються потенційними. p> b. Серед всіх потенційних клітин вибираємо клітину з найбільшим
порушенням.
c. Будуємо для обраної клітини замкнутий контур, що складається з вертикальних і горизонтальних відрізків прямої, причому вершини контуру лежать в зайнятих клітках.
За винятком тієї клітини, для якої будується контур
d. Вершини контуру по черзі позначаємо знаками плюс і мінус, починаючи з клітини, для якої будується контур.
e. Серед клітин помічених знаком мінус вибираємо найменше перевезення і на цю величину збільшуємо перевезення в клітинах помічених знаком плюс і зменшуємо в клітинах помічених знаком мінус в результатах перепризначення звільняється одна клітина.
5. Знову отриманий план перевіряємо на оптимальність.
В
1.2.4 Метод апроксимації Фогеля
Даний метод полягає в наступному:
1. На кожній ітерації знаходять різниці між двома найменшими тарифами у всіх рядках і стовпцях, записуючи їх в додаткові стовпець і рядок таблиці;
2. Знаходять max О”c ij і заповнюють клітину з мінімальною вартістю в рядку (стовпці), якій відповідає дана різниця.
Процес продовжується до тих пір, поки всі Грузія не будуть розвезені по споживачам. Даний метод у ряді завдань призводить до оптимального плану.
ГЛАВА 2. ПРАКТИЧНА РЕАЛІЗАЦІЯ МЕТОДІВ РІШЕННЯ ТРАНСПОРТНОЇ ЗАВДАННЯ
2.1 Постановка завдання
Є три пункти поставки моніторів: Склад № 1, Склад № 2, Склад № 3. І п'ять магазинів: Магазин "Терабайт", Ма...
