1.1 Математична модель транспортної задачі (ТЗ)
Нехай є m пунктів відправлення A1, A2, ..., Am. в яких знаходиться однорідний вантаж в кількостях а1, а2, ..., аm cоответственно, і n пунктів призначення B1, B2, ..., Bn. потреби яких в даному вантажі рівні b1, b2, ..., bn. Відомі cij витрати на перевезення одиниці вантажу з i -го пункту відправлення в j -й пункт споживання. Потрібно скласти план перевезень так, щоб запаси кожного постачальника були б вивезені, попит кожного споживача задоволений, і загальна вартість всіх перевезень була мінімальною.
Число базисних клітин
m + n-1 = 3 + 4-1 = 6.
Примітка. При знаходженні початкового плану перевезень можливий випадок виродження, коли в результаті обчислень значення xij виходить, що потреби в пункті Bj задоволені, а запаси в пункті Ai вичерпані. Тоді одночасно з розгляду вибувають рядок і стовпець. Рекомендується в одну з клітин вибувають рядки і стовпці (краще в клітку з найменшою вартістю) ставити так званий базисний нуль. Ця клітина вважається базисної (в ній пишеться 0), а загальне число базисних клітин залишається рівним m + n -1.
1.3.2 Метод мінімального елемента
Одержуваний методом північно-західного кута початковий план перевезень не залежить від їх вартості і тому в загальному випадку далекий від найкращого. У методі мінімального елементу враховуються витрати на перевезення. Відповідний початковий план дозволяє забезпечити сумарну вартість перевезень, ближчу до оптимальної.
У цьому методі за формулою (11) послідовно заповнюються клітини з найменшою вартістю перевезень. Якщо є кілька клітин з найменшою вартістю, то з них вибирається будь-яка.
Приклад 2. Знайти початковий план перевезень в ТЗ методом мінімального елемента.
Запишемо матрицю перевезень (табл. 1.3).
Таблиця 1.3
Метод потенціалів - метод, що забезпечує поліпшення початкового плану перевезень. При цьому відбувається перехід від одного плану перевезень до іншого (від однієї матриці перевезень до іншої) до тих пір, поки зменшення сумарної вартості перевезень стане неможливим.
7. Для вільних клітин знаходимо суми відповідних потенціалів, заносимо їх в матрицю в нижній правий кут вільних клітин.
8. Для вільних клітин перевіряємо виконання умови оптимальності: для. Для клітин (1,4) і (2,1) умова не виконана.
9. Для вільних клітин будуємо позначений цикл.
10. Виробляємо зрушення по циклу на Клітка (2,1) стає базисної. а клітина (1,1) - вільною.
11. Переходимо до кроку 2 алгоритму методу потенціалів.
12. Будуємо нову матрицю перевезень.
Для вільної клітини (1,4) умова оптимальності не виконано. Будуємо для неї позначений цикл, здійснюємо зрушення по циклу на Клітка (1,4) стає базисної. клітина (2,4) - вільною. Будуємо нову матрицю перевезень.
13. Переходимо до кроку 2 методу потенціалів:
Для всіх вільних клітин
Отриманий план є оптимальним:
При цьому плані вартість перевезень:
транспортна задача рішення методи
2Решеніе транспортної задачі.Метод північно-західного кута
Є 3 постачальника молочної продукції - компанія «ВІММ-Білль-ДАНН», ВАТ «Петмол» і ТОВ «Пискаревского» - і чотири споживача однорідної продукції: ВАТ «Ленстройкераміка» для працівників підприємства за важкий, шкідливий працю, ТОВ «АГРОТОРГ» для подальшої перепродажу населенню, ЗАТ «ТАНДЕР» і ВАТ «Діксі Груп» також для подальшого перепродажу населенню.