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

n

ij x j

xn i

i ,

i 1, m

j 1

(5.1.3)

x j

0,

j

1, n

m

j x j

0,

j 1, n

i xn i

0 i 1, m,

i

0,

i

1, m,

j

0, j

1, n .

Решение

(x1, x2 ,...,xn+m , 1,...,

m ,

1,..., n )

данной системы

n m линейных

уравнений

содержит,

по крайней

мере n

m

нулевых координат.

Задачу нахождения

решения системы

без

____

____

условий i xn i

0,

i=1,m и

j xj

0,

j=1,n

можно свести к

z1 z2

...

z n

z n 1

...

z n m

min

n q ij x j

n

i

ij

j

z j

b j , j 1, n

i 1

i 1

n

ij x j

x n i

z n i

i , i 1, m

j 1

x j

0, z j

0

j

1, n

m

i

0,

i

1, m,

j

0,

j

1, n .

При реализации метода искусственного базиса следует

учитывать условия

_____

____

ш xn i

0,

i=1,m,

j xj

0,

j=1,n,

т.е. не включать в базисные переменные одновременно

i и xn i с

одним и тем же номером i

и переменные

j

и xj с одинаковым

номером j .

Пример. Решить задачу квадратичного программирования:

x 2

2x x

2

2x 2

2x

6x

2

min

1

1

2

1

x1

x2

2

x1 2x2 2

x1

0, x2

0.

Решение. Целевая функция данной задачи является

квадратичной с матрицей

A

1

1

1

2

1

1,

2

1

положительны, то данная матрица является

2x1

2x2

1

2

1

2

2x1

4x2

1

2 2

2

6

x1

x2

x3

2

x1

2x2

x4

2

x1 , x2 , x3 , x4 , 1 ,

2 , 1 ,

2

0

1x1

2 x2

1x3

2 x4

0.

x5

x6

max

2x1

2x2

1

2

1 x5

2

2x1

4x2

1

2 2

2

x6 6

x1

2x2

x4

2

x1, x2 , x3 , x4 ,

1,

2 , 1,

2

0,

взяв

в

качестве

первоначального

базисного

множества

J

{5, 6,3, 4}.. Приведем последовательность симплексных таблиц.

cB

J

xB

x1

x2

x3

x4

λ1

λ2

μ1

μ2

-1

5

2

2

-2

0

0

1

-1

-1

0

-1

6

6

-2

4

0

0

1

2

0

-1

0

3

2

1

1

1

0

0

0

0

0

0

4

2

-1

2

0

1

0

0

0

0

-8

0

-2

0

0

-2

-1

1

1

-1

5

4

1

0

0

1

1

-1

-1

0

-1

6

2

0

0

0

-2

1

2

0

1

0

3

1

3/2

0

1

-1/2

0

0

0

0

0

2

1

-1/2

1

0

½

0

0

0

0

-6

-1

0

0

1

-2

-1

1

1

-1

5

10/3

0

0

-2/3

4/3

1

-1

-1

0

-1

6

2

0

0

0

-2

1

2

0

-1

0

1

2/3

1

0

2/3

-1/3

0

0

0

0

0

2

4/3

0

1

1/3

1/3

0

0

0

0

-16/3

0

0

2/3

2/3

-2

-1

1

1

-1

5

4/3

0

0

-2/3

10/3

0

-3

-1

1

0

λ1

2

0

0

0

-2

1

2

0

-1

0

1

2/3

1

0

2/3

-1/3

0

0

0

0

0

2

4/3

0

1

1/3

1/3

0

0

0

0

-4/3

0

0

2/3

-10/3

0

3

1

-1

0

4

4/10

0

λ1

28/10

0

1

4/5

0

2

6/5

0

0

0

0

0

0

0

0

0

x , x

, x

, x

,

,

,

,

4

,

6

,0,

2

,

14

,0,0,0

2

3

4

1

2

1

2

1

5

5

5

5

.

имеет вид x*

4

,

6

с значением целевой функции

5

5

f * f (x* )

36

.

5

Задачи для самостоятельного решения

1.

Решить

следующие

задачи

квадратичного

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

5.1.1)

(x 4)2

(x 2)2

min

1

2

cxT

max

____

(5.2.1)

: fi (x) bi ,

i=1,m.

З а м е ч а н и е

1 .

Любая

задача

выпуклого

функцией

(x)

max

_____

fi (x)

bi , i=1,m,

то она может быть переписана следующим образом:

max

(x)

0,

_____

fi (x)

bi ,

i=1,m.

Для решения задач вида (5.2.1) применяется метод секущих

плоскостей,

основанный

на

приближении

всех нелинейных

функций

fi (x) линейными

с использованием

разложения по

формуле Тейлора:

fi (x)

fi (x0 )

fi (x0 )(x x0 )T .

Рассмотрим задачу

cxT

max

(x0 )

(x0 )(x x0 )T

_____ (5.2.2)

1

:

f

f

b ,

i=1,m .

i

i

i