убування цільової функції, тобто в напрямку антіградіента.
Граничне положення - лінія (5). Отже, точка А є оптимальним рішенням, що забезпечує мінімальне значення цільової функції.
Визначимо координати точки В як перетин прямих (2) і (3):
Отже, максимальне значення цільова функція досягає в точці і одно.
Визначимо координати точки А як перетин прямих (2) і осі Ох1:
Отже, мінімальне значення цільова функція досягає в точці і одно.
Завдання 3
Вирішити симплексним методом завдання:
Рішення.
Запишемо цю задачу у формі основної задачі лінійного програмування. Для цього перейдемо від обмежень-нерівностей до обмежень-равенствам. Введемо трьох додаткові змінні, в результаті чого обмеження запишуться у вигляді системи рівнянь
Введемо штучні змінні x:
Для постановки задачі на максимум цільову функцію запишемо так:
Z (X)=x1 + 4x2 + x3 - Mx6 - Mx7? max
З рівнянь висловлюємо штучні змінні і підставимо в цільову функцію:
x6=4 + x1 - 2x2 - x37=6 - 2x1 - 3x2 - x3 + x5 (X)=x1 + 4x2 + x3 - M (4 + x1 - 2x2 - x3) - M (6 - 2x1 - 3x2- x3 + x5)? max (X)=(1 + M) x1 + (4 + 5M) x2 + (1 + 2M) x3 + (- M) x5 + (- 10M)? max
Вирішимо систему рівнянь щодо базисних змінних: x6, x4, x7.
Вважаючи, що вільні змінні рівні 0, отримаємо перші опорний план: X1=(0,0,0,9,0,4,6)
азісBx 1 x 2 x 3 x 4 x 5 x 6 x 7 x 6 4 - 1210010 x 4 93121000 x 7 62310 - 101 Z (X0) - 10M - 1 - M - 4 - 5M -1 - 2M0M00
Поточний опорний план не оптимальний, оскільки в індексному рядку знаходяться негативні коефіцієнти.
В якості ведучого виберемо стовпець, відповідний змінної x 2, так як це найбільший коефіцієнт за модулем.
Обчислимо значення D i по рядках як частка від ділення: bi/a i2
і з них виберемо найменше: min (4: 2, 9: 1, 6: 3)=2
Отже, перша рядок є провідною.
Отримуємо нову симплекс - таблицю:
БазісBx 1 x 2 x 3 x 4 x 5 x 6 x 7 x 2 2 - 0.510.5000.50 x 4 73.501.510 - 0.50 x 7 03.50 - 0.50 - 1 - 1.51 Z (X 1) 8 - 3 - 3.5M01 + M0M2 + 2.5M0
Поточний опорний план не оптимальний, оскільки в індексному рядку знаходяться негативні коефіцієнти.
В якості ведучого виберемо стовпець, відповідний змінної x 1, так як це найбільший коефіцієнт за модулем.
Обчислимо значення D i по рядках як частка від ділення: bi/a i1
і з них виберемо найменше:
(-, 7: 3.5, 0: 3.5)=0
Отже, 3-ий рядок є провідною.
Отримуємо нову симплекс - таблицю:
БазісBx 1 x 2 x 3 x 4 x 5 x 6 x 7 min x 2 2013/70 - 1/72/71/7 - x 4 7002111 - 1 7 x 1010 - 1/70 - 2/7 - 3/72/7 - Z (X3) 8004/70 - 6/75/7 + M6/7 + M0
Поточний опорний план не оптимальний, оскільки в індексному рядку знаходяться негативні коефіцієнти.
В якості ведучого виберемо стовпець, відповідний змінної x 5, так як це найбільший коефіцієнт за модулем.
Обчислимо значення D i по рядках як частка від ділення: bi/a i5
і з них виберемо найменше:
(-, 7: 1, -)=7
Отже, другий рядок є провідною.
Отримуємо нову симплекс - таблицю:
БазісBx 1 x 2 x 3 x 4 x 5 x 6 x 7 x 2301 5/7 1/7 0 3/7 0 x 5 7002111 - 1 x 1210 3/7 2/7 0 - 1/7 0 Z (X3) 14002 2/7 6/7 01 4/7 + MM
Серед значень індексного рядка немає негативних. Тому ця таблиця визначає оптимальний план задачі.
Так як в оптимальному рішенні відсутні штучні змінні (дорівнюють нулю) то дане рішення є допустимим.
Оптимальний план можна записати так: x 2=3, x 1=2.
Тоді Z max=4 * 3 + 1 * 2=14.
Завдання 4
Вирішити методом потенціалів транспортні завдання:
12345Всего115793102464713203153491042421033053256410всего1010252530
Рішення.
Перевіримо рівність запасів і потреб:
;
.
Рівність не виконується (), отже, транспортна задача є відкритою. Зведемо її до закритої моделі шляхом введення фіктивного постачальника. Покладемо його запас рівним дефіцит...