Пример транспортной задачи

Построить экономико-математическую модель следующей задачи. имеются три поставщика и четыре потребителя. мощность поставщиков и спросы потребителей, а также затраты на перевозку единицы груза для каждой пары “поставщик - потребитель” сведены в таблицу поставок (табл. 3).

Таблица 3

поставщики	мощность поставщиков	потребители и их спрос
		1	2	3	4
		20	110	40	110
1	60	1 х11	2 х12	5 х13	3 х14
2	120	1 х21	6 х22	5 х23	2 х24
3	106	6 х31	3 х32	7 х33	4 х34

 

В левом верхнем углу произвольной (ij -клетки (i - номер строки, j - номер столбца) стоит так называемый коэффициент затрат - затраты на перевозку единицы груза от i-го поставщика к j -му потребителю, например, в левом верхнем углу клетки (1, 4) стоит число 3, следовательно, перевозка единицы груза от 1-го поставщика к 4-му потребителю обойдется в 3 условных денежных единицы и т. д.

Задача ставится следующим образом: найти объемы перевозок для каждой пары «поставщик — потребитель» так, чтобы:

1) мощности всех поставщиков были реализованы;

2) спросы всех потребителей были удовлетворены;

3) суммарные затраты на перевозку были бы минимальны.

Решение. Построим экономико-математическую модель данной задачи, искомый объем перевозки от i-го поставщика к j -му потребителю обозначим черёз x_ij и назовём поставкой клетки (i,j). Например, х₁₂ - искомый объем перевозки от 1- го поставщика ко 2-му потребителю или поставка клетки (1,2) и т. д. заданные мощности поставщиков и спросы потребителей накладывают ограничения на значения неизвестных х. так, например, объем груза, забираемого от 1 -го поставщика, должен быть равен мощности этого поставщика - 60 единицам, т.е.  (уравнение баланса по первой строке). Таким образом, чтобы мощность каждого из поставщиков была реализована, необходимо составить уравнения баланса для каждой строки таблицы поставок, т. е.

,

,                                                                 (19)

.  

 

Аналогично, чтобы спрос каждого из потребителей был удовлетворен, подобные уравнения баланса составляем для каждого столбика таблицы поставок:

,

,                                                                             (20)

,

.     

 

Очевидно, что объем перевозимого груза не может быть отрицательным, поэтому следует дополнительно предположить, что

 

Суммарные затраты р на перевозку выражаются через коэффициенты затрат и поставки следующим образом;

                   (21)

Найдем первоначальное базисное распределение поставок для транспортной задачи методом «северо-западного угла».

Решение. дадим переменной х₁₁ максимально возможное значение или, иными словами, максимально возможную поставку в клетку (1,1) - “северо-западный” угол таблицы поставок: х₁₁= min {60, 20) = 20. После этого спрос 1-го потребителя будет полностью удовлетворен, в результате чего первый столбец таблицы поставок выпадет из последующего рассмотрения (заполненные клетки будем перечеркивать сплошной линией (табл. 4) клетки, выпавшие из последующего рассмотрения, перечеркнуты пунктирной линией. в таблице поставок найдем новый “северо-западный” угол - клетку (1,2) и дадим в нее максимально возможное значение. Учитывая, что 1-й поставщик уже отдал 20 единиц груза и у него осталось только 40 = 60 - 20 единиц груза, получаем, что . После этого мощность 1-го поставщика полностью реализована и из рассмотрения выпадет первая строка таблицы поставок (перечеркиваем сплошной линией клетку (1,2) и пунктирной линией оставшиеся свободные клетки первой строки). в оставшейся таблице снова находим “северо-западный угол” и т. д. в результате получаем следующее исходное распределение поставок (табл.4).

Таблица 4.

	20	110	40	110
60	1 20	2 40	5	5
120	1	6 70	5 40	2 10
100	6	3	7	4 100

Решение методом наименьших затрат.

Решение. Находим в таблице поставок (табл.4) клетки с наименьшим коэффициентом затрат. Таких клеток две – (1,1) и (2,1) с коэффициентами затрат, равными 1. сравним максимально возможные поставки для этих клеток: для клетки (1,1) , для клетки (2,1) .

Так как они совпадают, то максимально возможную поставку даем в любую из них. Например, даем поставку, равную 20 единицам, в клетку (2,1). в результате спрос первого потребителя удовлетворен и первый столбец таблицы поставок выпадает из последующего рассмотрения (табл. 5.).

Таблица 5

	20	110	40	110
60	1	2	5	3
120	1 20	6	5	2
100	6	3	7	7

 

В оставшейся таблице наименьшим коэффициентом затрат обладают две клетки: с₁₂ = с₂₄= 2. Сравним максимально возможные поставки для этих клеток: для клетки (1,2) ; для клетки (2,4) . Даем поставку в клетку (2,4), для которой максимально возможная поставка оказалась больше: х₂₄ =100. При этом из рассмотрения выпадает вторая строка таблицы поставок (табл. 6).

Таблица 6

	20	110	40	110
60	1	2	5	3
120	1 20	6	5	2 100
100	6	3	7	4

Аналогично, продолжая заполнение таблицы поставок шаг за шагом, получаем , , табл. 7.

 

 

Таблица 7

	20	110	40	110
60	1	2 60	5	3
120	1 20	6	5	2 100
100	6	3 50	7 40	4 10