Курсова робота. „Розв’язування нелінійних задач оптимізації за допомогою пакету Mathcad”

з курсу:

“Методи оптимізації”

на тему:

„Розв’язування нелінійних задач оптимізації за допомогою пакету Mathcad”

Виконав:

ст.гр. ПМ-31

Зелінський Ю.В.

Прийняла:

Уханська О.М.

Львів – 2015

Анотація

В даній курсовій роботі розглянуто методи розв’язування задач нелінійного програмування і застосування до їх розв’язування пакету Mathcad. Розглянуто питання постановки основної задачі нелінійного програмування та її геометричну інтерпретацію. Подано метод множників Лагранжа, теорему Куна-Такера та поняття опуклого програмування.

Зміст

Анотація. 2

Зміст. 3

Вступ. 4

1. Постановка задачі нелінійного програмування. 5

2. Умовний та безумовний екстремуми функції 7

3. Метод множників Лагранжа. 9

4. Опуклі й угнуті функції 12

5. Теорема Куна-Таккера. 13

6. Опукле програмування. 14

7. Розв’язування задачі нелінійного програмування за допомогою пакету Mathcad. 16

Висновок. 19

Список використаної літератури. 20

Вступ

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

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

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

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

1. Постановка задачі нелінійного програмування

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

Загальна задача математичного програмування формулюється так: знайти такі значення змінних , щоб цільова функція набувала екстремального (максимального чи мінімального) значення:

(1.1)

за умов:

(1.2)

(1.3)

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

Розглянемо основні труднощі розв’язування нелінійних задач.

1. Для лінійних задач можна завжди знайти оптимальний розв’язок універсальним методом — симплексним. При цьому не існує проблеми стосовно доведення існування такого розв’язку, тобто в результаті застосування алгоритму симплексного методу завжди отримують один з таких варіантів відповіді:

а) отримали оптимальний розв’язок;

б) умови задачі суперечливі, тобто розв’язку не існує;

в) цільова функція необмежена, тобто розв’язку також не існує.

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

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

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

3. У задачах лінійного програмування точка оптимуму завж­ди була граничною точкою багатогранника допустимих планів. Для нелінійних задач точка, яка визначає оптимальний план, може бути як граничною, так і знаходитися всередині допустимої області розв’язків (планів).

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

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