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

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

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

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

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

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

на тему:

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

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

студент  ПИ – 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 может оказаться настолько большим, что этот перебор невыполним на ЭВМ любой мощности.

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

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

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

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

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

                                      

                                                               (1.2)

                                     

                                                    (1.3)

                                         

                                                          (1.4)

                                    

  целые                                                (1.5)

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

     

 

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

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

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

 

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

рис.1 

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

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

рис.2 

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

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

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

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

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

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

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

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

     

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

     

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

     

     

     

 

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

     

 

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

 

 

 

 

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

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