Для задачи (5.11), (5.12) функция Лагранжа будет иметь вид

.

Если функция имеет седловую точку ( , ), то в этой точке выполняются соотношения (5.9). Вводя дополнительные переменные  и , перепишем выражения (5.9) в виде

 

                 (5.13)

 

5.3.2 Метод неопределенных множителей Лагранжа для решения задач квадратичного программирования

 

Рассмотрим задачу (5.11), (5.12) из пункта 5.3.1. Чтобы найти решение задачи квадратичного программирования (5.11), (5.12) нужно определить неотрицательное решение систем линейных уравнений (5.13). Это решение можно найти с помощью метода искусственного базиса.

Процесс нахождения решения включает следующие этапы:

1) составляют функцию Лагранжа;

2) записывают в виде системы (5.13) необходимые и достаточные условия существования седловой точки для функции Лагранжа;

3) используя метод искусственного базиса, либо устанавливают отсутствие седловой точки для функции Лагранжа, либо находят ее координаты;

4) записывают оптимальное решение исходной задачи и находят значение целевой функции.

Пример 5.3.

Найти максимальное значение функции

                                   (5.14)

при условиях

                                                (5.15)

Решение. Функция f является вогнутой, так как представляет собой сумму линейной функции  (которую можно рассматривать как вогнутую) и квадратичной формы , которая является отрицательно определенной. Система ограничений включает только линейные неравенства. Следовательно, можно воспользоваться теоремой Куна-Таккера. Составим функцию Лагранжа:

(5.16)

 

и запишем необходимые и достаточные условия существования седловой точки построенной функции:

 

                                                        (5.17)

 

                               (5.18)

Систему линейных неравенств (5.17) перепишем в виде:

                                                                   (5.19)

 

Вводя теперь дополнительные неотрицательные переменные v₁,v₂,w₁ и w₂, обращающие неравенства (5.17) в равенства, получим

                                 (5.20)

                        .

Учитывая равенства (5.20), можно записать:

      .             (5.21)

Если теперь найти базисное решение системы линейных уравнений (5.20) с учетом (5.21), то будет получена седловая точка функции Лагранжа для исходной задачи, то есть определено оптимальное решение.

Для нахождения базисного решения системы линейных уравнений (5.20) воспользуемся методом искусственного базиса. В первое и второе уравнения (5.20) добавим неотрицательные переменные Z₁ и Z₂ и рассмотрим задачу линейного программирования, состоящую в определении максимального значения функции

 

                                         (5.22)

при условиях

                                (5.23)

   .        (5.24)

 

В результате решения задачи линейного программирования (5.22)−(5.24) находим допустимое базисное решение системы линейных уравнений (5.23) (таблица 5.1):

Отсюда .

Так как , то ( , )=(1,1,0,0) является седловой точкой функции Лагранжа для исходной задачи. Следовательно, =(1,1) – оптимальный план исходной задачи и  f_max=3.

 

Таблица 5.1 – Результаты вычислений методом Лагранжа

 

	Базис	Cб	С0	0	0	0	0	0	0	0	0	-М	-М
1		-М	2	2	0	1	2	-1	0	0	0	1	0
2		-М	4	0	4	2	-1	0	-1	0	0	0	1
3		0	8	1	2	0	0	0	0	1	0	0	0
4		0	12	2	-1	0	0	0	0	0	1	0	0
5			0	0	0	0	0	0	0	0	0	0	0
6			-6	-2	-4	-3	-1	1	1	0	0	0	0
1		-М	2	2	0	1	2	-1	0	0	0	1	0
2		0	1	0	1	1/2	-1/4	0	-1/4	0	0	0	1/4
3		0	6	1	0	-1	1/2	0	1/2	1	0	0	-1/2
4		0	13	2	0	1/2	-1/4	0	-1/4	0	1	0	-1/4
5		0	0	0	0	0	0	0	0	0	0	0	0
6			-2	-2	0	-1	-2	1	0	0	0	0	1
1		0	1	1	0	1/2	1	-1/2	0	0	0	1/2	0
2		0	1	0	1					0	0
3		0	5	0	0					1	0
4		0	11	0	0					0	1
5			0	0	0					0	0

 

---

Дата добавления: 2018-04-04; просмотров: 377; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!