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

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 путем экспорта проблемы из приложения Оптимизации, как описано в Экспорте работы. Можно импортировать структуру 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) \leq 2$

$x (1) + x (2) / 4 \leq 1$

$x (1) - x (2) \leq 2$

$- x (1) / 4 - x (2) \leq 1$

$- x (1) - x (2) \leq - 1$

$- x (1) + x (2) \leq 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) \leq 2$

$x (1) + x (2) / 4 \leq 1$

$x (1) - x (2) \leq 2$

$- x (1) / 4 - x (2) \leq 1$

$- x (1) - x (2) \leq - 1$

$- x (1) + x (2) \leq 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) \leq 2$

$x (1) + x (2) / 4 \leq 1$

$x (1) - x (2) \leq 2$

$- x (1) / 4 - x (2) \leq 1$

$- x (1) - x (2) \leq - 1$

$- x (1) + x (2) \leq 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 \leq x (1) \leq 1.5$

$- 0.5 \leq x (2) \leq 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) \leq 2$

$x (1) + x (2) / 4 \leq 1$

$x (1) - x (2) \leq 2$

$- x (1) / 4 - x (2) \leq 1$

$- x (1) - x (2) \leq - 1$

$- x (1) + x (2) \leq 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 \leq x (1) \leq 1.5$

$- 0.5 \leq x (2) \leq 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.

Решите LP Используя основанный на проблеме подход для `linprog`

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

$\max_{x} (x + y / 3) s u b j e c t t o {\begin{array}{llllllllllllllllllll} x + y \leq 2 \\ x + y / 4 \leq 1 \\ x - y \leq 2 \\ x / 4 + y \geq - 1 \\ x + y \geq 1 \\ - x + y \leq 2 \\ x + y / 4 = 1 / 2 \\ - 1 \leq x \leq 1.5 \\ - 1 / 2 \leq y \leq 1 . 25 \end{array}$

Создайте объект 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) \leq 2$

$x (1) + x (2) / 4 \leq 1$

$x (1) - x (2) \leq 2$

$- x (1) / 4 - x (2) \leq 1$

$- x (1) - x (2) \leq - 1$

$- x (1) + x (2) \leq 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) \leq 2$

$x (1) + x (2) / 4 \leq 1$

$x (1) - x (2) \leq 2$

$- x (1) / 4 - x (2) \leq 1$

$- x (1) - x (2) \leq - 1$

$- x (1) + x (2) \leq 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 \leq x (1) \leq 1.5$

$- 0.5 \leq x (2) \leq 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) = - 5 x_{1} - 4 x_{2} - 6 x_{3} .$

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

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

$x_{1} - x_{2} + x_{3} \leq 20$

$3 x_{1} + 2 x_{2} + 4 x_{3} \leq 42$

$3 x_{1} + 2 x_{2} \leq 30 .$

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

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

$x_{1} \geq 0$

$x_{2} \geq 0$

$x_{3} \geq 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. Это указывает, что вторые и третьи линейные ограничения неравенства удовлетворены равенствами:

$3 x_{1} + 2 x_{2} + 4 x_{3} = 42$

$3 x_{1} + 2 x_{2} = 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-by-N матрица, где M является количеством неравенств, и N является количеством переменных (длина f). Для больших проблем передайте A как разреженную матрицу.

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

A*x <= b,

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

Например, чтобы задать

x ₁ + 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-by-N матрица, где Me является количеством равенств, и N является количеством переменных (длина f). Для больших проблем передайте Aeq как разреженную матрицу.

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

Aeq*x = beq,

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

Например, чтобы задать

x ₁ + 2x2 + 3x3 = 10
2x1 + 4x2 + x ₃ = 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-by-N.

Например, чтобы задать

x ₁ + 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-by-N.

Например, чтобы задать

x ₁ + 2x2 + 3x3 = 10
2x1 + 4x2 + x ₃ = 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-компоненты - меньше чем один, ub = ones(size(f))

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

`опции` Опции оптимизации
вывод `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`. См. Текущие и Устаревшие Таблицы Имени Опции.
Предварительно обработать	Уровень предварительной обработки LP до итераций алгоритма. Задайте `'basic'` (значение по умолчанию) или `'none'`.
Двойной симплексный алгоритм
`ConstraintTolerance`	Допуск выполнимости к ограничениям, скаляру от `1e-10` до `1e-3`. `ConstraintTolerance` измеряет основной допуск выполнимости. Значением по умолчанию является `1e-4`. Для `optimset` именем является `TolCon`. См. Текущие и Устаревшие Таблицы Имени Опции.
`MaxTime`	Максимальное количество времени в секундах, которые запускает алгоритм. Значением по умолчанию является `Inf`.
Предварительно обработать	Уровень предварительной обработки LP до двойных симплексных итераций алгоритма. Задайте `'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.

Самым простым способом получить структуру problem является экспорт задачи из Optimization app.

Типы данных: 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	Решатель потерял выполнимость.

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

`вывод` Информация о процессе оптимизации
структура

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

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

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

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

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

Алгоритмы