Применение двоичных переменных

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

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

Таблица

Проекты расширения производственных мощностей. (Все суммы в тыс. долл.).

Для построения формальной модели введем следующие двоичные переменные: Х_i =1, если проект i-го ПК включается в общий план расширения производственных мощностей холдинга, Х_i =0 в противном случае. С помощью введенных переменных мы можем записать ограничения по объему средств, доступных для проектов расширения производственных мощностей по годам:

100Х₁  + 300Х₂  +100 Х₃  + 150Х₄  +50Х₅  £ 650

50Х₁  +200Х₂  +200 Х₃  + 60Х₄  +40Х₅  £ 550

100Х₁  + 100Х₂  +250 Х₃  + 250Х₄  +150Х₅  £ 700

100Х₁  + 100Х₂  +200 Х₃  + 100Х₄  +100Х₅  £ 500

  100Х₂  +100 Х₃  + 100Х₄  +100Х₅  £ 300

Целевая функция (общая прибыль по всем проектам, выбранным для реализации) может быть представлена с помощью введенных переменных следующим образом:

Z = 4 000Х₁  + 7000Х₂  +8000 Х₃  + 6000Х₄  +4000Х₅

Необходимо найти значения переменных X₁,….X₅, при которых выполнены все ограничения и целевая функция принимает максимальное значение.

Оптимальное решение данной задачи найдем с помощью средств Поиск решения MS Excel. При введении ограничений необходимо указать, что все переменные X₁,….X₅  являются двоичными, т.е. могут принимать только значения 0 или 1 (см. Рисунок 2.9). В оптимальном решении данной задачи будут получены следующие значения переменных и целевой функции

Х₁  =1, Х₂=1, Х₃  =1, Х₄ =1, Х₅  =0, Z_max = 2500

Введение дополнительных условий.

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

Х₁  + Х₂  +Х₃  + Х₄  +Х₅  £ 3

В оптимальном решении задачи с введенным дополнительным условием будут получены следующие значения переменных и целевой функции Х₁  =0, Х₂=1, Х₃  =1, Х₄ =1, Х₅  =0, Z_max = 2100

Предположим также, что руководство холдинга считает целесообразным начинать реализацию проекта расширения производственных мощностей для ПК3 только в том случае, если одновременно будет осуществляться проект расширения производственных мощностей для ПК1. Для того чтобы учесть это требование достаточно в модель ввести еще одно дополнительное ограничение:

Х₃   £ Х₁

В оптимальном решении задачи с введенными дополнительными условиями будут получены следующие значения переменных и целевой функции Х₁  =1, Х₂=1, Х₃  =1, Х₄ =0, Х₅  =0, Z_max = 1900.

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