2015-06-30
1253
Метод потенціалів використовується для знаходження оптимального розв’язку транспортної задачі. Якщо методи знаходження початкового розв’язку були першим кроком загального алгоритму пошуку, то цей метод є його 2-м і 3-м кроком.
Розв’яжемо нашу задачу, використовуючи початковий розв’язок, який отримано за допомогою методу північно-західного кута (рис. 3). Як нам вже відомо, цей розв’язок не є оптимальним.
При розв’язуванні симплекс-методом мінімізацію цільової функції
можна представити як максимізацію
У симплекс-таблиці на рис. 7а коефіцієнти при базисних змінних у рядку Z (значення яких перед застосуванням методу дорівнюють 6, 8, 5, 6, 1, 2) мають дорівнювати нулю. На рис. 7б показано симплекс таблицю збалансованої транспортної задачі загального вигляду.
Рис. 7а
Рис. 7б
Якщо подивитися на симплекс-таблицю, то у ній у кожному стовпчику знаходяться по дві одиниці. Тому кожному рядку i та кожному стовпчику j транспортної таблиці ставиться у відповідність числа (потенціали) ui та vj. Іншими словами, кожний рядок симплекс таблиці, що відповідає пропозиції, помножується на відповідне ui (і – номер пропозиції), а кожний рядок симплекс таблиці, що відповідає попиту, помножується на vj (j – номер попиту). Помножені на ці числа вони вираховуються з Z рядка симплекс-таблиці. Тому значення ui та vj мають бути такими, щоб для базисних змінних виконувалася умова
|
|
|
сij – ui – vj = 0
Запишемо її у вигляді системи з шести рівнянь (за кількістю базисних змінних) з сімома невідомими (ui та vj)
u1 + v1 = 6
u1 + v2 = 8
u2 + v2 = 5
u2 +v3 = 6
u2 +v4 = 1
u3 +v4 = 2
У нашій задачі є 7 потенціалів, а рівнянь всього 6, тому одному з невідомих присвоюємо довільне значення (зазвичай це u1=0) і потім послідовно знаходять значення інших потенціалів.
Таблиця
| Базисні змінні | Рівняння | Розв’язок |
| х11 | u1+v1=6 | u1=0àv1=6 |
| х12 | u1+v2=8 | u1=0àv2=8 |
| х22 | u2+v2=5 | v2=8àu2=-3 |
| х23 | u2+v3=6 | u2=-3àv3=9 |
| х24 | u2+v4=1 | u2=-3àv4=4 |
| х34 | u3+v4=2 | v4=4àu3=-2 |
Після того як потенціали знайдено, помножимо їх на відповідні рядки симплекс таблиці і віднімемо від першого рядка.
с11-u1-v1=6-0-6=0,
с12-u1-v2=8-0-8=0,
с13-u1-v3=9-0-9=0,
с14-u1-v4=3-0-4=-1,
с21-u2-v1=3-(-3)-6=0,
с22-u2-v2=5-(-3)-8=0,
с23-u2-v3=6-(-3)-9=0,
с24-u2-v4=1-(-3)-4=0
с31-u3-v1=1-(-2)-6=-3
с32-u3-v2=6-(-2)-8=0
с33-u3-v3=4-(-2)-9=-3
с34-u3-v4=2-(-2)-4=0
Таким чином перший рядок симплекс таблиці матиме наступний вигляд:
Рис. 8
Деякі значення у таблиці є від’ємними, тому цей розв’язок не є оптимальним і необхідно продовжувати пошук далі. Для цього вводимо в базис змінну, при якій коефіцієнт у першому рядку симплекс таблиці (див. рис. 8) є найбільшим по модулю від’ємним числом. Якщо таких декілька, обираємо довільну з них.
При розв’язуванні такого типу задач потенціали знаходять, як правило, безпосередньо у транспортній таблиці, так як це показано на рис.9. Послідовність їх знаходження показано римськими цифрами. У правому нижньому куті записується значення сij – ui – vj для небазисних змінних.
|
|
|
Рис. 9
Отже, як зазначено вище, даний розв’язок не є оптимальним. Крок 2 загального алгоритму знаходження оптимального розв’язку виконано. Тому необхідно виконувати крок 3 для знаходження оптимального розв’язку.
