И ее математическая модель

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

1. Экономическая трактовка транспортной задачи и ее математическая модель.

2. Типы транспортных задач. Теорема о разрешимости транспортной задачи.

3. Построение начального плана транспортной задачи.

4. Метод потенциалов.

В современных условиях большие транспортные расходы связаны с простоями в ожидании обслуживания на погрузочно-разгрузочных работах, порожними пробегами, встречными и нерациональными перевозками, затратами на бензин, техничес­кое обслуживание и заработную плату водителей. В связи с этим необходимо решать задачи оптимального планирования перево­зок грузов в коммерческой деятельности из пунктов отправле­ния (баз, станций, фабрик, совхозов, заводов) в пункты назна­чения (магазины, склады) методами, позволяющими оптимизи­ровать план по какому-либо экономическому показателю, напри­мер финансовых затрат или времени на перевозку грузов.

Для решения подобного рода задач существует в линейном программировании специально разработанные методы, а задачи такого рода называются транспортными задачами.

Экономическая трактовка транспортной задачи

и ее математическая модель

Простейшая транспортная задача по критерию стоимости формулируется следующим образом:

Имеется:

1) m пунктов отправления А₁, А₂, …, А_m с запасами а_i единиц груза в каждом (i = 1, 2,..., т);

2) п пунктов назначения В₁, В₂, …, В_n с потреб­ностями в грузах b_j (j = 1, 2,..., п).

Известна стоимость перевозки единицы груза по каждому возможному маршруту. В общем виде она обозначается через c_ij и называется тарифом.

Требуется составить план перевозок, т. е. определить, сколько единиц груза надо перевезти по каждому маршруту: (x_11, x₁₂…,x_ij,..x_mn).

При этом должны выполняться следующие условия:

1) из каждого пункта отправления должен быть вывезен весь груз (ограничения по запасам);

2) в каждый пункт назначения необходимо доставить потребное ко­личество груза (ограничения по потребностям);

3) перевозки в обратном направлении не допускаются (условие неотрицательности);

4) общая стоимость перевозок должна быть минимальной.

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

Тогда первое условие будет равносильно требованию, чтобы сумма перевозок по каждой строке равнялась запасу груза:

x_i1 + х_i2 + …+х_in = a_i, i = 1,2,…,m.

Второе условие превращается в равенство сумм перевозок по столб­цам, соответствующим потребностям:

x_1j + х_{2 j}+ …+х_mj= b _j j = 1,2,…,n.

Обратные перевозки исключаются условием неотрицательности переменных:

х_ij 0, i = 1, 2,..., т, j = 1, 2,..., п.

Общая стоимость перевозок (целевая функция задачи) имеет вид:

f = c₁₁ x₁₁ + c₁₂ x₁₂ + …+ c_mnx_mn (min)

Для нее надо найти минимум при соблюдении указанных ограничении.