нь за даним планом становить: 7300 тис. руб.
Вирішимо задачу із застосуванням методу потенціалів .
Для цього плану можна визначити платежі ( a i і b j ), так, щоб у кожній базисної клітці виконувалася умова:
a i + b j = з i, j (*)
Рівнянь (*) всього m + n - 1, а число невідомих дорівнює m + n. Отже, одну з цих невідомих можна задати довільно (наприклад, рівною нулю). Після цього з m + n - 1 рівнянь (*) можна знайти інші платежі a i , b j , а по них обчислити псевдостоімость: u i, j = a i + b j для кожної вільної клітини.
Якщо виявилося, що всі ці псевдостоімость не перевищують вартостей u i, j ? з i, j ,
то план потенціалом і, значить, оптимальний. Якщо ж хоча б в одній вільній клітці псевдостоімость більше вартості (як у нашому прикладі), то план не є оптимальним і може бути поліпшений переносом перевезень по циклу, відповідному даної вільної клітині. Ціна цього циклу рівна різниці між вартістю і псевдостоімость в цій вільній клітці. br/>
b j a i +180190110210200120130 a i 4905 7 8 4 6 9 0 0 5 1...
