Содержание
Введение            3
1 Целочисленное линейное программирование     4
1.1 Методы решения задач целочисленного программирования  4
1.2 Метод отсекающихся плоскостей (метод Гомори)    8
1.3 Метод ветвей и границ        17
2 Решение задачи целочисленного программирования    21
Список использованной литературы       26
 
Введение
Общая постановка задачи целочисленного программирова¬ния отличается от общей постановки задачи линейного про¬граммирования лишь наличием дополни-тельного ограничения. Этим ограничением является требование целочисленно-сти, в соответствии с которым значения всех или части пере¬менных модели в оп-тимальном решении являются целыми нео¬трицательными числами. При этом если требование целочисленности распространяется на все переменные, то задачу це-лочисленного программирова¬ния называют полностью целочисленной задачей. Если же требование целочисленности относится лишь к части пе¬ременных, то за-дачу называют частично целочисленной. Задачу линейного программирования, отличающуюся от рас¬сматриваемой задачи целочисленного программирования лишь отсутствием требования целочисленности, называют задачей с ослабленны-ми ограничениями, соответствующей задаче целочисленного программирования.
 
1 Целочисленное линейное программирование
1.1 Методы решения задач целочисленного программирования
На первый взгляд наиболее естественным методом реше¬ния задач целочис-ленного программирования является метод округления, реализация которого со-стоит из двух этапов. На первом этапе находят оптимальное решение задачи ли-нейного программирования с ослабленными ограничениями, соответ¬ствующей рассматриваемой задаче целочисленного программи¬рования. На втором этапе зна-чения переменных в оптимальном решении X*, не являющиеся целыми, округля-ют так, чтобы получить допустимое решение X** с целочисленными значе¬ниями.
Соблазнительность использования метода округления по¬нятна, особенно ес-ли погрешность округления невелика по сравнению со значениями округляемых переменных. Однако практическая реализация метода округления может привести к допустимому решению, значимо отличающемуся от оптималь¬ного решения ис-ходной задачи целочисленного программирова¬ния.
Несостоятельность метода округления как общего метода решения задач це-лочисленного программирования обусловлена не только возможностью получения неоптимального решения. Дело заключается в том, что многие задачи математиче-ского программирования, не имеющие на первый взгляд никакого отношения к полностью или частично целочисленным задачам, могут быть сформулированы как задачи целочисленного программирования, в которых переменные модели принима¬ют значения из множества {0, 1}. В этой ситуации процедура округления является логически неприемлемой.
Для иллюстрации основной идеи методов решения задач це¬лочисленного программирования, известных как методы отсечений, рассмотрим полностью це-лочисленную задачу, множество допустимых решений которой изображено на ри-сунке 1. Допустимым решениям этой задачи соответствуют не все точ¬ки множест-ва G допустимых решений, а лишь те, координаты которых удовлетворяют требо-ванию целочисленности. Теоре¬тически из множества G всегда можно выделить такое подмножество G*, что (см. рис. 1.1):
а) оно содержит все точки множества G, координаты которых удовлетворя-ют требованию целочисленности;
б) оно является выпуклым множеством;
в) ко¬ординаты всех его крайних точек удовлетворяют требованию целочис-ленности.
 
Рисунок 1.1
Если в рассматриваемой полностью целочисленной задаче множество G до-пустимых решений заменить множеством G*, то это не может привести к измене-нию ее оптимального ре¬шения, так как G* получено из G путем отсечения от него подмножества, заведомо не содержащего допустимых решений, удовлетворяющих требованию целочисленности. Но в этом слу¬чае оптимальное решение задачи ли-нейного программирования с ослабленными ограничениями и множеством G* до-пустимых решений соответствует крайней точке множества G*. Как следствие, оно удовлетворяет требованию целочисленности и обеспечивает экстремальное значение целевой функции не толь¬ко на G*, но и на G, т.е. является оптимальным решением исходной полностью целочисленной задачи. Основные разли¬чия в ме-тодах отсечений связаны с процедурами выделения подмножества G* множества допустимых решений задачи це¬лочисленного программирования.
В основе комбинаторных методов решения задач цело¬численного програм-мирования лежит идея перебора всех эле¬ментов G множества допустимых реше-ний, удовлетворяющих требованию целочисленности, с целью нахождения опти-мального решения. При этом за счет использования различных спе¬циальных про-цедур, как правило, непосредственно рассматри¬вают лишь часть элементов G, удовлетворяющих требованию целочисленности, а оставшиеся элементы учиты-вают некото¬рым косвенным образом.
Наиболее известным комбинаторным методом является ме¬тод ветвей и гра-ниц, использующий процедуру решения задачи линейного программирования с ослабленными ограни¬чениями, соответствующей исходной задаче целочисленного программирования. Если оптимальное решение X* задачи ли¬нейного программи-рования с ослабленными ограничениями не удовлетворяет требованию целочис-ленности (на рисунке 2 этому решению соответствует точка В), то из множества G допу¬стимых решений выделяют два непересекающихся выпуклых подмножества К1 и К2, содержащих все допустимые реше¬ния из G, удовлетворяющих требова-нию целочисленности и не содержащих X* (см. рис. 1.2). Это позволяет заменить рас¬сматриваемую задачу целочисленного программирования со¬вокупностью двух эквивалентных ей задач с множествами допустимых решений К1 и К2 соответст-венно, так как   или  .
 
Рисунок 1.2
Комбинаторные методы широко используют для решения задач булева про-граммирования, т.е. для решения полностью целочисленных задач, переменные которых принимают значе¬ния из множества {0, 1}. Эти переменные называют бу-левыми переменными. Свойства булевых переменных позво¬ляют существенно уп-ростить процедуры поиска оптимального решения.
К настоящему времени разработано значительное количе¬ство частных мето-дов решения конкретных типов задач цело¬численного программирования. Тем не менее почти все эти методы и их модификации можно описать на основе единой принципиальной схемы, состоящей из трех элементов.
Элемент 1. Предусматривается процедура формирования и решения после-довательности взаимосвязанных задач, которые называют задачами, порожденны-ми исходной задачей, или задачами-истоками. При этом оптимальное решение по крайней мере одной из задач-истоков должно со¬впадать с оптимальным решением породившей их задачи.
Элемент 2. Каждой задаче, порожденной исходной за¬дачей, ставится в соот-ветствие так называемая ослабленная задача (задача с ослабленными ограниче-ниями), оптимальное решение которой может быть найдено с гораздо меньшими затратами, чем оптимальное решение соответствующей ей за¬дачи-истока. Специ-фика ослабленной задачи чаще всего за¬ключается в том, что ее система ограниче-ний является менее жесткой по сравнению с системой ограничений задачи-истока и определяет множество допустимых решений, содержащее все допустимые ре-шения задачи-истока. Как правило, в целочи¬сленном программировании ослаб-ленная задача представляет собой задачу линейного программирования с ограни-чениями, более слабыми, чем в соответствующей целочисленной задаче-истоке. Очевидно, что если ослабленная задача не имеет допустимых решений, то их не имеет и задача-исток. В некоторых модификациях методов целочисленного про-граммирования це¬левая функция ослабленной задачи также может отличаться от целевой функции задачи-истока. В этом случае оптималь¬ное значение целевой функции ослабленной задачи (т.е. значение, соответствующее оптимальному ре-шению) должно быть не меньше оптимального значения целевой функции за¬дачи-истока, если речь идет о задаче максимизации. Кроме того, оптимальное значение целевой функции ослабленной за¬дачи определяет (для задачи максимизации) верхнюю границу для оптимального значения целевой функции задачи-истока.
Элемент 3. В результате анализа решения ослабленной задачи в зависимости от специфики метода, как правило, при¬нимается решение, относящееся к задаче-истоку:
а) исключить ее из рассмотрения;
б) заменить одной порожденной задачей, выбранной по специальному пра-вилу из определенной совокуп¬ности;
в) заменить системой порожденных задач.
Следует отметить, что существуют и другие подходы к решению задач це-лочисленного программирования, которые в общем случае не гарантируют нахо-ждения оптимального реше¬ния, но приводят к допустимому решению, близкому (в смысле значения целевой функции) к оптимальному, а иногда и совпа¬дающему с ним. В основе одного из таких подходов лежит идея использования случайной выборки допустимых решений с по¬следующим улучшением (в смысле значения целевой функции) каждого из них, когда возможность улучшения допустимого решения достаточно просто обнаружить.
 
Список использованной литературы
1. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програму-вання: Навч.-метод. Посібник для самост. Вивч. Диск. – к.: КНЕУ, 2001. – 248с.
2. Волков И.К., Загоруйко Е.А. Исследование операций: Учеб. для вузов. 2-е узд. / Под ред.. В.С. Зарубина, А.П. Крищенко. – М.: Узд-во МГТУ им. Н.Э. Баумана, 2002. – 436 с.
3. Зайченко Ю.П. Исследование операций: Учеб. пособие для студентов вузов. – 2-е изд., перераб. и доп. – Киев: Вища школа. Главное изд-во, 1979. 392 с.
4. И. А. Акулич. Математическое программирование в примерах и задачах. - М.: «Высшая школа», 1986.- 319 с.
5. Сакович В.А. Исследование операций (детерминированные методы и моде-ли): Справочное пособие. - Мн.: Выш. шк., 1984.-256с.
6. Таха Х. Введение в исследование операций: в двух книгах. Кн.1,2 Пер. с англ. - М.: Мир, 1985.
7. Хазанова Л.Э. Математическое программирование в экономике: Учебное пособие. – М.: Издательство БЕК, 1998. – 141с.