2. Ms Excel: Задачи целочисленного программирования: постановка задачи и метод решения, решение и анализ задач, задачи с булевыми переменными.

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

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

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

• задачи оптимизации раскроя;

• оптимальное проектирование лесных машин и оборудования;

• оптимизации системы сервиса и технического обслуживания машинно-тракторного парка;

• и т.д.

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

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

Методы решения целочисленных задач

Графический метод

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

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

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

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

Для решения задачи графическим методом используется сервис Графический метод. Целочисленное программирование.

Метод ветвей и границ

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

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

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

Ветвление производится последовательным введением дополнительных ограничений. Пусть xk – целочисленная переменная, значение которой в оптимальном решении получилось дробным. Интервал [βk] ≤ xk ≤ [βk ]+1 не содержит целочисленных компонентов решения. Поэтому допустимое целое значение xk должно удовлетворять одному из неравенств xk≥[βk]+1 или xk≤[βk ]. Это и есть дополнительные ограничения. Введение их в методе ветвей и границ на каждом шаге порождает две не связанные между собой подзадачи. Каждая подзадача решается как задача линейного программирования с исходной целевой функцией. После конечного числа шагов будет найдено целочисленное оптимальное решение.

Задачи с булевыми переменными

Одним из видов задач линейного программирования является бинарная задача, в результате решения которой искомые переменные могут принимать только значение 0 или 1.

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

Введем переменные х1, х2, х3, х4, х5 такие, что хi=1 – если проект i реализуется, хi=0 – если не реализуется. Получаем следующую модель задачи:

при

После ввода необходимых данных и ограничений в окне Поиска Решения получили следующие результаты: в течение трех лет предлагается реализовать проекты 1,2, 3 и 4, что потребует 19.86 ед. капиталовложений в первом году, 19.65 – во втором и 17.07 – в третьем и принесет суммарную прибыль в размере 65.39 ед.