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)

Если этот флаг установлен, решатель симплексом использует встроенный препроцессор 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);