Постановка задачи линейного программирования. Значительная часть задач принятия решения – это задачи распределения ресурсов между объектами

Значительная часть задач принятия решения – это задачи распределения ресурсов между объектами.

Пусть имеется m видов ресурсов. Наличие каждого i -го вида ресурса составляет b_i (i = 1.. m) в соответствующих единицах измерения. Эти ресурсы предназначены для производства n видов продукции. Для выпуска единицы j -го вида продукции необходимо a_ij единиц i -го вида ресурса. Требуется определить, какого вида и сколько продукции следует произвести, чтобы такой выпуск был наилучшим для принятого критерия оптимальности.

Обозначим через x_j количество выпускаемой j -го вида продукции. Тогда для i -го вида ресурса можно записать

где левая часть неравенства выражает потребность в ресурсе i -го вида, правая – располагаемое количество этого ресурса.

Распространяя на m видов ресурсов, это ограничение можно записать

Если номенклатуру продукции ограничить предельными значениями объемов производства и продаж, то запишутся следующие граничные условия

где – соответственно минимально – и максимально – допустимые объемы производства и продаж продукции j -го вида.

В зависимость (1) можно ввести дополнительные переменные. Тогда

В реальных задачах суммарное количество основных x_i (j = 1.. n) и дополнительных y_i (i = 1.. m) переменных всегда больше, чем число зависимостей m, поэтому система (1) имеет бесчисленное множество решений. Из этого бесчисленного множества следует выбрать одно – оптимальное, соответствующее критерию – цели решения задачи.

Цель задачи распределения ресурсов устанавливается какой–либо одной из двух взаимоисключающих постановок:

1) при заданных ресурсах максимизировать получаемый результат;

2) при заданном результате минимизировать потребные ресурсы.

Первая постановка аналитически запишется:

где x_j – количество выпускаемой продукции j -го вида – искомая переменная (j = 1.. n); n – количество наименований продукции; c_j – величина, показывающая, какой вклад в результат дает единица продукции j -го вида; b_i – заданное количество ресурса i -го вида (i = 1.. m); m – количество наименований ресурсов; a_ij – норма расхода ресурса, то есть какое количество ресурса i -го вида потребляется на производство единицы j -го вида продукции.

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

Вторая постановка задачи будет иметь вид:

где C – минимально допустимое значение потребного результата.

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

Каждая задача линейного программирования содержит целевую функцию (4) или (7), ограничения (5), (6) или (8)–(10), граничные условия (6) или (10), (11). Ограничения могут включать зависимости как для ресурсов (b_i), так и для экономических показателей (C).

Для решения задач линейного программирования используют графический и аналитический методы.