Математические методы

  • 02 окт. 2012 г.
  • 406 Слова
Отчет по практической работе №3
Определение наикратчайшего пути между вершинами ориентированного графа с циклами
Задача №1
Рассмотреть график, найти все кратчайшие пути отвершены x1 ко всем остальным вершинам.
Для решения транспортной задачи в процедуре EXCEL «Поиск решения», представим ее как транспортную задачу с промежуточными пунктами. Будем считать, что транспортныерасходы при перевозке одной единицы груза равны (в условных единицах) расстояниям между вершинами.
Так как транспортные расходы при перемещении груза из одной вершины в другую равны расстояниюмежду вершинами, то последовательность вершин, при которой транспортные расходы будут минимальными определяет наикратчайший путь, которая представлена в таблице 1.
В таблице 1 приведены расстояниямежду вершинами.
[pic]
Цифрой 100 обозначается случай когда между соответствующими вершинами нет пути.
Ввод данных. Переносим данные задачи в EXCEL. Результаты заполнения таблицы EXCELможно увидеть на рисунке 2.
[pic]
Рисунок 2- Ввод данных в EXCEL.
В ячейках B4 : I12 введены длины путей из исходных пунктов в пункты назначения.
Ячейки B15 : I23 являютсяизменяемыми ячейками для нашей процедуры.
В ячейках B24 : I24 находятся суммы значений соответствующих столбцов изменяемых ячеек.
В ячейках J15 : J23 находятся суммы значений соответствующихстолбцов изменяемых ячеек. Для обеих случаев делаем автозаполнене.
Целевая функция заносится в ячейку I3 и вычисляется по формуле «СУММПРОИЗВ (B4:G9 ; B12:G17)».
Заполнение окна процедуры«Поиск решения».
целевая функция : K3;
значение целевой функции : min;
изменяемые ячейки : B15 : I23;
ограничения задачи :
B24 : I24 = 1 и J15 : J23 = 1;
B15 : I23 [pic] 0 (ячейкидолжны иметь положительные значения).
В окне «Параметры» установить «Линейная модель», что соответствует решению задачи симплекс-методом. Результаты заполнения окна...
tracking img