Рассчитайте значение неизвестного объема продукции для потребителя так, чтобы задача была сбалансированной.
2. Решите задачу методом потенциалов, используя оценки свободных клеток.
3. Выполните первоначальное распределение поставок методом наименьших затрат.
4. Сформулируйте понятие цикла пересчета и оценки свободной клетки.
b
a 6 12 13 20 ?
16 30 2 5 6 15
15 5 29 9 5 7
14 16 24 14 6 26
15 13 28 4 25 8
Решение
1. Рассчитываем значение неизвестного объема продукции для потребителя так, чтобы задача была сбалансированной.
В общем случае условие разрешимости транспортной задачи состоит в том, что сумма запасов поставщиков в пунктах отправления (ПО) должна быть равна суммарной потребности потребителей в пунктах назначения (ПН) , то есть транспортная задача должна быть закрытой.
Согласно условию нашей задачи имеем:
m = 4; n = 5;
= a1 + a2 + a3 + a4 = 16 + 15 + 14 + 15 = 60.
Выражение для определения неизвестного значения b5 имеет вид:
b5 = – b1 – b2 – b3 – b4 = 60 – 6 – 12 – 13 – 20 = 9.
Таким образом, условие разрешимости транспортной задачи выполнено.
Вводим обозначения: xij – объемы перевозок грузов между ПО Ai и ПН Bj; cij – заданные стоимости перевозки единицы продукции между ПО Ai и ПН Bj.
Математическая модель нашей транспортной задачи в виде задачи линейного программирования формулируется так: найти совокупность значений переменных xij ≥ 0, минимизирующих целевую функцию (суммарные затраты на перевозки) при ограничениях по m = 4 поставщикам , и n = 5 потребителям , .
2. Выполняем первоначальное распределение поставок методом наименьших затрат.
Составляем рабочую таблицу представления числовых данных задачи:
ПН B1 B2 B3 B4 B5 ui
ПО
b1=6 b2=12 b3=13 b4=20 b5=9
A1 a1=16
30
2
5
6
15
A2 a2=15
5
29
9
5
7
A3 a3=14
16
24
14
6
26
A4 a3=15
13
28
4
25
8
vj
Выполняем первоначальное распределение поставок X(0) методом наименьших затрат.
В соответствии с этим методом перевозки распределяются в первую очередь в те ячейки распределительной таблицы, которые имеют наименьшую стоимость. Если же наименьшие стоимости совпадают, то ячейку можно выбрать произвольно. Объем перевозки, вносимый в ячейку, определяется как минимальное значение среди значений запаса и потребности xij = min(ai, bj). При этом исключается или только строка, или только столбец. Соответственно, или в столбце, или в строке образуется остаток (возможно, даже нулевой), который распределяется на последующих шагах процесса распределения на общих основаниях
.
а). Наименьшая стоимость 2 в ячейке (1, 2). Назначаем x12 = 12. Столбец B2 исключаем. Остаток a1 = 4.
б). Наименьшая стоимость 4 в ячейке (4, 3). Назначаем x43 = 13. Столбец B3 исключаем. Остаток b4 = 2.
в). Наименьшая стоимость 5 в ячейках (2, 1) и (2, 4). Выбираем и назначаем x21 = 6. Столбец B1 исключаем. Остаток a2 = 9.
г). Наименьшая стоимость 5 в ячейке (2, 4). Назначаем остаток x24 = 9. Строку A2 исключаем. Остаток b4 = 11.
д). Наименьшая стоимость 6 в ячейках (1, 4) и (3, 4). Выбираем и назначаем остаток x14 = 4. Строку A1 исключаем. Остаток b4 = 7.
е). Наименьшая стоимость 6 в ячейке (3, 4). Назначаем остаток x34 = 7. Столбец B4 исключаем. Остаток a3 = 7.
ж). Заполняем остатками x35 = 7 и x45 = 2 незаполненные ячейки (3, 5) и (4, 5).
Все перевозки распределены.
Первоначальное распределение поставок X(0) транспортной задачи, составленное по методу наименьших затрат, имеет вид:
X(0) ПН B1 B2 B3 B4 B5 ui
ПО
b1=6 b2=12 b3=13 b4=20 b5=9
A1 a1=16
30
2
5
6
15
12
4
A2 a2=15
5
29
9
5
7
6
9
A3 a3=14
16
24
14
6
26
7
7
A4 a3=15
13
28
4
25
8
13
2
vj
Первоначальное распределение поставок содержит m + n – 1 = 4 + 5 – 1 = 8 занятых клеток, следовательно, опорное решение – невырожденное.
Значение целевой функции:
Z(X(0)) = 2·12+6·4+5·6+5·9+6·7+26·7+4·13+8·2 = 415.
3. Полученное распределение поставок оптимизируем методом потенциалов, используя оценки свободных клеток.
Для проверки, является ли распределение поставок оптимальным, строится система потенциалов поставщиков ui и потребителей vj.
Чтобы распределение поставок было оптимальным, необходимо выполнение следующих условий:
1) для каждой занятой ячейки должно выполняться ui + vj + cij = 0;
2) для каждой свободной ячейки должно выполняться ui + vj + cij ≥ 0.
Проверяем, является ли найденное распределение поставок X(0) оптимальным. Для этого строим систему потенциалов ui и vj из условия выполнения равенства ui + vj + cij = 0 для каждой из занятых ячеек.
1). Полагаем u1 = 0 (1).
2). Для занятой ячейки (1, 2); v2 = –2 (2); u1 + v2 + c12 = 0 – 2 + 2 = 0.
3). Для занятой ячейки (1, 4); v4 = –6 (3); u1 + v4 + c14 = 0 – 6 + 6 = 0.
4). Для занятой ячейки (2, 4); u2 = 1 (4); u2 + v4 + c24 = 1 – 6 + 5 = 0.
5). Для занятой ячейки (2, 1); v1 = –6 (5); u2 + v1 + c21 = 1 – 6 + 5 = 0.
6). Для занятой ячейки (3, 4); u3 = 0 (6); u3 + v4 + c34 = 0 – 6 + 6 = 0.
7). Для занятой ячейки (3, 5); v5 = –26 (7); u3 + v5 + c35 = 0 – 26 + 26 = 0.
8). Для занятой ячейки (4, 5); u4 = 18 (8); u4 + v5 + c45 = 18 – 26 + 8 = 0.
9). Для занятой ячейки (4, 3); v3 = –22 (9); u4 + v3 + c43 = 18 – 22 + 4 = 0.
Найденные значения потенциалов заносим в рабочую таблицу (в скобках указан номер шага их вычисления)
Задать вопрос
на новый заказ в Автор24.
