Семь угольных карьеров добывают уголь и поставляют его на пять электростанций. Потребности в угле по электростанциям распределены следующим образом: для электростанции М1 требуется 200 тыс. тонн угля в месяц, для М2 – 600, М3 – 800, М4 – 900 и для М5 – 1200 тысяч тонн угля в месяц. Качество угля, оптовые цены и транспортные издержки отражены в показателях прибыли, приведенных в табл. 1.
Таблица 1
Показатели прибыли электростанций
Электростанции Распределение прибыли по карьерам, долл./т
1 2 3 4 5 6 7
М1
М2
М3
М4
М5 8
9
6
5
4 3
11
10
12
7 2
5
6
11
10 7
2
4
8
9 4
6
7
10
8 5
3
5
13
5 9
4
8
7
6
Производственные мощности карьеров представлены в табл. 2.
Таблица 2
Распределение производственных мощностей по карьерам, тыс. тонн
Карьеры
1
1 300
2 300
3 700
4 700
5 800
6 500
7 700
Решение
1. Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 300 + 300 + 700 + 700 + 800 + 500 + 700 = 4000
∑b = 200 + 600 + 800 + 900 + 1200 = 3700
Как видно, суммарные запасы угля на карьерах превышают его потребности на электростанциях. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) энергостанцию с потребностями в угле, равными 300 (3700—4000), при этом прибыль по карьерам полагаем равными нулю.
Исходные данные отразим в распределительной табл. 3:
Таблица 3
Исходные данные транспортной задачи
B1 B2 B3 B4 B5 B6 B7 Потребности
A1 8 3 2 7 4 5 9 200
A2 9 11 5 2 6 3 4 600
A3 6 10 6 4 7 5 8 800
A4 5 12 11 8 10 13 7 900
A5 4 7 10 9 8 5 6 1200
A6 0 0 0 0 0 0 0 300
Запасы 300 300 700 700 800 500 700
2. Поиск первого опорного плана.
Используя метод наибольшей стоимости, построим первый опорный план транспортной задачи. Суть метода заключается в том, что из всей таблицы стоимостей выбирают наибольшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj. Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку, и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наибольшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Таким образом получим следующий опорный план задачи (табл. 4).
Таблица 4
Опорный план транспортной задачи
B1 B2 B3 B4 B5 B6 B7 Потребности
A1 8
3 2 7 4 5 9
200 200
A2 9
300 11
5 2 6
300 3 4 600
A3 6 10 6 4 7
300 5 8
500 800
A4 5 12
300 11
100 8 10 13
500 7 900
A5 4 7 10
600 9
600 8 5 6 1200
A6 0 0 0 0
100 0
200 0 0 300
Запасы 300 300 700 700 800 500 700
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
Подсчитаем число занятых клеток таблицы, их 12, а должно быть m + n - 1 = 12. Следовательно, опорный план является невырожденным.
Значение целевой функции данного опорного плана равно: F(x) = 9*200 + 9*300 + 6*300 + 7*300 + 8*500 + 12*300 + 11*100 + 13*500 + 10*600 + 9*600 + 0*100 + 0*200 = 35000 долл.
3
. Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0 (табл. 5).
Таблица 5
Потенциалы и оценки для опорного решения задачи
№
1 2 3 4 5 6 7
-209554508500vi
ui 11 10 9 8 8 11 9
1 0 -17861236855008
-20320233680003
+7 -48260233680002
+7 -20955233680007
+1 -40005233680004
+4 -17780233680005
+6 9
200
2 -2 9
300 466178250415463928250415-2032024638000+ 11
-3 -48260246380005
+2 -20955246380002
+4 526158250415- 6
300 -17780246380003
+5 -36195248832004
+3
3 -1 -46684252730006
+4 -203202489200010
-1 -46355252730006
+2 -2095525273000 4
+3 7
300 -17780252730005
+5 8
500
4 2 -33085243205005
+4 - 12
46392846009300 353518239451+ 11
100 -20955243205008
+2 -400052432050010
0 13
500 -40906238189007
+4
5 1 -53340237490004
+8 -20320237490007
+4 291304242007- 10
600 407405239757+ 9
600 -39040237289008
+1 -17780237490005
+7 -47167238495006
+4
6ф -8 -3635625508500 0
+3 -17780252730000
+2 -47907252079000
+1 405154251050- 0
100 + 0
200 -17780252730000
+3 -47167248108000
+1
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(2;2): -2 + 10 < 11; ∆22 = -2 + 10 - 11 = -3 > 0
(3;2): -1 + 10 < 10; ∆32 = -1 + 10 - 10 = -1 > 0
Выбираем максимальную оценку свободной клетки (2;2): 11. Для этого в перспективную клетку (2;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (6, 4) = 100. Прибавляем 100 к объемам грузов, стоящих в плюсовых клетках, и вычитаем 100 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план, который также проверим на оптимальность (табл. 6)
Таблица 6
Потенциалы и оценки для улучшенного плана задачи
№
1 2 3 4 5 6 7
-209554508500vi
ui 11 13 12 11 8 14 9
1 0 -17861236855008
+3 -20320233680003
+10 -48260233680002
+11 -20955233680007
+4 -40005233680004
+4 -17780233680005
+9 9
200
2 -2 9
300 504253251484498628249233+ 11
100 -48260246380005
+5 -20955246380002
+7 579908249232- 6
200 -17780246380003
+9 -36195248832004
+3
3 -1 -46684252730006
+4 -203202489200010
+2 -46355252730006
+5 -2095525273000 4
+6 7
300 -17780252730005
+8 8
500
4 -1 -33085243205005
+5 429180238270- 12
200 11
200 -20955243205008
+2 -4000524320500+ 10
-3 13
500 -40906238189007
+1
5 -2 -53340237490004
+5 -20320237490007
+4 10
500 9
700 -39040237289008
-2 -17780237490005
+7 -47167238495006
+2
6ф -8 -3635625508500 0
+3 -17780252730000
+5 -47907252079000
+4 -25561247481000
+3 0
300 -17780252730000
+6 -47167248108000
+1
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(4;5): -1 + 8 < 10; ∆45 = -1 + 8 - 10 = -3 > 0
(5;5): -2 + 8 < 8; ∆55 = -2 + 8 - 8 = -2 > 0
Выбираем максимальную оценку свободной клетки (4;5): 10 Для этого в перспективную клетку (4;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е
Задать вопрос
на новый заказ в Автор24.
