Решите задачи линейного программирования
Линейный решатель программирования
Находит минимум целевой функции
f, x, b, beq, lb и ub являются векторами, и A и Aeq являются матрицами.
Примечание
linprog
применяется только к основанному на решателе подходу. Для обсуждения двух подходов оптимизации смотрите, Сначала Выбирают Problem-Based or Solver-Based Approach.
задает набор нижних и верхних границ на переменных проекта, x
= linprog(f
,A
,b
,Aeq
,beq
,lb
,ub
)x
, так, чтобы решением всегда был в области значений lb ≤ x ≤ ub
. Установите Aeq = []
и beq = []
если никакие равенства не существуют.
Примечание
Если заданные входные границы для проблемы противоречивы, выход fval
[]
.
находит минимум для x
= linprog(problem
)problem
, структура, описанная в problem
.
Можно импортировать problem
структура от использования файла MPS mpsread
. Можно также создать problem
структура от OptimizationProblem
объект при помощи prob2struct
.
Решите простую линейную программу, заданную линейными неравенствами.
В данном примере используйте эти линейные ограничения неравенства:
A = [1 1 1 1/4 1 -1 -1/4 -1 -1 -1 -1 1]; b = [2 1 2 1 -1 2];
Используйте целевую функцию .
f = [-1 -1/3];
Решите линейную программу.
x = linprog(f,A,b)
Optimal solution found.
x = 2×1
0.6667
1.3333
Решите простую линейную программу, заданную линейными неравенствами и линейными равенствами.
В данном примере используйте эти линейные ограничения неравенства:
A = [1 1 1 1/4 1 -1 -1/4 -1 -1 -1 -1 1]; b = [2 1 2 1 -1 2];
Используйте линейное ограничение равенства .
Aeq = [1 1/4]; beq = 1/2;
Используйте целевую функцию .
f = [-1 -1/3];
Решите линейную программу.
x = linprog(f,A,b,Aeq,beq)
Optimal solution found.
x = 2×1
0
2
Решите простую линейную программу с линейными неравенствами, линейными равенствами и границами.
В данном примере используйте эти линейные ограничения неравенства:
A = [1 1 1 1/4 1 -1 -1/4 -1 -1 -1 -1 1]; b = [2 1 2 1 -1 2];
Используйте линейное ограничение равенства .
Aeq = [1 1/4]; beq = 1/2;
Установите эти границы:
lb = [-1,-0.5]; ub = [1.5,1.25];
Используйте целевую функцию .
f = [-1 -1/3];
Решите линейную программу.
x = linprog(f,A,b,Aeq,beq,lb,ub)
Optimal solution found.
x = 2×1
0.1875
1.2500
'interior-point'
АлгоритмРешите линейную программу с помощью 'interior-point'
алгоритм.
В данном примере используйте эти линейные ограничения неравенства:
A = [1 1 1 1/4 1 -1 -1/4 -1 -1 -1 -1 1]; b = [2 1 2 1 -1 2];
Используйте линейное ограничение равенства .
Aeq = [1 1/4]; beq = 1/2;
Установите эти границы:
lb = [-1,-0.5]; ub = [1.5,1.25];
Используйте целевую функцию .
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.
x = 2×1
0.1875
1.2500
linprog
В этом примере показано, как настроить проблему с помощью подхода, основанного на проблеме и затем решить его с помощью основанного на решателе подхода. Проблема
Создайте 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
. См. алгоритмы.
Вычислите значение функции решения и целевой функции для простой линейной программы.
Ограничения неравенства
A = [1 1 1 1/4 1 -1 -1/4 -1 -1 -1 -1 1]; b = [2 1 2 1 -1 2];
Целевая функция .
f = [-1 -1/3];
Решите задачу и возвратите значение целевой функции.
[x,fval] = linprog(f,A,b)
Optimal solution found.
x = 2×1
0.6667
1.3333
fval = -1.1111
Получите выходной флаг и структуру output, чтобы лучше изучить процесс решения и качество.
В данном примере используйте эти линейные ограничения неравенства:
A = [1 1 1 1/4 1 -1 -1/4 -1 -1 -1 -1 1]; b = [2 1 2 1 -1 2];
Используйте линейное ограничение равенства .
Aeq = [1 1/4]; beq = 1/2;
Установите эти границы:
lb = [-1,-0.5]; ub = [1.5,1.25];
Используйте целевую функцию .
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.
x = 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
, значение целевой функции, больше, чем Возвращают Значение Целевой функции, потому что существует больше ограничений.
exitflag
= 1 указывает, что решение надежно.
output.iterations
= 0 указывает на тот linprog
найденный решением во время предварительно решают и не должен был выполнять итерации вообще.
Решите простую линейную программу и исследуйте решение и множители Лагранжа.
Используйте целевую функцию
f = [-5; -4; -6];
Используйте линейные ограничения неравенства
A = [1 -1 1 3 2 4 3 2 0]; b = [20;42;30];
Ограничьте все переменные быть положительными:
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
x = 3×1
0
15.0000
3.0000
ans = 3×1
0
1.5000
0.5000
ans = 3×1
1.0000
0
0
lambda.ineqlin
является ненулевым для вторых и третьих компонентов x
. Это указывает, что вторые и третьи линейные ограничения неравенства удовлетворены равенствами:
Проверяйте, что это верно:
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 1 + 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 1 + 2x2 + 3x3 = 10
2x1 + 4x2 + x 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
- N
.
Например, рассмотрите эти неравенства:
x 1 + 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 1 + 2x2 + 3x3 = 10
2x1 + 4x2 + x 3 = 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 | Выберите алгоритм оптимизации:
Для получения информации о выборе алгоритма см. Линейные Алгоритмы Программирования. |
Диагностика | Отобразите диагностическую информацию о функции, которая будет минимизирована или решена. Выберите |
| Level of display (см. Итеративное Отображение):
|
| Максимальное количество позволенных итераций, положительное целое число. Значение по умолчанию:
Смотрите допуски и критерий остановки и итерации и функциональные количества. Для |
| Допуск завершения на двойной выполнимости, положительной скалярной величине. Значение по умолчанию:
Для |
Алгоритм внутренней точки | |
ConstraintTolerance | Допуск выполнимости к ограничениям, скаляру от Для |
Предварительно обработать | Уровень предварительной обработки LP до итераций алгоритма. Задайте |
Двойной симплексный алгоритм | |
ConstraintTolerance | Допуск выполнимости к ограничениям, скаляру от Для |
MaxTime | Максимальное количество времени в секундах, которые запускает алгоритм. Значением по умолчанию является |
Предварительно обработать | Уровень предварительной обработки LP до двойных симплексных итераций алгоритма. Задайте |
Пример: options = optimoptions('linprog','Algorithm','interior-point','Display','iter')
problem
— Структура задачиСтруктура задачи в виде структуры со следующими полями.
Имя поля | Запись |
---|---|
| Линейный вектор целевой функции f |
| Матрица для линейных ограничений неравенства |
| Вектор для линейных ограничений неравенства |
| Матрица для линейных ограничений равенства |
| Вектор для линейных ограничений равенства |
lb | Вектор из нижних границ |
ub | Вектор из верхних границ |
| 'linprog' |
| Опции, созданные с optimoptions |
Необходимо предоставить, по крайней мере, solver
поле в problem
структура.
Типы данных: struct
x
РешениеРешение, возвращенное как вектор действительных чисел или действительный массив. Размер x
совпадает с размером f
.
fval
— Значение целевой функции в решенииЗначение целевой функции в решении, возвращенном как вещественное число. Обычно fval
= f'*x
.
exitflag
— Обоснуйте linprog
остановленныйОбоснуйте linprog
остановленный, возвращенный как целое число.
3 | Решение выполнимо относительно относительного |
1 | Функция сходилась к решению |
0 | Количество итераций превысило |
-2 | Никакая допустимая точка не была найдена. |
-3 | Проблема неограниченна. |
-4 |
|
-5 | И основные и двойные проблемы неосуществимы. |
-7 | Поисковое направление стало слишком маленьким. Никакие дальнейшие успехи не могли быть сделаны. |
-9 | Решатель потерял выполнимость. |
Exitflags 3
и -9
относитесь к решениям, которые имеют большой infeasibilities. Они обычно являются результатом линейных ограничительных матриц, которые имеют большое число обусловленности или проблемы, которые имеют большие компоненты решения. Чтобы откорректировать эти проблемы, попытайтесь масштабировать содействующие матрицы, устранить избыточные линейные ограничения или дать более трудные границы на переменных.
output
— Информация о процессе оптимизацииИнформация о процессе оптимизации, возвращенном как структура с этими полями.
iterations | Количество итераций |
algorithm | Алгоритм оптимизации используется |
cgiterations | 0 (алгоритм внутренней точки только, включенный для обратной совместимости) |
message | Выходное сообщение |
constrviolation | Максимум ограничительных функций |
firstorderopt | Мера оптимальности первого порядка |
lambda
— Множители Лагранжа в решенииМножители Лагранжа в решении, возвращенном как структура с этими полями.
Множители Лагранжа для линейных ограничений удовлетворяют этому уравнению с length(f)
компоненты:
на основе функции Лагранжа
Эти соответствия соглашения знака тот из нелинейных решателей (см. Ограниченную Теорию Оптимальности). Однако этот знак является противоположностью знака в большой линейной литературе программирования, таким образом, a 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 Алгоритм.
Оптимизировать задача Live Editor обеспечивает визуальный интерфейс для 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.
intlinprog
| mpsread
| Оптимизировать | optimoptions
| prob2struct
| quadprog
У вас есть модифицированная версия этого примера. Вы хотите открыть этот пример со своими редактированиями?
1. Если смысл перевода понятен, то лучше оставьте как есть и не придирайтесь к словам, синонимам и тому подобному. О вкусах не спорим.
2. Не дополняйте перевод комментариями “от себя”. В исправлении не должно появляться дополнительных смыслов и комментариев, отсутствующих в оригинале. Такие правки не получится интегрировать в алгоритме автоматического перевода.
3. Сохраняйте структуру оригинального текста - например, не разбивайте одно предложение на два.
4. Не имеет смысла однотипное исправление перевода какого-то термина во всех предложениях. Исправляйте только в одном месте. Когда Вашу правку одобрят, это исправление будет алгоритмически распространено и на другие части документации.
5. По иным вопросам, например если надо исправить заблокированное для перевода слово, обратитесь к редакторам через форму технической поддержки.