Навчальний посібник призначений для студентів спеціальностей "Комп'ютерна інженерія" та "Метрологія тв інформаційно-вимірювальна техніка". У ньому розглянуті методи лінійного, дискретного та нелінійного програмування, а також програмне забезпечення методів оптимізації у середовищі MatLab. Матеріали підручника ілюструються рисунками, графіками і прикладами. Кожний розділ підручника закінчується контрольними питаннями та завданням, які служать для самоперевірки і самостійної роботи студентів. Книга буде корисною для студентів технічних університетів, які прослухали курс вищої математики і мають певні навики у програмуванні. ЗМІСТ ПЕРЕДМОВА………………………………………… 6 ВСТУП ……………………………………………… 8 1 ЛІНІЙНЕ ПРОГРАМУВАННЯ …………………… 12 1.1 Постановка задачі лінійного програмування … 12 1.2 Основні теореми задачі лінійного програмування ………13 1.3 Графічний метод розв'язування задач лінійного програмування ………………15 1.4 Симплекс-метод розв'язування задач лінійного програмування ……………. 18 1.5 Двоетапний метод розв'язання задач лінійного програмування …………… 34 1.6 Метод великих штрафів (М-метод) …………… 46 1.7 Двоїста задача лінійного програмування ……… 51 1.8 Модифікований симплексний метод …………… 59 Контрольні питання та завдання ……………… 74 2 ДИСКРЕТНЕ ПРОГРАМУВАННЯ ………………… 77 2.1 Постановка задачі дискретного програмування…… 77 2.2 Приклади задач дискретного (цілочислового) програмування ……………………..78 2.3 Методи розв'язування задач дискретного (цілочислового) програмування ……………………. 80 2.3.1 Метод відтинання (метод Гоморі) ………… 81 2.3.2 Метод гілок і меж …………………………... 90 2.3.3 Алгоритм розв'язання задачі цілочисельного програмування ……………………94 2.3.4 Задача комівояжера ………………………… 107 2.3.5 Симетрична задача комівояжера ………….. 124 Контрольні питання та завдання ………….. 136 3 НЕЛІНІЙНЕ ПРОГРАМУВАННЯ …………………. 139 3.1 Класичний метод пошуку умовного екстремуму. Метод множників Лагранжа ……………………….. 139 3.2 Методи нелінійного програмування при наявності обмежень. Теорема Куна-Таккера ………. 148 3.3 Числові методи розв'язання задач нелінійного програмування. Методи штрафних функцій і бар'єрів …………………………………………156 3.3.1 Ідея методів бар'єрних і штрафних функцій ………………………………………………157 3.3.2 Метод бар'єрних функцій …………………. 159 3.3.3 Метод штрафних функцій ………………… 160 3.3.4 Алгоритм мінімізації з використанням методів бар'єрних і штрафних функцій ……………. 163 3.3.5 Порівняння методів бар'єрних і штрафних функцій ………………………………164 3.4 Квадратичне програмування ……………………. 166 3.5 Апроксимаційне нелінійне програмування 175 3.6 Геометричне програмування ……………………. 187 Контрольні питання та завдання ………………… 198 4 ПРОГРАМНЕ ЗАБЕЗПЕЧЕННЯ МЕТОДІВ ОПТИМІЗАЦІЇ У СЕРЕДОВИЩІ MATLAB ……… 200 4.1 Коротка характеристика системи MatLab …200 4.2 Основи роботи у системі MatLab ……………….. 200 4.2.1 Типи даних системи MatLab ……………… 200 4.2.2 Арифметичні операції …………………….. 209 4.2.3 Програмування у середовищі MatLab …… 221 4.2.4 Побудова графіків у середовищі MatLab … 235 4.3 Задачі лінійного програмування ……………….. 243 4.4 Задачі нелінійного програмування …………….. 248 4.5 Задачі квадратичного програмування …………. 256 4.6 Задачі геометричного програмування ………….260 Контрольні питання та завдання 267 Література ……………………………………………. 270 ДОДАТКИ …………………………………………… 273 Д1 КОРОТКІ ВІДОМОСТІ З ТЕОРІЇ МАТРИЦЬ …….. 273 Д1.1 Вектори …………………………………………. 273 Д1.2 Матриці …………………………………………. 275 Д1.3 Квадратичні форми ……………………………. 285 Д2 ЕЛЕМЕНТИ БАГАТОВИМІРНОГО АНАЛІЗУ ….. 288 Д3 ДЕЯКІ ПИТАННЯ ТЕОРІЇ ГРАФІВ ……………….. 294 Д3.1 Основні поняття та визначення ……………….. 294 Д3.2 Матричне подання графів …………………….. 299 Література …………………………………………… 301