Метод північно-західного кута

Методи складання первісного опорного плану

Для опорних планів ТЗ пред'являються наступні вимоги:

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

Така таблиця починає заповнюватися з лівого верхнього кута (з північно-заходу). Принцип заповнення виражається співвідношенням

Аналізуємо співвідношення між а₁ в₁ і далі процес заповнення кліток розвивається по рядку вправо, або по стовпцю вниз. Допустимо,

Далі, процес розвивається по стовпцях і рядках доти, поки не буде заповнена клітка з адресою m∙ n. Якщо ж процес завершиться раніше, ніж у клітці m∙ n, то задача є виродженою.

Особливості методу:

1. Такого характеру методи ще називаються діагональними, оскільки порядок заповнення кліток здійснюється з лівого верхнього кута до правого нижнього.

2. Метод відрізняється надзвичайною простотою, тому що, якщо процес заповнення кліток закінчується в клітці з адресою m∙ n, те побудований план свідомо буде опорним і немає необхідності перевіряти всі три вимоги до опорних планів.

3. Отриманий опорний план буде далекий від оптимального, оскільки він не враховує значення тарифів.

Дата добавления: 2014-12-07