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

от Българският сайт за математика

Ще разгледаме една от типичните задачи на линейното програмиране - така наречената транспортна задача. Ще изясним метода за решаването й с конкретна задача.

1. Дадени са три производителя (отправни пунктове) и . Производството трябва да се разпредели на пет потребителя (крайни пунктове) така, че транспортните разходи да бъдат минимални. Производството, потребностите и транспортните разходи са дадени в следната таблица:

 Потребители                         Производство
Производители
              4      2      5      7      6           20 
              7      8      3      4      5          110
              2      1      4      3      2          120
 Потребности    70     40     30     60     50          250

Стойностите с удебелен шрифт показват транспортните разходи за единица стоки от производител до съответен потребител. Например, от до транспортните разходи на единица стоки са 4.

Разпределителният метод се състои в сътавяне на изходен (базисен) план, проверка за оптималност на този план и ако не е оптимален - подобряването му и т.н.

За построяване на изходния план се използва така нареченото двупосочно предпочитание. Отбелязват се най-ниските транспортни разходи в таблицата както по редове, така и по колонки.

В първия ред най-нисък разход има клетката (1, 2), т.е. (2). Отбелязваме я с кръстче ("x"). Във втория - клетката (2, 3), в третия (3, 2). По същия начин се отбелязват разходите и по колонки. Запълването на клетките започва от двойно отбелязаните келтки. Това са клетките (2, 3) и (3, 2). По-малък транспортен разход има втората клетка, така че ще започнем от нея. В клетката (3, 2) ще поставим по-малкото от числата 120 и 40. С други думи цялата потребност на втория потребител задоволяваме само от третия производител или клетките (1, 2) и (2, 2) ще останат празни. Същото правим и с клетка (2, 3) - там поставяме по-малкото от числата 110 и 30, т.е. 30, а клетките (1, 3) и (3, 3) остават празни. Продължаваме запълването на онези клетки, които са еднократно отбелязани и с по-малък разход. Това са клетките (3, 5) и (3, 1). Понеже взехме 40 от производството на , то остават 90 и 50, т.е. 50. За клетка (3, 1) остава 30, а останалите са празни. Производството на може да се даде единствено на , т.е. в клетка (1, 1) поставяме 20, а в (2, 1) оставащите също 20 единици.

Получава се едно примерно разпределение, което, за да бъде решение, е необходимо да отговаря на следното условие:

 P = a + b - 1
 P - броят на запълнените с нулеви товари клетки;
 a - броят на производителите (отправните пунктове);
 b - броят на потребителите (крайните пунктове).
 При тази задача: P = 3 + 5 - 1 = 8 - 1 = 7.

В разпределението, което направихме, броят на запълнените с ненулеви товари клетки е точно 7, следователно то е решение или план.

Следващият етап при решаване на транспортната задача е проверка за оптималност.

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

 Z = 20.4 + 20.7 + 30.3 + 60.4 + 30.2 + 40.1 + 50.2 = 

   = 80 + 140 + 90 + 240 + 60 + 40 + 100 = 750

За да се провери за оптималност е необходимо да се направи обход на всички нулеви клетки. Ако решението е оптимално, то всички обходи са неотрицателни числа. В противен случай решението се нуждае от подобрение. Обход на нулева клетка се нарича изпъкнал многоъгълник със следните изисквания:

- тръгва се от нулевата клетка и се връщаме пак в нея;
- може да се преминава през друга празна клетка, но се спира само в нулевата;
- числото на обхода се получава като алгебричен сбор от транспортните разходи на клетките, които са върхове на многоъгълника, като се започва с + и знаците алтернативно се сменят.

За обхода на клетка (1, 2) се тръгва от нея, спираме в клетка (3, 2), след това - в (3, 1) от нея в клетка (1, 1) и се връщаме в (1, 2). За числата на обхода се получава:

  (1, 2) -> +2 - 1 + 2 - 4 = -1 

  (1, 3) -> +5 - 3 + 7 - 4 = +5 

  (1, 4) -> +7 - 4 + 7 - 4 = +6 
 
  (1, 5) -> +6 - 2 + 2 - 4 = +2 

  (2, 2) -> +8 - 1 + 2 - 7 = +2 

  (2, 5) -> +5 - 2 + 2 - 7 = -2 

  (3, 3) -> +4 - 2 + 7 - 3 = +6 

  (3, 4) -> +3 - 2 + 7 - 4 = +4

При две от клетките се получават отрицателни числа, а именно (1, 2) и (2, 5), следователно решението не е оптимално и се нуждае от подобрение.

Нека разгледаме обходите на тези клетки, като ги изведем вън от таблицата.

Стремежът е да сменим знаците на числата, чрез които се получава обходът, т.е. да изпразним клетка (2, 1), а да запълним клетка (2, 5). За да се наруши балансът, то от клетка (3, 1), чийто товар става 50.

Получава се ново разпределение, което е подобрен план.

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

Аналогично за:

Получихме ново решение: