ЛАБОРАТОРНЫЙ ПРАКТИКУМ ДЛЯ ИЗУЧЕНИЯ
ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ
(*****@***ru)
Государственный социально-гуманитарный университет (ГСГУ)
г. Коломна
Аннотация
Описан лабораторный практикум для решения линейных целочисленных задач линейного программирования на основе метода отсекающих плоскостей Гомори и метода ветвей и границ. Применяется в курсе «Исследование операций» на физико-математическом факультете педагогического вуза.
Целочисленное программирование ориентировано на решение задач, в которых все или некоторые переменные должны принимать целые значения. Использование при решении задач этого вида принципа округления решения до целых неприемлемо во многих случаях. В курсе "Исследование операций" рассматриваются два метода решения целочисленных задач линейного программирования (ЗЛП).
В методе отсекающих плоскостей Гомори первоначально решается задача линейного программирования без условия целочисленности переменных. Если полученное решение не удовлетворяет условию целочисленности, то от многогранника решений отсекается его часть с точкой текущего максимума, не содержащая целочисленных допустимых точек. Это отсечение осуществляется линейным ограничением (отсекающей плоскостью Гомори), которое формируется из анализа последней оптимальной симплекс-таблицы на основе ее производящей строки [1]. Далее решается ЗЛП с введенным дополнительным ограничением. Если оптимальное решение новой задачи не удовлетворяет условию целочисленности, то процедуру усечения многогранника решений (то есть введения новых отсекающих плоскостей) следует продолжить до получения целочисленного решения.
В лабораторной работе необходимо решить полностью целочисленную ЗЛП относительно двух переменных с системой ограничений из двух или трех неравенств. Такая задача в курсе "Исследование операций" ранее решалась графическим методом. При выполнении лабораторной работы ЗЛП решаются с помощью программы "Решение и моделирование задачи линейного программирования", написанной на Visual Basic for Applications (VBA) и реализующей алгоритм симплексного метода [2]. После получения оптимального решения на основе производящей строки формируется отсечение Гомори, которое необходимо внедрить в текущую оптимальную таблицу. При этом текущее нецелочисленное решение оказывается недопустимым. Программа выдает соответствующую диагностику и двойственным симплекс-методом находит новое оптимальное и допустимое решение. Новое текущее оптимальное решение снова проверяется на целочисленность, после чего принимается решение об окончании решения или введении дополнительного отсечения Гомори. Так образом, в лабораторной работе главной задачей студента является правильное построение отсечения Гомори на основе анализа оптимальной симплекс-таблицы, полученной при решении ЗЛП с помощью программы, и внедрение нового ограничения в текущую оптимальную таблицу для формирования исходных данных для решения новой ЗЛП.
Полученное в лабораторной работе решение можно проверить с помощью программы "Метод Гомори для полностью целочисленных задач", написанной в форме макроса VBA [3]. На рабочем листе выводится количество использованных отсечений Гомори и результирующая симплекс-таблица. В специальном рабочем листе, скрытом от пользователя в обычном режиме работы, выводятся все промежуточные итерации симплекс-метода и процедуры построения отсечений Гомори. В процессе решения могут возникать альтернативные варианты действия (например, при выборе производящего уравнения). Поэтому возможны получения разных решений при ручном и программном способах построения отсечений Гомори. Но в альтернативных решениях обязаны совпадать значения целевых функций. В этом случае различие в оптимальных планах говорит лишь о неоднозначном решении исходной задачи.
Другой рассматриваемый способ решения задач линейного целочисленного программирования – метод ветвей и границ. Сначала решается ЗЛП без условия целочисленности переменных. Пусть переменная xr - целочисленная переменная, которая в оптимальном решении ЗЛП без условия целочисленности принимает дробное значение xr*. Очевидно, что интервал значений
[xr*] < xr < [xr*] + 1 не содержит оптимального решения задачи (здесь [a] – целая часть числа a). Значит, оптимальное решение задачи должно удовлетворять одному из неравенств: xr ≤ [xr*] или xr ≥ [xr*] + 1. Вводя эти неравенства в исходную ЗЛП, порождаем две новые задачи, то есть исходная ЗЛП разветвляется. Каждая полученная задача снова решается и разветвляется по указанному принципу. Если в какой-либо из подзадач полученный оптимум является целочисленным, то это решение следует зафиксировать как наилучшее (границу). При этом продолжать ветвление данной подзадачи нет необходимости. Улучшить полученное решение таким образом не удастся, потому что при введении нового ограничения область допустимых значений задачи только сокращается. Если в одной из подзадач решение оказывается лучше имеющегося, то оно фиксируется как новая граница. Ветвление ведется до тех пор, пока каждая подзадача не приведена к целочисленному решению, или пока не будет установлена невозможность улучшения имеющегося решения. Если решение некоторой подзадачи хуже, чем текущая граница, то далее эту подзадачу разветвлять не надо. В этом случае говорят, что подзадача прозондирована. Таким образом, решение заканчивается, если все подзадачи либо прозондированы, либо приведены к целочисленному решению. Из сказанного выше следует, что имеющееся решение задачи является критерием, определяющим необходимость дальнейшего ветвления подзадачи. Отсюда следует важность быстрого определения близкой к оптимальному решению границы. В этом случае объем вычислений значительно сокращается. Но строгого алгоритма порядка ветвления (а значит, и выбора границы) - не существует.
В лабораторной работе решается та же задача, что и ранее методом отсечений Гомори. Все ЗЛП, соответствующие подзадачам, решаются с помощью рассмотренной ранее программы "Решение и моделирование задачи линейного программирования". В процессе решения студенту необходимо правильно сформировать систему ограничений текущей подзадачи, сформировать исходные данные для программы, получить решение подзадачи и проанализировать полученный результат для принятия решения о дальнейшем ветвлении или объявления ветви прозондированной. Процесс вычислений необходимо проиллюстрировать построением дерева решений, в вершинах которого указаны оптимумы соответствующих подзадач, а на ветках указаны условия ветвления [3].
Таким образом, задача линейного целочисленного программирования решается методом отсекающих плоскостей Гомори и методом ветвей и границ. Причем основная вычислительная работа в обоих методах осуществляется с помощью освоенной ранее программы, реализующей симплексный метод решения ЗЛП, а учебной целью является освоение вычислительных процедур построения отсекающих плоскостей и ветвления текущего решения. Данный подход к изучению основ целочисленного программирования реализован при изучении курса "Исследование операций" на физико-математическом факультете педагогического вуза.
Литература
ведение в исследование операций, 7-е издание.: Пер. с англ - М.: Издательский дом "Вильямс", 2005. Трушков операций. Основы теории и компьютерный практикум. Часть 1. Линейное программирование: Учебное пособие. – Коломна: ГСГУ, 2016. Трушков операций. Основы теории и компьютерный практикум. Часть 2. Задачи транспортного типа. Сетевое и целочисленное программирование: Учебное пособие. – Коломна: ГСГУ, 2016.