linprog

Решение задач линейного программирования

свернуть все на странице

Синтаксис

x = linprog (f, A, b)

x = linprog (f, A, b, Aeq, beq)

x = linprog (f, A, b, Aeq, beq, lb, ub)

x = linprog (f, A, b, Aeq, beq, lb, ub, опции)

x = linprog (проблема)

[x, fval] = linprog (___)

[x, fval, exitflag, output] = linprog (___)

[x, fval, exitflag, output, lambda] = linprog (___)

Описание

Решатель линейного программирования

Находит минимум проблемы, указанный в

$\underset{}{}^{} minxfTx такой , что {\begin{matrix} A⋅x≤b,Aeq⋅x=beq,lb≤x≤ub . \end{matrix}$

f, x, b, beq, lb и ub - векторы, а A и Aeq - матрицы.

Примечание

linprog применяется только к подходу, основанному на решателе. Обсуждение двух подходов к оптимизации см. в разделе Первый выбор подхода на основе проблем или подхода на основе решателей.

пример

x = linprog(f,A,b) решает min f'*x такой, что A*x ≤ b.

пример

x = linprog(f,A,b,Aeq,beq) включает ограничения равенства Aeq*x = beq. Набор A = [] и b = [] если неравенства не существует.

пример

x = linprog(f,A,b,Aeq,beq,lb,ub) определяет набор нижних и верхних границ для конструктивных переменных, x, чтобы решение всегда находилось в диапазоне lb ≤ x ≤ ub. Набор Aeq = [] и beq = [] если равенства отсутствуют.

Примечание

Если указанные входные границы для проблемы противоречивы, вывод fval является [].

пример

x = linprog(f,A,b,Aeq,beq,lb,ub,options) минимизирует с помощью опций оптимизации, указанных в options. Использовать optimoptions для установки этих параметров.

пример

x = linprog(problem) находит минимальное значение для problem, структура, описанная в problem.

Можно импортировать problem структура из файла MPS с использованием mpsread. Можно также создать problem структура из OptimizationProblem объект с помощью prob2struct.

пример

[x,fval] = linprog(___), для любых входных аргументов возвращает значение целевой функции fun на решении x: fval = f'*x.

пример

[x,fval,exitflag,output] = linprog(___) дополнительно возвращает значение exitflag который описывает условие выхода и структуру output содержит информацию о процессе оптимизации.

пример

[x,fval,exitflag,output,lambda] = linprog(___) дополнительно возвращает структуру lambda чьи поля содержат множители Лагранжа в решении x.

Примеры

свернуть все

Линейная программа, ограничения линейного неравенства

Открыть сценарий в реальном времени

Решение простой линейной программы, определяемой линейными неравенствами.

В этом примере используются следующие линейные ограничения неравенства:

$x (1) + x ($ 2) ≤2

$x (1) + x (2$ )/ 4≤1

$x (1) - x (2$ ) ≤2

$- x (1) / 4-x (2$ ) ≤1

$- x (1) - x (2)$ ≤-1

$- x (1) + x (2$ ) ≤2.

A = [1 1
    1 1/4
    1 -1
    -1/4 -1
    -1 -1
    -1 1];

b = [2 1 2 1 -1 2];

Используйте целевую функцию $- x (1) - x (2$ )/3.

f = [-1 -1/3];

Решите линейную программу.

x = linprog(f,A,b)

Optimal solution found.

Линейная программа с линейными неравенствами и равенствами

Открыть сценарий в реальном времени

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

В этом примере используются следующие линейные ограничения неравенства:

$x (1) + x ($ 2) ≤2

$x (1) + x (2$ )/ 4≤1

$x (1) - x (2$ ) ≤2

$- x (1) / 4-x (2$ ) ≤1

$- x (1) - x (2)$ ≤-1

$- x (1) + x (2$ ) ≤2.

A = [1 1
    1 1/4
    1 -1
    -1/4 -1
    -1 -1
    -1 1];

b = [2 1 2 1 -1 2];

Используйте линейное ограничение равенства $x (1) + x (2) /$ 4 = 1/2.

Aeq = [1 1/4];
beq = 1/2;

Используйте целевую функцию $- x (1) - x (2$ )/3.

f = [-1 -1/3];

Решите линейную программу.

x = linprog(f,A,b,Aeq,beq)

Optimal solution found.

Линейная программа со всеми типами ограничений

Открыть сценарий в реальном времени

Решение простой линейной программы с линейными неравенствами, линейными равенствами и границами.

В этом примере используются следующие линейные ограничения неравенства:

$x (1) + x ($ 2) ≤2

$x (1) + x (2$ )/ 4≤1

$x (1) - x (2$ ) ≤2

$- x (1) / 4-x (2$ ) ≤1

$- x (1) - x (2)$ ≤-1

$- x (1) + x (2$ ) ≤2.

A = [1 1
    1 1/4
    1 -1
    -1/4 -1
    -1 -1
    -1 1];

b = [2 1 2 1 -1 2];

Используйте линейное ограничение равенства $x (1) + x (2) /$ 4 = 1/2.

Aeq = [1 1/4];
beq = 1/2;

Установите следующие границы:

$- 1\leqx (1)$ ≤1.5

$- 0.5\leqx (2)$ ≤1.25.

lb = [-1,-0.5];
ub = [1.5,1.25];

Используйте целевую функцию $- x (1) - x (2$ )/3.

f = [-1 -1/3];

Решите линейную программу.

x = linprog(f,A,b,Aeq,beq,lb,ub)

Optimal solution found.

Линейная программа с использованием `'interior-point'` Алгоритм

Открыть сценарий в реальном времени

Решение линейной программы с помощью 'interior-point' алгоритм.

В этом примере используются следующие линейные ограничения неравенства:

$x (1) + x ($ 2) ≤2

$x (1) + x (2$ )/ 4≤1

$x (1) - x (2$ ) ≤2

$- x (1) / 4-x (2$ ) ≤1

$- x (1) - x (2)$ ≤-1

$- x (1) + x (2$ ) ≤2.

A = [1 1
    1 1/4
    1 -1
    -1/4 -1
    -1 -1
    -1 1];

b = [2 1 2 1 -1 2];

Используйте линейное ограничение равенства $x (1) + x (2) /$ 4 = 1/2.

Aeq = [1 1/4];
beq = 1/2;

Установите следующие границы:

$- 1\leqx (1)$ ≤1.5

$- 0.5\leqx (2)$ ≤1.25.

lb = [-1,-0.5];
ub = [1.5,1.25];

Используйте целевую функцию $- x (1) - x (2$ )/3.

f = [-1 -1/3];

Задайте параметры для использования 'interior-point' алгоритм.

options = optimoptions('linprog','Algorithm','interior-point');

Решите линейную программу с помощью 'interior-point' алгоритм.

x = linprog(f,A,b,Aeq,beq,lb,ub,options)

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in
feasible directions, to within the selected value of the function tolerance,
and constraints are satisfied to within the selected value of the constraint
tolerance.

Решение ЛП с использованием проблемного подхода для `linprog`

Открыть сценарий в реальном времени

В этом примере показано, как настроить задачу с помощью подхода, основанного на задачах, а затем решить ее с помощью подхода, основанного на решателях. Проблема в том, что

$\underset{maxx}{} (x + y/3) \begin{array}{llllllllllllllllllll} \end{array}$ subjectto{x+y≤2x+y/4≤1x-y≤2x/4+y≥-1x+y≥1-x+y≤2x+y/4=1/2-1≤x≤1.5-1/2≤y≤1.25

Создание OptimizationProblem объект с именем prob для представления этой проблемы.

x = optimvar('x','LowerBound',-1,'UpperBound',1.5);
y = optimvar('y','LowerBound',-1/2,'UpperBound',1.25);
prob = optimproblem('Objective',x + y/3,'ObjectiveSense','max');
prob.Constraints.c1 = x + y <= 2;
prob.Constraints.c2 = x + y/4 <= 1;
prob.Constraints.c3 = x - y <= 2;
prob.Constraints.c4 = x/4 + y >= -1;
prob.Constraints.c5 = x + y >= 1;
prob.Constraints.c6 = -x + y <= 2;
prob.Constraints.c7 = x + y/4 == 1/2;

Преобразование проблемного объекта в проблемную структуру.

problem = prob2struct(prob);

Решите возникшую структуру проблемы.

[sol,fval,exitflag,output] = linprog(problem)

Optimal solution found.

sol = 2×1

    0.1875
    1.2500

fval = -0.6042

exitflag = 1

output = struct with fields:
         iterations: 0
    constrviolation: 0
            message: 'Optimal solution found.'
          algorithm: 'dual-simplex'
      firstorderopt: 0

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

Какой компонент sol соответствует какой переменной оптимизации? Осмотрите Variables имущество prob.

prob.Variables

ans = struct with fields:
    x: [1x1 optim.problemdef.OptimizationVariable]
    y: [1x1 optim.problemdef.OptimizationVariable]

Как и следовало ожидать, sol(1) соответствует x, и sol(2) соответствует y. См. раздел Алгоритмы.

Возврат значения целевой функции

Открыть сценарий в реальном времени

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

Ограничения неравенства:

$x (1) + x ($ 2) ≤2

$x (1) + x (2$ )/ 4≤1

$x (1) - x (2$ ) ≤2

$- x (1) / 4-x (2$ ) ≤1

$- x (1) - x (2)$ ≤-1

$- x (1) + x (2$ ) ≤2.

A = [1 1
    1 1/4
    1 -1
    -1/4 -1
    -1 -1
    -1 1];

b = [2 1 2 1 -1 2];

Целевая функция - $- x (1) - x (2$ )/3.

f = [-1 -1/3];

Решите проблему и верните значение целевой функции.

[x,fval] = linprog(f,A,b)

Optimal solution found.

fval = -1.1111

Получение дополнительных выходных данных для анализа процесса решения

Открыть сценарий в реальном времени

Получите флаг выхода и структуру вывода для лучшего понимания процесса и качества решения.

В этом примере используются следующие линейные ограничения неравенства:

$x (1) + x ($ 2) ≤2

$x (1) + x (2$ )/ 4≤1

$x (1) - x (2$ ) ≤2

$- x (1) / 4-x (2$ ) ≤1

$- x (1) - x (2)$ ≤-1

$- x (1) + x (2$ ) ≤2.

A = [1 1
    1 1/4
    1 -1
    -1/4 -1
    -1 -1
    -1 1];

b = [2 1 2 1 -1 2];

Используйте линейное ограничение равенства $x (1) + x (2) /$ 4 = 1/2.

Aeq = [1 1/4];
beq = 1/2;

Установите следующие границы:

$- 1\leqx (1)$ ≤1.5

$- 0.5\leqx (2)$ ≤1.25.

lb = [-1,-0.5];
ub = [1.5,1.25];

Используйте целевую функцию $- x (1) - x (2$ )/3.

f = [-1 -1/3];

Задайте параметры для использования 'dual-simplex' алгоритм.

options = optimoptions('linprog','Algorithm','dual-simplex');

Решите линейную программу и запросите значение функции, флаг выхода и структуру вывода.

[x,fval,exitflag,output] = linprog(f,A,b,Aeq,beq,lb,ub,options)

Optimal solution found.

fval = -0.6042

exitflag = 1

output = struct with fields:
         iterations: 0
    constrviolation: 0
            message: 'Optimal solution found.'
          algorithm: 'dual-simplex'
      firstorderopt: 0

fval, значение целевой функции больше, чем возвращает значение целевой функции, поскольку существует больше ограничений.
exitflag = 1 указывает на надежность решения.
output.iterations = 0 означает, что linprog нашел решение во время предварительного решения, и вовсе не должен был повторять.

Получение множителей решения и лагранжа

Открыть сценарий в реальном времени

Решите простую линейную программу и изучите решение и множители Лагранжа.

Использовать целевую функцию

$f (x) =_{-}_{}_{}$ 5x1-4x2-6x3.

f = [-5; -4; -6];

Использование ограничений линейного неравенства

$_{}_{}_{} x1-x2+x3≤20$

$_{}_{}_{} 3x1+2x2+4x3≤42$

$_{}_{} 3x1+2x2≤30 .$

A =  [1 -1  1
      3  2  4
      3  2  0];
b = [20;42;30];

Ограничьте все переменные положительными:

$_{} x1≥0$

$_{} x2≥0$

$_{} x3≥0 .$

lb = zeros(3,1);

Набор Aeq и beq кому [], указывая на отсутствие ограничений линейного равенства.

Aeq = [];
beq = [];

Звонить linprogполучение множителей Лагранжа.

[x,fval,exitflag,output,lambda] = linprog(f,A,b,Aeq,beq,lb);

Optimal solution found.

Изучите решение и множители Лагранжа.

x,lambda.ineqlin,lambda.lower

lambda.ineqlin является ненулевым для второго и третьего компонентов x. Это указывает на то, что второй и третий линейные ограничения неравенства удовлетворяются равенствами:

$_{}_{}_{} 3x1+2x2+4x3=42$

$_{}_{} 3x1+2x2=30 .$

Убедитесь, что это верно:

A*x

ans = 3×1

  -12.0000
   42.0000
   30.0000

lambda.lower является ненулевым для первого компонента x. Это означает, что x(1) находится на нижней границе 0.

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

свернуть все

`f` - Вектор коэффициентов
вещественный вектор | вещественный массив

Вектор коэффициента, заданный как действительный вектор или вещественный массив. Вектор коэффициентов представляет целевую функцию f'*x. Запись предполагает, что f является вектором столбца, но можно использовать вектор строки или массив. Внутри, linprog новообращенные f к вектору столбца f(:).

Пример: f = [1,3,5,-6]

Типы данных: double

`A` - Линейные ограничения неравенства
реальная матрица

Линейные ограничения неравенства, заданные как вещественная матрица. A является Mоколо-N матрица, где M - количество неравенств, и N - количество переменных (длина f). По большим проблемам проходите A в виде разреженной матрицы.

A кодирует M линейные неравенства

A*x <= b,

где x - вектор столбца N переменные x(:), и b - вектор столбца с M элементы.

Например, рассмотрим эти неравенства:

x1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 20
5x1 + 6x2 ≤ 30.

Задайте неравенства, введя следующие ограничения.

A = [1,2;3,4;5,6];
b = [10;20;30];

Пример: Чтобы указать, что x-компоненты складываются до 1 или менее, возьмите A = ones(1,N) и b = 1.

Типы данных: double

`Aeq` - Линейные ограничения равенства
реальная матрица

Линейные ограничения равенства, заданные как вещественная матрица. Aeq является Meоколо-N матрица, где Me - количество уравнений, и N - количество переменных (длина f). По большим проблемам проходите Aeq в виде разреженной матрицы.

Aeq кодирует Me линейные равенства

Aeq*x = beq,

где x - вектор столбца N переменные x(:), и beq - вектор столбца с Me элементы.

Например, рассмотрим следующие равенства:

x1 + 2x2 + 3x3 = 10
2x1 + 4x2 + x3 = 20.

Задайте равенства, введя следующие ограничения.

Aeq = [1,2,3;2,4,1];
beq = [10;20];

Пример: Чтобы указать, что x-компоненты суммируются до 1, возьмите Aeq = ones(1,N) и beq = 1.

Типы данных: double

`b` - Линейные ограничения неравенства
действительный вектор

Линейные ограничения неравенства, заданные как действительный вектор. b является M-элементный вектор, связанный с A матрица. Если вы проходите b как вектор строки, решатели внутренне преобразуют b к вектору столбца b(:). По большим проблемам проходите b как разреженный вектор.

b кодирует M линейные неравенства

A*x <= b,

где x - вектор столбца N переменные x(:), и A является матрицей размера Mоколо-N.

Например, рассмотрим эти неравенства:

x1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 20
5x1 + 6x2 ≤ 30.

Задайте неравенства, введя следующие ограничения.

A = [1,2;3,4;5,6];
b = [10;20;30];

Пример: Чтобы указать, что компоненты x суммируются до 1 или менее, используйте A = ones(1,N) и b = 1.

Типы данных: double

`beq` - Линейные ограничения равенства
действительный вектор

Линейные ограничения равенства, заданные как действительный вектор. beq является Me-элементный вектор, связанный с Aeq матрица. Если вы проходите beq как вектор строки, решатели внутренне преобразуют beq к вектору столбца beq(:). По большим проблемам проходите beq как разреженный вектор.

beq кодирует Me линейные равенства

Aeq*x = beq,

где x - вектор столбца N переменные x(:), и Aeq является матрицей размера Meоколо-N.

Например, рассмотрим следующие равенства:

x1 + 2x2 + 3x3 = 10
2x1 + 4x2 + x3 = 20.

Задайте равенства, введя следующие ограничения.

Aeq = [1,2,3;2,4,1];
beq = [10;20];

Пример: Чтобы указать, что компоненты x суммируются до 1, используйте Aeq = ones(1,N) и beq = 1.

Типы данных: double

`lb` - Нижние границы
вещественный вектор | вещественный массив

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

x(i) >= lb(i) для всех i.

Если numel(lb) < numel(f), то lb указывает, что

x(i) >= lb(i) для 1 <= i <= numel(lb).

В этом случае решатели выдают предупреждение.

Пример: Чтобы указать, что все компоненты X являются положительными, используйте lb = zeros(size(f)).

Типы данных: double

`ub` - Верхние границы
вещественный вектор | вещественный массив

Верхние границы, заданные как вещественный вектор или вещественный массив. Если длина f равна длине ub, то ub указывает, что

x(i) <= ub(i) для всех i.

Если numel(ub) < numel(f), то ub указывает, что

x(i) <= ub(i) для 1 <= i <= numel(ub).

В этом случае решатели выдают предупреждение.

Пример: Чтобы указать, что все компоненты X меньше 1, использовать ub = ones(size(f)).

Типы данных: double

`options` - Варианты оптимизации
вывод `optimoptions` | структура как `optimset` прибыль

Опции оптимизации, указанные как выходные данные optimoptions или структура как optimset возвращает.

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

Некоторые опции отсутствуют в optimoptions дисплей. Эти параметры выделены курсивом в следующей таблице. Дополнительные сведения см. в разделе Параметры просмотра.

Все алгоритмы
`Algorithm`	Выберите алгоритм оптимизации: `'dual-simplex'` (по умолчанию) `'interior-point-legacy'` `'interior-point'` Сведения о выборе алгоритма см. в разделе Алгоритмы линейного программирования.
Диагностика	Отображение диагностической информации о функции, которая должна быть свернута или решена. Выбирать `'off'` (по умолчанию) или `'on'`.
`Display`	Уровень отображения (см. Итерационный просмотр): `'final'` (по умолчанию) отображает только окончательный результат. `'off'` или `'none'` не отображает выходные данные. `'iter'` отображает выходные данные в каждой итерации.
`MaxIterations`	Максимальное допустимое число итераций, положительное целое число. Значение по умолчанию: `85` для `'interior-point-legacy'` алгоритм `200` для `'interior-point'` алгоритм `10*(numberOfEqualities + numberOfInequalities + numberOfVariables)` для `'dual-simplex'` алгоритм См. раздел Допуски и критерии остановки, итерации и подсчеты функций. Для `optimset`, имя: `MaxIter`. См. раздел Имена текущих и устаревших опций.
`OptimalityTolerance`	Допуск окончания для двойной осуществимости, положительный скаляр. Значение по умолчанию: `1e-8` для `'interior-point-legacy'` алгоритм `1e-7` для `'dual-simplex'` алгоритм `1e-6` для `'interior-point'` алгоритм Для `optimset`, имя: `TolFun`. См. раздел Имена текущих и устаревших опций.
алгоритм внутренней точки
`ConstraintTolerance`	Допуск выполнимости для ограничений, скаляр из `1e-10` через `1e-3`. `ConstraintTolerance` измеряет предельно допустимую осуществимость. Значение по умолчанию: `1e-6`. Для `optimset`, имя: `TolCon`. См. раздел Имена текущих и устаревших опций.
Предварительно обработать	Уровень предварительной обработки НД до итераций алгоритма. Определить `'basic'` (по умолчанию) или `'none'`.
Двойной симплексный алгоритм
`ConstraintTolerance`	Допуск выполнимости для ограничений, скаляр из `1e-10` через `1e-3`. `ConstraintTolerance` измеряет предельно допустимую осуществимость. Значение по умолчанию: `1e-4`. Для `optimset`, имя: `TolCon`. См. раздел Имена текущих и устаревших опций.
`MaxTime`	Максимальное время в секундах, в течение которого выполняется алгоритм. Значение по умолчанию: `Inf`.
Предварительно обработать	Уровень предварительной обработки ЛП до итераций двойного симплексного алгоритма. Определить `'basic'` (по умолчанию) или `'none'`.

Пример: options = optimoptions('linprog','Algorithm','interior-point','Display','iter')

`problem` - Структура проблемы
структура

Структура проблемы, заданная как структура со следующими полями.

Имя поля	Вход
`f`	Вектор линейной целевой функции `f`
`Aineq`	Матрица для линейных ограничений неравенства
`bineq`	Вектор для линейных ограничений неравенства
`Aeq`	Матрица для линейных ограничений равенства
`beq`	Вектор для линейных ограничений равенства
`lb`	Вектор нижних границ
`ub`	Вектор верхних границ
`solver`	`'linprog'`
`options`	Параметры, созданные с помощью `optimoptions`

Вы должны предоставить, по крайней мере, solver в поле problem структура.

Типы данных: struct

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

свернуть все

`x` - Решение
вещественный вектор | вещественный массив

Решение, возвращаемое в виде вещественного вектора или вещественного массива. Размер x совпадает с размером f.

`fval` - Значение целевой функции при решении
вещественное число

Значение целевой функции в решении, возвращаемое как вещественное число. Как правило, fval = f'*x.

`exitflag` - Причина `linprog` остановленный
целое число

Причина linprog остановлено, возвращено как целое число.

`3`	Решение возможно по отношению к родственнику `ConstraintTolerance` допуск, но не осуществим в отношении абсолютного допуска.
`1`	Функция, сходящаяся к решению `x`.
`0`	Превышено число итераций `options.MaxIterations` или превышено время решения в секундах `options.MaxTime`.
`-2`	Выполнимая точка не найдена.
`-3`	Проблема безгранична.
`-4`	`NaN` при выполнении алгоритма обнаружено значение.
`-5`	Как первичные, так и двойственные проблемы неосуществимы.
`-7`	Направление поиска стало слишком маленьким. Дальнейшего прогресса достичь не удалось.
`-9`	Решатель потерял выполнимость.

Exitflags 3 и -9 относятся к решениям, имеющим большие несходимости. Они обычно возникают из матриц линейных ограничений, которые имеют большое число условий, или проблем, которые имеют большие компоненты решения. Чтобы исправить эти проблемы, попробуйте масштабировать матрицы коэффициентов, устранить избыточные линейные ограничения или установить более жесткие границы для переменных.

`output` - Информация о процессе оптимизации
структура

Информация о процессе оптимизации, возвращенная в виде структуры с этими полями.

`iterations`	Количество итераций
`algorithm`	Используемый алгоритм оптимизации
`cgiterations`	0 (только алгоритм внутренней точки, включен для обратной совместимости)
`message`	Выйти из сообщения
`constrviolation`	Максимум функций ограничения
`firstorderopt`	Измерение оптимальности первого порядка

`lambda` - Множители лагранжа в решении
структура

Множители лагранжа в решении, возвращаемые как структура с этими полями.

`lower`	Нижние границы, соответствующие `lb`
`upper`	Верхние границы, соответствующие `ub`
`ineqlin`	Линейные неравенства, соответствующие `A` и `b`
`eqlin`	Линейные равенства, соответствующие `Aeq` и `beq`

Множители Лагранжа для линейных ограничений удовлетворяют этому уравнению с length(f) компоненты:

$f +^{}_{} ATλ ineqlin +^{}_{}_{AeqTλ eqlin +}_{λ upper −}$ λ lower = 0,

на основе лагранжиана

$^{} fTx +_{}^{} λ ineqlinT (Ax -_{b) +}^{} λ eqlinT (Aeq x_{−}^{beq}) +_{λ upperT (}^{x} − ub)$ + λ lowerT (lb − x).

Это условное обозначение знака соответствует условию нелинейных решателей (см. раздел Теория ограниченной оптимальности). Однако этот знак противоположен знаку в литературе по линейному программированию, поэтому linprog Множитель Лагранжа - это негатив ассоциированной «теневой цены».

Алгоритмы

свернуть все

Двойной симплексный алгоритм

Описание см. в разделе Двойной симплексный алгоритм.

Алгоритм Interior-Point-Legacy

'interior-point-legacy' метод основан на LIPSOL (Linear Interior Point Solver, [3]), который является вариантом алгоритма предсказателя-корректора Мехротры [2], метода основной-двойной внутренней точки. Перед началом итерации алгоритма выполняется ряд шагов предварительной обработки. См. раздел Линейное программирование внутренних точек и старых версий.

Первый этап алгоритма может включать в себя предварительную обработку ограничений (см. Внутреннее линейное программирование (Interior-Point-Legacy Linear Programming)). Несколько условий могут вызвать linprog для выхода с сообщением о несходимости. В каждом случае linprog возвращает отрицательное значение exitflag, указывающий на отказ.

Если строка всех нулей обнаружена в Aeq, но соответствующий элемент beq не равно нулю, тогда сообщение о выходе
```
Exiting due to infeasibility: An all-zero row in the
constraint matrix does not have a zero in corresponding
right-hand-side entry.
```
Если один из элементов x обнаружено, что оно не ограничено ниже, тогда сообщение о выходе
```
Exiting due to infeasibility: Objective f'*x is unbounded below.
```
Если одна из строк Aeq имеет только один ненулевой элемент, затем связанное значение в x называется синглтоновой переменной. В этом случае значение этого компонента x может быть вычислено из Aeq и beq. Если вычисленное значение нарушает другое ограничение, то сообщение выхода будет
```
Exiting due to infeasibility: Singleton variables in
equality constraints are not feasible.
```
Если одиночная переменная может быть решена для, но решение нарушает верхнюю или нижнюю границы, то сообщение выхода
```
Exiting due to infeasibility: Singleton variables in
the equality constraints are not within bounds.
```

Примечание

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

По завершении предварительной обработки итеративная часть алгоритма начинается до тех пор, пока не будут выполнены критерии остановки. (Дополнительные сведения об остатках, основной проблеме, двойной проблеме и соответствующих критериях остановки см. в разделе Линейное программирование внутренних точек и старых версий.) Если остатки растут, а не уменьшаются, или остатки не растут и не сокращаются, отображается одно из двух следующих сообщений о завершении, соответственно,

One or more of the residuals, duality gap, or total relative error 
has grown 100000 times greater than its minimum value so far:

или

One or more of the residuals, duality gap, or total relative error 
has stalled:

После отображения одного из этих сообщений следует одно из следующих сообщений, указывающих на то, что двойственное, основное или оба кажутся неосуществимыми.

The dual appears to be infeasible (and the primal unbounded). (The primal residual < OptimalityTolerance.)
The primal appears to be infeasible (and the dual unbounded). (The dual residual < OptimalityTolerance.)
The dual appears to be infeasible (and the primal unbounded) since the dual residual > sqrt(OptimalityTolerance). (The primal residual < 10*OptimalityTolerance.)
The primal appears to be infeasible (and the dual unbounded) since the primal residual > sqrt(OptimalityTolerance). (The dual residual < 10*OptimalityTolerance.)
The dual appears to be infeasible and the primal unbounded since the primal objective < -1e+10 and the dual objective < 1e+6.
The primal appears to be infeasible and the dual unbounded since the dual objective > 1e+10 and the primal objective > -1e+6.
Both the primal and the dual appear to be infeasible.

Например, основная (цель) может быть неограниченной, а основная остаточная величина, которая является мерой удовлетворения основных ограничений, может быть небольшой.

Алгоритм внутренней точки

'interior-point' алгоритм аналогичен 'interior-point-legacy', но с более эффективной процедурой факторизации и с другой предварительной обработкой. См. Внутренний алгоритм линпрога точки.

Альтернативная функциональность

Приложение

Задача «Оптимизировать интерактивный редактор» обеспечивает визуальный интерфейс для linprog.

Ссылки

[1] Данциг, Г.Б., А. Орден и П. Вулф. «Обобщенный симплексный метод минимизации линейной формы при ограничениях линейного неравенства». Pacific Journal Math., том 5, 1955, стр. 183-195.

[2] Mehrotra, S. «О реализации метода первичных и двойственных внутренних точек». Журнал СИАМ по оптимизации, том 2, 1992, стр. 575-601.

[3] Чжан, Ю., «Решение крупномасштабных линейных программ методами внутренних точек в среде MATLAB». Технический отчет TR96-01, отдел математики и статистики, Университета Мэриленда, округ Балтимор, Балтимора, Мэриленд, июль 1995.

См. также

Темы

Представлен до R2006a

Документация

linprog

Синтаксис

Описание

Примеры

Линейная программа, ограничения линейного неравенства

Линейная программа с линейными неравенствами и равенствами

Линейная программа со всеми типами ограничений

Линейная программа с использованием `'interior-point'` Алгоритм

Решение ЛП с использованием проблемного подхода для `linprog`

Возврат значения целевой функции

Получение дополнительных выходных данных для анализа процесса решения

Получение множителей решения и лагранжа

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

`f` - Вектор коэффициентов
вещественный вектор | вещественный массив

`A` - Линейные ограничения неравенства
реальная матрица

`Aeq` - Линейные ограничения равенства
реальная матрица

`b` - Линейные ограничения неравенства
действительный вектор

`beq` - Линейные ограничения равенства
действительный вектор

`lb` - Нижние границы
вещественный вектор | вещественный массив

`ub` - Верхние границы
вещественный вектор | вещественный массив

`options` - Варианты оптимизации
вывод `optimoptions` | структура как `optimset` прибыль

`problem` - Структура проблемы
структура

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

`x` - Решение
вещественный вектор | вещественный массив

`fval` - Значение целевой функции при решении
вещественное число

`exitflag` - Причина `linprog` остановленный
целое число

`output` - Информация о процессе оптимизации
структура

`lambda` - Множители лагранжа в решении
структура

Алгоритмы

Двойной симплексный алгоритм

Алгоритм Interior-Point-Legacy

Алгоритм внутренней точки

Альтернативная функциональность

Приложение

Ссылки

См. также

Темы

Документация по панели инструментов оптимизации

Поддержка

Документация

linprog

Синтаксис

Описание

Примеры

Линейная программа, ограничения линейного неравенства

Линейная программа с линейными неравенствами и равенствами

Линейная программа со всеми типами ограничений

Линейная программа с использованием 'interior-point' Алгоритм

Решение ЛП с использованием проблемного подхода для linprog

Возврат значения целевой функции

Получение дополнительных выходных данных для анализа процесса решения

Получение множителей решения и лагранжа

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

f - Вектор коэффициентов вещественный вектор | вещественный массив

A - Линейные ограничения неравенства реальная матрица

Aeq - Линейные ограничения равенства реальная матрица

b - Линейные ограничения неравенства действительный вектор

beq - Линейные ограничения равенства действительный вектор

lb - Нижние границы вещественный вектор | вещественный массив

ub - Верхние границы вещественный вектор | вещественный массив

options - Варианты оптимизации вывод optimoptions | структура как optimset прибыль

problem - Структура проблемы структура

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

x - Решение вещественный вектор | вещественный массив

fval - Значение целевой функции при решении вещественное число

exitflag - Причина linprog остановленный целое число

output - Информация о процессе оптимизации структура

lambda - Множители лагранжа в решении структура

Алгоритмы

Двойной симплексный алгоритм

Алгоритм Interior-Point-Legacy

Алгоритм внутренней точки

Альтернативная функциональность

Приложение

Ссылки

См. также

Темы

Документация по панели инструментов оптимизации

Поддержка

Линейная программа с использованием `'interior-point'` Алгоритм

Решение ЛП с использованием проблемного подхода для `linprog`

`f` - Вектор коэффициентов
вещественный вектор | вещественный массив

`A` - Линейные ограничения неравенства
реальная матрица

`Aeq` - Линейные ограничения равенства
реальная матрица

`b` - Линейные ограничения неравенства
действительный вектор

`beq` - Линейные ограничения равенства
действительный вектор

`lb` - Нижние границы
вещественный вектор | вещественный массив

`ub` - Верхние границы
вещественный вектор | вещественный массив

`options` - Варианты оптимизации
вывод `optimoptions` | структура как `optimset` прибыль

`problem` - Структура проблемы
структура

`x` - Решение
вещественный вектор | вещественный массив

`fval` - Значение целевой функции при решении
вещественное число

`exitflag` - Причина `linprog` остановленный
целое число

`output` - Информация о процессе оптимизации
структура

`lambda` - Множители лагранжа в решении
структура