Відмінності між версіями «Методи побудови опорного плану ТЗ.»

Версія за 18:26, 4 травня 2012

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

Ідея методу північно-західного кута полягає в тому, що заповнення таблиці починають, не враховуючи вартостей перевезень, з лівого верхнього (північно-західного) кута. У клітину записують менше з двох чисел Неможливо розібрати вираз (невідома помилка): a_{i}

та Неможливо розібрати вираз (невідома помилка): b_{i}

. Далі переходять до наступної клітини в цьому ж рядку або у стовпчику і заповнюють її, і т. д. Закінчують заповнення таблиці у правій нижній клітинці. У такий спосіб значення поставок будуть розташовані по діагоналі таблиці.

Метод північно-західного кута є найпростішим, однак і найменш ефективним. Визначимо загальну вартість перевезень згідно з початковим опорним планом.

Неможливо розібрати вираз (невідома помилка): F=110\times 4+40\times 4+10\times 3+50\times 1+10\times 4+80\times 2=880

(ум. од.).

Теорема

Опорний план транспортної задачі, знайдений методом північно-західного кута, завжди ациклічний.

Доведення. Скористаємося методом індукції числа p=m+n. Для p=2 теорема очевидна: план Неможливо розібрати вираз (невідома помилка): x_{11}=a_{1}=b_{1}

ациклічний, оскільки складається з m+n-1=1 елемента. Так само ациклічним є план для p=n, оскільки він складається лише з двох клітин.