Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.abitu.ru/en2002/closed/viewwork.html?thesises=263 Дата изменения: Fri May 5 15:24:55 2006 Дата индексирования: Tue Oct 2 03:57:44 2012 Кодировка: koi8-r Поисковые слова: trees

Одной из стандартных задач линейного программирования является так
называемая задача о перевозках - или транспортная задача. Однако она
является уже канонической в своей изначальной постановке.
Эта задача является исторически одной из первых, для решения которой
использовалось линейное программирование. В зависимости от выбранного
критерия эффективности различают транспортные задачи по пробегу, по
стоимости, по времени, совместно по критериям пробега и стоимости, с
ограничениями по пропускной способности дорог и транспорта, задачи в
сетевой постановке и др. Эта задача имеет значение тогда, когда время не
является определяющим фактором при организации перевозок.
Рассмотрим транспортную задачу как классическую задачу не линейного
программирования, а как чисто информационную. Можно рассмотреть различные
варианты одной задачи.
Пусть имеется n городов, пронумерованных числами от 1 до n. Для каждой
пары городов с номерами i, j в таблице a[i][j] хранится целое число -
цена прямого билета из города i в город j. Считается, что рейсы существуют
между любыми городами, a[i,i] = 0 при всех i, a[i][j] может отличаться от
a[j,i]. Наименьшей стоимостью проезда из i в j считается минимально
возможная сумма цен билетов для маршрутов (в том числе с пересадками),
ведущих из i в j. Для решения задачи в такой постановке используются
алгоритм динамического программирования, или алгоритм Форда - Беллмана,
алгоритм Флойда и алгоритм Дейкстры.
При решении подобных задач возникает такой вопрос. Число реальных рейсов
может быть существенно меньше n*n, поэтому интересны алгоритмы, которые
работают эффективно в такой ситуации. Исходные данные естественно
представлять тогда в такой форме: для каждого города известно число
выходящих из него рейсов, их пункты назначения и цены. Приведем условие
рассматриваемой нами задачи с дополнительными условиями.
Имеется некоторое конечное число городов, которые связаны транспортной
сетью, состоящей из авиа, железнодорожных, автомобильных и водных рейсов
произвольного направления и включающих произвольное число городов.
Стоимость проезда различна по классам. Рейсы отправляются по недельному
расписанию. При пересадки между рейсами должно быть не менее 2-х часов. По
заданным начальному и конечному городам, дате желаемого отправления,
максимальному времени пути и максимальной стоимости и максимальному числу
пересадок выдать все возможные маршруты, так, чтобы маршруты с меньшей
датой и временем прибытия отображались раньше, чем с большим.
Транспортная схема представляет собой направленный взвешенный
мультиграф. Каждая дуга характеризуется принадлежностью к рейсу, временем
пути, ценой каждого из классов, временем отправления.
Входными данными является:
a) Транспортная система. (города и все рейсы)
b) Начальный, конечный город, ориентировочная дата и время
отправления, максимальное время пути максимальная цена, максимальное
количество пересадок.
Результатом работы программы является конечное множество маршрутов.
Два маршрута мы будем считать различными, если они отличаются хотя бы одним
городом следования или хотя бы одним рейсом. После того, как найдены все
маршруты они сортируются по времени прибытия.
Метод решения - метод последовательных испытаний. Поиск решений
осуществляется рекурсивно, причем максимальная глубина рекурсии будет равна
максимальному количеству пересадок. Так как мы имеем ограничения по
некоторым параметрам то мы можем отсечь заведомо ошибочную ветвь поиска
решений, сделав проверку на превышение параметров. Далее, т.к. транспортная
система включает в себя достаточно большой объем информации, в целях
доступа к большему объему памяти, также в целях более рационального
использования памяти и по причине недопустимости использования статических
объектов в некоторых случаях, в программе для внутреннего представления
широко используются динамические объекты. Для объединения большого
количества данных в одном объекте, а также для реализации динамических
объектов используется комбинированный тип (запись).
Реализация алгоритма выполнена на языке Паскаль.

ЛИТЕРАТУРА

1. Бешенков С.А., Гейн А.Г., Григорьев С.Г. "Информатика и информационные
технологии", УГПУ, Екатеринбург, 1995
2. Горстко А.Б., Чердынцева М.И. "Информатика для школьников и всех-всех-
всех", Ростов-на-Дону, "Феникс", 1996
3. Зайцева В.П., "Вычислительный эксперимент на уроке":В сб. "Информатика-
97", Мурманск, 1997
4. Зайцева В.П., Паялов А.В., "В помощь учителю. Задачи по теме
моделирование", Мурманск, !999
5. Лапчик М.П., "Вычисления. Алгоритмизация. Программирование.", М.,
"Просвещение", 1988
6. Лурье М.А., Александров Б.И., "Задачи на составление уравнений", М.,
"Наука", 1976
7. Пак Н.И., "Компьютерное моделирование", TV-info, 1996