Формирование зависимых решений

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

Если вариант m не принят, то и ограничение требует, чтобы значение также было равно нулю (т.е. вариант k принят не будет). Если же вариант m принят, и ограничение принимает вид . В этом случае программа может выбрать .

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

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

Общий алгоритм выбора некоторого подмножества ограничений из имеющихся формулируется следующим образом. Задано множество из m ограничений для n (недвоичных) переменных :

где - заданная функция от переменных . В модель вводится m дополнительных двоичных переменных и задается очень большое число M, такое, чтобы для всех заведомо выполнялись неравенства

Тогда следующие m + 1 ограничения выражают нужное условие:

Ограничение требует, чтобы ровно k новых переменных решения принимали значение 1. Это означает, что ровно k вышеприведенных ограничений-неравенств будут эквивалентны неравенствам

Оставшиеся m – k ограничений принимают вид

и так как M – очень большое число, все эти ограничения оказываются избыточными и не влияют на оптимальное решение задачи.

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

Простое указание этих ограничений в модели ЛП означало бы, что в процессе производства должны выполняться оба ограничения одновременно, а не одно из них. В данном случае в модель ЛП необходимо ввести две новые двоичные переменные и , преобразовав ее в модель частично целочисленного ЛП. Пусть условие означает выбор технологии I; а - отказ от выбора технологии I и аналогично для переменной .

Ограничения модели принимают вид:

В этом случае первое ограничение заставит программу-оптимизатор выбрать только одну технологию, а большое число (в данном случае 999999) необходимо подобрать так, чтобы или первое или второе ограничение оказалось избыточным, если соответственно или или будут равны единице.