В пунктах А имеется груз, который надо доставить в пункты В. Груз от поставщиков к потребителям доставляется в два этапа (через склады Д и К). Другими словами, груз не может поступить непосредственно от поставщика к потребителю. Данные о мощностях поставщиков, емкости складов и спросе потребителей для всех вариантов одинаковы.
Дополнительно к обычным условиям заданы ограничения по пропускной способности (ОПС) от поставщиков до потребителей.
Требуется найти оптимальный план перевозок, т.е. такой план, в котором общее значение функционала по задаче в целом было бы минимальным. Т.е. в качестве критерия оптимальности принимается общая сумма затрат (объем грузооборота) на доставку груза от поставщиков на склады и со складов потребителям.
Наличие груза у поставщиков:
А1=125
А2=180
А3=100
Спрос потребителей:
В1=115
В2=150
В3=140
Емкость промежуточных складов
Дi=250 Кi=250
Расстояния между пунктами и ограничения по пропускной способности:
Д1 Д2 Д3
А1 1 2 4
А2 2/100 4 2
А3 2 1/80 5
К1 К2 К3
Д1 5 2 1/160
Д2 2 3 4
Д3 3 1/150 2
В1 В2 В3
К1 2/90 4 3
К2 1 2 1/100
К3 4 6 4
Решение
Для ограничения x21 ≤ 100 добавляем 4-ый столбец со значениями столбца №1, но с запретом в (2,4). Потребности разделяются на 100 и 15.
Для ограничения x32 ≤ 80 добавляем 5-ый столбец со значениями столбца №1, но с запретом в (3,5). Потребности разделяются на 80 и 70.
Ограничение x43 ≤ 160 не учитываем, поскольку запасы (потребности) не превышают его значения.
Ограничение x62 ≤ 150 не учитываем, поскольку запасы (потребности) не превышают его значения.
Для ограничения x71 ≤ 90 добавляем 6-ый столбец со значениями столбца №1, но с запретом в (7,6). Потребности разделяются на 90 и 10.
Для ограничения x83 ≤ 100 добавляем 7-ый столбец со значениями столбца №1, но с запретом в (8,7). Потребности разделяются на 100 и 40.
Математическая модель транспортной задачи:
F = ∑∑cijxij, (1)
при условиях:
∑xij = ai, i = 1,2,…, m, (2)
∑xij = bj, j = 1,2,…, n, (3)
ij ≥ 0
Запишем экономико-математическую модель для нашей задачи.
Ограничения по запасам:
x11 + x12 + x13 + x14 + x15 + x16 + x17 ≤ 125 (для 1 базы)
x21 + x22 + x23 + x24 + x25 + x26 + x27 ≤ 180 (для 2 базы)
x31 + x32 + x33 + x34 + x35 + x36 + x37 ≤ 100 (для 3 базы)
x41 + x42 + x43 + x44 + x45 + x46 + x47 ≤ 250 (для 4 базы)
x51 + x52 + x53 + x54 + x55 + x56 + x57 ≤ 250 (для 5 базы)
x61 + x62 + x63 + x64 + x65 + x66 + x67 ≤ 250 (для 6 базы)
x71 + x72 + x73 + x74 + x75 + x76 + x77 ≤ 250 (для 7 базы)
x81 + x82 + x83 + x84 + x85 + x86 + x87 ≤ 250 (для 8 базы)
x91 + x92 + x93 + x94 + x95 + x96 + x97 ≤ 250 (для 9 базы)
Ограничения по потребностям:
x11 + x21 + x31 + x41 + x51 + x61 + x71 + x81 + x91 = 90 (для 1-го потребителя.)
x12 + x22 + x32 + x42 + x52 + x62 + x72 + x82 + x92 = 80 (для 2-го потребителя.)
x13 + x23 + x33 + x43 + x53 + x63 + x73 + x83 + x93 = 100 (для 3-го потребителя.)
x14 + x24 + x34 + x44 + x54 + x64 + x74 + x84 + x94 = 15 (для 4-го потребителя.)
x15 + x25 + x35 + x45 + x55 + x65 + x75 + x85 + x95 = 70 (для 5-го потребителя.)
x16 + x26 + x36 + x46 + x56 + x66 + x76 + x86 + x96 = 10 (для 6-го потребителя.)
x17 + x27 + x37 + x47 + x57 + x67 + x77 + x87 + x97 = 40 (для 7-го потребителя.)
Целевая функция:
1x11 + 2x12 + 4x13 + 1x14 + 2x15 + 1x16 + 4x17 + 2x21 + 4x22 + 2x23 + Mx24 + 4x25 + 2x26 + 2x27 + 2x31 + 1x32 + 5x33 + 2x34 + Mx35 + 2x36 + 5x37 + 5x41 + 2x42 + 1x43 + 5x44 + 2x45 + 5x46 + 1x47 + 2x51 + 3x52 + 4x53 + 2x54 + 3x55 + 2x56 + 4x57 + 3x61 + 1x62 + 2x63 + 3x64 + 1x65 + 3x66 + 2x67 + 2x71 + 4x72 + 3x73 + 2x74 + 4x75 + Mx76 + 3x77 + 1x81 + 2x82 + 1x83 + 1x84 + 2x85 + 1x86 + Mx87 + 4x91 + 6x92 + 4x93 + 4x94 + 6x95 + 4x96 + 4x97 → min
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
B1 B2 B3 B4 B5 B6 B7 Запасы
A1 1 2 4 1 2 1 4 125
A2 2 4 2 M 4 2 2 180
A3 2 1 5 2 M 2 5 100
A4 5 2 1 5 2 5 1 250
A5 2 3 4 2 3 2 4 250
A6 3 1 2 3 1 3 2 250
A7 2 4 3 2 4 M 3 250
A8 1 2 1 1 2 1 M 250
A9 4 6 4 4 6 4 4 250
Потребности 90 80 100 15 70 10 40
Поскольку в матрице присутствуют запрещенные к размещению клетки, то для отыскания оптимального плана достаточно заменить их на максимальные тарифы (6 умноженное на 3).
B1 B2 B3 B4 B5 B6 B7 Запасы
A1 1 2 4 1 2 1 4 125
A2 2 4 2 18 4 2 2 180
A3 2 1 5 2 18 2 5 100
A4 5 2 1 5 2 5 1 250
A5 2 3 4 2 3 2 4 250
A6 3 1 2 3 1 3 2 250
A7 2 4 3 2 4 18 3 250
A8 1 2 1 1 2 1 18 250
A9 4 6 4 4 6 4 4 250
Потребности 90 80 100 15 70 10 40
Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 125 + 180 + 100 + 250 + 250 + 250 + 250 + 250 + 250 = 1905
∑b = 90 + 80 + 100 + 15 + 70 + 10 + 40 = 405
Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах
. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равной 1500 (1905—405). Тарифы перевозки единицы груза к этому потребителю полагаем равны нулю.
Занесем исходные данные в распределительную таблицу.
B1 B2 B3 B4 B5 B6 B7 B8 Запасы
A1 1 2 4 1 2 1 4 0 125
A2 2 4 2 18 4 2 2 0 180
A3 2 1 5 2 18 2 5 0 100
A4 5 2 1 5 2 5 1 0 250
A5 2 3 4 2 3 2 4 0 250
A6 3 1 2 3 1 3 2 0 250
A7 2 4 3 2 4 18 3 0 250
A8 1 2 1 1 2 1 18 0 250
A9 4 6 4 4 6 4 4 0 250
Потребности 90 80 100 15 70 10 40 1500
Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.
B1 B2 B3 B4 B5 B6 B7 B8 Запасы
A1 1[90] 2 4 1[15] 2 1[10] 4 0[10] 125
A2 2 4 2 18 4 2 2 0[180] 180
A3 2 1[80] 5 2 18 2 5 0[20] 100
A4 5 2 1[100] 5 2 5 1[40] 0[110] 250
A5 2 3 4 2 3 2 4 0[250] 250
A6 3 1 2 3 1[70] 3 2 0[180] 250
A7 2 4 3 2 4 18 3 0[250] 250
A8 1 2 1 1 2 1 18 0[250] 250
A9 4 6 4 4 6 4 4 0[250] 250
Потребности 90 80 100 15 70 10 40 1500
Значение целевой функции для этого опорного плана равно:
F(x) = 1*90 + 1*15 + 1*10 + 0*10 + 0*180 + 1*80 + 0*20 + 1*100 + 1*40 + 0*110 + 0*250 + 1*70 + 0*180 + 0*250 + 0*250 + 0*250 = 405
2
Задать вопрос
на новый заказ в Автор24.
