Поля | Силосные траншеи | |||
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а.
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-ое поле из дальнейшего рассмотрения.
1б | Остатки | ||||
5 – | 6 – | 2 – | 2 400 | 0× | |
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–ютраншею вычёркиваем из дальнейшего рассмотрения.
1в | Остатки | ||||
5 – | 6 – | 2 – | 2 400 | 0× | |
9 | 7 – | 4 – | 6 | ||
7 | 1 600 | 4 – | 5 | ||
5 | 2 – | 2 800 | 4 | ||
6 | 4 – | 3 – | 4 | ||
Остатки | 0 × | 0× |
Переходим к четвёртому шагу. Наименьшие оплаты перевозки с44=4, с54=4. Выбираем клетку (5;4).Остатки равны: для поля 1100 т, для траншеи 600 т. Остаток 600 т будет минимальным. Пересчитываем остатки (табл. 1г): для поля 1100 – 600 = 500 т, для траншеи 600 – 600 = 0 т.Вычёркиваем 4-уютраншею.
1г | Остатки | ||||
5 – | 6 – | 2 – | 2 400 | 0× | |
9 | 7 – | 4 – | 6 – | ||
7 | 1 600 | 4 – | 5 – | ||
5 | 2 – | 2 800 | 4 – | ||
6 | 4 – | 3 – | 4 600 | ||
Остатки | 0 × | 0× | 600, 0× |
Переходим к пятому шагу. Минимальнаяоплата перевозки с41=5. Выбираем клетку (4;1). Остатки равны: для поля–100 т, для траншеи – 1200 т. Минимальным будет остаток 100 т. Делаем поставку в клетку (4;1) в объёме100 т. Опять пересчитываем остатки: для поля 100– 100 = 0 т, для траншеи 1200 – 100 =1100 т (табл. 1д).
1д | Остатки | ||||
5 – | 6 – | 2 – | 2 400 | 0× | |
9 | 7 – | 4 – | 6 – | ||
7 | 1 600 | 4 – | 5 – | ||
5 100 | 2 – | 2 800 | 4 – | 100, 0× | |
6 | 4 – | 3 – | 4 600 | ||
Остатки | 0 × | 0× | 600, 0× |
Переходим к шестому шагу. Оплата перевозки с51=6. Выбираем клетку (5;1). Остатки равны: поле 500 т, траншея – 1100 т. Минимальным будет остаток 500 т. Объём поставки 500 т. Остатки: 500 – 500 = 0 т для поля, 1100–500=600 т для траншеи (табл. 1е). 5-ое поле вычёркиваем. Оплата перевозки с31=7. Выбираем клетку (3;1).
1е | Остатки | ||||
5 – | 6 – | 2 – | 2 400 | 0× | |
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 × | 0× | 600, 0× |
Переходим к седьмому шагу. Минимальной будет оплата перевозки с31=7. Выбираем клетку (3;1).Остатки: поле – 100, траншея – 600 т. Минимальный остаток 100 т. Поставка в клетку (3;1) в объёме 100 т. Пересчитываем остатки:100 т для поля, для траншеи 100–100 =500 т (табл. 1ж). Вычёркиваем 3-е поле.
1ж | Остатки | ||||
5 – | 6 – | 2 – | 2 400 | 0× | |
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 × | 0× | 600, 0× |
Осталась последняя клетка,которая незаполнялась, это клетка (2;1). Проверяем баланс остатков:для поля остаток 500, для траншеи 500 т. Баланс есть. Поставляем в клетку остатки зелёной массы и поля, и траншеи в размере 500 т и вычёркиваем из рассмотрения и поле, и траншею (табл. 1з).
1з | Остатки | ||||
5 – | 6 – | 2 – | 2 400 | 0× | |
9 500 | 7 – | 4 – | 6 – | 0× | |
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 × | 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а).
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б).
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в).
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г).
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д).
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е).
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ж).
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з).
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и).
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) |
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; 3). Это клетка (4; 3). Автоматически её включаем в цикл, и цикл замыкаем (рис. 3е).
Построенный цикл для свободной клетки (2; 3) изображён на рисунке 3ж.
(2;1) |
(2;3) |
(4;1) |
Рис. 5 |
(4;3) |
– |
– |
+ |
+ |
(2;1) |
(2;3) |
(4;1) |
Рис. 4 |
(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.