3. Параметричне лінійне програмування.
Параметричне програмування являє собою один з розділів математичного програмування, вивчає завдання, в яких цільова функція або обмеження залежать від одного або кількох параметрів. Необхідність розгляду подібних завдань обумовлена різними причинами. Однією з основних є та, що вихідні дані для чисельного рішення будь-якої реальної задачі оптимізації в більшості випадків визначаються наближено або може змінюватися під впливом якихось чинників, що може істотно позначитися на оптимальності вибираної програми (плану) дій. Відповідно, розумно вказувати не конкретні дані, а діапазон можливої зміни даних, що б в результаті рішення мати найкращі плани для будь-якого варіанту вихідних даних. З математичної точки зору параметричне програмування виступає як один із засобів аналізу чутливості рішення до варіації вихідних даних, оцінки стійкості рішення.
Зауважимо, що існують різні підходи до подібного аналізу (наприклад, на основі постановки двоїстої задачі). Тут ми, не посилаючись на двоїсті оцінки, розглянемо найпростіші варіанти рішення для самих найпростіших параметричних задач. Розглянемо задачу параметричного лінійного програмування, в якій тільки коефіцієнти цільової функції лінійно залежать від деякого єдиного параметра λ (часу, температури і т. п.): Відшукати максимум (або мінімум) функції:
за умов
Якщо звернутися до геометричної інтерпретації задачі, то можна помітити, що вектор-градієнт лінійної форми визначається її параметром. Наприклад, для цільової функції L (х, λ) = λх1 + (1-λ) х2 при різних значеннях параметра λ градієнт визначає різні напрямки зростання функції. Неважко бачити, що, якщо при деякому значенні параметра максимум досягається в вершині A, то невелика варіація цього значення дещо змінить напрямок градієнта, але не змінить положення точки максимуму. Звідси напрошується висновок, що деякий план, оптимальний при λ = λ0 оптимальний і в околиці λ0, тобто при α ≤ λ ≤ β де λ0 [α, β]. Можна помітити, що при градієнті, що став перпендикулярним деякої сторони багатокутника планів, маємо два різних оптимальних опорних плани з одним і тим же значенням лінійної форми, звідки можна стверджувати безперервність екстремуму лінійної форми за λ.
У разі необмеженість безлічі планів можна стверджувати, що якщо лінійна форма не обмежена при λ = λ0, то вона не обмежена при всіх λ, більших або менших λ0. Алгоритм для вирішення завдань параметричного лінійного програмування в разі залежності від параметра коефіцієнтів цільової функції незначно відрізняється від звичайного симплексного методу. У разі залежності від параметра компонент вектора правих частин обмежень, тобто рішення задачі пошуку екстремуму функції
за умов
Приклад 2.
за умов
Приклад 3.
за умов
Для того щоб вирішити задачу, достатньо вирішити двоїсту задачу до неї, яка має вигляд
за умов
- Предмет математичного моделювання.
- Моделювання в економіці.
- 3. Класификація економіко – математичних моделей. Формальна класіфикація моделей.
- 4. Задачі планування та організації виробництва.
- 4.1. Задача про максимальну рентабельність підприємства.
- 4.2. Задача про завантаження обладнання.
- Питання для самоконтролю.
- Тема 1. Предмет, методи і завдання дисципліни. Класифікація задач. Лекція 2
- Задачі математичного програмування.
- 2. Класифікація методів математичного програмування.
- 3. Модель міжгалузевого балансу „Витрати - випуск”.
- Коефіціети прямих та побічних витрат.
- Питання для самоконтролю.
- Тема 2.Загальна задача лінійного програмування та деякі з методів її розв’язування Лекція 3 Тема лекції: Основні теореми та властивості задач лінійного програмування (лп).
- 1. Загальна форма задачі лінійного програмування (лп).
- 2. Форми запису загальної задачі лп.
- 3. Основні теореми та властивості задачі лп.
- Питання для самоконтролю.
- Тема 2.Загальна задача лінійного програмування та деякі зметодів її розв’язування Лекція 4 Тема лекції: Графічний метод розв’язування задач лп.
- 2. Графічний метод розв’язування задач лп з
- 3. Приклади розв’язування задач лп графічним методом.
- Питання для самоконтролю.
- Тема 2. Загальна задача лінійного програмування та деякі з методів її розв’язання Лекція 5 Тема лекції: Розв’язання задач лп симплекс-методом.
- 1. Симплекс-метод із стандартним базисом.
- 2. Теоретичні основи симплекс-метода.
- 3. Поняття виродженності задач лп.
- Тема 2. Загальна задача лінійного програмування та деякі з методів її розв’язування Лекція 6 Тема лекції: Розв’язання задач лп симплекс-методом (продовження)
- 4. Правило уникнення зациклювання при застосуванні симплекс-методу.
- 5. Метод штучної базиси розв’язування задач лп.
- 6. Приклад вирішення задачі лп методом штучної бази.
- Питання для самоконтролю.
- Тема 3. Транспортна задача. Лекція 7 Тема лекції: Транспортна задача
- 1 Економічна та математична моделі транспортної задачі.
- 2 Основні теореми транспортної задачі.
- 3. Метод північно-західного кута (діагональний.)
- Тема 3. Транспортна задача. Лекція 8 Тема лекції: Транспортна задача (продовження)
- 5. Метод потенціалів.
- 6. Приклад вирішення транспортної задачі.
- 7. Ускладнені задачі транспортного типу.
- Тема 3. Транспортна задача. Лекція 9 Тема лекції: Транспортна задача (продовження)
- Задача про призначення.
- Розподільчи задачі загального типу.
- Модель розподільчої задачі
- Етапи розв’язання розподільчої задачі
- Приклад вирішення задачі типу тз.
- Питання для самоконтролю.
- Тема 4. Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач. Лекція 10. Тема лекції: Двоїста задача лінійного програмування
- 1 Математичні моделі двоїстих задач.
- 3 Взаємозв’язок розв’язків прямої та двоїстої задач.
- Питання для самоконтролю.
- Тема 5. Цілочислові та параметричні задачі лінійного програмування
- Тема лекції: Узагальнення задачі лінійного програмування.
- Задачі цілочислового програмування.
- 2. Метод Гоморі.
- 3. Параметричне лінійне програмування.
- Питання для самоконтролю.
- Тема 6. Елементи теорії ігор
- Тема лекції: Матричні ігри
- 1. Постановка задач теорії парних ігор з нульовою сумою.
- Задачі з сідловою точкою. Задачі в чистих стратегіях.
- Ігри в мішаних стратегіях. Основна теорема теорії ігор.
- Тема 6. Елементи теорії ігор
- Тема лекції: Матричні ігри (продовження)
- 4. Графічний метод розв’язання теорії ігор.
- 5. Зведення задач теорії ігор до задач лп.
- Зведення задачі лп до матричної гри.
- Питання для самоконтролю.
- Тема 7. Нелінійні оптимізаційні моделі економічних систем
- Тема лекції: Задача дробово-лінійного програмування
- Постановка задачі дробово-лінійного програмування.
- 2. Приведення задачі дробово-лінійного програмування до задачі лінійного програмування.
- 3. Розв’янання задач дробово-лінійного програмування.
- 4. Графічне розв’язання задачі дробово-лінійного програмування.
- Питання для самоконтролю.
- Тема 7. Нелінійні оптимізаційні моделі економічних систем.
- Тема лекції: Задачі нелінійного програмування
- 1. Класичні методи розв’язання задач нелінійного програмування.
- 2. Метод множників Лагранжа.
- 3. Задачі опуклого програмування.
- Задачі опуклого програмування.
- Питання для самоконтролю.
- Тема 7. Нелінійні оптимізаційні моделі економічних систем.
- Тема лекції: Основні поняття теорії варіаційного числення
- Поняття про функціонал.
- 2. Екстремум функціоналу.
- 3. Класичні задачі варіаційного числення.
- 4. Варіація функції та приріст функціоналу.
- 5. Перша та друга варіації функціоналу.
- Питання для самоконтролю.