Методы принятия управленческих решений
Учебник: Методы
оптимальных решений Александрова,
Гончаренко
Транспортная задача
Примеры:
Задача логистики (поставщики и потребители) - //по аналогии решается задача банковских кредитов
Общая постановка задачи количественной оценки УР
Списать у демонов
Математическая подстановка ТЗ
Есть m поставщиков (А1 А2 … Ан)
n потребителей (В1 В2 … Вн)
ai i=1…m - запасы продукции
bj j=1….n - потребители
сij - стоимость перевозки
Требуется найти объем перевозки (от поставщика Аj до потребителя Bj) - xij
Z=∑m(i=1)∑n(j=1)*cijxij – min
Условия
Все запасы поставщиков вывезены ∑n(j=1)*xij=ai; a=1…m
Все потребности поставщиков должны быть удовлетворены ∑m(j=1)xij=bj; j=1…n,
xij>=0; i=1…m; j=1…m
В ТЗ система ограничений и целевая ф-ция являются ЛИНЕЙНЫМИ
Метод решения ТЗ
Решение ТЗ – матрица Х=||xij||i=1…mj=1…n
План, удовлетворяющий системе ограничений 1-3, называется опорным
План, для которого стоимость перевозки минимальна – называется оптимальным
Построение начального опорного плана ТЗ
Рассмотрим частный случай
-
В1
В2
В3
В4
Ai
A1
С11
C12
C13
C14
a1
A2
C21
C22
C23
C24
a2
A3
C31
C32
C33
C34
a3
Bj
b1
b2
b3
b4
Строки – поставщики
Столбцы – потребители
В доп столбце Ai – запасы поставщиков
В доп строке Bj – потребности потребителей
Условия решения
Правильный баланс (ТЗ называется задачей с правильным балансом, а ее модель – закрытой, если суммарные запасы поставщиков равны суммарным запасам потребителей ∑m(i=1)ai=∑n(j=1)bj) //в противном случае – баланс неправильный, модель открытая
Перед тем, как составлять начальный опорный план (удов системе ограничений) нужно проверить, является ли модель закрытой (с правильным балансом)
Для этого нужно вычислить сумму-компонент столбца ai и строки bj (совпадать должны они)
Метод минимального тарифа построения начального опорного плана тз
Суть: выбирается клетка с минимальным тарифом, в который ставится максимально возможная перевозка
В зависимости от того, чьи потребности удовлетворены, вычеркивается либо строка, либо столбец. Так продолжается до тех пор, пока вся таблица не будет заполнена (нет строк и столбцов)
-
В1
В2
В3
В4
Ai
A1
11
5
4
2
80
A2
1
4
5
9
170-70=100
70
A3
9
8
7
10
150
bi
70-70=0
60
180
90
(400)
Проверяем баланс (Aj=400 & Bi=400)
Находим мин тариф (1)
Выбираем максимальную возможную перевозку (значение Aj & Bi, записываем меньшее)
Вычеркиваем строку/столбец (удовлетворены потребности поставщика/потребителя)
-
В1
В2
В3
В4
Ai
A1
11
5
4
2
80-80=0
80
A2
1
4
5
9
170-70=100
70
A3
9
8
7
10
150
bi
70-70=0
60
180
90-80 =10
(400)
-
В1
В2
В3
В4
Ai
A1
11
5
4
2
80-80=0
80
A2
1
4
5
9
170-70=100
100-60=40
70
60
A3
9
8
7
10
150
bi
70-70=0
60-60=0
180
90-80 =10
(400)
-
В1
В2
В3
В4
Ai
A1
11
5
4
2
80-80=0
80
A2
1
4
5
9
170-70=100
100-60=40
40-40=0
70
60
40
A3
9
8
7
10
150
bi
70-70=0
60-60=0
180-40=140
90-80 =10
(400)
-
В1
В2
В3
В4
Ai
A1
11
5
4
2
80-80=0
80
A2
1
4
5
9
170-70=100
100-60=40
40-40=0
70
60
40
A3
9
8
7
10
150-140=10
140
bi
70-70=0
60-60=0
180-40=140
140-140=0
90-80 =10
(400)
-
В1
В2
В3
В4
Ai
A1
11
5
4
2
80-80=0
80
A2
1
4
5
9
170-70=100
100-60=40
40-40=0
70
60
40
A3
9
8
7
10
150-140=10
10-10=0
140
10
bi
70-70=0
60-60=0
180-40=140
140-140=0
90-80 =10
10-10=0
(400)
Клетка таблицы ТЗ называется занятой, если в нее вписана перевозка (xij>0)