Лінійне та нелінійне програмування

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Севастопольський національний технічний університет
Кафедра кібернетики і обчислювальної техніки
Пояснювальна записка
до курсового проекту
з дисципліни
«Прикладна математика»
Виконав: ст. гр. М-21Д
Ткаченко К. С.
зач. книжка № 040xxx
варіант № 22
Перевірив: ст. преп.
Балакірєва І. А.
Севастополь - 2006

Зміст
Введення. 4
1 Загальна формулювання завдання на курсовий проект. 5
2 Лінійне програмування. 7
2.1 Завдання лінійного програмування. 7
2.1.1 Постановка задачі лінійного програмування. 7
2.1.2 Математична модель задачі лінійного програмування. 8
2.1.3 Графічний метод. 9
2.1.4 Алгебраїчний метод. 10
2.1.5 Метод симплекс-таблиці .. 12
2.1.6 Метод допустимого базису. 14
2.1.7 Рішення двоїстої задачі. 17
2.2 Завдання цілочисельного лінійного програмування. 19
2.2.1 Постановка задачі цілочислового лінійного програмування. 19
2.2.2 Метод Гоморі. 20
2.2.3 Метод гілок і меж. 22
2.3 Завдання цілочисельного лінійного програмування з Булевського змінними 24
2.3.1 Постановка задачі цілочислового лінійного програмування з Булевського змінними. 24
2.3.2 Метод Баллаша. 25
2.3.3 Визначення зниження трудомісткості обчислень. 26
3 Нелінійне програмування. 27
3.1 Задача пошуку глобального екстремуму функції. 27
3.1.1 Постановка задачі пошуку глобального екстремуму функції. 27
3.1.2 Метод пошуку по координатній сітці з постійним кроком і метод випадкового пошуку. Порівняння результатів обчислень. 28
3.2 Завдання одномірної оптимізації функції. 29
3.2.1 Постановка завдання одномірної оптимізації функції. 29
3.2.2 Метод дихотомії. 30
3.2.3 Метод Фібоначчі. 31
3.2.4 Метод кубічної апроксимації. 32
3.3 Завдання багатовимірної оптимізації функції. 33
3.3.1 Постановка завдання багатовимірної оптимізації функції. 33
3.3.2 Метод Хука - Дживса. 34
3.3.3 Метод найшвидшого спуску (метод Коші) 36
3.3.4 Метод Ньютона. 37
3.3.5 Порівняння результатів обчислень. 38
Висновок. 39
Бібліографічний список. 40
ДОДАТОК. 41
А Текст програми глобальної багатовимірної оптимізації. 41
Б. Результати роботи програми .. 44


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


1 Загальна формулювання завдання на курсовий проект
Варіант завдання для задачі лінійного програмування (ЗЛП) представляє собою область допустимих рішень ЗЛП і цільову функцію. Для того щоб визначити, яке значення має досягати цільова функція - мінімальне або максимальне, необхідно знайти градієнт цільової функції. Якщо напрямок градієнта збігається з напрямком стрілки у цільової функції у варіанті завдання, то в задачі визначається максимальне значення цільової функції, інакше - мінімальне.
Отже, завдання за рішенням ЗЛП полягає в наступному: побудувати математичну модель ЗЛП відповідно до варіанту; отримати рішення ЗЛП графічним методом; вирішити ЗЛП алгебраїчним методом; вирішити ЗЛП методом симплекс-таблиці; визначити допустиме рішення ЗЛП методом введення штучного базису; побудувати ЗЛП, двоїсту даної, вирішити це завдання і дослідити взаємозв'язок між рішеннями взаімодвойственних завдань.
Варіант для задачі цілочисельного лінійного програмування (ЗЦЛП) представляє собою область допустимих рішень ЗЛП і цільову функцію. Завдання полягає в наступному: вирішити ЗЦЛП, за умови цілочисельності всіх змінних, що входять у завдання методом гілок і меж і методом відтинають площин (методом Гоморі).
Варіант для задачі цілочисельного лінійного програмування з Булевського змінними складається студентом самостійно з урахуванням наступних правил: у задачі використовується не менше 5 змінних, не менше 4 обмежень, коефіцієнти обмежень і цільової функції вибираються довільно, але таким чином, щоб система обмежень була сумісна. Завдання полягає в тому, щоб вирішити ЗЦЛП з Булевського змінними, використовуючи алгоритм Баллаша і визначити зниження трудомісткості обчислень по відношенню до вирішення задачі методом повного перебору.
Завдання на пошук глобального екстремуму функції полягає в написанні програми. Програма для пошуку екстремуму функції може бути розроблена на будь-якому алгоритмічній мові. Завдання полягає в наступному: 1) знайти точку глобального екстремуму функції f (X) методом пошуку по координатній сітці з постійним кроком, 2) знайти точку глобального екстремуму функції f (X) методом випадкового пошуку; 3) порівняти результати обчислень.
Завдання для знаходження одновимірного локального екстремуму функції (одномірна оптимізація) полягає в тому, щоб виконати пошук мінімуму заданої функції методом дихотомії (3-4 ітерації), уточнити інтервал пошуку методом Фібоначчі (3 ітерації) і завершити пошук методом кубічної апроксимації.
Завдання для знаходження багатовимірного локального екстремуму функції (багатовимірна оптимізація) полягає в тому, щоб мінімізувати функцію, застосовуючи такі методи: нульового порядку - Хука-Дживса, першого порядку - найшвидшого спуску (Коші), другого порядку - Ньютона, і провести порівняльний аналіз методів оптимізації за кількістю ітерацій, необхідних для пошуку екстремуму при фіксованій точності і початкових координатах пошуку X (0) = [-1, -1] T.


2 Лінійне програмування
2.1 Завдання лінійного програмування
2.1.1 Постановка задачі лінійного програмування
Побудувати математичну модель ЗЛП відповідно до варіанту. Отримати рішення ЗЛП графічним методом. Вирішити ЗЛП алгебраїчним методом. Вирішити ЗЛП методом симплекс-таблиці. Визначити допустиме рішення ЗЛП методом введення штучного базису. Побудувати ЗЛП, двоїсту даної, вирішити це завдання і дослідити взаємозв'язок між рішеннями взаімодвойственних завдань.


2.1.2 Математична модель задачі лінійного програмування
AB: ; ;

BC: ; ;

CD: ; ;

DE: ; ;

F: ; ;

Математична модель:


2.1.3 Графічний метод
Обчислюємо значення цільової функції у всіх вершинах симплекса і вибираємо з них найменша. Це і буде оптимальне рішення.
F A = 1
F B = -8
F C = -14
F D = 0
F E = 3
C (2, 4)

F = -14


2.1.4 Алгебраїчний метод


x 2, x 4, x 5, x 6 - базисні змінні, x 1, x 3 - вільні змінні

x 1 ↑ F ↑ x 3 ↑ F ↓ Вибираємо x 3 ↔ x 4
x 2, x 3, x 5, x 6 - базисні змінні, x 1, x 4 - вільні змінні

x 1 ↑ F ↓ x 4 ↑ F ↑ Вибираємо x 1 ↔ x 5
x 1, x 2, x 3, x 6 - базисні змінні, x 4, x 5 - вільні змінні

x 1 ↑ F ↑ x 4 ↑ F ↑
X = (2, 4, 7, 0, 0, 5)
F = -14


2.1.5 Метод симплекс-таблиці


Наведемо до канонічного вигляду:
x 2, x 4, x 5, x 6 - базисні змінні, x 1, x 3 - вільні змінні


b
x 1
x 3
x 2
1
2
-1
1
-3
1

x 4
1
-3
1
1
1
-3
1
x 5
12
-1
2
6
-2
6
-2
x 6
4
3
-1
1
-3
1
F
-4
-9
4
-4
12
-4

b
x 1
x 4
x 2
2
-1
1
2
1 / 5
-2 / 5
x 3
1
-3
1
6
3 / 5
-6 / 5

x 5
10
5
-2
2
2
1 / 5
-2 / 5
x 6
5
0
1
0
0
0
F
-8
3
-4
-6
-3 / 5
6 / 5

b
x 5
x 4
x 2
4
1 / 5
3 / 5
x 3
7
3 / 5
-1 / 5
x 1
2
1 / 5
-2 / 5
x 6
5
0
1
F
-14
-3 / 5
-14 / 5
X = (2, 4, 7, 0, 0, 5)
F = -14

2.1.6 Метод допустимого базису







b
x 1
x 2
x 3
x 4
x 5
x 6
F
0
-1
4
0
0
0
0
1 / 2
1 / 2
1 / 2
-1 / 2
0
0
0

ξ 1
1
2
1
-1
0
0
0
1 / 2
1 / 2
1 / 2
1 / 2
-1 / 2
0
0
0
ξ 2
2
-1
1
0
1
0
0
14 / 3
1 / 2
1 / 2
1 / 2
-1 / 2
0
0
0
ξ 3
14
3
2
0
0
1
0
3
-3 / 2
-3 / 2
-3 / 2
3 / 2
0
0
0
ξ 4
3
1
-1
0
0
0
1
-1 / 2
-1 / 2
-1 / 2
1 / 2
0
0
0
f
20
5
3
-1
1
1
1
-5 / 2
-5 / 2
-5 / 2
5 / 2
0
0
0


b
ξ 1
x 2
x 3
x 4
x 5
x 6
F
1 / 2
1 / 2
9 / 2
-1 / 2
0
0
0
5 / 2
-1 / 2
-3 / 2
1
0
0
1
x 1
1 / 2
1 / 2
1 / 2
-1 / 2
0
0
0
5 / 2
-1 / 2
-3 / 2
1
0
0
1
ξ 2
5 / 2
1 / 2
3 / 2
-1 / 2
1
0
0
5 / 2
-1 / 2
-3 / 2
1
0
0
1
ξ 3
25 / 2
-3 / 2
1 / 2
3 / 2
0
1
0
25 / 3
-15 / 2
3 / 2
9 / 2
-3
0
0
-3

ξ 4
5 / 2
-1 / 2
-3 / 2
1 / 2
0
0
1
5
5
-1
-3
2
0
0
2
f
35 / 2
-5 / 2
1 / 2
3 / 2
1
1
1
-15 / 2
3 / 2
9 / 2
-3
0
0
-3

b
ξ 1
x 2
ξ 4
x 4
x 5
x 6
F
3
0
3
1
0
0
1
-3
0
-3 / 5
9 / 5
0
-3 / 5
9 / 5
x 1
3
0
-1
1
0
0
1
1
0
1 / 5
-3 / 5
0
1 / 5
-3 / 5
ξ 2
5
0
0
1
1
0
1
0
0
0
0
0
0
0

ξ 3
5
0
5
-3
0
1
-3
1
1
0
1 / 5
-3 / 5
0
1 / 5
-3 / 5
x 3
5
-1
-3
2
0
0
2
3
0
3 / 5
-9 / 5
0
3 / 5
-9 / 5
f
10
-1
5
-3
1
1
-2
-5
0
-1
3
0
-1
3


b
ξ 1
ξ 3
ξ 4
x 4
x 5
x 6
F
0
0
-3 / 5
14 / 5
0
-3 / 5
14 / 5
-14
0
0
-14 / 5
-14 / 5
0
-14 / 5
x 1
4
0
1 / 2
2 / 5
0
1 / 5
2 / 5
10
-2
0
0
-2 / 5
-2 / 5
0
-2 / 5

ξ 2
5
0
0
1
1
0
1
5
5
0
0
1
1
0
1
x 2
1
0
1 / 5
-3 / 5
0
1 / 5
-3 / 5
3
0
0
3 / 5
3 / 5
0
3 / 5
x 3
8
-1
3 / 5
1 / 5
0
3 / 5
1 / 5
40
-1
0
0
-1 / 5
-1 / 5
0
-1 / 5
f
5
-1
-1
0
1
0
1
-5
0
0
-1
-1
0
-1




b
ξ 1
ξ 3
ξ 4
x 4
x 5
ξ 2
F
-14
0
-3 / 5
0
-14 / 5
-3 / 5
-14 / 5
x 1
2
0
1 / 5
0
-2 / 5
1 / 5
-2 / 5
x 6
5
0
0
1
1
0
1
x 2
4
0
1 / 5
0
3 / 5
1 / 5
-3 / 5
x 3
7
-1
3 / 5
0
-1 / 5
3 / 5
-1 / 5

f
0
-1
-1
-1
0
0
-1

b
x 4
x 5
F
-14
-14 / 5
-3 / 5
x 6
5
1
0
x 2
4
3 / 5
1 / 5
x 3
7
-1 / 5
3 / 5
x 1
2
-2 / 5
1 / 5
Допустиме базисне оптимальне рішення:
X = (2, 4, 7, 0, 0, 5)
F = -14

2.1.7 Рішення двоїстої задачі
Пряма задача:

Двоїста задача:

Наводимо до канонічного вигляду:

y 1, y 3 - базисні змінні, y 2, y 4, y 5, y 6 - вільні змінні


b
y 2
y 4
y 5
y 6

y 1
14
5
-5
2
-3
14 / 5
14 / 5
1 / 5
-1
2 / 5
-3 / 5
y 3
9
3
-3
1
-2
3
-42 / 5
-3 / 5
3
-6 / 5
9 / 5
Ф '
112
35
-40
12
-25
-98
-7
35
-14
21
b
y 2
y 4
y 5
y 6
y 1
14 / 5
1 / 5
-1
2 / 5
-3 / 5
y 3
3 / 5
-3 / 5
0
-1 / 5
-1 / 5
Ф '
14
-7
-5
-2
-4
x 1
x 2
x 3
x 4
x 5
x 6






y 5
y 6
y 1
y 2
y 3
y 4
2
4
7
0
0
5
F '= Ф' = 14
X = (2,4,7,0,0,5)
F =-F '= -14

2.2 Завдання цілочисельного лінійного програмування
2.2.1 Постановка задачі цілочислового лінійного програмування
Вирішити ЗЦЛП, за умови цілочисельності всіх змінних, що входять у завдання, методом гілок і меж і методом відтинають площин (методом Гоморі).



2.2.2 Метод Гоморі



x 3, x 4 - базисні змінні, x 1, x 2 - вільні змінні


b
x 1
x 2
x 3
11
2
3
11 / 2
-5
-1 / 2
-1 / 2

x 4
10
4
1
10 / 4
5 / 2
1 / 4
1 / 4
F '
0
2
1
-5
-1 / 2
-1 / 2

b
x 4
x 2

x 3
6
-1 / 2
5 / 2
12 / 5
12 / 5
-1 / 5
2 / 5
x 1
5 / 2
1 / 4
1 / 4
10
-3 / 5
1 / 20
-1/10
F '
-5
-1 / 2
1 / 2
-6 / 5
1 / 10
-1 / 5
b
x 1
x 2
x 3
12 / 5
-1 / 5
2 / 5
x 4
19/10
3 / 10
-1/10
F '
-31 / 5
-2 / 5
-1 / 5
X = (19/10, 12 / 5, 0, 0)
F =-F '= 31 / 5
Складаємо нерівність Гоморі:


b
x 4
x 3
F '
-31 / 5
-2 / 5
-1 / 5
1 / 5
1 / 10
-1 / 2
x 2
12 / 5
-1 / 5
2 / 5
-2 / 5
-1 / 5
1
x 1
19/10
3 / 10
-1/10
1 / 10
-1 / 4

u 2
-2 / 5
-1 / 5
-2 / 5
1
1 / 2
-5 / 2
b
x 4
u 2
F '
-6
-3/10
-1 / 2
x 2
2
-2 / 5
1
x 1
2
7 / 20
-1 / 4
x 3
1
1 / 2
-5 / 2
X = (2, 2, 1, 0)
F =-F '= 6

2.2.3 Метод гілок і меж
x 2
x 2 ≤ 2
x 2 ≥ 3
2 12 / 5 3

b
x 1
x 2
x 3
12 / 5
-1 / 5
2 / 5
x 4
19/10
3 / 10
-1/10
F '
-31 / 5
-2 / 5
-1 / 5
Завдання № 1


Наводимо до канонічного вигляду:
x 3, x 4, x 5 - базисні змінні, x 1, x 2 - вільні змінні


b
x 1
x 2
x 3
11
2
3
11 / 2
-5
-1 / 2
-1 / 2

x 4
10
4
1
5 / 2
5 / 2
1 / 4
1 / 4
x 5
2
0
1
0
0
0
F '
0
2
1
-5
-1 / 2
-1 / 2

b
x 4
x 2
x 3
6
-1 / 2
5 / 2
12 / 5
-5
0
-5 / 2
x 1
5 / 2
1 / 4
1 / 4
10
-1 / 2
0
-1 / 4

x 5
2
0
1
2
2
0
1
F '
-5
-1 / 2
1 / 2
-1
0
-1 / 2
b
x 4
x 5
x 3
1
-1 / 2
-5 / 2
x 1
2
1 / 4
-1 / 4
x 2
2
0
1
F '
-6
-1 / 2
-1 / 2
X = (2, 2, 1, 0, 0)
F '= -6
F =-F '= 6
Завдання № 2
Вирішуємо задачу з x 2 ≥ 3 в підсистемі «Пошук рішення» системи Excel. Отримуємо допустиме не оптимальне рішення F = 5, X = (1, 3)
= 2 * $ B $ 1 + $ B $ 2
1
= 2 * $ B $ 1 +3 * $ B $ 2
11
3
= 4 * $ B $ 1 + $ B $ 2
10
= $ B $ 2
3
5
1
11
11
3
7
10
3
3
Обмеження
Осередок
Ім'я
Значення
Формула
Статус
Різниця
$ C $ 1
11
$ C $ 1 <= $ D $ 1
пов'язане
0
$ C $ 2
7
$ C $ 2 <= $ D $ 2
не пов'язаний.
3
$ C $ 3
3
$ C $ 3> = $ D $ 3
пов'язане
0

2.3 Завдання цілочисельного лінійного програмування з Булевського змінними
2.3.1 Постановка задачі цілочислового лінійного програмування з Булевського змінними
Скласти самостійно варіант для задачі цілочисельного лінійного програмування з Булевського змінними з урахуванням наступних правил: у задачі використовується не менше 5 змінних, не менше 4 обмежень, коефіцієнти обмежень і цільової функції вибираються довільно, але таким чином, щоб система обмежень була сумісна. Завдання полягає в тому, щоб вирішити ЗЦЛП з Булевського змінними, використовуючи алгоритм Баллаша і визначити зниження трудомісткості обчислень по відношенню до вирішення задачі методом повного перебору.



2.3.2 Метод Баллаша

x 4
x 3
x 2
x 1
x 5
Виконання обмежень
Значення F
0
1
2
3
4
5
1
0
0
0
0
0
0
Fф = 0
2
0
0
0
0
1
44
3
0
0
0
1
0
17
4
0
0
0
1
1
61
5
0
0
1
0
0
13
6
0
0
1
0
1
57
7
0
0
1
1
0
30
8
0
0
1
1
1
74
9
0
1
0
0
0
-10
+
+
+
+
+
Fф =- 10
10
0
1
0
0
1
34
11
0
1
0
1
0
7
12
0
1
0
1
1
51
13
0
1
1
0
0
3
14
0
1
1
0
1
47
15
0
1
1
1
0
20
16
0
1
1
1
1
64
17
1
0
0
0
0
-49
+
+
+
+
+
Fф =- 49
18
1
0
0
0
1
-5
19
1
0
0
1
0
-32
20
1
0
0
1
1
12
21
1
0
1
0
0
-36
22
1
0
1
0
1
8
23
1
0
1
1
0
-19
24
1
0
1
1
1
25
25
1
1
0
0
0
-59
+
+
+
+
+
Fф =- 59
26
1
1
0
0
1
-15
27
1
1
0
1
0
-42
28
1
1
0
1
1
2
29
1
1
1
0
0
-46
30
1
1
1
0
1
-2
31
1
1
1
1
0
-29
32
1
1
1
1
1
15
Фільтруюче обмеження:


2.3.3 Визначення зниження трудомісткості обчислень
Рішення задачі методом повного перебору становить 6 * 2 5 = 192 обчислених вираження. Рішення задачі методом Баллаша становить 3 * 6 + (5 лютого -3) = 47 обчислених виразів. Разом зниження трудомісткості обчислень по відношенню до вирішення задачі методом повного перебору становить .


3 Нелінійне програмування
3.1 Задача пошуку глобального екстремуму функції
3.1.1 Постановка задачі пошуку глобального екстремуму функції
Необхідно написати програма для пошуку екстремуму функції. Завдання полягає в наступному: 1) знайти точку глобального екстремуму функції f (X) методом пошуку по координатній сітці з постійним кроком, 2) знайти точку глобального екстремуму функції f (X) методом випадкового пошуку; 3) порівняти результати обчислень.



3.1.2 Метод пошуку по координатній сітці з постійним кроком і метод випадкового пошуку. Порівняння результатів обчислень
Метод пошуку глобального мінімуму, званий методом пошуку по координатній сітці, є надійним, але застосовний тільки для задач малої розмірності (n <4). Неправильний вибір початкового кроку сітки може привести до того, що насправді один з локальних мінімумів може бути прийнятий як глобальний. З усіх значень цільової функції, обчислених у вузлах координатної сітки, обирається мінімальне. Результат: кількість випробувань 905, f (X *) = -2.500, X * = (-0.500; 2.000)
Метод випадкового пошуку характеризується навмисним введенням елемента випадковості в алгоритм пошуку. Цей метод передбачає наявність генератора випадкових чисел, звертаючись до якого, в будь-який потрібний момент часу можна отримати реалізацію випадкового вектора з заданим законом розподілу. Результат: кількість випробувань 299, f (X *) = -2.469, X * = (-0.677; 2.173).
Розрахунок в системі MathCAD: f (X *) = -2.500, X * = (-0.500; 2.000)

Як бачимо, метод випадкового пошуку скоротив число випробувань на 66%, при цьому відносна похибка становить 1%. Тобто ми досягли значного скорочення обчислень з невеликою відносною похибкою.

3.2 Завдання одномірної оптимізації функції
3.2.1 Постановка завдання одномірної оптимізації функції
Завдання для знаходження одновимірного локального екстремуму функції (одномірна оптимізація) полягає в тому, щоб виконати пошук мінімуму заданої функції методом дихотомії (3-4 ітерації), уточнити інтервал пошуку методом Фібоначчі (3 ітерації) і завершити пошук методом кубічної апроксимації.



3.2.2 Метод дихотомії

Ітерація 1






Ітерація 2






Ітерація 3






Ітерація 4





Після чотирьох ітерацій одержимо:


3.2.3 Метод Фібоначчі


Ітерація 1




Ітерація 2




Ітерація 3





Ітерація 4
Пошук закінчено. Довжина інтервалу:



3.2.4 Метод кубічної апроксимації












3.3 Завдання багатовимірної оптимізації функції
3.3.1 Постановка завдання багатовимірної оптимізації функції
Мінімізувати функцію, застосовуючи такі методи: нульового порядку - Хука-Дживса, першого порядку - найшвидшого спуску (Коші), другого порядку - Ньютона, і провести порівняльний аналіз методів оптимізації по кількості ітерацій, необхідних для пошуку екстремуму при фіксованій точності і початкових координатах пошуку X (0) = [-1, -1] T.


3.3.2 Метод Хука - Дживса

Ітерація 1
1 Досліджує пошук

2 Пошук за зразком

Ітерація 2
1 Досліджує пошук



2 Пошук за зразком

Ітерація 3
1 Досліджує пошук

2 Пошук за зразком

Пошук завершено


3.3.3 Метод найшвидшого спуску (метод Коші)



Ітерація 1. Рахунок ітерацій k = 0











Ітерація 2. Рахунок ітерацій k = 1

Пошук завершено


3.3.4 Метод Ньютона


3.3.5 Порівняння результатів обчислень
Метод Хука-Дживса сходиться за три ітерації, при цьому відбувається обчислення значення функції в 13 точках, всього 38 обчислень. Метод найшвидшого спуску (метод Коші) сходиться за одну ітерацію, 9 обчислень. Метод Ньютона сходиться за одну ітерація, 9 обчислень. Методи Коші і Ньютона в даному випадку сходяться за одну ітерацію, оскільки функція являє собою функцію для сфери (лінії рівня - концентричні кола) і напрям, протилежний градієнту функції, спрямоване на точку мінімуму. З цього можна зробити висновок, що у разі функцій такого виду використання методу Хука-Дживса нераціонально.


Висновок
Процес проектування інформаційних систем, що реалізують нову інформаційну технологію, безперервно вдосконалюється. У центрі уваги інженерів-системотехніків виявляються все більш складні системи, що утрудняє використання фізичних моделей і підвищує значущість математичних моделей і машинного моделювання систем. Машинне моделювання стало ефективним інструментом дослідження і проектування складних систем. Актуальність математичних моделей безперервно зростає через їх гнучкості, адекватності реальним процесам, невисокою вартістю реалізації на базі сучасних ПЕОМ. Всі великі можливості надаються користувачеві, тобто фахівця з моделювання систем засобами обчислювальної техніки. Особливо ефективним є застосування моделювання на ранніх етапах проектування автоматизованих систем, коли ціна помилкових рішень найбільш значна.
Сучасні обчислювальні засоби дозволили суттєво збільшити складність використовуваних моделей при вивченні систем, з'явилася можливість побудови комбінованих, аналітико-імітаційних моделей, що враховують все різноманіття чинників, що мають місце в реальних системах, тобто використання моделей, більш адекватних досліджуваним явищам.


Бібліографічний список
1 Лященко І.М. Лінійне і нелінійне програмування / І. М. Лященко, Є. А. Карагодова, Н. В. Чернікова, Н. З. Шор. - К.: «Вища школа», 1975, 372 с.
2 Методичні вказівки для виконання курсового проекту з дисципліни «Прикладна математика» для студентів спеціальності «Комп'ютерні системи та мережі» денної та заочної форм навчання / Укл.: І. О. Балакірєва, А.В.Скатков-Севастополь: Вид-во СевНТУ, 2003. - 15 с.
3 Методичні вказівки з вивчення дисципліни «Прикладна математика», розділ «Методи глобального пошуку та одномірної мінімізації» / Укл. А. В. Скатков, І. О. Балакірєва, Л. А. Литвинова - Севастополь: Вид-во СевГТУ, 2000. - 31с.
4 Методичні вказівки для вивчення дисципліни «Прикладна математика» для студентів спеціальності «Комп'ютерні системи та мережі» Розділ «Рішення задач цілочисельного лінійного програмування» денної та заочної форм навчання / Укл.: І. О. Балакірєва, О. В. Скатков - Севастополь: Вид-во СевНТУ, 2000. - 13 с.

ДОДАТОК
А Текст програми глобальної багатомірної оптимізації
{$ APPTYPE CONSOLE}
program GlobalMinimize;
const
large = 10e99;
var
a1, a2, b1, b2: real;
a1n, a2n, b1n, b2n: real;
fmin, x1, x2: real;
alpha, dV, eps: real;
Rho, P: real;
fT, fS: real;
d1, d2, dx1, dx2: real;
x1min, x2min: real;
i, N: integer;
t: boolean;
function f (x1, x2: real): real;
begin
f: = 2 * sqr (x1) + 2 * x1 * x2 + sqr (x2) - 2 * x1 - 3 * x2
end;
function ceil (x: real): integer;
var a: integer;
begin
a: = trunc (x);
if frac (x)> 0 then
a: = a + 1;
ceil: = a
end;
function max (a, b: real): real;
begin
if a> b then
max: = a
else
max: = b
end;
function min (a, b: real): real;
begin
if a <b then
min: = a
else
min: = b
end;
begin
randomize;
writeln ('Пошук глобального багатовимірного мінімуму функції');
writeln ('(для курсового проекту з прикладної математики)');
writeln ('Автор: Ткаченко К.С. М-21Д');
writeln;
writeln ('Введіть інтервал зміни x1');
write ('Введіть a1:'); readln (a1);
write ('Введіть b1:'); readln (b1);
writeln ('Введіть інтервал зміни x2');
write ('Введіть a2:'); readln (a2);
write ('Введіть b2:'); readln (b2);
write ('Введіть похибка eps:'); readln (eps);
write ('Введіть ймовірність пошуку P:'); readln (P);
write ('Введіть коефіцієнт alpha:'); readln (alpha);
write ('Введіть коефіцієнт dV:'); readln (dV);
writeln;
writeln ('Алгоритм пошуку глобального мінімуму по координатної' +
'Сітці з рівномірним кроком');
writeln;
t: = false; N: = 0;
fS: = large; fmin: = large;
a1n: = a1; a2n: = a2; b1n: = b1; b2n: = b2;
repeat
d1: = b1n - a1n; d2: = b2n - a2n;
dx1: = d1 / alpha; dx2: = d2 / alpha;
x1: = a1n; x2: = a2n;
fT: = f (x1, x2);
N: = N + 1;
if fT <fmin then
begin
fmin: = fT;
x1min: = x1; x2min: = x2;
end;
repeat
repeat
x1: = x1 + dx1; (* Крок 1 *)
fT: = f (x1, x2);
N: = N + 1;
if fT <fmin then (* Крок 2 *)
begin
fmin: = fT;
x1min: = x1; x2min: = x2;
end;
until x1> b1n; (* Крок 3 *)
x1: = a1n; x2: = x2 + dx2; (* Крок 4 *)
fT: = f (x1, x2); (* Крок 5 *)
N: = N + 1;
if fT <fmin then (* Крок 6 *)
begin
fmin: = fT;
x1min: = x1; x2min: = x2;
end;
until x2> b2n; (* Крок 7 *)
if abs (fS - fmin)> eps then (* Крок 8 *)
begin (* Крок 9 *)
fS: = fmin;
a1n: = max (x1min-dx1, a1n); b1n: = min (x1min + dx1, b1n);
a2n: = max (x2min-dx2, a2n); b2n: = min (x2min + dx2, b2n);
end
else t: = true; (* Крок 10 *)
until t;
writeln ('Кількість випробувань N =', N);
writeln ('fmin =', fmin: 6: 3);
writeln ('x1min =', x1min: 6: 3);
writeln ('x2min =', x2min: 6: 3);
writeln;
writeln ('Алгоритм пошуку глобального мінімуму функції' +
'Методом випадкового пошуку');
writeln;
fmin: = large;
x1min: = fmin; x2min: = fmin;
d1: = b1 - a1; d2: = b2 - a2;
Rho: = dV / (d1 * d2);
N: = ceil (ln (1 - P) / ln (1 - Rho));
writeln ('Кількість випробувань N =', N);
for i: = 1 to N do (* Кроки 1, 2 *)
begin
x1: = a1 + random * d1; (* Кроки 3, 4 *)
x2: = a2 + random * d2;
fT: = f (x1, x2); (* Крок 5 *)
if fT <fmin then (* Крок 6 *)
begin
fmin: = fT;
x1min: = x1;
x2min: = x2
end;
end; (* Крок 7 *)
writeln ('fmin =', fmin: 6: 3);
writeln ('x1min =', x1min: 6: 3);
writeln ('x2min =', x2min: 6: 3);
end.

Б. Результати роботи програми

Пошук глобального багатовимірного мінімуму функції
(Для курсового проекту з прикладної математики)
Автор: Ткаченко К.С. М-21Д
Введіть інтервал зміни x1
Введіть a1: -5
Введіть b1: 5
Введіть інтервал зміни x2
Введіть a2: -5
Введіть b2: 5
Введіть похибка eps: 0.0001
Введіть ймовірність пошуку P: 0.95
Введіть коефіцієнт alpha: 20
Введіть коефіцієнт dV: 1
Алгоритм пошуку глобального мінімуму по координатній сітці з рівномірним кроком
Число випробувань N = 905
fmin = -2.500
x1min = -0.500
x2min = 2.000
Алгоритм пошуку глобального мінімуму функції методом випадкового пошуку
Число випробувань N = 299
fmin = -2.469
x1min = -0.677
x2min = 2.173
Додати в блог або на сайт

Цей текст може містити помилки.

Математика | Курсова
772.1кб. | скачати


Схожі роботи:
Нелінійне програмування
Лінійне програмування
Лінійне програмування 2
Лінійне програмування
Динамічне і лінійне програмування
Лінійне програмування 2 лютого
Лінійне програмування 3 лютого
Лінійне програмування симплекс методом Данцига
Лінійне програмування симплекс-методом Данцига
© Усі права захищені
написати до нас