МОДЕЛИ ЛИНЕЙНОГО БУЛЕВА ПРОГРАММИРОВАНИЯ Исполнитель

МОДЕЛИ ЛИНЕЙНОГО  БУЛЕВА ПРОГРАММИРОВАНИЯ

План

1. Модели линейной дискретной  оптимизации  с булевыми переменными

2. Преобразование задачи с дискретными переменными к задаче  с булевыми переменными

3. Преобразование задачи линейного булева программирования  к задаче нелинейного булева программирования

1. Модели линейной дискретной  оптимизации
с булевыми переменными

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

Задача оптимизации (минимизации или максимизации)  линейной целевой функции с булевыми переменными и линейными ограничениями в общем виде описывается с помощью одной из следующих моделей линейного булева программирования:

I. Модель А - для задачи минимизации

                                                                    (1)

                                                       (2)

II. Модель В - для задачи максимизации

                                                                    (3)

                                                       (4)

т.е. требуется минимизировать или максимизировать линейную целевую функцию q(x) по булевым переменным x_jÎ{0,1} при выполнении условия, задаваемого системой линейных неравенств вида (2) или (4).

Проблема отыскания решения задачи (1), (2) или (3), (4) может в принципе решаться с применением метода полного перебора, суть которого заключается в переборе всех булевых векторов заданной длины, проверке для каждого вектора выполнения линейных ограничений, вычислении значений целевой функции для допустимых векторов и выборе из них минимального или максимального значения целевой функции. Однако решение, полученное методом полного перебора, связано с большим объемом вычислений, который неосуществим при больших размерностях задачи даже на сверхпроизводительных ЭВМ. Так как каждая из n компонент независимо от других может принимать два значения 0 или 1, поэтому общее число булевых векторов длины n равно 2ⁿ.

Это величина и характеризует сложность алгоритма полного перебора. В связи с тем, что для большинства задач дискретной оптимизации полный перебор неосуществим, были разработаны различные методы  неявного перебора, которые обеспечивают нахождение точного решения без пересмотра всех булевых векторов. Такими являются различные варианты метода отсечений, метода ветвей и границ, метода динамического программирования. Но опыт применения этих методов при решении реальных задач с достаточно большим числом переменных показал, что многие задачи линейного программирования с булевыми переменными еще являются нерешаемыми на ЭВМ из-за нехватки машинного времени. Следовательно, с ростом размера задачи n она становится "труднорешаемой", т.е. практически неразрешимой.

Задача (1), (2) или (3), (4) в числе многих задач комбинаторной оптимизации отнесена к классу "труднорешаемых" или, NP (nо polynomial) - полных       задач. Причина заключается в том, что алгоритма, решающего поставленную задачу за время, ограниченное полиномам от "размера задачи", в настоящее время нет.

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

Сначала рассмотрим широко распространенные практические задачи, описываемые моделями линейного программирования с булевыми переменными.

 {spoiler=Подробнее}

2. Преобразование задачи с дискретными переменными к задаче
с булевыми переменными

Пусть x дискретная переменная, принимающая только целые значения 0,1,2,...,k. Тогда эту переменную можно представить как линейную комбинацию (p+1) булевых переменных   y₀, y₁,...,y_p, т.е.:

                                ,                                      (1)

где  p-наименьшее целое число,  удовлетворяющее условию

                                                                                                 (2)

Пример. Рассмотрим следующую задачу целочисленного программирования

целые.

Переменная x₁ принимает шесть целых значений: 0,1,2,3,4,5. Для этой переменной k₁=5. Возьмем для переменной x₁ наименьшее целое число p₁ , оно определяется из условия (2)

 откуда

Исходя из (1), можно произвести замену переменных:

Переменная x₂ принимает четыре целых значения 0,1,2,3.

Следовательно, для

Исходная задача дискретного программирования преобразована к следующей задаче булева программирования :

Если дискретная переменная x принимает произвольные целые дискретные значения c₁ , c₂ , c₃ ,..., c_k , то в этом случае соотношения (1) и (2) соответственно преобразуются в следующие соотношения:

Таким образом, всегда можно ограничиться рассмотрением задачи булева программирования вместо задачи дискретного программирования.

3. Преобразование задачи линейного булева программирования
к задаче нелинейного булева программирования

Задача вида

                                                                     (1)

                                                                                     (2)

в числе многих задач комбинаторной оптимизации отнесена к классу “труднорешаемых”. Следовательно, для эффективного решения на вычислительных машинах задач большого размера нужно искать алгоритмические принципы, позволяющие определять оптимальное решение без необходимости явно перечислять элементы множества булева вектора   x=(x₁,x₂, . . . , x_n)   2ⁿ.

Именно эта идея неявного (в противоположность явному) перечисления решений  и лежит в основе методов, предлагаемых и исследуемых в данной книге. Идейная основа последних заключается в преобразовании исходной задачи (1), (2) к следующей задаче булева программирования:

                                           .                                           (3)

При переходе от задачи (1), (2) к задаче (3) возникает вопрос: не теряется ли смысловое содержание исходной задачи при переходе к новой форме. Оказывается, не теряется, это объясняется следующим образом: Максимизируя функцию Ф(х) по булевым переменным x=(x₁,x₂,..., x_n ), практически мы , во-первых, максимизируем числитель выражения (3), т.е. линейную функцию булевых переменных

что соответствует задаче (1). Во-вторых, при максимизации выражения (3), минимизируется знаменатель этого выражения, т.е.

Следовательно, минимизация выражения   хотя это процедура не обеспечивает точного выполнения условия (2), а способствует выполнению этого же условия.

В дальнейшем исследовании задачи о рюкзаке (см. п.п. 4.1)будет изложена вычислительная схема получения решения задачи (3) в виде упорядоченного ряда булевых переменных

                                                                                                   (4)

но этот ряд булевых переменных может не удовлетворять выполнению ограничения вида (2). После получения упорядоченного ряда (4) каждый очередной элемент этого ряда поочередно слева направо будет вставлен в выражения (2) и таким образом проверено выполнение условия

до максимального числа первых n¢ переменных упорядоченного ряда (4).

Таким образом, переход от исходной задачи линейного булева программирования вида (1), (2) к новой задаче – максимизации фишерского типа функционала вида (3) логичен.

Контрольные вопросы

1. Роль и место моделей булева программирования в проблеме оптимизации.
2. Основные виды моделей линиейного булева программирования.
3. О полиномиальных и не полиномиальных задачах в дискретной оптимизации.
4. Преобразование задачи с дискретными переменными к задаче с булевыми переменными.
5. Преобразование задачи *** к задаче нелинейного булева программирования.
6. Как записывается функционал Фишерского типа.{/spoilers}