Для заданої задачі лінійного програмування побудувати двоїсту задачу. Знайти розв'язок прямої задачі геометричним методом і симплекс-методом. Знайти розв'язок двоїстої задачі, використовуючи результати розв'язування прямої задачі симплекс-методом:
- 3. ,
- Розв?язання геометричним методом
- Побудуємо прямі, рівняння яких одержуються внаслідок заміни в обмеженнях знаків нерівностей на знаки рівностей.
Визначимо півплощини, що задовольняють нашим нерівностям.
- Умовам невід'ємності та відповідає перша чверть.
Заштрихуємо спільну частину площини, що задовольняє всім нерівностям.
Побудуємо вектор нормалі .
Максимального значення функція набуває в точці перетину прямих I та II.
Знайдемо координати цієї точки.
Приведемо систему до канонічного вигляду
Відповідь:
Розв?язання симплекс-методом
Приведемо систему рівнянь до канонічного вигляду
x(0)=(0,0,18,6,0,4)
Цільова функція
Побудуємо симплекс-таблицю
|
I | базис | Cб | P0 | 2 | 3 | 0 | 0 | 0 | -M | |
| | | | P1 | P2 | P3 | P4 | P5 | P6 | |
1 | P3 | 0 | 18 | 3 | 2 | 1 | 0 | 0 | 0 | |
2 | P4 | 0 | 6 | -1 | 1 | 0 | 1 | 0 | 0 | |
3 | P6 | -M | 4 | 1 | 1 | 0 | 0 | -1 | 1 | |
4 | | | 0 | -2 | -3 | 0 | 0 | 0 | 0 | |
5 | | | -4 | -1 | -1 | 0 | 0 | 1 | 0 | |
|
Отриманий план не оптимальний
Обраний ключовий елемент (3,2)
|
I | базис | Cб | P0 | 2 | 3 | 0 | 0 | 0 | -M | |
| | | | P1 | P2 | P3 | P4 | P5 | P6 | |
1 | P3 | 0 | 10 | 1 | 0 | 1 | 0 | 2 | -2 | |
2 | P4 | 0 | 2 | -2 | 0 | 0 | 1 | 1 | -1 | |
3 | P2 | 3 | 4 | 1 | 1 | 0 | 0 | -1 | -1 | |
4 | | | 12 | 1 | 0 | 0 | 0 | -3 | -3 | |
5 | | | 0 | 0 | 0 | 0 | 0 | 0 | -1 | |
|
Отриманий план не оптимальний
Обраний ключовий елемент (2,5)
|
I | базис | Cб | P0 | 2 | 3 | 0 | 0 | 0 | -M | |
| | | | P1 | P2 | P3 | P4 | P5 | P6 | |
1 | P3 | 0 | 6 | 5 | 0 | 1 | -2 | 0 | 0 | |
2 | P5 | 0 | 2 | -2 | 0 | 0 | 1 | 1 | -1 | |
3 | P2 | 3 | 6 | -1 | 1 | 0 | 1 | 0 | 0 | |
4 | | | 18 | -5 | 0 | 0 | 3 | 0 | 0 | |
5 | | | 0 | 0 | 0 | 0 | 0 | 0 | -1 | |
|
Отриманий план не оптимальний
Обраний ключовий елемент (1,1)
|
I | базис | Cб | P0 | 2 | 3 | 0 | 0 | 0 | -M | |
| | | | P1 | P2 | P3 | P4 | P5 | P6 | |
1 | P1 | 2 | 6/5 | 1 | 0 | 1/5 | -2/5 | 0 | 0 | |
2 | P5 | 0 | 22/5 | 0 | 0 | 2/5 | 1/5 | 1 | -1 | |
3 | P2 | 3 | 36/5 | 0 | 1 | 1/5 | 3/5 | 0 | 0 | |
4 | | | 24 | 0 | 0 | 1 | 1 | 0 | 0 | |
5 | | | 0 | 0 | 0 | 0 | 0 | 0 | 1 | |
|
План оптимальний
Розв'язок: X*(,) F*=24;
Розв'язок двоїстої задач
Побудуємо двоїсту функцію
3. ,
Система обмежень
Скористаємось теоремою
Якщо задача лінійного програмування в канонічній формі (7)-(9) має оптимальний план , то є оптимальним планом двоїстої задачі
, ,
Розв'язок:
Fmin*= 9,6;
Завдання 2. Задача цілочислового програмування
Для задачі із завдання 1, як для задачі цілочислового програмування, знайти розв'язки геометричним методом і методом Гоморі.
Розв?язання геометричним методом
,
Відповідь:
Розв?язання методом Гоморі
Наведемо останню симплекс-таблицю
|
I | базис | Cб | P0 | 2 | 3 | 0 | 0 | 0 | -M | |
| | | | P1 | P2 | P3 | P4 | P5 | P6 | |
1 | P1 | 2 | 6/5 | 1 | 0 | 1/5 | -2/5 | 0 | 0 | |
2 | P5 | 0 | 22/5 | 0 | 0 | 2/5 | 1/5 | 1 | -1 | |
3 | P2 | 3 | 36/5 | 0 | 1 | 1/5 | 3/5 | 0 | 0 | |
4 | | | 24 | 0 | 0 | 1 | 1 | 0 | 0 | |
5 | | | 0 | 0 | 0 | 0 | 0 | 0 | 1 | |
|
Побудуємо нерівність Гоморі за першим аргументом.
|
I | базис | Cб | P0 | 2 | 3 | 0 | 0 | 0 | 0 | |
| | | | P1 | P2 | P3 | P4 | P5 | P7 | |
1 | P1 | 2 | 6/5 | 1 | 0 | 1/5 | -2/5 | 0 | 0 | |
2 | P5 | 0 | 22/5 | 0 | 0 | 2/5 | 1/5 | 1 | 0 | |
3 | P2 | 3 | 36/5 | 0 | 1 | 1/5 | 3/5 | 0 | 0 | |
4 | P7 | 0 | -1/5 | 0 | 0 | -1/5 | -3/5 | 0 | 1 | |
5 | | | 24 | 0 | 0 | 1 | 1 | 0 | 0 | |
|
Обраний розв'язковий елемент (4,4)
|
I | базис | Cб | P0 | 2 | 3 | 0 | 0 | 0 | 0 | |
| | | | P1 | P2 | P3 | P4 | P5 | P7 | |
1 | P1 | 2 | 1 | 1 | 0 | 0 | -1 | 0 | 0 | |
2 | P5 | 0 | 4 | 0 | 0 | 0 | 11/5 | 1 | 0 | |
3 | P2 | 3 | 7 | 0 | 1 | 0 | 0 | 0 | 0 | |
4 | P4 | 0 | 2 | 0 | 0 | 1 | 3 | 0 | 1 | |
5 | | | 14 | 0 | 0 | 0 | 2 | 0 | 0 | |
|
Отриманий план являється оптимальним і цілочисельним.
Розв'язок: X*(1,7) Fmax*=23;
Відповідь: цілочисельною точкою максимуму даної задачі є точка (1,7)
Завдання 3. Задача дробово-лінійного програмування
Для задачі дробово-лінійного програмування знайти розв'язки геометричним методом і симплекс-методом:
,
Розв?язання геометричним методом
Визначимо, в яку сторону потрібно обертати пряму навколо початку координат, щоб значення цільової функції збільшувалось. Таким чином ми визначимо яка з крайніх точок є точкою максимуму.
f(1;0) = 2/3 f(0;1) = 3/7
Тобто при крутінні прямої проти годинникової стрілки значення цільової функції зменшується.
Використаємо результати обчислень і геометричних побудов з попереднього завдання.
З графіка очевидно, що розв'язок лежить на перетині двох прямих. Для визначення точки перетину прямої І та ІІ розв?яжемо систему з двох рівнянь.
Відповідь: функція набуває максимального значення при x1=6/5, x2=36/5.
Розв?язання симплекс-методом
Перейдемо від задачі дробово-лінійного програмування до задачі лінійного програмування.
Вводим заміну:
Вводим ще одну заміну:
Після замін наша задача має такий вигляд:
Приведемо її до канонічної форми і доповнимо її базисами:
Повернемось до заміни:
x1=0 x2=6
Завдання 4. Транспортна задача
Для заданих транспортних задач скласти математичну модель і розв'язати їх методом потенціалів, використавши для визначення початкового плану метод мінімального елемента або північно-західного кута.
1. Запаси деякого однорідного продукту знаходяться на трьох пунктах постачання (базах) A1, A2, A3 і цей продукт потрiбно доставити в три пункти споживання (призначення) B1, B2, B3. Задача полягає в тому, щоб визначити, яку кiлькiсть продукту потрiбно перевезти з кожного пункту постачання (бази) до кожного пункту споживання (призначення) так, щоб забезпечити вивезення всього наявного продукту з пунктів постачання, задовільнити повністю потреби кожного пункту споживання і при цьому сумарна вартiсть перевезень була б мiнiмальною (зворотні перевезення виключаються). Вартість перевезень сij (у грн.) з бази Аi до пункту призначення Bj вказана в таблиці, де також наведені дані про запаси ai (у тонанх) продукту і його потреби (у тонах) bj.
|
Пункти | Пункти споживання | Запаси | |
постачання | B1 | B2 | B3 | | |
A1 | 3 | 5 | 7 | 270 | |
A2 | 6 | 9 | 4 | 180 | |
A3 | 11 | 8 | 10 | 300 | |
Потреби | 260 | 280 | 300 | | |
|
Для даної транспортної задачі не виконується умова балансу , тому введемо додатковий пункт постачання з запасами 840-750=90 і тарифами С4s=0 (i=1,2,3). Тоді одержимо замкнену транспортну задачу, яка має розв'язок. Її математична модель має вигляд:
хi,
j 0, 1 i 4, 1 j 3.
|
Пункти | Пункти споживання | Запаси | |
постачання | B1 | B2 | B3 | | |
A1 | 3 | 5 | 7 | 270 | |
A2 | 6 | 9 | 4 | 180 | |
A3 | 11 | 8 | 10 | 300 | |
A4 | 0 | 0 | 0 | 90 | |
Потреби | 260 | 280 | 300 | 840 840 | |
|
За методом північно-західного кута знайдемо опорний план
|
Пункти | Пункти споживання | Запаси | |
постачання | B1 | B2 | B3 | | |
A1 | 3 260 | 5 10 | 7 | 270 | |
A2 | 6 | 9 180 | 4 | 180 | |
A3 | 11 | 8 90 | 10 210 | 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=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 с.
