Дискретное программирование

Размещено на /

Министерство образования Российской Федерации

Уфимский государственный авиационный технический университет

Кафедра автоматизированных технологических систем


Курсовая работа

По дисциплине: Программирование систем

На тему: Дискретное программирование


Уфа 2011

Содержание


1. Введение

2. Задачи с неделимостями

2.1 Пример кода на языке Java

2.2 Пример кода на языке C#

3. Комбинаторные задачи

4. Задачи с разрывными целевыми функциями

4.1 Основные идеи и принципы

4.2 Описание алгоритма

4.3 Пример решения ЦЗЛП методом Гомори

4.3.1 Итерация 1

4.3.1 Итерация 2

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

5.1 Общая схема метода "ветвей и границ"

5.2 Решение ЦЗЛП методом ветвей и границ

6. Заключение


1. Введение


Основные понятия. Многие экономические задачи характеризуются тем, что объемы управляемых ресурсов (в силу тех или иных объективных свойств) могут принимать только целые значения. Математическая формализация данных ситуаций приводит к моделям дискретного программирования. В общем виде задача дискретного программирования может быть сформулирована как задача нахождения максимума (или минимума) целевой функции f(x1, x2,...,xn) на множестве D, определяемом системой ограничений


Дискретное программирование


где Ω — некоторое конечное, или счетное*, множество. Условие х∊Ω. называется условием дискретности. Особое место среди дискретных задач занимает целочисленная задача линейного программирования в канонической форме (ЦКЗЛП):

* Напомним, что примерами счетных множеств являются множества натуральных, целых и рациональных чисел.


Дискретное программирование


где Z+ ={0; 1; 2; ...} — множество неотрицательных целых чисел.

Заметим, что в некоторых ситуациях требование "целочисленности" может быть наложено лишь на некоторые переменные xj, что кардинально не меняет характера задачи.

Дискретное программирование


Принципиальная сложность, вызываемая наличием условий целочисленности в системе ограничений оптимизационной задачи, состоит в том, что в значительном количестве случаев невозможно заменить дискретную задачу ее непрерывным аналогом и, найдя соответствующее решение, округлить его компоненты до ближайших целых значений. Пример, показанный на рис.1, демонстрирует, что при округлении оптимального плана х* обычной задачи ЛП до целых значений получается точка ([х1*],[x2*]), не принадлежащая области допустимых планов задачи D. Условимся целую часть числа хj. обозначать [хj], а дробную — как {хj}. Тогда хj =[хj]+{хj}. Отдельно следует добавить, что если даже оптимальный план непрерывной задачи, округленный до целых значений компонент, окажется допустимым, то целевая функция может вести себя так, что ее значение будет на нем существенно "хуже", чем на оптимальном плане целочисленной задачи.

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

Ш задачи с неделимостями;

Ш экстремальные комбинаторные задачи;

Ш задачи с разрывными целевыми функциями;

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


2. Задачи с неделимостями


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

Классическим представителем задач данного класса стала так называемая задача о ранце. Ее фабула носит достаточно условный характер и состоит в том, что солдат (или турист), собирающийся в поход, может нести груз весом не более W кг. Этот груз может состоять из набора предметов n типов, каждый предмет типа j весит wj кг и характеризуется некоторой "полезностью" uj, j < 1: n. В рамках описанной ситуации вполне естественным представляется вопрос: сколько предметов каждого вида нужно положить в ранец, чтобы его суммарная полезность была максимальной? Если в качестве компонент плана хj. принять количество укладываемых предметов типа j, то данную задачу можно записать:


Дискретное программирование


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


2.1 Пример кода на языке Java


int knapsack(int weights[], int costs[], int needed) {

int n = weights.length;

int dp[][] = new int[needed + 1][n + 1];

for (int j = 1; j <= n; j++) {

for (int w = 1; w <= needed; w++) {

if (weights[j-1] <= w) {

dp[w][j] = Math.max(dp[w][j - 1], dp[w - weights[j-1]][j - 1] + costs[j-1]);

} else {

dp[w][j] = dp[w][j - 1];}

}

}

return dp[needed][n];

}


2.2 Пример кода на языке C#


int knapsack(int[] weights, int[] costs, int needed)

{ int n = weights.Length;

int[,] dp = new int[needed + 1, n + 1];

for (int j = 1; j <= n; j++)

{ for (int w = 1; w <= needed; w++)

{ if (weights[j - 1] <= w)

{ dp[w, j] = Math.Max(dp[w, j - 1], dp[w - weights[j - 1], j - 1] + costs[j - 1]);

}

else

{ dp[w, j] = dp[w, j - 1];}

}

}

return dp[needed, n];}


3. Комбинаторные задачи


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

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


Дискретное программирование


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

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

дискретный программирование итерация комбинаторный

Дискретное программирование


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


1, если в маршруте предусмотрен переезд из пункта i в j,

xi,j = 0, если в маршруте не предусмотрен переезд из пункта i в j,

причем по условию задачи xii =0, i<1:n.


Допустимыми планами служат связные маршруты, однозначно определяемые упорядоченным набором посещаемых пунктов:

Дискретное программирование


Каждый такой маршрут можно отождествить с перестановкой n чисел (упорядоченной выборкой из n элементов по n). В свою очередь, таким

перестановкам взаимно однозначно соответствуют матрицы X, у которых в каждой строке и каждом столбце содержится точно одна единица.

С учетом сказанного задача коммивояжера принимает вид целочисленной задачи линейного программирования:


Дискретное программирование


Условия 6 и 7 с содержательной точки зрения означают, что в каждый пункт можно въехать и выехать только один раз. Приведенная форма записи задачи коммивояжера 4-8 не является самой рациональной и предназначена только для того, чтобы подчеркнуть ее общность с другими задачами дискретного программирования. Существует и другая форма, которая более ярко отражает комбинаторный характер данной проблемы:


Дискретное программирование


где D — множество перестановок чисел от 1 до n.

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


4. Задачи с разрывными целевыми функциями


Как уже упоминалось выше, многие экономические системы характеризуются наличием так называемых постоянных затрат, которые должны быть произведены независимо от объема производства. Учет в моделях этих и подобных факторов приводит к появлению в них целевых функций, не обладающих свойством непрерывности. В качестве примера может быть приведена транспортная задача с фиксированными доплатами. Она отличается от транспортной задачи в матричной постановке, рассмотренной в главе 3, тем, что в ней затраты по перевозке груза из i-го пункта производства в j-й пункт потребления определяются как


Дискретное программирование


где сi,j — по-прежнему издержки на перевозку единицы груза;

di,j — фиксированная доплата за аренду транспортных средств.

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


Дискретное программирование


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


Дискретное программирование

то целевая функция примет вид


Дискретное программирование


Действительно, если уi,j =0 , то переменные хi,j =0, а при уi,j =1 неравенства 12 становятся несущественными, поскольку они и так справедливы для любого опорного плана. Следовательно, задача 13 эквивалентна исходной задаче 10. В силу характера ограничений 11-12 задача 13 является задачей частично-целочисленного программирования.

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

В последующих параграфах мы остановимся на способах решения наиболее известных и хорошо изученных дискретных задач. Излагаемые ниже методы не имеют универсального характера, с каждым из них связаны определенные ограничения и, соответственно, ответ на вопрос о выборе того или иного из них зависит от конкретных особенностей решаемой задачи. Более того, цель изложения состоит в том, чтобы создать у читателя общие представления об основных идеях и подходах, не углубляясь далеко в вычислительные и математические тонкости, которыми буквально изобилуют алгоритмы дискретного программирования. Заметим также, что достаточно эффективный и широко применяемый подход к решению целочисленных задач основан на сведении их к задачам транспортного типа. Это объясняется тем, что если в условиях транспортной задачи значения запасов (аi) и потребностей (bj) являются целочисленными, то целочисленным будет и оптимальный план.


4.1 Основные идеи и принципы


Данный метод, который также носит название метода отсекающих плоскостей, предназначен для решения ЦЗЛП в канонической форме 2-3. Кратко представим его основные идеи.

Впервые был предложен Р.Гомори в 1957-1958 гг.

Отправной точкой для решения задачи 2-3 является решение ее непрерывного аналога, т. е. КЗЛП без учета условий целочисленности. Если получаемый в результате оптимальный план х* содержит только целые компоненты, то мы автоматически получаем и соответствующее решение ЦЗЛП. В противном случае к системе ограничений задачи должно быть добавлено такое ограничение, для которого:

Ш найденный нецелочисленный оптимальный план х* не удовлетворяет вновь добавляемому ограничению;

Ш любой допустимый целочисленный план непрерывной задачи 2-3 удовлетворяет вновь добавляемому ограничению.

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

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

Теперь необходимо несколько более подробно остановиться на принципах формирования отсекающих ограничений. Воспользуемся системой обозначений, применявшихся при изложении вычислительных методов линейного программирования. Пусть β(q) — оптимальный базис, полученный на последней итерации решения нецелочисленной ЗЛП. Если обозначить через αi,j и άi коэффициенты матрицы задачи и вектора ограничений в текущем базисе (A(β(q)) и b(β(q)))


Дискретное программирование


то i-ое уравнение в системе ограничений задачи примет вид:


Дискретное программирование


Так как план x(β(q)) является базисным, то в каждом уравнении все коэффициенты αi,j, соответствующие базисным столбцам (j∊N(β(q))), равны нулю за исключением некоторого αi,ji =1, на основе чего из (4.18) получаем:


Дискретное программирование


Если представить каждый коэффициент αi,j в виде суммы целой и дробной частей αi,j =[αi,j]+{αi,j}, то получим


Дискретное программирование


или


Дискретное программирование


Из 18 следует, что если все хj, j=1: n являются целыми, то целым будет и выражение


Дискретное программирование


стоящее в левой части 18, и, стало быть, правая часть данного уравнения:


Дискретное программирование


также должна быть целой. Предположим, что


Дискретное программирование


тогда, в силу того, что 0 ≤ {άi} < 1, а {αi,j} ≥ 0, xj ≥ 0, должно выполняться неравенство


Дискретное программирование


Однако неравенства 19 и 20 противоречат требуемой целочисленности правой части 18 xj(β(q)). Следовательно, для целочисленных решений должно выполняться условие, противоположное неравенству 19, или, что то же самое,


Дискретное программирование

В то же время 21 не выполняется для любого нецелочисленного базисного плана х. Действительно, небазисные компоненты плана равны нулю: хj =0 , j∊N(β(q)), и 21 приобретает вид {άi} ≤0 <=> {άi} =0, но это противоречит предположению о нецелочисленности плана х, т. к. в базисном плане хi = άi. Все сказанное позволяет утверждать, что ограничение 21 задает правильное отсечение.

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


Дискретное программирование


где xn+1 ≥0 — фиктивная переменная, добавляемая для преобразования неравенства в строгое равенство. Ей соответствует нулевой коэффициент в целевой функции.

Данному преобразованию условий задачи будет соответствовать преобразование симплекс-таблицы, показанное на рис.2. На нем по соображениям обеспечения наглядности использованы обозначения 14 и предполагается, что текущий базис β(q) состоит из первых m столбцов.


Дискретное программирование


Индекс i соответствует выбранной для формирования отсечения строке симплекс-таблицы, содержащей нецелочисленное значение bi(β(q)).

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


Дискретное программирование


совместно с добавленным столбцом


Дискретное программирование


образуют сопряженный (двойственно допустимый) базис для сформированной задачи, а (ά1, ..., άm, -{άi}) являются ненулевыми компонентами соответствующего псевдоплана. Исходя из этого, приходим к тому, что для решения вновь полученной задачи может быть эффективно применена процедура двойственного симплекс-метода.

Поскольку в начальном псевдоплане имеется только одна отрицательная компонента (-{άi}), то из базиса должен быть выведен соответствующий ей вектор аn+1 . Далее, следуя рекомендациям алгоритма двойственного симплекс-метода, находим оптимальный план. Если он не является целочисленным, то описанные действия итеративно повторяются.

Если в ходе решения дополнительная переменная хn+1 вновь становится базисной, ее значение оказывается безразличным для основных переменных. Поэтому строку и столбец, отвечающие ей, вычеркивают. С геометрической точки зрения это можно обосновать так: если псевдоплан оказывается внутри полупространства хn+1 ≥0, то дополнительное ограничение, определяемое гиперплоскостью хn+1=0, становится несущественным и опускается.


4.2 Описание алгоритма


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

1) Решение "текущей" задачи методами линейного программирования (малые итерации). На первой итерации в качестве "текущей" задачи выступает нецелочисленный аналог исходной ЦЗЛП.

2) Определение первой нецелочисленной компоненты в оптимальном плане, полученном на этапе 1. Если все компоненты являются целочисленными, то алгоритм завершается.

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

Двойственный симплекс-метод является основой для метода Гомори, так как он позволяет учитывать новые дополнительные ограничения (правильные отсечения) и переходить от текущего псевдоплана к новому оптимальному плану.

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

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


4.3 Пример решения ЦЗЛП методом Гомори


Рассмотрим особенности применения метода Гомори на конкретном примере. Пусть дана задача со следующими условиями:


Дискретное программирование


4.3.1 Итерация 1

Используя обычный симплекс-алгоритм, решаем непрерывный аналог исходной задачи, в котором игнорируются условия целочисленности 25. В качестве исходного базиса можно взять первый и второй столбцы. На его основе заполняется таблица T(1,1) (первый индекс в обозначении таблицы соответствует "большой" итерации, а второй — "малой").


Дискретное программирование


Как видно из строки оценок, данный базис является оптимальным, однако соответствующий ему план х ={11/5,17/5, 0) не является целочисленным, поэтому выбираем из таблицы T(1,1) строку, содержащую первый нецелый элемент, и согласно формуле 22 строим отсекающее ограничение:

Дискретное программирование


после чего переходим к следующей "большой" итерации.


4.3.1 Итерация 2

С учетом сформированного отсекающего ограничения заполняем симплекс-таблицу T(2,1).


Дискретное программирование


В соответствии с алгоритмом двойственного симплекс-метода переходим к следующему базису N(β(2,2))={1, 2, 3}.


Дискретное программирование


План, достигнутый в таблице T(2,2), является не только оптимальным (b(β(2,2))>0), но и полностью состоит из целочисленных компонент, т. е. решение задачи найдено: х* = (1, 2, 1) и f(x)=7.


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


5.1 Общая схема метода "ветвей и границ"


Другим широко применяемым для решения задач дискретного программирования методом является метод ветвей и границ. Впервые данный метод для решения ЦЗЛП предложили в 1960 г. Лэнг и Дойг, а его "второе рождение" произошло в 1963 г. в связи с выходом работы Литтла, Мурти, Суини и Кэрел, посвященной решению задачи о коммивояжере [33].

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

Пусть стоит задача: (*)


Дискретное программирование


где D — конечное множество.

Алгоритм является итеративным, и на каждой итерации происходит работа с некоторым подмножеством множества D. Назовем это подмножество текущим и будем обозначать его как D(q), где q — индекс итерации. Перед началом первой итерации в качестве текущего множества выбирается все множество D (D(1)=D), и для него некоторым способом вычисляется значение верхней оценки для целевой функции max f(x) ≤ ξ( D(1)). Стандартная итерация алгоритма состоит из следующих этапов:

1) если можно указать план x(q)<D(q), для которого f(x(q))≤ξ( D(q)), то x(q)=х* — решение задачи (*).

2) если такой план не найден, то область определения D(q) некоторым образом разбивается на подмножества D1(q), D2(q), ..., Dlq(q), удовлетворяющие условиям:


Дискретное программирование


Для каждого подмножества находятся оценки сверху (верхние границы) для целевой функции ξD1(q), ξD2(q), ..., ξDl1(q), уточняющие ранее полученную оценку ξD(q), то есть ξDi(q) ≤ ξD(q), i<1:lq. Возможно одно из двух:

2.1) если существует такой план х(q), что то этот план оптимальный.


Дискретное программирование

Дискретное программирование


2.2) если такой план не найден, то выбирается одно из множеств Di(q), i>1:lq (как правило, имеющее наибольшую оценку.


Дискретное программирование

Все имеющиеся к текущему моменту концевые подмножества, т. е. те подмножества, которые еще не подверглись процессу дробления, переобозначаются как D1(q+1), D2(q+1),..., Dl(q+1)(q+1), после чего процесс повторяется.

Схема дробления множества D представлена на рис.3 в виде графа. Существуют и более сложные системы индексации подмножеств, при которых не требуется их переобозначение на каждом шаге.

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


5.2 Решение ЦЗЛП методом ветвей и границ


Рассмотрим применение алгоритма метода ветвей и границ для решения ЦЗЛП (4.2)-(4.3). Как уже упоминалось, через D(q) обозначается подмножество множества допустимых планов задачи. Перед началом первой итерации (q = 1) в качестве текущего множества берется все множество D (D(1) = D), после чего решается стандартная задача линейного программирования (D(1), f). Нетрудно заметить, что она является непрерывным аналогом исходной задачи 2-3.


Дискретное программирование

Если найденный оптимальный план Дискретное программирование(1) содержит только целочисленные компоненты, то он является и оптимальным планом для 2-3: Дискретное программирование(1) = x*. В противном случае значение f(Дискретное программирование(1)) становится оценкой (верхней границей) значения целевой функции на множестве D(1), и мы переходим к выполнению стандартной итерации алгоритма. Опишем входящие в нее этапы.

1) Выбирается некоторая нецелочисленная компонента плана Дискретное программированиеk(q). Поскольку в оптимальном плане она должна быть целой, то можно наложить ограничения xk ≤ [Дискретное программированиеk(q)] и xk ≥ [Дискретное программированиеk(q)]+1. Таким образом, D(q) разбивается на подмножества


Дискретное программирование


Графическая интерпретация такого разбиения множества D(q) приведена на рис.4.

2) Решаются задачи линейного программирования


Дискретное программирование


Соответствующие максимальные значения целевой функции принимаются как ее оценки на этих множествах:


Дискретное программирование


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


Дискретное программирование


и содержит только целые компоненты, то, значит, найдено решение основной задачи 2-3. В противном случае среди всех концевых подмножеств, полученных как на предыдущих (Di(q)), так и на текущем (D1(q), D2(q)) этапе, выбирается область с наибольшей оценкой ξ(Di(q)). Она становится текущим рассматриваемым подмножеством (D(q+1)). Далее производится перенумерация концевых множеств и вычислительный процесс итеративно повторяется.

При решении задач (D1(q), f) и (D2(q), f) можно воспользоваться результатами решения предыдущей задачи (D(q), f). Рассмотрим вариант организации вычислительного процесса на примере задачи (Дискретное программирование1(q), f) (для (Дискретное программирование2(q), f) он выглядит аналогично с точностью до знаков неравенств).

Предположим, что на последнем шаге решения задачи (D(q), f) был получен оптимальный базис β. Без ограничения общности можно считать, что он состоит из первых m столбцов матрицы задачи. Данное предположение делается исключительно для обеспечения наглядности дальнейшего изложения и очевидно, что его выполнения можно всегда добиться за счет простой перенумерации векторов аj. По аналогии с предыдущим параграфом введем обозначения для элементов матрицы задачи (D(q), f) и ее вектора ограничений относительно базиса Дискретное программирование:


Дискретное программирование

Тогда система ограничений задачи (D(q), f) может быть представлена как


Дискретное программирование


а получаемая на ее основе система ограничений задачи (Дискретное программирование1(q), f) как


Дискретное программирование


Или


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

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: