Материал: Методы оптимизации в примерах и задачах. Медведь Н.А., Фокин А.А

sup cxT

,

1

даже если задача (5.2.1) разрешима).

Так как функции

fi (x)

выпуклы вниз, справедливо

неравенство

f

(x)

f

(x0 )

f

(x0 )(x x0 )T b .

i

i

i

i

Следовательно

1. . Пусть x1 - решение задачи (5.2.2).

тогда

f

i

(x1 )

f

i

(x1 )(x x1 )T

b , i :{ f

i

(x1 ) b }

.

i

i

Эти ограничения обладают следующими свойствами:

a) Точка

x1

не удовлетворяет этим ограничениям;

b) во всех точках множества

они выполняются.

Таким образом,

получаем

новое

множество

2

, такое

что

2

1. Далее итерационный процесс повторяется.

Доказано,

что

генерируемая

таким

образом

последовательность

Шаг 1. Задать x0

(не обязательно допустимое),

(точность

попадания в допустимую область).

Шаг 2.

Положить k 1

____

1

{x : f

i

(x0 )

f

(x0 )(x

x0 )T b , i=1,m}.

i

i

Шаг 3.

Найти xk - решение задачи линейного

программирования

cxT

max

x

k .

Шаг 4.

Если

i : f

(xk )

b

, то останов x* xk .

i

i

Шаг 5.

Положить

л 1

k

{x : f

i

(xk )

f

(xk )(x xk )T

b ,

i

i

i : f

(xk )

b };

i

i

0.92

( 2; 5.24)(x

2.97; x

2

2.62)T

15

1

12.3

(4.75; 2)(x

2.97; x

2

2.62)T

9

1

Добавляем эти ограничения к задаче линейного

программирования

и

находим

следующее

решение

(x)

x1

x2

max

f (x)

x

2

x2

9.

1

1

2

Решение.

Выберем

x0

(2, 3).

Вычислим

f1 (x)

(2x1; 2x2 ). Тогда

f (x)

13 (4;6)(x

2; x

3)T

4x

6x

13.

1

1

2

1

2

Решим графически задачу линейного программирования:

x1

x2

max

1 :

4x1

6x2

22.

функции допустимое множество не ограничено, sup (x)

,

1

т.е. ЗЛП решения не имеет. Однако исходная задача разрешима,

x*

3

,

3

.

2

2

Этот

пример

иллюстрирует

существенность

требования

ограниченности множества

1.

xk нелинейной функции f (x)

линейной функцией c xT . . Из

k

формулы Тейлора следует, что

f (x) f (x k )

f (x k )(x x k )T .