Решение транспортной задачи

Суммарные ресурсы в пунктах отправления и назначения равны соответственно a = иb = . Если общий объем производства (отправления) груза равен общему объему потребления (назначения), т.е. a = b, то такая задача называется сбалансированной (закрытой). В противном случае имеет место несбалансированная задача (открытая). Кроме того, в общем случае предполагается, что c_ij 0.

Чтобы вывезти грузы всех поставщиков (условие 1), необходимо, чтобы выполнялось равенство a= Чтобы удовлетворить заявки всех потребителей (условие 2), необходимо, чтобы выполнялось равенство b=

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

Функционал Y= ®min.

Ограничения

= a, = b, при условии сбалансированности a= b.

В случае a b задача несбалансированна. Для решения такой задачи ее необходимо свести к сбалансированной следующим образом.

1. Если a > b, то вводится дополнительный фиктивный склад потребителя b_n1=a–b и устанавливается стоимость перевозки c_i,n1= 0, (i=1, m);

2. Если a < b, то вводится дополнительный фиктивный склад поставщика a_m1=b–a и устанавливается стоимость перевозки c_m1,j = 0, (j=1, n).

Целевая функция.Стоимость всех перевозок определяется как сумма произведений стоимости перевозок единицы товара на количество перевозимого по маршруту груза:

Y = c₁₁x₁₁ + c₁₂x₁₂ + … + c_ijx_ij + … + c_mnx_mn, т.е. Y = .

Если перевозка по данному маршруту не определена, то x_ij=0.

Критерием оптимизации являются минимальные затраты на доставку всего груза потребителю, т.е. Y® min. Задача сводится к нахождению таких x_ij, которые удовлетворяют ограничениям задачи и минимизируют суммарные затраты Y. В матричной форме данная задача представлена на рис. 2. В крайнем правом столбце и нижней строке матрицы записаны ресурсы соответствующих поставщиков и потребителей, а в клетках проставляется стоимость перевозки грузов.

Рис. 2. Представление транспортной задачи в матричной форме