Исследование операций. Линейное, динамическое программирование



Исследование операций - часть 45


/p>

2. Задача о планировании производства. Предприятие производит изделия трех видов: U1, U2, U3. По каждому виду изделия предприятию спущен план, по которому оно обязано выпустить не менее b1 единиц изделия

U1, не менее b2 единиц изделия U2 и не менее b3 единиц изделия U3. План может быть перевыполнен, но в определенных границах; условия спроса ограничивают количества произведенных единиц каждого типа: не более соответственно

 единиц. На изготовление изделий идет какое-то сырье; всего имеется четыре вида сырья: s1, s2, s3, s4, причем запасы ограничены числами
 единиц каждого вида сырья. Теперь надо указать, какое количество сырья каждого вида идет на изготовление каждого вида изделий. Обозначим aij количество единиц сырья вида si (j = l, 2, 3, 4), потребное на изготовление одной единицы изделия Uj (j = 1, 2, 3). Первый индекс у числа aij — вид изделия, второй — вид сырья. Значения aij сведены в таблицу (матрицу) — см. таблицу 7.2.

При реализации одно изделие U1 приносит предприятию прибыль c1, U2 — прибыль c2, U3 — прибыль c3. Требуется так спланировать производство (сколько каких изделий производить), чтобы план был выполнен или перевыполнен (но при отсутствии «затоваривания»), а суммарная прибыль обращалась в максимум.

Запишем задачу в форме задачи линейного программирования. Элементами решения будут x1, x2, x3, — количества единиц изделий U1, U2, U3, которые мы произведем. Обязательность выполнения планового задания запишется в виде трех ограничений-неравенств:

x1 .

 b1,   x2
 b2,   x3 
 b3            (7.4)

Отсутствие излишней продукции (затоваривания) даст нам еще три ограничения-неравенства:

          (7.5)

Кроме того, нам должно хватить сырья. Соответственно четырем видам сырья будем иметь четыре ограничения-неравенства:

           (7.6)

Прибыль, приносимая планом (x1, x2, x3) ,

будет равна

L = c1x1 + c2x2 + c3x3.              (7.7)

Таким образом, мы снова получили задачу линейного программирования: найти (подобрать) такие неотрицательные значения переменных x1, x2, x3, чтобы они удовлетворяли неравенствам-ограничениям (7.4), (7.5), (7.6) и, вместе с тем, обращали в максимум линейную функцию этих переменных:




Содержание  Назад  Вперед