Обзор задач дискретного программирования

Пермский Национальный Исследовательский Политехнический Университет

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

по Методам оптимизации на тему

«Обзор задач дискретного программирования»

Выполнили студенты 3 курса Группы МКЭ-09

Деревянкин И.Л.,

Деревянкина А. Л.

Проверила: Третьякова Н. Г.

Пермь 2012

Содержание Введение Глава 1. Обзор и методы решений задач дискретного программирования

1.1 Предмет, постановка и особенности задач дискретного программирования

1.2 Модели дискретного программирования

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

1.2.2 Экстремальные комбинаторные задачи

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

1.3 Методы решения задач дискретного программирования Глава 2. Примеры решений задач дискретного программирования

2.1 Пример решения задачи методом Гомори

2.2 Пример решения задачи методом ветвей и границ Заключение Список литературы

Введение

Дискретное программирование сформировалось как самостоятельная и важная часть математического программирования в конце 60-х годов. В терминах дискретного программирования формулируются многие важные задачи экономики, управления, планирования, военного дела, биологии и т. п. Кроме того, к задачам дискретного программирования удается свести ряд экстремальных комбинаторных задач. По мнению автора, дискретное программирование является интересным и перспективным разделом математического программирования. Именно поэтому объектом настоящего исследования являются задачи дискретного программирования. Встают закономерные вопросы, в чем особенность данных задач, в чем прикладное значение их и какие существуют методы решения в дискретном программировании. Чтобы ответить на поставленные вопросы, в данной работе решены следующие задачи: во-первых, предлагаются формулировка, особенности дискретных задач. Во-вторых, приводится их классификация. Втретьих, рассматриваются методы решения дискретных задач.

Настоящая работа опирается прежде всего на работы авторитетных ученых, работающих в данной область (Сигал И. Х., Иванова А. П., Дроздов Н. Д., Корбут А. А., Фанкельштейн Ю. Ю.). В процессе работы привлекались данные сайтов в сети Интернет. Данная работа состоит из введения, 2 глав, заключения и списка литературы. В 1 главе приводятся теоритические данные, а именно, особенности задач дискретного программирования, классификация и методы решения. 2 глава — практическая, в ней приведены примеры задач и их решение.

Глава 1. Обзор и методы решений задач дискретного программирования

1.1 Предмет, постановка и особенности задач дискретного программирования дискретное программирование задача Дискретное программирование — раздел оптимального программирования, изучающий экстремальные задачи, в которых на искомые переменные накладывается условие целочисленности, а область допустимых решений конечна. Таким образом, здесь используется модель общей задачи математического программирования с дополнительным ограничением: x1, x2, …, xn — целочисленны. Итак, под задачей дискретного программирования понимается задача математического программирования F (x°)= min F (x), x Є G, множество допустимых решений которой конечно, т. е. 0?¦G¦=N< ?, где ¦G¦-число элементов множества G. Рассмотрим задачу линейного программирования.

> min,

x j ?0, j=1,…, n

x j целые, j=1,…, n1? n.

Если n1

x jЄ{0,1}, j=1,…, n1? n.

Рассмотрим особенности задач дискретного программирования.

1.Нерегулярность.

Сначала введем понятие регулярности задачи. Регулярные задачи — это задачи, в которых выполняются следующие условия.

1) Для каждой точки x Є G можно определить некоторым образом понятие непустой окрестности Gx с G, состоящей из точек, принадлежащих G.

2) Можно указать достаточно легко проверяемые необходимые и достаточные условия локальной оптимальности. На основе этих условий локальный оптимум целевой функции F (x)на множестве G может быть найден при помощи некоторого конечного (или бесконечного сходящегося) процесса.

3) Локальный оптимум целевой функции совпадает с глобальным. К задачам, не являющимся регулярными, относятся, в частности, так называемые многоэкстремальные задачи, т. е. задачи, в которых глобальный экстремум может не совпадать с локальным. К классу нерегулярных задач относятся дискретные задачи, в которых множество G не является связным и выпуклым (например, множество G может быть конечным или счетным, либо декартовым произведением конечных или счетных множеств).

2.Трудности при определении окрестности:

В задачах регулярного математического программирования значительная часть методов основана на следующем исходном положении: если точки х1 Є G и х2 Є G близки, то значения f (x1) и f (x2) также близки. В задачах дискретной оптимизации это положение не имеет места. Если в этом классе задач удается ввести естественным образом понятие окрестности, то близкие точки из этой окрестности могут сколь угодно значительно отличаться по значениям функции. В некоторых задачах дискретной оптимизации не удается естественным образом ввести понятие окрестности, оно вводится с помощью искусственных построений. Поэтому в задачах дискретной оптимизации близость двух точек х1 Є G и х2 Є G может быть оценена лишь по значениям f{x1) и f (x2).

3.Трудности нахождения допустимого целочисленного плана в задаче. Предположим, что рассматривается задача частично целочисленного линейного программирования общего вида. Вопрос о существовании допустимого решения сводится к выяснению, разрешима ли система линейных равенств и неравенств в целых неотрицательных числах. Известно, что это трудоемкая вычислительная задача из класса NP. Поэтому в общей задаче рассматриваемого класса поиск допустимого решения может оказаться столь же трудоемким, как и поиск оптимального решения. Невыпуклость и несвязность области допустимых решений делают невозможным применение к дискретным задачам обычных приемов «регулярного» математического программирования (продвижение из одной вершины многогранника в другую и т. п.). Идеяперебора для задач с конечным множеством допустимых решений также оказывается. практически неприменимой, так как количество точек (x i, .. ., x"), при ni = n, равно ?¦ G ¦?2? (¦G¦-число элементов множества G) и с увеличением количества переменных объем вычислительной работы растет весьма быстро. Отсюда вытекает еще одна особенность задач дискретного программирования, а именно:

4.Невозможность большого перебора на ЭВМ.

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

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

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

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

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

Рассмотрим некоторые из них.

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

Математические модели задач этого типа основаны на требовании целочисленности переменных, вытекающем из физических условий практических задач. В этих задачах переменные х1, …, хп обозначают количества физически неделимых ресурсов или видов продукции (станков, самолетов, деталей и т. п.). К таким задачам относится, в частности, задача об определении оптимальной структуры производственной программы, где - объемы выпуска соответствующей продукции. Математическая модель этой задачи имеет следующий вид:

Максимизировать при условиях

 — целое, при .

Если J=n, то задача называется полностью целочисленной, в противном случае — частично целочисленной.

Одной из наиболее распространенных задач этого класса является задача о ранце.

Задача об одномерном ранце.

Пусть имеется п предметов, каждый из которых имеет ценность Cj > 0 и вес aj > О, j = 1,2,…, n. Имеется ранец (рюкзак), грузоподъемность которого есть R, при этом? aj >R, т. е. все предметы в ранец положить невозможно. Необходимо положить в ранец набор предметов с максимальной суммарной ценностью. Введем п переменных:

j = 1,2,…, n.

После введения этих переменных суммарная ценность и грузоподъемность соответственно имеют вид

f (x1,x2,…, xn)=

g (x1,x2,…, xn) =

Поэтому задача об одномерном ранце имеет вид

>max, (1)

?R, (2)

x jЄ{0,1}, j=1,…, n. (3)

Естественно предположить, что cj > 0, 0 < aj < R, j = 1,2,…, n. Множество допустимых решений этой задачи — это множество n-мерных булевых векторов х = {х1, х2,…, хп), удовлетворяющих условию (2). Вместе с задачей (1)-(3) будем рассматривать задачу линейного программирования, в которой вместо условий (3) вводятся условия

Задача о многомерном ранце. Эта задача имеет вид

f (x1,x2,…, xn) = >max, (4)

gi (x1,x2,…, xn) = ?bi j, i = 1,2,…, m, (5)

3 = 1

x jЄ{0,1}, j=1,…, n. (6)

Предполагаем, что cj > 0, 0 < aij? bi, i = 1, 2,…, m, j = 1, 2,…, п. В этой задаче каждый предмет имеет т свойств (кроме ценности). Эти свойства описываются количественно с помощью элементов столбца с номером j матрицы, А = (aij)mxn. Множество допустимых решений этой задачи — это множество булевых векторов х = (x1,x2,…, xn), удовлетворяющих условиям (5). Вместе с задачей (4)-(6) будем рассматривать задачу линейного программирования, в которой вместо условий (6) вводятся условия

0<1, j = l, 2,…, n. (6/)

Экономическая интерпретация задачи о ранцах. Пусть имеется п проектов, и для их реализации задан вектор ресурсов BT = (b1,b2,…, bm), bi > 0. Обозначим через aij > 0 количество единиц ресурса типа i, необходимое для реализации проекта с номером j, при этом для любого ресурса Bs выполнено условие > bs, т. е. реализация всех проектов невозможна. Пусть Cj > 0, j = 1, 2,…, п — прибыль, полученная при реализации проекта j. Требуется выбрать для реализации набор проектов с максимальной суммарной прибылью. Введем п булевых переменных:

j = 1,2,…, n.

Получим задачу о многомерном ранце (4)-(6).

1.2.2 Экстремальные комбинаторные задачи

В данных задачах необходимо найти экстремум некоторой целевой функции, заданной на конечном множестве, элементами которого служат перестановки из n символов. Найти такую перестановку из чисел 1, 2, …, n, при которой достигается минимум по всем перестановкам .

Каждая такая перестановка может быть представлена точкой в n2-мерном пространстве или в виде матрицы .

Одной из наиболее простых задач этого класса является известная задача о назначениях.

Задача о назначениях.

Задача о назначениях — это распределительная задача, в которой для выполнения каждой работы требуется один и только один ресурс (один человек, одна автомашина и т. д.), а каждый ресурс может быть использован на одной и только одной работе. То есть ресурсы не делимы между работами, а работы не делимы между ресурсами. Таким образом, задача о назначениях является частным случаем транспортной задачи.

Исходные параметры модели задачи о назначениях

1. n — количество ресурсов, m — количество работ.

2. ai = 1 — единичное количество ресурса Ai (i =1,n), например: один работник; одно транспортное средство; одна научная тема и т. д.

3. bj = 1 — единичное количество работы Bj (j =1,m), например: одна должность; один маршрут; одна лаборатория.

4. cij — характеристика качества выполнения работы Bj с помощью ресурса Аi. Например, компетентность i-го работника при работе на j-й должности; время, за которое i-е транспортное средство перевезет груз по j-му маршруту; степень квалификации i-й лаборатории при работе над j-й научной темой.

Искомые параметры

1. xij — факт назначения или не назначения ресурса Аi на работу Bj:

2. L (X) — общая (суммарная) характеристика качества распределения ресурсов по работам.

Таблица 1 Общий вид транспортной матрицы задачи о назначениях

Модель задачи о назначениях

В некоторых случаях, например, когда cij — это компетентность, опыт работы, или квалификация работников, условие задачи может требовать максимизации ЦФ. В этом случае ЦФ L (X) заменяют на L1(X) = - L (X) и решают задачу с ЦФ L1(X) > min, что равносильно решению задачи с ЦФ L (X) > max.

Задача о покрытии.

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

Обозначим вершины графа i, i =1, 2, …, m, а ребра — j, j =1, 2, …, n… Граф характеризуется своей матрицей инциденций вершин и ребер, где Введем множество переменных {xj}, таких, что Тогда нахождение минимального покрытия эквивалентно следующей задаче:

минимизировать (10)

при ограничениях

(11)

Задача о коммивояжере Имеется N городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения:

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

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

Математическая модель задачи

N — число городов.

Ci j, i, j=1.N — матрица затрат, где Ci j — затраты на переход из iго города в j-й.

Xi j — матрица переходов с компонентами:

Xi j = 1, если коммивояжер совершает переход из i-го города в j-й,

Xi j = 0, если не совершает перехода, где i, j = 1. N и i j.

Критерий:

(12)

Ограничения:

i = 1. N (13)

j = 1. N (14)

Ui — Uj + N Ч Xij? N-1, i, j = 1. N, i j. (15)

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

(16)

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

di, j — фиксированная доплата за аренду транспортных средств. ai — объем производства в пункте производства i; bj — объем потребления в пункте потребления j. Обозначим через xij объемы перевозок из пункта i в пункт j.

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

(17)

содержит «скачкообразные» разрывы, что существенно затрудняет ее минимизацию, поэтому стандартный метод решения основан на следующем преобразовании. Если ввести вспомогательные переменные уi, j, такие, что М ij = min (ai, bj), i = 1,2,…, m; j = 1,2,…n.

yij = sign (xij) т. е. (18)

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

(19)

при дополнительном условии i = 1,2,…, m; j = 1,2,…n.

Действительно, если уi, j =0, то переменные хi, j =0, а при уi, j =1 неравенства (18) становятся несущественными, поскольку они и так справедливы для любого опорного плана. Следовательно, задача (19) эквивалентна исходной задаче (17). Задача (19) является задачей частично-целочисленного программирования.

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

1.3 Методы решения задач дискретного программирования.

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

· Метод отсечения;

· комбинаторные методы;

· приближенные методы.

Рассмотрим каждый класс в отдельности.

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

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

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

После решения каждой k-ой задачи ЛП (k = 0,1,2,.. .) проверятся удовлетворяет ли полученное оптимальное решение условиям исходной задачи. При положительном ответе итерационный процесс решения задач из последовательности прекращается — полученное оптимальное решение задачи ЛП является и решением исходной задачи.

Решение каждой k-ой задачи ЛП называется k-ой большой итерацией.

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

Основным понятием метода является термин правильное отсечение:

Правильные отсечения — отсечение (дополнительное ограничение), которое удовлетворяют следующим требованиям:

1. линейно;

2. отсекает от области допустимых решений ту ее часть, которая содержит оптимальное решение задачи ЛП, не удовлетворяющее требованиям исходной задачи;

3. в отсекаемой области не должно содержаться ни одной точки, принадлежащей области допустимых решений исходной задачи. (является «правильным»).

Общая формула построения правильного отсечения для всех алгоритмов запишется в следующем виде:

z? 0,

где xj — небазисные переменные оптимального решения k-ой задачи ЛП, г0, гj — определяются по коэффициентам разложения базисной переменной, не удовлетворяющей требованиям целочисленности (дискретности) исходной задачи по небазисным переменным в последней симплекс-таблице k-ой задачи ЛП (строка симплекс-таблицы с найденным оптимальным значением задачи ЛП).

Известны три алгоритма отсечения:

1). 1-ый алгоритм Гомори решения целочисленной задачи ЛП.

2). 2-ой алгоритм Гомори решения частично целочисленной задачи ЛП.

3). Алгоритм Дальтона-Ллевилина решения дискретной задачи ЛП.

Скажем пару слов о каждом приведённом алгоритме.

1-ый алгоритм Гомори решения целочисленной задачи ЛП.

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

Алгоритм метода Гомори № 1

1.Решим исходную задачу (без условия целочисленности) Симплекс-методом. Если все базисные компоненты оптимального плана решаемой задачи целые, то найденное решение есть оптимальное решение исходной задачи. Если некоторая компонента ;

нецелая, то переходим к п. 2.

2.Строим правильное отсечение. Гомори предложено делать каждый раз дополнительное ограничение для нецелой переменной с наибольшей дробной частью. Итак, задача с отброшенным условием целочисленности решена. Рассмотрим i-ю строку оптимальной симплексной таблицы, которой соответствует нецелое решение в i базисной переменной xi. Пусть R — множество индексов j, которые соответствуют небазисным переменным. Тогда переменная xi может быть выражена через небазисные переменные xj:

в i — нецелое.

Обозначим наибольшую целую часть числа a, его не превосходящую, через [a], (a?[a]), а дробную положительную часть — через {a} Очевидно a = [a] + {a}. Например, если a=4,7 то [a] = 4, {a} = 0,7.

Выразим базисную переменную xi в виде суммы целой и дробной частей.

Выражение в левых круглых скобках целое число, и чтобы xj было целым, необходимо, чтобы выражение в правых круглых скобках тоже было целым. Когда выражение Li= будет целым? Так как 0?{вi}?1, а ?0, то Li будет целым числом, если.

— правильное отсечение Гомори.

Задача не будет иметь полностью целочисленного решения, если встретится в симплекс-таблице уравнение такое, что вi дробное число, а dij -целые.

3.Добавляем полученное дополнительное условие к задаче из п. 1.Так как оптимальное решение задачи, решенной в п. 1, определяло одну из вершин многогранника условий, то оно может быть выбрано в качестве первоначального опорного решения для вновь полученной задачи. Решаем полученную задачу С-методом.

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

1) cjцелые коэффициенты целевой функции F, строка целевой функции в симплексной таблице учитывается при выборе строки для построения правильного отсечения;

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

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

Пример применение первого алгоритма Гомори будет рассмотрено в главе 2.

Алгоритм Дальтона-Ллевилина решения дискретной задачи ЛП.

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

xj ?0, j =1, 2, …, n,

x Є Aj (A j1, Aj2 ,…, Ajmj), j =1,2,…, n1, n1? n .

Полагаем, что коэффициенты Aj проранжированы, т. е. Аj1 < Аj2 < …< Аjmj.

Если x не удовлетворяет требованиям исходной задачи и

Aiv < xi0< Aiv+1 тогда, используя i-ю строку симплекс-таблицы, запишем правильное ограничение в виде

zi= - г 0 +? г j xj, z? 0,

г 0= xi0 — Aiv ,

г ij= xij, если xij? 0,

г ij= (-xij)*(xi0 — Aiv)/(Aiv+1 -xi0), если xij? 0,

Стоит отметить, что

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

2.) Известно, что с увеличением размерности задачи эффективность методов отсечения значительно снижается. Решение может быть не получено, в частности, из-за недостаточной точности вычисления коэффициентов.

1.3.2 Комбинаторные методы Основная идея методов этого класса заключается в использовании конечности множества допустимых решений и замене полного их перебора сокращенным (направленным перебором). Если каким-либо образом удается показать, что подмножество G' С G не может содержать оптимальных решений, то в дальнейшем задача решается на множестве хGG'. Таким образом, главную роль в сокращении перебора играют оценка и отбрасывание подмножеств, заведомо не содержащих оптимальных решений. Эта идея реализуется путем последовательного разбиения множества всех допустимых решений на подмножества. При этом среди подмножеств, последовательно порождаемых на каждом шаге процесса, могут обнаружиться как подмножества, не содержащие допустимых решений, так и подмножества, не содержащие оптимальных решений. Отбрасывание таких подмножеств позволяет заменить полный перебор частичным и тем самым делает реализуемым вычислительный процесс.

Таким образом, комбинаторные методы основаны на двух элементах:

— последовательное разбиение на подмножества;

— оценивание получаемых подмножеств.

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

Среди комбинаторных методов выделяют:

— метод последовательного анализа вариантов;

— метод ветвей и границ;

— методы, основанные на последовательностных схемах;

— метод динамического программирования;

— аппроксимационно-комбинаторный метод;

—метод последовательных расчетов.

Остановимся подробнее на самом распространённом из них, на методе ветвей и границ.

МЕТОД ВЕТВЕЙ И ГРАНИЦ Суть метода заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспективными, и отбрасывании бесперспективных вариантов.

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

Алгоритм действия метода ветвей и границ Первоначально находим, к примеру, симплекс-методом оптимальный план задачи без учета целочисленности переменных. Пусть им является план X0. Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи и Fmax = F (X0).

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

Предполагая, что найденный оптимальный план X0 не удовлетворяет условию целочисленности переменных, тем самым считаем, что среди его компонент есть дробные числа. Пусть, например, переменная приняла xi в плане X0 дробное значение. Тогда в оптимальном целочисленном плане ее значение будет по крайней мере либо меньше или равно ближайшему меньшему целому числу Ci0, либо больше или равно ближайшему большему целому числу Ci0 +1. Определяя эти числа, находим симплекс-методом решение двух задач линейного программирования:

(20)

(21)

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

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

2. Одна из задач неразрешима, а другая имеет оптимальный план, среди компонент которого есть дробные числа. Тогда рассматриваем вторую задачу и в ее оптимальном плане выбираем одну из компонент, значение которой равно дробному числу, и строим две задачи, аналогичные задачам (20) и (21).

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

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

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

4. Обе задачи разрешимы, и среди оптимальных планов обеих задач есть дробные числа. Тогда вычисляем значение целевой функции на данных оптимальных планах и рассматриваем ту из задач, для которой значение целевой функции является наибольшим. В оптимальном плане этой задачи выбираем одну из компонент, значение которой является дробным числом, и строим две задачи, аналогичные (20) и (21).

Таким образом, описанный выше итерационный процесс может быть представлен в виде некоторого дерева, на котором исходная вершина отвечает оптимальному плану Х0 исходной задачи, а каждая соединенная с ней ветвью вершина отвечает оптимальным планам задач (20) и (21). Каждая из этих вершин имеет свои ветвления. При этом на каждом шаге выбирается та вершина, для которой значение функции является наибольшим. Если на некотором шаге будет получен план, имеющий целочисленные компоненты, и значение функции на нем окажется больше или равно, чем значение функции в других возможных для ветвления вершинах, то данный план является оптимальным планом исходной задачи целочисленного программирования и значение целевой функции на нем является максимальным.

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

1. Находят решение задачи линейного программирования .

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

3. Находят решение задач (20) и (21), которые получаются из задачи в результате присоединения дополнительных ограничений.

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

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

Пример решения задачи данным методом разберем в главе 2.

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

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

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

Можно отметить два подхода к повышению вычислительной эффективности комбинаторных алгоритмов:

— локальный, под которым понимаются любые приемы расширения возможности решения конкретной задачи;

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

Возможные классификации приближенных методов Классификация А.

1) Методы, базирующиеся на точные.

2) Специфические (эвристические) методы.

Классификация Б.

1) Детерминированные методы (например, линейная аппроксимация, локальная оптимизация).

2) Методы случайного поиска (неуправляемый поиск, управляемый поиск).

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

4) Статистические эффективные методы.

5)? — оптимальные методы.

Глава 2. Примеры решений задач дискретного программирования

2.1 Пример решения задачи методом Гомори.

.

Решим задачу без учета целочисленности.

Определим минимальное значение целевой функции F (X) = - 5×1 — 4×2 при следующих условиях.

3x1 + 2×2?5

x2?2

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

3x1 + 2×2 + 1×3 + 0×4 = 5

0x1 + 1×2 + 0×3 + 1×4 = 2

Решим систему уравнений относительно базисных переменных:

x3, x4,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,5,2)

Переходим к основному алгоритму симплекс-метода.

Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.

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

Вычислим значения bi / ai1

и из них выберем наименьшее:

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.

Получаем новую симплекс-таблицу:

Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.

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

Вычислим значения bi / ai2

и из них выберем наименьшее:

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.

Получаем новую симплекс-таблицу:

Конец: индексная строка не содержит положительных элементов — найден оптимальный план Оптимальный план можно записать так:

x1 = 1/3

x2 = 2

F (X) = -5*1/3 + -4*2 = -92/3

Метод Гомори.

В полученном оптимальном плане присутствуют дробные числа.

Для переменной x, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 2/3, составляем дополнительное ограничение:

q3 — q31*x1 — q32*x2 — q33*x3 — q34*x4?0

Дополнительное ограничение имеет вид:

— 2/3−1/3×3−1/3×4?0

Преобразуем полученное неравенство в уравнение:

— 2/3−1/3×3−1/3×4 + x5 = 0

коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.

В полученном оптимальном плане присутствуют дробные числа.

Для переменной x5, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 2/3, составляем дополнительное ограничение:

q3 — q31*x1 — q32*x2 — q33*x3 — q34*x4 — q35*x5?0

Дополнительное ограничение имеет вид:

2/3−2/3×3−2/3×4?0

Преобразуем полученное неравенство в уравнение:

2/3−2/3×3−2/3×4 + x6 = 0

коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.

План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-2/3).

Выполняем преобразования симплексной таблицы.

Решение получилось целочисленным. Оптимальный целочисленный план можно записать так:

x1 = 1

x2 = 1

x5 = 1

x4 = 1

F (X) = -9

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

F (X)=2×1+х2 > max.

при условиях/

xj — целые (j=1,2,3,4,5)

Решение.

Находим решение сформулированной задачи симплексным методом без учета условия целочисленности переменных. В результате устанавливаем, что такая задача имеет оптимальный план Х0= (18/5, 3/5, 0, 0, 24/5). При этом плане F= (X0)=39/5.

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

Возьмем какую-нибудь переменную, значение которой является дробным числом, например х1. Тогда эта переменная в оптимальном плане исходной задачи будет принимать значение, либо меньшее или равное трём: Х1?3, либо больше или равно четырём: Х1?4, .

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

(I) (II)

Задача (I) имеет оптимальный план на котором значение целевой функции. Задача (II) неразрешима.

Исследуем задачу (I). Так как среди компонент оптимального плана этой задачи есть дробные числа, то для одной из переменных, например x2, вводим дополнительные ограничения:

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

(III)

(IV)

Задача (IV) неразрешима, а задача (III) имеет оптимальный план Х2 (3,1,3,3, 3), на котором значение целевой функции задачи

Таким образом исходная задача целочисленного программирования имеет оптимальный план Х*= (3, 1, 2, 3, 3). При этом плане целевая функция принимает максимальное значение .

Схему реализованного выше вычислительного процесса можно представить в виде дерева, ветвями которого являются соответствующие ограничения на переменные, а вершинами — решения соответствующих задач линейного программирования. Как видно задача (I) имеет оптимальный план (3, 3/2, 0, 9/2, 3/2), а задача (II) неразрешима. Поскольку среди компонент плана есть дробные числа, выберем переменную х2 и рассмотрим задачи (III) (IV). Задача (III) имеет оптимальный план (3, 1, 2, 3, 3) а задача (IV) неразрешима.

Итак, Х*= (3, 1, 2, 3, 3) является оптимальным планом задачи. При этом плане .

Заключение

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

Задачи этого класса обладают следующими особенностями:

1.Нерегулярность,

2.Трудности при определении окрестности,

3.Трудности нахождения допустимого целочисленного плана в задаче,

4.Невозможность большого перебора на ЭВМ.

Также была приведена классификация задач:

1. Задачи с неделимостями, к которым относятся задача о ранце

2. Экстремальные комбинаторные задачи (Задача о назначениях, задача коммивояжёра, Задача о покрытии)

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

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

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

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

1. Сигал И. Х., Иванова А. П. Введение в прикладное дискретное программирование. М.: ФИЗМАТЛИТ, 2007.

2. Корбут А. А., Финкельштейн Ю. Ю. Дискретное программирование. М.: Наука, 1969.

3. Дроздов Н. Д. Алгоритмы дискретного программирования. Тверь 2000

4. Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986.

5. Учебно-методические материалы для лабораторных и самостоятельных работ по курсу «Численные методы решения прикладных задач. Дискретное программирование. Комбинаторные методы» / Сост. Н. Д. Дроздов. — Калинин, 1990.