Вариант № 2.

Тема 3.

Транспортная задача

Решение:

Суммарные запасы Σ а_і = 180 + 200 + 150 = 530 ед,
суммарные потребности Σ b_j= 130 + 160 + 190 = 480 ед.

Σ а_і ≠ Σb_j, запасы не равны потребностям, т.е. это открытая модель транспортной задачи.
Вводим балансовый пункт потребления (фиктивного потребителя) В_4,ф с потребностями b₄ = 530 – 480 = 50 ед.

Составим математическую модель задачи.

Пусть х_іj – количество единиц, которое планируется перевезти из пункта А_і в пункт В_j (это план перевозок). Тогда общая стоимость всех перевозок будет :

Z = Σ Σ C_ij х_ij, её необходимо минимизировать.

Количество единиц не может быть отрицательной, поэтому х_іj ≥ 0.

Из условия задачи следует, что должны выполняться такие условия :

Σ х_іj = а_і , і =1,2,3 , т.е. весь товар из пунктов А_і необходимо вивезти.

Кроме того потребности В_j должны быть полностью удовлетворены, т.е.

Σ х_іj = b_j , j = 1,2,3,4.

Таким образом, математическая модель задачи имеет вид :


Z = Σ Σ Cij х_іj → min

Σ х_іj = а_і , і=1,2,3

Σ х_іj = b_j , j = 1,2,3,4.

х_іj ≥ 0



Построим начальный опорный план , пользуясь правилом «минимального элемента» .

Составим транспортную таблицу, в углы клеток запишем заданные тарифы С_іj ,а в середины клеток будемо последовательно заносить значения х_іj по схеме :

Из всей таблицы стоимостей выбираем клетку А_іВ_j с наименьшей стоимостью С_іj , т.е. ищем min С_іj , и заносимо в неё число х_іj = min { а_і , b_j }.

Потом вычёркиваем и больше не рассматриваем строку, что соответствует поставщику, запасы которого полностью исчерпаны, или столбец, что соответствует потребителю, потребности которого полностью удовлетворены и снова ищем min С

---

_іj, и так заполняем всю таблицу, пока все запасы не будут исчерпаны, а все потревности – удовлетворены. Если клеток с одинаковым значением min С_іj несколько, то берём любую из них. Фиктивные клетки, т.е. клетки столбца В_4,ф заполняем в последнюю очередь.

В1

В2

В3

В4,ф

Запасы

аі

А1

2

____

9

___

7

0

130

50

а1 = 180

а1 ’= 50

А2

___

4

5

1

____

0

10

190

а2 = 200

а2 ’= 10

А3

___

6

3

___

2

____

0

150

а3 = 150

Потребн.

bj

b1 = 130

b2 = 160

b3 = 190

b4 = 50

b2 = 10

---

1) min С_іj =C₂₃=1 ; х₂₃ =min { а₂ , b₃ } = min { 200, 190 } = 190 ;

Столбец В₃ вычёркиваем, а₂ ’= 200 – 190 = 10 ед.

2) min С_іj = С₁₁ =2 ; х₁₁ = min { а₁ , b₁ } = min { 180, 130 } = 130 ;
Столбец В₁ вычёркиваем, а₁ ’ =180 – 130 = 50 ед.
3) min С_іj = С₃₂ =3 ; х₃₂ = min { а₃ , b₂ } = min { 150, 160 } = 150 ;
Строку А₃ вычёркиваем, b₂ ’= 160 – 150 = 10 ед.

4) min С_іj =C₂₂ =5 ; х₂₂ =min { а₂ , b₂ } = min { 10, 10 } = 10 ;

Столбец В₂ и строку А₂ вычёркиваем

5) осталась одна клетка А₁В₄ ; х₁₄ = min { а₁’, b₄ } = min { 50, 50 } = 50.
В итоге таблица заполнена полностью. Получилось 5 занятых и 7 свободных клеток. Начальный опорный план имеет вид:
х₁₁ = 130; х₁₄ = 50; х₂₂ = 10; х₂₃ = 190; х₃₂ = 150; остальные х_іj = 0
При этом стоимость перевозок:

Z = 130 ∙ 2 + 10 ∙ 5 + 190 ∙ 1 + 150 ∙ 3 + 50 · 0 = 950.


Метод потенциалов.
Сначала проверяем этот план на оптимальность. Для этого вычисляем потенциалы u_iиv_j исходя из условия : u_i+v_j = С_іj для всех занятых клеток, причём u₁= 0. Опорный план должен быть невырожденный, т.е. число занятых клеток должно быть равно m + n – 1 = 3 + 4 – 1 = 6 , а в таблице только 5 занятых клеток, поэтому в одну клетку, например А₂В₁ , заносим нулевую перевозку

х₂₁ = 0 и считаем эту клетку занятой.

Получаем систему из 6 уравнений, из которой находим потенциалы u_iиv_j :




Клетка А₁В₁ → u₁ + v₁ = 4 u₁ = 0

Клетка А₁В₄ → u₁ + v₄ = 8 u₂ = 2

Клетка А₂В₁ → u₁ + v₅ = 0 u₃ = 0

Клетка А₂В₂ → u₂ + v₂ = 1 => v₁ = 2

Клетка А₂В₃ → u₂ + v₅ = 0 v₂ = 3
Клетка А₃В₂ → u₃ + v₃ = 2 v₃ = -1
v₄ = 0
Перепишем транспортную таблицу, добавив к ней строку и столбец для записи

потенциалов, и проверим выполнение условия оптимальности : u_i+v_j ≤ Сіj для
всех свободных ( не занятых ) клеток.

	vj  uі	В1		В2		В3		В4
		v1 = 2		v2 = 3		v3 = -1		v4 = 0		аі
А1	u1 = 0	+	2		9		7	–	0
		130						50		180
А2	u2 = 2	–	4		5		1		0
		0		10		190		+		200
А3	u3 = 0		6		3		2		0
				150						150
bj		130		160		190		50		530

---

?

Для свободных клеток : u_i+v_j ≤ С_іj
Клетка А₁В₂ → u₁ + v₂ = 0 + 3 = 3 < 9

Клетка А₁В₃ → u₁ + v₃ = 0 + (-1) = -1 < 7

Клетка А₂В₄ → u₂ + v₄ = 2 + 0 = 2 > 0

Клетка А₃В₁ → u₃ + v₁ = 0 + 2 = 2 < 6

Клетка А₃В₃ → u₃ + v₃ = 0 + (-1) = -1 < 2

Клетка А₃В₄ → u₃ + v₄ = 0 + 0 = 0 = 0
Видим, что условие оптимальности нарушено в клетке А₂В₄ , т.е. начальный опорний план не является оптимальным, т.е. его можно улучшить, т.е. построить новый опорный план, стоимость которого будет меньше. Для этого нужно перераспределить груз по клеткам таблицы. Строим цикл, т.е. замкнутую прямоугольную ломаную линию, одна вершина которого находится в клетке, в которой нарушено условие оптимальности , т.е. в клетке А₂В₄ , а остальные вершины – в занятых клетках. Вершины цикла по очереди отмечаем знаками “+” и “–“ , начиная с клетки А₂В₄ , затем среди клеток с “–“ выбираем наименьшее значение х_іj :
θ₀ = min { х_іj } = min { 50, 0 } = 0 - в клетке А₂В₁

Далее, двигаясь по вершинам цикла, добавляем это значение θ₀ к значениям х_іj в клетках с “+” и отнимаем от значений х_іj в клетках с “–” . Но, так как θ₀ = 0, то значения перевозок не меняются, просто нулевая перевозка переносится из клетки А₂В₁ в клетку А₂В₄.
Новую таблицу снова проверяем на оптимальность , т.е. вычисляем (непосредственно в таблице) новые значения потенциалов и проверяем выполнение условия оптимальности.

	vj  uі	В1		В2		В3		В4
		v1 = 2		v2 = 5		v3 = 1		v4 = 0		аі
А1	u1 = 0		2		9		7		0
		130						50		180
А2	u2 = 0		4		5		1		0
				10		190		0		200
А3	u3 = -2		6		3		2		0
				150						150
bj		130		160		190		50		530

---

?

Для свободных клеток : u_i+v_j ≤ С_іj
Клетка А₁В₂ → u₁ + v₂ = 0 + 5 = 5 < 9

Клетка А₁В₃ → u₁ + v₃ = 0 + 1 = 1 < 7

Клетка А₂В₁ → u₂ + v₁ = 0 + 2 = 2 < 4

Клетка А₃В₁ → u₃ + v₁ = -2 + 2 = 0 < 6

Клетка А₃В₃ → u₃ + v₃ = -2 + 1 = -1 < 2

Клетка А₃В₄ → u₃ + v₄ = -2 + 0 = -2 < 0
Условие оптимальности виполнено для всех свободных клеток, значит этот план является оптимальним, т.е. его стоимость минимальна :
х₁₁ = 130; х₁₄ = 50; х₂₂ = 10; х₂₃ = 190; х₃₂ = 150; остальные х_іj = 0


Z _min = 950
Оптимальний план перевозок:
Из пункта А₁ → в пункт В₁ - 130 ед.

Из пункта А₁ → в пункт В_4,ф - 50 ед. (останутся невывезенными)

Из пункта А₂ → в пункт В₂ - 10 ед.

Из пункта А₂ → в пункт В₃ - 190 ед.

Из пункта А₃ → в пункт В₂ - 150 ед.

---

Смотрите также файлы

• северокавказская государственнаяакадемия среднепрофессиональный колледж.docx

• Контрольное списывание 4 класс iv четверть. Скворцы.doc

• 1 станция собери пословицу.docx

• Отдел моховидные.docx

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