1) Каждой дуге присваивается только одно значение рассматриваемых критерий.
2) Каждому промежуточному пункту соответствуют одно или несколько значений, определяемых как сумма длин дуг.
3) Сетевой график не требует расчета раннего и позднего срока начала работы.
4) График используется для сравнения полученных характеристик схем доставки с заданными условиями.
В качестве критериев используют время транспортировки Т, стоимость С, приведенная стоимость
С' = (Сгруз+Ст)(1+Д)n,
где Сгруз = 45000 - закупочная стоимость товара; Ст - стоимость перевозки; (1+Д)n - множитель наращивания по годовой процентной ставке Д = 25.
Рисунок 2.1 - Принципиальная схема сетевого графика
Таблица 2.1 - Исходные данные о маршрутах
|
Номер маршрута |
Характеристика маршрута |
Вид транспорта |
|
|
1 |
Хельсинки - Москва |
Автомобильный |
|
|
2 |
Хельсинки - Москва |
Ж/д + Автомобильный |
|
|
3 |
Через порт Санкт-Петербург |
Морской + Автомобильный |
|
|
4 |
Через порт Санкт-Петербург |
Морской + ж/д+Автомобильный |
Построим схему движения с учетом всех операций, которые будут выполнены при перевозке.
Таблица 2.2 Перечень элементарных работ комплекса
|
№ |
Характеристика работы |
Время, дн. |
Стоимость, у.д.е. |
|
|
1-2 |
Затаможивание груза в Хельсинки |
1 |
189 |
|
|
2-3 |
Оформление документов и погрузка на автомобильный транспорт |
1 |
688 |
|
|
2-4 |
Оформление документов и погрузка на железную дорогу |
3 |
60 |
|
|
2-5 |
Оформление документов и погрузка на судно в п. Хельсинки |
2 |
255 |
|
|
5-6 |
Доставка морским транспортом до п. Санкт-Петербург |
2 |
553 |
|
|
6-7 |
Разгрузка в п. Санкт-Петербург |
1 |
91 |
|
|
7-8 |
Выпуск контейнера из п. Санкт-Петербург собственными силами с таможенной гарантией |
3 |
59 |
|
|
7-9 |
Выпуск контейнера из п. Санкт-Петербург экспедитором |
1 |
314 |
|
|
7-10 |
Выпуск контейнера из п. Санкт-Петербург под гарантию таможенного перевозчика |
2 |
- |
|
|
7-11 |
Выпуск груза из п. Санкт-Петербург на железную дорогу |
4 |
53 |
|
|
9-12 8-12 |
Доставка автомобильным транспортом до Москвы (СВХ) |
1,5 |
688 |
|
|
10-12 |
Доставка таможенным перевозчиком автомобильного транспорта до Москвы (СВХ) |
1,5 |
837 |
|
|
11-12 |
Доставка железной дорогой из Санкт-Петербурга в Москву (СВХ) |
4 |
366 |
|
|
3-12 |
Доставка автомобильным транспортом из Хельсинки до Москвы (СВХ) |
4 |
1380 |
|
|
4-12 |
Доставка железной дорогой из Хельсинки до Москвы (СВХ) |
7 |
330 |
|
|
12-13 |
Таможенная очистка груза в Москве собственными силами |
4 |
183 |
|
|
12-14 |
Таможенная очистка груза в Москве таможенным брокером |
1,5 |
341 |
|
|
14-15 13-15 |
Доставка по Москве автомобильным транспортом от СВХ до терминала грузополучателя |
0,5 |
41 |
Рисунок 2.2 Схемы маршрутов
Таблица 2.2 Варианты возможных маршрутов
|
№ |
Схема доставки |
Значения показателей |
|||
|
Т |
С |
С' |
|||
|
1(1) |
1-2-3-12-13-15 |
10,5 |
2481 |
52146,43 |
|
|
1(2) |
1-2-3-12-14-15 |
8 |
2639 |
51165,33 |
|
|
2(3) |
1-2-4-12-13-15 |
15,5 |
803 |
52599,53 |
|
|
2(4) |
1-2-4-12-14-15 |
13 |
961 |
51565,63 |
|
|
3(5) |
1-2-5-6-7-8-12-13-15 |
15 |
2059 |
53801,24 |
|
|
3(6) |
1-2-5-6-7-8-12-14-15 |
12,5 |
2217 |
52790,57 |
|
|
3(7) |
1-2-5-6-7-9-12-13-15 |
13 |
2314 |
53135,65 |
|
|
3(8) |
1-2-5-6-7-9-12-14-15 |
10,5 |
2472 |
52136,54 |
|
|
3(9) |
1-2-5-6-7-10-12-13-15 |
14 |
2149 |
53425,11 |
|
|
3(10) |
1-2-5-6-7-10-12-14-15 |
11,5 |
2307 |
52421,18 |
|
|
4(11) |
1-2-5-6-7-11-12-13-15 |
18,5 |
1731 |
55121,74 |
|
|
4(12) |
1-2-5-6-7-11-12-14-15 |
16 |
1889 |
54087,54 |
Для принятия решения в случае неопределенности: расчеты не дают однозначного определения по выбору, т. е. нет минимального значения в только одном варианте и вес критериев выбора неизвестен. Такая ситуация носит название - Принятие решения в условии неопределенности. В этом случае принято использовать критерии:
1) Лапласа
2) Вальда
3) Сэвиджа
4) Гурвица
Для принятия решения создается матрица возможных результатов. В данной матрице строки соответствуют возможным действиям, столбцы возможным состояниям природы. Под состоянием природы понимают критерий доставки. Каждый отдельный элемент матрицы показывает результат при выборе j-действия и реализации i-состояния.
Для составления матрицы полученные результаты представим в относительных единицах. Самый простой - соотношение текущего к минимальному.
1) Критерий Лапласа.
Он основан на предположении, что каждый вариант развития ситуации (состояния "природы") равновероятен. Поэтому, для принятия решения, необходимо рассчитать функцию Fi для каждой альтернативы, равную среднеарифметическому показателей по каждому "состоянию природы":
Выбирается та альтернатива, для которой функция минимальна.
2) Критерий Вальда.
Данный критерий основывается на принципе максимального пессимизма, то есть на предположении, что скорее всего произойдет наиболее худший вариант развития ситуации и риск наихудшего варианта нужно свести к минимуму. Для применения критерия нужно для каждой альтернативы выбрать наилучший показатель ai и выбрать ту альтернативу, для которой этот показатель минимальный.
3) Критерий Сэвиджа.
Он основан на принципе минимизации потерь, связанных с тем, что ЛПР принял не оптимальное решение. Для решения задачи составляется матрица потерь, которая называется матрицей рисков rij, которая получается из матрицы выигрышей a ij путем вычитания из текущего элемента каждого столбца наименьшего элемента каждого столбца. Далее, для каждой альтернативы определяем величины bi, равные максимальную (наименьшее число в каждой строке матрицы) и выбирают минимальную альтернативу.
5) Критерий Гурвица.
Это самый универсальный критерий, который позволяет управлять степенью "оптимизма - пессимизма" ЛПР. Введем некоторый коэффициент a, который назовем коэффициентом доверия или коэффициентом оптимизма. Этот коэффициент можно интерпретировать как вероятность, с которой произойдет наилучший для ЛПР исход. Исходя из этого, наихудший вариант можно ожидать с вероятностью (1-б). Коэффициент доверия a показывает, насколько ЛПР может управлять ситуацией и в той или иной степени рассчитывает на благоприятный для него исход. Если вероятности благоприятной и неблагоприятной ситуации для ЛПР равны, то следует принять б=0,5. Для реализации критерия определяются наилучшие a+i и наихудшие a-i значение каждой альтернативе по формуле:
Для выбора в условиях неопределённости, удобно составить таблицу 2.3.
Таблица 2.3 Выбор в условиях непределенности
|
№ маршрута |
Относительное значение параметра |
Критерии |
||||||
|
Т |
С |
С' |
Лапласа |
Вальда |
Сэвиджа |
Гурвица |
||
|
1 |
1,3125 |
3,089 |
1,091 |
1,8069 |
3,089 |
2,089 |
2,0540 |
|
|
2 |
1 |
3,286 |
1 |
1,7620 |
3,286 |
2,286 |
2,143 |
|
|
3 |
1,9375 |
1 |
1,0280 |
3,9655 |
1,9375 |
0,9375 |
1,4827 |
|
|
4 |
1,625 |
1,1968 |
1,0078 |
1,2765 |
1,6250 |
0,6250 |
1,3164 |
|
|
5 |
1,875 |
2,5641 |
1,0515 |
1,8302 |
2,5640 |
1,5641 |
1,8078 |
|
|
6 |
1,5625 |
2,7609 |
1,0318 |
1,7851 |
2,7609 |
1,7609 |
1,8963 |
|
|
7 |
1,625 |
2,8817 |
1,0385 |
1,8484 |
2,8817 |
1,8817 |
1,9601 |
|
|
8 |
1,3125 |
3,0784 |
1,0190 |
1,8033 |
3,0784 |
2,0784 |
2,0487 |
|
|
9 |
1,75 |
2,6762 |
1,0442 |
1,8235 |
2,6762 |
1,6762 |
1,8602 |
|
|
10 |
1,4375 |
2,8730 |
1,0245 |
1,7783 |
2,8730 |
1,8730 |
1,9487 |
|
|
11 |
2,3125 |
2,1557 |
1,0773 |
1,8485 |
2,3125 |
1,3125 |
1,6165 |
|
|
12 |
2 |
2,3524 |
1,0571 |
1,8032 |
2,3524 |
1,3524 |
1,7047 |
|
|
Min значение |
1,2765 |
1,6250 |
0,6250 |
1,3146 |
Вывод: Наилучший маршрут по критериям Лапласа, Вальда, Сэвиджа, Гурвица является №2(4): 1-2-4-12-14-15 - от Хельсинки до Москвы железной дорогой, по Москве - автотранспортом.
3. Маршрутизация грузов автотранспортом
Задача 4
Для рационализации движения автотранспорта при обслуживании клиентов будет использован метод линейного программирования, в частности, транспортная задача. Под термином транспортная задача подразумевается широкий круг задач не только транспортного характера, общим для них является распределение ресурсов, которые есть у m-поставщиков по n-потребителям.
Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления n-пунктов назначения. При этом в качестве критерия эффективности могут выступать критерий стоимости, времени, пробега совместно критерий ограничения стоимости и пробега. Условия транспортной задачи записывается в виде матрицы, в которой потребители однородного груза по столбцам. В последнем столбце указывается запас грузов у поставщиков в последней строке потребность потребителей.
Последовательность решений:
1. Составляется первоначальный план
2. Рассчитывается потенциалы
3. Проверяется на оптимальность
Экономико-математическая формулировка задачи: У нас имеется m пунктов отправления, объем отправления по каждому a1, a2, …am. Есть n пунктов потребления с потребностью b1, b2, …bn. Задана матрица критериев ограничений по каждому варианту Сij. Необходимо рассчитать оптимальный план перевозки с минимальными транспортными издержками.
Таблица 3.1 - Матрица критериев ограничений по каждому варианту Сij.
|
B1 |
B2 |
B3 |
Запас |
||
|
A1 |
X11 C11 |
X12 C12 |
X13 C13 |
a1 |
|
|
A2 |
X21 C21 |
X22 C22 |
X23 C23 |
a2 |
|
|
A3 |
X31 C31 |
X32 C32 |
X33 C33 |
a3 |
|
|
Потребность |
b1 |
b2 |
b3 |
Транспортная задача может быть решена только в том случае, когда размер поставок равен размеру потребления:
(3.1)
Ограничения:
· все грузы из i-пунктов отправления должны быть отправлены:
, ; (3.2)
· все j-потребители должны быть обеспечены грузом:
, ; (3.3)
· суммарный объем отправления должен быть равен суммарному полученному объему:
; (3.4)
· должны выполняться условие неотрицательности поставки:
; (3.5)
· перевозки необходимо осуществлять с минимальными транспортными издержками:
. (3.6)
В том случае, когда модель является незакрытой, ее необходимо привести к закрытой форме. Если потребность по пунктам отправления превышает запасы пунктов отправления, то вводится фиктивный поставщик с недостающим объемом отправления. Если запасы поставщика больше потребления, как в моём случае, то вводится фиктивный потребитель.
Таблица 3.1 - Характеристика обслуживаемых клиентов
|
Потребители |
Координаты, км |
Погрузка |
Выгрузка |
||
|
Конт/сут |
|||||
|
X |
Y |
||||
|
1 |
12 |
5 |
8 |
5 |
|
|
2 |
6 |
20 |
1 |
7 |
|
|
3 |
15 |
6 |
4 |
8 |
|
|
4 |
19 |
6 |
9 |
7 |
|
|
5 |
6 |
15 |
10 |
16 |
|
|
6 |
12 |
10 |
19 |
6 |
|
|
7 |
10 |
6 |
14 |
8 |
|
|
8 |
15 |
14 |
10 |
13 |
Фиктивные поставщик и потребитель являются контейнерным терминалом с координатами (0;0), получатели груза в контейнерах являются поставщиками порожних контейнеров.
По координатам построим зоны потребителей.
Рисунок 3.1 - Координаты потребителей
Занесем исходные данные в распределительную таблицу.
Таблица 3.2 - Распределительная таблица
1. Используя метод северо-западного угла, построим опорный план транспортной задачи.
Таблица 3.3 - Опорный план транспортной задачи
2. Используя программу, решим задачу методом потенциалов.
Таблица 3.4 - Решение задачи методом потенциалов
3. Произведем расчет экономической эффективности.