ідного кута).
Дивимося на запаси M 1 і потреби N 1 . Якщо M 1 1 , то в клітку (1,1) вписуємо M l (тобто віддаємо пункту призначення весь запас вантажу з першого пункту відправлення - випадок в таблиці). Якщо N 1 < M 1 , то в клітку (1,1) записуємо N 1 , тобто покриваємо всю потребу першого пункту призначення за рахунок першого пункту відправлення.
Перепишемо баланс після першої операції (Зміняться і потреби, і запаси). У першому рядку інші клітини можна прочеркнуть, так як весь вантаж пішов у перший пункт.
Другий тур починаємо знову з північно-західного кута. Задовольняємо залишилася потреба першого пункту призначення, доставивши туди ( N 1 - M l ) одиниць вантажу з другого пункту відправлення. Якщо потреба першого пункту задоволена повністю, інші клітини в першому стовпці прокреслюють. Переписуємо баланс після другої операції. p> Знову починаємо з північно-західного кута, задовольняємо потребу другого пункту призначення і т.д., поки справа і знизу не стоятимуть нулі, тобто весь вантаж розподілений і потреби задоволені. Отриманий всередині таблиці план буде допустимим. Його і беремо в якості початкового. p> Другий етап попереднього кроку: визначення системи потенціалів.
Потенціал приписується кожному пункту відправлення (позначається u i ) і кожному пункту призначення ( v j ). Всього потенціалів k + l чисел. Вони вносяться у спеціально відведені для цього рядок і стовпець макета.
Для Х -відмічених тарифів a ij , число яких завжди дорівнює ( k + l - 1), повинні виконуватися рівності v j - u i = a ij . Ці рівності і будуть служити тими рівняннями, з яких знаходяться потенціали. Однак таких рівнянь буде тільки ( k + l - 1), а невідомих у системі ( k + l ), тобто на одиницю більше. Така система рівнянь має незліченну безліч рішень, будь-яке з яких годиться для нашої мети. Щоб знайти якесь одне рішення, значення одного потенціалу вибираємо довільно. Решта потенціали визначаємо з рішення системи. Третій етап попереднього кроку: випробування плану або системи потенціалів на потенційність. Потенційність полягає в тому, щоб нерівність v j - U i ij виконувалося для всіх без винятків клітин. При цьому Х -відмічені клітини перевіряти не треба, так як потенціали підібрані з умови виконання в них рівності.
Виділяємо позитивні різниці d ij :
В
d ij = v j - u i - a ij > 0.
В
На цьому попередній крок закінчений.
11.2 Зага...
