Составители:
Рубрика:
84
канонических задач линейного программирования. Вычислить все опорные решения
системы уравнений (2.2.82). Затем подсчитать значение целевой функции (2.2.81) для
каждого из опорных решений. Опорное решение, соответствующее наибольшему (или
наименьшему) значению целевой функции будет оптимальным решением задачи. Однако
при сколько-нибудь значительных величинах m и n намеченный путь решения может
оказаться практически неприемлемым. Например, если допустить, что решение задачи
при m=25 и n=50 осуществляется машиной с быстродействием 10
5
операций в секунду, то
для определения оптимального решения понадобится примерно миллион лет.*
Однако, несмотря на практическую неприемлемость метода, основанного на
просмотре всех опорных решений, сама идея анализа опорных решений оказывается
плодотворной. Все конечные методы решения задач линейного программирования в той
или иной мере связаны с перебором опорных решений. Но этот перебор осуществляется
таким образом, что для решения задачи требуется просмотреть лишь относительно малую
часть всех опорных решений. Это достигается за счет упорядоченности перебора, в том
смысле, что каждый переход осуществляется к «лучшему» опорному решению, и наличия
критерия, позволяющего установить оптимальность или неоптимальность каждого
опорного решения. Каждому конечному методу линейного программирования
соответствует свой метод упорядочения перебора и свой критерий окончания перебора.
2.2.4 Геометрическая интерпретация линейного
программирования
Геометрический смысл простейших задач линейного программирования
Допустим, что в некоторой задаче линейного программирования, в которой
требуется найти значения n неотрицательных переменных x, y, x
3
,x
4
,…,x
n
,
максимизирующих ( или минимизирующих) целевую функцию
,...
33221 nn
xcxcycxcz ++++= (2.2.88)
в системе ее ограничений содержится n-2 уравнений:
=++++
=++++
=++++
−−−−−
....
....................................................
;...
;...
2,233,22,21,2
223232221
113131211
nnnnnnn
nn
nn
bxaxayaxa
bxaxayaxa
bxaxayaxa
(2.2.89)
Предположим, что система линейных уравнений (2.2.89) разрешима относительно
переменных x
3
,x
4
,…,x
n
при любых допустимых значениях x и y. Тогда переменные
x
3
,x
4
,…,x
n
могут быть выражены линейно через две переменные – х и y, т.е.
++=
++=
++=
.
..............................
;
;
321
4342414
3332313
nnnn
yxx
yxx
yxx
γγγ
γγγ
γγγ
(2.2.90)
Подставляя выражения (2.2.90) вместо переменных, x
3
,x
4
,…,x
n
в ограничения-
неравенства (если таковые в задаче содержатся) и в условия неотрицательности
переменных
,0;...;0;0
43
≥≥≥
n
xxx (2.2.91)
Страницы
- « первая
- ‹ предыдущая
- …
- 82
- 83
- 84
- 85
- 86
- …
- следующая ›
- последняя »
