Робота із симплекс-таблицею.

1. Якщо в рядку оцінок немає від’ємних - план оптимальний, задача розв’язана.

2. Якщо є хоча б одна від’ємна оцінка - план не оптимальний і може бути поліпшеним.

3. Вибираємо стовпець з найменшою негативною оцінкою, він називається напрямним стовпчиком.

4. Якщо всі елементи стовпчика не додатні, задача розв’язків не має.

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

Припустимо, що номер стовпчика дорівнює k.

Обчислюємо Θ_i= , a_lk> 0 знаходимо l з умови Θ_l= minΘ_i

Вирішувальний елемент, a_lk, рядок 1 - напрямний рядок.

6. Виконаємо перехід до нового базису: виведемо з базису вектор А_l і введемо замість нього вектор А_k. Для цього всі елементи рядка l (з 4-го стовпчика) розділимо на a_lkі методом Жордана-Гаусса виключимо всі інші елементи напрямного стовпчика. Отримаємо новий план Х₁ ; нову симплекс-таблицю.

7. За кінцеве число кроків одержуємо оптимальний план X*. Якщо нульові оцінки є тільки для базисних стовпчиків, оптимальний розв’язок є єдиним. Якщо ні – маємо кілька оптимальних планів.

Приклад. F = x₁ + 2x₂ + 8x₃ "max

;

Контрольні запитання

1. Якою є канонічна форма ЗЛП?

2. Як виглядає матричний запис канонічної форми ЗЛП?

3. Яким є алгоритм симплекс-методу?

4. Як будувати першу симплекс-таблицю в найпростіших умовах?

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

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

<== попередня сторінка	\|	наступна сторінка ==>
Побудова першої симплекс-таблиці	\|	Лекція 3

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

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