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

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

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

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

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

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

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

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

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

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

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

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

Задачи (1) и (2), в которые переменные x_j входят в первой степени, т.е. в виде линейных зависимостей, называют задачами ЛП.

Каждая задача ЛП содержит ЦФ (1.1), (2.1), ограничения (1.2), (2.2), граничные условия (1.3),(2.3). Ограничения могут включать зависимости как для ресурсов (b_j ), так и для экономических показателей (С).

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

Контрольные задания

1. В таблице приведены нормы затрат сырья, цены на сырьё и на изделия, а также ограничения по закупке сырья. Требуется определить план производства продукции с целью минимизировать затраты ресурсов.

Тип сырья	Цена 1 кг сырья (р.)	Нормы затрат сырья на одно изделие (кг)			Ограничения по закупке сырья (кг)
		А	В	С
I II III	2 1 2	1 4 6	3 1 5	4 3 2	3000 – 3320
Цена одно изделия (р.)		24	32	27

2. Цех может производить стулья и столы. На производство стула идет 5 единиц материала, на производство стола - 20 единиц (футов красного дерева). Стул требует 10 человеко-часов, стол - 15. Имеется 400 единиц материала и 450 человеко-часов. Прибыль при производстве стула - 45 долларов США, при производстве стола - 80 долларов США. Сколько надо сделать стульев и столов, чтобы получить максимальную прибыль?