Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

Таблица 4. Локальные стоимости перевозок.

|Ребро (ЕiЕj) |Расстояние,км |Стоимость перевозки, |
| | |долл/м3 |
|Е1-Е9 |15 |3,04 |
|Е9-Е10 |15 |3,04 |
|Е9-Е11 |10 |2,24 |
|Е2-Е5 |11 |2,40 |
|Е5-Е6 |6 |1,60 |
|Е6-Е10 |20 |3,71 |
|Е6-Е9 |13 |2,72 |
|Е9-Е11 |10 |2,24 |
|Е3-Е4 |14 |2,88 |
|Е4-Е8 |12 |2,56 |
|Е8-Е9 |19 |3,59 |
|Е9-Е10 |15 |3,04 |
|Е4-Е11 |11 |2,40 |

2.2. Определение кратчайшего расстояния в транспортной сети

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

Задача решается составлением минимального дерева-остова.

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

Расчет кратчайшего пути производится по формуле:

Uj=(Ui+Lij), где Uj - кратчайшее расстояние до текущего пункта j,км;

Ui - кратчайшее расстояние до предыдущего пункта i,км;

Lij - расстояние между i и j пунктами,км.

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

Ниже, в таблице 5, представлены эти маршруты с указанием промежуточных пунктов, через которые они проходят, и общей длины маршрута.

Таблица 5. Кратчайшие маршруты в транспортной сети
|Маршрут |Промежуточные |Стоимость перевозки 1м3 |Длина |
| |пункты |песка по маршруту, тыс. |мар-шрута, |
| | |руб. |км |
|Е1Е10 |Е1-Е9-Е10 |4,74 |30 |
|Е1Е11 |Е1-Е9-Е11 |4,09 |25 |
|Е2Е10 |Е2-Е5-Е6-Е10 |6,02 |37 |
|Е2Е11 |Е2-Е5-Е6-Е9-Е11|6,02 |40 |
|Е3Е10 | |7,81 |60 |
| |Е3-Е4-Е8-Е9-Е10| | |
|Е3Е11 |Е3-Е4-Е11 |4,09 |25 |

[pic]

Схема 2.Графическое изображение найденных кратчайших путей в сети

2.3. Решение задачи прикрепления пунктов производства к пунктам потребления (транспортная задача)

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

Исходные данные для решения транспортной задачи представляют собой матрицу. В клетках этой матрицы сверху указаны стоимости (Cij) перевозки 1 м3 груза из i-го пункта отправления в j-й пункт назначения, а в нижней части клеток будут показаны объёмы перевозок по этому маршруту (Xij).

Целевая функция транспортной задачи заключается в минимизации общей стоимости всех перевозок:

F =[pic] ( min

Ход решения задачи:

1. Приводим исходную матрицу (вычитаем из Сij каждой строки минимальное значение Сij в этой строке; затем для столбцов, в которых нет ни одного нуля, из каждого Сij в столбце вычитаем минимальное Сij).

2. Проводим первичное распределение потока ресурсов по клеткам с нулевой стоимостью и закрываем столбцы и строки.

3. Поскольку распределение оказалось неоптимальным, т.е. не все столбцы оказались закрытыми, проводим преобразование: выбираем минимальное

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

Рекомендуем скачать другие рефераты по теме: рефераты баллы, реферат стиль, сочинения по литературе.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата