/Tr> В В В
...
В
Перемінними (невідомими) транспортної задачі є (i = 1, ..., m; i = 1,2, ..., n) - обсяги перевезень від кожного i-го постачальника кожному j-му споживачеві. Ці змінні можуть бути записані в матриці перевезень
Математична модель транспортної задачі в загальному випадку має вигляд
(1.1)
i = 1,2, ..., m, (1.2)
j = 1,2, ..., n, (1.3)
i = 1,2, ..., m; j = 1,2, ..., n. (1.4)
Цільова функція задачі (1.1) виражає вимоги забезпечити мінімум сумарних витрат на перевезення всіх вантажів. Перша група з т рівнянь (1.2) описує той факт, що запаси всіх т постачальників вивозяться повністю. Друга група з n рівнянь (1.3) виражає вимоги повністю задовольнити запити всіх n споживачів. Нерівності (1.4) є умовами невід'ємності всіх змінних завдання.
Таким чином, математична формулювання транспортної задачі полягає в наступному: знайти змінні завдання
i = 1,2, ..., m; j = 1,2, ..., n,
задовольняє системі обмежень (1.2), (1.3), умовам неотрицательности (1.4) і забезпечує мінімум цільової функції (1.1). p> У розглянутим моделі транспортної задачі передбачається, що сумарні запаси постачальників дорівнюють сумарним запитам споживачів, тобто
.
Таке завдання називається завданням з правильним балансом, а її модель-закритою. Якщо ж це нерівність не виконується, то завдання називається завданням з неправильним балансом, а її модель-відкритою. p> Для того щоб транспортна задача лінійного програмування мала рішення, необхідно і достатньо, щоб сумарні запаси постачальників дорівнювали сумарним запитам споживачів, тобто задача повинна бути з правильним балансом.
Приклад 1:
Скласти математичну модель транспортної задачі перевозу вантажу з двох складів у 3 магазину:
Таблиця 2
В
50
70
80
90
9
5
3
110
4
6
8
Рішення. Введемо змінні завдання (матрицю перевезень)
В
Запишемо матрицю вартостей
.
Цільова функція завдання дорівнює сумі творів усіх відповідних елементів матриць С і Х:
В
Дана функція, визначальна сумарні витрати на всі перевезення, повинна досягати мінімального значення.
Складемо систему обмежень задачі. Сума всіх перевезень, що стоять в першому рядку матриці Х, повинна дорівнювати запасах першого постачальника, а сума перевезень у другому рядку матриці Х - запасам другого постачальника:
В
Це означає...
