25.1 Линейное программирование

Octave может решать задачи линейного программирования с помощью функции glpk. То есть Octave может решать

min C'*x

при линейных ограничениях A*x = b, где x ≥ 0.

Функция glpk также поддерживает различные варианты этой задачи.

: [xopt, fmin, errnum, extra] = glpk (c, A, b, lb, ub, ctype, vartype, sense, param)

Решение задачи линейного программирования с использованием библиотеки GNU GLPK.

При передаче трёх аргументов glpk решает следующую стандартную задачу линейного программирования:

min C'*x

при ограничениях

A*x  = b
  x >= 0

но также может решать задачи вида

[ min | max ] C'*x

при ограничениях

A*x [ "=" | "<=" | ">=" ] b
  x >= LB
  x <= UB

Входные аргументы:

c

Столбцовый массив, содержащий коэффициенты целевой функции.

A

Матрица, содержащая коэффициенты ограничений.

b

Столбцовый массив, содержащий правую часть каждого ограничения в матрице ограничений.

lb

Массив, содержащий нижнюю границу каждой переменной. Если lb не задан, нижняя граница переменных по умолчанию равна нулю.

ub

Массив, содержащий верхнюю границу каждой переменной. Если ub не задан, верхняя граница по умолчанию считается бесконечной.

ctype

Массив символов, задающий тип каждого ограничения в матрице ограничений. Каждый элемент массива может принимать одно из следующих значений:

"F"

Свободное (неограниченное) ограничение (ограничение игнорируется).

"U"

Ограничение-неравенство с верхней границей (A(i,:)*x <= b(i)).

"S"

Ограничение-равенство (A(i,:)*x = b(i)).

"L"

Ограничение-неравенство с нижней границей (A(i,:)*x >= b(i)).

"D"

Ограничение-неравенство с верхней и нижней границами (A(i,:)*x >= -b(i)) и (A(i,:)*x <= b(i)).

vartype

Столбцовый массив, содержащий типы переменных.

"C"

Непрерывная переменная.

"I"

Целочисленная переменная.

sense

Если sense равно 1, решается задача минимизации. Если sense равно -1, решается задача максимизации. Значение по умолчанию — 1.

param

Структура, содержащая следующие параметры, определяющие поведение решателя. Отсутствующим элементам структуры присваиваются значения по умолчанию, поэтому задавать нужно только те элементы, значения которых требуется изменить.

Целочисленные параметры:

msglev (default: 1)

Уровень вывода сообщений процедурами решателя:

0 (GLP_MSG_OFF)

Без вывода.

1 (GLP_MSG_ERR)

Только сообщения об ошибках и предупреждения.

2 (GLP_MSG_ON)

Обычный вывод.

3 (GLP_MSG_ALL)

Полный вывод (включая информационные сообщения).

scale (default: 16)

Параметр масштабирования. Значения можно комбинировать с помощью побитового оператора ИЛИ; возможны следующие значения:

1 (GLP_SF_GM)

Масштабирование по среднему геометрическому.

16 (GLP_SF_EQ)

Масштабирование с уравновешиванием.

32 (GLP_SF_2N)

Округлять коэффициенты масштабирования до степени двойки.

64 (GLP_SF_SKIP)

Пропустить, если задача хорошо масштабирована.

Кроме того, можно указать значение 128 (GLP_SF_AUTO); в этом случае процедура автоматически выбирает параметры масштабирования.

dual (default: 1)

Параметр метода симплекса:

1 (GLP_PRIMAL)

Использовать двухфазный прямой симплекс-метод.

2 (GLP_DUALP)

Использовать двухфазный двойственный симплекс-метод, а в случае неудачи переключиться на прямой симплекс-метод.

3 (GLP_DUAL)

Использовать двухфазный двойственный симплекс-метод.

price (default: 34)

Параметр выбора ведущего элемента (для прямого и двойственного симплекс-методов):

17 (GLP_PT_STD)

Классический выбор.

34 (GLP_PT_PSE)

Выбор по наискорейшему спуску.

itlim (default: intmax)

Ограничение числа итераций симплекс-метода. Оно уменьшается на единицу после каждой итерации симплекс-метода; при достижении нуля решатель прекращает поиск.

outfrq (default: 200)

Частота вывода, в итерациях. Этот параметр задаёт, как часто решатель отправляет сведения о решении в стандартный поток вывода.

branch (default: 4)

Параметр метода ветвления (только для MIP):

1 (GLP_BR_FFV)

Первая дробная переменная.

2 (GLP_BR_LFV)

Последняя дробная переменная.

3 (GLP_BR_MFV)

Наиболее дробная переменная.

4 (GLP_BR_DTH)

Эвристика Дрибека и Томлина.

5 (GLP_BR_PCH)

Гибридная эвристика псевдоиздержек.

btrack (default: 4)

Параметр метода возврата (только для MIP):

1 (GLP_BT_DFS)

Поиск в глубину.

2 (GLP_BT_BFS)

Поиск в ширину.

3 (GLP_BT_BLB)

Наилучшая локальная граница.

4 (GLP_BT_BPH)

Эвристика наилучшей проекции.

presol (default: 1)

Если этот флаг установлен, решатель симплекс-метода использует встроенный предпроцессор LP. В противном случае предпроцессор LP не используется.

lpsolver (default: 1)

Выбор используемого решателя. Если задача является задачей MIP, этот флаг игнорируется.

1

Пересмотренный симплекс-метод.

2

Метод внутренней точки.

rtest (default: 34)

Метод проверки отношений:

17 (GLP_RT_STD)

Стандартный («классический»).

34 (GLP_RT_HAR)

Двухпроходная проверка отношений Харриса.

tmlim (default: intmax)

Ограничение времени поиска, в миллисекундах.

outdly (default: 0)

Задержка вывода, в секундах. Этот параметр задаёт, как долго решатель должен задерживать отправку сведений о решении в стандартный поток вывода.

save (default: 0)

Если этот параметр ненулевой, сохранить копию задачи в формате CPLEX LP в файл "outpb.lp". В настоящее время изменить имя выходного файла нельзя.

Вещественные параметры:

tolbnd (default: 1e-7)

Относительная точность, используемая для проверки допустимости текущего базисного решения по прямым ограничениям. Не рекомендуется изменять этот параметр, если вы не имеете подробного представления о его назначении.

toldj (default: 1e-7)

Абсолютная точность, используемая для проверки допустимости текущего базисного решения по двойственным ограничениям. Не рекомендуется изменять этот параметр, если вы не имеете подробного представления о его назначении.

tolpiv (default: 1e-10)

Относительная точность, используемая для выбора допустимых опорных элементов симплекс-таблицы. Не рекомендуется изменять этот параметр, если вы не имеете подробного представления о его назначении.

objll (default: -DBL_MAX)

Нижний предел целевой функции. Если целевая функция достигает этого предела и продолжает уменьшаться, решатель прекращает поиск. Этот параметр используется только в двойственном симплекс-методе.

objul (default: +DBL_MAX)

Верхний предел целевой функции. Если целевая функция достигает этого предела и продолжает увеличиваться, решатель прекращает поиск. Этот параметр используется только в двойственном симплекс-методе.

tolint (default: 1e-5)

Относительная точность, используемая для проверки целочисленной допустимости текущего базисного решения. Не рекомендуется изменять этот параметр, если вы не имеете подробного представления о его назначении.

tolobj (default: 1e-7)

Относительная точность, используемая для проверки того, что значение целевой функции не лучше, чем в наилучшем известном целочисленно допустимом решении. Не рекомендуется изменять этот параметр, если вы не имеете подробного представления о его назначении.

Выходные значения:

xopt

Оптимизатор (значения переменных решения в точке оптимума).

fopt

Оптимальное значение целевой функции.

errnum

Код ошибки.

0

Ошибок нет.

1 (GLP_EBADB)

Недопустимый базис.

2 (GLP_ESING)

Вырожденная матрица.

3 (GLP_ECOND)

Плохо обусловленная матрица.

4 (GLP_EBOUND)

Недопустимые границы.

5 (GLP_EFAIL)

Сбой решателя.

6 (GLP_EOBJLL)

Достигнут нижний предел целевой функции.

7 (GLP_EOBJUL)

Достигнут верхний предел целевой функции.

8 (GLP_EITLIM)

Исчерпан лимит итераций.

9 (GLP_ETMLIM)

Исчерпан лимит времени.

10 (GLP_ENOPFS)

Нет допустимого решения по прямым ограничениям.

11 (GLP_ENODFS)

Нет допустимого решения по двойственным ограничениям.

12 (GLP_EROOT)

Оптимум исходной задачи LP не предоставлен.

13 (GLP_ESTOP)

Поиск прерван приложением.

14 (GLP_EMIPGAP)

Достигнута относительная допустимая погрешность MIP.

15 (GLP_ENOFEAS)

Нет допустимого решения по прямым или двойственным ограничениям.

16 (GLP_ENOCVG)

Сходимость не достигнута.

17 (GLP_EINSTAB)

Численная неустойчивость.

18 (GLP_EDATA)

Недопустимые данные.

19 (GLP_ERANGE)

Результат вне допустимого диапазона.

extra

Структура данных, содержащая следующие поля:

lambda

Двойственные переменные.

redcosts

Приведённые затраты.

time

Время (в секундах), затраченное на решение задачи LP/MIP.

status

Статус оптимизации.

1 (GLP_UNDEF)

Статус решения не определён.

2 (GLP_FEAS)

Решение допустимо.

3 (GLP_INFEAS)

Решение недопустимо.

4 (GLP_NOFEAS)

Задача не имеет допустимого решения.

5 (GLP_OPT)

Решение оптимально.

6 (GLP_UNBND)

Задача не имеет неограниченного решения.

Пример:

c = [10, 6, 4]';
A = [ 1, 1, 1;
     10, 4, 5;
      2, 2, 6];
b = [100, 600, 300]';
lb = [0, 0, 0]';
ub = [];
ctype = "UUU";
vartype = "CCC";
s = -1;

param.msglev = 1;
param.itlim = 100;

[xmin, fmin, status, extra] = ...
   glpk (c, A, b, lb, ub, ctype, vartype, s, param);