На трех базах (пунктах отправления) A1, A2, A3 находится однородный груз в количествах, соответственно равных а1, а2 и а3 единицам. Этот груз требуется перевести в три пункта назначения B1, B2, B3 соответственно в количествах b1, b2 и b3. единиц. Стоимость перевозки единицы груза из i-го пункта отправления в j-й пункт назначения составляет cij денежных единиц. Определить оптимальный план перевозок, при котором общая стоимость перевозок будет минимальной. Обязательные требования к решению задачи.
1. Проверить разрешимость транспортной задачи. Если задача не разрешима, свести ее к закрытой задаче введением фиктивного пункта отправления (поставщика) или пункта назначения (потребителя).
2. Построить экономико-математическую модель прямой транспортной задачи и двойственной задачи.
3. Найти начальное решение транспортной задачи и проверить его на вырожденность.
4. Решить транспортную задачу методом потенциалов.
5. Решить транспортную задачу в среде Microsoft Exсel, приложить отчет.
Исходные данные
Исходные данные варианта 9:
Стоимость перевозки В1 В2 В3 В4 Запасы
А1 9 17 9 8 22
А2 13 22 18 19 13
А3 20 20 24 26 17
А4 11 19 30 6 18
Потребности 17 17 18 18
Разрешимость транспортной задачи
Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 22 + 13 + 17 + 18 = 70
∑b = 17 + 17 + 18 + 18 = 70
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
Экономико-математическая модель прямой транспортной задачи и двойственной задачи
Математическая модель транспортной задачи:
F = ∑∑cijxij(1)
-80010262890при условиях:
∑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-у потребителю.
-99060316230Ограничения по запасам:
x11 + x12 + x13 + x14 ≤ 22 (для 1 базы)
x21 + x22 + x23 + x24 ≤ 13 (для 2 базы)
x31 + x32 + x33 + x34 ≤ 17 (для 3 базы)
x41 + x42 + x43 + x44 ≤ 18 (для 4 базы)
-99060287655Ограничения по потребностям:
x11 + x21 + x31 + x41 = 17 (для 1-го потребителя.)
x12 + x22 + x32 + x42 = 17 (для 2-го потребителя.)
x13 + x23 + x33 + x43 = 18 (для 3-го потребителя.)
x14 + x24 + x34 + x44 = 18 (для 4-го потребителя.)
Целевая функция:
9×11 + 17×12 + 9×13 + 8×14 + 13×21 + 22×22 + 18×23 + 19×24 + 20×31 + 20×32 + 24×33 + 26×34 + 11×41 + 19×42 + 30×43 + 6×44 → 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 должно быть:
-9906031115ui + vj ≤ cij, если xij = 0,
ui + vj = cij, если xij ≥ 0,
Эти условия являются необходимыми и достаточными признаками оптимальности плана транспортной задачи.
Числа ui , vj называются потенциалами. Причем число ui называется потенциалом поставщика, а число vj – потенциалом потребителя.
По первой теореме двойственности в оптимальном решении значения целевых функций прямой и двойственных задач совпадают: F = G.
Математическая модель двойственной задачи:
U – переменные для складов, поставщиков;
-194310306705V – переменные для магазинов, потребителей.
U1 + V1≤9
U1 + V2≤17
U1 + V3≤9
U1 + V4≤8
U2 + V1≤13
U2 + V2≤22
U2 + V3≤18
U2 + V4≤19
U3 + V1≤20
U3 + V2≤20
U3 + V3≤24
U3 + V4≤26
U4 + V1≤11
U4 + V2≤19
U4 + V3≤30
U4 + V4≤6
G(y)=17U1 + 17U2 + 18U3 + 18U4 + 22V1 + 13V2 + 17V3 + 18V4 → max
