Найдено
90 решенных задач данной темы.
Подробнее ...
Условие задачи
Решить транспортную задачу.
A = (60, 40, 100, 50)
B = (30, 80, 70, 35, 40)
$
C = \left(
\begin{array}{rrrrr}
8&12&4&9&10\\
7&5&15&3&6\\
9&4&6&12&7\\
5&3&2&6&4
\end{array}
\right)
$
Решение
Построим схему транспортной сети матричной задачи оптимизации.
Запишем условие задачи в экономическом виде на основании таблицы, где заданы пункты
отправления и назначения, запасы и потребности.
Пункты отправления |
Пункты назначения |
Запасы |
B1 |
B2 |
B3 |
B4 |
B5 |
A1 |
8 |
12 |
4 |
9 |
10 |
60 |
A2 |
7 |
5 |
15 |
3 |
6 |
40 |
A3 |
9 |
4 |
6 |
12 |
7 |
100 |
A4 |
5 |
3 |
2 |
6 |
4 |
50 |
Потребности |
30 |
80 |
70 |
35 |
40 |
255\250 |
Поскольку запасы и потребности не совпадают, имеем задачу с неправильным балансом или
открытую, следовательно введем фиктивный пункт отправления с количеством 5 единиц груза.
Запишем общую математическую постановку транспортной задачи как задачи линейного программирование, которая заключается в определении минимального значения функции:
$ F = \sum\limits_{i=1}^m \sum\limits_{j=1}^n c_{ij} x_{ij} $
при условиях:
$ \sum\limits_{i=1}^m x_{ij} = b_j (j=1..n),\; \sum\limits_{j=1}^n x_{ij} = a_i (i=1..m) $,
xij > 0, xij є Z.
Следовательно, задача линейного программирования запишется так:
F = 8x11 + 12x12 + 4x13 + 9x14 + 10x15 + 7x21 + 5x22 + 15x23 + 3x24 + 6x25 + 9x31 + 4x32 + 6x33 + 12x34 + 7x35 + 5x41 + 3x42 + 2x43 + 6x44 + 4x45 → min
при условиях:
x11 + x12 + x13 + x14 + x15 = 60,
x21 + x22 + x23 + x24 + x25 = 40,
x31 + x32 + x33 + x34 + x35 = 100,
x41 + x42 + x43 + x44 + x45 = 50,
x51 + x52 + x53 + x54 + x55 = 5,
x11 + x21 + x31 + x41 + x51 = 30,
x12 + x22 + x32 + x42 + x52 = 80,
x13 + x23 + x33 + x43 + x53 = 70,
x14 + x24 + x34 + x44 + x54 = 35,
x15 + x25 + x35 + x45 + x55 = 40,
xij > 0, xij є Z.
Найдем опорный план методом наименьшей стоимости.
Порядок заполнения клеток следующий:
A5B1 (0) = 5,
A4B3 (2) = 50,
A2B4 (3) = 35,
A1B3 (4) = 20,
A3B2 (4) = 80,
A2B5 (6) = 5,
A3B5 (7) = 20,
A1B1 (8) = 25,
A1B5 (10) = 15.
B A |
1 |
2 |
3 |
4 |
5 |
a |
30 |
80 |
70 |
35 |
40 |
1 |
60 |
8 |
12 |
4 |
9 |
10 |
0 |
25 |
|
|
|
20 |
+ |
|
|
15 |
– |
2 |
40 |
7 |
5 |
15 |
3 |
6 |
-4 |
|
|
|
|
|
|
35 |
|
5 |
|
3 |
100 |
9 |
4 |
6 |
12 |
7 |
-3 |
|
|
80 |
|
|
|
|
|
20 |
|
4 |
50 |
5 |
3 |
2 |
6 |
4 |
-2 |
|
|
|
|
50 |
– |
|
|
0 |
+ |
5 |
5 |
0 |
0 |
0 |
0 |
0 |
-8 |
5 |
|
|
|
|
|
|
|
|
|
b |
8 |
7 |
4 |
7 |
10 |
|
Стоимость начального плана перевозки:
z0 = 25 · 8 + 20 · 4 + 15 · 10 + 35 · 3 + 5 · 6 + 80 · 4 + 20 · 7 + 50 · 2 + 5 · 0 = 1125.
Для базисных клеток система потенциалов такая:
a1 + b1 = 8;
a1 + b3 = 4;
a1 + b5 = 10;
a2 + b4 = 3;
a2 + b5 = 6;
a3 + b2 = 4;
a3 + b5 = 7;
a4 + b3 = 2;
a5 + b1 = 0.
Поскольку количество переменных меньше, чем уравнений, то положим a1 = 0.
Проверяем условие оптимальности для свободных клеток: a + b < c.
a1 + b2 = 0 + 7 = 7 < 12;
a1 + b4 = 0 + 7 = 7 < 9;
a2 + b1 = -4 + 8 = 4 < 7;
a2 + b2 = -4 + 7 = 3 < 5;
a2 + b3 = -4 + 4 = 0 < 15;
a3 + b1 = -3 + 8 = 5 < 9;
a3 + b3 = -3 + 4 = 1 < 6;
a3 + b4 = -3 + 7 = 4 < 12;
a4 + b1 = -2 + 8 = 6 > 5 [1];
a4 + b2 = -2 + 7 = 5 > 3 [2];
a4 + b4 = -2 + 7 = 5 < 6;
a4 + b5 = -2 + 10 = 8 > 4 [4];
a5 + b2 = -8 + 7 = -1 < 0;
a5 + b3 = -8 + 4 = -4 < 0;
a5 + b4 = -8 + 7 = -1 < 0;
a5 + b5 = -8 + 10 = 2 > 0 [2].
Для клетки A4B5 (из тех, что не выполняется условие оптимальности) разница потенциалов наибольшая, потому для нее делаем цикл пересчета на минимальную величину отрицательных вершин: min(15, 50) = 15.
Переходим к следующей итерации.
Зарегистрируйтесь и Вы сможете посмотреть задачу полностью!
Найдено 90 решенных задач данной темы. Подробнее ...