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

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

 

 

 

 

 

Курсовая работа по Методам оптимизации  на тему

 

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

 

 

 

 

Выполнили студенты 3 курса

Группы МКЭ–09

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

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

 

Проверила

Третьякова  Н. Г.

 

 

 

 

 

Пермь  2012

Содержание

Содержание                                                                                                 1

Введение                                                                                                       2

Глава 1. Обзор и методы решений

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

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

                 дискретного программирования.                                     3

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

                  1.2. 1. Задачи с неделимостями.                                                6

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

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

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

Глава 2.Примеры решений

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

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

2.2.Пример решения  задачи методом ветвей и границ.                      30

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

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

 

Введение.

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

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

 

 

 

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

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

Дискретное  программирование - раздел оптимального программирования, изучающий экстремальные задачи, в которых на искомые переменные накладывается условие целочисленности, а область допустимых решений конечна. Таким образом, здесь используется модель общей задачи математического программирования с дополнительным ограничением: x₁, x₂, ..., x_n — целочисленны. Итак, под задачей дискретного программирования понимается задача математического программирования                 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<n , то задача называется частично целочисленной, если  n1=n-полностью целочисленной. Среди задач рассматриваемого класса выделяются задачи с  булевыми переменными

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

 

 

 

 

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

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

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

1) Для каждой точки x Є G можно определить некоторым образом понятие

непустой окрестности Gx с G , состоящей из точек, принадлежащих  G.

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

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

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

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

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(x₁,x₂,...,x_n)=

 

g(x₁,x₂,...,x_n) =

 

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

                         

                                →max,                  (1)

 

                                    ≤R,                            (2)

                             

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

 

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

0<xj<1, j = l,2,...,n. (3')

 

 

 

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

        f(x₁,x₂,...,x_n) = →max,     (4)

 

gi(x₁,x₂,...,x_n) =

≤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. Множество допустимых решений этой задачи — это множество булевых векторов х =  (x₁,x₂,...,x_n), удовлетворяющих условиям (5). Вместе с задачей (4)-(6) будем рассматривать задачу линейного программирования, в которой вместо условий (6) вводятся условия

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

Экономическая интерпретация задачи о ранцах. Пусть имеется п проектов, и для их реализации задан вектор ресурсов B^T = (b₁,b₂,...,b_m), bi > 0. Обозначим через aij > 0 количество единиц ресурса типа i, необходимое для реализации проекта с номером j, при этом для любого ресурса Bs

 

выполнено условие    > b_s, т.е. реализация всех проектов невозможна. Пусть Cj > 0, j = 1, 2,..., п — прибыль, полученная при реализации проекта j. Требуется выбрать для реализации набор проектов с максимальной суммарной прибылью. Введем п булевых переменных:

j = 1,2,..., n.

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

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

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

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

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

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

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

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

 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-й научной темой.

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

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