Численные методы оптимизации. Рейзлин В.И. - 58 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

58
других решений вообще нет. Если же среди чисел
0
i
x
имеется хотя бы одно от-
рицательное, то задача не имеет решения.
Таким образом, интерес представляет лишь случай
rn
, и только он бу-
дет нами рассматриваться в дальнейшем.
Каждую задача линейного программирования можно свести к форме ос-
новной задачи. Для этого нужно:
1. Уметь сводить задачу максимизации к задаче минимизации.
2. Уметь переходить от ограничений, заданных в виде неравенств, к неко-
торым им эквивалентным ограничениям-равенствам.
Покажем, как это сделать.
1. Очевидно, что форма
F
достигает наибольшей величины при тех же
самых значениях неизвестных
00
1
,...,
n
xx
, при которых форма
1
FF
достигает
наименьшей величины. Следовательно, максимизация формы
F
равносильна
минимизации формы
1
FF
. Тем самым задача максимизации сводится к зада-
че минимизации.
2. Допустим теперь, что среди ограничений задачи имеется некоторое не-
равенство. Его всегда можно записать в виде
1 1 2 2
... 0
nn
x x x
. (7.12)
Введем новую, так называемую добавочную, неизвестную, связанную с
неизвестными
1
,...,
n
xx
уравнением
1 1 1
...
n n n
x x x
. (7.13)
Очевидно, что условие неотрицательности величины
эквивалентно
выполнимости неравенства (7.12). Иными словами, если система
0 0 0
11
,..., ,
nn
x x x
неотрицательных значений
11
,..., ,
nn
x x x
удовлетворяет уравнению (7.13), то си-
стема
00
1
,...,
n
xx
удовлетворяет неравенству (7.12). И обратно, если величины
00
1
,...,
n
xx
неотрицательны и удовлетворяют неравенству (7.12), то величина
1 1 1
...
n n n
x x x
, найденная из уравнения (7.13), окажется неотрицатель-
ной.
Итак, ограничение-наравенство (7.12) эквивалентно ограничению-
равенству (7.13). Следовательно, ценою введения в задачу добавочных неизвест-
ных удается все ограничения-неравенства заменить ограничениями-равенствами.
При этом число добавочных неизвестных равно числу ограничений-неравенств в
исходной задаче.
Посмотрим, какой вид примут рассмотренные выше задачи после сведения
их к основной.

Страницы