Составители:
;...
............................................
,...
,...
2211
22222121
11212111
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
=+++
=+++
=
+
+
+
(9.15)
2) являются неотрицательными, т. е.
;0 ..., ,0 ,0
21
≥≥≥
n
xxx (9.16)
3) обеспечивают наименьшее значение линейной целевой функции
....),...,,(
2211021 nnn
xcxcxccxxxf +
+
+
+
=
(9.17)
Всякое решение системы уравнений 9.15, удовлетворяющее системе неравенств (9.16), называется допусти-
мым решением. Допустимое решение, которое минимизирует целевую функцию (9.17), называется
оптимальным решением.
Рассмотрим пример задачи линейного программирования (транспортную задачу).
ПРИМЕР. Автобаза обслуживает три овощных магазина, причем товар доставляется в магазины из двух
плодоовощных баз. Нужно спланировать перевозки так, чтобы их общая стоимость была минимальной.
Введем исходные данные. Ежедневно вывозится с первой базы 12 т товара, со второй 15 т. При этом завозится
в первый магазин 8 т, во второй 9 т, в третий 10 т. Стоимость перевозки 1 т товара (в рублях) с баз в магазины
дается следующей таблицей:
Магазин
База
первый второй третий
Первая
Вторая
0.80
1.00
1.10
0.70
0.90
1.20
Решение. Обозначим через х
1
, х
2
, х
3
количество товара, который нужно доставить с первой базы соответ-
ственно в первый, второй и третий магазины, а через x
4
, x
5
, x
6
количество товара, который нужно доставить со
второй базы в те же магазины. Эти значения в соответствии с исходными данными должны удовлетворять
следующим условиям:
.10
,9
,8
,15
,12
63
52
41
654
321
=+
=+
=+
=++
=
+
+
xx
xx
xx
xxx
xxx
(9.18)
Первые два уравнения этой системы описывают количество товара, которое необходимо вывезти с первой и
второй баз, а три последних — сколько нужно завезти товара в каждый магазин.
К данной системе уравнений нужно добавить систему неравенств
6, ..., 2, 1, ,0
=
≥ ix
i
(9.19)
которая означает, что товар обратно с магазинов на базы не вывозится. Общая стоимость перевозок с учетом
приведенных в таблице расценок выразится формулой
.2.17.09.01.18.0
654321
xxxxxxf +
+
+
+
+
=
(9.20)
Таким образом, мы пришли к типичной задаче линейного программирования: найти оптимальные значения
проектных параметров х
i
(i = 1, 2, ..., 6), удовлетворяющих условиям (9.18), (9.19) и минимизирующих общую
стоимость перевозок (9.20).
Из анализа системы уравнений (9.18) следует, что только первые четыре уравнения являются независимыми, а
последнее можно получить из них (путем сложения первого и второго уравнений и вычитания из этой суммы
третьего и четвертого уравнений). Поэтому фактически имеем систему
.9
,8
,15
,12
52
41
654
321
=+
=+
=++
=
+
+
xx
xx
xxx
xxx
(9.21)
Число неизвестных на два больше числа уравнений, поэтому выразим через x
1
и х
2
все остальные неизвестные.
Получим
Страницы
- « первая
- ‹ предыдущая
- …
- 138
- 139
- 140
- 141
- 142
- …
- следующая ›
- последняя »
