Целочисленные задачи линейного программирования

Существуют задачи, в которых неизвест­ные величины могут принимать только целочисленные значения. Например, задачи, связанные с определением необходимого чис­ла рабочих мест или количества дорогостоящих станков. При ре­шении таких задач с целочисленными переменными методы ли­нейного (выпуклого) программирования неприменимы. Другая сфера применения целочисленных моделей — выбор вариантов. В соответствующих задачах все или некоторые пере­менные могут принимать только два значения: 0 или 1. Такие пе­ременные носят название булевых.

Наиболее известные методы решения целочисленных задач — метод отсечения и метод ветвей и границ. Они разработаны в на­чале 60-х годов XX века и затем неоднократно усовершенствова­лись и модифицировались. Первоначальным стимулом к изучению целочисленных и дис­кретных задач явилось рассмотрение задач линейного программи­рования, в которых переменные представляли физически недели­мые величины (скажем, количество единиц продукции разных видов). Для характеристики этого класса моделей используется термин «задачи с неделимостями».

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

Целочисленная задача линейного программирования заключа­ется в максимизации функции:

(1)

при условиях

(2)

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

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

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

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

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

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

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

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

1) Взаимоисключение. Пусть x_j = 1, если реализуется проект А _j, и х _j = 0 в противном случае. Запись A_jÚA_k означает, что в план может быть включен либо проект А _j, либо проект А _k. Вместе они включены быть не могут. С помощью этой записи выражается от­ношение взаимоисключения между проектами.

В этих обозначениях взаимоисключение A_j Ú А _k выражается неравенством х _j + х _k £ 1;

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

В принятых обозначениях А _k ® А _j вы­ражается неравенством х _k £ х _j.