матан 5

ЗАДАЧА 5

ВАРИАНТ 9

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

Запишем экономико-математическую модель для нашей задачи.

Переменные:

x₁₁ – количество груза из 1-го склада в 1-й магазин

x₁₂ – количество груза из 1-го склада в 2-й магазин

x₁₃ – количество груза из 1-го склада в 3-й магазин

x₁₄ – количество груза из 1-го склада в 4-й магазин

x₁₅ – количество груза из 1-го склада в 5-й магазин

x₂₁ – количество груза из 2-го склада в 1-й магазин

x₂₂ – количество груза из 2-го склада в 2-й магазин

x₂₃ – количество груза из 2-го склада в 3-й магазин

x₂₄ – количество груза из 2-го склада в 4-й магазин

x₂₅ – количество груза из 2-го склада в 5-й магазин

x₃₁ – количество груза из 3-го склада в 1-й магазин

x₃₂ – количество груза из 3-го склада в 2-й магазин

x₃₃ – количество груза из 3-го склада в 3-й магазин

x₃₄ – количество груза из 3-го склада в 4-й магазин

x₃₅ – количество груза из 3-го склада в 5-й магазин

x₄₁ – количество груза из 4-го склада в 1-й магазин

x₄₂ – количество груза из 4-го склада в 2-й магазин

x₄₃ – количество груза из 4-го склада в 3-й магазин

x₄₄ – количество груза из 4-го склада в 4-й магазин

x₄₅ – количество груза из 4-го склада в 5-й магазин

x₅₁ – количество груза из 5-го склада в 1-й магазин

x₅₂ – количество груза из 5-го склада в 2-й магазин

x₅₃ – количество груза из 5-го склада в 3-й магазин

x₅₄ – количество груза из 5-го склада в 4-й магазин

x₅₅ – количество груза из 5-го склада в 5-й магазин

Ограничения по запасам:

x₁₁ + x₁₂ + x₁₃ + x₁₄ + x₁₅ = 200

x₂₁ + x₂₂ + x₂₃ + x₂₄ + x₂₅ = 400

x₃₁ + x₃₂ + x₃₃ + x₃₄ + x₃₅ = 600

x₄₁ + x₄₂ + x₄₃ + x₄₄ + x₄₅ = 200

x₅₁ + x₅₂ + x₅₃ + x₅₄ + x₅₅ = 200

Ограничения по потребностям:

x₁₁ + x₂₁ + x₃₁ + x₄₁ + x₅₁ = 200

x₁₂ + x₂₂ + x₃₂ + x₄₂ + x₅₂ = 400

x₁₃ + x₂₃ + x₃₃ + x₄₃ + x₅₃ = 400

x₁₄ + x₂₄ + x₃₄ + x₄₄ + x₅₄ = 300

x₁₅ + x₂₅ + x₃₅ + x₄₅ + x₅₅ = 500

Целевая функция:

F(x)=1x₁₁ + 6x₁₂ + 9x₁₃ + 3x₁₄ + 4x₁₅ + 3x₂₁ + 2x₂₂ + 2x₂₃ + 4x₂₄ + 5x₂₅ + 4x₃₁ + 5x₃₂ + 4x₃₃ + 7x₃₄ + 6x₃₅ + 1x₄₁ + 4x₄₂ + 3x₄₃ + 9x₄₄ + 8x₄₅ + 7x₅₁ + 9x₅₂ + 7x₅₃ + 1x₅₄ + 9x₅₅ → min

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

	1	2	3	4	5	Запасы
1	1	6	9	3	4	200
2	3	2	2	4	5	400
3	4	5	4	7	6	600
4	1	4	3	9	8	200
5	7	9	7	1	9	200
Потребности	200	400	400	300	500

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

∑a = 200 + 400 + 600 + 200 + 200 = 1600

∑b = 200 + 400 + 400 + 300 + 500 = 1800

Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равной 200 (1800—1600). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.

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

	1	2	3	4	5	Запасы
1	1	6	9	3	4	200
2	3	2	2	4	5	400
3	4	5	4	7	6	600
4	1	4	3	9	8	200
5	7	9	7	1	9	200
6	0	0	0	0	0	200
Потребности	200	400	400	300	500

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

	1	2	3	4	5	Запасы
1	1[200]	6	9	3	4	200
2	3	2[400]	2	4	5	400
3	4	5	4[200]	7	6[400]	600
4	1	4	3[200]	9	8	200
5	7	9	7	1[200]	9	200
6	0	0	0	0[100]	0[100]	200
Потребности	200	400	400	300	500

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

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

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

F(x) = 1*200 + 2*400 + 4*200 + 6*400 + 3*200 + 1*200 + 0*100 + 0*100 = 5000

	1	2	3	4	5	Запасы
1	1	6	9	3[100]	4[100]	200
2	3	2[400]	2	4	5	400
3	4	5	4[400]	7	6[200]	600
4	1[200]	4	3	9	8	200
5	7	9	7	1[200]	9	200
6	0	0	0	0	0[200]	200
Потребности	200	400	400	300	500

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

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

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

F(x) = 3*100 + 4*100 + 2*400 + 4*400 + 6*200 + 1*200 + 1*200 + 0*200 = 4700

	1	2	3	4	5	Запасы
1	1[200]	6	9	3	4	200
2	3	2[400]	2	4	5	400
3	4	5	4[200]	7	6[400]	600
4	1	4	3[200]	9	8	200
5	7	9	7	1[200]	9	200
6	0	0	0	0[100]	0[100]	200
Потребности	200	400	400	300	500

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

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

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

F(x) = 1*200 + 2*400 + 4*200 + 6*400 + 3*200 + 1*200 + 0*100 + 0*100 = 5000

	1	2	3	4	5	Запасы
1	1[200]	6	9	3	4	200
2	3	2[400]	2	4	5	400
3	4	5	4[200]	7	6[400]	600
4	1	4	3[200]	9	8	200
5	7	9	7	1[200]	9	200
6	0	0	0	0[100]	0[100]	200
Потребности	200	400	400	300	500

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

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

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

F(x) = 1*200 + 2*400 + 4*200 + 6*400 + 3*200 + 1*200 + 0*100 + 0*100 = 5000

	1	2	3	4	5	Запасы
1	1[200]	6	9	3	4	200
2	3	2	2[400]	4	5	400
3	4	5[200]	4	7	6[400]	600
4	1	4[200]	3	9	8	200
5	7	9	7	1[200]	9	200
6	0	0	0	0[100]	0[100]	200
Потребности	200	400	400	300	500

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

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

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

F(x) = 1*200 + 2*400 + 5*200 + 6*400 + 4*200 + 1*200 + 0*100 + 0*100 = 5400

	1	2	3	4	5	Запасы
1	1	6	9	3[200]	4	200
2	3	2[400]	2	4	5	400
3	4	5	4[400]	7	6[200]	600
4	1[200]	4	3	9	8	200
5	7	9	7	1[100]	9[100]	200
6	0	0	0	0	0[200]	200
Потребности	200	400	400	300	500

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

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

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

F(x) = 3*200 + 2*400 + 4*400 + 6*200 + 1*200 + 1*100 + 9*100 + 0*200 = 5400

	1	2	3	4	5	Запасы
1	1	6	9	3[100]	4[100]	200
2	3[200]	2[200]	2	4	5	400
3	4	5[200]	4[200]	7	6[200]	600
4	1	4	3[200]	9	8	200
5	7	9	7	1[200]	9	200
6	0	0	0	0	0[200]	200
Потребности	200	400	400	300	500

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

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

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

F(x) = 3*100 + 4*100 + 3*200 + 2*200 + 5*200 + 4*200 + 6*200 + 3*200 + 1*200 + 0*200 = 5500

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₄ = 3; 0 + v₄ = 3; v₄ = 3

u₅ + v₄ = 1; 3 + u₅ = 1; u₅ = -2

u₁ + v₅ = 4; 0 + v₅ = 4; v₅ = 4

u₃ + v₅ = 6; 4 + u₃ = 6; u₃ = 2

u₃ + v₂ = 5; 2 + v₂ = 5; v₂ = 3

u₂ + v₂ = 2; 3 + u₂ = 2; u₂ = -1

u₂ + v₁ = 3; -1 + v₁ = 3; v₁ = 4

u₃ + v₃ = 4; 2 + v₃ = 4; v₃ = 2

u₄ + v₃ = 3; 2 + u₄ = 3; u₄ = 1

u₆ + v₅ = 0; 4 + u₆ = 0; u₆ = -4

	v1=4	v2=3	v3=2	v4=3	v5=4
u1=0	1	6	9	3[100]	4[100]
u2=-1	3[200]	2[200]	2	4	5
u3=2	4	5[200]	4[200]	7	6[200]
u4=1	1	4	3[200]	9	8
u5=-2	7	9	7	1[200]	9
u6=-4	0	0	0	0	0[200]