Основы теории систем и системного анализа. Матвеев Ю.Н. - 73 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

73
оптимальном решении равны нулю не две, а больше переменных. Это
случай ОЗЛП называется вырожденным.
6.
Интуитивно понятно, что для поиска оптимального решения
ОЗЛП необходимо проанализировать опорные решения (опорные точки
ОДР) и выбрать из них то, где линейная функция W достигнет минимума.
Подобные выводы можно сделать для любых количеств переменных
ЗЛП и уравнений-ограничений при условии m<n.
Оптимальное решение, если оно существует, находится не внутри, а
на
границе ОДР, в одной из опорных точек. В каждой опорной точке не
менее
k
переменных (k = n – m) ЗЛП равны нулю.
Для ускорения процедуры отыскания оптимального решения
необходимо отыскать сначала опорные точки (опорные решения) и,
целенаправленно анализируя эти опорные решения, определить минимум
целевой функции W.
2.5. Задача линейного программирования с ограничениями-
неравенствами. Переход к ОЗЛП и обратно [10]
В большинстве практических задач ЛП ограничения заданы не
уравнениями, а неравенствами. Переход от ЗЛП общего вида к ОЗЛП
осуществляется следующим образом.
Пусть имеется ЗЛП с
j
x , nj ,1= переменными. Ограничения задачи
ЛП имеют вид линейных неравенств. Знаки неравенств могут быть как ≥,
так и ≤.
Зададим все ограничения неравенства в стандартной форме записи:
⎪
⎪
⎩
⎪
⎪
⎨
⎧
≥+++
≥+++
≥+++
.
2211
,
22222121
11212111
....
..............................................
...
,...
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
(2.28)
Считаем, что все неравенства линейно независимы, т.е. никакое из
них нельзя представить в виде линейной комбинации других. Требуется
найти такую неотрицательную совокупность значений x
1
, x
2
, …¸x
n
, которая
удовлетворяла бы неравенствам системы (13) и, кроме того, обращала бы в
минимум линейную функцию
nn
xcxcxcW
+
+
+
= ....
2211
.
От поставленной таким образом ЗЛП легко перейти к ОЗЛП.
Перепишем систему (2.28) в виде
⎪
⎪
⎩
⎪
⎪
⎨
⎧
++++=
++++=
++++=
,...
.....................................................
,...
...
2211
222221212
,
112121111
mnmnmmm
nn
nn
bxaxaxay
bxaxaxay
bxaxaxay
(2.29)

Страницы