Решение оптимизационных задач дискретного программирования

Федеральное Государственное образовательное  учреждение высшего профессионального  образования

Пермская  государственная сельскохозяйственная академия имени академика Д.Н.Прянишникова 
 
 
 
 

Кафедра Информационных технологий и автоматизированного  проектирования

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

по дисциплине: «Методы оптимизации»

на тему:

«Решение оптимизационных задач дискретного программирования». 
 
 
 
 
 
 
 
 

Выполнил:, Пинаев И. В.

студент  ПИ – 31 Б 

Проверил:

старший преподаватель Гревцев А.М. 
 
 
 
 
 
 
 

Пермь-2010

Содержание:

Введение……………………………………………………………………………..3

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

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

1.2.Особенности  задач………………..……………………………………………..9

2.Основные сведения о методах решения задач…………………..……………..11

2.1. Графический  метод решения задач…………………………………………….

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

3.1.Задачи  о назначении……………………………………………………………

3.1.Задачи  транспортного типа………………………………………..…..…..…...14

3.2.Задачи о ранце…………………………………………………....…...…....…...19

3.3. Общие  свойства задач о ранце…………………………………..…..…....…..21

3.4. Алгоритм  Данцига для линейной одномерной  задачи о ранце……..…..….22

Заключение…………………………………………………………………………25

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

     Введение

      Дискретное  программирование сформировалось как  самостоятельная и важная часть  математического программирования в конце 60-х годов.

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

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

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

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

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

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

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

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

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

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

1.1. Постановка задачи.

     Под задачей дискретного программирования (дискретной оптимизации) понимается задача математического программирования 

                                                                                              (1.1)

множество допустимых решений, которой конечно, т.е. 0 , где — число элементов множества G. В силу конечности G все допустимые решения можно пронумеровать:

вычислить и найти наименьшее значение. Однако такой метод полного перебора при решении задачи реализовать невозможно, так как N может оказаться настолько большим, что этот перебор невыполним на ЭВМ любой мощности.

     Во  многих задачах условия дискретности отделены от других условий, т.е. если

, то  . Поэтому ,

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

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

Задача  формулируется следующим образом:

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

     Последнее название связано с именем английского  математика Д. Буля (1815-1864г.г), одного из основоположников математической логики.

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

       Рассмотрим задачу

     Построим  область G. Пусть  — иррациональное число, например . Тогда на прямой нет ни одной точки с обеими целочисленными координатами, кроме точки (0, 0). Рассмотрим прямую при . Возьмем , тогда . В полученном прямоугольнике с вершинами выделим все точки с целочисленными координатами и проведем из точки два отрезка так, чтобы в полученном четырехугольнике ОABC не было ни одной целочисленной точки, кроме точки (0,0) (рис. 1). 

рис.1 

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

     Решение целочисленной задачи — точка (0,0), . Поэтому разность между значениями линейных функций целочисленной и линейной задачи для оптимальных решений этих задач может быть сколь угодно большой. Пусть теперь область G имеет вид треугольника ABC (рис.2). 

рис.2 

     В этом случае линейная задача имеет  то же решение, что и ранее, а целочисленная задача неразрешима.

     Рассмотрение  этого простого примера позволяет  сделать два важных вывода:

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

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

     Рассмотрим  примеры  задач дискретной оптимизации: задачу о ранце, задачу о коммивояжере.

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

     Имеется предметов, каждый из которых характеризуется стоимостью и весом Имеется ранец, грузоподъемность которого равна . Требуется положить в ранец набор предметов с максимальной суммарной стоимостью. При этом предполагается, что Для описания задачи на языке целочисленного линейного программирования введем булевы переменные :

       Тогда целевая функция имеет  вид 

     Ограничение на грузоподъемность —

     Получена  следующая задача целочисленного (булевого) линейного программирования:

     Множество G в этой задаче — это множество n-мерных булевых векторов с компонентами 0, 1, удовлетворяющих условию 

     Очевидно, что  . Оценим эту величину:

     Если  ЭВМ имеет быстродействие операций в секунду, то легко оценить время, необходимое для выполнения полного перебора. 

     Задача  о коммивояжере.

     Пусть — конечное множество точек, — «расстояние» от точки i до точки j, — матрица «расстояний». Маршрут z  коммивояжера — это любая перестановка точек из P, . Длина l(z) маршрута z  есть сумма соответствующих элементов матрицы :

     Пусть Z — множество всех маршрутов. Необходимо найти маршрут такой, что

     В этой задаче G = Z, . Оценим величину , пользуясь первым членом асимптотического представления Стирлинга для факториала

     Пусть  Тогда

отсюда  видно, что трудоемкость вычислений резко растет с ростом размерности  задачи. 
 
 

1.2. Особенности задач

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

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

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

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

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

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

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

2. Основные сведения о методах решения задач 

     Выделим следующие (основные) методы решения  задач:

     — метод отсечения для задач (частично) целочисленного линейного программирования;

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

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

     Методы  отсечения.

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

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

     Основная  идея методов отсечения, элементы алгоритма.

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

     — полученный нецелочисленный план ему не удовлетворяет;

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

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

     — нахождение универсального правила формирования отсечений;

     — доказательство конечности процесса отсечения;

     — борьба с чрезмерным «разрастанием» размерности задач при добавлении ограничений.

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

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

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

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

     — методы отсечения приспособлены в основном для решения чисто целочисленных задач;

     — методы отсечения не приспособлены для решения задач со слабо заполненными матрицами. 

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

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

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

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

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

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

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

      2.1 Графический метод решения задач дискретного программирования 

      Изначально  предположим существование множество  точек, которые в декартовой плоскости можно представить узлами.

         j(Аi ; Сj )

      Для решения подобного типа задач  необходимо визуально вращать луч  по часовой стрелки начальное  значение  Сj

      По  мере вращения находим сумму  i при этом заполнение заданного множества соответствует 

       i i; xi

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

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

      Пример 1

      Z=8x1+7x2+6x3+4x4+2x5 max

      5x1+6x2+7x3+6x4+5x5 23

      Решение 
 

       . 

      5+6+7+6=24

      Х=(1,1,1,0,0)

        Z 1 =21 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

3.1. Задача о назначении

      Имеет некоторое количество n исполнителей, которые могут выполнять n различных  работ. Известна полезность , связанная  с выполнением i-м исполнителем j-й работы          .  Необходимо назначить исполнителей на работы так, чтобы добиться максимальной полезности, при условии, что каждый исполнитель может быть назначен только на одну работу и за каждой работой должен быть закреплен только один исполнитель.

      Математическая  модель задачи примет вид:

     Каждый  исполнитель назначается только на одну работу:

     На  каждую работу назначается только один исполнитель:

     В задаче на узкое место вместо целевой  функции получаем

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

3.2. Задачи транспортного типа

     1. Транспортная задача в матричной  постановке.

     Постановка  задачи. Пусть имеется m пунктов производства и n пунктов потребления однородного продукта. Объем производства в пункте производства с номером i  равен ; объем потребления в пункте потребления с номером j равен . Предполагается, что производство и потребление сбалансированы, т.е.:

     Задана  матрица  транспортных расходов: затраты на перевозку единицы продукции из пункта производства i в пункт потребления j.

     Требуется составить план перевозок, который  не выводит за пределы мощностей  производителей, удовлетворяет полностью  всех потребителей и минимизирует суммарные  затраты на перевозки. Через  обозначим объем перевозки из пункта производства i в пункт потребления j, . Тогда