Лінійне програмування. Тема 4

Август 22, 2022

Главная
Математика
Лінійне програмування. Тема 4

Содержание

2. Симплекс-метод розв'язання задач лінійного програмування Симплекс-метод – це поетапна обчислювальна процедура, в основу якої покладено принцип
3. Алгоритм симплекс-методу розв'язання задач ЛП Визначення початкового опорного плану задачі ЛП. Побудова симплексної таблиці. Перевірка опорного
4. Алгоритм симплекс-методу розв'язання задач ЛП На етапі визначення початкового опорного плану задачі ЛП, після її зведення
5. Алгоритм симплекс-методу розв'язання задач ЛП Визначені одиничні лінійно незалежні вектори утворюють базис, і змінні задачі, що
6. Алгоритм симплекс-методу розв'язання задач ЛП
7. Алгоритм симплекс-методу розв'язання задач ЛП
8. Алгоритм симплекс-методу розв'язання задач ЛП
9. Алгоритм симплекс-методу розв'язання задач ЛП
10. Правила перебудови симплекс-таблиці за методом Жорданa-Гаусса 1. Розв’язувальний (напрямний) рядок необхідно поділити на розв’язувальний елемент і
11. Правило прямокутника перебудови симплекс-таблиці
12. Варіанти розв'язку задачі ЛП симплекс-методом
13. Приклад розв'язання задачі ЛП симплекс-методом
14. Приклад розв'язання задачі ЛП симплекс-методом
15. Приклад розв'язання задачі ЛП симплекс-методом
16. Приклад розв'язання задачі ЛП симплекс-методом
17. Приклад розв'язання задачі ЛП симплекс-методом
18. Приклад розв'язання задачі ЛП симплекс-методом
20. Скачать презентацию

Слайд 2

Симплекс-метод розв'язання задач лінійного програмування
Симплекс-метод – це поетапна обчислювальна процедура,

в основу якої покладено принцип послідовного покращення значень цільової функції переходом від одного опорного плану задачі лінійного програмування до іншого.
Алгоритм симплекс-методу завжди починається з деякого опорного розв’язку (плану) і потім намагається знайти інший опорний план, який покращує значення цільової функції.

Слайд 3

Алгоритм симплекс-методу розв'язання задач ЛП
Визначення початкового опорного плану задачі ЛП.
Побудова

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

Слайд 4

Алгоритм симплекс-методу розв'язання задач ЛП
На етапі визначення початкового опорного плану

задачі ЛП, після її зведення до канонічної форми, шукаємо m одиничних лінійно незалежних векторів, які становлять базис m-вимірного простору. Можливі такі випадки:
є необхідна кількість одиничних векторів, тоді початковий опорний план визначається безпосередньо без додаткових дій;
у системі обмежень немає необхідної кількості одиничних незалежних векторів. Тоді для побудови першого опорного плану застосовують метод штучного базису.

Слайд 5

Алгоритм симплекс-методу розв'язання задач ЛП
Визначені одиничні лінійно незалежні вектори утворюють

базис, і змінні задачі, що відповідають їм, називають базисними, а всі інші змінні – вільними.

Слайд 6

Алгоритм симплекс-методу розв'язання задач ЛП

Слайд 7

Алгоритм симплекс-методу розв'язання задач ЛП

Слайд 8

Алгоритм симплекс-методу розв'язання задач ЛП

Слайд 9

Алгоритм симплекс-методу розв'язання задач ЛП

Слайд 10

Правила перебудови симплекс-таблиці за методом Жорданa-Гаусса
1. Розв’язувальний (напрямний) рядок необхідно

поділити на розв’язувальний елемент і здобуті числа записати у відповідний рядок симплексної таблиці.
2. Розв’язувальний стовпчик у новій таблиці записують як одиничний з одиницею замість розв’язувального елемента.
3. Якщо в напрямному рядку є нульовий елемент, то відповідний стовпчик переписують у нову симплексну таблицю без змін.
4. Якщо в напрямному стовпчику є нульовий елемент, то відповідний рядок переписують у нову таблицю без змін.
5. Усі інші елементи наступної симплекс-таблиці розраховують за правилом прямокутника.

Слайд 11