Шпаргалка по "Логистике"

     Метод потенциалов для  решения транспортной задачи в матричной  форме с ограничениями  пропускной способности.

     Задание:

1. Построить оптимальный план перевозок каменного угля с пяти станций А_i (i = 1,2,3,4,5), до девяти крупных потребителей, имеющих подъездные пути В_j (j = 1,2,…,9).
2. Определить объем тонно-километровой работы начального и оптимального планов перевозки грузов.

     Исходные  данные (вариант 67):

     Данные  о наличии ресурсов на пяти станциях отправления А_i приведены в таблице 1, данные о размерах прибытия груза В_j на девять станций назначения – в таблице 2. 

     Таблица 1 - Ресурсы станций отправления  А_i (строки матрицы)

     Таблица 2 - Объем потребности В_j получателя (столбцы матрицы)

     Решение:

     Расстояние  перевозки от каждой i–й станции отправления до каждой j–й станции назначения указано в правом верхнем углу каждой клетки матрицы. В левом верхнем углу ряда клеток матрицы указаны ограничения пропускной способности.

     Условием  задачи установлено, что размер всех ресурсов у отправителей равен общей  потребности получателей: 

     С учетом полученных условий необходимо найти такие неотрицательные  значения величин объемов перевозок  х_ij, при которых сумма произведений значений критерия С_ij на размер перевозок будет минимальной, т.е. 

     Первоначально строится начальный план базисного  варианта способом наименьшего значения критерия.

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

     V_j – U_i ≤ C_ij для х_ij = 0; (1)

     V_j – U_i = C_ij для d_ij > х_ij > 0; (2)

      V_j – U_i ≥ C_ij для х_ij = d_ij; (3) 

     где V_j – потенциал j–го столбца;

     U_i – потенциал i–й строки;

     C_ij – расстояние перевозки от i–го поставщика до j–го потребителя;

     х_ij – корреспонденция (размеры перевозок) от i–го поставщика до j–го потребителя;

     d_ij – величина пропускной способности ij клетки.

     Присвоение  потенциалов начинают со строки, в  которой среди базисных клеток имеется  максимальное расстояние. Этой строке можно присвоить любой положительный  потенциал, например, 100. Затем, используя  условие оптимальности (2), находят  потенциалы остальных строк и  столбцов по формулам:

     для j–го столбца  

     V_j = U_i + C_ij; 

     для i–й строки  

     U_i = V_j – C_ij. 

     Корреспонденция улучшения плана находится из следующего выражения: 

     х_ул = min [х_{ij четн}, (d_ij – х_ij)_нечетн] 

     F(х) = 45·90 + 30·50 + 75·60 + 80·10 + 80·25 + 10·20 + 105·35 + 15·70 + 135·40 + 135·60 + 95·30 + 55·40 + 95·10 + 20·35 + 5·25 + 20·80 = 39700 ден. ед.

     80 – 70 + 60 – 90 + 10 – 25 + 25 – 80 = –  90 < 0 – цикл подходит

     r = {15; 45; 80; 20} =15 

     F(х) = 39700 – 90·15 = 38350 ден.ед.

     30 – 90 + 10 – 25 + 25 – 80 + 80 – 35 = –  85 < 0 – цикл подходит 

     r = {30; 65; 5; 105} = 5