Целочисленное программирование

    ВВЕДЕНИЕ 

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

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

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

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

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

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

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

1. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ

 

1.1 Общие понятия  целочисленного программирования 

     Целочисленным  программированием называется раздел математического программирования, изучающий экстремальные задачи, в которых на искомые переменные накладывается условие целочисленности, а область допустимых решений конечна. Огромное количество экономических задач носит дискретный, чаще всего целочисленный характер, что связано, как правило, с физической неделимостью многих элементов расчета: например, нельзя построить два с половиной завода, купить полтора автомобиля  и т.д. В ряде случаев такие задачи решаются обычными методами, например, симплексным методом, с последующим округлением до целых чисел. Однако такой подход оправдан, когда отдельная единица составляет очень малую часть всего объема (например, товарных запасов); в противном случае он может внести значительные искажения в действительно оптимальное решение [1].

     Целочисленное линейное программирование (сокращенно ЦЛП) занимается задачами линейного программирования с целочисленными переменными, общая задача формулируется следующим образом: найти тах{сх|Ах ≤ b; х - целочисленный}. ЦЛП может рассматриваться так же, как поиск точки решетки, принадлежащей многограннику или как решение системы линейных уравнений с целыми неотрицательными переменными. Иными словами, в ЦЛП рассматриваются совместные ограничения – не отрицательность и целочисленность [3].

     Специфика задач целочисленного программирования заключается в том, что на переменные x_i и функцию цели F(x) налагается дополнительное ограничение – условие целочисленности. Целочисленное программирование иногда называют дискретным программированием. Если требование целочисленности распространяется не на все переменные, а только на часть из них, то задача называется частично целочисленной [2].

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

     Процедура решения задачи методом отсечения  осуществляется следующим образом:

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

     2. Строятся дополнительные линейные  ограничения, отсекающие от ОДЗП  ту её часть, в которой содержится  оптимальное решение и не содержится  ни одного целочисленного решения.

     3. В исходную задачу включается  дополнительное ограничение и  применяется симплекс-процедура.  Если же найденное оптимальное  решение опять будет дробным,  то формируется новое дополнительное  ограничение и процесс вычислений  повторяется [1].

     Рекомендации  по формулировке и решению задач ЦП:

1. Количество целочисленных переменных уменьшать насколько возможно. Например, целочисленные переменные, значения которых должно быть не менее 20, можно рассматривать как непрерывные.
2. В отличие от общих задач ЛП, добавление новых ограничений особенно включающих целочисленные переменные, обычно уменьшают время решения задач ЦП.
3. Если нет острой необходимости в нахождении точного оптимального целочисленного решения, отличающегося от непрерывного решения, например, 3%. Тогда реализацию метода ветвей и границ для задачи максимизации можно заканчивать, если отношение разницы между верхней и нижней границ к верхней границы меньше 0,03 [4].

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

     К частному случаю задачи целочисленного линейного программирования относятся  задачи, где переменные X могут принимать  всего лишь два значения — 0 и 1. Соответствующие задачи часто называют задачами булевского программирования. Наиболее известные из этих задач — задача о назначениях (какого работника на какую работу поставить), задача выбора маршрута (задача коммивояжера, задача почтальона), задача о максимальном паросочетании и т. д. Целочисленное программирование применяется при решении задачи оптимизации развития компании, в которой 0 или 1 означают покупку какого-либо оборудования.

     Для решения задач этого типа разрабатываются  специфические алгоритмы, основанные на комбинаторике, графах и т. д. [5] 

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

 

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

     Задача  линейного целочисленного программирования формируется следующим образом: найти такое решение (план) X = (x₁,x₂,...,x_n), при котором линейная функция

         (1)

принимает максимальное или минимальное значение при ограничениях

      =b_i, i=1, 2…, m.   (2)

           х_j ³ 0, j=1, 2,..., п.   (3)

     x_j - целые числа   (4)

     Для наглядности рассмотрим пример решения  задачи целочисленного программирования: [3]

     Задача  о выборе оборудования. На приобретение оборудования для нового участка цеха выделено 20000 долларов США. При этом можно занять площадь не более 38 м². Имеется возможность приобрести станки типа А и станки типа Б. При этом станки типа А стоят 5000 долларов США, занимают площадь 8 м² (включая необходимые технологические проходы) и имеют производительность 7 тыс. единиц продукции за смену. Станки типа Б стоят 2000 долларов США, занимают площадь 4 м² и имеют производительность 3 тыс. единиц продукции за смену. Необходимо рассчитать оптимальный вариант приобретения оборудования, обеспечивающий при заданных ограничениях максимум общей производительности участка.

     Решение: Пусть Х - количество станков типа А, а У - количество станков типа Б, входящих в комплект оборудования. Требуется выбрать комплект оборудования так, чтобы максимизировать производительность С участка (в тыс. единиц за смену):  

      С = 7 Х + 3 У → max .

     При этом должны быть выполнены следующие  ограничения:

по стоимости (в тыс. долларов США)

     5 Х + 2 У ≤ 20,

по занимаемой площади (в м² )

     8 Х + 4 У ≤ 38,

а также  вновь появляющиеся специфические  ограничения по целочисленности, а именно,

     Х ≥ 0 , У ≥ 0 , Х и У - целые числа.

     Сформулированная  математическая задача отличается от задачи линейного программирования только последним условием целочисленности. Однако наличие этого условия позволяет (в данном конкретном случае) легко решить задачу перебором. Действительно, как ограничение по стоимости, так и ограничение по площади дают, что Х ≤ 4. Значит, Х может принимать лишь одно из 5 значений: 0, 1, 2, 3, 4.

     Если  Х = 4, то из ограничения по стоимости следует, что У = 0, а потому С = 7 Х = 28.

     Если  Х= 3, то из первого ограничения вытекает, что У ≤ 2, из второго У ≤ 3. Значит, максимальное С при условии выполнения ограничений достигается при У =2, а именно С = 21 + 6 = 27. 

     Если  Х= 2, то из первого ограничения следует, что У ≤ 5, из второго также У ≤ 5. Значит, максимальное С при условии выполнения ограничений достигается при У =5, а именно С = 14 + 15 = 29.

     Если  Х= 1, то из первого ограничения имеем У ≤ 7, из второго также

У ≤ 7. Значит, максимальное С при условии выполнения ограничений достигается при У = 7, а именно С = 7 + 21 = 28.

     Если  Х= 0, то из первого ограничения вытекает У ≤ 10, из второго У ≤ 9. Значит, максимальное С при условии выполнения ограничений достигается при У = 9, а именно, С = 27.

     Все возможные случаи рассмотрены. Максимальная производительность. С = 29 (тысяч единиц продукции за смену) достигается  при Х = 2, У = 5. Следовательно, надо покупать 2 станка типа А и 5 станков типа Б.  

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

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