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

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

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

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

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

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

(1)

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

(2)

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

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

(3)

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

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

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

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

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

(4)

(5), (6)

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

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

(7)

(8), (9), (10), (11)

где С - минимально допустимое значение потребного ре­зультата.

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

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

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

Поиск по сайту: