Три электрогенерирующие станции мощностью 25, 40 и 30 миллионов кВтч поставляют электроэнергию в три города. Максимальная потребность в электроэнергии этих городов оценивается в 30, 35 и 24 миллионов кВтч. Цены за миллион кВтч в данных городах приведены в табл.2.
Стоимость за электроэнергию, руб./млн.кВтч
Города
1 2 3
Станция 1 600 700 400
2 320 300 350
3 500 480 450
В августе на 20% возрастает потребность в электроэнергии в каждом из трех городов. Недостаток электроэнергии могут восполнить из другой электросети по цене 1000 за 1 миллион кВтч. Но третий город не может подключиться к альтернативной электросети. Электрогенерирующие станции планируют разработать наиболее экономичный план распределения электроэнергии и восполнения ее недостатка в августе. Сформулируйте эту задачу в виде транспортной модели и постройте опорный план, используя метод северо-западного угла.
Решение
Целевая функция:
600x11 + 700x12 + 400x13 + 320x21 + 300x22 + 350x23 + 500x31 + 480x32 + 450x33 → min
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
B1 B2 B3 Запасы
A1 600 700 400 25
A2 320 300 350 40
A3 500 480 450 30
Потребности 36 42 30
Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 25 + 40 + 30 = 95
∑b = 36 + 42 + 30 = 108
Как видно, суммарная потребность энергии в пунктах назначения превышает запасы энергии на станциях. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) станции с запасом энергии, равным 13 (95—108).
Занесем исходные данные в распределительную таблицу.
B1 B2 B3 Запасы
A1 600 700 400 25
A2 320 300 350 40
A3 500 480 450 30
A4 0 0 0 13
Потребности 36 42 30
Используя метод северо-западного угла, построим первый опорный план транспортной задачи.
План начинается заполняться с верхнего левого угла.
Искомый элемент равен c11=600. Для этого элемента запасы равны 25, потребности 36.
Поскольку минимальным является 25, то вычитаем его.
x11 = min(25,36) = 25.
600 x x 25 - 25 = 0
320 300 350 40
500 480 450 30
0 0 0 13
36 - 25 = 11 42 30
Искомый элемент равен c21=320. Для этого элемента запасы равны 40, потребности 11. Поскольку минимальным является 11, то вычитаем его.
x21 = min(40,11) = 11.
600 x x 0
320 300 350 40 - 11 = 29
x 480 450 30
x 0 0 13
11 - 11 = 0 42 30
Искомый элемент равен c22=300. Для этого элемента запасы равны 29, потребности 42. Поскольку минимальным является 29, то вычитаем его.
x22 = min(29,42) = 29.
600 x x 0
320 300 x 29 - 29 = 0
x 480 450 30
x 0 0 13
0 42 - 29 = 13 30
Искомый элемент равен c32=480. Для этого элемента запасы равны 30, потребности 13. Поскольку минимальным является 13, то вычитаем его.x32 = min(30,13) = 13.
600 x x 0
320 300 x 0
x 480 450 30 - 13 = 17
x x 0 13
0 13 - 13 = 0 30
Искомый элемент равен c33=450. Для этого элемента запасы равны 17, потребности 30. Поскольку минимальным является 17, то вычитаем его.
x33 = min(17,30) = 17.
600 x x 0
320 300 x 0
x 480 450 17 - 17 = 0
x x 0 13
0 0 30 - 17 = 13
Искомый элемент равен c43=0
. Для этого элемента запасы равны 13, потребности 13. Поскольку минимальным является 13, то вычитаем его.x43 = min(13,13) = 13.
600 x x 0
320 300 x 0
x 480 450 0
x x 0 13 - 13 = 0
0 0 13 - 13 = 0
B1 B2 B3 Запасы
A1 600[25] 700 400 25
A2 320[11] 300[29] 350 40
A3 500 480[13] 450[17] 30
A4 0 0 0[13] 13
Потребности 36 42 30
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6.
Следовательно, опорный план является невырожденным.Значение целевой функции для этого опорного плана равно:F(x) = 600*25 + 320*11 + 300*29 + 480*13 + 450*17 + 0*13 = 41110
Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 600; 0 + v1 = 600; v1 = 600
u2 + v1 = 320; 600 + u2 = 320; u2 = -280
u2 + v2 = 300; -280 + v2 = 300; v2 = 580
u3 + v2 = 480; 580 + u3 = 480; u3 = -100
u3 + v3 = 450; -100 + v3 = 450; v3 = 550
u4 + v3 = 0; 550 + u4 = 0; u4 = -550
v1=600 v2=580 v3=550
u1=0 600[25] 700 400
u2=-280 320[11] 300[29] 350
u3=-100 500 480[13] 450[17]
u4=-550 0 0 0[13]
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij(1;3): 0 + 550 > 400; ∆13 = 0 + 550 - 400 = 150 > 0(4;1): -550 + 600 > 0; ∆41 = -550 + 600 - 0 = 50 > 0(4;2): -550 + 580 > 0; ∆42 = -550 + 580 - 0 = 30 > 0max(150,50,30) = 150
Выбираем максимальную оценку свободной клетки (1;3): 400
Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 2 3 Запасы
1 600[25][-] 700 400[+] 25
2 320[11][+] 300[29][-] 350 40
3 500 480[13][+] 450[17][-] 30
4 0 0 0[13] 13
Потребности 36 42 30
Цикл приведен в таблице (1,3 → 1,1 → 2,1 → 2,2 → 3,2 → 3,3).Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е
Задать вопрос
на новый заказ в Автор24.
