О В Амельницька - Система лoгicтичнoгo сервісу тpaнcнopтнo-eкcнeдицiйнoгo ніднриємства - страница 54

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90 

Если же, поступивший на склад товар нуждается в сортировке, первичной переработке, упаковке и т.п., то I     ^ 0 . Что

приводит к увеличению совокупных расходов. Целевая функция (4) примет вид:

п _р

W

УУ( dJk+' yJk) - min.

J— 1 к=1

При этом система ограничений (5) и условие не отрицательности (6) останутся прежними.

Т.о. получена задача квадратичного программирования, которая всегда труднее задачи линейного программирования. Можно воспользоваться компьютерной математической системой «WinQSB» - Windows Quantitative System for Business, которая содержит

mподсистему «Quadratic and Integer Quadratic Programming)). Однако более эффективным будет применение команды «Поиск решения» в «Microsoft Excel)).

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

Эту задачу называют задачей коммивояжёра. Её впервые сформулировал математик Карл Менгер. Было это 5 февраля 1930 г. на математическом коллоквиуме в Вене. Менгер называл её «задачей о посыльном».

Пусть имеется n городов. Расстояния между ними составляют Qj ( i, J = 1, n, i ^ J ). Если прямого маршрута между городами i и J не существует, то QiJ = 00. Расстояния записывают в виде матрицы (табл. 1), где Qii = 00.

Табл. 1. Матрица расстояний

J

І

1

2

 

n

1

да

 

 

 

2

a21

да

 

a2n

 

 

 

 

 

п

 

an 2

 

да

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

Пусть городам поставлены в соответствие вершины графа, а соединяющим их дорогам - дуги. Тогда говорят, что задача заключается в определении гамильтонова контура минимальной длины. Гамильтоновым контуром называется путь, проходящий через все вершины графа, у которого начальная вершина совпадает с конечной. Название связано с Уильямом Роуэном Гамильтоном (1805-1865) -выдающимся ирландским математиком и физиком, который занимался похожими проблемами.

Для записи задачи коммивояжёра введём булевы переменные:

= 11, если коммивояжёр переезжает из города i в город J (i, J = 1, n),

X ■ ■  л

J    [0, в противном случае.

Целевая функция имеет вид

nn

Z = zZzZaij  xij ~*mil1, (7)

i=1 J=1

при выполнении следующих ограничений

n _

У^ Xj = 1 , J = 1, n (въезд в город J ), (8)

i=1

n _

У ' Xjj = 1 , i = 1, n (отъезд из города i ). (9)

J 1

В настоящее время разработано большое число эффективных алгоритмов для решения задачи коммивояжёра. Эти алгоритмы запрограммированы в компьютерных математических системах. Автор использует «WinQSB». В этой системе имеется подсистема «Network Modeling» (сетевое моделирование), которая содержит опцию «Traveling Salesman Problem» (задача коммивояжёра). Данная опция позволяет находить оптимальный маршрут разными методами. Среди них - метод ветвей и границ и ещё три эвристических метода (метод эвристической ближайшей вершины и др.).

Проблемы, сводящиеся к решению задачи коммивояжёра, весьма разнообразны и заслуживают внимания. Однако их обычно рассматривают в детерминистической постановке. Т.е. фактор случайности не учитывается совсем.

Будем считать расстояния между городами случайными величинами. Действительно, пользуясь картой или навигатором, водитель рассчитывает на одно расстояние. Оно же может оказаться несколько другим. Это связано со следующими обстоятельствами: а) ремонт участка дороги и необходим объезд; б) маршрут проходит через крупный населённый пункт и водитель, не зная точно направления, может заблудиться; в) стиль вождения автомобиля и др.

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

Пусть расстояние между городами - случайные величины О у (бО) (1, ] 1, ¥, 1 ' Ф ] ), равномерно распределённые на

отрезках \_ОС у ^ ] . По смыслу задачи концы отрезка могут быть только положительными числами. Причём, чем меньше участок дороги преподносит неожиданностей, тем меньше длина отрезка (разброс величины расстояния).

Функция распределения вероятностей случайной величины, равномерно распределённой на отрезке у \ /у ] , имеет вид:

Р (х) = Р{аа И < х}

0, х <аь-; х - аі;

_и

[1,  х >Рг].

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

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

О у (О)) распределены равномерно на отрезках  у ^ ], где 1, ] 1, ¥, 1 Ф у .

Табл. 2. Данные об отрезках распределения расстояний

І

і

1

2

 

п

і

да

 

 

1п ;Р1п ]

2

21;Р21]

да

 

[«2п 2п ]

 

 

 

 

 

п

 

 

 

да

Пусть  2 (о)  (км) - общая протяжённость кольцевого маршрута. Стохастическую постановку задачи можно свести к детерминированному случаю, если взять от целевой функции математическое ожидание:

М\2(о)] — у (о)] ■ Ху - шт.

1—1 у1

Известно, что математическое ожидание равномерно распределённой случайной величины О у (о)

вычисляется как середина

отрезка

\ О ■■, и - I, т.е. -. Введём обозначение

у    у 2

сіє/

21 = М [ 2 (ю)\.

Это позволит нам перейти от модели (7)-(9) к стохастической модели задачи коммивояжера. Благодаря тому, что известен тип распределения случайных величин, нам удастся свести стохастическую модель к детерминированной. В такой постановке, целевая функция будет иметь вид

пп   ОС-- + Р

і=1 і=і 2

х и шт,

У

(10)

при выполнении следующих ограничений

х у = 1, І = 1, п (въезд в город І ),

(11)

і=1і=1

, п (отъезд из города    ). (12)

Новая модель (10)-(12) является более адекватной, т.к. учитывает факторы случайности. Кроме того, она является аналогом задачи коммивояжёра. А это, в свою очередь, позволяет применить для нахождения кратчайшего кольцевого маршрута описанные выше методы оптимизации.

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

что к концу (І     1) -го дня на складе имеется запас в количестве     —1 единиц. Руководствуясь спросом, сделана заявка на пополнение

запаса товара объёмом Н единиц. Следовательно, запас товара на начало І -го дня будет составлять     __у + Н единиц.

Пусть потребители нуждаются в »^ единицах товара, причём этот объём был зафиксирован в договорах на поставку. Рассмотрим следующую картину развития событий.

Ситуация 1. Если + Н{ ^ »^, то потребители будут удовлетворены полностью, а остаток       = + Н{ »^

переходит на следующий "т~ 1) -й день. Пусть С грн./ед. - это стоимость хранения единицы товара за один день. Тогда издержки по хранению запаса прямо пропорциональны объёму и составляют = С(1 + Н{ »^ ).

Ситуация 2. Если же потребители не могут быть удовлетворены в полном объёме, т.е. 1 + Н{ < St, тогда по отношению к складу применяются штрафные санкции. Обозначим через к грн./ед. размер компенсации за недопоставку единицы товара за один день. Поэтому размер штрафа, который должен выплатить склад за І -й день, составит к (Si —     Н{ ) = к (х^—^ + Н{ Si ) .

Как видно, издержки склада ( грн. в І -й день зависят от запаса , его пополнения Н{ и объёма поставки Si . Очевидно, что полные издержки могут быть записаны в виде:

р( х{—1, Н, Sf) = шах (х{—1 + Н St); к (хІ—1 + Н St)}.

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90 


Похожие статьи

О В Амельницька - Система лoгicтичнoгo сервісу тpaнcнopтнo-eкcнeдицiйнoгo ніднриємства

О В Амельницька - Аналіз ефективності функціонування локальних електричних мереж в сучасних умовах

О В Амельницька - Аналіз методів оцінки соціально-економічної ефективності проектних рішень в електричних мережах