начення функціоналу
.
Так як ми ще не знаємо, оптимальний план Х чи ні, то візьмемо завідомо оптимальний план Х '(x Вў ij ) і подивимося, яке значення він доставляє функціоналу:
В
(транспортні витрати мінімальні). Чи виконуються умови потенційності для плану Х ' - невідомо, але кожній клітці ( i , j ) макета 8, виходячи з потенційності плану Х , відповідає нерівність v j - u i ВЈ a ij або, навпаки, a ij ≥ v j - u i. Візьмемо з кожної клітини макета відповідний х ' ij , помножимо його на ліву і праву частини останнього нерівності і складемо. Одержимо нерівність
.
Подвійну суму в правій частині позначимо для стислості буквою S:
,
її можна переписати у вигляді різниці двох подвійних сум:
.
Перетворимо ці суми наступним чином. Перша з них в розгорнутому вигляді дає
В
або
.
Аналогічно другу подвійну суму можна записати так:
.
Тоді рівність запишеться в іншій формі:
.
Але є сума компонент плану з j -му стовпцю, вона
дорівнює потреби j -ro пункту призначення
.
Аналогічно є сума компонент плану, взята по i -й рядку, вона дорівнює запасам в i -м пункті відправлення
.
Ці рівності сум компонент по рядку і стовпцю відповідно запасах і потребам виконуватимуться для будь-якого допустимого плану, в тому числі і для взятого на самому початку плану Х ( x ij ):
В
Тому для будь-яких допустимих планів будемо мати
В
і в написаному вище рівність суми x Вў ij можна замінити відповідними сумами x ij :
В
Тепер повернемося до форми запису
.
У плані Х ( x ij ) за умовою його потенційності для кожної позитивної компоненти x ij > 0 виконується рівність v j - u i = a ij .
Інші компоненти плану дорівнюють нулю, і відповідні доданки в сумі звернуться до нулі. Тому отримана сума буде дорівнює
.
Підставляючи в
,
приходимо до нерівності
В
або z min ≥ z X. Іншими словами, транспортні витрати за планом Х менше або дорівнюють мінімальним видатках. Але менше мінімальних вони бути не можуть, залишається тільки рівність z X = Z min .. План Х доставляє мінімальні витрати, тобто він оптимальний, що і треба ...
