Разработка программы "Организация перевозок"

 

     Пусть x_ij(i=1,3;j=1,4)-количество единиц груза, перевозимого из i-го пункта отправления в j-ый пункт назначения. Тогда экономико-математическая модель задачи:

F_min=3*x₁₁+4*x₁₂+5*x₁₃+4*x₂₁+2*x₂₂+3*x₂₃+1*x₃₁+2*x₃₂+4*x₃₃+

                                                          +6*x₄₁+2*x₄₂+5*x_{43 ;} (10)

     x₁₁+x₁₂+x₁₃+x₁₄=45;

     x₂₁+x₂₂+x₂₃+x₂₄=48;

     x₃₁+x₃₂+x₃₃+x₃₄=54;

     x₄₁+x₄₂+x₄₃+x₄₄=33;

     x₁₁+x₂₁+x₃₁+x₄₁=55;

     x₁₂+x₂₂+x₃₂+x₄₂=43;

     x₁₃+x₂₃+x₃₃+x₄₃=33;

     x_ij=0(i=1,4;j=1,3).

     2.2 Реализация модели  математическим методом 

     Таблица 2.2 - Исходная таблица

 

     Транспортная  задача является открытой, так как  запас груза больше потребностей на 49 единиц. Приведем задачу к закрытому типу - введем фиктивного потребителя B4.

     Таблица 2.3 – Ввод фиктивного потребителя:

 

     Находим опорный план по правилу северо-западного угла.

     Введем  некоторые обозначения:

A_i^* - излишек нераспределенного груза от поставщика A_i;  
B_j^* - недостача в поставке груза потребителю B_j;

     Помещаем  в клетку (1,1) меньшее из чисел A₁^*=45 и B₁^*=55. Так как запасы поставщика A₁ исчерпаны, то строка 1 в дальнейшем в расчет не принимается. Помещаем в клетку (2,1) меньшее из чисел A₂^*=48 и B₁^*=10. Так как спрос потребителя B₁ удовлетворен, то столбец 1 в дальнейшем в расчет не принимается. Помещаем в клетку (2,2) меньшее из чисел A₂^*=38 и B₂^*=43. Так как запасы поставщика A₂ исчерпаны, то строка 2 в дальнейшем в расчет не принимается. Помещаем в клетку (3,2) меньшее из чисел A₃^*=54 и B₂^*=5. Так как спрос потребителя B₂ удовлетворен, то столбец 2 в дальнейшем в расчет не принимается. Помещаем в клетку (3,3) меньшее из чисел A₃^*=49 и B₃^*=33. Так как спрос потребителя B₃ удовлетворен, то столбец 3 в дальнейшем в расчет не принимается. Помещаем в клетку (3,4) меньшее из чисел A₃^*=16 и B₄^*=49. Так как запасы поставщика A₃ исчерпаны, то строка 3 в дальнейшем в расчет не принимается. Помещаем в клетку (4,4) меньшее из чисел A₄^*=33 и B₄^*=33.

     Таблица 2.4 – Нахождение первого опорного плана

 

     Целевая функция F = 393 тонно-километра.

     Решаем  задачу методом потенциалов:

     Примем  некоторые обозначения:

     i - индекс строки;

     j - индекс столбца;

     m - количество поставщиков;

     n - количество потребителей.

     Итерация 1

     Полагая потенциал U₁=0, определяем остальные потенциалы из соотношения

      U_i+V_j=C_i,j(i=1..m, j=1..n) (11)

просматривая  все занятые клетки.

     Потенциалы  U_i:

     U₁=0

     V₁=C_1,1-U₁= 3

     U₂=C_2,1-V₁=1

     V₂=C_2,2-U₂= 1

     U₃=C_3,2-V₂=1

     V₃=C_3,3-U₃= 3

     V₄=C_3,4-U₃= -1

     U₄=C_4,4-V₄=1

     Определяем  значения оценок

      S_i,j=C_i,j-(U_i+V_j) (12)

для всех свободных клеток:

     S_1,2 = c_1,2 - (u₁ + v₂) = 3;

     S_1,3 = c_1,3 - (u₁ + v₃) = 2;

     S_1,4 = c_1,4 - (u₁ + v₄) = 1;

     S_2,3 = c_2,3 - (u₂ + v₃) = -1;

     S_2,4 = c_2,4 - (u₂ + v₄) = 0;

     S_3,1 = c_3,1 - (u₃ + v₁) = -3;

     S_4,1 = c_4,1 - (u₄ + v₁) = 2;

     S_4,2 = c_4,2 - (u₄ + v₂) = 0;

     S_4,3 = c_4,3 - (u₄ + v₃) = 1.

     Если  имеется несколько клеток с одним  и тем же наименьшим значением  оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (3,1). Для нее оценка равна -3. Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

     Таблица 2.5 – Итерация 1