Министерство высшего и профессионального образования РФ

Тульский государственный университет

КАФЕДРА ПРИКЛАДНОЙ МАТЕМАТИКИ И ИНФОРМАТИКИ

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту по дисциплине

«ВАРИАЦИОННОЕ ИСЧИСЛЕНИЕ И ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ»

на тему:

«Методы отсечения»

Тула 2003 г.

Содержание

Введение

1. Постановка линейной целочисленной задачи

2. Теоретические основы методов отсечения

3. Первый алгоритм Гомори

4. Второй алгоритм Гомори

5. Алгоритм Дальтона и Ллевелина

6. Алгоритм Данцига

7. Некоторые выводы

Заключение

Список литературы

Приложение

Введение

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

Исторически первой задачей целочисленного типа является опубликованная венгерским математиком Е. Эгервари в 1932 г. задача о назначении персонала.

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

1. Постановка линейной целочисленной задачи

Среди совокупности п неделимых предметов, каждый i-и (i=1,2,…, п) из которых обладает по i-й характеристике показателем и полезностью найти такой набор, который позволяет максимизировать эффективность использования ресурсов величины .

Математическая модель этой задачи может быть представлена следующим образом:

в области, определенной условиями

(1)

(2)

- целые, . (3)

найти решение при котором максимизируется (минимизируется) значение целевой функции

(4)

Если , то (1–4) является моделью задачи целочисленного программирования, если - моделью задачи частично целочисленного программирования.

Частным случаем задачи целочисленного программирования является задача с булевыми переменными. Ее математическая модель в общем виде записывается следующим образом:

в области, определенной условиями

(5)

(6)

найти решение , при котором максимизируется (минимизируется) значение функции

(7)

К классу задач целочисленного программирования примыкают задачи, в которых условие целочисленности всех или части переменных заменено требованием дискретности. А именно, для каждой j-и переменной заранее определен набор значений (не обязательно целых), которые она может принимать: где .

Предполагается, что ранжированы, т.е. . Математическая модель общей задачи дискретного программирования может быть представлена следующим образом:

в области, определенной условиями

(8)

(9)

найти решение , при котором максимизируется (минимизируется) линейная функция

(10)

Условие (9) определило название этого класса; задач. Если , то (8–10) называется задачей дискретного программирования; если , то (8–10) называется задачей частично дискретного программирования.

Нетрудно видеть, что условие (2–3) задачи (1–4) и условие (6) задачи (5–7) являются частным случаем условия (9) задачи (8–10). Действительно, (2–3) соответствует тому случаю, когда для . Условие (9) соответствует случаю, когда .

Для задач целочисленного типа определено понятие допустимого и оптимального решения.

Вектор , удовлетворяющий условиям (1–3) (соответственно (8–9)), называется допустимым решением задачи (1–4) (соответственно (8–10)). Допустимое решение, при котором функция (4) (соответственно (10)) достигает наибольшего (наименьшего) значения, называется оптимальным решением.

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

ПРИМЕР. В области, определенной условиями

– целые

найти максимум функции .

Решим задачу геометрически (рис. 1). Область поиска экстремума – многоугольник ODABC, но так как линия уровня целевой функции параллельна стороне АВ многоугольника, экстремум достигается в вершинах и , а также в любой точке отрезка АВ, и равен 7.

(рис. 1)

Однако нас интересуют лишь точки с целочисленными координатами, следовательно, ни А, ни В не являются допустимым решением задачи. Округляя значение координат А, получим Но точка А' не принадлежит области поиска. Можно показать, что целочисленный оптимум достигается в точках N (3; 2) и M (2; 3) и равен 5. Обе точки внутри области поиска.

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

2. Теоретические основы методов отсечения

Запишем общую задачу целочисленного программирования: в области, определенной условиями

(11)

(12)

- целые, (13)

максимизировать функцию

(14)

Назовем для кратности задачу (11–14) (£^ц, C) – задачей. Соответствующую ей задачу без требования целочисленности переменных, т.е. задачу (11, 12, 14) назовем (£, C) – задачей. Поставим вопрос: нельзя ли решение (£^ц, C) – задачи получить путем решения некоторой специальным образом построенной задачи без требования целочисленности переменных и такой, что оптимальные решения исходной (£^ц, C) – задачи и задачи без требований целочисленности переменных будут совпадать. Другими словами: нельзя ли хорошо изученный аппарат решения задач линейного программирования приспособить к решению целочисленных задач. Принципиальный ответ на этот вопрос дает следующая теорема.

Теорема. Пусть £ – многогранник, £^ц – множество его целых точек, R – выпуклая, линейная оболочка множества £^ц, тогда:

1) R=R^ц – целочисленный многогранник;

2) R^ц = £^ц;

3) R* – множество опорных решений задачи (£^ц, C) содержится в многограннике R^ц.

Доказательство. Докажем, что R – целочисленный многогранник. По условию теоремы £ – многогранник, поэтому множество его целых точек (оно обозначено через £^ц) конечно. Поскольку R – выпуклая линейная оболочка этого конечного множества точек, R – тоже многогранник.

По самому определению выпуклой линейной оболочки, она содержит все опорные планы множества, на которое она натянута, т.е. многогранник R содержит все целочисленные точки £^ц. Поэтому R – целочисленный многогранник. Обозначим его через R^ц. Первая часть теоремы доказана.

Докажем, что R^ц совпадает с £^ц. Так как R – выпуклая оболочка точек множества £^ц, то £^ц R^ц.

Покажем, что справедливо также и противоположное неравенство–включение, т.е. R^ц£^ц. Для этого выберем некоторый произвольный элемент х°R^ц. Поскольку R^ц содержит все опорные решения задачи (£^ц, C), то х° удовлетворяет условиям задачи (£^ц, C), т.е. х°£^ц. Но поскольку произвольный элемент из R^ц принадлежит £^ц, то очевидно, что справедливоR^ц£^ц. Сопоставляя противоположные включения R^ц£^ц и £^цR^ц приходим к выводу: что £^ц=R^ц. Вторая часть теоремы также доказана.

Доказательство 3-го пункта теоремы является совершенно очевидным. Так как R^* – множество опорных решений задачи (£^ц, C), то R^*£^ц но £^ц=R^ц, поэтому R^*R^ц

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

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

Доказанная теорема и следствие из нее показывают принципиальную возможность замены решения задачи типа (£^ц, C) некоторой процедурой построения и решения вспомогательной задачи типа (£, C), однако не дают алгоритма решений. К тому же построение выпуклой оболочки множества £^ц реальных задач – чрезвычайно сложная, а подчас практически неразрешимая задача,

В 1954 г. Дж. Данциг высказал идею о том, что построение выпуклой оболочки целочисленной области для задачи (£^ц, C) можно осуществлять поэтапно и решать получаемые при этом задачи. Однако при этом возникли вопросы как строить ограничения новой задачи и как обеспечить конечность процесса.

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

Алгоритм Р. Гомори состоит из следующих процедур:

1. Решается (£, C) – задача, соответствующая исходной (£^ц, C) – задаче.

2. Полученное оптимальное решение (£, C) – задачи, если оно существует, проверяется на целочисленность. Если условие целочисленности выполняется по всем переменным, то оптимальное решение (£, C) – задачи есть оптимальное решение (£^ц, C) – задачи. Если условие целочисленности не выполняется хотя бы по одной координате, то переходят к третьему этапу. Если (£, C) – задача, оказывается неразрешимой, то (£^ц, C) – задача тоже решения не имеет.

3. Строится дополнительное ограничение, обладающее тем свойством, что с его помощью отсекается часть области, в которой содержится оптимальное решение (£, C) – задачи и не содержится ни одного допустимого решения (£^ц, C) – задачи. Процесс построения дополнительных ограничений и решения получаемых при этом (£, C) – задач продолжается до тех пор, пока не получим целочисленного решения или не убедимся в неразрешимости задачи.

При этом свойства, которыми должно обладать каждое из дополнительных ограничений при переходе от одной задачи к другой следующие:

1. дополнительное ограничение должно быть линейным, чтобы оставаться в области применимости аппарата линейного программирования;

2. дополнительное ограничение должно отсекать часть области, в которой не содержится допустимых решений целочисленной (£^ц, C) – задачи, но есть найденное оптимальное решение нецелочисленной (£, C) – задачи, т.е. ограничение должно обладать свойством правильности, которое не позволяет потерять оптимальное решение исходной (£^ц, C) – задачи.

Пусть х (£, C) – оптимальное решение (£, C) – задачи, которое является недопустимым решением для (£^ц, C) – задачи. Неравенство

(15)

определяет правильное отсечение, если удовлетворяет

а) условию отсечения: x(£, C) удовлетворяет неравенству (15)

б) условию правильности: любое допустимое решение задачи (£^ц, C), удовлетворяет неравенству (15).

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

3. Первый алгоритм Гомори

Следуя общей схеме методов отсечения, решим (£, C) – задачу (11, 12, 14), соответствующую (£^ц, C) – задаче (11–14). Пусть x(£, C) – ее оптимальное решение. Проанализируем координаты x(£, C) на целочисленность. Если все координаты вектора x(£, C) целые, то x(£, C) = x(£^ц, C). Если хотя бы одна координата, пусть x_i, будет нецелой, поступим следующим образом.

Обозначим через N совокупность небазисных переменных и на основании последней симплексной таблицы запишем разложение x_i по небазисным переменным x_i, jN