Министерство образования Российской Федерации
Санкт-Петербургский государственный технологический институт (Технический университет)
Кафедра финансов и статистики Кафедра менеджмента и маркетинга
И.Л. Корнилова, н.Н. Парамонова метод ветвей и границ решения задач целочисленного линейного программирования
Методические указания к лабораторной работе
Санкт-Петербург 2003
Корнилова И.Л., Парамонова Н.Н. Метод ветвей и границ решения задач целочисленного линейного программирования: Метод, указания. СПб СПбГТИ(ТУ), 2003. - 20 с.
В методических указаниях описана лабораторная работа, посвященная решению задач целочисленного линейного программирования с помощью метода ветвей и границ. Рассмотрены примеры решения задач, в том числе задачи с булевыми переменными.
Методические указания предназначены для студентов 2-4 курсов факультета экономики и менеджмента и соответствуют рабочей программе дисциплины «Экономико-математические методы».
Ил. 10, библиогр. 3 назв.
УДК 519.8
Рецензент: А.Е. Викуленко, д-р экон. наук, проф. кафедры менеджмента и маркетинга СПбГТИ(ТУ).
-
Утверждены на заседании учебно-методической комиссии факультета экономики и менеджмента 14.01.03.
Рекомендованы к изданию РИСо СПбГТИ(ТУ).
Введение
Задача линейного программирования (ЗЛП), переменные которой могут принимать только целые значения, является задачей целочисленного линейного программирования (ЗЦЛП):
(1)
где
;
xj
- переменные, aij,
bi,
cj
- константы.
Записанная в таком виде задача представляет собой полностью целочисленную задачу. Существуют, кроме того, частично целочисленные задачи, в которых ограничения целочисленности наложены только на часть переменных, а остальные переменные могут быть как целыми, так и дробными. Переменные, на которые не накладывается ограничения целочисленности, иногда называют непрерывными, и нецелочисленные задачи также называют непрерывными (в противоположность целочисленным).
Примером целочисленной задачи в экономике может служить задача производственного планирования [1, 2], в которой в качестве продукции выступают корабли, дома, вагоны и т.п. предметы, выпуск которых нельзя измерить в непрерывной шкале. Часто переменные в экономико-математических моделях измеряются в количестве человек, которое также не может быть дробным.
На первый взгляд, тривиальным подходом к решению такой задачи является решение задачи линейного программирования без ограничений целочисленности и последующее округление полученного решения до целых. Однако в общем случае такой подход неверен, так как он может привести к одной из двух ошибок. Во-первых, при округлении возможен выход за пределы области допустимых планов (ОДП), т.е. полученное решение не будет удовлетворять ограничениям. Во-вторых, даже оставшись в пределах ОДП, можно в результате получить неоптимальное решение.
Поэтому округление допустимо использовать лишь в тех случаях, когда по своему экономическому смыслу целочисленные переменные не представляют особо ценные объекты, либо в модели рассматривается очень большое количество таких объектов; т.е. нет необходимости получить точное решение. В противном случае задача должна ставиться, как целочисленная, и к ее решению необходимо применить специфические методы, которые обычно относятся к одной из трех групп:
а) Метод ветвей и границ.
б) Методы отсечения.
в) Методы динамического программирования.
Здесь будет рассмотрен метод, относящийся к первой группе. При этом используется ряд определений теории графов, сформулированных в Приложении А.