p align="left">За методом північно-західного кута опорний план має вигляд: . 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 | | | | |
План отриманий в результаті розв'язування задачі симплекс-методом, не є оптимальним так як він не задовольняє умови: Отже перерахуємо симплекс-таблицю ще раз. Обраний розв'язковий елемент (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 Список використаної літератури 1. Карманов В. Г. Математическое программирование: Учеб. пособие. -- 5-е издание., стереотип. -- М.: ФИЗМАТЛИТ, 2001. -- 264 с. 2. Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М. Методы оптимизации --М.: Наука, 1978. -- 352 с.
Страницы: 1, 2, 3
|