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 применяется только к основанному на решателе подходу. Для обсуждения двух подходов оптимизации смотрите, Сначала Выбирают Problem-Based or Solver-Based Approach.

пример

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.

Примеры

свернуть все

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

Скрипт Open 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.

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

Скрипт Open 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.

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

Скрипт Open 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'` Алгоритм

Скрипт Open 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.

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

Скрипт Open 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. См. алгоритмы.

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

Скрипт Open 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

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

Скрипт Open 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 найденный решением во время предварительно решают и не должен был выполнять итерации вообще.

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

Скрипт Open 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- 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- 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- 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- 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

`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`. См. текущие и устаревшие таблицы имени опции.
Предварительно обработать	Уровень предварительной обработки 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 структура должна экспортировать проблему из приложения Оптимизации.

Типы данных: 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 относитесь к решениям, которые имеют большой infeasibilities. Они обычно являются результатом линейных ограничительных матриц, которые имеют большое число обусловленности или проблемы, которые имеют большие компоненты решения. Чтобы откорректировать эти проблемы, попытайтесь масштабировать содействующие матрицы, устранить избыточные линейные ограничения или дать более трудные границы на переменных.

`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' метод основан на LIPSOL (Линейный Решатель Внутренней точки, [3]), который является вариантом алгоритма корректора предиктора Мехротры [2], основной двойной метод внутренней точки. Много шагов предварительной обработки происходят, прежде чем алгоритм начинает выполнять итерации. Смотрите Устаревшее внутренней точкой Линейное Программирование.

Первая стадия алгоритма может включить некоторую предварительную обработку ограничений (см. Устаревшее внутренней точкой Линейное Программирование). Несколько условий могут вызвать 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] Dantzig, G.B., А. Орден и П. Вольф. “Обобщенный Симплекс-метод для Минимизации Линейной Формы Под Линейными Ограничениями Неравенства”. Тихоокеанская Математика Журнала., Издание 5, 1955, стр 183–195.

[2] Mehrotra, S. “На Реализации Основного Двойного Метода внутренней точки”. SIAM Journal на Оптимизации, Издании 2, 1992, стр 575–601.

[3] Чжан, Y., “Решая Крупномасштабные Линейные Программы Методами внутренней точки Под Средой MATLAB”. Технический отчет TR96-01, Отдел Математики и Статистики, Университета Мэриленда, округ Балтимор, Балтимора, MD, июль 1995.

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

linprog

Синтаксис

Описание

Примечание

Примечание

Примеры

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

exitflag — Обоснуйте linprog остановленный целое число

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

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

Алгоритмы

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

Устаревший внутренней точкой алгоритм

Примечание

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

Ссылки

Смотрите также

Темы

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

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

Поддержка

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

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

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

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

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

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

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

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

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

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

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

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

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

`exitflag` — Обоснуйте `linprog` остановленный
целое число

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

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