Пример решения транспортной задачи (открытая модель)

1.

Пример решения
транспортной задачи
(открытая модель)
Исследование операций

2. Задача

Выпуск продукции трех заводов A1, A2, A3 составляет
260, 240, 300 т. Потребности четырех потребителей
B1, B2, B3, B4 равны 300, 200, 250, 100 т.
Известно:
1) продукция завода A1 не требуется пункту B4;
2) с завода A3 потребителю B2 должно быть доставлено
груза не более 50 т.
Тарифы перевозок сij (в ден/ед.) из Ai в Bj приведены в
матрице:
3 4 6 1
C 5 7 2 3
4
3
8
6
Составить оптимальный план перевозок груза.

3. Решение:

Так как a1+a2+a3 = 260+240+300 = 800,
b1+b2+b3+b4 = 300+200+250+100 = 850,
т.е. (b1+b2+b3+b4)-(a1+a2+a3) = 50, то введем
фиктивного поставщика A4 с запасами a4=50 и
нулевыми тарифами.
Получили закрытую модель транспортной задачи.
Учтем условия:
1) В клетку A1B4 запишем число M (блокируем).
2) В столбце B2 запишем потребности b2=50, остальные
b2*=150 заносим в дополнительный столбец B2*.
Все тарифы, как в B2, но в A3B2* ставим число M.

4.

Решение задачи методом наименьшей стоимости
B1
A1
A2
110
B2
3
4 шаг
Х
5
Х
Х
4
7
190
50
5 шаг
1 шаг
0
Х
240
Х
Х
Х
bj
300
50
6
2
M
Х
8
B2*
1
3
6
60
0
150
Х
M
0
10
40
7 шаг
8 шаг
250
100
ai
4
2 шаг
6 шаг
0
A4
B4
3 шаг
3
4
A3
B3
7
260
240
3
300
0
Х
50
150
850

5. Опорное решение задачи

110 150 0 0
0 0 240 0
X 1 190 50 0 60
0 0 10 40
Проверим опорный план X1
на оптимальность

6. Составим систему уравнений для заполненных ячеек:

110 150 0 0
0 0 240 0
X1
190
50
0
60
Пусть u1 = 0, тогда: v1 = 3
0 0 10 40
3 4 6 1
v2*= 4
5 7 2 3
Так как v3 = 5, то u2 = 3
C
4
3
8
6
Так как v1 = 3, то u3 = 1
0 0 0 0
Составим систему уравнений
для заполненных ячеек:
u1 + v 1 = 3
u1 + v2* = 4
u2 + v 3 = 2
u3 + v 1 = 4
u3 + v 2 = 3
u3 + v 4 = 6
u4 + v 3 = 0
u4 + v 4 = 0
Так как u3 = 1, то v2 = 2
Так как u3 = 1, то v4 = 5
Так как u4 = 5, то v3 = 5
Так как v4 = 5, то u4 = 5
Итак, u1 = 0, u2 = 3, u3 = 1, u4 = 5,
v1 = 3, v2 = 2, v2*= 4, v3 = 5, v4 = 5

7. Проверим второе условие теоремы для незаполненных строк

110 150 0 0
3
0 0 240 0
5
X1
C
190 50 0 60
4
0 0 10 40
0
4
7
3
0
6
2
8
0
1
3
6
0
u1 = 0, u2 = 3, u3 = 1, u4 = 5,
v1 = 3, v2 = 2, v2*= 4, v3 = 5, v4 = 5
u1 + v2* = 4 ≤ C12 = 4 +
u1 + v3 = 5 ≤ C13 = 6 +
u1 + v4 = 5 > C14 = 1 ( 4)
u2 + v1 = 0 ≤ C21 = 5 +
u2 + v2 = 1 ≤ C22 = 7 +
u2 + v4 = 2 ≤ C24 = 3 +
u3 + v3 = 6 ≤ C33 = 8 +
u4 + v1 = 2 ≤ C41 = 0 +
u4 + v2 = 3 ≤ C42 = 0 +
Но ячейка A1B4 заблокирована, следовательно,
план X1 оптимальный

8. Оптимальное решение:

110 150 0 0
0 0 240 0
X1
190 50 0 60
0 0 10 40
3
5
C
4
0
4
7
3
0
6
2
8
0
1
3
6
0
Zmin = 110*3+150*4+240*2+190*4+50*3+60*6+
+10*0+40*0 = 2680

9. Используемая литература:

Борзунова Т.Л., Барыкин М.П. , Данилов Е.А.
Соловьева О.Ю. - Математическое моделирование:
учебное пособие/ВолгГТУ, - Волгоград, 2008.
Конюховский П.В. Математические методы
исследования операций в экономике – СПб: Питер,
2000.