Тема 4. Целочисленное программирование как инструмент принятия управленческих решений

1. Сущность и методы целочисленного программирования.

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

Задача ЛП, в которой часть переменных или все переменные принимают только целые значения, называется задачей линейного целочисленного программирования.

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

Метод отсечения сначала предусматривает решение исходной задачи симплекс-методом без учета целочисленности. Если полученное решение нецелочисленно, то вводится добавочное ограничение, геометрически представляющее собой гиперплоскость, которая отсекает часть плоскости исходной задачи вместе с полученным оптимальным нецелочисленным решением. При введение дополнительного ограничения (а все ограничения в данной задаче представлены в виде равенств) оптимальное нецелочисленное решение находится вне области допустимых решений. Затем задачи ЦП уже с (n+1) ограничением вновь решается симплекс-методом и находится оптимальное решение для новой области допустимых решений. Если это решение опять не является целочисленным, то процедура повторяется. Таким образом, отличительная особенность метода отсечений – рост числа ограничителей и сужение области допустимых решений задачи на каждом последующем шаге.

Метод ветвей и границ применяется для решения полностью целочисленных и смешанных задач ЦП. На первом шаге решается задача без учета целочисленности. Допустим, что получено решение х₀ и f(х₀)=z₀. Если в этом решении некоторые переменные имеют дробные значения, то z₀ является верхней границей z=f(x*). На втором шаге производится ветвление по одной из целочисленных переменных, имеющих дробное значение в оптимальном плане x₀. Пусть целочисленная переменная принесла дробное значение b_k. Тогда допустимое множество решений разбирается на два подмножества, в одном из которых

x_k ≤ │b_k│ (19)

в другом

x_k ≥ │b_k│+ 1 (20)

Исходная задача разбивается на 2 новые. Допустимые области решений задач 1 и 2, вместе взятые, содержат все допустимые решения целочисленной задачи. Если в оптимальных решениях новых задач целочисленные переменные опять приняли дробные значения, то происходит дальнейшее ветвление задачи. Процесс ветвления и решения задачи продолжается до тех пор, пока не будет получено оптимальное целочисленное решение х* одной из задач. Если такое решение получено, то все вершины задачи ЛП, в которых значения целевой функции z = f(x*) отбрасываются, и в дальнейшем ветвлении участвуют только вершины, значения целевой функции в которых больше z. Процесс разбиения продолжается до тех пор, пока каждое подмножество не будет представлять собой точку допустимого множества. Ветвление какой-либо задачи заканчивается, если выполняется одно из трех следующих условий.

1. Решение недопустимое.

2. Решение целочисленное и допустимое.

3. Добавление последующих ограничений не может улучшить значения целевой функции (ЦФ).

В целях ускорения сходимости процесса при выборе точки ветвления используются следующие правила:

1) выбирается задача, соответствующая наилучшим значениям ЦФ

2) выбирается задача ЛП, решавшаяся последней

3) выбирается целочисленная переменная, имеющая дробную часть, близкую к ½.

2. Примеры задач ЦП – найти число бревен, распиливаемых каждым способом, с тем чтобы заготовки любого вида (длиной 1,2 и 0,9 м и числом не менее 50 и 81 шт. соответственно) было получено из наименьшего числа бревен; транспортная задача; задача коммивояжера – коммивояжеру нужно побывать в каждом из n городов, начиная и заканчивая свой маршрут городом 1. Он не имеет права дважды заезжать ни в один из городов – оптимизационная задача заключается в отыскании кратчайшего пути; распределение капиталовложений (бинарное решение – принцип выбор – «да-нет»).