На комбинатах ЖБК имеются Хi единиц железобетонных панелей, размешенных в i-х складских помещениях. Их необходимо доставить на j-е объекты с учетом их потребностей (Уj). Стоимость перевозки единицы продукции от i-ro поставщика к j-му потребителю известна для всех возможных вариантов доставки и равна Сij руб (рис.1).
Составьте план перевозки (Аij) железобетонных изделий так, чтобы общая стоимость этих перевозок была наименьшей и потребности всех потребителей были бы удовлетворены. Задачу решите двумя способами: методом северо-западного угла и методом наименьшей стоимости.
10 19 34 21
10
1
1
6
1
А11
А12
А13
А1j
16
2
4
1
2
А21
А22
А23
А2j
42
1
8
4
2
А31
А32
А33
А3j
16
1
5
0
2
Аi1
Аi2
Аi3
Аij
Рис. 1. Графическое изображение транспортной задачи
Решение
1. Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 10 + 16 + 42 + 16 = 84
∑b = 10 + 19 + 34 + 21 = 84
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
3. Построим опорный план решения задачи с помощью метода северо-западного угла. При данном методе поставки распределяются, начиная с верхней левой клетки.
Первый искомый элемент равен c11=1, значение при x11 = min(10,10) = 10.
Второй искомый элемент равен c22=4, значение при x22 = min(16,19) = 16.
Третий искомый элемент равен c32=8, значение при x32 = min(42,3) = 3.
Четвертый искомый элемент равен c33=4, значение при x33 = min(39,34) = 34.
Пятый искомый элемент равен c34=2, значение при x34 = min(5,21) = 5.
Шестой искомый элемент равен c44=2, значение при x44 = min(16,16) = 16.
Далее, согласно алгоритму, ищем элементы среди не вычеркнутых. Последний искомый элемент равен c12=1, но т.к. ограничения выполнены, то x12=0.
10 19 34 21
10
1
1
6
1
10
0
16
2
4
1
2
16
42
1
8
4
2
3
34
5
16
1
5
0
2
16
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
Число занятых клеток таблицы при данном опорном плане – 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Стоимость доставки при таком плане равна:
F(x) = 1*10 + 1*0 + 4*16 + 8*3 + 4*34 + 2*5 + 2*16 = 276 руб.
3. Решим задачу методом наименьшей стоимости.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj. Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку, и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя
. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены. Таким образом получим следующий опорный план задачи.
Первый искомый элемент равен c43=0 значение при x43 = min(16,34) = 16.
Второй искомый элемент равен c11=1, значение при x11 = min(10,10) = 10.
Третий искомый элемент равен c23=1, значение при x23 = min(16,18) = 16.
Четвертый искомый элемент равен c34=2, значение при x34 = min(42,21) = 21.
Пятый искомый элемент равен c33=4, значение при x33 = min(21,2) = 2.
Шестой искомый элемент равен c32=8, значение при x32 = min(19,19) = 19.
Далее, согласно алгоритму, ищем элементы среди не вычеркнутых. Последний искомый элемент равен c41=1, но т.к. ограничения выполнены, то x41=0.
Таким образом, получим следующий опорный план решения данной транспортной задачи:
10 19 34 21
10
1
1
6
1
10
16
2
4
1
2
16
42
1
8
4
2
19
2
21
16
1
5
0
2
0
16
В результате получен опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
Число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Стоимость доставки при таком плане равна:
F(x) = 1*10 + 1*16 + 8*19 + 4*2 + 2*21 + 1*0 + 0*16 = 228 руб.
Проверяем план на оптимальность, с помощью потенциалов. Обнулив один любой потенциал строк или столбцов находим остальные, из условия что в базисных клетках (клетках, где запланирована поставка) сумма потенциалов строки (ui) и столбца (vj) должна быть равна стоимости доставки (cij). Потенциалы клеток (pij) находим из того же условия.
№ 1 2 3 4
1 4 0 -2
1 0 1
10 -24765233680001
+3 -48895240665006
-6 -25400232410001
-3
2 1 -13335251460002
0 -24765254635004
+1 1
16 -20955246380002
-2
3 4 3276607302532766073025-2095525273000+ 1
+4 8
19 42418073025 - 4
2 2
21
4 0 - 1
3276601035050 -35560266065005
-1 + 0
16 -22860255270002
-4
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
Задать вопрос
на новый заказ в Автор24.
