Ирина Эланс

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

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

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

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

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

Выполнили студенты 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 – количество работ.

ai = 1 – единичное количество ресурса Ai (i =1,n), например: один работник; одно транспортное средство; одна научная тема и т.д.
bj = 1 – единичное количество работы Bj (j =1,m), например: одна должность; один маршрут; одна лаборатория.
cij – характеристика качества выполнения работы Bj с помощью ресурса Аi. Например, компетентность i-го работника при работе на j-й должности; время, за которое i-е транспортное средство перевезет груз по j-му маршруту; степень квалификации i-й лаборатории при работе над j-й научной темой.

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

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

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

Таблица 1 Общий вид транспортной матрицы задачи о назначениях
Ресурсы, Ai	Работы, B1				Количество ресурсов
Ресурсы, Ai	B1	B2	…	Bm	Количество ресурсов
A1	c11	c12	…	c1m	1
A2	c21	c22	…	c2m	1
…	…	…	…	…	…
An	cn1	cn2	…	cnm	1
Количество работ	1	1	…	1

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

(9)

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

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

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

Обозначим вершины графа i, i =1, 2, …, m, а ребра — j, j =1, 2, …, n... Граф характеризуется своей матрицей инциденций вершин и ребер , где

Введем множество переменных {x_j}, таких, что

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

минимизировать (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—издержки на перевозку единицы груза;

d_i,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-ой большой итерацией.

Доказывается, что при выполнении определенных условий решение

исходной задачи будет получено через конечное число итераций. Если

задачи ЛП не имеют решения, не имеет решения и исходная задача.

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

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

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

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

, z ≥ 0,

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

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

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

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

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

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

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

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

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

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

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

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

, β _i– нецелое.

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

Выразим базисную переменную x_i в виде суммы целой и дробной частей.
Выражение в левых круглых скобках целое число, и чтобы x_jбыло целым, необходимо, чтобы выражение в правых круглых скобках тоже было целым. Когда выражение Li= будет целым? Так как 0≤{β_i}≤1, а ≥0, то L_i будет целым числом, если  .
- правильное отсечение Гомори.
Задача не будет иметь полностью целочисленного решения, если встретится в симплекс-таблице уравнение такое, что β_iдробное число, а d_ij–целые.

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,

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

Обзор задач дискретного программирования 📙 Курсовая → 🆔 144404