Умова
F(x1,x2) = 3x1 + 6x2 
max;
x 1 + x 2 
8,
3x 1 + 7 x 2 
21,
x 1 + 2 x 2 6,
0 x 1 7, 0 x 2 7.
Тут розглядається варіант зі снаходженням оптимального плану для max.
Для побудови першого опорного плану систему нерівностей приведемо до системи рівностей шляхом введення додаткових змінних (перехід до канонічної формі).
В 1-й нерівності типу (≤) вводимо базисну змінну x3. В 2-й нерівності типу (≥) вводимо базисну змінну x4 зі знаком мінус. У 3-й нерівності типу (≥) вводимо базисну змінну x5 зі знаком мінус.
1x1 + 1x2 + 1x3 + 0x4 + 0x5 = 8
3x1 + 7x2 + 0x3-1x4 + 0x5 = 21
1x1 + 2x2 + 0x3 + 0x4-1x5 = 6
Введемо штучні змінні x: в 2-e рівність вводимо змінну x6; в 3-у рівність вводимо змінну x7;
1x1 + 1x2 + 1x3 + 0x4 + 0x5 + 0x6 + 0x7 = 8
3x1 + 7x2 + 0x3-1x4 + 0x5 + 1x6 + 0x7 = 21
1x1 + 2x2 + 0x3 + 0x4-1x5 + 0x6 + 1x7 = 6
Для постановки задачі на максимум цільову функцію запишемо так:
F (X) = 3x1 +6 x2 - Mx6 - Mx7 → max
За використання штучних змінних, що вводяться у цільову функцію, накладається так званий штраф величиною М, дуже велике позитивне число, яке зазвичай не задається.
Отриманий базис називається штучним, а метод рішення називається методом штучного базису.
Причому штучні змінні не мають відношення до змісту поставленого завдання, однак вони дозволяють побудувати стартову точку, а процес оптимізації змушує ці змінні приймати нульові значення та забезпечити допустимість оптимального рішення.
З рівнянь виражаємо штучні змінні:
x6 = 21-3x1-7x2+x4
x7 = 6-x1-2x2+x5
які підставимо в цільову функцію:
F(X) = 3x1 + 6x2 - M(21-3x1-7x2+x4) - M(6-x1-2x2+x5) → max
або
F(X) = (3+4M)x1+(6+9M)x2+(-1M)x4+(-1M)x5+(-27M) → max
Матриця коефіцієнтів A = a (ij) цієї системи рівнянь має вигляд:
| -1 | ||||||
| -1 |
Базисні перемінні це змінні, які входять тільки в одне рівняння системи обмежень і при цьому з одиничним коефіцієнтом.
Вирішимо систему рівнянь щодо базисних змінних:
x3, x6, x7,
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:
X1 = (0,0,8,0,0,21,6)
Базисне рішення називається допустимим, якщо воно невід’ємне.
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| x3 | ||||||||
| x6 | -1 | |||||||
| x7 | -1 | |||||||
| F(X0) | -27M | -3-4M | -6-9M | 1M | 1M |
Переходимо до основного алгоритму симплекс-методу.
Ітерація № 1.
| Крок1 | ||||||||
| Базис | БП | x 1 | x 2 | x 3 | x 4 | x 5 | X6 | x7 |
| x3 | ||||||||
| X6 | -1 | |||||||
| X7 | -1 | |||||||
| F(x) | -27M | -4M-3 | -9M-6 | M | M |
Перерахунок симплекс-таблиці.
Формуємо наступну частину симплексного таблиці.
Замість змінної x до таблиці 1 увійде змінна x2.
Рядок, відповідної змінної x2 в плані(таблиці) 2, отриманої в результаті поділу всіх елементів рядка x6 таблиці 1 на дозвільний (той який стоїть на перетині рядків) елемент ДЕ = 7
На місці дозвільного елемента в таблиці(плані) 1 отримуємо 1.
В інших клітинах стовпця x2 плану 1 записуємо нулі.
Таким чином, у новому плані 1 заповнюю рядок x2 і стовпець x2.
Всі інші елементи нового плану 1, включаючи елементи індексного рядка, визначаються за правилом прямокутника.
Для цього вибираємо зі старого плану(таблиці 1) чотири числа, які розташовані у вершинах прямокутника і завжди включають дозвільний елемент ДЕ.
Зроблю розрахунок кожного елемента у вигляді таблиці:
| Крок 2 | ||||||||
| Базис | B | x 1 | x 2 | x 3 | x 4 | x 5 | x6 | X7 |
| x3 | 4/7 | 1/7 | -1/7 | |||||
| x2 | 3/7 | -1/7 | 1/7 | |||||
| X7 | 1/7 | 2/7 | -1 | -2/7 | ||||
| F(X) | -1/7M-3/7 | -2/7M-6/7 | M | 9/7M+6/7 |
Отримуємо нову симплекс-таблицю:
| Крок 3 | ||||||||
| Базис | B | x 1 | x 2 | x 3 | x 4 | x 5 | X6 | x7 |
| x3 | 1/2 | 1/2 | -1/2 | |||||
| x2 | 1/2 | -1/2 | 1/2 | |||||
| x4 | 1/2 | -7/2 | -1 | 7/2 | ||||
| F(X) | -3 | M | M+3 |
Перерахунок симплекс-таблиці.
| Крок 4 | ||||||||
| Базис | B | x 1 | x 2 | x 3 | x 4 | x 5 | X6 | X7 |
| x5 | -1 | |||||||
| x2 | ||||||||
| x4 | -1 | |||||||
| F(X3) | M | M |
Отже отримали нову симплекс-таблицю:
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| x5 | -1 | |||||||
| x2 | ||||||||
| x4 | -1 | |||||||
| F(X3) | 1M | 1M |
Оптимальний план запишемо так:
x5 = 10
x2 = 8
x4 = 35
F(X) = 6•8 = 48
3. Розв’язання з допомогою пакету програм SimplexWin
Cимплекс метод з додаванням змінних, розв’язаний за допомогою сиплекс таблиць.
Ввід даних:
Крок 1
Крок 2
Крок 3
Крок 4
Результат:
4. Розв’язання за допомогою власної програми.
Програма написана мовою С++
Для правильного вирішення система лінійних обмежень повинна бути приведена до канонічного виду.
При запуску програми потрібно ввести кількість рівнянь обмежень (rows) і найбільший індекс змінної (cols).
Після цього потрібно послідовно ввести коефіцієнти рівнянь (xi) та їх праві частини (b), а також коефіцієнти цільової функції. Якщо який-небудь коефіцієнт відсутній, слід ввести нуль.
Для виведення результату потрібно натиснути пробіл.
Якщо для вирішення завдання були введені додаткові перемінні або штучні базиси, то їх потрібно виключити з підсумкового відповіді.
Дата добавления: 2015-11-14; просмотров: 55 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Жордана -Гауса. | | | Лістинг програми main.cpp |