Целочисленная задача линейного программирования (задача с неделимостями).

Целочисленная задача линейного программирования заключается в максимизации функции: с,Х( + с2х2 + ...

(1)

при условиях

ntll \' "тУ-2 "пиг\'п - "т >

X, > 0, Xj > 0, ..., Х„ > 0, (3)

Xj — целые числа, j є J, ^

где J — некоторое подмножество множества индексов N = ={1,2,...,n}.

Если J = N (T.e. требование целочисленности наложено на все переменные), то задачу называют полностью целочисленной; если же J Ф N, она называется частично целочисленной.

Модель (1)—(4) естественно интерпретировать, например, в следующих терминах. Пусть через i = 1,..., т обозначены производственные факторы, через j = 1, ..., п — виды конечной продукции.

Обозначим далее:

aij — количество факторов i, необходимое для производства единицы продукта j;

bi — наличные ресурсы фактора i;

СІ — прибыль, получаемая от единицы продукта j.

Пусть продукты j для j^J являются неделимыми, т.е. физический смысл имеет лишь их целое неотрицательное количество («штуки»). Предположим, что требуется составить производственную программу, обеспечивающую максимум суммарной прибыли и не выводящую за пределы данных ресурсов. Обозначая через x}- искомые объемы выпуска продукции, мы сводим эту задачу к модели

(1)-(4).

Задача с булевыми переменными. Логическая взаимосвязь:

1) взаимоисключение. Пусть x}- = 1, если реализуется проект Aj, и х}- = 0 в противном случае. Запись AjVAk означает, что в план может быть включен либо проект Aj, либо проект Ak. Вместе они включены быть не могут. С помощью этой записи выражается отношение взаимоисключения между проектами.

В этих обозначениях взаимоисключение Aj v Ак выражается неравенством Xj + хк < 1;

2) взаимообусловленность. Запись Ак ® Aj («проект Ак влечет за собой проект А;») означает, что проект Ак может быть включен в план только в том случае, если в план включен и проект Aj. С помощью этой записи выражается отношение между обусловливающими друг друга проектами, например когда проект Ak — результат тиражирования проекта Aj на другом объекте или когда Ак базируется на результатах реализации проекта Aj.

В принятых обозначениях взаимообусловленность Ак ® АЦ выражается неравенством хк < Xj.