7.1.3. Симплексний метод рішення.
Нехай потрібно мінімізувати цільову функцію при обмеженнях (4). Приведемо (4) до стандартного виду (2). Для цього до лівої частини кожного обмеження, що має вид нерівності ≤, добавляємо додатну змінну: . Якщо обмеження у виді нерівності ≥, то з лівої частини віднімаємо . Система прийме вигляд:
Усього змінних . Усі повинні бути додатними. Якщо , то дане рівняння потрібно помножити на (-1). Так як цільова функція не має стаціонарних точок, то своїх максимального і мінімального значень вона досягає на границі області.
Th. Нехай область припустимих рішень - обмежений замкнутий багатогранник, тоді мінімальне (максимальне) значення цільової функції досягається в кутовій точці.
Так як число невідомих більше числа рівнянь , то частина невідомих покладається базисними. Вільні змінні переносяться в праву частину. Система вирішується відносно базисних змінних. Така система сумісна, якщо визначник, що складається з коефіцієнтів при базисних невідомих у системі обмежень відмінний від нуля, чи якщо вектори , що відповідають базисним змінним, є незалежними.
Визначення. Рішення називається базисним, якщо вільні змінні рівні 0.
Кожне базисне рішення відповідає кутовій точці. Кількість базисних рішень:
Таким чином, щоб знайти оптимальне рішення, потрібно обчислити значення цільової функції у всіх кутових точках і вибрати точку, у якій значення цільової функції мінімально (максимально); якщо n велике, то кількість кутових точок велике число.
Визначення. Симплексний метод - упорядкований перехід від одного базисного рішення до іншого, при якому відбувається зменшення значення цільової функції. (Використовується для відшукання мінімального значення цільової функції )
Розглянемо побудову нульового базисного рішення. Припустимо, що система обмежень (3) містить одиничних векторів (така ситуація виникає, якщо всі обмеження визначаються нерівностями ≤; інакше перші перемінних вибираються в якості базисних і щодо них вирішується система лінійних рівнянь ). Тоді система обмежень має вигляд:
Базисні змінні: ; інші - вільні. Нехай вільні змінні рівні 0, отримуємо нульове базисне рішення: .
Далі виникає необхідність перевірити, чи не є знайдене базисне рішення оптимальним. Помітимо, що вектори системи обмежень мають вигляд:
; ;…;; ;…;.
Вектори ,…, – одиничні і утворюють базис у – вимірному просторі, тобто кожний з векторів можна розкласти за даним базисом:
Так як базис одиничний, то . Кожному розкладанню відповідає єдине значення :
Th: (критерій оптимальності) Якщо для деякого базисного рішення розкладання усіх векторів задовольняють умові , то план оптимальний, інакше потрібно вибрати новий базис і шукати нове базисне рішення.
- Питання до модульного контролю 1 з дисципліни
- Питання до модульного контролю 2 з дисципліни
- Текстовий редактор. Редактор формул.
- Панель Programming
- Панель Symbolic.
- 1.1.2. Створення й використання простих формул 7
- 1. 1.3. Абсолютні й відносні адреси чарунок 7
- 4. Лабораторна робота №4 „Основні прийоми роботи в Системе MathCad” 37
- 5.1.3. Метод ітерацій. 52
- 5.1.4. Метод Зейделя. 53
- 1.1. Теоретичні відомості
- 1.1. 1.Основні поняття електронних таблиць
- 1.1.2. Створення й використання простих формул
- 1. 1.3. Абсолютні й відносні адреси чарунок
- Рекомендації й вимоги до виконання завдання 2
- Питання для самоперевірки
- 2. Лабораторна робота №2 „Побудувати рівняння моделі методом найменших квадратів.”
- 2.1. Теоретичні відомості
- 2.2. Приклад виконання лабораторної роботи №2
- 2.3.Завдання до лабораторної роботи №2
- Питання для самоперевірки
- 3.1.Теоретичні відомості .
- 3.1.1. Постановка задачі.
- Метод Ньютона (дотичних).
- 3.2. Приклад виконання лабораторної роботи №3
- 3. 3. Завдання до лабораторної роботи №3
- 3.4. Використання Excel для развязку лабораторної роботи №3
- Питання для самоперевірки
- 4.1. Теоретичні відомості
- 4.1.1. Призначення MathCad. Стандартний інтерфейс.
- 4.1.2. Панель інструментів Математика(Math).
- 4.1.3. Текстовий редактор.
- 4.1.4. Редактор формул.
- 4.1.6. Користувальницькі й стандартні функції.
- 4.1.7. Побудова графіків.
- 4.1.8. Робота з векторами й матрицями.
- Обчислення визначника;
- 4.1.9. Панель Programming.
- 4.1.10. Панель Symbolic.
- 4. 2. Завдання та приклад виконання лабораторної роботи №4 Зробить завдання по наведеному зразку
- Питання для самоперевірки
- Використовувана література.
- 5.1. Теоретичні відомості
- 5.1.1. Норма вектора. Норма матриці.
- 5.1.2. Приведення системи до виду зручному для ітерацій.
- 5.1.3. Метод ітерацій.
- 5.1.4. Метод Зейделя.
- 5.2. Приклад виконання лабораторної роботи №5
- 5.3. Завдання до лабораторної роботи №5
- Питання для самоперевірки
- Використовувана література
- 6.1.Теоретичні відомості
- 6.1.1. Постановка задачі.
- 6.1.2. Інтерполяційний многочлен Лагранжа
- 6.1.2.1. Погрішність інтерполяції.
- Інтерполяційний многочлен Лагранжа з рівновіддаленими вузлами.
- 6.1.3. Інтерполяційний многочлен Ньютона
- 6.1.3.1. Кінцеві різниці.
- 6.1.3.2. Формула Ньютона для інтерполяції «вперед».
- 6.1.3.3. Формула Ньютона для інтерполяції «назад».
- 6.2. Приклад виконання лабораторної роботи №6
- 6.3. Завдання до лабораторної роботи №6
- Питання для самоперевірки
- Література, що використовується
- 7. Лабораторна робота №7 „Рішення задачі лінійного програмування. ”
- 7.1. Теоретичні відомості
- 7.1.1. Постановка задачі.
- 7.1.2. Геометричний метод рішення.
- 7.1.3. Симплексний метод рішення.
- 7.1.4. Алгоритм симплексного методу.
- 7.2. Приклад виконання лабораторної роботи №7
- Задачі лінійного програмування
- 7.3. Завдання до лабораторної роботи №7
- Питання для самоперевірки
- Використовувана література
- 8. Список літератури
- Методичні вказівки до виконання лабораторних робіт з дисципліни
- Для студентів денної форми навчання напряму підготовки
- 6.051301 „Хімічна технологія”.
- 1 Семестр.