Искать:

  

Методы оптимизации

Назад Домашняя Вверх Далее

 Купим рекламу на вашем сайте.

На исходе времён, когда цивилизация
достигла своего апогея,
когда учёные победили болезни и даже смерть, нарушилось равновесие между силами
Света и Тьмы.

Этот сдвиг породил губительные последствия для всего человечества. Спаслось всего
десять тысяч,
и ценою спасения
был отказ
от бессмертия.

Именно так началось
противостояние...

Вечная битва...

Вселенская битва...

Купить книгу

С. Подклетнова. Вселенская битва: НАЧАЛО. -

Самара, Россия: Издательско-полиграфический комплекс "Самарская губерния", 2005 г., 674 с.

Стоимость книги 250 руб.

Вопросы и предложения по распространению admin@big-biblioteka.com

 

Самарский государственный аэрокосмический университет им. акад. С.П.Королева

Кафедра технической кибернетики

 

 

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

 и задания для решения задач по курсу

“Методы оптимизации”

 

 

 

Самара - 1998

  

Методические указания предназначены для студентов дневного обучения специальности 0102 “Прикладная математика”. Они содержат решения типовых задач по курсу “Методы оптимизации ” и необходимые пояснения, по которым студенты могут самостоятельно получать практические навыки использования математических методов нахождения экстремумов функций в задачах на безусловный и условный экстремум, а также в задачах линейного программирования. Задачи, приведенные в методических указаниях, могут быть использованы для выдачи индивидуальных заданий студентам при проведении практических занятий по курсу.

 

 

Составитель:  доц. Дубина С.М.


 

9. Квадратичное программирование

Рассмотрим задачу квадратичного программирования:

               –x12 + 4x1 –x22 + 6x2 –x32 + x3 –x42 ® max

                                     –x1 + 2x2 + x3 = 2

                             3x1 + 2x2 + x4 = 6

                                               xi³ 0, i =.

Решим ее с помощью метода Вольфа. Составим первую задачу ЛП.

 L = –x12+4x1 –x22+6x2 –x32+x3 –x42+l1(2+x1 –2x2 –x3)+l2(6 –3x1 –2x2 –x4)

-P1 = -2x1 +4 +l1 –3l2

-P2 = -2x2 +6 –2l1 –2l2

-P3 = -2x3 +1 –l1

-P4 = -2x4  –l2

 

f = y1 + y2 ® min

y1 =2 –(-x1 +2x2 +x3)

y2 =6 –(3x1 +2x2 +x4)

w1=4 –(2x1 –P1 –l1+3l2)                                     (1)

w2=6 –(2x2 –P2+2l1+2l2)

w3=1 –(2x3 –P3 +l1)

w4= –(2x4 –P4 +l2)

xi,y1 ,y2,wi,Pi³ 0, i =.

Для решения задачи ЛП (1) заполним симплекс-таблицу (табл. 1). Таблицы 2 и 3 иллюстрируют решение задачи (столбцы, которые не могут измениться, не показаны). Звездочками помечены генеральные элементы.  В результате решения этой задачи получили план (невязки y1 ,y2 равны 0). Значение квадратичной формы для него равно 9,75.

 Сформулируем вторую задачу, решение которой обеспечит выполнение условий оптимальности.

Табл. 1                                             Табл. 2                                 Табл. 3

 

 

x1

x2

x3

x4

 

 

 

x1

x3

x4

 

 

 

x3

x4

f

8

2

4

1

1

 

f

4

4

-1

1

 

f

 

 

 

y1

2

-1

2*

1

 

 

x2

1

-1/2

1/2

 

 

x2

3/2

3/8

1/8

y2

6

3

2

 

1

 

y2

4

4*

-1

1

 

x1

1

-1/4

1/4

w1

4

2

 

 

 

 

w1

4

2

 

 

 

w1

2

1/2

-1/2

w2

6

 

2

 

 

 

w2

4

1

-1

 

 

w2

3

-3/4

-1/4

w3

1

 

 

2

 

 

w3

1

 

2

 

 

w3

1

2

 

w4

 

 

 

 

2

 

w4

 

 

 

2

 

w4

 

 

2

 

Она имеет вид:

F = w1 + w2 + w3 + w4 ® min

x1 =1 –(-0,25x3 +0,25x4)

x2 =1,5 –(0,375x3 +0,125x4)

w1=2 –(0,5x3 –0,5x4 –P1 –l1+3l2)                           (2)

w2=3 –(–0,75x3 –0,25x4–P2+2l1+2l2)

w3=1 –(2x3 –P3 +l1)

w4= –(2x4 –P4 +l2)

xiPi =0; xi,wi,Pi³ 0, i =.

Для задачи (2) заполним симплекс-таблицу

 

Табл. 3                                

 

 

x3

x4

P1

P2

P3

P4

l1

l2

F

6

7/4

5/4

-1

-1

-1

-1

2

6

x1

1

-1/4

1/4

 

 

 

 

 

 

x2

3/2

3/8

1/8

 

 

 

 

 

 

w1

2

1/2

-1/2

-1

 

 

 

-1

3

w2

3

-3/4

-1/4

 

-1

 

 

2

2

w3

1

2

 

 

 

-1

 

1*

 

w4

 

 

2

 

 

 

-1

 

1

 

Решение показано в таблицах 4 – 7. Обратите внимание на то, что xi и Pi не могут одновременно находиться в базисе.

 

Табл. 4                                

 

 

x3

x4

P1

P2

P3

P4

l2

F

4

-9/4

5/4

-1

-1

1

-1

6

x1

1

-1/4

1/4

 

 

 

 

 

x2

3/2

3/8

1/8

 

 

 

 

 

w1

3

5/2

-1/2

-1

 

-1

 

3

w2

1

-19/4

-1/4

 

-1

2

 

2

l1

1

2

 

 

 

-1

 

 

w4

 

 

2

 

 

 

-1

1*

 

Генеральные элементы в таблицах помечены звездочками.  Пустые  ячейки  таблиц соответствуют нулевым значениям. В таблице 7 серым закрашены ячейки, значения в которых нас не интересуют.

В итоге получено оптимальное решение (таблица 7) со значением квадратичной формы, равным приблизительно 9,777.

 

Табл. 5                                

 

 

x3

x4

P1

P2

P3

P4

F

4

-9/4

-43/4

-1

-1

1

5

x1

1

-1/4

1/4

 

 

 

 

x2

3/2

3/8

1/8

 

 

 

 

w1

3

5/2

-13/2

-1

 

-1

3

w2

1

-19/4

-17/4

 

-1

2

2*

l1

1

2

 

 

 

-1

 

l2

 

 

2

 

 

 

-1

 

Табл. 6              

 

 

x3

x4

P1

P2

P3

F

3/2

77/8

-1/8

-1

3/2

-4

x1

1

-1/4

1/4

 

 

 

x2

3/2

3/8

1/8

 

 

 

w1

3/2

77/8*

-1/8

-1

3/2

-4

P4

1/2

-19/8

-17/8

 

-1/2

1

l1

1

2

 

 

1/2

-1

l2

1/2

-19/8

-1/8

 

-1/2

1

 

Табл. 7                   

 

 

x4

P1

P2

P3

F

 

 

 

 

 

x1

80/77

 

 

 

 

x2

111/77

 

 

 

 

x3

12/77

 

 

 

 

P4

67/77

 

 

 

 

l1

 

 

 

 

 

l2

 

 

 

 

 

 

Задания

 Найти минимум квадратичной формы:

 а) 3(x2 + y2 + z2 + u2 + v2) + 5(xy + xz + yz) – ax –by –cz –u,

     при ограничениях (3):

dx +ey +fz +gu +hv +kw = A

lx  nz +bu +ov +pw = B                               (3)

qx +ry +sz + tu + iv + jw = C

x,y,z,u,v,w³ 0.


 

вариант

1

2

3

4

5

6

7

8

9

10

11

12

a

6,3

6,8

7,3

7,8

6,9

7,4

7,9

8,4

7,5

8

8,5

9

b

6,4

6,9

7,6

8,1

6,9

7,4

8,1

8,6

7,4

7,9

8,6

9,1

c

6,5

7,1

7,5

8,1

7

7,6

8

8,6

7,5

8,1

8,5

9,1

d

1

1

 

2

1

1

1

1

 

1

2

1

e

-2

1

1

1

-2

2

1

-2

1

 

 

-1

f

-2

 

-2

 

-2

4

-1

 

2

 

 

 

g

1

 

11

-2

1

 

 

1

 

4

7

1

h

-9

5

 

 

-1

 

 

 

-4

 

-2

1

k

8

 

8

 

 

 

 

 

 

-2

 

2

l

1

3

1

1

 

1

1

 

 

1

 

-4

m

-1

-2

-2

-1

-2

-2

 

1

1

1

-4

 

n

 

1

5

1

-1

1

1

1

2

 

2

 

b

2

 

-24

6

3

 

 

-2

3

 

1

1

o

-5

4

-4

1

2

 

1

 

-3

 

 

3

p

3

 

16

 

 

2

 

 

3

1

1

4

q

1

2

1

10

 

1

 

 

1

 

7

1

r

-3

1

 

-1

1

 

1

3

1

1

 

-1

s

-5

 

 

3

8

2

 

 

1

1

-3

4

t

 

1

2

20

1

-1

1

1

2

4

2

1

i

13

3

-5

 

3

-1

 

1

2

1

 

1

j

10

 

-5

 

 

2

1

 

2

 

-7

4

A

4

1

 

4

1

7

 

3

2

 

25

3

B

9

6

8

1

5

1

9

5

4

2

5

6

C

-2

10

5

14

20

3

8

4

4

2

20

8

  

вариант

13

14

15

16

17

18

19

20

21

22

23

24

a

7,3

7,8

8,3

8,8

7,8

8,3

8,8

9,3

8,3

8,8

9,3

9,8

b

7,4

7,9

8,4

8,9

8

8,5

9

9,5

8,6

9,1

9,6

10,1

c

7,7

8,3

8,9

9,5

8,2

8,8

9,4

10

8,7

9,3

9,9

10,5

d

1

1

 

2

1

1

1

1

 

1

2

1

e

-2

1

1

1

-2

2

1

-2

1

 

 

-1

f

-2

 

-2

 

-2

4

-1

 

2

 

 

 

g

1

 

11

-2

1

 

 

1

 

4

7

1

h

-9

5

 

 

-1

 

 

 

-4

 

-2

1

k

8

 

8

 

 

 

 

 

 

-2

 

2

l

1

3

1

1

 

1

1

 

 

1

 

-4

m

-1

-2

-2

-1

-2

-2

 

1

1

1

-4

 

n

 

1

5

1

-1

1

1

1

2

 

2

 

b

2

 

-24

6

3

 

 

-2

3

 

1

1

o

-5

4

-4

1

2

 

1

 

-3

 

 

3

p

3

 

16

 

 

2

 

 

3

1

1

4

q

1

2

1

10

 

1

 

 

1

 

7

1

r

-3

1

 

-1

1

 

1

3

1

1

 

-1

s

-5

 

 

3

8

2

 

 

1

1

-3

4

t

 

1

2

20

1

-1

1

1

2

4

2

1

i

13

3

-5

 

3

-1

 

1

2

1

 

1

j

10

 

-5

 

 

2

1

 

2

 

-7

4

A

4

1

 

4

1

7

 

3

2

 

25

3

B

9

6

8

1

5

1

9

5

4

2

5

6

C

-2

10

5

14

20

3

8

4

4

2

20

8

 

ЛИТЕРАТУРА

1.   Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. -М.: Наука, 1978.

2. Карпелевич Ф.И., Садовский Л.Е. Элементы линейной алгебры и линейного программирования. -М.: Наука, 1967.

3.        Корбут А.А., Финкельштейн Ю.Ю.  Дискретное программирование. –М.: Наука, 1969.

 4.        Беллман Р. Динамическое программирование. –М.: Мир,1960.

Закажи рекламу на Rambler.ru, Mail.ru, Aport.ru!
От 130 руб. за все!

 

 

bulletБиблиотека начинающего бизнесмена
bulletУчебная литература
bulletРефераты, курсовые и дипломные работы (бесплатная часть)
bulletРефераты, курсовые и дипломные работы (платные ресурсы)
bulletКонтрольные работы
bulletЭлектронный справочник по математике
bulletХудожественная литература
bulletФорматы электронных книг
bulletФотогалерея
bulletХудожественная галерея
bulletАнекдоты
bulletПрофессиональная вёрстка текстов
bulletОбмен ссылками
bulletКаталог сайтов
bulletВарианты оплаты

Специальное предложение типографиям!!! Профессиональная верстка текста. Примеры сверстанных книг можно увидеть в разделе "Библиотека сетевого маркетинга" (книги из формата Adobe PageMaker переведены в формат Acrobat Reader для удобства чтения).

Если Вы выбрали необходимую Вам курсовую или дипломную работу, здесь можно оформить её заказ или заказать новый реферат

Для желающих оставить свои предложения и замечания у нас работает  Гостевая книга

Желающих обсудить какие-либо вопросы, связанные с темой сайта, приглашаем на Форум

Здесь можно найти ссылки на те сайты интернета, которые кажутся нам наиболее интересными

Все материалы сайта охраняются законом об авторском праве. Частичная или полная перепечатка материалов сайта без разрешения администрации сайта строго запрещена!
С предложениями и вопросами просьба обращаться   admin@big-biblioteka.com
Последнее изменение: 29.10.2007

Rambler's Top100    HotLog    Находится в каталоге Апорт

Hosted by uCoz