4.6.5. Задачи целочисленного программирования с булевыми переменными

Если искомые параметры (переменные) должны иметь только целые значения, то для их нахождения надо применять методы решения задач целочисленного программирования. Их достаточно легко реализовать, например, с помощью табличного процессора Excel. Однако Mathcad специальных реализаций таких методов не имеет.

Рис. 4.30. Решение транспортной задачи

Однако в некоторых практических задачах целочисленного программирования искомые переменные могут принимать не любые целые значения, а лишь значения 0 -ответ «нет» и 1 – ответ «да». Такие переменные называют логическими или булевыми. Одной из задач с такими переменными является задача о назначениях. В подобных случаях требуется решить, как распределить рабочих по различным рабочим местам, чтобы общая выработка была наибольшей или затраты на зарплату наименьшими, и как выбрать из нескольких возможных вариантов инвестиционных проектов (например, закупки станков для модернизации цеха) наиболее эффективный проект.

В общем случае можно подобные задачи сформулировать следующим образом.

Предлагается n управленческих решений x_i, каждое из которых позволяет получить эффект от его реализации С₁, С­₂,…С_n. В наличии имеется m видов ресурсов в количестве S_j. Управленческое решение требует для своей реализации объем ресурсов B_ij, где ,. Необходимо так распорядиться имеющимися ресурсами, чтобы максимизировать эффект от принимаемых решений.

Оптимизируемая переменная может принимать только два значения:

Тогда задача оптимизации будет следующей. Найти максимум целевой функции

- экономическая эффективность, при ограничениях:

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

Рассмотрим пример на выбор инвестиционного проекта. Имеется четыре инвестиционных проекта, каждый из которых требует затрат материальных и трудовых ресурсов. Количество ресурсов ограничено и не позволяет реализовать все проекты сразу. Выбрать для реализации оптимальные по суммарному экономическому эффекту проекты. Конкретные числовые данные приведены в таблице, представленной ниже [15].

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

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

Метод заключается в переборе всех возможных вариантов сочетаний допустимых значений переменных, проверке выполнения для каждого из ограничений и вычислении в удовлетворительных случаях соответствующих значений целевой функции. Из полученного множества значений выбирается максимальное (или минимальное), а набор значений переменных для него и будет решением задачи. В общем случае число вычислительных процедур при полном переборе быстро растет и равняется , гдеn – число переменных, m – число ограничений.

Метод имеет простой алгоритм и может быть легко реализован с использованием средств программирования пакета Mathcad (рис. 4.31).

Рис. 4.31. Пример решения задачи целочисленного программирования с булевыми переменными методом прямого перебора