Транспортная задача
.docЗадание №2
На трех хлебокомбинатах ежедневно производится 110, 190 и 90 т муки. Эта мука потребляется четырьмя хлебозаводами, ежедневные потребности которых равны соответственно 80, 60, 170 и 80 т. Составить такой план доставки муки, при котором общая стоимость перевозок является минимальной, тарифы перевозок 1т. Муки с хлебокомбинатов к каждому из хлебозаводов задаются матрицей.
;
Математическая модель.
Обозначим номера хлебокомбинатов через i а номера хлебозаводов через j. Количество муки привезенного из хлебокомбината i на хлебозавод j xij.
Тогда должны выполнятся следующие условия:
Минимизируемся функция затрат имеет вид:
Данная задача сбалансирована
Кроме того необходимо учесть что кол-во перевозимого товара не может быть отрицательным:
Поиск оптимальных затрат
Построим первоначальный опорный план методом «северо-западного угла».
Таблица 1
|
B1 |
B2 |
B3 |
B4 |
Запас |
||||
A1 |
|
|
|
|
|
|
|
|
110 |
80 |
|
30 |
|
|
|
|
|
||
A2 |
|
|
|
|
|
|
|
|
190 |
|
|
30 |
|
160 |
|
|
|
||
A3 |
|
|
|
|
|
|
|
|
90 |
|
|
|
|
10 |
|
80 |
|
||
План |
80 |
60 |
170 |
80 |
|
Припишем к таблице снизу добавочную строку для потенциалов , справа добавочный столбец для потенциалов , см. таблица 2
Таблица 2
|
B1 |
B2 |
B3 |
B4 |
Запас |
|||||
A1 |
- |
8 |
+ |
1 |
-3 |
9 |
-2 |
7 |
110 |
0 |
80 |
|
30 |
|
|
|
|
|
|||
A2 |
13 |
4 |
- |
6 |
+ |
2 |
3 |
12 |
190 |
5 |
|
|
30 |
|
160 |
|
|
|
|||
A3 |
19 |
3 |
12 |
5 |
- |
8 |
|
9 |
90 |
11 |
+ |
|
|
|
10 |
|
80 |
|
|||
План |
80 |
60 |
170 |
80 |
390 |
|
||||
8 |
1 |
-3 |
-2 |
|
|
Составим систему шести уравнений с семью неизвестными. Положим a1=0. Решая уравнения найдем неизвестные и сразу получаемые результаты впишем в таблицу. Вычислим псевдостоимости для свободных переменных и также впишем их в таблицу 2
+ =8 =8 + =2 =-3
+ =1 =1 + =8 =11
+ =6 =5 + =9 =-2
Вычисляем псевдостоимости для свободных перемнных =-3, =-2, =13,
=3, =19, =12,
Максимальная разность, между Псевдостоимостью и заданной стоимостью, в ячейке (A3:B1). Построим цикл с началом в найденной свободной клетке.
Припишем к таблице снизу добавочную строку для потенциалов , справа добавочный столбец для потенциалов , см. таблица 3
Таблица 3
|
B1 |
B2 |
B3 |
B4 |
Запас |
|||||
A1 |
- |
8 |
+ |
1 |
-3 |
9 |
14 |
7 |
110 |
0 |
70 |
|
40 |
|
|
|
|
|
|||
A2 |
13 |
4 |
- |
6 |
|
2 |
19 |
12 |
190 |
5 |
+ |
|
20 |
|
170 |
|
|
|
|||
A3 |
19 |
3 |
-4 |
5 |
-8 |
8 |
|
9 |
90 |
-5 |
10 |
|
|
|
|
|
80 |
|
|||
План |
80 |
60 |
170 |
80 |
390 |
|
||||
8 |
1 |
-3 |
14 |
|
|
Составим систему шести уравнений с семью неизвестными. Положим a1=0. Решая уравнения найдем неизвестные и сразу получаемые результаты впишем в таблицу. Вычислим псевдостоимости для свободных переменных и также впишем их в таблицу 2
+ =8 =8 + =2 =5
+ =1 =1 + =3 =-5
+ =6 =5 + =9 =14
Вычисляем псевдостоимости для свободных перемнных =-3, =14, =13,
=19, =-4, =-8,
Максимальная разность, между Псевдостоимостью и заданной стоимостью, в ячейке (A2:B1). Построим цикл с началом в найденной свободной клетке, см. таблицу 4
Таблица 4
|
B1 |
B2 |
B3 |
B4 |
Запас |
|||||
A1 |
- |
8 |
|
1 |
6 |
9 |
14 |
7 |
110 |
0 |
50 |
|
60 |
|
|
|
+ |
|
|||
A2 |
|
4 |
-3 |
6 |
|
2 |
10 |
12 |
190 |
-4 |
20 |
|
|
|
170 |
|
|
|
|||
A3 |
+ |
3 |
-4 |
5 |
1 |
8 |
- |
9 |
90 |
-5 |
10 |
|
|
|
|
|
80 |
|
|||
План |
80 |
60 |
170 |
80 |
390 |
|
||||
8 |
1 |
6 |
14 |
|
|
Составим систему шести уравнений с семью неизвестными. Положим a1=0. Решая уравнения найдем неизвестные и сразу получаемые результаты впишем в таблицу. Вычислим псевдостоимости для свободных переменных и также впишем их в таблицу 2
+ =8 =8 + =2 =6
+ =1 =1 + =3 =-5
+ =4 =-4 + =9 =14
Вычисляем псевдостоимости для свободных перемнных =6, =14, =-3,
=10, =-4, =1,
Максимальная разность, между Псевдостоимостью и заданной стоимостью, в ячейке (A1:B4). Построим цикл с началом в найденной свободной клетке, см. таблицу 5
Таблица 4
|
B1 |
B2 |
B3 |
B4 |
Запас |
|||||
A1 |
1 |
8 |
|
1 |
-1 |
9 |
|
7 |
110 |
0 |
|
|
60 |
|
|
|
50 |
|
|||
A2 |
|
4 |
4 |
6 |
|
2 |
10 |
12 |
190 |
3 |
20 |
|
|
|
170 |
|
|
|
|||
A3 |
|
3 |
3 |
5 |
1 |
8 |
|
9 |
90 |
2 |
60 |
|
|
|
|
|
30 |
|
|||
План |
80 |
60 |
170 |
80 |
390 |
|
||||
1 |
1 |
-1 |
7 |
|
|