Методы принятия управленческих решений

Учебник:

Методы оптимальных решений

Александрова, Гончаренко

Лекция 1

Транспортная задача

Примеры:

Задача логистики (поставщики и потребители) - //по аналогии решается задача банковских кредитов

Общая постановка задачи количественной оценки УР

Списать у демонов

Математическая подстановка ТЗ

Есть m поставщиков (А1 А2 … Ан)

n потребителей (В1 В2 … Вн)

a_i i=1…m - запасы продукции

b_j j=1….n - потребители

с_ij - стоимость перевозки

Требуется найти объем перевозки (от поставщика А_j до потребителя B_j) - x_ij

Z=∑m(i=1)∑n(j=1)*c_ijx_ij – min

Условия

1. Все запасы поставщиков вывезены ∑n(j=1)*x_ij=a_i; a=1…m

2. Все потребности поставщиков должны быть удовлетворены ∑m(j=1)x_ij=b_j; j=1…n,

3. x_ij>=0; i=1…m; j=1…m

В ТЗ система ограничений и целевая ф-ция являются ЛИНЕЙНЫМИ

Метод решения ТЗ

Решение ТЗ – матрица Х=||x_ij||^i=1…m_j=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

Строки – поставщики

Столбцы – потребители

В доп столбце A_i – запасы поставщиков

В доп строке B_j – потребности потребителей

Условия решения

Правильный баланс (ТЗ называется задачей с правильным балансом, а ее модель – закрытой, если суммарные запасы поставщиков равны суммарным запасам потребителей ∑m(i=1)a_i=∑n(j=1)b_j) //в противном случае – баланс неправильный, модель открытая

Перед тем, как составлять начальный опорный план (удов системе ограничений) нужно проверить, является ли модель закрытой (с правильным балансом)

Для этого нужно вычислить сумму-компонент столбца a_i и строки b_j (совпадать должны они)

Метод минимального тарифа построения начального опорного плана тз

Суть: выбирается клетка с минимальным тарифом, в который ставится максимально возможная перевозка

В зависимости от того, чьи потребности удовлетворены, вычеркивается либо строка, либо столбец. Так продолжается до тех пор, пока вся таблица не будет заполнена (нет строк и столбцов)

	В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)

1. Проверяем баланс (A_j=400 & B_i=400)

2. Находим мин тариф (1)

3. Выбираем максимальную возможную перевозку (значение A_j & B_i, записываем меньшее)

4. Вычеркиваем строку/столбец (удовлетворены потребности поставщика/потребителя)

	В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)