Метод Форда
Постановка сетевой транспортной задачи. Составление исходной таблицы расстояний. Определение длины кратчайших путей. Краткая характеристика программы "Ford". Описание подпрограмм и процедур. Таблица идентификаторов. Примеры решения контрольных задач.
Рубрика | Экономико-математическое моделирование |
Вид | курсовая работа |
Язык | русский |
Дата добавления | 11.03.2015 |
Размер файла | 43,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Введение
В данной курсовой работе мы рассмотрим метод Форда и определим кратчайший маршрут решения задачи. Алгоритм Форда, необходим для решения сетевой транспортной задачи. Большое внимание уделим достижению конечного результата, который производится в 4 этапа. Излагаемые этапы иллюстрируются схемами и графиками. Выбранная мною эта тема, достаточно актуальная в наши дни. Этот метод интересен инженерам, экономистам и научным работникам, интересующихся применением математики к обоснованию оптимальных решений.
1. Постановка сетевой транспортной задачи
На практике часто встречается задача определения кратчайшего маршрута по заданной сети из начального пункта до конечного пункта маршрута. Транспортная сеть может быть представлена в виде графа (рис.1), дуги которого - транспортные магистрали, а узлы - пункты отправления и назначения. Графически транспортная сеть изображается в виде совокупности n пунктов P1,P2,...,Pn, причем некоторые упорядоченные пары (Pi,Pj) пунктов назначения соединены дугами заданной длинны (Pi,Pj)=lij. Некоторые или все дуги могут быть ориентированы, т.е. по ним возможно движение только в одном направлении, указанном стрелками.
На рис.1 построена ориентированная транспортная сеть, содержащая шесть пунктов P1,P2,...,P6, которые связаны между собой восьмью транспортными путями.
Необходимо определить кратчайший маршрут из пункта P1 в P6. Определение кратчайшего маршрута состоит в указании последовательности прохождения маршрута через промежуточные пункты и суммарной длинны маршрута.
Например, маршрут из пункта P1 в пункт P6: P1P2P4P6; L=l12+l24+l46=10.
Постановка задачи приобретает смысл в том случае, если имеется несколько вариантов маршрута из начального пункта в конечный. В этом случае физический смысл функции цели задачи состоит в минимизации общей длины маршрута, т.е. в определении кратчайшего пути из P1 в Pn.
2. Описание метода и алгоритма решения
Метод Форда бал разработан специально для решения сетевых транспортных задач и основан, по существу, на принципе оптимальности.
Алгоритм метода Форда содержит четыре этапа (схема 1). На первом этапе производится заполнение исходной таблицы расстояний от любого i-го пункта в любой другой j-й пункт назначения. На втором этапе определяются для каждого пункта некоторые параметры i и j по соответствующим формулам. Далее на третьем этапе определяются кратчайшие расстояния. Наконец, на четвертом этапе определяются кратчайшие маршруты из пункта отправления Р1 в любой другой пункт назначения Рj, j=1,2,...,n.
Рассмотрим подробнее каждый из этих четырех этапов.
2.1 Первый этап: Составление исходной таблицы расстояний
Данная таблица содержит n+1 строк и такое же количество столбцов; Pi - пункты отправления; Pj - пункты назначения. Во второй строке и втором столбце проставляется значения параметров i иj, определение значений которых производятся на втором этапе решения задачи. В остальных клетках таблицы проставляются значения расстояний lij из i-го пункта в j-й пункт. Причем заполняем клетки таблицы, лежащие выше главной диагонали. Если пункт Pi не соединен отрезком пути с пунктом Pj, то соответствующая клетка таблицы не заполняется.
2.2 Второй этап: Определение i и j
Определяется значение параметров в соответствии с формулой:
j=min(i+lij); i=1,2,...,n; j=1,2,...,n, (1)
где 1=0.
Эти значения заполняются во второй строке и во втором столбце.
2.3 Третий этап: Определение длины кратчайших путей
Возможны два случая определения длинны кратчайших путей из пунктов Pi в пункты Pj, i=1,2,...,n; j=1,2,...,n.
В первом случае, если выполняются неравенство:
j - i lij; lij0; j=1,2,...,n; j=1,2,...,n, (2)
то значения параметров 1,...,n удовлетворяют условиям оптимальности. Каждое значение j есть не что иное, как кратчайшее расстояние от пункта Pi до пункта Pj, j=2,3,...,n.
Во втором случае, если для некоторых клеток (i,j) таблицы имеет место неравенство:
j - i > lij; i=1,...,n; j=1,...,n, (3)
то значения j и i могут быть уменьшены.
Если справедливо (3), тогда исправим значение j0, пересчитав его по формуле:
j0=i0+li0j0. (4)
2.4 Четвертый этап: Нахождение кратчайшего пути
Определения последовательности пунктов кратчайшего маршрута. С этой целью для каждого столбца определяют величину:
lr1,j = j - r1, (5)
где lr1,j берется из таблицы, причем r1 выбирается так, чтобы выполнилось равенство (5). Таким образом определим r1. Далее продолжим ту же операцию, но будем считать, последней не Pn, а Pr1. Будем продолжать до тех пор, пока rn=1.
Таким образом, кратчайший маршрут проходит через Pr1,Pr2,...,Prn, а длинна маршрута Lmin=lr2,r1+lr3,r2+...+lrn-1,rn.
Рис. 1
3. Описание программы
Программа “FORD” написана на языке высокого уровня - Pascal, в интегрированной среде разработки “Turbo Pascal 7.0” фирмы Borland Inc.
Программа предназначена для нахождения кратчайшего пути в сетевом графе по методу Форда. Программа легка в использовании, что достигается за счет использования дружественного интерфейса и иерархического меню. Вначале программы производится ввод данных, затем нахождение кратчайшего маршрута и вычисление его длинны, далее выводится результат. Вывод результатов возможен как в файл, так и на экран.
В программе предусмотрена возможность повторного решения задачи с другими исходными данными.
4. Описание подпрограмм и процедур
4.1 Подпрограммы и функции
ТИП |
НАЗВАНИЕ |
НАЗНАЧЕНИЕ |
|
Function type : real |
min; |
Вычисляет минимальное значение вектора k[i]; |
|
Procedure |
set_graph_mode; |
Устанавливает графический режим; |
|
Procedure |
install_firewall; |
Инициализирует огонь; |
|
Procedure |
fire; |
Процедура рисования огня; |
|
Procedure |
ok; |
Выводит сообщение о корректности операции; |
|
Procedure |
notok; |
Выводит сообщение о некорректности операции; |
|
Procedure |
check_input_data; |
Проверяет корректность ввода данных; |
|
Procedure |
keybord_input; |
Ввод исходных данных с клавиатуры; |
|
Procedure |
ramka; |
Выводит рамку по краям экрана; |
|
Procedure |
save; |
Сохранение результатов в файл; |
|
Procedure |
about_program; |
Выводит информацию о программе; |
|
Procedure |
about_method; |
Выводит информацию о методе Форда; |
|
Procedure |
output_graph; |
Рисует вершины графа; |
|
Procedure |
draw_ways; |
Рисует дуги графа; |
|
Procedure |
draw_short_way; |
Рисует кратчайший маршрут; |
|
Procedure |
count_point_coord; |
Вычисляет экранные координаты вершин графа; |
|
Procedure |
set_font; |
Инициализирует шрифт пользователя; |
|
Procedure |
calculate; |
Основное математическое ядро программы; |
|
Procedure |
draw_menu; |
Открытие меню; |
|
Procedure |
redraw_menu; |
Закрытие меню; |
|
Procedure |
main_menu; |
Основной механизм меню; |
|
Procedure |
pixel; |
Ставит точку; |
|
Procedure |
stars; |
Инициализирует массив со звездами; |
|
Procedure |
welcomescreen; |
Заставка; |
4.2 Таблица идентификаторов
ИМЯ |
ТИП |
НАЗНАЧЕНИЕ |
|
Константы |
|||
menu |
array of string |
Описывает меню программы |
|
menuof |
array of byte |
Описывает меню программы |
|
menugo |
array of byte |
Описывает меню программы |
|
name1 |
string |
Имя файла входных данных |
|
name2 |
string |
Имя файла выходных данных |
|
xxx |
word |
Размер огня по х |
|
yyy |
word |
Размер огня по у |
|
xx1 |
word |
Координата х огня |
|
yy1 |
word |
Координата у огня |
|
messize |
byte |
Размер заглавия |
|
title |
array of string |
Заглавие |
|
Переменные |
|||
mas |
array of real |
Основная матрица вычислений |
|
coord_point |
array of real |
Координаты вершин графа |
|
i |
integer |
Переменная для организации цикла |
|
j |
integer |
Переменная для организации цикла |
|
t |
integer |
Используется при расчете пути |
|
m |
integer |
Счетчик кол-ва вершин в крат. Пути |
|
n |
integer |
Кол-во вершин в графе |
|
z |
integer |
Код ошибки |
|
x1 |
integer |
Исп. в процедуре вывода на экран |
|
y1 |
integer |
Исп. в процедуре вывода на экран |
|
x2 |
integer |
Исп. в процедуре вывода на экран |
|
y2 |
integer |
Исп. в процедуре вывода на экран |
|
kk |
integer |
Промежуточное значение |
|
iii |
integer |
Промежуточное значение |
|
x |
integer |
Координата х конца отрезка |
|
y |
integer |
Координата у конца отрезка |
|
lenth |
integer |
Кол-во вершин в кратчайшем маршруте |
|
chrus |
integer |
Номер шрифта пользователя |
|
z1 |
integer |
Номер графического драйверв |
|
z2 |
integer |
Номер графического режима |
|
k |
array of real |
Используется для нахождения минимума |
|
result |
array of integer |
Номера вершин, которые входят в кратчайший маршрут |
|
error_code |
array of byte |
Коды ошибок при вводе данных |
|
fire1 |
array of byte |
Хранит цвета огня |
|
fire2 |
array of byte |
Матрица промежуточных данных |
|
aa |
real |
Используется при вычислении координат вершин графа |
|
pi1 |
real |
Используется при вычислении координат вершин графа |
|
s |
real |
Хранит промежуточное значение |
|
l |
boolean |
Исп. при определении кратчайшего маршрута |
|
inputdata |
boolean |
TRUE, если данные вводились |
|
calculatedata |
boolean |
TRUE, если данные били обработаны |
|
mov |
boolean |
Используется в процедуре меню |
|
o |
string |
Используется при вводе с клавиатуры |
|
temp |
byte |
Хранит временное значение |
|
cursor |
byte |
Координаты курсора меню |
|
lastcursor |
byte |
Последние координаты курсора меню |
|
menulevel |
byte |
Уровень меню |
|
nline |
byte |
Кол-во строк в текушем уровне меню |
|
pressed |
char |
Используется при вводе с клавиатуры |
|
f1 |
text |
Файловая переменная |
|
f2 |
text |
Файловая переменная |
5. Примеры решения контрольных задач
Исходная таблица расстояний для одного из вариантов ранжированного графа:
Pi/Pj |
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
X |
5 |
3 |
||||
2 |
X |
2 |
5 |
||||
3 |
X |
7 |
7 |
||||
4 |
X |
3 |
|||||
5 |
X |
2 |
|||||
6 |
X |
транспортный задача программа ford
После обработки таблицы с заданными исходными данными, программа выдает следующие результаты: кратчайший маршрут: 1-2-4-6, длина кратчайшего маршрута: 10
Исходная таблица расстояний для одного из вариантов не ранжированного графа:
Pi/Pj |
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
X |
1 |
6 |
2 |
|||
2 |
X |
1 |
|||||
3 |
8 |
X |
|||||
4 |
2 |
X |
5 |
||||
5 |
1 |
3 |
X |
9 |
|||
6 |
X |
После обработки таблицы с заданными исходными данными, программа выдает следующие результаты:
- кратчайший маршрут: 1-5-4-2-6
- длинна кратчайшего маршрута: 8
Программа работоспособна при любых других вариантах исходных данных.
Заключение
Анализ алгоритма операций, необходимых при решении сетевой транспортной задачи методом Форда в заданной постановке подтверждает:
Достижение конечного результата производится в четыре этапа.
Каждый этап описывается простыми математическими операциями и может быть записан на одном из языков программирования.
Составлена программа на алгоритмическом языке высокого уровня “Pascal”, позволяющая решать задачу в диалоговом режиме, удобном для пользователя не программиста.
Алгоритм решения транспортной задачи методом Форда является универсальным, что позволяет производить расчёты как с ранжированными, так и с не ранжированными графами. Возможность реализаций для удобства работы пользователя в программе сервисной части.
Возможность неоднократного решения задачи методом Форда при различных исходных данных.
Список используемой литературы
1. Вентцель Е.С. «Исследование операций» М.: Сов. Радио 1972 г.
2. Захаров В.Н. «Алгоритмические методы решения задач оптимального планирования и управления» ВАД. 1986 г.
3. Зубов В.С. «Программирование на языке Turbo Pascal» М.: Филин 1997 г.
Размещено на Allbest.ru
Подобные документы
Основные подходы и способы решения транспортной задачи, ее постановка и методы нахождения первоначального опорного решения. Математическая модель транспортной задачи и алгоритм ее решения методом потенциалов. Составление опорного плана перевозок.
курсовая работа [251,0 K], добавлен 03.07.2012Главные элементы сетевой модели. Задача линейного программирования. Решение симплекс-методом. Составление отчетов по результатам, по пределам, по устойчивости. Составление первоначального плана решения транспортной задачи по методу северо-западного угла.
контрольная работа [747,3 K], добавлен 18.05.2015Постановка, анализ, графическое решение задач линейной оптимизации, симплекс-метод, двойственность в линейной оптимизации. Постановка транспортной задачи, свойства и нахождение опорного решения. Условная оптимизация при ограничениях–равенствах.
методичка [2,5 M], добавлен 11.07.2010Применение линейного программирования для решения транспортной задачи. Свойство системы ограничений, опорное решение задачи. Методы построения начального опорного решения. Распределительный метод, алгоритм решения транспортной задачи методом потенциалов.
реферат [4,1 M], добавлен 09.03.2011Расчёт кратчайших расстояний и кратчайших путей следования. Маршрутизация перевозок мелкопартийных грузов. Определение потребности в транспортных средствах для работы на маршрутах. Сравнительный анализ существующего и предлагаемого вариантов маршрутов.
дипломная работа [350,8 K], добавлен 24.01.2016Математическая постановка и алгоритм решения транспортной задачи. Сбалансированность и опорное решение задачи. Методы потенциалов и северо-западного угла. Блок-схема. Формы входной и выходной информации. Инструкция для пользователя и программиста.
курсовая работа [113,8 K], добавлен 10.11.2008Основные методы решения задач линейного программирования. Графический метод, симплекс-метод. Двойственная задача, метод потенциалов. Моделирование и особенности решения транспортной задачи методом потенциалов с использованием возможностей Мicrosoft Excel.
контрольная работа [1,1 M], добавлен 14.03.2014Формулировка проблемы в практической области. Построение моделей и особенности экономико-математической модели транспортной задачи. Задачи линейного программирования. Анализ постановки задач и обоснования метода решения. Реализация алгоритма программы.
курсовая работа [56,9 K], добавлен 04.05.2011Использование симплексного метода решения задач линейного программирования для расчета суточного объема производства продукции. Проверка плана на оптимальность. Пересчет симплексной таблицы методом Жордана-Гаусса. Составление модели транспортной задачи.
контрольная работа [613,3 K], добавлен 18.02.2014Общая постановка задачи линейного программирования (ЛП). Приведение задачи ЛП к стандартной форме. Примеры экономических задач, приводящихся к задачам ЛП. Геометрический и симплексный методы решения. Теоремы двойственности и их использование в задачах ЛП.
курсовая работа [1,1 M], добавлен 21.11.2010