10. Формулировка транспортной задачи и ее математическая модель. Условия разрешимости транспортной задачи.

Транспортная задача формулируется как задача о сотавлении наиболее оптимистичного плна перевозок однородного груза. Однородный груз n – пункты направления в количестве aj, aj=1,2,3….m.

Требуется доставить в n- пунктах назначения, стоимость перевозки единицы груза из i-того пункта направления в j пункт назначения составляет Cij. В совокупности числа Cij образуют матрицу, которая называется матрицей тарифов. Требуется составит план перевозок, при котором все грузы будут вывезены из пунктов отправления в пункты назначения, удовлетворяющей имеющуюся минимальную стоимость.

Xij – количество грузов отправленных от i- поставщика к j – потребителю.

Хтхн – (Xij) f(Xij)= , Cij*Xij→min

ПО Xij = ai, i=

ПН Xij= bj, j=

Xij≥0

Постановка транспортной задачи в форме: все грузы вывезенные из пунктов отправления и потребности всех пунктов назначения удовлетворены, возможно только в том случае, если суммарные запасы груза = суммарным потребностям.

А= ai= bj= В

При выполнении этого равенства транспортная модель называется замкнутой (сбалансированной, закрытой)

Замкнутость транспортной модели является необходимым к достижению цели решаемости транспортной задачи.

Транспортная модель является задачей линейного программирования и может быть решаема симплекс методом, однако специфика модели: каждая переменная входит в 2 ограничения, причем с коэфф.1, позволяет применить к решению задачи более простой метод. Этот метод является частным случаем симплекс метода, в котором повторяются все основные моменты общего симплекс метода.