Транспортная задача по критерию времени

Пункт отправления Пункт назначения Наличие груза, т
Б1 Б2 Б3 Б4
Время доставки
А1
20
х11 15
х12
17
х13
22
х14 60
А2
14
х21
11
х22
12
х23
18
х24 110
А3
16
х31
12
х32
13
х33
20
х34 70
А4
20
х41
19
х42
18
х43
25
х44 50
Потребность в грузе, т 90 70 100 30 290
Запасы продукта в пунктах отправления и потребность в нем в пунктах назначения равны между собой и составляют соответственно а1, а2,…, аi,..., аm и b1,b2, ... , bj, . .., bn единиц. Время доставки груза из каждого пункта Ai в каждый пункт Бj, известно и составляет tij часов
Сумма запаса груза у поставщиков:
.
Сумма потребностей в грузе у потребителей
.
Поскольку аi = bj, транспортная задача является закрытой.
Математическая модель транспортной задачи:F = ∑∑tijxij, (1)при условиях:∑xij = ai, i = 1,2,…, m, (2)∑xij = bj, j = 1,2,…, n, (3)xij ≥ 0Запишем экономико-математическую модель для нашей задачи.Переменные:x11 – количество груза из 1-го склада к 1-у потребителю.x12 – количество груза из 1-го склада к 2-у потребителю.x13 – количество груза из 1-го склада к 3-у потребителю.x14 – количество груза из 1-го склада к 4-у потребителю.x21 – количество груза из 2-го склада к 1-у потребителю.x22 – количество груза из 2-го склада к 2-у потребителю.x23 – количество груза из 2-го склада к 3-у потребителю.x24 – количество груза из 2-го склада к 4-у потребителю.x31 – количество груза из 3-го склада к 1-у потребителю.x32 – количество груза из 3-го склада к 2-у потребителю.x33 – количество груза из 3-го склада к 3-у потребителю.x34 – количество груза из 3-го склада к 4-у потребителю.x41 – количество груза из 4-го склада к 1-у потребителю.x42 – количество груза из 4-го склада к 2-у потребителю.x43 – количество груза из 4-го склада к 3-у потребителю.x44 – количество груза из 4-го склада к 4-у потребителю.Ограничения по запасам:x11 + x12 + x13 + x14 ≤ 60 (для 1 базы)x21 + x22 + x23 + x24 ≤ 110 (для 2 базы)x31 + x32 + x33 + x34 ≤ 70 (для 3 базы)x41 + x42 + x43 + x44 ≤ 50 (для 4 базы)Ограничения по потребностям:x11 + x21 + x31 + x41 = 90 (для 1-го потребителя.)x12 + x22 + x32 + x42 = 70 (для 2-го потребителя.)x13 + x23 + x33 + x43 = 100 (для 3-го потребителя.)x14 + x24 + x34 + x44 = 30 (для 4-го потребителя.)Целевая функция:20x11 + 15x12 + 17x13 + 22x14 + 14x21 + 11x22 + 12x23 + 18x24 + 16x31 + 12x32 + 13x33 + 20x34 + 20x41 + 19x42 + 18x43 + 25x44 → minС целью составления задачи переменные xij в условии (2) заменим на u1, u2, ui,.., um, а переменные xij в условия (3) на v1, v2, vj,.., vn.Поскольку каждая переменная xij входит в условия (2,3) и целевую функцию (1) по одному разу, то двойственную задачу по отношению к прямой транспортной задаче можно сформулировать следующим образом.Требуется найти не отрицательные числа ui (при i = 1,2,…,m) и vj (при j = 1,2,..,n), обращающие в максимум целевую функцию:G = ∑aiui + ∑bjvjпри условии:ui + vj ≤ cij, i = 1,2,..,m; j = 1,2,..,n (4)В систему условий (4) будет mxn неравенств. По теории двойственности для оптимальных планов прямой и двойственной задачи для всех i,j должно быть:ui + vj ≤ cij, если xij = 0,ui + vj = cij, если xij ≥ 0,Эти условия являются необходимыми и достаточными признаками оптимальности плана транспортной задачи.Числа ui , vj называются потенциалами. Причем число ui называется потенциалом поставщика, а число vj – потенциалом потребителя.По первой теореме двойственности в оптимальном решении значения целевых функций прямой и двойственных задач совпадают: F = G.Математическая модель задачи:U – переменные для складов, поставщиков;V - переменные для магазинов, потребителей.U1 + V1≤20U1 + V2≤15U1 + V3≤17U1 + V4≤22U2 + V1≤14U2 + V2≤11U2 + V3≤12U2 + V4≤18U3 + V1≤16U3 + V2≤12U3 + V3≤13U3 + V4≤20U4 + V1≤20U4 + V2≤19U4 + V3≤18U4 + V4≤25G(y)=90U1 + 70U2 + 100U3 + 30U4 + 60V1 + 110V2 + 70V3 + 50V4 → maxВремя доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
B1 B2 B3 B4 Запасы
A1 20 15 17 22 60
A2 14 11 12 18 110
A3 16 12 13 20 70
A4 20 19 18 25 50
Потребности 90 70 100 30
Проверим необходимое и достаточное условие разрешимости задачи.∑a = 60 + 110 + 70 + 50 = 290∑b = 90 + 70 + 100 + 30 = 290Условие баланса соблюдается . Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.Занесем исходные данные в распределительную таблицу.
B1 B2 B3 B4 Запасы
A1 20 15 17 22 60
A2 14 11 12 18 110
A3 16 12 13 20 70
A4 20 19 18 25 50
Потребности 90 70 100 30
Этап I. Поиск первого опорного плана.1. Построим первый опорный план транспортной задачи.Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.Из оставшейся части таблицы стоимостей снова выбирают наименьшее время, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.Искомый элемент равен c22=11. Для этого элемента запасы равны 110, потребности 70. Поскольку минимальным является 70, то вычитаем его.x22 = min(110,70) = 70.
20 x 17 22 60
14 11 12 18 110 - 70 = 40
16 x 13 20 70
20 x 18 25 50
90 70 - 70 = 0 100 30
Искомый элемент равен t23=12. Для этого элемента запасы равны 40, потребности 100. Поскольку минимальным является 40, то вычитаем его.x23 = min(40,100) = 40.
20 x 17 22 60
x 11 12 x 40 - 40 = 0
16 x 13 20 70
20 x 18 25 50
90 0 100 - 40 = 60 30
Искомый элемент равен t33=13. Для этого элемента запасы равны 70, потребности 60. Поскольку минимальным является 60, то вычитаем его.x33 = min(70,60) = 60.
20 x x 22 60
x 11 12 x 0
16 x 13 20 70 - 60 = 10
20 x x 25 50
90 0 60 - 60 = 0 30
Искомый элемент равен t31=16. Для этого элемента запасы равны 10, потребности 90. Поскольку минимальным является 10, то вычитаем его.x31 = min(10,90) = 10.
20 x x 22 60
x 11 12 x 0
16 x 13 x 10 - 10 = 0
20 x x 25 50
90 - 10 = 80 0 0 30
Искомый элемент равен t11=20. Для этого элемента запасы равны 60, потребности 80. Поскольку минимальным является 60, то вычитаем его.x11 = min(60,80) = 60.
20 x x x 60 - 60 = 0
x 11 12 x 0
16 x 13 x 0
20 x x 25 50
80 - 60 = 20 0 0 30
Искомый элемент равен tc41=20. Для этого элемента запасы равны 50, потребности 20. Поскольку минимальным является 20, то вычитаем его.x41 = min(50,20) = 20.
20 x x x 0
x 11 12 x 0
16 x 13 x 0
20 x x 25 50 - 20 = 30
20 - 20 = 0 0 0 30
Искомый элемент равен t44=25. Для этого элемента запасы равны 30, потребности 30. Поскольку минимальным является 30, то вычитаем его.x44 = min(30,30) = 30.
20 x x x 0
x 11 12 x 0
16 x 13 x 0
20 x x 25 30 - 30 = 0
0 0 0 30 - 30 = 0
B1 B2 B3 B4 Запасы
A1 20[60] 15 17 22 60
A2 14 11[70] 12[40] 18 110
A3 16[10] 12 13[60] 20 70
A4 20[20] 19 18 25[30] 50
Потребности 90 70 100 30
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.2