Симплексный метод линейного программирования

103 
Общую задачу линейного программирования приводят к канониче-
ской форме путем введения дополнительных переменных 
x
n
+1 
≥ 0 (
i
= l, 
k
) и 
x
n
+1 
≤ 0 (
i
= 1, 
e
).
Тогда неравенства (4.8) приобретут вид равенств:
d
i
1
x
1 
+ 
d
i
2
x
2 
+ …+ 
d
in
x
n
+ 
x
n
+1 
= 
e
i
; (
i
= 1, 
k
)
f
i
1
x
1 
+ 
f
i
2
x
2 
+ … + 
f
in
x
n
+ 
x
n
+1 
= 
h
i
. (
i
= 1, 
e
)
Общая схема решения задач линейного программирования сим-
плексным методом показана на рис 4.11. Она состоит из пяти этапов.
1. Определение ранга матрицы, образованной коэффициентами и 
свободными членами. Если ранг матрицы 
А
меньше 
m
строк, можно отбро-
сить линейно зависимые строки: число оставленных в матрице строк 
должно равняться ее рангу
. 
Рис. 4.11. Схема решения задачи линейного программирования симплекс-методом 
2. Переменные 
x
1
; 
x
2
, …, 
x
n
разбиваются на две группы: первая со-
держит 
m
базисных переменных, вторая 
n − m
свободных переменных. 
Пусть 
x
1
,… 
x
m
базисные, 
x
m
+1
,…, 
x
n
свободные переменные. Базисные пе-
ременные выражаются через свободные: 
(4.9) 
Составление 
оптимизационной 
модели 
Электронный
архив
УГЛТУ

104 
=
+ (
+
+ ⋯ +
)
=
+ (
+
+ ⋯ +
) (4.10)
..........................................................................
=
+ (
+
+ ⋯ +
)
. 
Если все числа 
β
1
,
β
2
,..., 
β
m
 
неотрицательные, то разбиение перемен-
ных на базисные и свободные произведено правильно.
Приняв 
x
i
= 
β
для 
i
= 1, 2,…, 
m
; 
x
i
 
= 0 для 
i = m
+ 1, 
m
+ 2,…, 
n
, полу-
чаем допустимое решение. Если же среди чисел
β
1
,
β
2
,...,
β
n
есть отрица-
тельные, то разбиение переменных на базисные и свободные произведено 
неправильно и необходимо в качестве базисных и свободных взять другие 
переменные. 
3. Подставив в целевую функцию значение базисных переменных 
(4.10), получим выражение целевой функции через свободные переменные:
=
+
+ ⋯ +
, (4.11)
где 
γ
– значение целевой функции при выбранном первом допустимом ре-
шении. 
Если все числа
+ ⋯ +
неотрицательные, то выбранное до-
пустимое решение является оптимальным.
4. Если среди чисел
+ ⋯ +
есть отрицательные и числа
α
lk
, ..., 
α
mk
 
все положительные, то оптимального решения не существует. 
Если же среди этих чисел есть отрицательные, то для нахождения второго 
решения в базисную переводятся другие свободные переменные, а одна из 
базисных переменных – в свободную группу.
5. Находится второе допустимое решение целевой функции. Вновь 
полученные базисные переменные выражаются через свободные, и итера-
ционный процесс продолжается. За конечное число этапов находится оп-
тимальное решение либо делается вывод, что оно не существует.
Задача оптимизации может быть представлена в матричном виде.
Оптимизировать 
Z = cx
при ограничениях
Ax = b, х ≥ 
0
, b ≥ 
0
,
 
где 
А
– матрица размерности 
m 

 n
(матрица коэффициентов);
x
– вектор-столбец размерности 

жүктеу/скачать 6,77 Mb.

Достарыңызбен бөлісу: