4. Задача квадратического программирования
Одним из частных видов ЗВП является задача, в которой целевая функция содержит квадратичное слагаемое, а ограничения носят линейный характер. Такая задача относиться к квадратичному программированию.
В качестве основной в квадратичном программировании рассматривается задача минимизации функции
Далее будем считать, что решаемая задача квадратичного программирования является частным случаем ЗВП.
Функция Лагранжа в данном случае имеет вид:
Найдем стационарные точки функции Лагранжа:
С учетом ориентации и применяя теорему Куна-Таккера:
Преобразуем систему (10.1) к системе уравнений:
Тогда систему уравнений (10.2) можно записать в виде:
Чтобы учесть условие (10.3) при решении ЗНП надо следить за тем, чтобы среди базисных переменных не было u и x с одним и тем же индексом, аналогично λ и v.
Далее задача решается методом искусственного базиса.
Задача. Минимизировать функцию при ограничениях:
Составим функцию Лагранжа:
Составим локальные условия Куна-Таккера:
Преобразуем полученную систему ограничений к допустимому виду канонической формы:
Далее решаем задачу методом искусственного базиса, учитывая условие (10.3):
Получили оптимальный план решения задачи . Найдем значение целевой функции в данной точке:
Педагогический комментарий. Данное лекционное занятие закладывает основы для формирования следующих профессиональных умений студентов-экономистов: умение разрабатывать и обосновывать варианты эффективных производственно-технологических решений; умение ставить цель и формулировать задачи, связанные с профессиональной деятельностью, умение использовать для их решения методы изученных дисциплин; умение логически мыслить; умение совершенствовать составление оперативно-производственного плана с использованием инструментария математического программирования; умение эффективно управлять экономическими процессами и регулировать использование комплекса имеющихся ресурсов; умение использовать аналитические методы решения задач математического программирования при наличии нелинейных функциональных зависимостей экономических переменных.
Квадратичное программирование
Квадратичное программирование позволяет проводить оптимизационные исследования в задачах, в которых целевая функция составлена из линейных и квадратичных слагаемых, а ограничения являются линейными функциями. Задача квадратичного программирования представляет собой случай общей задачи нелинейного программирования. Модель задачи квадратичного программирования имеет следующую структуру: найти максимальное (минимальное) значение функции 
при ограничениях 
Второе слагаемое в выражении (*) называется квадратичной формой переменных х1, х2, …, хn и представляются в виде: 
Матрица 
коэффициентов квадратичной формы предполагается симметричной(dkj=djk). Диагональные элементы dkk этой матрицы являются коэффициентами при 
, а недиагональные элементы(dkj=djk) равны половине коэффициента при xkxj Можно использовать следующий порядок нахождения решения решения задачи квадратичного программирования:
- Составляется функция Логранжа.
- Записываются условия для ограничений.
- Используется метод искусственного базиса с применением математической модели.
- Находится оптимальное решение при выполнении условий п. (2).
Расчетная часть
ЗАДАЧА 1 Целевая функция F(x)=2x1 + 4x2 max; при ограничениях : 
Для приведения к положительным правым частям умножаем необходимые ограничения на (-1) и записываем в виде: 
Приведём ограничения к расширенной форме, при этом если знак неравенства 
, то базисная переменная входит в уравнение с положительным знаком. Если знак неравенства
, то переменная входит в уравнение с отрицательным знаком: Неравенства ограничений приведем к равенствам, используя дополнительные переменные x 3 , x 4 и x 5 : 
х1, х2 – свободные переменные. х3, х4, х5 – базисные переменные. Выразим систему ограничений относительно базисных переменных и приравняем полученные уравнения к нулю: 
где x 1, x 2, x 3, x 4, x 5 >0 переменные x 3 , x 4 и x 5 примем в качестве базисных и выразим через свободные x 1 и x 2 Прямые, соответствующие граничным значениям переменных x3 = x4 = x5= 0 представлены на рис. 2. Заштрихованная область будет областью допустимых решений. 
Рис.2 Максимального значения целевая функция достигает в крайней точке A области допустимых решений. Координаты точки A будут оптимальным решением задачи: 
ЗАДАЧА 2 Решить задачу методом симплекс — таблиц. Целевая функция F(x)= – 2x1+2x2 min; Уравнения ограничения 
Так как целевую функцию необходимо исследовать на минимум, то для удобства умножим ее на –1, и она будет выглядеть следующим образом: F(x)= 2x1–2x2 max Запишем уравнения ограничения в расширенной форме: 4x1 + 7x2 + x3 = 28 , x1 + x2 +x4 = 6 , –3x1 + 2x2 x5 +x6 = 3 , x1 , x2 0 . Целевая функция примет вид: F(x)= 2x1–2x2 +0x3 +0x4 +0x5 Mx6 max , где M. Обозначим векторы условий задачи через A1 A6 . Векторы A3 , A4 , A6 образуют единичную матрицу, которую примем за базис. В результате начальное базисное допустимое решение будет иметь вид X(0,0,28,6,0,3). Составим исходную симплекс-таблицу (табл.6), в которой рассчитаем элементы строки S. Таблица 6
| C | c1 2 | c2 –2 | c3 0 | c4 0 | c5 0 | c6 M | ||
| ХP | B | A1 | A2 | A3 | A4 | A5 | A6 | |
| c3 0 | x3 | 28 | 4 | 7 | 1 | 0 | 0 | 0 |
| c4 0 | x5 | 6 | 1 | 1 | 0 | 1 | 0 | 0 |
| c6 M | x6 | 3 | –3 | 2 | 0 | 0 | 1 | 1 |
| S | 3M | 23M | –2+M | 0 | 0 | –M | 0 |
В индексной строке табл.6 имеются Sj > 0, что позволяет улучшить решение задачи. Вводим в новый базис вектор A2, которому соответствует наибольшее значение S2 = 2 + M, а в новое базисное решение переменную x2. Столбец, содержащий вектор A2 будет направляющим. Составим отношения вида 
, по которым определим направляющую строку. Для этого находим: 
Таким образом направляющая строка вторая, направляющий элемент a22 (в таблице заключен в прямоугольник). Из базиса выводится вектор A6 , а из базисного решения переменная x6 . Рассчитаем и заполним новую таблицу соответствующую новому базисному решению. Таблица 7
| C | c1 2 | c2 –2 | c3 0 | c4 0 | c5 0 | c6 M | ||
| ХP | B | A1 | A2 | A3 | A4 | A5 | A6 | |
| c3 0 | x3 | 35/2 | 29/2 | 0 | 1 | 0 | 7/2 | -7/2 |
| c4 0 | x5 | 9/2 | 5/2 | 0 | 0 | 1 | 1/2 | -1/2 |
| с2 2 | х2 | 3/2 | –3/2 | 1 | 0 | 0 | 1/2 | 1/2 |
| S | 3 | 23M | 0 | 0 | 0 | –1 | 1– M |
В таблице все Sj 0. Поэтому полученное решение является оптимальным: 
ЗАДАЧА 3 Решить транспортную задачу . 3 5 Целевая функция F = c ij xij; i=1 j=1 Условия транспортной задачи представлены в табл. 8 Табл.8
| ПП ПО | В1 | В2 | В3 | В4 | В5 | Запасы |
| А1 | 5 | 2 | 10 | 10 | 6 | 80 |
| А2 | 6 | 4 | 3 | 9 | 2 | 80 |
| А3 | 8 | 9 | 7 | 8 | 4 | 40 |
| Заявки | 40 | 30 | 30 | 40 | 60 |
Определим опорный план, используя правило “северо-западного угла”. 
Результаты сведены в табл. 9. Таблица 9
| 5 40 | 2 30 | 10 10 | 10 | 6 | 80 |
| 6 | 4 | 3 20 | 9 40 | 2 20 | 80 |
| 8 | 9 | 7 | 8 | 4 40 | 40 |
| 40 | 30 | 30 | 40 | 60 |
Таким образом опорный план имеет вид: 
Полученное решение является опорным (начальным базисным допустимым решением), в котором переменные имеют значения: х11=40; х12=30; х13=10; х23=20; х24=40; х25=20; х35= 40. Стоимость полученного плана найдем, умножив каждую перевозку на соответствующую стоимость: F = 40*5 + 30*2 + 10*10 + 20*3 + 40*9 + 20*2 + 40*4 = = 980. Находим значения потенциалов ui и vj , соответствующие базисным клеткам, принимая для удобства u1=0. u1 + v1 =5; u1 = 0, v1 = 5; u1 + v2 =2; v2 = 2; u1 +v3 = 10; v3 = 10; u2 + v3 = 3; u2 =7; u2 + v4 = 9; v4 = 16; u2 + v5 = 2; v5 = 9; u3 +v5 = 4; u3 = -5. Находим для небазисных клеток оценки 
с учетом значений потенциалов ui и vj: 
Так как среди оценок 
имеются положительные, то план можно улучшить, осуществляя перевозки по замкнутому циклу. Начальная вершина цикла соответствует небазисной клетке с наибольшей положительной оценкой(
). Таким образом перевозки осуществляем по следующему циклу x14 x24 x23 x13. Полученные результаты представим в табл. 10. Таблица10
| ui\vj | 5 | 2 | 10 | 16 | 9 | |
| 0 | 5 40 | 2 30 | 10 10 | 6 10 | 3 6 | 80 |
| -7 | -8 6 | -9 4 | 3 20 | 9 40 | 2 20 | 80 |
| -5 | -8 8 | -12 9 | -2 7 | 3 8 | 4 40 | 40 |
| 40 | 30 | 30 | 40 | 60 | bj\ai |
Новый опорный план: 
Проверим на вырожденность опорный план m+n-1=6. Опорный план не вырожден. Стоимость полученного плана найдем умножив каждую перевозку на соответствующую стоимость: F = 40*5 + 30*2 + 10*10 + 30*3 + 30*9 + 20*2 + 40*4 = 920. Находим значения потенциалов ui и vj , соответствующие базисным клеткам, принимая для удобства u1=0. u1 + v1 =5; u1 = 0, v1 = 5; u1 + v2 =2; v2 = 2; u1 +v4 = 10; v4 = 10; u2 + v3 = 3; v3 = 4; u2 + v4 = 9; u2 = -1; u2 + v5 = 2; v5 = 3; u3 +v5 = 4; u3 = 1. Находим для небазисных клеток оценки 
с учетом значений потенциалов ui и vj: 
Так как среди оценок 
имеются положительные, то план можно улучшить осуществляя перевозки по замкнутому циклу. Начальная вершина цикла соответствует небазисной клетке с наибольшей положительной оценкой (
). Таким образом перевозки осуществляем по следующему циклу x34 x35 x25 x24. Полученные результаты представим в табл. 11. Таблица 11
| ui\vj | 5 | 2 | 4 | 10 | 3 | |
| 0 | 5 40 | 2 30 | -6 10 | 10 10 | -3 6 | 80 |
| -1 | -2 6 | -3 4 | 3 20 | 9 40 — | 2 20 + | 80 |
| -1 | -2 8 | -7 9 | -2 7 | 3 8 + | 4 40 — | 40 |
| 40 | 30 | 30 | 40 | 60 | bj\ai |
Новый опорный план: 
Стоимость полученного плана найдем, умножив каждую перевозку на соответствующую стоимость: F = 40*5 + 30*2 + 10*10 + 30*3 + 50*2 + 30*8 + 10*4 = 830. Находим значения потенциалов ui и vj, соответствующие базисным клеткам, принимая для удобства u1=0. u1 + v1 =5; u1 = 0, v1 = 5; u1 + v2 =2; v2 = 2; u1 +v4 = 10; v4 = 10; u2 + v3 = 3; v3 = 7; u2 + v5 = 2; u2 = -4; u3 + v4 = 8; u3 = -2; u3 +v5 = 4; v5 = 6. Находим для небазисных клеток оценки 
с учетом значений потенциалов ui и vj: 
Так как все оценки для небазисных клеток 
отрицательны, то полученный план является оптимальным. F * = 40*5 + 30*2 + 10*10 + 30*3 + 50*2 + 30*8 + 10*4 = 830. ЗАДАЧА 4 Решить задачу квадратичного программирования графически. Привести задачу к задаче линейного программирования специального вида. Решить задачу модифицированным методом искусственного базиса. 
при ограничениях: 2х1 + х2 4; — х1 + х2 2; х1, х2 0. Приведем задачу к задаче линейного программирования специального вида и решим модифицированным методом искусственного базиса. Составим матрицу D и рассмотрим ее определители: D =
; ∆1= -1 < 0 Составим функцию Лагранжа. 
Запишем условие Куна — Таккера: 
Систему линейных неравенств перепишем в виде: 2
х1 – 2х2 + 21 — 2 2 4х2 – 2х1 + 1 + 2 2 2х1 + х2 4 — х1 + х1 2 Получим систему линейных неравенств, т.е. задача приведена к задаче линейного программирования. Используя дополнительные переменные v1, v2, w1, w2 приведем неравенства к равенствам. 2х1 – 2х2 + 21 — 2 — v1 = 2; 4х2 – 2х1 + 1 + 2 – v2 = 2; (*) 2х1 + х2 + w1 = 4; — х1 + х1 + w2 = 2; Дополним равенства условиями, которые представим в виде: v1x1 = 0; v2x2 = 0; w11 = 0; w22 = 0. (**) Найдем базисное дополнительное решение системы (*) с учетом (**). Для этого воспользуемся методом искусственного базиса, вводя искусственные переменные z1 и z2. Получим: F(x) = —Mz1 —M z2 2х1 – 2х2 + 21 — 2 — v1 + z1 = 2; 4х2 – 2х1 + 1 + 2 – v2 + z2 = 2; 2х1 + х2 + w1 = 4; — х1 + х1 + w2 = 2; Решим задачу методом симплекс-таблиц. Результаты показаны в табл. 12 — 15 Таблица 12
| С | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -M | -M | ||
| XP | A0 | Ax1 | Ax2 | A1 | A2 | Av1 | Av2 | Aw1 | Aw2 | Az1 | Az2 | |
| -M | z1 | 2 | 2 | -2 | 2 | -1 | -1 | 0 | 0 | 0 | 1 | 0 |
| -M | z2 | 2 | -2 | 4 | 1 | 1 | 0 | -1 | 0 | 0 | 0 | 1 |
| 0 | w1 | 4 | 2 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | w2 | 2 | -1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| S | -4M | 0 | 2M | 3M | 0 | -M | -M | 0 | 0 | 0 | 0 |
Таблица 13
| С | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -M | -M | ||
| XP | A0 | Ax1 | Ax2 | A1 | A2 | Av1 | Av2 | Aw1 | Aw2 | Az1 | Az2 | |
| 0 | 1 | 1 | 1 | -1 | 1 | -1/2 | -1/2 | 0 | 0 | 0 | 1/2 | 0 |
| -M | z2 | 1 | -3 | 5 | 0 | 3/2 | 1/2 | -1 | 0 | 0 | -1/2 | 1 |
| 0 | w1 | 4 | 2 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | w2 | 2 | -1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| S | -M | -3M | 5M | 0 | 3/2M | 1/2M | -M | 0 | 0 | -3/2M | 0 |
Таблица 14
| С | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -M | -M | ||
| XP | A0 | Ax1 | Ax2 | A1 | A2 | Av1 | Av2 | Aw1 | Aw2 | Az1 | Az2 | |
| 0 | 1 | 6/5 | 2/5 | 0 | 1 | -1/5 | -2/5 | -1/5 | 0 | 0 | 9/10 | 1/5 |
| 0 | X2 | 1/5 | -3/5 | 1 | 0 | 3/10 | 1/10 | -1/5 | 0 | 0 | -1/10 | 1/10 |
| 0 | W1 | 19/5 | 13/5 | 0 | 0 | -3/10 | -1/10 | 1/5 | 1 | 0 | 1/10 | -1/5 |
| 0 | W2 | 6/5 | -2/5 | 0 | 0 | -3/10 | -1/10 | 1/5 | 0 | 1 | 1/10 | -1/5 |
| S | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -M | -M |
В таблице 14 получено, предположительно оптимальное решение, но оно не отвечает условиям (**), следовательно, проделаем еще одну итерацию: Табл. 15
| С | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -M | -M | |
| XP | A0 | Ax1 | Ax2 | A1 | A2 | Av1 | Av2 | Aw1 | Aw2 | Az1 | Az2 |
| 0 | 1 | 8/13 | 0 | 0 | 1 | 0 | 0 | ||||
| 0 | x2 | 14/13 | 0 | 1 | 0 | 3/13 | 0 | ||||
| 0 | x1 | 19/13 | 1 | 0 | 0 | 5/13 | 0 | ||||
| 0 | w2 | 64/65 | 0 | 0 | 0 | 2/13 | 1 | ||||
| S | 0 | 0 | 0 | 0 | 0 | 0 |
Таким образом, получаем оптимальное решения, удовлетворяющее заданным условиям: 
Для нахождения решения графическим методом, построим линии уровня исходной функции F(x1,x2) и линии ограничения (ОДР) (рис.3). 
Рис.3 На рис.3 видно, что значения 