Теорема. Теорема (про оптимальний план ТЗ

Теорема (про оптимальний план ТЗ

Попередні відомості. Складемо математичну модель ТЗ

(75)   (76)

(74)

(77)

До задачі (74)-(77) складають двоїсту

(78)

З огляду на те, що U_i й V_j можуть мати будь-які знаки, то якщо змінним U_i присвоїти знак (-), тоді двоїста задача має вид

(79)

(80)

Для того, щоб деякий план був оптимальним необхідно й достатньо, щоб для нього існувала система m+n чисел U_i й V _j, причому таких чисел, щоб виконувалися умови

(81)

для кліток небазисного набору й

(82)

для кліток базисного набору.

Тут числа U_i й V _j відповідно називаються потенціалами пунктів відправлення й потенціалами пунктів призначення. Тоді умови (81) і (82) називаються умовами потенційності кліток небазисного набору (81) і базисного набору (82).

У зв'язку з відзначеним теорему про оптимальний план ТЗ у компактному виді можна представити в такий спосіб.

Дата добавления: 2014-12-07