(2) заменим на u₁, u₂, u_i,.., u_m, а переменные x_ij в условия (3) на v₁, v₂, v_j,.., v_n.

Поскольку каждая переменная x_ij входит в условия (2,3) и целевую функцию (1) по одному разу, то двойственную задачу по отношению к прямой транспортной задаче можно сформулировать следующим образом.

Требуется найти не отрицательные числа u_i (при i = 1,2,…,m) и v_j (при j = 1,2,..,n), обращающие в максимум целевую функцию:

G = ∑a_iu_i + ∑b_jv_j

при условии:

u_i + v_j ≤ c_ij, i = 1,2,..,m; j = 1,2,..,n (4)

В систему условий (4) будет mxn неравенств. По теории двойственности для оптимальных планов прямой и двойственной задачи для всех i,j должно быть:

u_i + v_j ≤ c_ij, если x_ij = 0,

u_i + v_j = c_ij, если x_ij ≥ 0,

Эти условия являются необходимыми и достаточными признаками оптимальности плана транспортной задачи.

Числа u_i , v_j называются потенциалами. Причем число u_i называется потенциалом поставщика, а число v_j – потенциалом потребителя.

По первой теореме двойственности в оптимальном решении значения целевых функций прямой и двойственных задач совпадают: F = G.

Математическая модель двойственной задачи:

U – переменные для поставщиков, поставщиков;

V - переменные для магазинов, потребителей.

U₁ + V₁≤7

U₁ + V₂≤4

U₁ + V₃≤9

U₁ + V₄≤3

U₂ + V₁≤2

U₂ + V₂≤11

U₂ + V₃≤8

U₂ + V₄≤4

U₃ + V₁≤3

U₃ + V₂≤8

U₃ + V₃≤6

U₃ + V₄≤5

G(y)=450U₁ + 250U₂ + 200U₃ + 350U₄ + 400V₁ + 550V₂ + 300V₃ → max

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

	B1	B2	B3	B4	Запасы
A1	7	4	9	3	400
A2	2	11	8	4	550
A3	3	8	6	5	300
Потребности	450	250	200	350

---

Проверим необходимое и достаточное условие разрешимости задачи.

∑a = 400 + 550 + 300 = 1250

∑b = 450 + 250 + 200 + 350 = 1250

Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

Занесем исходные данные в распределительную таблицу.

	B1	B2	B3	B4	Запасы
A1	7	4	9	3	400
A2	2	11	8	4	550
A3	3	8	6	5	300
Потребности	450	250	200	350

Этап I. Поиск первого опорного плана.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел a_i, или b_j.

Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.

Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают

---

, пока все запасы не будут распределены, а потребности удовлетворены.

Искомый элемент равен c₂₁=2. Для этого элемента запасы равны 550, потребности 450. Поскольку минимальным является 450, то вычитаем его.

x₂₁ = min(550,450) = 450.

x	4	9	3	400
2	11	8	4	550 - 450 = 100
x	8	6	5	300
450 - 450 = 0	250	200	350

Искомый элемент равен c₁₄=3. Для этого элемента запасы равны 400, потребности 350. Поскольку минимальным является 350, то вычитаем его.

x₁₄ = min(400,350) = 350.

x	4	9	3	400 - 350 = 50
2	11	8	x	100
x	8	6	x	300
0	250	200	350 - 350 = 0

Искомый элемент равен c₁₂=4. Для этого элемента запасы равны 50, потребности 250. Поскольку минимальным является 50, то вычитаем его.

x₁₂ = min(50,250) = 50.

x	4	x	3	50 - 50 = 0
2	11	8	x	100
x	8	6	x	300
0	250 - 50 = 200	200	0

---

Искомый элемент равен c₃₃=6. Для этого элемента запасы равны 300, потребности 200. Поскольку минимальным является 200, то вычитаем его.

x₃₃ = min(300,200) = 200.

x	4	x	3	0
2	11	x	x	100
x	8	6	x	300 - 200 = 100
0	200	200 - 200 = 0	0

Искомый элемент равен c₃₂=8. Для этого элемента запасы равны 100, потребности 200. Поскольку минимальным является 100, то вычитаем его.

x₃₂ = min(100,200) = 100.

x	4	x	3	0
2	11	x	x	100
x	8	6	x	100 - 100 = 0
0	200 - 100 = 100	0	0

Искомый элемент равен c₂₂=11. Для этого элемента запасы равны 100, потребности 100. Поскольку минимальным является 100, то вычитаем его.

x₂₂ = min(100,100) = 100.

x	4	x	3	0
2	11	x	x	100 - 100 = 0
x	8	6	x	0
0	100 - 100 = 0	0	0

---

	B1	B2	B3	B4	Запасы
A1	7	4[50]	9	3[350]	400
A2	2[450]	11[100]	8	4	550
A3	3	8[100]	6[200]	5	300
Потребности	450	250	200	350

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является

---

Смотрите также файлы

• История развития сестринского дела.docx

• Содружество Независимых Государств Презентацию.pptx

• Трансплантология.docx

• Одаай толы маынасы болмайтын, адамны трлі кіл кйін білдіретін жне жанжануарлара.docx

• Лабораторная работа 2 Решение задач на газовые смеси.docx