Имя материала: Справочник по математике для экономистов

Автор: В.И. Ермаков

9.2. задачи линейного программирования

Оптимизационная задача (V, /, Q), в которой целевая функция является линейной функцией на V= R", ail - множеством решений некоторой системы линейных уравнений и линейных неравенств от п неизвестных, называется задачей линейного программирования. При этом система линейных уравнений и линейных неравенств, определяющая допустимое множество Q, называется системой ограничений задачи линейного программирования.

Задача линейного программирования будет поставлена, если:

л

а)       указана линейная целевая функция / = ^ДуХу-;

7=1

б)       записана система ограничений

л

Y,ayxj = ьі> ієі>1 £ м = ft2>w}>

7=1 л

< bt, і є МІ,

7=1

xj>0,  jeJ,  /<=уУ = {1,2,...,и}

221

(часто бывает полезно в системе ограничений особо выделить неравенства вида х}. > 0);

в) определено, к какому типу (максимизации или минимизации) принадлежит данная задача. (Задачу максимизации всегда можно свести к задаче минимизации, поменяв знаки у коэффициентов целевой функции.)

Любую задачу линейного программирования можно записать в следующем виде:

 

У=1

Y^ai]xj = А>  1 є 7> / е М = {1,2,тп),

/=1

Xj > 0.

п

 

jsJ,  J^N = {l,2,...,n}.

(9.1)

 

(9.2)

(9.3) (9.4)

В частности, если /= 0, то система (9.2), (9.3) состоит только из линейных неравенств, если же I-М, то только из линейных уравнений.

Матрица^ размера тхп,у которой на месте (/,/") стоит коэффициент при Xj в і-м ограничении системы (9.2), (9.3), т.е.

ГаП     «12    - аЫЛ

А =

*21

*22

<hn

 

 

 

 

222

В =

 

 

.bmJ

Свойства задач линейного программирования:

Г. Допустимое множество задачи линейного программирования либо пусто, либо является выпуклым подмножеством пространства R".

2°. Если допустимое множество задачи линейного программирования не пусто, а целевая функция ограничена снизу (для задачи минимизации) на этом множестве, то задача линейного программирования имеет оптимальное решение.

3°. Оптимальные решения задачи линейного программирования (если они существуют) всегда находятся на границе допустимого множества и образуют выпуклое подмножество пространства R".

Рассмотрим примеры экономических задач, приводимых к задаче линейного программирования.

Задача о рационе. В хозяйстве имеется и видов кормов, каждый из которых содержит т разновидностей питательных веществ. Известно, что одна единицау'-го вида кормов (J - 1, 2, п) содержит atj. единиц г-го питательного вещества (і - 1, 2, т) и имеет стоимость е.. Требуется составить такой рацион, который бы удовлетворил всем потребностям Ь. (і - 1, 2,т) в питательных веществах и имел наименьшую стоимость.

Обозначим количество у'-го корма в рационе х„ х. > О (j - 1,

У=1

Рацион должен удовлетворять всем потребностям в питательных веществах. Значит,

У=1

Таким образом, мы получим задачу линейного программирования:

л

 

223

Простейшая задача планирования производства. Предприятие располагает т видами ресурсов и может выпускать некоторую однородную продукцию я различными технологическими способами. За единицу времени использованияу'-го технологического способа (у = 1, 2, л) расходуется a(j. единиц г'-го ресурса (/ = 1, 2, т) и выпускается Cj единиц продукции. Требуется спланировать работу предприятия так, чтобы оно выпускало наибольшее количество продукции при условии, что ресурса г'-го вида нельзя израсходовать более чем bi единиц (/ = 1, 2,т).

Пусть х}., Xj > О (у = 1, 2,..., я) — время использования предприятием у'-го технологического процесса. Если при этом /— количество ВЫПущеННОЙ ПРОДУКЦИИ, ТО / = ^CjXj.

j=l п

Для выпуска продукции предприятие израсходует ^ciyXj еди-ницг'-горесурса. Значит, 2^ayXj <bt,  і = 1,2,...,т.

Итак, мы снова имеем задачу линейного программирования:

л

/ = Х^хДтах),

л

^ayXj^bj, і = 1,2,...,/я,

7=1

Х;>0,        у = 1,2,..., я.

Важным примером задачи линейного программирования является транспортная задача (см. п. 9.12).

 

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 | 101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 | 126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 | 151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 | 176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 |