Имеются четыре пункта поставки однородного груза – А1; A2; A3; А4 и пять пунктов потребления этого груза B1; B2; B3; B4; B5. В пунктах A1; A2; A3; А4 находится груз 18; 12; 20; 18 соответственно. Груз необходимо доставить в пункты B1; B2; B3; B4; B5 в количестве 14; 11; 17; 15; 14 соответственно. Стоимость перевозки в каждый из пунктов задана следующей матрицей
Требуется найти оптимальный план закрепления потребителей за поставщиками однородного груза при условии минимизации стоимости перевозок.
Решение
Проверим условие разрешимости задачи.
A=i=1mai=18+12+20+18=68; B=j=1nbj=14+11+17+15+14=71.
Условие баланса не соблюдается. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную базу с запасом груза, равным 3. Тарифы перевозки единицы груза из базы во все магазины полагаем равными нулю.
Занесем исходные данные в распределительную таблицу.
Bj
Ai B1 B2 B3 B4 B5 запасы
A1 9 21 22 14 10 18
A2 30 34 42 23 26 12
A3 8 17 30 27 9 20
A4 11 20 24 7 25 18
A5 0 0 0 0 0 3
потребители 14 11 17 15 14
Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Bj
Ai B1 B2 B3 B4 B5 запасы
A1 9 21
8 22
2 14 10
8 18
A2 30 34 42
12 23 26 12
A3 8
14 17 30 27 9
6 20
A4 11 20
3 24 7
15 25 18
A5 0 0 0
3 0 0 3
потребители 14 11 17 15 14
Подсчитаем число занятых клеток таблицы, их 9, а должно быть m + n - 1 =9. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
FX0=21∙8+22∙2+10∙8+42∙12+8∙14+9∙6+20∙3+7∙15+0∙3=1127
Оптимизируем план производства и организации перевозок методом потенциалов. Составим систему уравнений для определения потенциалов
α1+β2=21
α1+β3=22
α1+β5=10
α2+β3=42
α3+β1=8
α3+β5=9
α4+β2=20
α4+β4=7
α5+β3=0
Проверим оптимальность опорного плана. Найдем потенциалы αi, βj. по занятым клеткам таблицы, в которых αi+βj=cij, полагая, что α1=0.
α1=0; α2=20; α3=-1; α4=-1; α5=-22;
β1=9; β2=21; β3=22; β4=8; β5=10.
Вычислим оценки ∆st свободных переменных (свободных клеток):
∆11=9-0-9=0
∆14=14-0-8=6
∆21=30-20-9=1
∆22=34-20-21=-7
∆24=23-20-8=-5
∆25=26-20-10=-4
∆32=17+1-21=-3
∆33=30+1-22=9
∆34=27+1-8=20
∆41=11+1-9=3
∆43=24+1-22=3
∆45=25+1-10=16
∆51=0+22-9=13
∆52=0+22-21=1
∆54=0+22-8=14
∆55=0+22-10=12
Опорный план не является оптимальным, так как существует отрицательная оценка свободной клетки: ∆22=-7.
Для этого в клетку (2;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Bj
Ai B1 B2 B3 B4 B5 запасы
A1 9 - 21
86808-26890085948841008 + 22
3454400002 14 10
8 18
A2 30 + 839691586380034 - 42
12 23 26 12
A3 8
14 17 30 27 9
6 20
A4 11 20
3 24 7
15 25 18
A5 0 0 0
3 0 0 3
потребители 14 11 17 15 14
Цикл приведен в таблице 2,2→2,3→1,3→1,2.
Из грузов, стоящих в минусовых клетках, выбираем наименьшее.
Прибавляем 8 к объемам грузов, стоящих в плюсовых клетках и вычитаем из стоящих в минусовых клетках
. В результате перемещения числа k=8 по циклу получим новую распределительную таблицу, в которой клетка 2;2 стала занятой.
Bj
Ai B1 B2 B3 B4 B5 запасы
A1 9 21 22
10 14 10
8 18
A2 30 34
8 42
4 23 26 12
A3 8
14 17 30 27 9
6 20
A4 11 20
3 24 7
15 25 18
A5 0 0 0
3 0 0 3
потребители 14 11 17 15 14
Оптимизируем план производства и организации перевозок методом потенциалов. Составим систему уравнений для определения потенциалов
α1+β3=22
α1+β5=10
α2+β2=34
α2+β3=42
α3+β1=8
α3+β5=9
α4+β2=20
α4+β4=7
α5+β3=0
Проверим оптимальность опорного плана
Задать вопрос
на новый заказ в Автор24.
