СПЕЦИАЛЬНЫЕ ЗАДАЧИ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ

Транспортная задача (задача оптимального планирования перевозок груза)

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

Таблица 3.2

Bj	В1	В2	В3	В4
Ai
А1
А2
А3

Решение. Обозначим через х_ij количество груза, перевозимого из пункта i в пункт j, где .

Балансовое равенство выполняется (суммарная потребность в грузе равняется суммарным запасам: 7 + 8 + 6 = 3 + 6 + 7 + 5), значит, транспортная задача - закрытая. Тогда экономико-математическая модель задачи выглядит следующим образом:

Вариант 1. Построим исходный опорный план методом северо-западного угла. В левую верхнюю ячейку делаем максимально возможную поставку х₁₁ =min(a₁; b₁) = min(7; 3) = 3. Тем самым на первом складе остается 4 ед. груза, а потребности первого магазина удовлетворены полностью, поэтому следующую перевозку будем осуществлять с первого склада ко второму потребителю: x₁₂ = min(a₁- 3; b₂) = min(4; 6) = 4. Так как при этом на первом складе запас груза исчерпан, а потребности второго магазина удовлетворены не полностью, то производим поставку со второго склада второму магазину: х₂₂ = min(a₂; b₂- 4) = min(8; 2) = 2. Продолжаем до тех пор, пока все запасы не будут исчерпаны, а потребности магазинов не удовлетворены полностью. В итоге получаем (табл. 3.3).

Таблица 3.3

bj аi
			-	-
	-			-
	-	-

или

.

Проверим найденный опорный план на вырожденность. Вычислим m + n -1= 3+4-1 = 6; число занятых ячеек равно 6. Так как эти значения совпадают, то найденный опорный план является невырожденным. Посчитаем стоимость перевозки:

ден. ед.

Вариант 2. Построим исходный опорный план методом наименьшего тарифа. На первом шаге заполняется ячейка с наименьшим тарифом 1. Заметим, что таких ячеек две, но, так как максимальные объемы поставок в обе ячейки одинаковы, заполнение таблицы можно начать как с той, так и с другой ячейки. Будем осуществлять поставку с первого склада ко второму потребителю: х₁₂ =min(a₁; b₂)=min(7; 6) =6. Тем самым на первом складе осталась 1 ед. груза, а потребности второго магазина удовлетворены полностью. Поэтому далее выбираем ячейку с наименьшим тарифом из первого, третьего и четвертого столбцов таблицы. Будем осуществлять поставку со второго склада к первому потребителю: х₂₁ = min(a₂; b₁) = min(8; 3)=3. Далее заполнение таблицы происходит следующим образом:

х₁₃ = min(a₁- 6; b₃) = min(1; 5) = 1;

х₃₃ = min(a₃; b₃) = min(6; 7) = 6;

х₂₃ =min(a₂- 3; b₃- 6)=min(5; 1)=1;

х₂₄ =min(a₂- 3-1; b₄- 1)=min(4; 4)=4.

Исходный опорный план, построенный методом наименьшего тарифа, следующий (табл. 3.4).

Таблица 3.4

bj аi
	-		-
		-
	-	-		-

или

.

Проверим найденный опорный план на вырожденность. Вычислим m + n -1=6; число занятых ячеек равно 6. Так как эти значения совпадают, то найденный опорный план является невырожденным.

Стоимость перевозки:

ден. ед.

Практически всегда метод наименьшего тарифа дает более приближенный к оптимальному опорный план, чем метод северо-западного угла. Проверим план, построенный методом наименьшего тарифа, на оптимальность. Для этого по занятым объемами перевозок ячейкам составим систему уравнений по формуле (3.4):

Неизвестные потенциалы u₁, u₂, u₃, v₁, v₂, v₃, v₄ находим из этой системы уравнений, полагая u₁ =0. Тогда из первого и второго уравнений: v₂ =1, v₄ =4; далее из предпоследнего: u₂ =4; затем из третьего и четвертого уравнений: v₁ =-2, v₃ =4; наконец, из последнегоуравнения: u₃ =2. Перепишем матрицу перевозок, добавив справа столбец с потенциалами u_i, а внизу - строку с потенциалами v_j (табл. 3.5).

Таблица 3.5

bj аi					ui
	-		-
		-
	-	-		-
vj	-2

Посчитаем оценки свободных ячеек по формуле (3.6):

План не оптимальный, так как оценка D₃₂ положительна, поэтому ставим в этой ячейке знак «+» и строим цикл (табл. 3.6). Заметим, что такой цикл всегда существует и он единственный.

 

Таблица 3.6

bj аi					ui
	-	1 6	-	4 1
		-	8 1	8
	-	1 -	6	-
vj	-2

Наименьший объем груза в «минусовых» ячейках: d = 4. Новую таблицу перевозок составляем с учетом следующих изменений: в ячейках со знаком «+» объем перевозок увеличится на 4 ед., в ячейках со знаком «-» уменьшится на 4 ед., а в остальных останется без изменений (табл. 3.7).

Таблица 3.7

bj аi					ui
	-		-
		-		-
	-			-
vj

или

.

Для проверки полученного плана на оптимальность по формуле (3.4) составляем систему уравнений:

Решив систему, получаем новые значения для потенциалов u_i, v_j, которые заносим в таблицу перевозок (таблица 3.7).

По формуле (3.5) определим оценки свободных ячеек:

Проверяя план на оптимальность, замечаем, что все оценки свободных ячеек не положительны, т.е. полученный план перевозок является оптимальным. Стоимость перевозки: min F (X^*) = 84 ден. ед.

Пример 2. Составить оптимальный план перевозки грузов от трех поставщиков с грузами 240, 40, 110 т к четырем потребителям с запросами 90, 190, 40 и 130 т. Стоимость перевозок единицы груза от каждого поставщика к каждому потребителю с_ij задана матрицей

.

Решение. Равенство (3.3) не выполняется, поэтому задача открытая, так как суммарная потребность в грузе превышает суммарный запас на 60 т. Для решения этой задачи вводим фиктивного поставщика с запасом груза 60 т.

Модель задачи запишется следующим образом: х_ij - количество груза, перевозимого из пункта i в пункт j, где .

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

Исходное опорное решение, найденное методом наименьшего тарифа, следующее (табл. 3.8).

Таблица 3.8

bj аi
	-		-
	-	0		-
		-	-
	-		-	-

или

.

Проверим исходный опорный план на вырожденность. Вычислим m + n -1= 4+4-1 = 7; число занятых ячеек равно 6. Так как эти значения не совпадают, найденный опорный план является вырожденным. Для исключения вырожденности поместим нулевую поставку в ячейку (2, 2).

Оценки свободных ячеек равны:

План не оптимальный, так как оценка D₁₃ больше нуля, перераспределим грузы (табл. 3.9).

Таблица 3.9

bj аi					ui
	-	13 130	9 -
	-	8 0	7	-	- 5
		-	-		- 2
	-		-	-
vj

Запишем полученное перераспределение грузов в таблицу 3.10.

Оценки свободных ячеек:

Таблица 3.10

bj аi					ui
	-
	-	40	-	-	- 5
		-	-		- 2
	-		-	-
vj

или

.

Так как все оценки свободных ячеек положительные, получили оптимальное решение. Чтобы получить оптимальный план исходной задачи, нужно отбросить последнюю строку, соответствующую фиктивному поставщику:

.

Отброшенная строка плана Х^* означает, сколько единиц груза недополучат потребители, а именно второй потребитель недополучит 60 т груза.

Решение транспортных задач с использованием MSExcel

Решим задачу примера 1 в MS Excel.

Экранная форма, задание переменных, целевой функции и ограничений задачи и ее решение представлены на рис. 3.1-3.3 и в таблице 3.11.

Рисунок 3.1 – Экранная форма

Таблица 3.11

Объект математической модели	Выражение в MS Excel
Переменные задачи	C3: F5
Формула в целевой ячейке G13	=CУMMПРOИЗB(C3: F5; C11: F13)
Ограничения по строкам в ячейках G3, G4, G5	=CУMM(C3: F3) =CУMM(C4: F4) =CУMM(C5: F5)
Ограничения по столбцам в ячейках С6, D6, Е6, F6	=СУММ(С3: С5) =CУMM(D3: D5) =СУММ(Е3: Е5) =CУMM(F3: F5)
Суммарные запасы и суммарные потребности в ячейках I7, Н8	=СУММ(I3: I5) =CУMM(C8: F8)

Ограничения неотрицательности переменных () можно задать в виде ограничения $C$3: $F$5> =0 или установить флажок «Неотрицательные значения» в окне «Параметры поиска решения».

Рисунок 3.2 – Ограничения

Требование целочисленности ($C$3: $F$5=целое) задается, если это требуется по условию задачи.

Рисунок 3.3 – Экранная форма после получения решения