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

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

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

Вступ

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

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

Одним з основних стає завдання створення єдиної системи оптимального планування та управління народним господарством на базі широкого застосування математичних методів і електронно-обчислювальної техніки в економіці.

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

У даній роботі буде розглянуто один з найкращих, за даними дослідження С. Стейнхауса [1], універсальний математичний пакет MATLAB, проаналізовано його основні засоби, призначені для знаходження екстремумів функцій від багатьох змінних, а також для розв’язування задач програмування. Це обумовлено тим, що:

по-перше, не дивлячись на те, що МОН України визначило пакет MATLAB як базовий для ВНЗ України, використання цього пакету при вивченні математичних дисциплін, за даними проведеного Ю. Триусом та М. Жалдаком [2] анкетування викладачів, є невиправдано низьким (7% з 70 респондентів);

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

1. Характеристика середовища MATLAB та допоміжного пакету Optimization Toolbox

(скорочено від Matrix Laboratory, розроблена фірмою The MathWorks, Inc. (США, м. Нейтік, шт. Массачусетс)) - найбільш розвинена система програмування для науково-технічних розрахунків, доповнена до теперішнього часу кількома десятками більш спеціалізованих додатків, що відносяться до обчислювальної математики, обробки інформації, конструювання електронних приладів, економіки та ряду інших розділів прикладної науки.призначений насамперед для програмування чисельних алгоритмів. Він розробляється вже більше 15 років і виник на основі більш ранніх прикладних пакетів LINPACK і EIGPACK, створених в 1970-і рр. в США, і в свою чергу вплинув на появу таких систем, як MathCad, MAPLE і Mathematica. Удосконалення системи MATLAB відбувалося як у зв'язку з досягненнями в обчислювальній математиці, так і у зв'язку із змінами в архітектурі персональних комп'ютерів і розвитком загальносистемних засобів. З часом MATLAB був доповнений цілим рядом вже згадуваних додатків (toolboxes), що збільшили межі його застосовності.- система програмування високого рівня, що працює як інтерпретатор і включає великий набір інструкцій (команд) для виконання найрізноманітніших обчислень, завдання структур даних та графічного представлення інформації. Команди ці розбиті на тематичні групи, розташовані в різних директоріях системи. Зараз у системі налічується близько 800 команд, і приблизно половина з них цілком доступна починаючому користувачеві. Команди з великим можливим обсягом обчислень написані на мові програмування С, тому система виявляється майже відкритою для користувача. Є великі можливості для виведення двовимірної і тривимірної графіки і засоби управління нею. Користувач може без особливих труднощів додавати свої команди і писати програми в термінах вже існуючих команд. Стислість і наочність програмування і виняткові можливості візуалізації результатів роблять систему дуже ефективною при пошуках і апробації нових алгоритмів, при проведенні разових розрахунків і в навчальному процесі, оскільки її можна освоювати без попереднього знайомства з основами програмування й виконувати такі складні приклади, які неможливо робити з використанням інших систем.

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

При цьому:

• для вказівки введення початкових даних використовується символ»;

• дані вводяться за допомогою найпростішого рядкового редактора;

• для блокування виведення обчислень деякого виразу після нього треба встановити знак; (крапка з комою);

• якщо не вказана змінна зі значенням результату обчислень, то MATLAB призначає таку змінну з ім’ям ans;

• знаком привласнення є звичний математиці знак рівності =, а не комбінований знак: =, як в багатьох інших математичних системах;

• вбудовані функції (наприклад, sin) записуються малими буквами і їх аргументи вказуються в круглих дужках;

• результат обчислень виводиться в рядках висновку (без знаку»);

Для вирішення оптимізаційних задач у середовищі MATLAB використовується пакет оптимізації Optimization Toolbox.

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

• безумовна оптимізація нелінійних функцій;

• метод найменших квадратів;

• вирішення нелінійних рівнянь;

• лінійне програмування;

• квадратичне програмування;

• умовна мінімізація нелінійних функцій;

• методи мінімаксу;

• багатокритеріальна оптимізація.

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

2. Функція linprog та її застосування у вирішенні оптимізаційних задач

оптимізаційний програмування лінійний мінімізація

Для розв’язання задач лінійного програмування у пакеті оптимізації Optimization Toolbox використовується функція linprog. Вона призначена для розв’язування задачі виду:

f(x) = ,             (1)

A·x ≤ b,                                            (2)

Aeq·x = beq,                                              (3)

lb ≤ x ≤ ub,                                       (4)

де c, x, b, beq, lb, ub - вектор-стовпчики, A, Aeq - прямокутні матриці, і яка має такий синтаксис:

= linprog (c, A, b, Aeq, beq);= linprog (c, A, b, Aeq, beq, lb, ub);= linprog (c, A, b, Aeq, beq, lb, ub, x0);= linprog (c, A, b, Aeq, beq, lb, ub, x0, options);

[x, fval, exitflag] = linprog(…);

[x, fval, exitflag, output] = linprog(…);

[x, fval, exitflag, output, lambda] = linprog(…).

Розглянемо особливості параметрів exitflag, lambda, output, які використовуються в функції linprog. Так параметр exitflag приймає додатне значення, якщо ітераційний процес завершився у відповідності до заданої точності обчислень; від’ємне значення, якщо ітераційний процес не збігається до розв’язку, і 0, якщо було перевищено максимальну кількість ітерацій, яка визначається за параметром MaxIten, або максимальну кількість обчислень значень цільової функції, яка визначається за параметром MaxFunEvals.

Параметр lambda являє собою структуру з полями, які містять множники Лагранжа для кожної групи обмежень задачі в точці x, що є результатом розв’язування поставленої задачі:

ineqlin - для обмежень-нерівностей,

eqlin - для обмежень-рівнянь,

upper - для прямих обмежень типу x ≤ ub,

lower - для прямих обмежень типу lb ≤ x,

при цьому ненульові елементи векторів у полях параметра lambda відповідають активним обмеженням для знайденої точки x.

Якщо в умові задачі деякі вхідні дані відсутні, то замість відповідних величин треба ставити []. Наприклад, якщо в умові задачі (1) - (4) відсутні обмеження-нерівності виду (2), то треба ввести A=[] і b=[].

Функція може використовувати алгоритм великої розмірності lipsol або алгоритм середньої розмірності (метод проекцій).

3. Приклад вирішення оптимізаційної задачі

Розглянемо приклад вирішення задачі лінійного програмування у середовищі MATLAB.

Знайти f(x) = x₁ - 4x₂ - 2x₃ → min

x₁ + 2x₂ + 2x₃ ≤ 8₁ + x₂ - x₃ ≤ 2

x₁ - 3x₂ + 3x₃ ≤ 6_j ≥ 0, j = 1, 2, 3

Розв’язання

Вхідні дані задачі подамо у матричному вигляді. Для цього у вікні Command Window пакету MATLAB треба виконати послідовно такі команди (%-… - коментарі до відповідних дій):

>> f = [1, -4, -2];% Вектор коефіцієнтів лінійної цільової функції

>> A = [-1 2 2; 1 1 -1; 2 -3 3];

>> b = [8; 2; 6];% Вектор обмежень-нерівностей

>> lb=zeros (3,1),

де функція zeros створює масив з нульовими елементами.

Після цього треба набрати і виконати команду

>> [x, fval, exitflag, output, lambda] = linprog (f, A, b, [], [], lb);

При цьому буде одержано такий результат:

Optimization terminated successfully.=

.0000

.0000

.0000=

.0000=

=: 6: 'large-scale: interior point': 0: 'Optimization terminated successfully.'=: [3x1 double]: [0x1 double]: [3x1 double]: [3x1 double]

Таким чином, ми бачимо, що:

-        оптимальний розв’язок х = [0.0000 3.0000 1.0000];

         мінімальне значення цільової функції дорівнює -14.0000;

         розрахунки закінчились знаходженням розв’язку (exitflag>0);

         всього було виконано 6 ітерацій;

         був використаний метод внутрішньої точки LIPSOL - Linear Interior Point Solver, який застосовується, як правило, для розв’язування задач великої розмірності (large-scale).

Висновки

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

Список посилань

1. Stefan Steinhaus Comparison of mathematical programs for data analysis (Edition 4.4). - Munchen/Germany. - 60 p.: http://www.scientificweb.de/ncrunch/

. Ю.В. Триус, М.І. Жалдак. Основи теорії і методів оптимізації: навч. посібник. - Черкаси: Брама-Україна, 2005. - 608 с.

. Дьяконов В.П. Компьютерная математика. Теория и практика. - М.: Нолидж, 2001. - 1296 с.

. Дащенко О.Ф., Кириллов В.Х., Коломієць Л.В., Оробей В.Ф. MATLAB в інженерних та наукових розрахунках: Монографія. - Одеса: Астро-принт, 2003. - 214 с.

. Ульянченко О.В. Дослідження операцій в економіці: Підручник для студентів вузів / Харк. нац. аграр. ун-т ім. В.В. Докучаєва. - Харків: Гриф, 2002. - 580 с.