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

Рассмотрим классическую задачу математического программирования, подробно исследованную в детерминистической постановке многими авторами, в частности, Г. Вагнером [8], У. Чечменом [9], Е. Вентцель [8].

Допустим, что имеется I поставщиков дорогостоящих изделий, в которых нуждаются N потребителей. Стоимость перевозки x_in изделий от i-го поставщика n-му потребителю оценивается значением функции F_in(x_in). Все изделия одинаковы по типу и стоимости. Изделия могут перевозиться только автомобильным транспортом и только по одному изделию в машине. Общий спрос Q на изделия в точности равен их суммарному запасу D у всех поставщиков.

Задача состоит в выборе такого плана перевозок, для которого общая стоимость транспортировки всех изделий будет минимальной.

Обозначим через c(x) суммарную стоимость планируемой операции, тогда задача сводится к выбору такого вектора x_in*, для которого:

(6.3.4)

где:

(6.3.5)

(6.3.6)

(4.3.7)

(6.3.8)

, (достаточность изделий на i-м складе) (6.3.9)

, ( удовлетворение спроса n-го потребителя) (6.3.10)

Функция стоимости перевозки x_in изделий от i-го поставщика n-му потребителю имеет вид:

(6.3.11)

где: A_in, B_in, C_in, - соответствующие значения коэффициентов.

Стоимость поставки n-му потребителю x_n изделий зависит не только от условий перевозки (6.3.1), но и от степени удовлетворения спроса:

(6.3.12)

где: k_n - коэффициент штрафа, определяющий издержки за недопоставку или излишнюю поставку n-му потребителю одного изделия.

Сформулированная задача отличается от постановок, приведенных в рассмотренных ранее примерах, целочисленностью аргумента целевой функции, в роли которого выступает количество x_in изделий, включаемых в план перевозок, а также неявной зависимостью процесса от времени. В рассматриваемой постановке распределение изделий между потребителями можно трактовать как функциональную зависимость стоимости перевозок от времени, т. е. зависимость переменных от индекса n в данном случае адекватна их зависимости от времени, что должно исключить сомнения в необходимости решения транспортной задачи именно в динамической постановке.

Кроме того, рассматривается вариант дискретного изменения фазовых координат системы, что приводит к необходимости использования конечно-разностных, а не дифференциальных уравнений в модели, отражающей закон изменения состояния системы.

В постановке (6.3.4)...(6.3.12) транспортная задача имеет стандартные методы решения. Приблизим поставленную задачу к реальности и допустим, что спрос на изделия известен компании лишь приближенно, с достоверностью w_n по каждому n-му потребителю.

Если руководство компании принимает отличное от оптимального решение при полной уверенности в достоверности спрогнозированного спроса, то компании представляются конкретные точные расчеты издержек и ни о каком риске не может быть речи. В том случае, когда значения w_n отличны от единицы, руководство компании не имеет оснований для полной уверенности в совпадении предложенного расчетного варианта поставок изделий с реальным, определяемым сложившимися обстоятельствами по формированию спроса.

В этом случае руководство компании запрашивает несколько вариантов решения задачи и производит оценку риска принимаемого решения.

В качестве целевой функции риска можно рассматривать ожидаемую долю потерянных средств в плановом варианте, отличном от оптимального:

(6.3.13)

(6.3.14)

Конкретизируем пример числовыми данными.

Будем рассматривать два склада с индексами i=0, i=1.

Запасы изделий на этих складах соответственно равны D₀=100, D₁=80.

Значения остальных величин приведены в табл. 6.3.6.

Результаты решения транспортной задачи в стохастической постановке представлены в табл. 6.3.7, где кроме оптимального варианта (вариант 3) приведены результаты расчета еще трех вариантов возможного осуществления перевозок в условиях недостаточной информации о спросе.

В нижней части табл. 6.3.7 приведены значения суммарных затрат c(x) на перевозки изделий.

Таблица 6.3.6.

Исходные данные транспортной задачи.

Индекс N	Спрос Qn	Достов wn	Штраф Kn	Поставщик i = 0 An Bn Cn			Поставщик i = 1 An Bn Cn
0	10	0.9	2	1.0	0.0	0	3.1	0.0	2
1	25	0.8	3	2.0	0.0	1	4.1	0.0	0
2	45	0.9	2	3.0	0.01	0	2.1	0.0	0
3	15	0.7	4	1.5	0.0	0	1.1	0.1	0
4	5	0.6	5	2.5	0.0	0	2.6	0.0	0
5	15	0.5	2	5.0	-0.01	10	3.0	0.0	0
6	20	0.9	6	3.0	0.0	0	1.0	0.2	5
7	15	0.7	2	6.0	0.0	0	2.0	0.0	0
8	10	0.6	7	6.0	-0.05	8	2.0	0.0	0
9	20	0.5	3	6.0	0.0	0	5.0	0.01	0

Таблица 6.3.7.

Результаты расчетов поставок изделий x_in и значений L_n .

n	Количество изделий xin
	Вариант 1			Вариант 2			Вариант 3			Вариант 4
	I=0	i=1	Ln	i=0	i=1	Ln	i=0	i=1	Ln	i=0	i=1	Ln
0	10	0	.000	10	0	.000	8	1	.033	10	1	.041
1	23	0	.027	23	0	.027	25	0	.000	30	0	.125
2	5	38	.003	5	38	.003	5	38	.004	0	40	.026
3	10	0	.241	10	0	.241	12	0	.175	10	3	.108
4	3	0	.218	3	0	.218	3	0	.218	6	0	.150
5	0	18	.187	0	18	.187	0	17	.118	0	10	.218
6	25	12	.097	21	1	.035	21	0	.013	20	1	.017
7	0	10	.171	0	11	.133	0	12	.085	4	16	.215
8	2	2	.370	2	12	.349	2	12	.348	0	8	.218
9	22	0	.083	26	0	.272	24	0	.187	20	1	.031
	c (x) = 2731			c (x) = =953.5			c (x) = 768.4 optimum			c (x) = 772.5

Рассмотрим модули разностей значений целевой функции для оптимального варианта и для рассматриваемых вариантов, приведенные в табл. 6.3.7. Значение модуля разностей вычислялось следующим образом:

(6.3.15)

где i - номер рассматриваемого варианта решения, i = 3 соответствует оптимальному варианту решения (табл. 6.3.7).

Таблица 6.3.8.

Величины модулей отклонений значений целевой функции для различных вариантов решения транспортной задачи.

Индекс n потребителя	Модуль D1n	Модуль D2n	Модуль D4n
0	0.033	0.033	0.008
1	0.027	0.027	0.125
2	0.001	0.001	0.022
3	0.066	0.066	0.067
4	0.000	0.000	0.068
5	0.069	0.069	0.100
6	0.084	0.022	0.004
7	0.086	0.048	0.130
8	0.022	0.000	0.130
9	0.104	0.085	0.156
	0.104	0.085 (min)	0.156

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

В этом случае, отказавшись от оптимального варианта и выбрав указанный план перевозок, компания теряет в стоимости всей операции:

935.5 - 768.4 = 185.1 условных финансовых единиц,

между тем как при реализации варианта 4 эти потери могли составить:

772.5 - 768.1 = 4.4 условных финансовых единиц, правда, с небольшим превышением в значении показателя риска.

Удовлетворяя исследовательское любопытство, приведем оптимальное решение транспортной задачи в детерминистической постановке, т. е. при тех же исходных данных, но для w_n = 1, n = 0,1,2,....,N.

Таблица 6.3.9.

Детерминистический вариант оптимального решения задачи.

Потребитель n	0	1	2	3	4	5	6	7	8	9
Поставщик i=0	10	25	5	15	5	0	20	0	0	20	100
Поставщик i=1	0	0	40	0	0	15	0	15	10	0	80
Спрос Q	10	25	45	15	5	15	20	15	10	20	180

Стоимость осуществления перевозок изделий по варианту, представленному в табл. 6.3.9, составляет 470.25 условных финансовых единиц, что, естественно, меньше значения затрат при наличии неопределенности в спросе изделий.

Предложенный выше подход к оценке риска был построен на сравнении риска, связанного с решением принятия оптимального варианта развития систем, и риска, определяемого волевым решением принятия программы, отличной от оптимального варианта.

На практике зачастую возникает задача сравнения различных предложений или различных программ, ни одна из которых не претендует на роль оптимальной.

Предположим, что поставлена задача сравнения риска нескольких (всего I) вариантов динамических программ, определяющих условия функционирования однотипных систем в одинаковых исходных условиях. Опираясь на разработанный аппарат, можно рассчитать для каждого i  I функцию L_i (t) изменения показателя риска во времени на рассматриваемом интервале t  [0 , T], которая в динамической постановке задачи несколько преломляет свое смысловое содержание.

Возникает задача сравнения функций критериев риска. Как известно, сама по себе задача сравнения функций далеко нетривиальна и могут найти применение различные варианты сравнения. Например:

- по минимуму средних значений функции риска

(6.3.16)

- по минимуму максимального или минимального на интервале [0, T] значения функции риска

(6.3.17)

(6.3.18)

Остановимся на следующем предложении. Поскольку в задаче рассматривается конечный ряд программ, то представляется возможным построить функцию F(t) в гипотетическом предположении, что в любой момент времени t реализована программа с минимальным значением показателя риска:

(6.3.19)

Таким образом, F(t) представляет собой огибающую минимальных значений функций риска среди рассматриваемых. Добиться меньших значений показателя риска без изменения условий задачи не представляется возможным.

Далее построим функцию P_i(t) отклонений значений целевых функций показателей риска каждой из рассматриваемых задач от значений функции F(t), принятой за наилучшую:

(6.3.20)

Значения функции (6.3.20) могут претендовать на роль критерия в задаче сравнения риска при выборе решения в условиях динамического развития систем.

Какую характеристику функции P_i(t) выбрать в качестве скалярного показателя сравнительной оценки (среднее значение, минимальное или максимальное) предстоит решать в каждом конкретном случае отдельно и общие рекомендации здесь будут излишними.

Опасные природные процессы