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 решает следующую стандартную задачу LP:

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