Составители:
Рисунок 9.9 Область допустимых решений
При дальнейшем параллельном переносе этой прямой вверх можем попасть в точку D (опорная прямая l
2
) и
получить максимум целевой функции.
4.4 Симплекс-метод. Рассмотренный геометрический метод решения задач линейного программирования
достаточно прост и нагляден для случая двух и даже трех переменных. Для большего числа переменных
применение геометрического метода становится невозможным.
Правда, мы видели, что оптимальные значения целевой функции достигаются на границе области допустимых
решений. Поэтому в случае п неизвестных (п > 3) можно построить n-мерный многогранник решений, найти
его вершины и вычислить значения целевой функции в этих точках. Наименьшее среди полученных значений
можно принять за искомое, а координаты соответствую щей вершины — за оптимальные значения проектных
параметров.
Однако решение задачи линейного программирования не так просто, как может показаться на первый взгляд.
Сложность состоит в том, что количество проектных параметров в реальных задачах (особенно в экономиче-
ских) может достигать сотен и даже тысяч. При этом число вершин многогранника G может быть настолько
большим, что перебор вершин и вычисление в них значений целевой функции приведет к такому объему вы-
числений, который практически невозможно осуществить в течение разумного времени даже с помощью
ЭВМ.
Одним из методов, позволяющих эффективно решать подобные задачи, причем с гораздо меньшим числом
операций, является симплекс-метод.
Симплексом называется простейший выпуклый многогранник при данном числе измерений. В частности, при
п = 2 — произвольный треугольник, п = 3 — произвольный тетраэдр.
Идея симплекс-метода состоит в следующем. Примем в качестве начального приближения координаты
некоторой вершины многогранника допустимых решений и найдем все ребра, выходящие из этой вершины.
Двигаемся вдоль того ребра, по которому линейная целевая функция убывает. Приходим в новую вершину,
находим все выходящие из нее ребра, двигаемся по одному из них и т. д. В конце концов мы придем в такую
вершину, движение из которой вдоль любого ребра приведет к возрастанию целевой функции. Следовательно,
минимум достигнут, и координаты этой последней вершины принимаются в качестве оптимальных значений
рассматриваемых проектных параметров.
Отметим, что (поскольку f — линейная функция, а многогранник выпуклый) данный вычислительный про-
цесс сходится к решению задачи, причем за конечное число шагов k. В данном случае их число порядка п, т. е.
значительно меньше числа шагов в методе простого перебора вершин, где k может быть порядка 2
n
.
Пусть задача линейного программирования состоит в том, что нужно найти такие неотрицательные значения
проектных параметров x
1
, х
2
, ..., х
п
, которые минимизируют линейную целевую функцию при заданных
ограничениях в виде системы линейных уравнений
;...
............................................
,...
,...
2211
22222121
11212111
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
=+++
=+++
=
+
+
+
(9.29)
Если в качестве ограничений заданы неравенства, то их можно преобразовать в равенства путем введения до-
полнительных неотрицательных переменных, которые называются балансовыми. Например, имея некоторое
неравенство bxaxaxa
nn
≤
+++ ...
2211
, можно всегда ввести новую переменную x
n+1
> 0 такую, что после
ее прибавления к левой части данного неравенства получим равенство a
1
x
1
+ а
2
х
г
+ ... + а
п
х
п
+ х
п+1
= b.
Будем считать, что все уравнения, системы 9.29 линейно независимы, т. е. ни одно из них нельзя получить как
линейную комбинацию других. В противном случае линейно зависимые уравнения можем отбросить. И кроме
того, эта система совместна, т. е. среди уравнений системы нет противоречивых. Ясно, что при этих
предположениях число уравнений m меньше числа переменных п, поскольку при т = п система 9.29 имеет
единственное решение, что исключает всякую оптимизацию; при m > n не выполняются сделанные выше
предположения.
Страницы
- « первая
- ‹ предыдущая
- …
- 141
- 142
- 143
- 144
- 145
- …
- следующая ›
- последняя »
