7.8. Максимізація опуклої цільової функції

Розглянемо випадок, при якому всі обмеження лінійні, а цільова функція , що мінімізується, опукла. Про таку цільову функцію іноді говорять, що вона відбиває економічність укрупнення. Як і раніше припустимо, що регулярна і має кінцевий максимум з на множини припустимих значень х. Разом з тим, немає необхідності робити допущення, що всі часткові похідні dc/dx_j визначені та безперервні при всіх значеннях х, що задовольняють обмеженням. Допущення про опуклість сама по собі забезпечує безперервність у внутрішній частині області допустимих рішень; на границях цієї області функція може бути розривною. Так, наприклад, може включати умовно-постійні витрати на операції по переналагодженню, що виникають тільки при строго позитивних x_j. Можна довести наступну теорему.

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

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

Розглянемо модель розподілу зусиль. нехай модель має вигляд

Максимізувати (7.48)

при виконанні одного лінійного обмеження

(7.49)

де всі та є безперервними перемінними. Припустимо, що є опуклою функцією, при цьому всі . Тоді в сформульованій вище теоремі затверджується, що існує оптимальна стратегія, для якої позитивним є значення тільки однієї . Оптимальну можна знайти, порівнюючи значення при j = 1, 2, ..., s. Якщо є т лінійних обмежень, оптимальне рішення можна знайти, порівнюючи значення цільової функції для всіх можливих базисних рішень, яких існує не більше , тобто не більш числа сполучень із п по т. Якщо т мале або п невелике у порівнянні з т, такий перебір здійснимо на потужній ЕОМ. Наприклад, при т = 2 необхідно розглянути усього п(п – 1)/2 можливих варіантів.

Другий приклад – модель управління запасами з детермінованим попитом та увігнутою функцією витрат, приведена раніше.

Якщо помножити цільову функцію на –1 й тим самим змінити напрямок оптимізації, то одержимо модель, що відповідає припущенням про максимізації опуклої цільової функції при лінійних обмеженнях.

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

Кожна з цих програм відповідає деякій схемі розподілу за часом відрізків зі строго позитивним обсягом випуску (випуск для відрізка 1 завжди позитивний) і задовольняє теоремі про вид оптимальної програми. Повний перебір можна реалізувати, якщо сукупна сума витрат є увігнутою функцією загального виду від усіх перемінних, що характеризують обсяг виробництва та рівень запасів; він легко може бути здійснений на потужній ЕОМ при . Однак якщо цільова функція до того ж сепарабельна по відрізках, то має бути застосований відповідний алгоритм, так що обсяг обчислювальних операцій скорочується до розгляду можливих варіантів.

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

• Запитання для самоконтролю

1. Що таке нелінійне програмування ?

2. Коли рішення є завжди оптимальним ?

3. В яких випадках використовується максимізація функції багатьох перемінних без обмежень ?

4. Яка умова існування максимуму ?

5. В яких випадках використовується метод найшвидшого підйому ?

6. Які задачі квадратичного програмування ?

7. В яких задачах використовується метод сеперабельного програмування ?

8. Яким методом лінеаризується нелінійна цільова функція ?

9. У яких випадках використовується метод максимізації опуклої цільової функції ?

131