задача 4

Транспортная задача.

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

F = ∑∑c_ijx_ij, (1)

при условиях:

∑x_ij = a_i, i = 1,2,…, m, (2)

∑x_ij = b_j, j = 1,2,…, n, (3)

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

	1	2	3	4	5	Запасы
1	5	8	7	10	3	200
2	4	2	2	5	6	450
3	7	3	5	9	2	250
Потребности	100	125	325	250	100

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

∑a = 200 + 450 + 250 = 900

∑b = 100 + 125 + 325 + 250 + 100 = 900

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

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

	1	2	3	4	5	Запасы
1	5	8	7	10	3	200
2	4	2	2	5	6	450
3	7	3	5	9	2	250
Потребности	100	125	325	250	100

Этап I. Поиск первого опорного плана.

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

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

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

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

Искомый элемент равен 2

Для этого элемента запасы равны 450, потребности 125. Поскольку минимальным является 125, то вычитаем его.

x₂₂ = min(450,125) = 125.

5	x	7	10	3	200
4	2	2	5	6	450 - 125 = 325
7	x	5	9	2	250
100	125 - 125 = 0	325	250	100	0

Искомый элемент равен 2

Для этого элемента запасы равны 325, потребности 325. Поскольку минимальным является 325, то вычитаем его.

x₂₃ = min(325,325) = 325.

5	x	x	10	3	200
x	2	2	x	x	325 - 325 = 0
7	x	x	9	2	250
100	0	325 - 325 = 0	250	100	0

Искомый элемент равен 2

Для этого элемента запасы равны 250, потребности 100. Поскольку минимальным является 100, то вычитаем его.

x₃₅ = min(250,100) = 100.

5	x	x	10	x	200
x	2	2	x	x	0
7	x	x	9	2	250 - 100 = 150
100	0	0	250	100 - 100 = 0	0

Искомый элемент равен 5

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

x₁₁ = min(200,100) = 100.

5	x	x	10	x	200 - 100 = 100
x	2	2	x	x	0
x	x	x	9	2	150
100 - 100 = 0	0	0	250	0	0

Искомый элемент равен 9

Для этого элемента запасы равны 150, потребности 250. Поскольку минимальным является 150, то вычитаем его.

x₃₄ = min(150,250) = 150.

5	x	x	10	x	100
x	2	2	x	x	0
x	x	x	9	2	150 - 150 = 0
0	0	0	250 - 150 = 100	0	0

Искомый элемент равен 10

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

x₁₄ = min(100,100) = 100.

5	x	x	10	x	100 - 100 = 0
x	2	2	x	x	0
x	x	x	9	2	0
0	0	0	100 - 100 = 0	0	0

	1	2	3	4	5	Запасы
1	5[100]	8	7	10[100]	3	200
2	4	2[125]	2[325]	5	6	450
3	7	3	5	9[150]	2[100]	250
Потребности	100	125	325	250	100

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

Строим новый план.

Значение целевой функции для этого опорного плана равно:

F(x) = 5*100 + 10*100 + 2*125 + 2*325 + 9*150 + 2*100 = 3950

Искомый элемент равен 2

Для этого элемента запасы равны 450, потребности 325. Поскольку минимальным является 325, то вычитаем его.

x₂₃ = min(450,325) = 325.

5	8	x	10	3	200
4	2	2	5	6	450 - 325 = 125
7	3	x	9	2	250
100	125	325 - 325 = 0	250	100	0

Искомый элемент равен 2

Для этого элемента запасы равны 125, потребности 125. Поскольку минимальным является 125, то вычитаем его.

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

5	x	x	10	3	200
x	2	2	x	x	125 - 125 = 0
7	x	x	9	2	250
100	125 - 125 = 0	0	250	100	0

Искомый элемент равен 2

Для этого элемента запасы равны 250, потребности 100. Поскольку минимальным является 100, то вычитаем его.

x₃₅ = min(250,100) = 100.

5	x	x	10	x	200
x	2	2	x	x	0
7	x	x	9	2	250 - 100 = 150
100	0	0	250	100 - 100 = 0	0

Искомый элемент равен 5

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

x₁₁ = min(200,100) = 100.

5	x	x	10	x	200 - 100 = 100
x	2	2	x	x	0
x	x	x	9	2	150
100 - 100 = 0	0	0	250	0	0

Искомый элемент равен 9

Для этого элемента запасы равны 150, потребности 250. Поскольку минимальным является 150, то вычитаем его.

x₃₄ = min(150,250) = 150.

5	x	x	10	x	100
x	2	2	x	x	0
x	x	x	9	2	150 - 150 = 0
0	0	0	250 - 150 = 100	0	0

Искомый элемент равен 10

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

x₁₄ = min(100,100) = 100.

5	x	x	10	x	100 - 100 = 0
x	2	2	x	x	0
x	x	x	9	2	0
0	0	0	100 - 100 = 0	0	0

	1	2	3	4	5	Запасы
1	5[100]	8	7	10[100]	3	200
2	4	2[125]	2[325]	5	6	450
3	7	3	5	9[150]	2[100]	250
Потребности	100	125	325	250	100

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

Строим новый план.

Значение целевой функции для этого опорного плана равно:

F(x) = 5*100 + 10*100 + 2*125 + 2*325 + 9*150 + 2*100 = 3950

Искомый элемент равен 2

Для этого элемента запасы равны 250, потребности 100. Поскольку минимальным является 100, то вычитаем его.

x₃₅ = min(250,100) = 100.

5	8	7	10	x	200
4	2	2	5	x	450
7	3	5	9	2	250 - 100 = 150
100	125	325	250	100 - 100 = 0	0

Искомый элемент равен 2

Для этого элемента запасы равны 450, потребности 125. Поскольку минимальным является 125, то вычитаем его.

x₂₂ = min(450,125) = 125.

5	x	7	10	x	200
4	2	2	5	x	450 - 125 = 325
7	x	5	9	2	150
100	125 - 125 = 0	325	250	0	0

Искомый элемент равен 2

Для этого элемента запасы равны 325, потребности 325. Поскольку минимальным является 325, то вычитаем его.

x₂₃ = min(325,325) = 325.

5	x	x	10	x	200
x	2	2	x	x	325 - 325 = 0
7	x	x	9	2	150
100	0	325 - 325 = 0	250	0	0

Искомый элемент равен 5

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

x₁₁ = min(200,100) = 100.

5	x	x	10	x	200 - 100 = 100
x	2	2	x	x	0
x	x	x	9	2	150
100 - 100 = 0	0	0	250	0	0

Искомый элемент равен 9

Для этого элемента запасы равны 150, потребности 250. Поскольку минимальным является 150, то вычитаем его.

x₃₄ = min(150,250) = 150.

5	x	x	10	x	100
x	2	2	x	x	0
x	x	x	9	2	150 - 150 = 0
0	0	0	250 - 150 = 100	0	0