Pod_redakciei_professora_N_SH_Kremera_ISSLED - Стор 15
цикл перерахунку, у вершинах цього циклу розставити послідовно чергують знаки, починаючи зі знака "+" у вільній клітині, тоді значення оцінки вільної клітини дорівнює сумі алгебри коефіцієнтів витрат клітин циклу, взятих з відповідними знаками.
Аналогічно, складаючи зазначений цикл перерахунку кожної вільної клітини, можна знайти її оцінку. При цьому, звичайно, цикл не завжди виходитиме таким простим, як у розібраному прикладі для клітини (1,3). Наприклад, зазначений цикл перерахунку клітини (1,1), показаний на .рис. 7.2, складніший.
Оцінка клітини (1,1) у цьому випадку дорівнює
Р„ = (1 + 3 + 2) - (2 + 1 + 4) =
Зауваження. Іноді для довільного зазначеного циклу вводиться поняття оцінка циклу сума алгебри коефіцієнтів, що стоять у вершинах циклу, взятих з відповідними знаками. Наведені вище міркування показують, що оцінка циклу дорівнює оцінці єдиної вільної клітині, яка входить у даний цикл.
Для полегшення перебування циклу перерахунку у конкретних завданнях дамо його точне визначення. Циклом у матриці називатимемо ламану з вершинами в клітинах і ланками, що лежать уздовж рядків та стовпців матриці, що задовольняє умовам:
• ламана має бути зв'язною, тобто. з будь-якої її вершини можна потрапити в будь-яку іншу вершину за ланками ламаної;
• у кожній вершині ламаної зустрічаються дві ланки, одна з
яких розташовується по рядку, інше - по стовпцю.
Циклом перерахунку називається такий цикл у таблиці з базисним розподілом поставок, у якому одна з його вершин лежить у вільній клітині, решта — у заповнених. Цикл перерахунку називається зазначеним, якщо у його вершинах розставлені знаки "+" ітак, щоу вільній клітці стоїть знак "+", а сусідні вершини мають протилежні знаки.
Для кожної вільної клітини базисного розподілу поставок існує і єдиний цикл перерахунку, причому операція означення циклу є коректною. Детальні докази можна знайти, наприклад, у [16].
Таким чином, отримано правило, що дозволяє визначити оцінку довільної вільної клітини. Однак знаходження оцінок сво-
бодних клітин можна суттєво спростити. Розглянемо таку уявну ситуацію. Нехай коефіцієнти витрат всіх заповнених клітин дорівнюють нулю. Якщо за розглянутим правилом визначити оцінку вільних клітин, то виявиться, що оцінки вільних клітин рівні їх коефіцієнтам витрат, тобто. у разі значення оцінок зчитуються з таблиці поставок і жодних циклів будувати зайве.
З іншого боку, справедлива така теорема.
Теорема 7.3. (Про потенціали). Оцінка вільної клітини не зміниться, якщо до коефіцієнтів витрат деякого рядка (стовпця) таблиці поставок додати деяке число. Це число, що додається до коефіцієнтів витрат виділеного рядка (стовпця), називатимемо потенціалом цього рядка (стовпця).
D Нехай для фіксованої вільної клітини побудовано цикл. Для кожної ланки цього циклу, що входить у довільний виділений рядок, маємо пару сусідніх вершин циклу. За визначенням зазначеного циклу перерахунку одна з цих двох вершин має знак "+", інша - знак Тоді внесок від цих двох вершин у значення оцінки визначається різницею коефіцієнтів витрат цих вершин. Очевидно, що якщо до кожного з цих коефіцієнтів витрат додати те саме число, то саме значення різниці не зміниться.
Розгляд уявного випадку та теорема 7.3 призводять до правила 2знаходження оцінок вільних клітин: до коефіцієнтів витрат таблиці поставок у кожному рядку та стовпці треба додати такі числа (потенціали), щоб коефіцієнти витрат у заповнених клітинах стали рівними нулю. Отримані у своїй коефіцієнти витрат вільних клітин рівні оцінкам цих клітин.
7.6. Знайти оцінки вільних клітин базисного розподілу-
ня поставок, знайденого в задачі 7.3.
Рішення . Знайдемо оцінки вільних клітин, виходячи з викладеної вище послідовності дій. Зміна коефіцієнтів витрат можна починати з будь-якого стовпця (рядки). Потенціал стовпця (рядки), обраного для початку, може бути довільним, але можна довести, що після його фіксації потенціали інших стовпців та рядків будуть визначені однозначно.
Почнемо з першого стовпця. Нехай потенціал цього стовпця ра-
вен нулю (табл. 7.11). Поруч із потенціалом у дужках