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



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


Требуется составить такой пищевой рацион (т. е. назначить количества продуктов П1, П2, П3, П4, входящих в него), чтобы условия по белкам, углеводам и жирам были выполнены и при этом стоимость рациона была минимальна.

Таблица 7.1

Продукт

Элементы

белки

углеводы

Жиры

П1

П2

П3

П4

а11

а21

а31

а41

а12

а22

а32

а42

а13

а23

а33

а43

Составим математическую модель (в данном случае это очень просто).  Обозначим х1, х2, x3, x4 количества продуктов П1, П2, П3, П4, входящих в рацион. Показатель эффективности, который требуется   минимизировать,— стоимость рациона (обозначим ее L); она линейно зависит от элементов решения х1, х2, x3,, x4:

L = c1x1+c2x2+c3x3+c4x4,

или, короче,

L =

                     (7.2)

Итак, вид целевой функции известен и она линейна. Запишем теперь в виде формул ограничительные условия по белкам, углеводам и жирам. Учитывая, что в одной единице продукта П1 содержится а11

единиц белка, в х1

единицах—а11 х1

единиц белка, в х2

единицах продукта П2 содержится а21

х2 единиц белка и т. д., получим три неравенства:

               (7.3)

Эти линейные неравенства представляют собой ограничения, накладываемые на элементы решения x1, x2, x3, x4,.

1) Разумеется, мы могли бы для «оживления» материала задать как числа b1, b2, b3,, так и числа аij вполне конкретными значениями, но это все равно не создало бы у читателя впечатления, что автор — специалист по откорму скота.

 

 

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

L ==

Перед нами — типичная задача линейного программирования. Не останавливаясь покуда на способах ее решения, приведем еще три примера аналогичных задач.

Таблица 7.2

Сырьё

Изделия

U1

U2

U3

s1

s2

s3

s4

а11

а12

а13

а14

а21

а22

а23

а24

а31

а32

а33

а34

<


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