Расстояния между полями и силосными траншеями

⇐ ПредыдущаяСтр 3 из 3

Поля	Силосные траншеи
1-ый	2-ой	3-ий	4-ый
1-е
2-е
3-е
4-е
5-е

Составить такой план перевозок, чтобы суммарные транспортные затраты были минимальными. Опорный план найти методом наименьшего элемента. Оптимальный план найти методом потенциалов.

Решение. Проверим баланс между общим объёмом А зелёной массы, вывозимой с полей и суммарной вместимостью Ввсех силосныхтраншей. A = a₁+a₂+a₃+a₄+a₅=400+500+700+ +900+ +1100 = 3600, В = b₁+b₂+b₃+b₄ =1200+600+800+1000 =3600. Так как А = В, то задача является закрытой.

Определим опорный план методом наименьшего элемента. Среди стоимостей за перевозку зелёной массы с полейксилосным траншеям выберем наименьшую. Это стоимость перевозки между третьим полем и второйсилосной траншеей с₃₂=1. Поставим зелёную массу в клетку (3; 2).

Объём поставки в эту клетку – минимум из остатков объёма зелёной массы 3 поля и вместимости 2 силосной траншеи. Так как зелёная масса ещё не распределялась, то остатки равны начальным значениям массы и вместимости: 700 и 600 тонн. Остаток 600 т будет минимальным. Поставляем в клетку (3; 2) 600 т зелёной массы.

Пересчитываем остатки: с 3-го поля осталось перевезти 700 – 600 = 100 т, а остаток вместимости 2-ойсилосной траншеи стал равным 600 – 600 = 0. 2-уюсилосную траншею вычёркиваем из дальнейшего рассмотрения. Нумеруем таблицы в левом верхнем углу. Выполненные действия отметим в таблице 1а.

1а					Остатки
	⁵	⁶–	²	²
	⁹	⁷–	⁴	⁶
	⁷	¹600	⁴	⁵
	⁵	²–	²	⁴
	⁶	⁴–	³	⁴
Остатки		0 ×

Переходим ко второму шагу распределения зелёной массы с полей в силосные траншеи. Среди всех оплат в оставшейся части таблицы выберем минимальную. Это стоимости перевозки с₁₃=2, с₁₄=2 и с₄₃=2. Выберем любую из клеток (1; 3), (1; 4), (4; 3), например, клетку (1; 4). Определим объём поставки в эту клетку. Остатки равны: для поля 400 т, для траншеи 1000 т. Минимальный– 400 т. Поставляем в клетку (1; 4) 400 т зелёной массы. Пересчитываем остатки: для 1-го поля: 400 – 400 = 0 т, для 4-ойтраншеи: 1000 – 400 = 600 т (табл. 1б). Вычёркиваем 1-ое поле из дальнейшего рассмотрения.

1б					Остатки
	⁵–	⁶–	²–	²400	0×
	⁹	⁷–	⁴	⁶
	⁷	¹600	⁴	⁵
	⁵	²–	²	⁴
	⁶	⁴–	³	⁴
Остатки		0 ×

Переходим к третьему шагу.

Среди всех стоимостей в оставшейся части таблицы находим минимальную. Это стоимость с₄₃=2. Выбираем клетку (4; 3). Остатки: для поля – 900 т, для траншеи 800 – т. Минимальным будет остаток 800 т. Поставляем в клетку (4; 3) 800 т. Пересчитываем остатки: 900–800=100 т – остаток для поля, 800–800=0 т – остаток для траншеи(табл. 1в). 3–ютраншею вычёркиваем из дальнейшего рассмотрения.

1в					Остатки
	⁵–	⁶–	²–	²400	0×
	⁹	⁷–	⁴–	⁶
	⁷	¹600	⁴–	⁵
	⁵	²–	²800	⁴
	⁶	⁴–	³–	⁴
Остатки		0 ×	0×

Переходим к четвёртому шагу. Наименьшие оплаты перевозки с₄₄=4, с₅₄=4. Выбираем клетку (5; 4).Остатки равны: для поля 1100 т, для траншеи 600 т. Остаток 600 т будет минимальным. Пересчитываем остатки (табл. 1г): для поля 1100 – 600 = 500 т, для траншеи 600 – 600 = 0 т.Вычёркиваем 4-уютраншею.

1г					Остатки
	⁵–	⁶–	²–	²400	0×
	⁹	⁷–	⁴–	⁶–
	⁷	¹600	⁴–	⁵–
	⁵	²–	²800	⁴–
	⁶	⁴–	³–	⁴600
Остатки		0 ×	0×	600, 0×

Переходим к пятому шагу. Минимальнаяоплата перевозки с₄₁=5. Выбираем клетку (4; 1). Остатки равны: для поля–100 т, для траншеи – 1200 т. Минимальным будет остаток 100 т. Делаем поставку в клетку (4; 1) в объёме100 т. Опять пересчитываем остатки: для поля 100– 100 = 0 т, для траншеи 1200 – 100 =1100 т (табл. 1д).

1д					Остатки
	⁵–	⁶–	²–	²400	0×
	⁹	⁷–	⁴–	⁶–
	⁷	¹600	⁴–	⁵–
	⁵100	²–	²800	⁴–	100, 0×
	⁶	⁴–	³–	⁴600
Остатки		0 ×	0×	600, 0×

Переходим к шестому шагу. Оплата перевозки с₅₁=6. Выбираем клетку (5; 1). Остатки равны: поле 500 т, траншея – 1100 т. Минимальным будет остаток 500 т. Объём поставки 500 т. Остатки: 500 – 500 = 0 т для поля, 1100–500=600 т для траншеи (табл. 1е). 5-ое поле вычёркиваем. Оплата перевозки с₃₁=7. Выбираем клетку (3; 1).

1е					Остатки
	⁵–	⁶–	²–	²400	0×
	⁹	⁷–	⁴–	⁶–
	⁷–	¹600	⁴–	⁵–
	⁵100	²–	²800	⁴–	100, 0 ×
	⁶500	⁴–	³–	⁴600	500, 0×
Остатки	1100, 600	0 ×	0×	600, 0×

Переходим к седьмому шагу. Минимальной будет оплата перевозки с₃₁=7. Выбираем клетку (3; 1).Остатки: поле – 100, траншея – 600 т. Минимальный остаток 100 т. Поставка в клетку (3; 1) в объёме 100 т. Пересчитываем остатки: 100 т для поля, для траншеи 100–100 =500 т (табл. 1ж). Вычёркиваем 3-е поле.

1ж					Остатки
	⁵–	⁶–	²–	²400	0×
	⁹	⁷–	⁴–	⁶–
	⁷100	¹600	⁴–	⁵–	100, 0×
	⁵100	²–	²800	⁴–	100, 0 ×
	⁶500	⁴–	³–	⁴600	500, 0×
Остатки	1100, 600, 500	0 ×	0×	600, 0×

Осталась последняя клетка, которая незаполнялась, это клетка (2; 1). Проверяем баланс остатков: для поля остаток 500, для траншеи 500 т. Баланс есть. Поставляем в клетку остатки зелёной массы и поля, и траншеи в размере 500 т и вычёркиваем из рассмотрения и поле, и траншею (табл. 1з).

1з					Остатки
	⁵–	⁶–	²–	²400	0×
	⁹500	⁷–	⁴–	⁶–	0×
	⁷100	¹600	⁴–	⁵–	100, 0×
	⁵100	²–	²800	⁴–	100, 0 ×
	⁶500	⁴–	³–	⁴600	500, 0×
Остатки	1100, 600, 500, 0×	0 ×	0×	600, 0×

Мы получили опорный план, построенный методом наименьшего элемента (табл. 1).


⁵	⁶	²	²400
⁹500	⁷	⁴	⁶
⁷100	¹600	⁴	⁵
⁵100	²	²800	⁴
⁶500	⁴	³	⁴600

Будем искать оптимальный план. Для этогоприменим метод потенциалов.

Оптимальный план будем находить пошагово. На каждом шаге метода осуществляем переход от одного опорного плана к другому, выполняя следующие действия: 1) вычислим потенциалы полей и силосных траншей; 2) вычислим косвенные издержки для свободных клеток; 3) проверим признак оптимальности плана; 4) одну из свободных клеток выберем для перераспределения зелёной массы; 5) для выбранной клетки построим цикл перераспределения зелёной массы; 6) пометим клетки цикла знаками «+» и «–»; 7) определим объём перераспределения зелёной массы; 8) построим новый опорный план.

Выполняем действие 1). Вычислим потенциалы полей и силосных траншейпо заполненным и условно заполненным клеткам. Произвольно задаём значение одного из потенциалов. Например, положим значение потенциала для первого поля u₁равным нулю.Рассматриваем первую строку (табл. 2а).

2а					u_i
	⁵	⁶	²	²400
	⁹500	⁷	⁴	⁶
	⁷100	¹600	⁴	⁵
	⁵100	²	²800	⁴
	⁶500	⁴	³	⁴600
v_j

В строкенаходим нерассмотренные заполненные и условно заполненные клетки. Это клетка (1; 4). По клетке определяем потенциал 4-ойсилосной траншеи: v₄=u₁+c₁₄=

=0 + 2 = 2.

Больше нерассмотренных заполненных и условно заполненных клеток в первой строке нет. Переходим к последнему вычисленному потенциалу, к потенциалу v₄= 2. Это потенциал 4-ой силосной траншеи. Рассматриваем 4-ый столбец (табл. 2б).

2б					u_i
	⁵	⁶	²	²400
	⁹500	⁷	⁴*	⁶
	⁷100	¹600	⁴	⁵
	⁵100	²	²800	⁴
	⁶500	⁴	³	⁴600	-2
v_j

Находим в этом столбце нерассмотренные заполненные и условно заполненные клетки. Это клетка (5; 4). По этой клетке определяем потенциал 5-ого поля: u₅=v₄–c₅₄= =2 – 4 = –2. Большенерассмотренных заполненных и условно заполненных клеток в четвёртом столбце нет. Переходим к последнему вычисленному потенциалу, к потенциалу u₅= –2. Это потенциал 5-ого поля. Рассматриваем 5-ую строку (табл. 2в).

2в					u_i
	⁵	⁶	²	²400
	⁹500	⁷	⁴*	⁶
	⁷100	¹600	⁴	⁵
	⁵100	²	²800	⁴
	⁶500	⁴	³	⁴600	-2
v_j

Находим в этой строке нерассмотренные заполненные и условно заполненные клетки. Это клетка (5; 1). По этой клетке определяем потенциал 1-ой силосной траншеи: v₁=u₅+c₅₁= –2 + 6 = 4. Больше нерассмотренных заполненных и условно заполненных клеток в пятой строке нет. Переходим к последнему вычисленному потенциалу, к потенциалу v₁= –2. Это потенциал 1-ой силосной траншеи. Рассматриваем 1-ый столбец (табл. 2г).

2г					u_i
	⁵	⁶	²	²400
	⁹500	⁷	⁴*	⁶	-5
	⁷100	¹600	⁴	⁵	-3
	⁵100	²	²800	⁴	-1
	⁶500	⁴	³	⁴600	-2
v_j

Находим в этом столбце нерассмотренные заполненные и условно заполненные клетки. Это клетки (2; 1), (3; 1) и (4; 1). По этим клеткам определяем потенциалы 2-ого,

3-его и 4-го полей: u₂=v₁–c₂₁=4–9= –5, u₃=v₁–c₃₁=4–7= –3, u₄=v₁–c₄₁=4–5 = –1. Большенерассмотренных заполненных и условно заполненных клеток в первом столбце нет. Переходим к последним потенциалам u₂= –5, u₃= –3 и u₄= –1. Это потенциалы 2-ого поля, 3-его поля и 4-ого поля. Сначала рассмотрим 2-ую строку (табл. 2д).

2д					u_i
	⁵	⁶	²	²400
	⁹500	⁷	⁴	⁶	-5
	⁷100	¹600	⁴	⁵	-3
	⁵100	²	²800	⁴	-1
	⁶500	⁴	³	⁴600	-2
v_j		-2

Находим в этой строке нерассмотренные заполненные и условно заполненные клетки. Таких клеток нет.

Переходим к следующему вычисленному потенциалу, к потенциалу u₃=–3, потенциалу 3-его поля. Смотрим 3-ю строку (табл. 2д). Находим в этой строке нерассмотренные заполненные и условно заполненные клетки. Это клетка (3; 2). По этой клетке определяем потенциал 2-ой силосной траншеи: v₂=u₃+c₃₂= –3 + 1 = –2. Больше нерассмотренных заполненных и условно заполненных клеток в третьей строке нет.Переходим к следующему вычисленному потенциалу, к потенциалу u₄= –1. Это потенциал 4-тьего поля. Рассматриваем 4-ую строку (табл. 2е).

2е					u_i
	⁵	⁶	²	²400
	⁹500	⁷	⁴	⁶	-5
	⁷100	¹600	⁴	⁵	-3
	⁵100	²	²800	⁴	-1
	⁶500	⁴	³	⁴600	-2
v_j		-2

Находим в этом строке нерассмотренные заполненные и условно заполненные клетки. Это клетка (4; 3). По этой клетке определяем потенциал 3-ей силосной траншеи: v₃=u₄+c₄₃=–1+2 =1. Больше нерассмотренных заполненных и условно заполненных клеток в четвёртой строке нет.Мы вычислили все потенциалы. Результаты вычислений представлены таблицей 2.

					u_i
	⁵	⁶	²	²400
	⁹500	⁷	⁴	⁶	-5
	⁷100	¹600	⁴	⁵	-3
	⁵100	²	²800	⁴	-1
	⁶500	⁴	³	⁴600	-2
v_j		-2

Переходим к выполнению следующего пункта шага метода потенциалов.

2) вычислим косвенные издержки для свободных клеток, которые обозначим Δ _ij. Косвенные издержки для свободных клеток вычисляем по формуле: Δ _ij=c_ij–(v_j–u_i).

Δ ₁₁ =5–(4 – 0)=1; Δ ₁₂ =6–(-2–0) =8; Δ ₁₃=2 – (1 – 0) = 1; Δ ₂₂=7 –(–2+5)=4; Δ ₂₃ = 4 – (1+5) = – 2; Δ ₂₄ = 6–(2+5) = – 1; Δ ₃₃ = 4 – (1+ 3) = 0; Δ ₃₄= 5 – (2+3)= 0; Δ ₄₂=2–( – 2+1) = 3; Δ ₄₄=4–(2+1)=1; Δ ₅₂ =4 – (–2+2) = 4; Δ ₅₃ =3–(1+2)=0.

3) Проверяем признак оптимальности плана: если для всех свободных клеток косвенные издержки положительные (Δ _ij ≥ 0), то опорный план является оптимальным. План не оптимальный, так как Δ ₂₃ = – 2< 0 и Δ ₂₄ = – 1< 0.

4) Выбираем клетку для перераспределения зелёной массы. Это одна из клеток таблицы, для которой косвенные издержки строго отрицательные. Выбираем клетку (2; 3).

5) Для выбранной клетки (2; 3) строим цикл перераспределения зелёной массы. Выбранную свободную клетку (2; 3) включаем в цикл. Далее рассматриваем строку,

содержащую эту клетку. Это вторая строка. Во второй строке ищем заполненные и условно заполненные клетки (табл. 2ж).

2ж					u_i
	⁵	⁶	²	²400
	⁹500	⁷	^{4 *}	⁶	-5
	⁷100	¹600	⁴	⁵	-3
	⁵100	²	²800	⁴	-1
	⁶500	⁴	³	⁴600	-2
v_j		-2

Такие клетки есть, это клетка (2; 1). Так как она единственная, то её включаем в цикл (рис. 3а) и переходим к ней. Рассматриваем столбец, содержащий включённую в цикл клетку (2; 1). Это первый столбец. В первом столбце находим нерассмотренные заполненные и условно заполненные клетки. Это клетки (3; 1), (4; 1) и (5; 1)(табл. 2з).

2з					u_i
	⁵	⁶	²	²400
	⁹500	⁷	^{4 *}	⁶	-5
	⁷100	¹600	⁴	⁵	-3
	⁵100	²	²800	⁴	-1
	⁶500	⁴	³	⁴600	-2
v_j		-2

Выбираем любую из них, например клетку (3; 1). Включаем её в цикл (рис. 3б). Переходим к ней. Cмотрим строку, содержащую эту клетку. Это третья строка. В третьей строке ищем нерассмотренные заполненные и условно заполненные клетки (табл. 2и).

2и					u_i
	⁵	⁶	²	²400
	⁹500	⁷	^{4 *}	⁶	-5
	⁷100	¹600	⁴	⁵	-3
	⁵100	²	²800	⁴	-1
	⁶500	⁴	³	⁴600	-2
v_j		-2

Такие клетки есть, это клетка (3; 2). Так как она единственная, то её включаем в цикл (рис. 3в) и переходим к ней.

Рассматриваем столбец, содержащий клетку (3; 2). Это второй столбец. В столбце находим нерассмотренные заполненные и условно заполненные клетки. Таких клеток нет. Вычёркиваем клетку (3; 2) из цикла и переходим к предыдущей клетке цикла, к клетке (3; 1) (рис. 3г).

Опять рассматриваем третью строку. В третьей строке ищем нерассмотренные заполненные и условно заполненные клетки (табл. 2и). Клетки (3; 1) и (3; 2) уже рассматривались, других клеток нет. Вычёркиваем клетку (3; 1) из цикла и переходим к предыдущей клетке цикла, к клетке (2; 1) (рис. 3д). Снова рассматриваем столбец, содержащий клетку (2; 1). В первом столбце находим нерассмотренные заполненные и условно заполненные клетки. Это клетки (4; 1) и (5; 1), клетки (2; 1) и (3; 1) уже рассматривались(табл. 2з). Выбираем любую из них, например клетку (4; 1). Включаем её в цикл (рис. 3е). Переходим к ней. Рассматриваем строку, содержащую клетку (4; 1). Это четвёртая строка (табл. 2к)

(2; 1)

(2; 3)

Рис. 3а

(2; 1)

(2; 3)

(3; 1)

Рис. 3б

(2; 1)

(2; 3)

(3; 1)

Рис. 3в

(3; 2)

(2; 1)

(2; 3)

(3; 1)

Рис. 3г

(3; 2)

(2; 1)

(2; 3)

(3; 1)

Рис. 3д

(2; 1)

(2; 3)

(4; 1)

Рис. 3е

(2; 1)

(2; 3)

(4; 1)

Рис. 3ж

(4; 3)

Рис. 3. Построение цикла для клетки (2; 3)

2к					u_i
	⁵	⁶	²	²400
	⁹500	⁷	^{4 *}	⁶	-5
	⁷100	¹600	⁴	⁵	-3
	⁵100	²	²800	⁴	-1
	⁶500	⁴	³	⁴600	-2
v_j		-2

В этой строке есть заполненная клетка, которая располагается в том же столбце, что и начальная клетка цикла, клетка (2; 3). Это клетка (4; 3). Автоматически её включаем в цикл, и цикл замыкаем (рис. 3е).

Построенный цикл для свободной клетки (2; 3) изображён на рисунке 3ж.

(2; 1)

(2; 3)

(4; 1)

Рис. 5

(4; 3)

–

6) Пометим клетки цикла знаками «+» и «–». Помечать клетки цикла начнём со свободной клетки цикла, клетки (2; 3). Её пометим знаком «+». Далее, двигаясь по циклу в направлении его построения, помечаем остальные клетки цикла, чередуя знаки (рис. 4).

(2; 1)

(2; 3)

(4; 1)

Рис. 4

(4; 3)

–

Клетку (2; 1) пометим знаком «–», клетку (4; 1) знаком «+», клетку (4; 3) знаком «–». В клетки, помеченные знаком «+» зелёную массу будем добавлять, а из клеток, помеченных знаком «–» зелёную массу будем забирать. Клетками, откуда зелёная масса забирается, будут (2; 1) и (4; 3).

7) Определим объём перераспределения зелёной массы. Объём перераспределения зелёной массы Δ V равняется наименьшему из объёмов отрицательных клеток цикла. В клетке (2; 1) объём поставки зелёной массы равняется 500 т, а в клетке (4; 3) – 800 т (рис. 5). Объём перераспределения зелёной массы Δ V равен:

Δ V = min{500; 800}= 500.

8) Строим новый опорный план. Сначала пересчитываем объёмы зелёной массы для клеток цикла (табл. 3):

					u_i
	⁵	⁶	²	²400
	⁹	⁷	⁴500	⁶	-3
	⁷100	¹600	⁴	⁵	-3
	⁵600	²	²300	⁴	-1
	⁶500	⁴	³	⁴600	-2
v_j		-2

для клетки (2; 3) новый объём равен x₂₃ = 0 + 500 = 500 т, для клетки (2; 1) новый объём равен x₂₁ = 500 – 500 = 0 т, для клетки (4; 1) новый объём равен x₄₁ = 100+500 = 600 т, для клетки (4; 3) новый объём равен x₄₃ = 800 – 500 = 300 т. Объём клетки (2; 1) стал равным нулю, её переводим в ранг свободных, а клетку (2; 3) переводим в ранг заполненных. Объёмы остальных клеток таблицы, не вошедших в цикл, не меняются: x₁₄=400, x₃₁=100, x₃₂ =600, x₅₁=500, x₅₄=600 (табл. 3). Шаг метода потенциалов закончен. Переходим к новому шагу. В качестве опорного рассматриваем план, соответствующий таблице 3.

1) Вычислим потенциалы полей и силосных траншей (табл. 3). 2) Вычислим косвенные издержки для свободных клеток: Δ ₁₁ =5–(4–0)=1; Δ ₁₂ =6–(–2–0) =8; Δ ₁₃ =2–(1–0)=1;

Δ ₂₁ =9–(4+3) = 2; Δ ₂₂ =7–(–2+3)=6; Δ ₂₄=6–(2+3)=1; Δ ₃₃=4–(1+3)=0; Δ ₃₄=5–(2+3) =0;

Δ ₄₂=2–(–2+1)=3; Δ ₄₄ =4–(2+1) =1; Δ ₅₂=4–(–2+2)=4; Δ ₅₃=3–(1+2) = 0. 3) Проверим признак оптимальности плана. План оптимальный, так как для всех свободных клеток косвенные издержки больше либо равны нуля (Δ _ij ≥ 0). По таблице 3 выписываем оптимальный план: X* = .Для оптимального плана рассчитываем суммарные транспортные издержки: Z_min = 2∙ 400 +4∙ 500 +7∙ 100 +1∙ 600 +5∙ 600+ +2∙ 300+ +6∙ 500 +4∙ 600 = 13100.

⇐ Предыдущая 1 23