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)

Вариант метода ветвления (только для задач целочисленного программирования):

1 (GLP_BR_FFV)

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

2 (GLP_BR_LFV)

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

3 (GLP_BR_MFV)

Переменная с наибольшей дробной частью.

4 (GLP_BR_DTH)

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

5 (GLP_BR_PCH)

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

btrack (default: 4)

Вариант техники возврата (только для задач целочисленного программирования):

1 (GLP_BT_DFS)

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

2 (GLP_BT_BFS)

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

3 (GLP_BT_BLB)

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

4 (GLP_BT_BPH)

Лучшая эвристика проекции.

presol (default: 1)

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

lpsolver (default: 1)

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

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)

Оптимальное решение начальной задачи ЛП не предоставлено.

13 (GLP_ESTOP)

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

14 (GLP_EMIPGAP)

Достигнута относительная толерантность к разнице значений задачи целочисленного программирования.

15 (GLP_ENOFEAS)

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

16 (GLP_ENOCVG)

Не сходится.

17 (GLP_EINSTAB)

Численная нестабильность.

18 (GLP_EDATA)

Неверные данные.

19 (GLP_ERANGE)

Результат выходит за пределы диапазона.

extra

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

lambda

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

redcosts

Сниженные стоимости.

time

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

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);