Теорема
Теорема (про оптимальний план ТЗ
Попередні відомості. Складемо математичну модель ТЗ
|
(74)
(77)
До задачі (74)-(77) складають двоїсту
(78)
З огляду на те, що Ui й Vj можуть мати будь-які знаки, то якщо змінним Ui присвоїти знак (-), тоді двоїста задача має вид
(79)
(80)
Для того, щоб деякий план 
був оптимальним необхідно й достатньо, щоб для нього існувала система m+n чисел Ui й Vj, причому таких чисел, щоб виконувалися умови
(81)
для кліток небазисного набору й
(82)
для кліток базисного набору.
Тут числа Ui й Vj відповідно називаються потенціалами пунктів відправлення й потенціалами пунктів призначення. Тоді умови (81) і (82) називаються умовами потенційності кліток небазисного набору (81) і базисного набору (82).
У зв'язку з відзначеним теорему про оптимальний план ТЗ у компактному виді можна представити в такий спосіб.