Математичне програмування (стр. 2 из 3)
Межі області
Цільова функція F(x) => min
Розглянемо цільову функцію завдання F = 7X1+5X2 => min.
Побудуємо пряму, що відповідає значенню функції F = 0: F = 7X1+5X2 = 0. Будемо рухати цю пряму паралельним чином. Оскільки нас цікавить мінімальне рішення, тому рухався прямо до першого торкання позначеної області. На графіку ця пряма позначена пунктирною лінією.
Рівний масштаб
Перетином півплощини буде область, яка представляє собою багатокутник, координати точок якого задовольняють умові нерівностей системи обмежень задачі.
Пряма F(x) = const перетинає область у точці A. Оскільки точка A отримана в результаті перетину прямих 4 i 3, то її координати задовольняють рівнянням цих прямих:
x2=0
3x1-5x2≥11
Вирішивши систему рівнянь, одержимо: x1 = 3.6667, x2 = 0
Звідки знайдемо мінімальне значення цільової функції:
F(X) = 7*3.6667 + 5*0 = 25.67
Розв’язок методом симплексних таблиць.
Вирішимо пряму задачу лінійного програмування симплексним методом, з використанням симплексної таблиці.
Визначимо мінімальне значення цільової функції F(X) = 7x1+5x2 за таких умов-обмежень.
2x1+4x2≥1
5x1-x2≤42
3x1-5x2≥11
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних (перехід до канонічної форми).
2x1 + 4x2-1x3 + 0x4 + 0x5 = 1
5x1-1x2 + 0x3 + 1x4 + 0x5 = 42
3x1-5x2 + 0x3 + 0x4-1x5 = 11
Введемо штучні змінні x.
2x1 + 4x2-1x3 + 0x4 + 0x5 + 1x6 + 0x7 = 1
5x1-1x2 + 0x3 + 1x4 + 0x5 + 0x6 + 0x7 = 42
3x1-5x2 + 0x3 + 0x4-1x5 + 0x6 + 1x7 = 11
Для постановки завдання на мінімум цільову функцію запишемо так:
F(X) = 7x1+5x2+Mx6+Mx7 => min
Отриманий базис називається штучним, а метод рішення називається методом штучного базису.
Причому штучні змінні не мають відношення до змісту поставленого завдання, однак вони дозволяють побудувати стартову точку, а процес оптимізації змушує ці змінні приймати нульові значення та забезпечити допустимість оптимального рішення.
З рівнянь висловлюємо штучні змінні:
x6 = 1-2x1-4x2+x3
x7 = 11-3x1+5x2+x5
які підставимо в цільову функцію:
F(X) = 7x1 + 5x2 + M(1-2x1-4x2+x3) + M(11-3x1+5x2+x5) => min
або
математичний модель лінійний програмування
F(X) = (7-5M)x1+(5+1M)x2+(1M)x3+(1M)x5+(12M) => min
Матриця коефіцієнтів A = a(ij) цієї системи рівнянь має вигляд:
| 2 | 4 | -1 | 0 | 0 | 1 | 0 |
| 5 | -1 | 0 | 1 | 0 | 0 | 0 |
| 3 | -5 | 0 | 0 | -1 | 0 | 1 |
Базисні перемінні це змінні, які входять тільки в одне рівняння системи обмежень і притому з одиничним коефіцієнтом.
Вирішимо систему рівнянь відносно базисних змінних:
x6, x4, x7,
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:
X1 = (0,0,0,42,0,1,11)
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| 0 | x6 | 1 | 2 | 4 | -1 | 0 | 0 | 1 | 0 |
| x4 | 42 | 5 | -1 | 0 | 1 | 0 | 0 | 0 | |
| x7 | 11 | 3 | -5 | 0 | 0 | -1 | 0 | 1 | |
| Індексний рядок | F(X0) | 12M | -7+5M | -5-1M | -1M | 0 | -1M | 0 | 0 |
Переходимо до основного алгоритму симплекс-методу.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | x7 | min |
| 1 | x6 | 1 | 2 | 4 | -1 | 0 | 0 | 1 | 0 | 0.5 |
| x4 | 42 | 5 | -1 | 0 | 1 | 0 | 0 | 0 | 8.4 | |
| x7 | 11 | 3 | -5 | 0 | 0 | -1 | 0 | 1 | 3.67 | |
| Індексний рядок | F(X1) | 12M | -7+5M | -5-1M | -1M | 0 | -1M | 0 | 0 | 0 |
Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться позитивні коефіцієнти
В якості ведучого виберемо стовпець, відповідної змінної x1, так як це найбільший коефіцієнт .
Обчислимо значення Di по рядках як частку від ділення
і з них виберемо найменше:
Отже, 1-ий рядок є ведучим
Дозвільний елемент дорівнює 2 і знаходиться на перетині ведучого стовпця і головною рядка
Формуємо наступну частину симплексної таблиці.
Замість змінної x6 в план 1 увійде змінна x1
Рядок, відповідної змінної x1 в плані 1, отриманий в результаті поділу всіх елементів рядка x6 плану 0 на дозвільний елемент ДЕ=2
На місці дозвільного елемента в плані 1 отримуємо 1.
В інших клітинах стовпця x1 плану 1 записуємо нулі.
Таким чином, у новому плані 1 заповнені рядок x1 і стовпець x1 .
Всі інші елементи нового плану 1, включаючи елементи індексного рядка, визначаються за правилом прямокутника.
Для цього вибираємо зі старого плану чотири числа, які розташовані в вершинах прямокутника і завжди включають дозвільний елемент ДЕ.
НE = СE - (А*В)/ДE
СДЕ - елемент старого плану, ДЕ - дозвільний елемент (2), А і В - елементи старого плану, що утворюють прямокутник з елементами СДЕ і ДЕ.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | x7 | min |
| 2 | x1 | 0.5 | 1 | 2 | -0.5 | 0 | 0 | 0.5 | 0 | 0 |
| x4 | 39.5 | 0 | -11 | 2.5 | 1 | 0 | -2.5 | 0 | 15.8 | |
| x7 | 9.5 | 0 | -11 | 1.5 | 0 | -1 | -1.5 | 1 | 6.33 | |
| Індексний рядок | F(X2) | 3.5+9.5M | 0 | 9-11M | -3.5+1.5M | 0 | -1M | 3.5-2.5M | 0 | 0 |
Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться позитивні коефіцієнти
В якості ведучого виберемо стовпець, відповідної змінної x3, так як це найбільший коефіцієнт .
Обчислимо значення Di по рядках як частку від ділення
і з них виберемо найменше:
Отже, 3-ий рядок є ведучим
Дозвільний елемент дорівнює 1.5 і знаходиться на перетині ведучого стовпця і головною рядка
Формуємо наступну частину симплексної таблиці.
Замість змінної x7 в план 2 увійде змінна x3
Рядок, відповідної змінної x3 в плані 2, отримана в результаті поділу всіх елементів рядка x7 плану 1 на дозвільний елемент ДЕ=1.5
На місці дозвільного елемента в плані 2 отримуємо 1.
В інших клітинах стовпця x3 плану 2 записуємо нулі.
Таким чином, у новому плані 2 заповнені рядок x3 і стовпець x3 .
Всі інші елементи нового плану 2, включаючи елементи індексного рядка, визначаються за правилом прямокутника.
Кінець ітерацій: індексний рядок не містить негативних елементів - знайдений оптимальний план
Остаточний варіант симплекс-таблиці:
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| 3 | x1 | 3.67 | 1 | -1.67 | 0 | 0 | -0.3333 | 0 | 0.3333 |
| x4 | 23.67 | 0 | 7.33 | 0 | 1 | 1.67 | 0 | -1.67 | |
| x3 | 6.33 | 0 | -7.33 | 1 | 0 | -0.6667 | -1 | 0.6667 | |
| Індексний рядок | F(X3) | 25.67 | 0 | -16.67 | 0 | 0 | -2.33 | -1M | 2.33-1M |
Оптимальний план можна записати так:
x1 = 3.67
x4 = 23.67
x3 = 6.33
F(X) = 7*3.67 = 25.67
Складемо двоїсту задачу до прямої задачі.
2y1+5y2+3y3≤7
4y1-y2-5y3≤5
y1+42y2+11y3 => max
y1 ≥ 0
y2 ≤ 0
y3 ≥ 0
Рішення двоїстої задачі дає оптимальну систему оцінок ресурсів.
Використовуючи останню інтерпретацію прямої задачі знайдемо, оптимальний план двоїстої задачі.
З першої теореми двоїстості випливає, що Y = C*A-1.
Складемо матрицю A з компонентів векторів, що входять в оптимальний базис.
Визначивши зворотну матрицю А-1 через алгебраїчні доповнення, отримаємо:
Як видно з останнього плану симплексної таблиці, зворотна матриця A-1 розташована в стовпцях додаткових змінних .
Тоді Y = C*A-1 =
Оптимальний план двоїстої задачі дорівнює:
y1 = 0
y2 = 0
y3 = 2.33
Z(Y) = 1*0+42*0+11*2.33 = 25.67
Завдання 3
Знайти початковий розв’язок транспортної задачі методом «північно-західного кута» і мінімальної вартості. Вибравши один із знайдених початкових розв’язків, знайти оптимальний розв’язок транспортної задачі.
| 3 | 5 | 1 | 4 | 200 |
| 4 | 1 | 2 | 3 | 140 |
| 1 | 2 | 3 | 5 | 160 |
| 90 | 110 | 220 | 80 | 500 |
Розв’язок
Побудова математичної моделі. Нехай xij — кількість продукції, що перевозиться з і-го пункту виробництва до j-го споживача
. Перевіримо необхідність і достатність умов розв'язання задачі: 
Умова балансу дотримується. Запаси рівні потребам. Отже, модель транспортної задачі є закритою.
Занесемо вихідні дані у таблицю.
| В1 | В2 | В3 | В4 | Запаси | |
| А1 | 3 | 5 | 1 | 4 | 200 |
| А2 | 4 | 1 | 2 | 3 | 140 |
| А3 | 1 | 2 | 3 | 5 | 160 |
| Потреби | 90 | 110 | 220 | 80 |
Розпочинаємо будувати математичну модель даної задачі:
Економічний зміст записаних обмежень полягає в тому, що весь вантаж потрібно перевезти по пунктах повністю.
Аналогічні обмеження можна записати відносно замовників: вантаж, що може надходити до споживача від чотирьох баз, має повністю задовольняти його попит. Математично це записується так: