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)

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

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)

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

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

Время (в секундах), затраченное на решение задачи ЛП/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);