АЛГОРИТМ ДЛЯ РЕШЕНИЯ СМЕШАННО-ЦЕЛОЧИСЛЕННЫХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

В пунктах 32.1 и 32.2 приведены алгоритмы для решения специальных дискретных задач (т-задача и М-за- дача) методом поиска. В пунктах 32.3 и 32.4 с помощью этих специальных алгоритмов обобщаются методы решения задач целочисленного программирования.

Пункт 32.1. т-задача и алгоритм ее решения. Формулировка /п-задачи:

где

Предполагается, что > 0 для всех / = 1, ..., п. Это соответствует предположению о том, что оптимальный план исходной задачи (без требования целочисленности) двойственно невырожденный (см. ниже 32.4). Ясно, что Ь в общем случае не является целочисленным вектором, иначе задача имела бы очевидное решение:

Положим , для которых система

совместна и /(у) = +ос в противном случае, очевидно, что /(у) — выпуклая функция на Н^т и что

Легко видеть, что /п-задача эквивалентна задаче

Пусть () — выпуклое множество в т-мерном пространстве и 0 е <3. Рассмотрим следующую задачу:

Г-задача:

Теорема 32.1. Существует такое оптимальное решение Г-задачи у и соответственно такой х, что

причем х имеет только одну ненулевую компоненту.

Иными словами, оптимальное решение Г-задачи достигается на ребрах конуса

Доказательство. Пусть у — оптимальное решение Г- задачи. Так как — выпуклое множество, то существует опорная плоскость Н, проходящая через у и не пересекающаяся с открытым ядром множества С. Пусть Н = {у: ёУ = р}, где g = (?₁₍ ё'₂, ..., ?„,)> р — число.

Рассмотрим следующую задачу:

Н-задача:

Так как оптимальное решение Г-задачи у является допустимым решением Н-задачи, то

Так как гиперплоскость Н не пересекается с ядром множества <3, то из теоремы 32.1 следует, что

Отсюда имеет место:

Н-задача в форме

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

Пусть х — оптимальное базисное решение этой задачи и у = Ах (х имеет только одну ненулевую компоненту). Чтобы доказать, что у является оптимальным решением Г-задачи, достаточно доказать, что у е Г(С}).

Предположим противное. Пусть у ёГ(ф).

Очевидно, что в этом случае у является внешней точкой множества (?. Ясно, что существует такое X е [0,1), что #еГ(<3).

Отсюда: ха — допустимое решение задачи

Следовательно, f{Ху)<хХс, и так как >,<1, то хХс < что противоречит предположению об оптимальности у. Значит, //еГ(С}).

Теорема доказана.

Эта теорема позволяет решать Г-задачу простым перебором всех точек пересечения ребер конуса К_А с Г(<3).

При решении /п-задачи методом поиска лучше всего брать в качестве выпуклых множеств <3 — открытые прямоугольники следующего вида

где

Через Н_к⁺(Н‘_к) обозначим гиперплоскость в/п-мерном пространстве

В соответствии с теоремой 32.1 можно проверить, что задача

решается с помощью соотношения

где а_к?_! — элемент матрицы А из исходной /п-задачи.

Из следствия 31.2 пункта 31.1 следует, что

Множество можно определить следующим образом. Пусть, например,

Тогда

По построению ясно, что для всех ?.

Отметим, что в ходе вычисления не надо запоминать элементы множества {у: у е 0,; у = Ь(тос11)} и их значения {(у).

Замечание к блок-схеме, в может принимать несколько значений, если г' лежит на пересечении нескольких гиперплоскостей, дающих ограничения для 0_;.

Пункт 32.2. Блок-схема 6 (упрощенная).

Блок-схема 6 Определение Б множеств

Пункт 32.2 (методы решения М-задачи).

М-задача является обобщенной формой /п-задачи. Формулировка М-задачи:

где А, с, Ь, х, у — определяются как в пункте 32.1.

Для понимания предполагаемых методов важно отметить, что компоненты вектора с1, как правило, не являются большими отрицательными числами.

Положим Р(у) = пипсх,

для тех у, для которых система

совместна и Р(у) = +оо — в противном случае.

Очевидно, что выпуклая функция на 11"' и М-задача эквивалентна задаче

Ясно,что

где х является оптимальным решением задачи

По предположению х не очень отличается от 0, т. е. вектор х не далеко от начала координат пространства К"'.

Первый метод решения Ш-задачи.

Строится последовательность у¹, у², ..., у^г, в которой у'Ч — оптимальное решение задачи.

Построение такой последовательности легко осуществляется с помощью алгоритма для решения т-задачи.

Имеем:

Соответственно, строим последовательность С¹, <3²,

С, где

Ясно, что & > р. Если выполняется ,

то у¹ — оптимальное решение М-задачи. Если б⁵ > /^-г, то строим /^г+1 и С⁺¹ и продолжаем проверку. Если оптимальное решение М-задачи значительно удалено от 0, то для нахождения решения потребуется много итераций.

Второй метод решения М-задачи.

Как и для решения /п-задачи, строится такая последовательность выпуклых множеств <3,, что Ах е и 0 е Q?, х — оптимальное решение задачи

Но вместо обобщенной Г-задачи решаем задачу

Ясно,что

Таким образом, получаем нижнюю оценку для решения Г-задачи и неравенство

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

Третий метод решения М-задачи (непосредственное применение метода поиска).

Для решения обобщенной Г-задачи применяется следствие 31.2 из п. 31.1. Чтобы найти г¹ такое, что

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

При решении предыдущей Г-задачи и используя результаты предыдущих итераций (минимумы на гиперплоскостях). Такой алгоритм сходится так же быстро, как и алгоритм для решения т-задачи? Но первая итерация очень трудоемкая (сравни алгоритм из п. 31.4). Для сходимости третьего метода не играет роли, на сколько вектор х удален от 0.

Четвертый метод решения М-задачи (комбинированный метод). Этот метод является комбинацией второго и третьего метода.

Пренебрежем ограничением Вх < с1 при нахождении минимума на границе выпуклых множеств и начнем решать задачу вторым методом, но пока не требуем, чтобы Ах е<3, .

Начиная с этой итерации, когда Ах е <3, , ищем минимумы на гиперплоскостях методом линейного программирования, как в третьем методе. Такой метод не на много хуже, чем третий метод, но менее трудоемкий.

Для сходимости третьего и четвертого методов условие Су > 0, у = 1,..., п (двойственная невырожденность оптимального плана исходной задачи) не является необходимым.

Пункт 32.3 (алгоритм решения для специального класса задач). Рассмотрим задачу смешанно-целочисленного программирования в эквивалентной форме (IX).

Если для оптимального решения (х*_ы,у’_к) задачи выполняется неравенство

то (Хн,у1) будет оптимальным решением задачи (IX). Аналогично тому, как это было сделано в [3], можно показать, что это имеет место для определенного класса задач.

Для решения задачи (X) предлагается следующий метод. Решим задачу

для всех р е Р(м) методом динамического программирования [3] или методом из § 26, или каким-либо другим методом динамического программирования очень эффективно можно решать задачу (XI) для всех элементов группы р(ы).

Трудоемкость при решении задачи (XI) для всех р е еЕ(х) возрастает лишь незначительно по сравнению с решением задачи (XI) только для одного значения р. Оптимальное решение этой задачи есть функция ц - д;_Лг(р). Потом решаем задачу

для всех методом поиска из пункта 32.1 (XII т-

задача).

Пусть оптимальное решение этой задачи г/_А.(р). Найдем р’ из условия:

Легко проверить, что ягдХр*), ?/_А(р*) — оптимальное решение задачи (X).

Значительно уменьшить вычислительную работу можно следующим образом. Упорядочим все решения задачи (XI) по возрастанию

Пусть I число элементов группы Р(м).

Построим последовательность ЧЧр¹),..., Ч^р') решения задачи (XI) для р', 1 < I < г < 1.

Если

то *(р⁸), р(р^я) — оптимальное решение задачи.

В противном случае определим Ч'(р^г+1) и продолжаем проверку условия (32.2) для г: = г + 1.

Пункт 32.4 (общий алгоритм). Рассмотрим случай, когда для оптимального решения задачи (X) Хд^р’), г/*(р*) не выполняется соотношение (32.1).

Ищем последовательность ?-оптимальных решений задачи

алгоритмом из § 30 (см. упрощенную блок-схему).

Последовательно для каждого х‘_к, ?=1,2,..., решаем задачу

Задача (XIV) решается одним методом из пункта 32.2 (XIV — М-задача). Пусть имеем

Если

то — оптимальное решение задачи (IX).

В противном случае определим и продолжаем проверку условия (32.3) для г := г + 1.

Если для решения М-задачи применяли третий или четвертый методы пункта 32.2, тогда этот метод и сходится, если для некоторых у еу =0. Если среди компонентов вектора с* имеются нулевые, то поступаем так же, как это предлагается в п. 32.2.