Алгоритм знаходження оптимального плану

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

		….			….		І
		….			….
….	….	….	….	….	….	….	….
		….			….
….	….	….	….	….	….	….	….
		….			….
		….			….

1. Після отримання опорного плану переглядаємо коефіцієнти рядка функціоналу . Якщо всі окрім , то оптимальний план знайдено. Цей розв’язок можна виписати із таблиці, прирівнюючі «верхні» змінні до нуля, а «бокові» ‑ до вільних членів.

2. Якщо у рядку є елементи (не враховуючи ), то стовпчик з цим елементом буде розв’язуючий. Якщо таких елементів декілька, то за розв’язуючий обирається стовпчик з максимальним за модулем елементом.

3. У якості розв’язуючого елемента обирається елемент у розв’язуючому стовпчику, якому відповідає мінімальне симплексне відношення. З цим елементом робимо один крок МЖВ.

4. Отриманий план досліджуємо на оптимальність (п. 1). За наявності процес продовжується.

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

Приклад.

Знайти максимум функціоналу