ТРАНСПОРТНАЯ ЗАДАЧА

пунктов производства (поставщиков) и n пунктов потребления (потребителей) однородного продукта.

Заданы величины:

поставщика, i=1, m ;

-

объем потребления (спрос) j-го потребителя, i=1, n ;

- стоимость перевозки (транспортные затраты) единицы продукта от i-го поставщика к j-му потребителю.

Требуется составить такой план перевозок, при котором спрос всех потребителей был бы выполнен и при этом общая стоимость всех перевозок была бы минимальна.

совпадают, называется закрытой моделью; в противном случае - открытой.

Открытая модель решается приведением к закрытой.

фиктивный n+1 потребитель, потребности которого

вводится фиктивный m+1 поставщик, запасы которого

стоимость перевозки единицы груза от фиктивного поставщика полагают равными нулю,

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

обладают общими чертами, а именно,
1) коэффициенты целевой функции неотрицательны

(стоимости перевозок не могут быть отрицательными величинами);
2) коэффициенты правых частей ограничений неотрицательны (запасы и потребности продукта);
3) коэффициенты в ограничениях принимают только два значения, это нули и единицы.

к простым операциям с транспортной таблицей, которая имеет вид:

нуля положительными перевозками, остальные клетки - свободные. Базисные клетки образуют

опорный план транспортной задачи, если выполняются два условия:
1) сумма перевозок в каждой строке равна запасу в данной строке.

Опорный план транспортной задачи содержит не более n+m-1 отличных

от нуля перевозок


Опорный план называется вырожденным, если число ненулевых перевозок

меньше и n+m-1, опорный план - невырожден, если число ненулевых перевозок равно n+m-1.

потребителя B1 за счет запаса поставщика А1. Для этого сравниваем

a1 = 100 с bi = 200, a1< b1 меньший из объемов, т. е. = 100 ед. записываем в левый нижний угол клетки А1B1.

прочеркиваем. Потребности В остались неудовлетворенными на 200–100=100 ед. Сравниваем этот

остаток с запасами поставщика А2: так как 100<250, то 100 ед. записываем в клетку А2 .B1, чем полностью удовлетворяем потребности потребителя B1, а оставшиеся клетки в первом столбце прочеркиваем.

за счет оставшегося у поставщика А2 груза. Для этого сравниваем

этот остаток с потребностями потребителя B2: 150<200, записываем 150 ед. в клетку А2B2 и, так как запасы А2 полностью израсходованы, прочеркиваем остальные клетки второй строки.

счет поставщика А3 и переходим к удовлетворению B3 за счет

остатка, имеющегося у поставщика А3, и т. д. Процесс продолжаем до тех пор, пока не удовлетворим всех потребителей за счет запасов поставщиков. На этом построение первоначального опорного плана заканчивается.

числа, определяющие стоимость перевозки единицы грузов, а в левых нижних

углах — числа, определяющие план перевозок, так как их сумма по строкам равна запасам соответствующего поставщика, а сумма по столбцам — потребности соответствующего потребителя.

начиная движение от занятой клетки 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 . Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.

процесс распределения запасов продолжают, пока все запасы не будут распределены,

а потребности удовлетворены. Составим с помощью этого метода опорный план уже рассмотренной задачи. Запишем ее условие в таблицу:

A1 , B4 ) так как A1 = b4, 100

ед. груза помещаем в этой клетке и исключаем из рассмотрения первую строку и четвертый столбец. В оставшейся таблице стоимостей наименьшей является стоимость, расположенная в клетке A2 , B1 и в клетке A3 , B5. Заполняем любую из них, например A2 , B1.

исключаем из рассмотрения столбец 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 и заполняют клетку с минимальной стоимостью в строке (столбце), которой соответствует данная разность.

развезены по потребителям. Данный метод в ряде задач приводит к

оптимальному плану. Решим этим методом задачу из ранее приведенного примера.

5 и min cij = 6), исключаем 1-ый столбец, отметив

в дополнительной строке буквой «В» факт выполнения заказа пункта B1 . Находим новые разности минимальных тарифов по строкам (в столбцах они не изменились) и max Δc = 2 в 1-ой строке и в 4-ом столбце. Заполняем клетку A1B4 и исключаем 4-й столбец и т.д. В конце остается последовательно заполнить клетки 3-го столбца остатками запасов в A1 , A3 , A2 . Составленный опорный план дает значение Z3 = 909 < Z2.

элементов затруднителен. В этом случае используют метод двойного предпочтения, суть

которого заключается в следующем. В каждом столбце отмечают знаком V клетку с наименьшей стоимостью. Затем то же проделывают в каждой строке. В результате некоторые клетки имеют отметку VV. В них находится минимальная стоимость, как по столбцу, так и по строке. В эти клетки помещают максимально возможные объемы перевозок, каждый раз исключая из рассмотрения соответствующие столбцы или строки. Затем распределяют перевозки по ячейкам, отмеченным знаком V. В оставшейся части таблицы перевозки распределяют по наименьшей стоимости.

столбце, затем - в каждой строке

с них и начинаем заполнение. Затем заполняем ячейку A4B2 (т.к.

в столбце B2 нет ни одной ячейки с отметкой VV). В оставшейся части таблицы последовательно заполняем ячейки по минимальной стоимости A1B3 , A4B3 , A4B5 . План, полученный в табл., является вырожденным опорным планом.

= 100*1 + 200*2 + 50*10 + 200*2 + 200*8

+ 50*12 + 50*13 = 4250 (ед.).
Таким образом, наименьшую стоимость имеет опорный план, полученный методом двойного предпочтения, следовательно, он наиболее близок к оптимальному плану.