Max {Tдост I } min.
Реальная математическая постановка задачи динамического программирования.
Рассматривается семь маршрутов вывоза запасов с реальными объемами МС – результат решения транспортной задачи линейного программирования – рис. 8. С этой целью введем обозначения используемых маршрутов: маршрут А1 – В1 определим как маршрут № 1 для задачи динамического программирования, А1 – В3 - № 2, А2 – В3 - № 3, А2 – В2 - № 4, А1 – В6 - № 5, А1 – В4 - № 6, А2 – В5 - № 7.
В качестве неизвестных величин будет распределение исправных автомобилей по маршрутам вывоза запасов:
{N1; N2; N3; N4; N5; N6; N7},
где Ni – выделенное количество автомобилей на i-й маршрут, i = 1 7.
При этом должно выполняться естественное условие:
7
Ni = N*,
i=1
где N* - количество распределяемых автомобилей.
Время вывоза МС со складов для каждого маршрута, в соответствии с исходными данными, определяется:
T1 = [1,4 + 1,3 + 2 * 25 * 1,2 / 35] * [310 / (5,5 * N1)];
T2 = [1,1 + 1,3 + 2 * 24 * 1,2 / 35] * [70 / (5,5 * N2)];
T3 = [1,3 + 1,3 + 2 * 27 * 1,2 / 35] * [250 / (5,5 * N3)];
T4 = [1,4 + 1,3 + 2 * 25 * 1,2 / 35] * [380 / (5,5 * N4)];
T5 = [1,1 + 1,3 + 2 * 28 * 1,2 / 35] * [90 / (5,5 * N5)];
T6 = [1,4 + 1,3 + 2 * 33 * 1,4 / 35] * [330 / (5,5 * N6)];
T7 = [1,3 + 1,3 + 2 * 28 * 1,2 / 35] * [220 / (5,5 * N7)].
Тогда целевая функция примет вид
max {T1, Т2, Т3, Т4, Т5, Т6, Т7} min,
а ограничениями будут
T1 + Т2 + Т3 + Т4 + Т5 + Т6 + Т7 = N*;
T1 1; Т2 1; Т3 1; Т4 1; Т5 1; Т6 1; Т7 1;
Данные для решения задачи динамического программирования сведем в таблицу 9.
Таблица 9
|
Марш-руты |
Протяжен-ность, км |
Ку.д. |
Время разгрузки МС на складе потребителя, ч |
Количество МС, перевозимых по данному маршруту, т |
|
1 |
25 |
1,2 |
1,4 |
310 |
|
2 |
24 |
1,2 |
1,1 |
70 |
|
3 |
27 |
1,2 |
1,3 |
250 |
|
4 |
25 |
1,2 |
1,4 |
380 |
|
5 |
28 |
1,2 |
1,1 |
90 |
|
6 |
33 |
1,4 |
1,4 |
330 |
|
7 |
28 |
1,2 |
1,3 |
220 |
Количество автомобилей в автомобильном предприятии – 66; средняя грузоподъемность автомобиля – 5,5 т; время загрузки на складах – 1,3 часа; средняя скорость движения – 35 км/ч.
Постановка вероятностной модели.
Решение задачи динамического программирования ведется для нескольких различных значений параметра Nt – количества исправных автомобилей в автомобильном предприятии на момент времени t. Ясно, что вывоз материальных средств со складов потребителям смогут осуществлять только исправные автомобили. Их количество заблаговременно не известно. Причина в том, что процессы выхода из строя, ремонта автомобилей и введение их в строй являются стохастическими. Поэтому в произвольный момент времени, когда будет осуществляться вывоз МС со складов, нам не известно точное количество исправных автомобилей, участвующих в этом процессе, т.е. возможна только некоторая вероятностная оценка количества исправных автомобилей.
Исходя из КТГ автомобильного предприятия, ожидаемое количество исправных автомобилей выражается как Ncp = N * КТГ. Однако среднее (ожидаемое) значение тоже не дает исчерпывающей информации о конкретном количестве исправных автомобилей в автомобильном предприятии в произвольный момент времени. Поэтому вместе с количеством исправных автомобилей необходимо знать вероятность того, что в произвольный момент времени будет точно Nt автомобилей.
Данное значение можно получить опираясь на теорему теории вероятностей: при воздействии на любую систему большого количества случайных величин (процессов), подчиненных различным законам распределения, итоговое случайное событие будет распределено по закону асимптотически близкому к нормальному, а отклонения его значений от среднего (ожидаемого) значения подчиняются правилу трех сигм. Исходя из этого предположения, количество исправных автомобилей в автомобильном предприятии также будет иметь распределение близкое к нормальному распределению.
Допустим, что в нашем случае распределение случайных величин асимптотически близко к нормальному распределению, а ее функция плотности имеет вид:
f(N) = 1/((2 )½ ) exp {-(N - Nср)2/(2 2) },
где - средне квадратическое отклонение, определяемое из предположения нормальности распределения количества автомобилей. Его значение в нашем случае равно = N (1 – KTГ) / 3.
Тогда количество исправных автомобилей с вероятностью 0,997 будет находиться винтервале [(2*КТГ – 1)*N; N] - рис. 8, а их вероятное количество определяются из рисунка 9. Для нашего случая N = 66; Ncp = 49,5; интервал значений - [33; 66]. Проводим моделирование на ЭВМ для автомобилей, осуществляющих вывоз МС со складов потребителям и их конкретное распределение по маршрутам вывоза запасов МС, начиная с 33 до 66 единиц.
Рис. 8
Рис. 9
Полученные результаты приведены в виде таблицы значений – табл. 10, в графической форме – рисунок 10.
Рис. 10
Таблица 10
|
N |
33 |
34 |
35 |
36 |
37 |
38 |
39 |
40 |
41 |
42 |
43 |
44 |
45 |
46 |
47 |
48 |
49 |
|
T |
45,2 |
45,2 |
44,5 |
44,1 |
44,1 |
42,7 |
39,7 |
39,7 |
38,9 |
37,4 |
36,2 |
35,6 |
35,3 |
35,3 |
32,0 |
32,0 |
31,6 |
|
1 |
6 |
6 |
6 |
6 |
6 |
7 |
7 |
7 |
8 |
8 |
8 |
8 |
8 |
8 |
9 |
9 |
9 |
|
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
|
3 |
5 |
5 |
5 |
6 |
6 |
6 |
6 |
6 |
6 |
6 |
6 |
6 |
7 |
7 |
7 |
7 |
7 |
|
4 |
7 |
7 |
7 |
7 |
8 |
8 |
8 |
9 |
9 |
9 |
9 |
9 |
9 |
10 |
10 |
10 |
10 |
|
5 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
|
6 |
7 |
8 |
8 |
8 |
8 |
8 |
9 |
9 |
9 |
9 |
10 |
10 |
10 |
10 |
10 |
11 |
12 |
|
7 |
4 |
4 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
6 |
6 |
6 |
6 |
6 |
6 |
|
N |
50 |
51 |
52 |
53 |
54 |
55 |
56 |
57 |
58 |
59 |
60 |
61 |
62 |
63 |
64 |
65 |
66 |
|
T |
31,2 |
30,9 |
30,9 |
30,9 |
28,3 |
27,1 |
26,7 |
26,7 |
26,7 |
26,7 |
26,7 |
26,5 |
26,5 |
26,5 |
26,5 |
25,9 |
22,6 |
|
1 |
9 |
9 |
9 |
9 |
10 |
10 |
10 |
10 |
10 |
10 |
10 |
10 |
10 |
10 |
10 |
12 |
12 |
|
2 |
2 |
2 |
2 |
2 |
2 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
|
3 |
7 |
8 |
8 |
8 |
8 |
8 |
8 |
8 |
10 |
10 |
10 |
10 |
10 |
10 |
10 |
10 |
10 |
|
4 |
10 |
10 |
10 |
12 |
12 |
12 |
12 |
12 |
12 |
12 |
12 |
12 |
12 |
14 |
14 |
14 |
14 |
|
5 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
4 |
3 |
4 |
3 |
4 |
|
6 |
12 |
12 |
12 |
12 |
12 |
12 |
12 |
12 |
12 |
12 |
12 |
15 |
15 |
15 |
15 |
15 |
15 |
|
7 |
7 |
7 |
8 |
7 |
7 |
7 |
8 |
8 |
8 |
8 |
10 |
8 |
8 |
8 |
8 |
8 |
8 |
Здесь под цифрами 1, 2, 3, 4, 5, 6 и 7 подразумеваются номера маршрутов, а им соответствующие цифры – количество автомобилей выделенных на данный конкретный маршрут при выделении Nt автомобилей для вывоза запасов.
Однако последняя зависимость (рис. 10) не дает ответа на вопрос: с какой вероятностью для каждого значения Nt будет осуществлен вывоз запасов МС. Ясно, что вероятность распределения наличия исправных автомобилей на интервале [33; 66], представленная на рисунках 8 и 9, будет каким то образом представляться на оси времени в интервале [22,6; 45,2] -рис. 10. Форма этого представления следующая: определяются интервалы на оси ординат - времени, соответствующие каждому единичному интервалу оси абсцисс – размером в один автомобиль. Вероятность, присущая данному значению количества автомобилей, соответствует, полученной в результате моделирования, длительности вывоза запасов. Учитывая, что нескольким интервалам на оси абсцисс соответствует одно и то же значение длительности вывоза на оси ординат (например, для значений 56, 57, 58, 59, 60 автомобилей получено одно значение времени – 26,7 часа), то необходимо производить нормирование полученной плотности распределения – рис. 11.
Рис.
11
На основании плотности распределения строится функция распределения времени вывоза запасов МС со складов, представленная на рисунке 12.
Рис.
12.
Результаты моделирования можно представить на одном-двух листах, где представлены все результаты моделирования – рис. 13-14. К этим графикам студент дает детальное описание методики получения каждого результата.