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

                                                                                            (2.1)

                                                                                  (2.2)

                                                                                (2.3)

                                                                      (2.4)

     Задача (2.1) – (2.4) — это задача линейного  программирования, число переменных равно , число ограничений (2.2) и (2.3)  равно . Число ненулевых значений не превосходит -1, так как в силу условия сбалансированности строки матрицы задачи, формируемой из условий (2.2) и (2.3), линейно зависимы. Поэтому ранг матрицы транспортной задачи не превосходит -1. Известно, что условие сбалансированности производства и потребления является необходимым и достаточным условием разрешимости транспортной задачи. Известно также, что значение целевой функции (2.1) ограничено снизу и сверху, если все , и ограничены, при этом .

     2. Транспортная задача с фиксированными доплатами.

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

     величины: — объем производства в пункте производства i ; - объем потребления в пункте потребления j.

     Обозначим через  объемы перевозок из пункта i в пункт j. Тогда задача будет иметь вид

                                                                                      (2.10)

                                                                                  (2.11)

                                                                                (2.12)

                                                                    (2.13)

       Каждая из функций  в формуле (2.10) имеет вид

           

     Числа — затраты на перевозку единицы груза из i в j. Под можно понимать, например, плату за аренду транспортных средств, не зависящую от их загрузки, либо затраты на строительство магистрали от каждого пункта i до

каждого пункта j, не зависящие от будущих грузопотоков. Предполагается, что , , , . График функции cxeматически изображен на рис.3. 

     

     рис.3

     Задачу (2.10) – (2.14) называют транспортной задачей  с фиксированными доплатами или  неоднородной транспортной задачей. Очевидно, что если все  , задача превращается в обычную транспортную задачу. 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

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

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

     

     

. 
 

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

     

     

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

                                                                                               (2.15)

                                                                                                    (2.16)

                                           .                                       (2.17)

     Естественно предположить, что  , , .

       Множество допустимых решений  этой задачи — это множество  n-мерных булевых векторов , удовлетворяющих условию (2.16).

     Вместе  с задачей   (2.15) – (2.17) будем  рассматривать  задачу линейного  программирования, в которой вместо условий (2.17) вводятся условия

                                      ,                                        ( )

     2. Задача о многомерном ранце.

     Эта задача имеет вид

                                                                      (2.18)

                   ,                        (2.19)

                                         .                                      (2.20)

     Предполагаем, что  , , , .

     В этой задаче каждый предмет имеет  m свойств. Эти свойства описываются количественно с помощью элементов столбца с номером j матрицы .

     Множество допустимых решений этой задачи — это множество булевых векторов , удовлетворяющих условиям (2.18)

     Вместе  с задачей   (2.18) – (2.20) будем  рассматривать  задачу линейного  программирования, в которой вместо условий (2.20) вводятся условия

                                     ,                                         ( ) 
 
 
 
 
 
 

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

     Существование допустимого решения. В задачах (2.15) – (2.17) и (2.18) – (2.20) допустимое решение всегда существует (например, нулевое). Если решить задачи линейного программирования (2.15) – ( ) и (2.18) – ( )и в полученных оптимальных решениях заменить  дробные значения нулевыми, то получим допустимые решения задач (2.15) – (2.17) и (2.18) – (2.20). Число дробных значений в оптимальных решениях линейных задач не превосходит m.

     Отсев подмножеств булевых  векторов, не содержащих оптимальных решений.  Рассмотрим вектор , имеющий k единиц и n – k нулей. Если вектор является допустимым, то можно исключить из дальнейшего рассмотрения векторов, получающихся из заменой любого числа единиц нулями, так как для любого такого вектора x значение функции будет меньше, чем . Если вектор не является допустимым, то можно исключить из дальнейшего рассмотрения векторов, которые получаются из

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

     Оценка  точности приближенных булевых решений. Пусть допустимое булево решение задачи (2.15) – (2.17) или (2.18) – (2.20); — оптимальное булево решение; — оптимальное решение задачи (2.15) – ( ) или (2.18) – ( ).Тогда имеет место следующее неравенство:

                                                                                         (2.21)

     Величина  есть гарантированная оценка отклонения приближенного решения от оптимума .

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

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

     Рассмотрим  задачу линейного программирования (2.15) – ( )и опишем алгоритм нахождения оптимального решения .

     ТЕОРЕМА (правило Данцига). Пусть переменные , перенумерованы так, что , где . Тогда оптимальное решение имеет вид

     

где s определяется из условия

     

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

     

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

     

     Перейдем  к доказательству теоремы. Рассмотрим решение линейной задачи (2.15) – ( ),полученное в соответствии с правилом Данцига:

     

     Для этого решения имеем

     

     Пусть и . Построим допустимое решение x задачи (2.15) – ( ) по следующему правилу: пусть , тогда

     

     Покажем, что  . Вычислим

     

     Выпишем ограничение для решения х:

     

     Поскольку

     

     то 

     

     Получаем

     

     Вычислим  разность:

     

 

так как  при  имеем , а для   имеем . Поэтому , что и требовалось доказать. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Заключение 

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

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

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

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