Математичне моделювання економічних систем
![]()
Отже
план
є оптимальним
F=4010
Завдання 5. Задача квадратичного програмування
Розв’язати задачу квадратичного програмування геометричним методом та аналітичним методом, використовуючи функцію Лагранжа і теорему Куна-Таккера:
Розв’язання графічним методом
,

![]()
Графік кола має центр в точці (-1, 4)
![]()
![]()
![]()

X* (0 , 4); F*(X*)=-16
Розв’язання аналітичним методом
,

Складемо функцію Лагранжа:
![]()
Система обмежень набуде вигляду:

Перенесемо вільні члени вправо, і при необхідності домножимо на -1

Зведемо систему обмежень до канонічного вигляду

Введемо додаткові змінні для утворення штучного базису

Розв’яжемо задачу лінійного програмування на знаходження мінімуму.
Введемо додаткові прямі обмеження на змінні.
,
![]()
![]()
Вектори з коефіцієнтів при невідомих:



Розв’язуємо отриману задачу звичайним симплекс-методом
| I | базис | Cб | P0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | M | M |
| Px1 | Px2 | Py1 | Py2 | Py3 | Pu1 | Pu2 | Pv1 | Pv2 | Pv3 | Pz1 | Pz2 | ||||
| 1 | Pz1 | M | 2 | -2 | 0 | -3 | 1 | 1 | -1 | 0 | 0 | 0 | 0 | 1 | 0 |
| 2 | Pu2 | 0 | 8 | 0 | 2 | 2 | 1 | -1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 3 | Pv1 | 0 | 18 | -3 | -2 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 4 | Pv2 | 0 | 6 | -1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 5 | Pz2 | M | 4 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 1 |
| 5 | -M | M | -3M | M | M | -M | 0 | 0 | 0 | -M | 0 | 0 |
Обраний розв’язковий елемент (5,2)
| I | базис | Cб | P0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | M | M |
| Px1 | Px2 | Py1 | Py2 | Py3 | Pu1 | Pu2 | Pv1 | Pv2 | Pv3 | Pz1 | Pz2 | ||||
| 1 | Pz1 | M | 2 | -2 | 0 | -3 | 1 | 1 | -1 | 0 | 0 | 0 | 0 | 1 | 0 |
| 2 | Pu2 | 0 | 0 | -2 | 0 | 2 | 1 | -1 | 0 | 1 | 0 | 0 | 2 | 0 | 0 |
| 3 | Pv1 | 0 | 26 | -1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | -2 | 0 | 0 |
| 4 | Pv2 | 0 | 2 | -2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 5 | Px2 | 0 | 4 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 1 |
| 5 | 2М | -2М | 0 | -3М | М | M | -М | 0 | 0 | 0 | 0 | 0 | 0 |
Обраний розв’язковий елемент (2,4)
| I | базис | Cб | P0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | M | M |
| Px1 | Px2 | Py1 | Py2 | Py3 | Pu1 | Pu2 | Pv1 | Pv2 | Pv3 | Pz1 | Pz2 | ||||
| 1 | Pz1 | M | 2 | 0 | 0 | -5 | 0 | 2 | -1 | -1 | 0 | 0 | -2 | 1 | |
| 2 | Py2 | 0 | 0 | -2 | 0 | 2 | 1 | -1 | 0 | 1 | 0 | 0 | 2 | 0 | |
| 3 | Pv1 | 0 | 26 | -1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | -2 | 0 | |
| 4 | Pv2 | 0 | 2 | -2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | |
| 5 | Px2 | 0 | 4 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | |
| 5 | 2M | 0 | 0 | -5M | 0 | 2M | -M | -M | 0 | 0 | -2M | 0 |
Обраний розв’язковий елемент (1,5)
| I | базис | Cб | P0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | M | M |
| Px1 | Px2 | Py1 | Py2 | Py3 | Pu1 | Pu2 | Pv1 | Pv2 | Pv3 | Pz1 | Pz2 | ||||
| 1 | Py3 | 0 | 1 | 0 | 0 | -5/2 | 0 | 1 | -1/2 | -1/2 | 0 | 0 | -1 | ||
| 2 | Py2 | 0 | 1 | -2 | 0 | -1/2 | 1 | 0 | -1/2 | -1/2 | 0 | 0 | 1 | ||
| 3 | Pv1 | 0 | 26 | -1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | -2 | ||
| 4 | Pv2 | 0 | 2 | -2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | ||
| 5 | Px2 | 0 | 4 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | ||
| 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
План отриманий в результаті розв’язування задачі симплекс-методом, не є оптимальним так як він не задовольняє умови:

Отже перерахуємо симплекс-таблицю ще раз.
Обраний розв’язковий елемент (2,7)
| I | базис | Cб | P0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| Px1 | Px2 | Py1 | Py2 | Py3 | Pu1 | Pu2 | Pv1 | Pv2 | Pv3 | ||||
| 1 | Py3 | 0 | 10 | 0 | 2 | -3 | 1 | 1 | -1 | 0 | 0 | 0 | -2 |
| 2 | Pu2 | 0 | 18 | 0 | 4 | -1 | 2 | 0 | -1 | 1 | 0 | 0 | -2 |
| 3 | Pv1 | 0 | 30 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | -3 |
| 4 | Pv2 | 0 | 10 | 0 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | -1 |
| 5 | Px2 | 0 | 4 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 |
| 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Отриманий план оптимальний X* (0,4); F*(X*)=-16
Список використаної літератури
Карманов В. Г. Математическое программирование: Учеб. пособие. — 5-е издание., стереотип. — М.: ФИЗМАТЛИТ, 2001. — 264 с.
Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М. Методы оптимизации —М.: Наука, 1978. — 352 с.