Відмінності між версіями «Умова оптимальності опорного плану ТЗ»
| Рядок 13: | Рядок 13: | ||
Потенціали опорного плану визначаються із системи рівнянь <math>u_i + v_j = c_{ij}</math>, які записують для всіх заповнених клітинок транспортної таблиці. | Потенціали опорного плану визначаються із системи рівнянь <math>u_i + v_j = c_{ij}</math>, які записують для всіх заповнених клітинок транспортної таблиці. | ||
| − | == Приклад перевірки транспортної задачі на | + | == Приклад перевірки плану транспортної задачі на оптимальність == |
Нехай дана транспортна таблиця: | Нехай дана транспортна таблиця: | ||
| Рядок 38: | Рядок 38: | ||
Далі згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності <math>u_i + v_j \leq c_{ij}</math> (для порожніх клітинок таблиці): | Далі згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності <math>u_i + v_j \leq c_{ij}</math> (для порожніх клітинок таблиці): | ||
| − | <math>\begin{array} | + | <math>\begin{array}{l} |
A_1B_2: u_1 + v_2 = 5 + (-1) = 4 = 4; \\ | A_1B_2: u_1 + v_2 = 5 + (-1) = 4 = 4; \\ | ||
A_1B_3: u_1 + v_3 = 5 + (-1) = 4 > 2; \\ | A_1B_3: u_1 + v_3 = 5 + (-1) = 4 > 2; \\ | ||
| Рядок 48: | Рядок 48: | ||
Умова оптимальності не виконується для клітинки <math>A_1B_3</math>. Порушення <math>\bigtriangleup_{13} = (u_1 + v_3) - c_{13} = 4 - 2 = 2</math> записуємо в лівому нижньому кутку відповідної клітинки. | Умова оптимальності не виконується для клітинки <math>A_1B_3</math>. Порушення <math>\bigtriangleup_{13} = (u_1 + v_3) - c_{13} = 4 - 2 = 2</math> записуємо в лівому нижньому кутку відповідної клітинки. | ||
| + | |||
| + | Перший опорний план транспортної задачі є неоптимальним. Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці. | ||
| + | |||
| + | Після цих операцій ми отримаємо другу транспортну таблицю, яку знову перевіряємо на оптимальність. | ||
Версія за 18:37, 10 травня 2012
Умова оптимальності опорного плану транспортної задачі
Опорний план перевіряють на оптимальність за допомогою потенціалів Неможливо розібрати вираз (невідома помилка): u_i
та Неможливо розібрати вираз (невідома помилка): v_j відповідно постачальників та споживачів.
Якщо для деякого опорного плану Неможливо розібрати вираз (невідома помилка): X^* = (x_{ij}^*)
існують числа Неможливо розібрати вираз (невідома помилка): u_i та Неможливо розібрати вираз (невідома помилка): v_j
, для яких виконується умова:
Неможливо розібрати вираз (невідома помилка): u_i + v_j = c_{ij}, x_{ij} > 0,
Неможливо розібрати вираз (невідома помилка): u_i + v_j \leq c_{ij}, x_{ij} = 0
для всіх Неможливо розібрати вираз (невідома помилка): i = \bar{1,m}
та Неможливо розібрати вираз (невідома помилка): j = \bar{1,n}
, то він є оптимальним планом транспортної задачі.
Потенціали опорного плану визначаються із системи рівнянь Неможливо розібрати вираз (невідома помилка): u_i + v_j = c_{ij} , які записують для всіх заповнених клітинок транспортної таблиці.
Приклад перевірки плану транспортної задачі на оптимальність
Нехай дана транспортна таблиця:
Z = 4 * 110 + 5 * 40 + 1 * 60 + 1 * 40 + 2 * 40 = 820 ум. од.
Перший опорний план транспортної задачі вироджений, оскільки кількість заповнених клітинок у таблиці дорівнює п'яти, а (m + n - 1) = 3 + 4 - 1 = 6. Для подальшого розв'язування задачі необхідно в одну із порожніх клітинок записати "нульове перевезення" так, щоб не порушити опорності плану, тобто можна зайняти будь-яку вільну клітинку, яка не утворює замкненого циклу. Наприклад, заповнимо клітинку Неможливо розібрати вираз (невідома помилка): A_2 B_4 . Тепер перший план транспортної задачі є невиродженим, і його можна перевірити на оптимальність за допомогою методу потенціалів.
На основі першої умови оптимальності Неможливо розібрати вираз (невідома помилка): u_i + v_j = c_{ij}
складемо систему рівнянь для визначення потенціалів плану:
Неможливо розібрати вираз (невідома помилка): \begin{cases} u_1 + v_1 = 4, \\ u_1 + v_4 = 5, \\ u_2 + v_3 = 1, \\ u_2 + v_4 = 2, \\ u_3 + v_2 = 1, \\ u_3 + v_4 = 2. \end{cases}
Записана система рівнянь є невизначеною, і один з її розв'язків дістанемо, якщо, наприклад, Неможливо розібрати вираз (невідома помилка): v_4 = 0
. Тоді всі інші потенціали однозначно визначаються: Неможливо розібрати вираз (невідома помилка): u_1 = 5, u_2 = 2, u_3 = 2, v_1 = -1, v_2 = -1, v_3 = -1.
Далі згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності Неможливо розібрати вираз (невідома помилка): u_i + v_j \leq c_{ij}
(для порожніх клітинок таблиці):
Неможливо розібрати вираз (невідома помилка): \begin{array}{l} A_1B_2: u_1 + v_2 = 5 + (-1) = 4 = 4; \\ A_1B_3: u_1 + v_3 = 5 + (-1) = 4 > 2; \\ A_2B_1: u_2 + v_1 = 2 + (-1) = 1 < 5; \\ A_2B_2: u_2 + v_2 = 2 + (-1) = 1 < 3; \\ A_3B_1: u_3 + v_1 = 2 + (-1) = 1 < 2; \\ A_3B_3: u_3 + v_3 = 2 + (-1) = 1 < 4. \end{array}
Умова оптимальності не виконується для клітинки Неможливо розібрати вираз (невідома помилка): A_1B_3
. Порушення Неможливо розібрати вираз (невідома помилка): \bigtriangleup_{13} = (u_1 + v_3) - c_{13} = 4 - 2 = 2
записуємо в лівому нижньому кутку відповідної клітинки.
Перший опорний план транспортної задачі є неоптимальним. Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці.
Після цих операцій ми отримаємо другу транспортну таблицю, яку знову перевіряємо на оптимальність.
