Геометрична інтерпретація задачі

ПАРАМЕТРИЧНА ТА НЕЛІНІЙНА ОПТИМІЗАЦІЯ

Тема 11. Задачі параметричного програмування

Задачі параметричного програмування є узагальненням задач лінійного програмування.

Це узагальнення полягає в тому, що дані задач параметричного програмування вважаються не постійними величинами, а функціями, що певним чином залежать від деяких параметрів.

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

а) постійної – вартості продукції на момент її виготовлення;

б) змінної, що залежить від терміну зберігання продукції.

Цільову функцію задачі оптимального планування такого виробництва можна виразити через коефіцієнти, що лінійно залежать від одного параметра, зокрема від часу .

Часто на практиці зустрічаються задачі, в яких значення коефіцієнтів цільової функції відомі лише наближено.

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

Аналогічно можна провести дослідження для випадку, коли змінюються коефіцієнти системи обмежень.

Розглянемо залежність від параметра тільки коефіцієнтів цільової функції.

Математична модель задачі.

Нехай параметр

,

де і – будь-які дійсні числа.

Необхідно знайти для кожного на відрізку свій вектор

, (1)

що максимізує

(2)

за умов

(3)

У виразі (2) числа і відомі і постійні.

Геометрична інтерпретація задачі.

Нехай система обмежень (3) сумісна і визначає опуклий многокутник .

Рис.1

Рівнянню

(4)

відповідає система гіперплощин, які проходять через початок координат.

Якщо параметру надати деяке значення

, (5)

то гіперплощина займе цілком визначене положення.

Переміщаючи її від початку координат, в напрямку зростання функції, отримаємо розв’язок в точці (рис.1.).

Надамо параметру інше значення і знову знайдемо в області точку оптимуму. Гіперплощина внаслідок зміни параметра t повернеться навколо початку координат на деякий кут.

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

Однак значення функціоналу при зміниться, так як воно дорівнює зваженому відхиленню точки А від початкової гіперплощини.

Нехай при гіперплощина буде паралельною ребру АВ.

Оптимальний розв’язок в цьому випадку досягатиметься в будь-якій точці відрізка АВ.

Покладаючи ( ), отримаємо оптимальний розв’язок у вершині В.

Для цієї вершини буде свій інтервал зміни параметра .

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

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

Якщо многокутник необмежений,

Рис.2

то гіперплощина при деяких значеннях параметра може зайняти таке положення, що виявиться необмеженим.

Положення гіперплощини (рис.2) відповідає необмеженому значенню функції, а положення гіперплощини максимальному.