Алгебра симплексного процесу при визначенні opt типу min

1. Розв'язувальний стовпець вибирається по невід’ємному елементу в рядку лінійної форми F (за винятком вільного члена). У розглянутій задачі це стовпець, що відповідає вільній змінній х₄.

2. Розв'язувальний рядок вибирається по мінімальному симплексному відношенню, тобто по мінімальному відношенню елемента стовпця вільних членів до відповідного невід’ємного елемента розв'язувального стовпця. У розглянутій задачі , тобто розв'язувальний рядок – перший.

3. Розв'язувальний елемент завжди невід’ємний.

4. Перетворення симплексних таблиць проводиться в умовах прямо припустимості розв’язків.

Розв'язок прямо припустимий, якщо серед базисних змінних немає невід’ємних.

5. Процес триває доти, поки в рядку лінійної форми F всі коефіцієнти стануть від’ємними (за винятком, бути може, самого значення лінійної форми).

Визначення оптимального плану типу max проілюструємо на прикладі розв'язування наступної задачі:

Первісне значення лінійної форми F₀ = 3, .

На основі останньої форми запису ЗЛП складемо первісну жорданову таблицю

		-х4	-х5				-х4	-х1
х1					х5
х2					х2		–1	–3
х3		–1	–3		х3
F			–1		F

Нове значення лінійної форми , новий план Цей план є оптимальним, тому що в рядку лінійної форми F всі елементи невід’ємні й подальше збільшення значення функції цілі неможливо. Таким чином,

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