47543 (572026), страница 3
Текст из файла (страница 3)
.
F=3*260+5*10+9*180+8*90+10*210+0*90=5270
Перевіримо чи буде він оптимальним.
Знаходимо потенціали для пунктів постачання
Для тих клітинок, де
, розв’яжемо систему рівнянь
Знаходимо з системи:
. 
Для тих клітинок, де
, знайдемо числа 
Оскільки 
, то план Х1 не є оптимальним. Будуємо цикл перерахунку
| Пункти | Пункти споживання | Запаси | ||||||
| постачання | B1 | B2 | B3 | |||||
| A1 | 3 | 5 | 7 | 0 | 270 | |||
| 260 | 10 | |||||||
| A2 | 6 | 1 | 9 | 4 | 7 | 180 | ||
| - | 180 | + | ||||||
| A3 | 11 | -5 | 8 | 10 | 300 | |||
| + | 90 | - | 210 | |||||
| A4 | 0 | -4 | 0 | -2 | 0 | 90 | ||
| 90 | ||||||||
| Потреби | 260 | 280 | 300 | 840 840 | ||||
В результаті перерахунку отримаємо
| Пункти | Пункти споживання | Запаси | |||
| постачання | B1 | B2 | B3 | ||
| A1 | 3 260 | 5 10 | 7 | 270 | |
| A2 | 6 | 9 | 4 180 | 180 | |
| A3 | 11 | 8 270 | 10 30 | 300 | |
| A4 | 0 | 0 | 0 90 | 90 | |
| Потреби | 260 | 280 | 300 | 840 840 | |
Наступний опорний план
F=3*260+5*10+9*180+8*90+10*210+0*90=4010
Для тих клітинок, де , розв’яжемо систему рівнянь
Знаходимо з системи:
.
Для тих клітинок, де , знайдемо числа
Отже план є оптимальним 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 |
План отриманий в результаті розв’язування задачі симплекс-методом, не є оптимальним так як він не задовольняє умови:
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
