linprog

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

Описание

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

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

minxfTx таким образом , что {Axb,Aeqx=beq,lbxub.

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.

Примеры

свернуть все

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

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

x(1)+x(2)2

x(1)+x(2)/41

x(1)-x(2)2

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

-x(1)-x(2)-1

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

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

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

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

f = [-1 -1/3];

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

x = linprog(f,A,b)
Optimal solution found.
x = 2×1

    0.6667
    1.3333

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

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

x(1)+x(2)2

x(1)+x(2)/41

x(1)-x(2)2

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

-x(1)-x(2)-1

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

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

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

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

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

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

f = [-1 -1/3];

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

x = linprog(f,A,b,Aeq,beq)
Optimal solution found.
x = 2×1

     0
     2

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

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

x(1)+x(2)2

x(1)+x(2)/41

x(1)-x(2)2

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

-x(1)-x(2)-1

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

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

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

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

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

Установите эти границы:

-1x(1)1.5

-0.5x(2)1.25.

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

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

f = [-1 -1/3];

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

x = linprog(f,A,b,Aeq,beq,lb,ub)
Optimal solution found.
x = 2×1

    0.1875
    1.2500

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

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

x(1)+x(2)2

x(1)+x(2)/41

x(1)-x(2)2

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

-x(1)-x(2)-1

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

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

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

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

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

Установите эти границы:

-1x(1)1.5

-0.5x(2)1.25.

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

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

f = [-1 -1/3];

Установите опции использовать 'interior-point' алгоритм.

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

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

x = linprog(f,A,b,Aeq,beq,lb,ub,options)
Minimum found that satisfies the constraints.

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

    0.1875
    1.2500

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

max x(x+y/3)subjectto{x+y2x+y/41x-y2x/4+y-1x+y1-x+y2x+y/4=1/2-1x1.5-1/2y1.25

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

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

Преобразуйте объект задачи в структуру задачи.

problem = prob2struct(prob);

Решите получившуюся структуру задачи.

[sol,fval,exitflag,output] = linprog(problem)
Optimal solution found.
sol = 2×1

    0.1875
    1.2500

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

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

Какой компонент sol соответствует который переменная оптимизации? Исследуйте Variables свойство prob.

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

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

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

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

x(1)+x(2)2

x(1)+x(2)/41

x(1)-x(2)2

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

-x(1)-x(2)-1

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

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

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

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

f = [-1 -1/3];

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

[x,fval] = linprog(f,A,b)
Optimal solution found.
x = 2×1

    0.6667
    1.3333

fval = -1.1111

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

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

x(1)+x(2)2

x(1)+x(2)/41

x(1)-x(2)2

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

-x(1)-x(2)-1

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

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

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

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

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

Установите эти границы:

-1x(1)1.5

-0.5x(2)1.25.

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

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

f = [-1 -1/3];

Установите опции использовать 'dual-simplex' алгоритм.

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

Решите линейную программу и запросите значение функции, выходной флаг и структуру 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(x)=-5x1-4x2-6x3.

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

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

x1-x2+x320

3x1+2x2+4x342

3x1+2x230.

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

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

x10

x20

x30.

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

3x1+2x2+4x3=42

3x1+2x2=30.

Проверяйте, что это верно:

A*x
ans = 3×1

  -12.0000
   42.0000
   30.0000

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

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

свернуть все

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

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

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

Линейные ограничения неравенства, заданные как действительная матрица. 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 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 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 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

Нижние границы, заданные как вектор действительных чисел или действительный массив. Если длина 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

Верхние границы, заданные как вектор действительных чисел или действительный массив. Если длина 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 отображение. Эти опции появляются курсивом в следующей таблице. Для получения дополнительной информации, Опции вида на море.

Все алгоритмы
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')

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

Имя поляЗапись

f

Линейный вектор целевой функции f

Aineq

Матрица для линейных ограничений неравенства

bineq

Вектор для линейных ограничений неравенства

Aeq

Матрица для линейных ограничений равенства

beq

Вектор для линейных ограничений равенства
lbВектор нижних границ
ubВектор верхних границ

solver

'linprog'

options

Опции создаются с optimoptions

Необходимо предоставить, по крайней мере, solver поле в problem структура.

Самый простой способ получить problem структура должна экспортировать проблему из приложения Оптимизации.

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

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

свернуть все

Решение, возвращенное как вектор действительных чисел или действительный массив. Размер x совпадает с размером f.

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

Обоснуйте linprog остановленный, возвращенный как целое число.

3

Решение выполнимо относительно относительного ConstraintTolerance допуск, но не выполнимо относительно абсолютного допуска.

1

Функция сходилась к решению x.

0

Количество итераций превысило options.MaxIterations или время решения в секундах превысило options.MaxTime.

-2

Никакая допустимая точка не была найдена.

-3

Проблема неограниченна.

-4

NaN со значением столкнулись во время осуществления алгоритма.

-5

И основные и двойные проблемы неосуществимы.

-7

Поисковое направление стало слишком маленьким. Никакие дальнейшие успехи не могли быть сделаны.

-9

Решатель потерял выполнимость.

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

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

iterations

Количество итераций

algorithm

Алгоритм оптимизации используется

cgiterations

0 (алгоритм внутренней точки только, включенный для обратной совместимости)

message

Выходное сообщение

constrviolation

Максимум ограничительных функций

firstorderopt

Мера по оптимальности первого порядка

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

lower

Нижние границы, соответствующие lb

upper

Верхние границы, соответствующие ub

ineqlin

Линейные неравенства, соответствующие A и b

eqlin

Линейные равенства, соответствующие Aeq и beq

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

f+ATλineqlin+AeqTλeqlin+λверхнийλниже=0,

на основе функции Лагранжа

fTx+λineqlinT(Axb)+λeqlinT(Aeq xbeq)+λверхнийT(xub)+λнижеT(lbx).

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

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

Для просмотра документации необходимо авторизоваться на сайте