Транспортна задача закритого типу. Методи північно-західного кута та найменшого елемента для побудови опорного розв'язку транспортної задачі і умова його невиродженості - Економіко-математичне моделювання

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

.

Теорема:Будь-яка задача закритого типу має хоча б один розв'язок.

Методи побудови опорних розв'язків ТЗ:

Метод північно-західного кута полягає в тому, що заповнення таблиці починають, не враховуючи вартостей перевезень, з лівого верхнього (північно-західного) кута. У клітину записують менше з двох чисел А1 та B1. Далі переходять до наступної клітини в цьому ж рядку або у стовпчику і заповнюють її, і т. д. Закінчують заповнення таблиці у правій нижній клітинці. У такий спосіб значення поставок будуть розташовані по діагоналі таблиці.

Недоліком даного методу є те, що він не враховує вартість перевезень, а отже знайдений опорний розв'язок може бути "далеким" від оптимального.

Метод найменшої елемента

Суть цього методу полягає в тому, що ми, в першу чергу, заповнюємо ті клітини, де вартість перевезення найменша. Заповнювати таблицю можна по стовпчиках, тобто спочатку шукаємо найменшу вартість перевезення в першому стовпчику, а потім у другому і так далі. (Заповнювати таблицю можна по рядках).

Опорний план транспортної задачі - це такий допустимий її план, що містить не більш ніж додатних компонент, а всі інші його компоненти дорівнюють нулю. Такий план є Невиродженим.

Похожие статьи




Транспортна задача закритого типу. Методи північно-західного кута та найменшого елемента для побудови опорного розв'язку транспортної задачі і умова його невиродженості - Економіко-математичне моделювання

Предыдущая | Следующая