MATLAB.Exponenta
MATLAB и Simulink на русском
Технологии разработки и отладки
		сложных технических систем

Математика\Optimization Toolbox

Список функций Optimization Toolbox

  В оглавление \ К следующему разделу \ К предыдущему разделу

BINTPROG

Решение задачи целочисленного программирования вида при условии
где f, b и beq являются векторами, A и Aeq - матрицы, а x есть целочисленный вектор решения вектор решения, то есть его компоненты должны принимать значения 0 или 1.

Синтаксис:

x = bintprog(f)
x = bintprog(f, A, b)
x = bintprog(f, A, b, Aeq, beq)
x = bintprog(f, A, b, Aeq, beq, x0)
x = bintprog(f, A, b, Aeq, beq, x0, options)
[x, fval] = bintprog(...)
[x,fval, exitflag] = bintprog(...)
[x, fval, exitflag, output] = bintprog(...)

Описание:

·     x = bintprog(f)
·     x = bintprog(f, A, b)
·     x = bintprog(f, A, b, Aeq, beq)
·     x = bintprog(f, A, b, Aeq, beq, x0)
·     x = bintprog(f, A, b, Aeq, beq, x0, options)
·     [x, fval] = bintprog(...)
·     [x,fval, exitflag] = bintprog(...)
·     [x, fval, exitflag, output] = bintprog(...)

Описание

x = bintprog(f) решает задачу целочисленного программирования

x = bintprog(f, A, b) задачу целочисленного программирования

при условии

x = bintprog(f, A, b, Aeq, beq) решает предыдущую задачу при дополнительных условиях типа равенств

x = bintprog(f, A, b, Aeq, beq, x0) устанавливает начальную точку поиска в x0. Если точка x0 находится в недопустимой области, то команда bintprog принимает произвольную начальную точку.

x = bintprog(f, A, b, Aeq, Beq, x0, options) при оптимизации используется принимаемая по умолчанию опция из структуры options, которую можно задать с помощью функции optimset.

[x, fval] = bintprog(...) возвращает fval как значение целевой функции в точке x.

[x,fval, exitflag] = bintprog(...) возвращает параметр exitflag с описанием выходных условий команды bintprog. Более подробно описание даннлй функции и значения отдельных аргументов можно найти в разделе Выходные агументы.

[x, fval, exitflag, output] = bintprog(...) возвращает структуру output, которая содержит информацию о данных результатах оптимизации. См. радел Выходные агументы.

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

Далее в таблице приводится перечень входных аргументов команды bintprog.

f

Вектор с коэффициентами линейной целевой функции.

A

Матрица с коэффициентами линейных ограничений типа неравенств

b

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

Aeq

Матрица с коэффициентами линейных ограничений типа равенств.

beq

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

x0

Начальная точка поиска по данному алгоритму.

options

Структура опций для данного алгоритма.

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

Выходные параметры exitflag и output имеет ряд особенностей.

exitflag

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

 

1

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

0

Число итераций превысило значение options.MaxIter.

-2

Данная задача не имеет решения.

-4

Число перебранных узлов превышает значение options.MaxNodes.

-5

Время перебора превышает значение options.MaxTime.

-6

Число итераций решателя LP для некого узла при решении задачи LP-релаксации превысило значение options.MaxRLP.

output

Структура с информацией о результатах оптимизации. Поле данной структуры имеет вид.

 

iterations

Число выполненных итераций.

 

nodes

Число узлов перебора.

 

time

Превышение времени работы алгоритма.

 

algorithm

Используемый алгоритм.

 

message

Причина остановки работы алгоритма .

Опции

Далее приводится описание опций команды bintprog. Для установки или изменения значений поля данной структуры используется команда optimset.

BranchStrategy

Тип алгоритма, используемого при выборе переменной ветвления в дереве поиска:
  • 'mininfeas' - Выбор переменной с минимальной целочисленной недостижимостью, т.е. выбираются переменные со значением, близким к 0 или 1, но не равным 0 или 1.
  • 'maxinfeas' -- Выбор переменной с максимальной целочисленной недостижимостью, т.е. выбираются переменные со значением близким к 0,5 (принимаемым по умолчанию).
  • Diagnostics

    Отображение диагностической информации о данной функции.

    Display

    Уровень отображения. 'off' нет вывода отображения; 'iter' отображения выводится на каждой итерации.; 'final' (принимается по умолчанию) Отображение только при окончательном выводе.

    DispNodeInterval

    Интервал отображений узлов.

    MaxIter

    Максимальное число допустимых итераций.

    MaxNodes

    Максимальное число решений (или узлов) функции перебора.

    MaxRLPIter

    Максимальное число итераций решателя LP для некого узла при решении задачи LP-релаксации.

    MaxTime

    Максимальное количество времени в секундах для выполнения заданной функции.

    NodeSearchStrategy

    Стратегия алгоритма, используемого для отбора следующего узла при переборе в дереве поиска:
  • 'df' - стратегия глубины первого поиска. На каждом узле дерева поиска, если дочерний узел с нижнего уровня дерева, которое ранее не было использовано, в данном алгоритме проводится выбор одного такого элемента для перебора. В противном случае данный алгоритм переходит к определенному узлу на один уровень вверх по дереву и выбирается дочерний узел на один уровень вниз от данного узла
  • 'bn' - Наилучшая стратегия перебора узлов, при которой отбирается узел с наименьшим предельным значением целевой функции
  • TolCon

    Конечный допустимый предел на нарушение заданного ограничения

    TolFun

    Конечный для значения функции.

    TolXInteger

    Допустимый предел, в котором рассматриваются значения переменных

    TolRLPFun

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

    Алгоритм

    В функции bintprog для решения задачи целочисленного программирования используется алгоритм линейного программирования (LP) на основе метода ветвей и границ. В данном алгоритме проводится перебор оптимальных решений задачи целочисленного программирования путем решения некого набора задач LP релаксации, в котором требование целочисленности переменных заменяется на более слабое ограничение . Данный алгоритм включает в себя:

    1. Перебор целочисленных допустимых решений.
    2. Корректировка наилучшей целочисленной допустимой точки по мере продвижения по дереву поиска.
    3. Проверка невозможности достижения более лучших целочисленных решений посредством рядя задач линейного программирования.

    Далее приводится более детальное описание метода ветвей и границ.

    Ветвление

    Предложенный алгоритм образует дерево поиска путем многократного добавления ограничений на данную задачу, т.е. "ветвления". На этапе ветвления в алгоритме проводится выбор некой переменной х, чье текущее значение не является целым и, далее, накладываются ограничение xj = 0 для формирования одной ветви и ограничение xj = 1 для формирования другой ветви. Весь этот процесс может быть представлен в виде некоего двоичного дерева, узлы которого представляют собой дополнительно налагаемые ограничения. Далее на графике приводится иллюстрация законченного бинарного дерева для задачи с тремя переменными x1, x2 и x3. Отметим, что в общем случае порядок переменных при снижении уровней дерева может не соответствовать обычному порядку индексов переменных.

    Решение о ветвлении

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

    Если задача LP-релаксации для данной текущей точки является недопустимой или ее оптимальное значение больше, чем это значение в наилучшей точке целых значений, то алгоритм удаляет эту точку из данного дерева, после чего не проводится никаких переборов в ветвях ниже данного узла. Далее алгоритм переходит к анализу нового узла согласно методу, задаваемому опцией NodeSearchStrategy.

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

    Если задача LP-релаксации является оптимальной, но не целочисленной, то значение оптимальной целевой функции задачи LP-релаксации является меньшим, чем в наилучшей целой точке, а алгоритм переходит на новую ветвь согласно методу, заданному опцией BranchStrategy.

    Границы

    Искомое решение задачи LP-релаксации определяет нижнюю границу для задачи бинарного целочисленного программирования. Если решение задачи LP-релаксации уже является бинарным целым вектором, то это решение определяет верхнюю границу задачи бинарного целочисленного программирования.

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

    Ограничения по алгоритму

    Алгоритм функции bintprog потенциально может перебрать все 2n бинарных целых векторов, где n есть число переменных. Поскольку для реализации полного алгоритма может потребоваться чрезмерно много времени, то, возможно, наложить некое ограничение на процедуры перебора с помощью следующих опций:

    MaxRLPIter - Максимальное число итераций решателя LP для некого узла при решении задачи LP-релаксации.

    MaxTime - Максимальное количество времени в секундах для выполнения заданной функции.

    Более подробно информацию по данному разделу можно найти в разделе Опции.

    Пример

    Необходимо минимизировать функцию

    при наличии ограничений

    ,

    где x1, x2, x3 и x4 являются бинарными целыми. Выполним следующие команды:

    f = [-9; -5; -6; -4]; 
    A = [6 3 5 2; 0 0 1 1; -1 0 1 0; 0 -1 0 1];
    b = [9; 1; 0; 0];
    x = bintprog(f,A,b)
    
    Optimization terminated successfully.
    
    x =
    
         1
         1
         0
         0
    

    Смотри также

    optimset

    Литература

    [1]  Wolsey, Laurence A., Integer Programming, John Wiley & Sons, 1998.
    [2]  Nemhauser, George L. and Laurence A. Wolsey, Integer and Combinatorial Optimization, John Wiley & Sons, 1988.
    [3]  Hillier, Frederick S. and Lieberman Gerald J., Introduction to Operations Research, McGraw-Hill, 2001.

      В оглавление \ К следующему разделу \ К предыдущему разделу


    Поиск по сайту:

    Система Orphus

    Яндекс.Метрика