Задача о распределении бюджета

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

Вариант	Чистая прибыль, тыс. д.е.	Вложения по годам, тыс. д.е.
		1	2	3	4	5
Расширение завода в стране А	400	100	50	200	100	0
Расширение мощностей по производству ПК в своей стране	700	300	200	100	100	100
Открытие нового завода в стране Б	800	100	200	270	200	100
Расширение мощностей по производству комплектующих в своей стране	1000	200	100	400	200	200
Имеющиеся средства		500	450	700	400	300

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

при ограничениях

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

(следует принять первые три проекта). Отметим, что метод округления дает при этом неправильный результат – он рекомендует отвергнуть третий проект.

12.2. Использование логических условий и формирование зависимых решений с помощью целочисленных переменных

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

Например, ограничение

,

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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