- •З дисципліни
- •1 Змістовий модуль 1. Лінійне та нелінійне програмування
- •Тема 1 «Введення в дисципліну. Побудова математичних моделей проблемних ситуацій»
- •1. Загальна методологія дослідження операцій
- •2. Модель операції, основні принципи її побудови
- •3. Методика проведення дослідження операцій
- •4. Типові класи задач дослідження операцій
- •Тема 2 «Задачі математичного програмування (мп)»
- •1. Загальна постановка задачі математичного програмування (мп)
- •2. Класифікація задач мп
- •3. Типи максимумів. Теорема Вейєрштрасса та теореми про достатні умови глобального максимуму
- •4. Специфіка задач математичного програмування
- •Тема 3 «Лінійне програмування»
- •1. Загальна постановка задачі лінійного програмування (злп)
- •2. Форми запису злп (загальна, стандартна, канонічна форми)
- •Приклади практичних задач лінійного програмування
- •Тема 4 «Геометрична інтерпретація злп»
- •1. Графічний метод розв'язання злп. Умови графічного розв'язання злп.
- •2. З’ясування основних особливостей та властивостей розв’язків злп за допомогою геометричної інтерпретації.
- •3. Основні етапи графічного розв'язання злп (Алгоритм геометричної інтерпретації злп)
- •Тема 5 «Симплексний метод розв'язування злп»
- •1. Аналітичні методи розв'язування злп
- •2. Ідея симплексного методу розв'язування злп
- •3. Основні теореми, на яких базується симплексний метод
- •4. Симплекс-алгоритм розв'язування невироджених злп
- •Тема 6 «злп з штучним базисом»
- •1. Ідея симплексного методу розв'язування злп із штучною базою
- •3. Алгоритм розв'язання злп із штучною базою
- •Тема 7 «Двоїстість. Двоїстість (спряженість) у лінійному програмуванні»
- •1. Поняття двоїстості в лінійному програмуванні
- •2. Основні теореми двоїстості та їх економічний зміст
- •Тема 8 «Спеціальні задачі мп. Спеціальні методи розв’язання злп»
- •Транспортна задача ( т-Задача) та її математична модель.
- •2. Методи визначення опорного плану т-Задачі
- •3. Методи розв’язання т-задач
- •Розв'язання т-задач методом потенціалів
- •Тема 9 «Параметричне програмування»
- •2. Моделі задач параметричного програмування
- •Тема 10 «Нелінійне програмування»
- •1. Загальна постановка задачі нелінійного програмування
- •2. Класичні умови екстремуму. Метод множників Лагранжа
- •4. Задача нелінійного програмування й сідлова точка
- •5. Умови Куна-Таккера для знп. Теорема Куна-Таккера
- •2 Змістовий модуль 2. Дискретне та стохастичне програмування
- •Тема 1 «Дискретне програмування»
- •1. Загальні характеристика дискретних задач
- •2. Класифікація задач дискретного програмування. Математичні моделі задач дискретного програмування
- •1. Як у загальному виді надається задача дискретного програмування?
- •Тема 2 «Клас цілочислових лінійних задач»
- •Особливості задач цілочисельне програмування. Моделі цзлп
- •Моделі цзлп
- •2. Метод відсікань (метод Гоморі) розв'язання зцлп
- •3.Комбінаторні методи розв’язування цзлп
- •4. Метод гілок та меж в задачах цілочислового програмування. Ідея методу гілок і меж, ознака оптимальності плану
- •Тема 3 «Динамічне програмування»
- •1. Загальна структура задач динамічного програмування
- •2. Принципи динамічного програмування. Принцип оптимальності Беллмана
- •3. Приклади задач динамічного програмування
- •Тема 4 «Стохастичне програмування»
- •1. Загальна характеристика задач стохастичного програмування. Методи розв’язання задач стохастичного програмування.
- •2. Приклади задач стохастичного програмування
- •3 Змістовий модуль 3. Методи оптимізації
- •Тема 1 «Методи оптимізації функцій, що диференціюються та що не диференціюються»
- •Тема 2 «Методи оптимізації в задачах великої розмірності та методи багатокритеріальної оптимізації»
- •1. Методи оптимізації багатовимірних задач
- •Градієнтні методи
- •Найшвидший підйом з використанням одномірного пошуку
- •Метод найшвидшого спуску
- •Метод Флетчера – Рівса
- •Метод Девідона – Флетчера – Пауела
- •Метод конфігурацій Хука – Дживса
- •Метод конфігурацій Розенброка
- •4 Навчально–методичні матеріали з дисципліни
Тема 4 «Геометрична інтерпретація злп»
План лекції
1. Графічний метод розв'язання ЗЛП. Умови графічного розв'язання ЗЛП.
2. З’ясування основних особливостей та властивостей розв’язків ЗЛП за допомогою геометричної інтерпретації.
3. Основні етапи графічного розв'язання ЗЛП (Алгоритм геометричної інтерпретації ЗЛП).
1. Графічний метод розв'язання злп. Умови графічного розв'язання злп.
Геометрична інтерпретація економічних задач дає можливість наочно представити їхню структуру, виявити особливості й відкриває шляхи дослідження більш складних властивостей. ЗЛП із двома змінними завжди можна вирішити графічно. Однак уже в тривимірному просторі таке рішення ускладнюється, а в просторах, розмірність яких більше трьох, графічне рішення, загалом кажучи, неможливо. Випадок двох змінних не має особливого практичного значення, однак його розгляд прояснює властивості ОЗЛП, приводить до ідеї її рішення, робить геометрично наочними способи рішення й шляхи їхньої практичної реалізації.
Нехай дана задача
(1)
(2)
(3)
Дамо
геометричну інтерпретацію елементів
цієї задачі. Кожне з обмежень (2), (3) задає
на площині
деяку напівплощину. Напівплощина -
опукла множина. Але перетинання будь-якого
числа опуклих множин є опуклою множиною.
Звідси видно, що область припустимих
рішень задачі (1) - (3) є опуклу множина.
Перейдемо
до геометричної інтерпретації цільової
функції. Нехай область припустимих
рішень ЗЛП – непуста множина, наприклад
багатокутник
.
Виберемо
довільне значення цільової функції
.
Отримаємо
..
Це рівняння прямої лінії. У точках прямій
NМ
цільова функція зберігає те саме постійне
значення
.
Вважаючи в рівності (1)
параметром, одержимо рівняння сімейства
паралельних прямих, які називаються
лініями рівня цільової функції (лініями
постійного значення).
Знайдемо
частки похідні цільової функції по
й
(4)
(5)
Частинна
похідна (4) – (5) функції показує швидкість
її зростання уздовж даної осі. Отже,
і
–
швидкості зростання
відповідно уздовж осей
і
.
Вектор
називається градієнтом функції. Він
показує напрямок найшвидшого зростання
цільової функції:
.
Вектор
указує напрямок найшвидшого убування
цільової функції. Його називають
антиградієнтом.
Вектор
перпендикулярний
до прямих
сімейства
.
2. З’ясування основних особливостей та властивостей розв’язків злп за допомогою геометричної інтерпретації.
При знаходженні графічних розв’язків задачі ЛП можуть зустрітися випадки, коли:
а) цільова функція приймає максимальне значення в єдиній точці припустимої множини (єдине рішення);
б) цільова функція приймає максимальне значення в будь-якій точці відрізка (якщо лінія рівня збігається з обмеженням, тоді маємо випадок нескінченної множини рішень);
в) цільова функція може бути необмежена на множині припустимих рішень (тобто fmax = + ∞ – це також випадок нескінченної множини рішень);
г) рішення ЗЛП не існує, оскільки система обмежень цієї задачі несумісна.
