Метод північно-західного кута
Нехай умови транспортної задачі задані таблиці 2.3. Не враховуючи вартості перевезення одиниці вантажу, починаємо задоволення потреб першого споживача B1 за рахунок запасу постачальника А1. Для цього сравніваемa1 = 100 сbi = 200, a1
У постачальника А2 осталось150 од. вантажу. Задовольняємо потребітеляB2 за рахунок залишився у поставщікаА2 вантажу. Для цього порівнюємо цей залишок до потреб потребітеляB2: 150<200 . записываем150 ед. в клеткуА2B2 и, так как запасыА2 полностью израсходованы, прочеркиваем остальные клетки второй строки. ПотребностиB2 остались неудовлетворенными на50 ед. Удовлетворяем их за счет поставщикаА3 и переходим к удовлетворениюB3 за счет остатка, имеющегося у поставщикаА3 . и т. д. Процесс продолжаем до тех пор, пока не удовлетворим всех потребителей за счет запасов поставщиков. На этом построение первоначального опорного плана заканчивается. Таким образом, в табл. в правых верхних углах клеток стоят числа, определяющие стоимость перевозки единицы грузов, а в левых нижних углах — числа, определяющие план перевозок, так как их сумма по строкам равна запасам соответствующего поставщика, а сумма по столбцам — потребности соответствующего потребителя. Проверим, является ли план, построенный втабл. 2.2 . опорным. Видим, что, начиная движение от занятой клетки A1B1, вернуться не только в нее, но и в любую другую занятую клетку, двигаясь только по занятым ячейкам, невозможно. Следовательно, план является опорным. В то же время план невырожденный, так как содержит точноm + n -1 = 4 + 5 - 1 = 8 занятых клеток. При составлении первоначального опорного плана методом северо-западного угла стоимость перевозки единицы груза не учитывалась, поэтому построенный план далек от оптимального, получение которого связано с большим объемом вычислительных работ. Поэтому рассмотренный метод используется при вычислениях-с помощью ЭВМ. Найдем общую стоимость составленного плана как сумму произведений объемов перевозок, стоящих в левом углу занятых клеток, на соответствующие стоимости в этих же ячейках:Z = 100 *10 + 100*2 + 150 *7+ 50 *5 + 100*3 + 50*2 + 50*16+ 250*13 = 6950 (eд. стоимости) Если при составлении опорного плана учитывать стоимость перевозки единицы груза, то, очевидно, план будет значительно ближе к оптимальному.
Метод мінімальної вартості
Суть методу полягає в тому, що з усієї таблиці вартостей вибирають найменшу, і в клітку, яка їй відповідає, поміщають менше з чисел ai. іліbj. Потім, з розгляду виключають або рядок, відповідну постачальнику, запаси якого повністю витрачені, або стовпець, відповідний споживачеві, потреби якого повністю задоволені, або і рядок і стовпець, якщо витрачені запаси постачальника і задоволені потреби споживача. З решти таблиці вартостей знову вибирають найменшу вартість, і процес розподілу запасів продовжують, поки всі запасів не будуть розподілені, а потреби задоволені. Складемо за допомогою цього методу опорний план вже розглянутої задачі. Запишемо її умова в таблицю (табл. 2.5). Вибираємо в таблиці найменшу вартість (це вартість, вміщена в клеткеA1, B4) так какA1 = b4, 100 од. вантажу поміщаємо в цій клітці і виключаємо з розгляду перший рядок і четвертий стовпець. У решти таблиці вартостей найменшою є вартість, розташована в клеткеA2, B1 і в клеткеA3, B5. Заповнюємо будь-яку з них, напрімерA2, B1. Імеем200 <250 . следовательно, записываем в нее200 и исключаем из рассмотрения столбецB1 . В клеткуA3, B5 записываем200 ед. и исключаем из рассмотрения строкуA3 . В оставшейся таблице стоимостей снова выбираем наименьшую стоимость и продолжаем процесс до тех пор, пока все запасы не будут распределены, а потребности удовлетворены. В результате получен планX = (X14= 100; X21= 200; X22= 50; X35= 200, X42= 150; X43= 100; X45= 50), остальные значения переменных равны нулю.
План не містить циклів і складається з семи позитивних перевезень, отже, є виродженим опорним планом. Визначимо його вартість: Z = 100 * 1 + 200 * 2 + 50 * 7 + 200 * 2 + 150 * 8 + 100 * 12 + 50 * 13 = 4300 (од) Вартість плану перевезень значно менше, отже, він ближче до оптимального .
Метод апроксимації Фогеля
Даний метод полягає в наступному:
на кожній ітерації знаходять різниці між двома найменшими тарифами у всіх рядках і шпальтах, записуючи їх в додаткові стовпець і рядок таблиці;
знаходять max Δcij і заповнюють клітину з мінімальною вартістю в рядку (стовпці), якій відповідає дана різниця.
Процес триває до тих пір, поки всі Грузії не будуть розвезені по споживачах. Даний метод в ряді завдань призводить до оптимального плану. Вирішимо цим методом задачу з прикладу 2.6.1 (див. Табл.2.7).
Метод подвійного переваги
Якщо таблиця вартостей велика, то перебір всіх елементів скрутний. У цьому випадку використовують метод подвійного переваги, суть якого полягає в наступному. У кожному стовпці відзначають знаком V клітку з найменшою вартістю. Потім те долають в кожному рядку. В результаті деякі клітини мають отметкуVV. У них знаходиться мінімальна вартість, як повз колонку так і по рядку. У ці клітини поміщають максимально можливі обсяги перевезень, кожен раз виключаючи з розгляду відповідні стовпці або рядки. Потім розподіляють перевезення по осередках, зазначеним знакомV. У решти таблиці перевезення розподіляють за найменшою вартістю.