Метод північно-західного кута
Методи складання первісного опорного плану
Для опорних планів ТЗ пред'являються наступні вимоги:
1. Повинна задовольнятися система обмежень.
2. Кількість базисних кліток повинна дорівнювати m+ n-1. Якщо ця умова не виконується, то до складу базисного набору кліток уводять додаткові клітки небазисного набору, але з нульовими значеннями перевезень. Саме в такий спосіб й усувається виродженість ТЗ.
3. Базисний набір кліток ТЗ повинен бути ациклічним.
Метод, що називається правилом північно-західного кута, є одним з найбільш простих методів складання первісного опорного плану.
Розглянемо розподільну таблицю ТЗ
Пост. | Споживач | Зап. | |||
В1 | В2 | ... | Вn | ||
А1 | с11 а1 | с12 | ... | с1n | a1 |
А2 | с21 | с22 | ... | с2n | a2 |
... | ... | ... | |||
Аn | сm1 | сm2 | ... | сmn | am |
Потр. | в1 | в2 | ... | вn |
Така таблиця починає заповнюватися з лівого верхнього кута (з північно-заходу). Принцип заповнення виражається співвідношенням
Аналізуємо співвідношення між а1 в1 і далі процес заповнення кліток розвивається по рядку вправо, або по стовпцю вниз. Допустимо,
Далі, процес розвивається по стовпцях і рядках доти, поки не буде заповнена клітка з адресою m∙ n. Якщо ж процес завершиться раніше, ніж у клітці m∙ n, то задача є виродженою.
Особливості методу:
1. Такого характеру методи ще називаються діагональними, оскільки порядок заповнення кліток здійснюється з лівого верхнього кута до правого нижнього.
2. Метод відрізняється надзвичайною простотою, тому що, якщо процес заповнення кліток закінчується в клітці з адресою m∙ n, те побудований план свідомо буде опорним і немає необхідності перевіряти всі три вимоги до опорних планів.
3. Отриманий опорний план буде далекий від оптимального, оскільки він не враховує значення тарифів.