- Lektsia - бесплатные рефераты, доклады, курсовые работы, контрольные и дипломы для студентов - https://lektsia.info -

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

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

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

Решение. Проверим баланс между общим объёмом А зелёной массы, вывозимой с полей и суммарной вместимостью Ввсех силосныхтраншей. A = a1+a2+a3+a4+a5=400+500+700+ +900+ +1100 = 3600,В = b1+b2+b3+b4 =1200+600+800+1000 =3600. Так как А = В, то задача является закрытой.

 

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

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

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

Остатки
5 6 2 2  
9 7 4 6  
7 1 600 4 5
5 2 2 4  
6 4 3 4  
Остатки   0 ×      

Переходим ко второму шагу распределения зелёной массы с полей в силосные траншеи. Среди всех оплат в оставшейся части таблицы выберем минимальную. Это стоимости перевозки с13=2, с14=2 и с43=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-ое поле из дальнейшего рассмотрения.

Остатки
5 6 2 2 400
9 7 4 6  
7 1 600 4 5
5 2 2 4  
6 4 3 4  
Остатки   0 ×    

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

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

Остатки
5 6 2 2 400
9 7 4 6  
7 1 600 4 5
5 2 2 800 4
6 4 3 4  
Остатки   0 ×  

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

Остатки
5 6 2 2 400
9 7 4 6  
7 1 600 4 5
5 2 2 800 4
6 4 3 4 600
Остатки   0 × 600, 0×  

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

Остатки
5 6 2 2 400
9 7 4 6  
7 1 600 4 5
5 100 2 2 800 4 100, 0×
6 4 3 4 600
Остатки 0 × 600, 0×  

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

Остатки
5 6 2 2 400
9 7 4 6  
7 1600 4 5
5 100 2 2800 4 100, 0 ×
6 500 4 3 4 600 500, 0×
Остатки 1100, 600 0 × 600, 0×  

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

Остатки
5 6 2 2 400
9 7 4 6  
7 100 1 600 4 5 100, 0×
5 100 2 2 800 4 100, 0 ×
6 500 4 3 4 600 500, 0×
Остатки 1100, 600,500 0 × 600, 0×  

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

Остатки
5 6 2 2 400
9 500 7 4 6
7 100 1600 4 5 100, 0×
5 100 2 2800 4 100, 0 ×
6 500 4 3 4 600 500, 0×
Остатки 1100,600, 500, 0× 0 × 600, 0×  

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

5 6 2 2 400
9 500 7 4 6
7 100 1 600 4 5
5 100 2 2 800 4
6 500 4 3 4 600

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

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

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

 

ui
5 6 2 2 400
9 500 7 4 6  
7 100 1 600 4 5  
5 100 2 2 800 4  
6 500 4 3 4 600  
vj        

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

=0 + 2 = 2.

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

 

ui
5 6 2 2 400
9 500 7 4 * 6  
7 100 1 600 4 5  
5 100 2 2 800 4  
6 500 4 3 4 600 -2
vj        

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

ui
5 6 2 2 400
9 500 7 4 * 6  
7 100 1 600 4 5  
5 100 2 2 800 4  
6 500 4 3 4 600 -2
vj      

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

ui
5 6 2 2 400
9 500 7 4 * 6 -5
7 100 1 600 4 5 -3
5 100 2 2 800 4 -1
6 500 4 3 4 600 -2
vj      

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

3-его и 4-го полей: u2=v1–c21=4–9= –5, u3=v1–c31=4–7= –3, u4=v1–c41=4–5 = –1. Большенерассмотренных заполненных и условно заполненных клеток в первом столбце нет. Переходим к последним потенциалам u2= –5, u3= –3 и u4= –1. Это потенциалы 2-ого поля, 3-его поля и 4-ого поля. Сначала рассмотрим 2-ую строку (табл. 2д).

ui
5 6 2 2 400
9 500 7 4 6 -5
7 100 1 600 4 5 -3
5 100 2 2 800 4 -1
6 500 4 3 4 600 -2
vj -2    

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

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

 

 

ui
5 6 2 2 400
9 500 7 4 6 -5
7 100 1 600 4 5 -3
5 100 2 2 800 4 -1
6 500 4 3 4 600 -2
vj -2  

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

ui
5 6 2 2 400
9 500 7 4 6 -5
7 100 1 600 4 5 -3
5 100 2 2 800 4 -1
6 500 4 3 4 600 -2
vj -2  

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

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

Δ11 =5–(4 – 0)=1 ; Δ12 =6–(-2–0) =8; Δ13 =2 – (1 – 0) = 1; Δ22=7 –(–2+5)=4; Δ23 = 4 – (1+5) = – 2; Δ24 = 6–(2+5) = – 1; Δ33 = 4 – (1+ 3) = 0; Δ34 = 5 – (2+3)= 0; Δ42=2–( – 2+1) = 3; Δ44=4–(2+1)=1; Δ52 =4 – (–2+2) = 4; Δ53 =3–(1+2)=0.

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

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

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

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

ui
5 6 2 2 400
9 500 7 4 * 6 -5
7 100 1 600 4 5 -3
5 100 2 2 800 4 -1
6 500 4 3 4 600 -2
vj -2  

 

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

ui
5 6 2 2 400
9 500 7 4 * 6 -5
7 100 1 600 4 5 -3
5 100 2 2 800 4 -1
6 500 4 3 4 600 -2
vj -2  

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

ui
5 6 2 2 400
9 500 7 4 * 6 -5
7 100 1 600 4 5 -3
5 100 2 2 800 4 -1
6 500 4 3 4 600 -2
vj -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)

ui
5 6 2 2 400
9 500 7 4 * 6 -5
7 100 1 600 4 5 -3
5 100 2 2 800 4 -1
6 500 4 3 4 600 -2
vj -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):

ui
5 6 2 2 400
9 7 4 500 6 -3
7 100 1 600 4 5 -3
5 600 2 2 300 4 -1
6 500 4 3 4 600 -2
vj -2  

для клетки (2; 3) новый объём равен x23 = 0 + 500 = 500 т, для клетки (2; 1) новый объём равен x21 = 500 – 500 = 0 т, для клетки (4; 1) новый объём равен x41 = 100+500 = 600 т, для клетки (4; 3) новый объём равен x43 = 800 – 500 = 300 т. Объём клетки (2; 1) стал равным нулю, её переводим в ранг свободных, а клетку (2; 3) переводим в ранг заполненных. Объёмы остальных клеток таблицы, не вошедших в цикл, не меняются: x14=400, x31=100, x32 =600, x51=500, x54=600 (табл. 3). Шаг метода потенциалов закончен. Переходим к новому шагу. В качестве опорного рассматриваем план, соответствующий таблице 3.

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

Δ21 =9–(4+3) = 2; Δ22 =7–(–2+3)=6; Δ24=6–(2+3)=1; Δ33=4–(1+3)=0; Δ34=5–(2+3) =0;

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