Экономико-математический практикум (стр. 5 из 9)

Значения оценок поместим в левом нижнем углу незанятых клеток табл. 3.4. Фиксируем наибольшую положительную оценку. В данном случае:

. Разрешающей объявим коммуникацию (4,3). Строим цикл пересчета, который показан в табл. 3.4 пунктирной линией.

Величина корректировки ρ=(58,79)=58. Вносим изменение в план: перевозки отрицательного полуцикла уменьшаем на

, а перевозки положительного полуцикла увеличиваем на эту же величину, остальные перевозки оставим без изменения. Переменная х₁₁вводится в базис со значением =58,переменная х₁₄выводится из базиса. Получим план

(табл. 3.5).

План

Таблица 3.5

34	29	39	29	6
0	34		30		39	29	18
	34⁽⁵⁾	48⁽⁴⁾	82
	-1		0		-12
6	40		35		45	41	10
	14⁽⁷⁾	22	36
	0		-6		-2
2	36		38		41	50	8
	29⁽⁶⁾	50⁽¹⁾		79
	-7		0		-19
-19	14		10		13	10	12
	60⁽²⁾	20⁽³⁾	80
	1		7		-25
77	60	22	68	50

Значение функции уменьшилось на (38*16-9*38=290) и стало:

План не оптимален. Заново вычисляем потенциалы и оценки (табл. 3.6). Наибольшая положительная оценка– это

, план не оптимален. Строим цикл пересчета и определяем величину корректировки плана ρ=(48,58)=48.

Таблица 3.6

План X₂

34	29	39	29	6
0	34		30		39	29	18
	14	68⁽⁴⁾	82
	-1		0		-12
6	40		35		45	41	10
	36		36
	0		-6		-2
2	36		38		41	50	8
	65	14		79
	-7		0		-19
-19	14		10		13	10	12
	12	46⁽²⁾	22	80
	1		7		-25
77	60	22	68	50

Значение функции и соответственно транспортные расходы составили

Положительных оценок нет, план Х₂оптимален.

3. Метод Фогеля

В табл. 3.4 показаны последовательность определения базисных переменных, наборы разностей

в строках справа от таблицы, а

в столбцах снизу под таблицей.

План Х₀

Таблица 3.4

1	2	3	4	5	6	7	8
34	30	39	29	18	11	11	11	11	11	11	-	-
34⁽⁶⁾	48⁽⁵⁾	82
34⁽⁶⁾	48⁽⁵⁾	40	35	45	41	10	25	25	25	25	25	25	25	25
14⁽⁷⁾	22⁽⁸⁾	36
14⁽⁷⁾	22⁽⁸⁾	36	38	41	50	8	28	2	-	-	-	-	-	-
29⁽²⁾	50⁽¹⁾	79
29⁽²⁾	50⁽¹⁾	14	10	13	10	12	2	2	2	2	-	-	-	-
12⁽⁴⁾	68⁽³⁾	80
12⁽⁴⁾	68⁽³⁾	77	60	22	68	50
Этап 1	20	20	26	19	2
Этап 2	20	20	26	19	-
Этап 3	20	20	26	19	-
Этап 4	20	20	26	12	-
Этап 5	20	-	26	-	-
Этап 6	20	-	26	-	-
Этап 7	16	-	26	-	-
Этап 8	-	-	26	-	-

Суммарные транспортные расходы, соответствующие данному плану перевозок равны

Сравним расчеты, проделанные тремя методами. Транспортные расходы, рассчитанные:

1) методом северо-западного угла составили 8452 у.е.,

2) методом минимального элемента соответственно 6342 у.е.,

3) пересчитанные по методу потенциалов – 6118 у.е.,

4) методом Фогеля соответственно – 6390 у.е.

Наименьшие транспортные расходы составили расходы, рассчитанные по методу потенциалов.

Задача № 4

Сетевая задача

Ниже приведено 10 вариантов транспортной задачи в сетевой постановке. Каждая задача изображена в виде неориентированного связного графа. На ребрах проставлены значения тарифов

, на вершинах (в кружках) — значения запасов-потребностей

. Построить пробный допустимый план, проверить его на оптимальность. В случае необходимости довести до оптимального плана методом потенциалов.

Решение. Построим пробный опорный план (рис.1).

Рис. 1. Пробный план перевозок по сети.

В качестве начальной выберем вершину 12, которая является поставщиком с запасами в 20 единиц продукции. Из этой вершины отправим транзитом через 13 с запасами 45 ед. и 10 вершину с запасами 30 единиц в 8 вершину и удовлетворяем её потребности в 40 единиц. Оставшиеся 55 единиц отправим в 6 вершину с потребностями 40 единиц, оставшиеся 15 единиц отправляем в 5 вершину с потребностями 10 единиц, оставшиеся 5 единиц направим в 1 вершину, потребности которой составляют 35 единиц.

Из 11 вершины с запасами 45 единиц направим транзитом через 9 вершину , всего запасов стало 75 единиц, направим их транзитом через 7 вершину в 4 вершину, потребности которой составляют 40 единиц, оставшиеся 35 единиц направим во 2 вершину и удовлетворим ее потребности.

Из 3 вершины с запасами 30 единиц направим транзитом через 7 вершину в 1 вершину, потребности которой удовлетворим.

В результате проведенных операций все запасы вывезены, потребности всех потребителей удовлетворены.

В результате проведенных операций все запасы вывезены, потребности всех потребителей удовлетворены. Число базисных ребер здесь равно 11, число вершин 13.