Функція 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] = linprog(…);

[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 або алгоритм середньої розмірності (метод проекцій).