Визначення початкового опорного плану задачі лінійного програмування

Алгоритм симплексного методу

- визначення початкового опорного плану починають із запису ЗЛП у канонічній формі.

Якщо в системі обмежень є обмеження-нерівності, то до лівої частини обмежень типу «≤» додаємо додаткові невід’ємні невідомі, а від лівих частин обмежень типу «≥» віднімаємо додаткові невід’ємні невідомі.

Якщо права частина обмеження від’ємна, то множимо все обмеження на (-1).

Якщо цільова функція містить базисні невідомі, то виражаємо їх через вільні з системи обмежень і підставляємо в цільову функцію.

- перевіряємо, чи кількість базисних невідомих дорівнює кількості рівнянь системи обмежень, якщо так, то початковий опорний план визначається безпосередньо без додаткових дій.

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

Якщо ж кількість базисних невідомих менша від кількості рівнянь-обмежень задачі, то для побудови початкового опорного плану використовують метод штучного базису.

2. Побудова симплексної таблиці.

№ таблиці	№ рядка	Базис	Опорний план	Коефіцієнти при невідомих
х 1	х 2	х 3	х 4	х 5
		Z
	х 3
	х 4
	х 5

3. Перевірка опорного плану на оптимальність за допомогою чисел нульового рядка симплекс-таблиці.

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

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

- перехід від одного опорного плану до іншого виконується зміною базису.

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

Якщо цільова функція досліджується на мінімум і в нульовому рядку симплекс-таблиці є додатні числа (за винятком стовпчика «Опорний план»), то вибираємо найбільше з цих чисел і невідому, що відповідає цьому числу, вводимо в базис.

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

Стовпець, який відповідає невідомій, що вводиться в базис, називається ключовим.

Для визначення змінної, яка має бути виведена з базису, знаходять відношення елементів стовпця «Опорний план» до відповідних додатних елементів ключового стовпця (нульовий рядок не розглядаємо) і вибираємо найменше з цих відношень.

Невідому, яка відповідає цьому відношенню, виключаємо з базису.

Рядок, який відповідає цьому найменшому відношенню, називається ключовим рядком.

На перетині ключового рядка і ключового стовпця знаходиться ключовий (генеральний) елемент.

За допомогою генерального елемента і методу Жордана-Гауса переходимо до нової симплекс-таблиці.

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