2. Составить математическую модель транспортной задачи. (1 балл)

Целевая функция – это стоимость всех перевозок.

Z = 2х₁₁+3х₁₂+2х₁₃+4х₁₄+3х₂₁+2х₂₂+5х₂₃+х₂₄+4х₃₁+3х₃₂+2х₃₃+6х₃₄→min

3. Решить задачу методом северо-западного угла. (1 балл)

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

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

Заполним транспортную таблицу.

Поставщики	Потребители (пункты назначения)				Запасы
			B3
	=20	=10			30
		=20	=20		40
			=10	=10	20
Заявки	20	30	30	10	90

Подставим найденные значения в целевую функцию, Найдем стоимость перевозок. Z = 2х₁₁+3х₁₂+2х₁₃+4х₁₄+3х₂₁+2х₂₂+5х₂₃+х₂₄+4х₃₁+3х₃₂+2х₃₃+6х₃₄=

= 2*20+3*10+2*20+5*20+2*10+6*10=290 ден.ед

Ответ: план перевозок, найденный по методу северо-западного угла, дает стоимость перевозок 290 ден. ед.

4. Решить задачу методом Фогеля. Сравнить полученные результаты. (1 балл)

Метод Фогеля состоит в вычислении для каждой строки транспортной таблицы разницы между двумя наименьшими тарифами. Аналогичное действие выполняют для каждого столбца этой таблицы. Наибольшая разница между двумя минимальными тарифами соответствует наиболее предпочтительной строке или столбцу (если есть несколько строк или столбцов с одинаковой разницей, то выбор между ними произволен). В пределах этой строки или столбца отыскивают ячейку с минимальным тарифом, куда пишут отгрузку. Строки поставщиков или столбцы потребителей, которые полностью исчерпали свои возможности по отгрузке или потребности которых в товаре были удовлетворены, вычеркиваются из таблицы и вычисление повторяются до полного удовлетворения спроса и исчерпания отгрузок без учета вычеркнутых ячеек, то есть когда все запасы будут исчерпаны, а все заявки клиентов будут удовлетворены.

Вычислим разницы между двумя минимальными тарифами по строкам и по столбцам.

	Стр 1	Стр 2	Стр 3	Столб 1	Столб 2	Столб 3	Столб 4
Мин 1	2	1	2	2	2	2	1
Мин 2	2	2	3	3	3	2	4
Разница	0	1	1	1	1	0	3

Наиболее предпочтителен столбец 4, поскольку разница для него максимальна.

В столбце 4 найдем минимальную цену — 1 ден.ед/т в строке 2. В нашем примере это ячейка (2;4) (2-й поставщик, 4-й потребитель), где цена доставки = 1 ден.ед. Вписываем в эту ячейку максимальный объем, который позволяет запас поставщика и спрос потребителя х₂₄=10. Поскольку спрос потребителя В4 – полностью удовлетворен, то потребитель В4 выходит из игры., Зачеркнем соответствующий столбец.

Вновь составляем таблицу для оставшихся строк и столбцов.

	Стр 1	Стр 2	Стр 3	Столб 1	Столб 2	Столб 3
Мин 1	2	2	2	2	2	2
Мин 2	2	3	3	3	3	2
Разница	0	1	1	1	1	0

Есть несколько строк и столбцов с одинаковой предпочтительностью, возьмем любую из них, например строку 2, а в ней — выберем минимальный тариф.

В нашем примере это ячейка (2;2) (2-й поставщик, 2-й потребитель), где цена доставки = 2 ден.ед. Вписываем в эту ячейку максимальный объем, который позволяет запас поставщика и спрос потребителя (х₂₂=30). Поскольку спрос потребителя В2 полностью удовлетворен, зачеркиваем столбец В2. Возможности поставщика А2 также исчерпаны, зачеркиваем строку А2. И поставщик А2 и потребитель В2 – выходят из игры.

Из оставшихся строк и столбцов составляем таблицу минимальных элементов.

	Стр 1	Стр 3	Столб 1	Столб 3
Мин 1	2	2	2	2
Мин 2	2	4	4	2
Разница	0	2	2	0

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

В нашем примере это ячейка (3;3) (3-й поставщик, 3-й потребитель), где цена доставки = 2 ден.ед. Вписываем в эту ячейку максимальный объем, который позволяет запас поставщика и спрос потребителя (минимальное значение между 20 и 30 т, то есть X₃₃ =20). Поскольку возможности поставщика А3 полностью исчерпаны, зачеркиваем соответствующую строку.

Остался только поставщик А1. Назначаем X₁₁=20 единиц груза для потребителя В1.

Все запасы исчерпаны, все заявки выполнены.

Поставщики (пункты отправления)	Потребители (пункты назначения)				Запасы
			B3
	=2 =20	=3	=2 =10	=4	=30
	=3	=2 =30	=5	=1 =10	=40
	=4	=3	=2 =20	=6	=20
Потребности	=20	=30	=30	=10	90

Найдем стоимость перевозок: Z= 2*20+2*10+2*30+1*10+2*20 = 170 ден.ед – это оптимальный план, т.е. минимальная стоимость перевозок?

Ответить на этот вопрос можно, если выполнить вычисления методом потенциалов, или выполнить расчеты в программе MS Excel.