Математические методы принятия решений. Бодров В.И - 47 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Рис. 4.5 Геометри-
ческое представле-
ние сведения огра-
ничений типа
неравенств к огра-
ничениям типа ра-
венств
u
2
1
a
b
u
3
> 0
u
3
< 0
1
a
b
u
3
= 0
u
1
Полученная каноническая задача
max)(
1211
→
+
=
uCuCuQ при ограничениях
0,0,0,
32132211
≥≥≥=++ uuubuuaua является равноценной задачей по отношению к исходной.
4.5 СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Основным методом решения задач линейного программирования является симплексный метод. Для
его изложения необходимо ввести некоторые определения.
Переменные (u
1
, u
2
, ..., u
n
), удовлетворяющие условиям (4.2) – (4.4) общей задачи линейного про-
граммирования называются планом задачи линейного программирования.
План (u
1
, u
2
, ..., u
n
) = U называется опорным, если в разложении
ι
=ι
ι
ρ=
∑
n
uP
1
0
при
ιι
ρ
> ,0u – линейно
независимы.
План, максимизирующий линейный критерий оптимальности (4.1) называется оптимальным пла-
ном или решением задачи линейного программирования.
В теории линейного программирования строго доказывается [2], что множество всех планов задачи
линейного программирования выпукло. Критерий оптимальности (4.1) достигает своего максимума в
крайней точке этой выпуклой области.
Каждой крайней точке выпуклой области соответствует m линейно независимых векторов из систе-
мы ρ
1
, ρ
2
, ..., ρ
n
.
Симплексный метод позволяет, отталкиваясь от известного опорного плана задачи линейного про-
граммирования, за конечное число итераций получить ее решение. Так как оптимальный план связан с
системой m линейно независимых векторов – базисами плана, то поиски разумно ограничить опорными
планами, число которых конечно и равно числу сочетаний из n по m
.
!
!
m
n
C
m
n
= Как видно, при больших
значениях m и n отыскать решение путем перебора всех опорных планов невозможно. Симплексный ме-
тод упорядочивает переход от одного опорного плана к другому таким образом, чтобы критерий опти-
мальности принимал значение большее или равное предыдущему. Суть алгоритма симплексного метода
сводится к следующему.
1 Определяется некоторый опорный план, которому соответствует вершина области допустимых
решений (
n
uuu ...,,,
21
).
2 Найденный опорный план (вершина) проверяется на оптимальность. Пусть этот план не оптима-
лен.
3 Определяется следующий опорный план (вершина) лучший по отношению к предыдущему в ре-
зультате движения по ребру. Найденная таким образом вершина проверяется на оптимальность.
4 Процесс поиска продолжается до тех пор, пока не будет найдена оптимальная вершина, т.е. ре-
шение задачи линейного программирования.
Использование симплексного метода удобно рассматривать на примере решения задачи линейного
программирования для случая двух переменных.
Пусть требуется изготовить два продукта из четырех видов сырья – S
1
, S
2
, S
3
, S
4
. Требуется опреде-
лить сколько должно быть изготовлено продукта П
1
– u
1
, продукта П
2
– u
2
, чтобы стоимость их (при-

Страницы