z= 3x1 + x2 ® max
Розв’язок.
1. Приведемо задану модель до канонічного вигляду.
Для перетворення обмежень-нерівностей в рівняння:
а) оскільки права частина третього обмеження від’ємна, домножаємо обидві
частини рівняння на (–1);
б) до лівої частини перших трьох нерівностей додаємо додаткові змінні , , відповідно, а від лівої частини четвертої нерівності віднімемо , які ввійдуть у функцію мети з коефіцієнтом 0;
z= 3x1 + x2 + 0х3 + 0х4 + 0х5 + 0х6 ® max
2. Знайдемо допустимий базисний розв’язок.
Оскільки в четвертому обмеженні немає базисних змінних (немає змінних з коефіцієнтом +1, яких немає в інших рівняннях), то до лівої частини додаємо штучну невід’ємну зміну х7.
z= 3x1 + x2 + 0х3 + 0х4 + 0х5 + 0х6 – Mx7 ® max
ДБР х1 = 0, х2 = 0, х6 = 0 – вільні змінні,
х3 = 1, х4 = 7, х5 = 4, х7 = 6 – базисні змінні.
3. Заповнення першої симплекс-таблиці.
i | xбаз | сбаз | –М | b | q | ||||||
х1 | х2 | х3 | х4 | х5 | х6 | х7 | |||||
х3 | –1 | ||||||||||
х4 | 7/2 | ||||||||||
х5 | –1 | 4/2 | |||||||||
х7 | –М | –1 | 6/6 | ||||||||
–3 | –1 | ||||||||||
–2М | –6М | М | –6М |
4. Перевірка отриманого ДБР на оптимальність
План х3 = 1, х4 =7, х5 = 4, х7 = 6 не оптимальний, оскільки D1 = –2М – 3 < 0,
D2 = –6М – 1 < 0. Вводимо в базис х2, оскільки D2 найменше від’ємне. Виводимо
з базису х7, оскільки q4 = 1 найменше додатнє.
5. Перехід до наступної ітерації
Заповнюємо наступну симплекс-таблицю, перераховуючи її елементи за правилами Жорданових виключень з головним елементом аrk (ark = а42 = 6).
Зауваження. Після виведення з базису штучної змінної х7 можна стовбчик при змінній х7 не обчислювати.
i | xбаз | сбаз | –М | b | q | ||||||
х1 | х2 | х3 | х4 | х5 | х6 | х7 | |||||
х3 | 8/6 | –1/6 | 12/8 | ||||||||
х4 | 2/6 | 2/6 | 30/2 | ||||||||
х5 | –10/6 | 2/6 | |||||||||
х2 | 2/6 | –1/6 | 6/2 | ||||||||
–16/6 | –1/6 | ||||||||||
План х3 = 2, х4 = 5, х5 = 2, х2 = 1 не оптимальний, оскільки D1 = –16/6 < 0,
D6 = –1/6 < 0. Вводимо в базис х1, оскільки D1 найменше від’ємне. Виводимо з базису х3, оскільки q1 = 12/8 найменше додатнє.
Заповнюємо наступну симплекс-таблицю, перераховуючи її елементи за правилами Жорданових виключень з головним елементом аrk (ark = а11 = 8/6).
i | xбаз | сбаз | –М | b | q | ||||||
х1 | х2 | х3 | х4 | х5 | х6 | х7 | |||||
х1 | 6/8 | –1/8 | 12/8 | ||||||||
х4 | –2/8 | 3/8 | 36/8 | ||||||||
х5 | –10/8 | 1/8 | 36/8 | ||||||||
х2 | –2/8 | –1/8 | 4/8 | ||||||||
16/8 | –4/8 | 40/8 | |||||||||
План х1 =12/8, х2 = 4/8, х4 = 36/8, х5 = 36/8 не оптимальний, оскільки
D6 = –4/8 < 0. Вводимо в базис х6, оскільки D6 від’ємне. Виводимо з базису х4, оскільки найменьше додатнє.
Заповнюємо наступну симплекс-таблицю, перераховуючи її елементи за правилами Жорданових виключень з головним елементом аrk (ark = а26 = 3/8).
i | xбаз | сбаз | –М | b | q | ||||||
х1 | х2 | х3 | х4 | х5 | х6 | х7 | |||||
х1 | 2/3 | 1/3 | |||||||||
х6 | –2/3 | 8/3 | |||||||||
х5 | 4/3 | –1/3 | |||||||||
х2 | –1/3 | 1/3 | |||||||||
5/3 | 4/3 | ||||||||||
План х1 = 3, х2 = 2, х3 = 0, х4 = 0, х5 = 3, х6 = 12 оптимальний, оскільки
Dj ³ 0, j = . Zmax = 11.
ЛАБОРАТОРНА РОБОТА № 7