Тема 14. Транспортна задача

Транспортна задача

Розглянемо наступну класичну задачу лінійного програмування - транспортну  задачу:

Нехай у місті є два продовольчі склади і дві пекарні. Потрібно щоденно з першого складу вивозити 50 т борошна, а з другого - 70 т. Перша пекарня при цьому отримує 40 т, а друга - 80 т борошна.

Вартість перевезення борошна зі складів до пекарень у гривнях за тонну подана в таблиці:

	1 пекарня	2 пекарня
1 склад 2 склад	1,2 0,8	1,6 1,0

Потрібно спланувати роботу транспорту так, щоб, виходя­чи з витрат на перевезення борошна зі складів до пекарень, загальна сума витрат була мінімальною.

Позначимо m[i,j] — кількість борошна, яка перевозиться зі складу і на пекарню j. Запишемо математичну модель транспортної за­дачі.

Система обмежень буде такою:

m[1,1] + m[1,2] = 50

m[2,1] + m[2,2] = 70

m[1,1] + m[2,1] = 40

m[1,2] + m[2,2] = 80

Перші два рядки системи обмежень визначають кількість борошна, що виво­зиться зі складів на пекарні, а другі два - кількість борошна, яка ввозиться на пекарні зі складів.

Оскільки нам відома вартість кожного з перевезень, то за­гальна сума вартості визначатиметься за формулою:

L=1,2*m[1,1] + 1,6*m[1,2] + 0,8*m[2,1] + m[2,2]

Отже, розв'язок транспортної задачі полягає у відшуканні таких невід'ємних значень m[i,j], які задовольняють систему об­межень, a функція L набуває мінімального значення.

Для розв'язування задач лінійного програмування використовують симплекс-метод. Транспортну задачу можна розв'язати ще і методом потенціалів.

Завдання

Фабрики Світоч, Roshen та АВК виробляють солодощі та перевозять їх у супермаркети: Aшан, Метро, Сільпо, Вопак.

Задати скільки кілограмів солодощів щоденно перевозиться з фабрик у супермаркети та ціни на перевезення..

Створити математичну модель цієї транспортної задачі.