Лекція 5. Завдання оптимізації
Це найбільш поширений в інженерній практиці клас задач. Дійсно, проектуючи установку, технологію або процес, ми прагнемо мінімізувати деякі витрати або навантаження, максимально збільшити позитивний ефект, найбільшим чином скоротити виробничий цикл або, навпаки, збільшити його з метою досягнення найкращих якісних показників продукту.
Зверніть увагу, які прикметники використовуються: найбільший, максимальний, мінімальний, найкращий. Всі вони характеризують завдання оптимізації. Економічні розрахунки - взагалі часто-густо рішення таких задач, деякі з яких вже стали класичними. Наприклад, завдання про розподіл ресурсів, завдання комівояжера.
Думаю, очевидно, що завдання цього класу вельми різноманітні і, отже, вимагають принципово різних підходів. До честі Scilab слід зазначити, що він має в своєму розпорядженні достатній арсенал засобів для вирішення завдань оптимізації, до знайомства з якими ми і переходимо.
Локальний мінімум функцій однієї змінної
В якості найпростішої оптимізаційної задачі розглянемо пошук локального мінімуму функції однієї змінної. Завдання полягає в пошуку координат точки локального мінімуму заданої функції.
Як і у випадку з пошуком коренів нелінійного рівняння, рішення здійснюється в два етапи. Спочатку потрібно побудувати графік, щоб переконатися в існуванні мінімуму і вибрати початкове наближення для абсциси шуканої точки. Потім знаходяться точне значення координат точки мінімуму.
Розглянемо конкретний приклад.
Знайти мінімум функції
f (x) = x4 + 3x 3 -13x 2 -6x + 26
Будуємо графік функції на довільному інтервалі. який згодом при необхідності можна буде скорегувати.
Видно, що функція має два локальних мінімуму, але для більш наочного її подання має сенс розглянути поведінку функції на меншому інтервалі. оскільки «хвіст» графіка праворуч малоинформативен.
Тепер добре видно точки мінімуму. Перша знаходиться в околиці -4, друга - близько 2. Для знаходження більш точного значення мінімуму функції в Scilab служить команда
Тут x0 - початкове наближення. Команда optim повертає абсциссу точки мінімуму xmin і значення функції в цій точці fmin. Головною особливістю команди optim є структура її основний аргумент - функції fun.
Припустимо, що функція f (x). мінімум якої ми шукаємо, задана за допомогою команди deff або конструкції function (так воно і є, оскільки ми ж будували її графік). Тоді fun визначається наступним чином:
function [Fmain, Fdif, ind] = fun (x, ind)
Функція fun. таким чином, повертає саму функцію Fmain і її похідну Fdif. Параметр ind ми не чіпаємо: це внутрішній параметр і він потрібен SciLab для зв'язку fun з командою optim.
Застосуємо тепер ці відомості до нашого завдання.
Тепер знаходимо значення точок мінімуму, скориставшись з'ясованим раніше початковим наближенням.
Таким чином, точки мінімуму в нашому випадку:
(-3,8487884; -95,889413) і (1,8068586; 1,0725284).
Підкреслимо, основною проблемою є правильний вибір початкового наближення. Але це проблема не пакета SciLab, а математична.
Зауважимо, що при завданні fun функції Fmain і Fdif можна було ставити явно, проте при цьому вам доведеться самостійно обчислювати похідну Інша справа, що в даному випадку це не складає труднощів.
Результат, звичайно, буде той же:
Мінімум функції Розенброка
Перейдемо до більш складної задачі - пошуку мінімуму функцій декількох змінних. Для визначеності будемо говорити про функції двох змінних.
Формально підхід до вирішення мало відрізняється від представленого в попередньому розділі. Слід тільки враховувати, що тепер аргументом є не змінна, а вектор x, що складається з двох елементів x (1) і x (2).
Як приклад розглянемо пошук мінімуму функції Розенброка
Це відома функція в силу своєї специфіки використовується в якості тестової для алгоритмів мінімізації.
Починаємо рішення, природно, з побудови графіка.
Побудова тривимірних графіків
Графік функції двох змінних, заданої, як в нашому випадку, в явному вигляді, найпростіше побудувати за допомогою команди surf.
Код досить простий. Спочатку ставимо область зміни аргументів за допомогою команди meshgrig. так звану сітку. Потім в вузлах цієї сітки обчислюються значення функції, і якщо все зроблено правильно, команда surf дає шуканий результат.
Звертаємо вашу увагу, оскільки x і y є стовпцями, під час запису функції слід використовувати поелементні дії. У нашому випадку це зведення в ступінь: «. ^»
Графік має вигляд:
Це не функція одного аргументу, і графічно знайти мінімум у неї набагато складніше, тим не менш, за забарвленням видно, що в обраній галузі є сенс пошукати мінімум. Тому задамося початковим наближенням (0, 0), оскільки в околиці цієї точки найбільше чорного кольору.
Пошук мінімуму
Початкове наближення вибрано, переходимо до безпосереднього визначення точки мінімуму. Для зручності програмування перепишемо функцію Розенброка «в термінах» Scilab.
Так як функція немає від однієї змінної, а від вектора, простіше поставити її за допомогою конструкції function:
Так як тут використовуються вже числа, а не стовпці значень, можна використовувати звичайний оператор піднесення до степеня.
Задамо функцію fn в точності так само, як ми це робили для випадку функції однієї змінної.
Задаємо початкове наближення і знаходимо точку мінімуму:
Таким чином, функція Розенброка має мінімум в точці (1; 1), рівний 0. Результат відповідає теоретичному. SciLab впорався зі складним тестовим прикладом!
Завдання про раціоні
Ще однією часто зустрічається на практиці завданням оптимізації є завдання лінійного програмування. До цього класу відносять завдання про план, транспортну задачу, задачу про раціоні і інші. Як приклад розглянемо останню.
Скласти такий раціон, щоб забезпечити задані умови при мінімальній вартості.
Постановка задачі
Нехай x1. x2. x3. x4 - шукана кількість продуктів П1. П2. П3. П4 відповідно. Тоді загальна вартість раціону
Наше завдання - підібрати xi так, щоб ця функція була мінімальною. При цьому на невідомі xi накладаються наступні обмеження:
- обмеження на знак (дійсно, шукані величини повинні бути позитивними)
Таким чином, математична постановка задачі: знайти значення змінних x1. x2. x3. x4. задовольняють системі обмежень (2) - (5), при яких лінійна функція (1) була б мінімальною. Функція L називається цільовою функцією.
Для вирішення завдання лінійного програмування в SciLab призначена функція linpro. має синтаксис:
с - вектор-стовпець коефіцієнтів при xi в цільової функції; довжина вектора, природно, дорівнює числу невідомих.
А - матриця коефіцієнтів при невідомих в системі обмежень; кількість рядків матриці дорівнює числу обмежень, а кількість стовпців збігається з числом невідомих. Все що обмежують умови повинні мати знак «≤». Якщо в вихідного формулювання (як в нашому випадку) присутній знак «≥», нерівність множиться на -1.
b - вектор-стовпець вільних членів системи обмежень.
сi - вектор-стовпець, що містить нижню межу для шуканих змінних; при відсутності вказується [].
сs - вектор-стовпець, що містить верхню межу для шуканих змінних; при відсутності вказується [].
k - целочисленная змінна, дорівнює числу рівності в обмеженні. У цьому лучае при формуванні матриці А спочатку враховуються рівності, а потім нерівності.
х0 - вектор-стовпець початкових наближень для шуканих значень.
Функція linpro повертає масив невідомих х, мінімальне значення функції f і масив множників Лагранжа kl.
Для роботи команди linpro повинен бути підключений інструмент quapro. Якщо він не встановлений, скачайте цей модуль з сайту scilab.org, встановіть, і виконайте (Файл - Виконати) файл loader з директорії quapro.
Рішення завдання
Знайти таке значення змінних x1. x2. x3. x4. при яких цільова функція
досягає свого мінімального значення при наступних обмеженнях
Зверніть увагу, що в четвертому наближенні знак «≥» потрібно поміняти на «≤», для чого помножити це нерівність на «-1»:
Реалізація рішення в SciLab має вигляд:
