Постановка задачи целочисленного линейного программирования

I. Теоретическая часть

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

Задача линейного целочисленного программирования формулируется следующим образом:

вычислить такое решение (план) Х* = (х*₁, х*₂, …, х*_n,), при котором линейная функция

(17.1)

принимает максимальное или минимальное значение при ограничениях

, (17.2)

, (17.3)

x_j - целые числа. (17.4)

Определение 17.1. Целой частью числа f_i называют наибольшее целое число, не превосходящее f_i. Обозначим:

[f_i ] – целая часть числа f_i;

{ f_i } – дробная часть числа f_i..

Дробная часть числа вычисляется следующим образом: { f_i } = f_i - [f_i ].

Примеры. ;

;

;

.

Следует отметить, что классическая транспортная задача и некоторые другие задачи транспортного типа «автоматически» обеспечивают решение задачи в целых числах (если, конечно, целочисленны параметры условий).

В общем случае ус­ловие целочисленности (17.4), добавляемое к обычным задачам линейного программирования, существенно усложняет ее ре­шение.

Для решения задач линейного целочисленноro программи­рования используется ряд методов. Самый простой из них ­обычный метод линейного программирования. В случае если компоненты оптимального решения оказываются нецелочис­ленными, их округляют до ближайших целых чисел. Этот ме­тод применяют тогда, когда отдельная единица совокупности составляет незначительную часть объема всей совокупности. В против­ном случае округление может привести далеко не к опти­мальному целочисленному решению, поэтому используют спе­циально разработанные методы.

Методы целочисленной оптимизации делят на три группы:

а) методы отсечения;

б) комбинаторные методы;

в) приближенные методы. Остановимся подробнее на методах отсечения.