Критерій оптимальності. Метод потенціалів

Наведемо тепер математичну модель транспортної задачі для будьяких постачальників і споживачів: знайти такі значення змінних (; ), які відповідають обмеженням:

(з кожного пункту відправлення повністю вивозиться продукція і кожний пункт споживання одержує потрібну кількість цієї продукції) і перетворюють у мінімум цільову функцію:

Ці співвідношення і цільову функцію можна зобразити в більш компактній формі:

Необхідною і достатньою умовою розв’язку транспортної задачі є умова балансу:

тобто загальна кількість виробленої продукції дорівнює загальній кількості попиту споживачів.

Транспортна задача, в якій виконується ця умова, називається закритою. Кожна транспортна задача розв’язується за тією ж схемою , що й будь-яка задача ЛП симплексним методом:

1) знаходимо спочатку будь-який базисний невід’ємний розв’язок;

2) перевіряємо, чи буде знайдений розв’язок оптимальним ;

3) якщо знайдений розв’язок не оптимальний, то виконуємо кілька кроків однократної заміни базису, які приводять до оптимального розв’язку.

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

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Способи складання першого базисного плану. Правило переходу від одного базисного плану до іншого	\|	Теорема

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.004 сек.