матан 5
.rtfЗАДАЧА 5
ВАРИАНТ 9
Транспортная задача.
Запишем экономико-математическую модель для нашей задачи.
Переменные:
x11 – количество груза из 1-го склада в 1-й магазин
x12 – количество груза из 1-го склада в 2-й магазин
x13 – количество груза из 1-го склада в 3-й магазин
x14 – количество груза из 1-го склада в 4-й магазин
x15 – количество груза из 1-го склада в 5-й магазин
x21 – количество груза из 2-го склада в 1-й магазин
x22 – количество груза из 2-го склада в 2-й магазин
x23 – количество груза из 2-го склада в 3-й магазин
x24 – количество груза из 2-го склада в 4-й магазин
x25 – количество груза из 2-го склада в 5-й магазин
x31 – количество груза из 3-го склада в 1-й магазин
x32 – количество груза из 3-го склада в 2-й магазин
x33 – количество груза из 3-го склада в 3-й магазин
x34 – количество груза из 3-го склада в 4-й магазин
x35 – количество груза из 3-го склада в 5-й магазин
x41 – количество груза из 4-го склада в 1-й магазин
x42 – количество груза из 4-го склада в 2-й магазин
x43 – количество груза из 4-го склада в 3-й магазин
x44 – количество груза из 4-го склада в 4-й магазин
x45 – количество груза из 4-го склада в 5-й магазин
x51 – количество груза из 5-го склада в 1-й магазин
x52 – количество груза из 5-го склада в 2-й магазин
x53 – количество груза из 5-го склада в 3-й магазин
x54 – количество груза из 5-го склада в 4-й магазин
x55 – количество груза из 5-го склада в 5-й магазин
Ограничения по запасам:
x11 + x12 + x13 + x14 + x15 = 200
x21 + x22 + x23 + x24 + x25 = 400
x31 + x32 + x33 + x34 + x35 = 600
x41 + x42 + x43 + x44 + x45 = 200
x51 + x52 + x53 + x54 + x55 = 200
Ограничения по потребностям:
x11 + x21 + x31 + x41 + x51 = 200
x12 + x22 + x32 + x42 + x52 = 400
x13 + x23 + x33 + x43 + x53 = 400
x14 + x24 + x34 + x44 + x54 = 300
x15 + x25 + x35 + x45 + x55 = 500
Целевая функция:
F(x)=1x11 + 6x12 + 9x13 + 3x14 + 4x15 + 3x21 + 2x22 + 2x23 + 4x24 + 5x25 + 4x31 + 5x32 + 4x33 + 7x34 + 6x35 + 1x41 + 4x42 + 3x43 + 9x44 + 8x45 + 7x51 + 9x52 + 7x53 + 1x54 + 9x55 → 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
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v4 = 3; 0 + v4 = 3; v4 = 3
u5 + v4 = 1; 3 + u5 = 1; u5 = -2
u1 + v5 = 4; 0 + v5 = 4; v5 = 4
u3 + v5 = 6; 4 + u3 = 6; u3 = 2
u3 + v2 = 5; 2 + v2 = 5; v2 = 3
u2 + v2 = 2; 3 + u2 = 2; u2 = -1
u2 + v1 = 3; -1 + v1 = 3; v1 = 4
u3 + v3 = 4; 2 + v3 = 4; v3 = 2
u4 + v3 = 3; 2 + u4 = 3; u4 = 1
u6 + v5 = 0; 4 + u6 = 0; u6 = -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] |