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

Рассмотрим полностью целочисленную задачу линейного программирования (13.4) – (13.7), в которой n1 = n.

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

Обозначим через N совокупность небазисных переменных и на основании последней симплексной таблицы выразим целевую функцию и все переменные через небазисные переменные :

Первый алгоритм гомори решения полностью целочисленных задач . (13.10)

Так как – нецелая величина, обозначим ближайшее целое число, не превосходящее , через [ ] (целая часть ) и определим дробную часть числа ({ }):{ }= – .

Очевидно, { }0.

Теорема 13.5. Пусть – допустимое решение задачи Первый алгоритм гомори решения полностью целочисленных задач . Тогда соотношение

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

(13.11)

определяют правильное отсечение.

Доказательство. Запишем выражение (13.10) в виде

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

Используя выражение (13.11), получим

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

или

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

На основании предположения теоремы о допустимости решения задачи Первый алгоритм гомори решения полностью целочисленных задач – целые. Величины целые по определению. Следовательно, тоже целое.

Докажем, что . Предположим, что . Это значит, что

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

По определению дробной части . По условию теоремы x – допустимое решение задачи Первый алгоритм гомори решения полностью целочисленных задач , поэтому . Следовательно, Первый алгоритм гомори решения полностью целочисленных задач , . Отсюда Первый алгоритм гомори решения полностью целочисленных задач , или, что то же самое, . Итак, – нецелое, а это противоречит только что доказанному. Следовательно, предположение неверное. Теорема доказана.

Следствие. Любое оптимальное решение X(D, F) задачи (D, F), не являющиеся допустимым решением задачи Первый алгоритм гомори решения полностью целочисленных задач не удовлетворяет условию правильного отсечения (13.11).

Доказательство. Пусть X(D, F) – оптимальное решение задачи (D, F), –дробное. Покажем, что не удовлетворяет условию отсечения. Из оптимальности плана следует, что . Поэтому Первый алгоритм гомори решения полностью целочисленных задач . Учитывая это, подставим в выражение (13.11):

что противоречит условию .

Важной проблемой метода отсечения является нарастание количества дополнительных ограничений по мере решения вспомогательных задач, оптимальные планы которых будут содержать нецелые координаты, т.е. возникает проблема размерности. Гомори предложил прием, ограничивающий размеры рассматриваемых расширенных симплексных таблиц числом (n+2)(k+1), где n – количество переменных задач , k – число ее небазисных переменных. Этот прием основан на том, что дополнительные ограничения (правильные отсечения) интересуют нас лишь как способ отсечения нецелочисленного оптимального решения и перехода от задачи к задаче . Заметим, что переменная выводится из базиса сразу же после введения ограничения:

,

.

Идею Гомори проиллюстрируем на конкретном примере.

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

максимизировать

при условиях

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

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

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

Решение задачи :

Номер итерации Базисные переменные Первый алгоритм гомори решения полностью целочисленных задач
-1
F -7 -9
I -1/3 1/3
22/3 -1/3 9/2
F -10
II 7/2 7/22 1/22
9/2 -1/22 3/22
F 28/11 15/11

После II итерации получаем в последней симплексной таблице оптимальное решение . Это решение не целочисленное. Поэтому переходим к построению задачи . С нецелочисленным значением две строки – первая и вторая. Номер k выбираем из условия

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

В нашем случае . Тогда для образования сечения выбирается первая строка, т.е. k= 1. Запишем первое сечение Гомори:

.

Так как {7/2} = 1/2, {7/22} = 7/22, {1/22} = 1/22, получаем

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

Перенеся члены с переменными в правую часть и введя неотрицательную балансовую переменную , получим сечение в форме 3-го дополнительного уравнения Первый алгоритм гомори решения полностью целочисленных задач . (13.12)

Присоединив его к предыдущим двум, придем к задаче . Ее решение можно начинать с окончательной симплексной таблицы для , добавив уравнение (13.12).

Решение задачи :

Номер итерации Базисные переменные Первый алгоритм гомори решения полностью целочисленных задач Первый алгоритм гомори решения полностью целочисленных задач
7/2 7/22 1/22
9/2 -1/22 3/22 11/3
1/2 7/22 1/22 -1 11/7
F 28/11 15/11
I -1
32/7 1/7 -1/7
11/7 1/7 -22/7
F

В уравнении (13.12) переменная может быть базисной, однако коэффициент при ней равен –1, поэтому в исходной для задачи таблице базисное решение не является опорным . Значит, необходимо получить исходное опорное решение.

Выделим третью дополнительную строку и для столбцов, имеющих в ней положительные элементы (в нашем случае для 3-го и 4-го), вычислим отношения . Если найдется столбец, для которого min{ } соответствует выделенной строке, то данные столбец и строку выбираем в качестве разрешающих, после чего переменная сразу же выводится из базиса и новое решение становится опорным. Если такого столбца нет, то в качестве разрешающих выбираются столбец с наименьшим элементом в выделенной строке и строка по min{ }. После этого начинается процесс преобразования симплексной таблицы.

В данном случае min{ } соответствует выделенной строке 3-го столбца. Поэтому, выбрав за разрешающие 3-ю строку и 3-й столбец, сразу получим опорное решение, которое одновременно и оптимально: . Так как оно опять не целочисленное, то перейдем к построению задачи Первый алгоритм гомори решения полностью целочисленных задач .

Соответствующие сечение следующее:

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

Так как Первый алгоритм гомори решения полностью целочисленных задач Первый алгоритм гомори решения полностью целочисленных задач Первый алгоритм гомори решения полностью целочисленных задач имеем новое,4-е уравнение

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

Введя неотрицательную балансовую переменную , получим сечение 4-го дополнительного уравнения для задачи Первый алгоритм гомори решения полностью целочисленных задач :

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

После выполнения I итерации имеем опорное решение которое одновременно и оптимальное и целочисленное. Таким образом, , .

Решение задачи Первый алгоритм гомори решения полностью целочисленных задач :

Номер итерации Базисные переменные Первый алгоритм гомори решения полностью целочисленных задач Первый алгоритм гомори решения полностью целочисленных задач
32/7 1/7 -1/7
11/7 1/7 -22/7
4/7 1/7 6/7 -1 2/3
F
I
-1
-4
-7
F

Дадим геометрическую интерпретацию решения задачи. На рис. 13.2 построена область допустимых решений задачи и показано определение ее оптимального решения. При решении задачи введено первое сечение Гомори Первый алгоритм гомори решения полностью целочисленных задач . Исключив из него переменные и с помощью исходных уравнений, получим . Этому неравенству соответствует граничная прямая , отсекающая из области найденное нецелочисленное решение , но сохраняющая все целочисленные решения.

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

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

Теорема 13.6. Пусть множество оптимальных планов задачи ограничено и выполняются следующие условия:

1) гарантирована целочисленность целевой функции (например, все – целые) и строка целевой функции учитывается при выборе строки для построения правильного отсечения:

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

Тогда первый алгоритм Гомори требует лишь конечного числа больших итераций.

Метод Отсечений

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

Первый алгоритм гомори решения полностью целочисленных задач (13.24)

Первый алгоритм гомори решения полностью целочисленных задач (13.25)

Будем говорить, что отсечение (13.24) более эффективно, чем отсечение (13.25), если для всех j, причем хотя бы при одном j выполняется строгое неравенство.

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

Оптимальное значение целевой функции (F = 63) задачи , рассмотренное в предпоследнем примере, достигается в точке . Поскольку значение F является целым, соответствующая строка не может быть выбрана в качестве производящей. Так как Первый алгоритм гомори решения полностью целочисленных задач , первое практическое правило не позволяет осуществить выбор производящей строки. Применим второе правило. Запишем отсечения, соответствующие производящим строкам с базисными переменными и :

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

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

Так как

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

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

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

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

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

Второе практическое правило также не применимо. В этом случае для образования сечения выбирается первая их данных строк.

Основные недостатки методов отсечений.

1. Ни один тип отсечений не обеспечивает высокой эффективности соответствующих вычислительных процедур.

2. Методы отсечений не подходят для решения целочисленных задач больших размерностей.

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

В основе комбинаторных методов лежит идея перебора всех допустимых целочисленных решений. Наиболее известным из них является метод ветвей и границ, который также опирается на процедуру решения задачи с ослабленными ограничениями. При таком подходе из рассматриваемой задачи получаются две подзадачи путем специального разбиения пространства решений и отбрасывания областей, не содержащих допустимых целочисленных решений. В случае, когда целочисленные переменные являются булевыми, применяются комбинаторные методы. Булевы свойства переменных существенно упрощают поиск решения.

Метод ветвей и границ

Впервые метод ветвей и границ был предложен в 1960 г. А. Лэндом и А. Дойгом применительно к задаче целочисленного линейного программирования. Фактически «второе рождение» этого метода связано с работой Дж. Литтла, К. Мурти, Д. Суини и С. Кэрела. В ней же было предложено и принятое теперь название метода: «метод ветвей и границ». Он применим как к полностью, так и частично целочисленным задачам.

Приведем описание идеи данного метода. Рассматривается целочисленная (частично целочисленная) задача линейного программирования:

минимизировать

Первый алгоритм гомори решения полностью целочисленных задач (13.26)

при условиях

Первый алгоритм гомори решения полностью целочисленных задач (13.27)

Первый алгоритм гомори решения полностью целочисленных задач (13.28)

(13.29)

Многогранное множество (13.27) – (13.28) предполагается ограниченным. Как в методах отсечения, процесс начинается с решения задачи линейного программирования (13.26) – (13.28). Если полученный при этом оптимальный план Первый алгоритм гомори решения полностью целочисленных задач не удовлетворяет условиям целочисленности (13.29), то значение целевой функции Первый алгоритм гомори решения полностью целочисленных задач на этом плане дает нижнюю границу для исходного оптимума, т.е. Первый алгоритм гомори решения полностью целочисленных задач . Пусть – целочисленная переменная, значение которой в оптимальном плане задачи является дробным . Интервал

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

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

Если границы изменения заранее не заданы, то их можно вычислить, решив для этого две вспомогательные задачи линейного программирования, заключающиеся в максимизации и минимизации при условиях (13.27) – (13.28). Введение их в задачу без учета ограничения (13.29) порождает две не связанные между собой задачи. В этом случае говорят, что задача разветвляется (или разбивается) на две подзадачи. Осуществляемый в процессе ветвления учет ограничения (13.29) позволяет исключить части многогранника допустимых решений, не содержащие точки с целыми координатами. Теперь каждая подзадача решается как задача линейного программирования (с целевой функцией исходной задачи) с условиями (13.27) и дополнительным ограничением . Если полученный оптимум оказывается допустимым для целочисленной задачи, такое решение следует зафиксировать как наилучшее. При этом нет необходимости продолжать «ветвление» подзадачи, поскольку улучшить найденное решение, очевидно, не удастся. В противном случае подзадача вновь разбивается на две подзадачи при условии целочисленности переменных, значения которых в оптимальном решении не являются целыми. Как только полученное допустимое целочисленное решение одной из подзадач оказывается лучше имеющегося, оно фиксируется вместо зарегистрированного ранее. Процесс ветвления продолжается до тех пор, пока каждая подзадача не приведет к целочисленному решению или пока не будет установлена возможность улучшения имеющегося решения. Зафиксированное допустимое решение и будет оптимальным.

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

Вышеизложенное можно представить в виде некоторого дерева задач, в котором вершина отвечает исходному плану , а каждая из соединенных с ней ветвью вершина отвечает оптимальному плану задачи (13.26) – (13.28) при дополнительном условии . Каждой из вершин приписывается граница Первый алгоритм гомори решения полностью целочисленных задач , равная минимальному (максимальному – в случае максимизации) значению z для соответствующей задачи. Ясно, что Первый алгоритм гомори решения полностью целочисленных задач для всех k.

Опишем формально данный алгоритм.

1. Задание множества . Множество задается условиями (13.27) – (13.29).

2. Задание множества . Множество ( определяется условиями (13.27) – (13.28) и дополнительным условием

Первый алгоритм гомори решения полностью целочисленных задач (j = 1, 2,…, n). (13.37)

3. Вычисление границ (оценок). Для множества оценка Первый алгоритм гомори решения полностью целочисленных задач , где – оптимальный план задачи линейного программирования (13.26) – (13.28). Для множества оценка Первый алгоритм гомори решения полностью целочисленных задач , где Первый алгоритм гомори решения полностью целочисленных задач – оптимальный план задачи линейного программирования (13.26), (13.27), (13.30). Если множество оказывается пустым, то полагаем Первый алгоритм гомори решения полностью целочисленных задач ( – в случае максимизации).

4. Вычисление планов. Если удовлетворяет условию целочисленности (13.29), то – оптимальный план задачи (13.26) – (13.29). Если Первый алгоритм гомори решения полностью целочисленных задач удовлетворяет условию целочисленности (13.29), то Первый алгоритм гомори решения полностью целочисленных задач – оптимальный план задачи (13.26), (13.27), (13.29), (13.30) и исходной задачи (13.27) – (13.29).

5. Ветвление. Оно необходимо в том случае, когда план Первый алгоритм гомори решения полностью целочисленных задач не удовлетворяет условию целочисленности (13.29). Пусть Первый алгоритм гомори решения полностью целочисленных задач – один из нецелочисленных компонентов этого плана . Тогда множество Первый алгоритм гомори решения полностью целочисленных задач разбивается на два множества: Первый алгоритм гомори решения полностью целочисленных задач , где

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

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

Замечание 1. Если все коэффициенты в соотношении (13.26) нецелые при и равны нулю при , то оценку Первый алгоритм гомори решения полностью целочисленных задач можно заменить более сильной:

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

где ]a[ – наименьшее целое число, не меньшее чем а.

Замечание 2. Вопрос о наилучшем способе выбора переменной ветвления или последовательности решения конкретных задач в настоящее время не решен.

Пример. Максимизировать

(13.31)

при условиях

(13.32)

– целые. (13.33)

0-й шаг. Оптимальный план задачи (13.31) – (13.33) следующий: Первый алгоритм гомори решения полностью целочисленных задач . Имеем Первый алгоритм гомори решения полностью целочисленных задач . План не удовлетворяет условию целочисленности (13.33). Возьмем его не целочисленный компонент и разобьем на два множества:

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

Первый алгоритм гомори решения полностью целочисленных задач , Первый алгоритм гомори решения полностью целочисленных задач .

1-й шаг. Решим две ЗЛП, состоящие из в максимизации функции (13.31) по и .

Решение задачи Первый алгоритм гомори решения полностью целочисленных задач :

Номер итерации Базисные переменные Первый алгоритм гомори решения полностью целочисленных задач
-1
F -7 -9
I -1/3 1/3
22/3 -1/3 9/2
F -10

II 10/3
11/3
F

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

Решение задачи Первый алгоритм гомори решения полностью целочисленных задач :

Номер итерации Базисные переменные Первый алгоритм гомори решения полностью целочисленных задач
-1
-1
F -7 -9
I -1 11/3
-1
F -9
II -3 -10
-1
F

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

Производим разветвление по :

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

где Первый алгоритм гомори решения полностью целочисленных задач , Первый алгоритм гомори решения полностью целочисленных задач .

Переобозначения: Первый алгоритм гомори решения полностью целочисленных задач .

2-й шаг. Решаем две задачи линейного программирования, заключающиеся в максимизации функции (13.31) по множествам Первый алгоритм гомори решения полностью целочисленных задач .

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

Номер итерации Базисные переменные Первый алгоритм гомори решения полностью целочисленных задач
-1
F -7 -9
I 22/7 1/7 7/2
1/7 1/7
F -8
II 11/7
32/7
F

Максимум достигается при .

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

#93. РЕАЛЬНЫЙ ВАРИАНТ ЕГЭ-2017 ПО МАТЕМАТИКЕ ЗА 23 МИНУТЫ!


Похожие статьи.

Понравилась статья? Поделиться с друзьями: