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,options)

x = linprog(problem)

[x,fval]
= linprog(___)

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

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

Описание

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

Находит минимум задачи, заданной в

$\min_{x} f^{T} x таким , что {\begin{matrix} A \cdot x \leq b, \\ A e q \cdot x = b e q, \\ l b \leq x \leq u b . \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.

Примеры

свернуть все

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

Открыть Live Script

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

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

$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.

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

Открыть Live Script

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

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

$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.

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

Открыть Live Script

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

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

$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'` Алгоритм

Открыть Live Script

Решите линейную программу, используя '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.

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

Открыть Live Script

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

$\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. См. Алгоритмы.

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

Открыть Live Script

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

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

$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

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

Открыть Live Script

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

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

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

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

[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 нашел решение во время предварительного решения, и не должен был итерации вообще.

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

Открыть Live Script

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

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

$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 элементы.

Для примера рассмотрим эти неравенства:

<reservedrangesplaceholder1> 1 + 2 <reservedrangesplaceholder0> 2 10
3 <reservedrangesplaceholder1> 1 + 4 <reservedrangesplaceholder0> 2 20
5 <reservedrangesplaceholder1> 1 + 6 <reservedrangesplaceholder0> 2 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 элементы.

Для примера рассмотрим эти равенства:

<reservedrangesplaceholder2> 1 + 2 <reservedrangesplaceholder1> 2 + 3 <reservedrangesplaceholder0> 3 = 10
2 <reservedrangesplaceholder2> 1 + 4 <reservedrangesplaceholder1> 2 + <reservedrangesplaceholder0> 3 = 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.

Для примера рассмотрим эти неравенства:

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

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.

Для примера рассмотрим эти равенства:

Задайте равенства путем ввода следующих ограничений.

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`	Level of 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 stop, возвращается как целое число.

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

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

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

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

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

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

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

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

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

$f + A^{T} λ_{ineqlin} + {Aeq}^{T} λ_{eqlin} + λ_{upper} - λ_{lower} = 0,$

основанный на Лагранже

$f^{T} x + λ_{ineqlin}^{T} (A x - b) + λ_{eqlin}^{T} (Aeq x - beq) + λ_{верхний}^{T} (x - ub) + λ_{ниже}^{T} (lb - x) .$

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

Алгоритмы

свернуть все

Алгоритм двойного симплекса

Для получения описания смотрите Алгоритм Двойного Симплекса.

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

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

Первый этап алгоритма может включать некоторую предварительную обработку ограничений (см. 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.
```
Если переменную singleton можно решить для, но решение нарушает верхние или нижние границы, то выходное сообщение является
```
Exiting due to infeasibility: Singleton variables in
the equality constraints are not within bounds.
```

Примечание

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

Когда предварительная обработка заканчивается, итерационная часть алгоритма начинается до тех пор, пока не будут достигнуты критерии остановки. (Для получения дополнительной информации об невязках, основной задаче, двойственной задаче и связанных критериях остановки, смотрите Interior-Point-Legacy Linear Programming.) Если невязки растут вместо того, чтобы становиться меньше, или невязки не растут и не сжимаются, отображается одно из двух следующих сообщений о прекращении, соответственно,

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.

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

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

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

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

Приложение

Задача Optimize Live Editor обеспечивает визуальный интерфейс для linprog.

Ссылки

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

[2] Mehrotra, S. «On the Implementation of a Primal-Dual Interior Point Point Method». SIAM Journal по оптимизации, том 2, 1992, стр. 575-601.

[3] Zhang, Y., «Решение масштабных линейных программ методами Interior-Point в среде 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

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

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

Приложение

Ссылки

См. также

Темы

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

Поддержка

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

linprog

Синтаксис

Описание

Примеры

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

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

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

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

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

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

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

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

Входные параметры

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

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

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

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

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

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

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

options - Опции оптимизации выход optimoptions | структуру следующим optimset возвраты

problem - Структура задачи структура

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

x - Решение вектор действительных чисел | вещественный массив

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

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

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

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

Алгоритмы

Алгоритм двойного симплекса

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

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

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

Приложение

Ссылки

См. также

Темы

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

Поддержка

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

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

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

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

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

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

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

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

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

`options` - Опции оптимизации
выход `optimoptions` | структуру следующим `optimset` возвраты

`problem` - Структура задачи
структура

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

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

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

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

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