Как составить план перевозки?

Рефераты, курсовые, дипломные, контрольные (предпросмотр)

Тип: Курсовая работа. Файл: Word (.doc) в архиве zip. Категория: Математика
Адрес этого реферата http://referat-kursovaya.repetitor.info/?essayId=20184 или
Загрузить
В режиме предпросмотра не отображаются таблицы, графики и иллюстрации. Для получения полной версии нажмите кнопку «Загрузить». Рефераты, контрольные, дипломные, курсовые работы предоставляются в ознакомительных целях, не для плагиата.
Страница 2 из 2 [Всего 2 записей]« 1 2

3. Определим недостающие индексы V j. В нашем примере это индексы

V 5, V 6 и V 8. Для этого в каждом столбце, соответсвующем неизвестному индексу V j, просмотрим заполненные клетки и вычислим недостающие индексы по формуле V j = U i + L ij, если для них известны индексы U i.

Для столбца, соответствующего индексу V 5, этими элементами будут L 4, 5 = 16 и L 7, 5 = 25. Значения U 4 и U 7 известны: U 4 = 10, U 7 = 12.

Следовательно,

V 5 = min(U 4 + L 4, 5 = 10 + 16 = 26; U 7 + L 7, 5 = 12 + 25 = 37) = 26.

Для столбца, соответствующего индексу V 6, ими будут L 2, 6 = 7, L 3, 6 = 17, L 7, 6 = 18. Значения индексов U 2, U 3, U 7 известны: U 2 = 8, U 3 = 10, U 7 = 12. Следовательно,

V 6 = min(U 2 + L 2, 6 = 8 + 7 = 15; U 3 + L 3, 6 = 10 + 17 = 27;

U 7 + L 7, 6 = 12 + 18 = 30) = 15.

Для столбца, соответствующего индексу V 8, ими будут L 5, 8 = 17, L 6, 8 = 13, L 7, 8 = 19. Значения индексов U 5, U 6, U 7 известны: U 5 = 26, U 6 = 15, U 7 = 12. Следовательно,

V 8 = min(U 5 + L 5, 8 = 26 + 17 = 43; U 6 + L 6, 8 = 15 + 13 = 28;

U 7 + L 7, 8 = 12 + 19 = 31) = 28.

Запишем их в строку V i (смотрите таблицу ниже).

4. Все индексы найдены. Проверим полученное решение на

оптимальность, т. е. выполнение условия L ij = V j - U i для каждой заполненной клетки матрицы.

Для всех заполненных клеток условие L ij = V j - U i соблюдается. Полученное решение является оптимальным. Следовательно, минимальными расстояниями от вершины 1 до всех остальных будут:

V 2 = 8, V 3 = 10, V 4 = 10, V 5 = 26, V 6 = 15, V 7 = 12, V 8 = 28.

Определим кратчайший путь от вершины 1 до вершины 5. Для этого в столбце 5 найдём элемент, значение которого равно разности индексов столбца и строки L ij = V j - U i :

L 4, 5 = V 5 - U 4 = 26 - 10.

L 4, 5 - последнее звено пути и, соответственно, вершина 4 - предпоследняя.

И далее, в столбце 4 определим:

L 1, 4 = V 4 - U 1 = 10 - 0 = 10.

L 1, 4 - первое звено пути, так как вершина 1 является начальной фиксированной.

Таким образом, имеем минимальный путь от вершины 1 до вершины 5, проходящий через вершины 1, 4, 5, длина которого равна 26.

RSSСтраница 2 из 2 [Всего 2 записей]« 1 2


При любом использовании материалов сайта обязательна гиперссылка на сайт «Репетитор».
Разработка и Дизайн компании Awelan
www.megastock.ru
Проверить аттестат