[ Лінійне програмування 3 лютого ] | 7 | - 7 | - 1 | -15 |
-2 | - 6 | 5 | 1 | 9 | |
1 | 2 | -1 | 1 | 0 | |
-1 | - 3 | 3 | -2 | 6 | |
4 | 9 | - 8 | 1 | -15 |
-2 / 5 | -6 / 5 | 1 / 5 | 1 / 5 | 9 / 5 | |
3 / 5 | 4 / 5 | 1 / 5 | 6 / 5 | 9 / 5 | |
1 / 5 | 3 / 5 | -3 / 5 | -13 / 5 | 3 / 5 | |
4 / 5 | -3 / 5 | 8 / 5 | 13 / 5 | -3 / 5 |
0 | 2 | -1 | -5 | 3 | |
1 / 3 | -4 / 3 | 1 | 14 / 3 | 1 | |
1 / 3 | 5 / 3 | -1 | -13 / 3 | 1 | |
1 | 1 | 1 | 0 | 0 |
У нижньому рядку останньої симплекс-таблиці немає негативних елементів, отже, мінімум допоміжної цільової функції досягнутий і є кутова точка допустимого безлічі вихідної задачі лінійного програмування, тоді
Відповідь: і .
Завдання 8 (16.237)
Вирішити повністю цілочисельну задачу лінійного програмування методом Гоморі.
Рішення:
Введемо додаткові змінні і запишемо умову допоміжної задачі лінійного програмування для розглянутого випадку:
Вважаючи додаткові змінні базисними, запишемо симплекс таблицю цього завдання, відповідну кутовий точці :
1 | 0 | 2 | 1 | 8 | |
1 | 1 | 0 | -1 | 4 | |
-1 | 2 | 1 | 3 | 6 | |
-1 | -3 | -3 | -3 | -18 |
Зробимо перетворення вихідної симплекс-таблиці симплекс-методом наступним чином: дивимося на нижній рядок - вибираємо той стовпець, в якому нижній елемент негативний, якщо таких стовпців кілька, то вибираємо будь-який (у нашому випадку вибираємо перший стовпець ), Далі дивимося на останній і вибраний стовпці - порівнюємо відносини елементів останнього і вибраного стовпців (у вибраному стовпці беремо тільки позитивні числа), і вибираємо той елемент вибраного стовпця, де ставлення елементів буде найменшим (в нашому випадку 9 / 3 і 0 / 1 , так як друге ставлення найменше, отже, опорним елементом буде 1); міняємо місцями змінні і , Інші змінні залишаємо на своїх місцях; на місце опорного елемента ставимо ставлення 1 / (опорний елемент); а інших місцях роздільної рядка записуємо відповідні елементи вихідної таблиці, поділені на опорний елемент; на вільні місця дозволяє стовпця ставимо зі знаком мінус відповідні елементи вихідної таблиці , поділені на опорний елемент; залишилися вільні місця в новій симплекс-таблиці заповнюємо порядково наступним чином: з рядка елементів вихідної таблиці віднімаємо твір її елемента з дозволяючого стовпця на вже заповнену роздільну рядок нової таблиці. Виробляючи перетворення симплекс-методу, отримаємо таку послідовність симплекс-таблиць:
4 / 3 | -2 / 3 | 5 / 3 | -1 / 3 | 6 | |
2 / 3 | 5 / 3 | 1 / 3 | 1 / 3 | 6 | |
-1 / 3 | 2 / 3 | 1 / 3 | 1 / 3 | 2 | |
-2 | -1 | -2 | 1 | -12 |
1 | 1 | 2 | 0 | 8 | |
3 / 2 | -5 / 2 | -1 / 2 | -1 / 2 | 1 | |
-1 / 2 | 3 / 2 | 1 / 2 | 1 / 2 | 3 | |
-5 / 2 | 3 / 2 | -3 / 2 | 3 / 2 | -9 |
1 / 2 | 1 / 2 | 1 / 2 | 0 | 4 | |
7 / 4 | -9 / 4 | 1 / 4 | -1 / 2 | 3 | |
-3 / 4 | 5 / 4 | -1 / 4 | 1 / 2 | 1 | |
-7 / 4 | 9 / 4 | 3 / 4 | 3 / 2 | -3 |
-2 / 7 | 8 / 7 | 3 / 7 | 1 / 7 | 22 / 7 | |
4 / 7 | -9 / 7 | 1 / 7 | -2 / 7 | 12 / 7 | |
3 / 7 | 2 / 7 | -1 / 7 | 2 / 7 | 16 / 7 | |
1 | 0 | 1 | 1 | 0 |
Як бачимо, в останньому рядку таблиці всі елементи позитивні, тобто отримуємо рішення і . Але це рішення не задовольняє умові цілочисельності, тому доповнюємо останню симплекс-таблицю рядком, використовуючи наступні правила: серед нецілих елементів вибирається довільний елемент , По r-ої рядку симплекс-таблиці складається додаткове обмеження виду (Тут ми вважаємо, що вільні змінні мають номери m +1, ..., n). За допомогою допоміжної змінної це обмеження представляється у вигляді рівності і вводиться в симплекс-таблицю додаткової рядком
Де
,
де фігурні дужки означають дробову частину.
Таким чином, ми отримуємо таку таблицю:
-2 / 7 | 8 / 7 | 3 / 7 | 1 / 7 | 22 / 7 | |
4 / 7 | -9 / 7 | 1 / 7 | -2 / 7 | 12 / 7 | |
3 / 7 | 2 / 7 | -1 / 7 | 2 / 7 | 16 / 7 | |
2 / 7 | -1 / 7 | -3 / 7 | -1 / 7 | -1 / 7 | |
1 | 0 | 1 | 1 | 0 |
Так як , То після доповнення рядком симплекс-таблиця перестає відповідати допустимому базисного вирішення завдання лінійного програмування, яку вона описує.
Для переходу до допустимого базисного рішенням проводяться наступні операції:
а) рядок з негативним вільним членом вважається роздільної;
б) якщо всі коефіцієнти , То задача не має рішення, у противному випадку номер l дозволяє стовпця знаходиться з умови:
в) відбувається перетворення симплекс-таблиці з опорним елементом
Якщо в новій таблиці, як і раніше є хоча б один негативний вільний член, то описана процедура повторюється, починаючи з операції а), необхідне число разів.
Застосовуючи ці правила до нашої симплекс-таблиці, ми отримуємо такі перетворення:
-2 / 7 | 8 / 7 | 3 / 7 | 1 / 7 | 22 / 7 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4 / 7 | -9 / 7 | 1 / 7 | -2 / 7 | 12 / 7
Отримана симплекс-таблиця не тільки відповідає допустимому базисного вирішення, а й дає вирішення розглянутої задачі: і Відповідь: і Задача 9 (16.258) Вирішити завдання дробово - лінійного програмування.
Знаменник цільової функції позитивний попри всі x з допустимого безлічі U, так як . Вводимо нові змінні , , і отримуємо таку завдання лінійного програмування:
Невідомі параметри ми можемо вже з цих висловів знайти:
, Відповідь: , Завдання 10 (16.268) Вирішити завдання квадратичного програмування. ,
Рішення: Матриця нашої квадратичної функції позитивно визначена. Наша вихідна задача має вигляд: (1) , , (2) , . (3) На підставі теореми Куна-Таккера точка мінімуму цільової функції з (1) на допустимому безлічі (2) і (3) може бути знайдена як рішення наступної системи рівнянь з додатковими змінними ; : , , , , , , , , задовольняє умові неотрицательности: , , , , . Застосовуючи вище описані умови, ми перетворимо вихідну задачу в такий вигляд:
Будемо шукати кутову точку безлічі, що визначається цією системою, методом штучного базису. Введемо додаткові змінні і в 3-е і четверте рівняння вище написаної системи, вважаючи базисними змінними початкової кутової точки , , і . Допоміжну цільову функцію виразимо через вільні змінні , , , , і за допомогою двох перших рівнянь вище написаної системи. Послідовність симплекс-таблиць, що призводять до вирішення завдання, наведена нижче. Рамками обведені опорні елементи, а ті вільні змінні, які на даному кроці можна переносити в базисні через умови , Обведені гуртками. Як бачимо, в останньому рядку немає негативних чисел, отже, ми знайшли рішення і воно має вигляд і . Відповідь: і Будь ласка, не зберігайте тестовий текст. |