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

Министерство образования Российской Федерации Государственное образовательное учреждение высшего профессионального образования

СЕВЕРО-ЗАПАДНЫЙ ГОСУДАРСТВЕННЫЙ ЗАОЧНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра автомобильного транспорта

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ НА АВТОМОБИЛЬНОМ ТРАНСПОРТЕ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ НА ТРАНСПОРТЕ Рабочая программа Задание на контрольные работы и курсовую работу Факультет экономики и управления на автомобильном транспорте Направления и специальности подготовки дипломированного специалиста:

653300 – эксплуатация наземного транспорта и транспортного оборудования 150200 - автомобили и автомобильное хозяйство 653400 – организация перевозок и управление на транспорте 240100.01 – организация перевозок и управление на транспорте (Автомобильный транспорт) Специализации: 150201- техническая эксплуатация автомобилей 240101.01-организация перевозок Направление подготовки бакалавра 551400 – наземные транспортные системы

Санкт-Петербург 2004

Утверждено редакционно-издательским советом университета УДК 629.113:65.011.56 (07) Информационные технологии на автомобильном транспорте. Информационные технологии на транспорте: Рабочая программа, задания на контрольные работы и курсовую работу. - СПб.: СЗТУ, 2004.- 23 с. Рабочая программа разработана в соответствии с государственными образовательными стандартами высшего профессионального образования по направлениям подготовки дипломированных специалистов 653300 (специальность 150200 – «Автомобили и автомобильное хозяйство», специализация 150201 – «Техническая эксплуатация автомобилей»), 653400 (специальность 240100.01 – «Организация перевозок и управление на транспорте», специализация 240101.01 – «Организация перевозок») и направлению подготовки бакалавра 551400 – «Наземные транспортные системы». Методический сборник содержит рабочую программу, тематический план лекций, перечень основной и дополнительной литературы, задание на контрольные работы и курсовую работу и методические указания к их выполнению. В рабочей программе изложены вопросы, описывающие основы современных средств подвижной связи, систем управления, проектирования и использования баз данных, компьютерных сетей и телекоммуникаций, автоматизированных систем планирования и управления перевозками и математическим методам решения автотранспортных задач. Рассмотрено и утверждено на заседании кафедры автомобильного транспорта СЗТУ февраля 2004 г., протокол № , утверждено методической комиссией факультета экономики и управления на автомобильном транспорте февраля 2004 г., протокол № . Рецензенты: кафедра автомобильного транспорта (зав. кафедрой А.Б. Егоров, канд. тех. наук, доц.), Ю.А. Кудряшов, канд. экон. наук, проф., академик международной академии информатизации, генеральный директор АООТ «Сервис – фирма «АРДИС». Составители: В.И. Костенко, канд. тех. наук, доц., Т.К. Екшикеев, канд. экон. наук, доц. © Северо-Западный государственный заочный технический университет, 2004

Предисловие Дисциплины «Информационные технологии на автомобильном транспорте» и «Информационные технологии на транспорте» знакомят студентов со связью и ее ролью в организации транспортного обслуживания, информационным обеспечением транспортного процесса, назначением и видом систем и средств связи на транспорте, их характеристиками, сферами применения различных систем связи на транспорте, а также с информационными потоками в транспортных системах, их взаимосвязью с глобальной системой передачи, хранения и обработки информации. В курсе дисциплины предусмотрено изучение основ автоматизированных систем управления автомобильным транспортом (АСУ), предназначенной для оптимизации процессов управления в транспортных системах. Рассматриваются структура и уровни построения АСУ на транспорте, их функции, алгоритмы эффективного принятия оперативных решений, техническое и информационное обеспечение АСУ, системы управления. Студенты знакомятся с основами передачи данных, а также с понятием о базах и банках данных. Целью преподавания курсов дисциплин «Информационные технологии на автомобильном транспорте» и «Информационные технологии на транспорте» для студентов указанных специальностей является формирование системы научных и профессиональных знаний и навыков в области управления автомобильным транспортом. Основными задачами изучения дисциплины являются: -формирование у студентов научного мышления, умения применять его на практике, понимания социальной и гуманитарной направленности информационных систем; -овладение программно-целевыми методами системного анализа и прогнозирования информационных потоков; -создание у студентов основ теоретической подготовки в области управления АТП; -выработка у студентов приемов и навыков в решении инженерных задач связанных с управлением и интенсификацией производства, экономических проблем. Дисциплины «Информационные технологии на автомобильном транспорте» и «Информационные технологии на транспорте» изучаются посредством чтения лекций и самостоятельной работы над учебной и научнотехнической литературой. Все разделы изучаемой дисциплины получают практическое закрепление знаний в процессе лабораторно-практических занятий, контрольных работ и курсовой работы.

В результате изучения дисциплины будущий инженер должен знать: -роль связи в организации транспортного обслуживания; -назначение и виды систем и средств связи на транспорте; -сферы применения различных систем связи на транспорте; -алгоритмы эффективного принятия оперативных решений; -АСУ на транспорте; -взаимосвязь глобальной системы передачи, хранения и обработки информации с информационными потоками в транспортных системах. В курсе изучения дисциплин предусмотрено выполнение двух контрольных работ для студентов специальности 150200 и курсовой работы для студентов специальности 240100.01.

1.1.

1. Содержание дисциплины Содержание дисциплины по ГОС

Связь и ее роль в организации транспортного обслуживания; информационное обеспечение транспортного процесса; назначение и виды систем и средств связи на транспорте, их характеристики; сферы применения различных систем связи на транспорте; информационные потоки в транспортных системах, их взаимосвязь с глобальной системой передачи, хранения и обработки информации; АСУ как инструмент оптимизации процессов управления в транспортных системах; структура и уровни построения АСУ на транспорте, их функции; алгоритмы эффективного принятия оперативных решений; техническое и информационное обеспечение АСУ; основы передачи данных; понятие о базах и банках данных; АСУ взаимодействием различных видов транспорта. 1.2. Рабочая программа (объем дисциплины 140 ч. для специальности 150200 и 186 ч. для специальности 240100 Введение [3], с. 12…22 Информационная технология. Системный подход к решению задач автоматизации и управления на транспорте. Основные положения, определения и понятия. Применение АСУ на транспорте. 1.2.1. Назначение и виды систем и средств связи на транспорте, их характеристики. [1], с. 18…76, 95…186; [6], с. 55…154

Технология подвижной связи. Типы подвижной связи. Принципы построения сетей сотовой связи. Алгоритмы функционирования систем сотовой связи. Системы подвижной связи. Пейджинговые сети. Аналоговые системы подвижной сотовой связи. Цифровые системы сотовой связи. Структура и типы систем спутниковой связи. Действующие системы спутниковой связи Глобалстар. Инмарсат. 1.2.2. Сферы применения различных систем связи на транспорте. [3], с. 119…130 Связь и ее роль в организации транспортного обслуживания (на примере системы Евтелтракс). Назначение и область использования систем определения местоположения (ОМП) и связи. Технологические принципы реализации ОМП в локальных и зональных АСУ АТП. 1.2.3. Понятие о базах и банках данных как о информационном обеспечении АСУ [ 7 ], с. 36…92; [ 8 ] Системы управления базами данных. Базы и банки данных. Основные положения. Основные функции СУБД. Реляционная модель БД. Языки баз данных. Основы проектирования баз данных. 1.2.4. Компьютерные сети и телекоммуникации как техническое обеспечение АСУ [ 2 ], с. 58…97; [ 5 ], с. 148…218 Типы локальных сетей. Локальные и территориально-распределенные вычислительные сети. Базовые сетевые топологии. Сетевые технические и программные средства. Основы передачи информации. 1.2.5. Информационные потоки в транспортных системах, их взаимосвязь с глобальной системой передачи, хранения и обработки информации. [ 3 ], с. 167…188 Защита информации в автоматизированных системах обработки данных. Информационное обеспечение транспортного процесса. Протокол. Эталонная модель взаимодействия открытых систем. Использование Интернета при

организации перевозок. Внутрифирменные информационные системы. Взаимодействие с глобальными информационными сетями. Организация информационного взаимодействия субъектов рынка автоперевозок с использованием Intranet-технологий. 1.2.6. АСУ как инструмент оптимизации процессов управления в транспортных системах [ 3 ], с. 145…166, 207…220 Структура и уровни построения АСУ на транспорте, их функции. Состав и задачи системы автоматизированного диспетчерского управления перевозками. Задачи оперативного управления работой подвижного состава на маршрутах. Оперативное управление пассажирскими перевозками. АСУ взаимодействия различных видов транспорта. Автоматизированная система оперативного управления ТО и ТР подвижного состава. Автоматизированная система технико-экономического планирования и учета. Проектирование и внедрение АСУ. Перспективы развития АСУ на автомобильном транспорте. 1.2.7. Алгоритмы эффективного принятия оперативных решений [ 4 ], с. 15…80 Математические методы решения автотранспортных задач. Роль математических методов при решении автотранспортных задач. Решение транспортной задачи методом линейного программирования. Решение транспортной задачи методом потенциалов. Решение транспортной задачи в сетевой форме. Решение транспортной задачи в виде сетевой модели без ограничения пропускной способности сети. Решение транспортной задачи в виде сетевой модели с ограничением пропускной способности сети. 1.3.Тематический план лекций 1.3.1.Тематический план лекций для студентов очно-заочной формы обучения специальности 150200 (16 часов) 1. Введение. Задачи курса. Современные средства связи. Современные проблемы информатики……………………………………………………4 часа 2. Системы управления базами данных Вычислительные сети. Управление автотранспортным производством как объектом

автоматизации. Автоматизированные системы планирования и управления грузовыми перевозками……………………………………..4 -//3. Автоматизированная система оперативного управления техническим обслуживанием и текущим ремонтом подвижного состава. Автоматизированная система технико-экономического планирования и учета. Проектирование и внедрение АСУ……………….4 -//4. Задачи и методы линейного программирования. Методы решения автотранспортных задач…………………………………………..4 -//1.3.2.Тематический план лекций для студентов очно-заочной формы обучения специальности 240100 (24 часа) 1. Введение. Задачи курса. Современные средства связи. Современные проблемы информатики……………………………………………………4 часа 2. Системы управления базами данных Вычислительные сети. Управление автотранспортным производством как объектом автоматизации. Автоматизированные системы планирования и управления грузовыми перевозками……………………………………..4 -//3. Автоматизированная система оперативного управления техническим обслуживанием и текущим ремонтом подвижного состава. Автоматизированная система технико-экономического планирования и учета. Проектирование и внедрение АСУ……………….8 -//4. Задачи и методы линейного программирования. Методы решения автотранспортных задач…………………………………………..8 -//1.4.Темы лабораторных работ (12 часов) Изучение прикладного программного обеспечения АРМов…………….12 часов 1.5. Темы практических занятий (4 часа) 1. Алгоритмы и методы решения транспортной задачи линейного программирования………………………………………………………….2 часа 2. Алгоритмы и методы решения транспортной задачи в сетевой форме……………………………………………..………………………….2 -//3. Библиографический список Основной: 1.Адаменко М.В. Сотовые телефоноы. М.: ДМК, 2002, -240с.

2.Советов Б.Я. Информационная технология. Учебник для вузов. М.: Высшая школа, 1994, -366 с. 3. Николаев А.Б., Алексахин С.В., Кузнецов И.А., Строганов В.Ю. Автоматизированные системы обработки информации и управления на автомобильном транспорте. Учебник. М.: Академия, 2003, -224 с. 4.Бобарыкин В.А. Математические методы решения автотранспортных задач: Учебное пособие. –Л.: СЗПИ, 1986, -84 с. Дополнительный: 5.Microsoft Corporation. Компьютерные сети. Учебный курс. –М.: 1997. –696 с. 6. Соколов А.В., Андрианов В.И. Альтернатива сотовой связи: транкинговые системы.- СПб.: БХВ – Петербург, 2002. – 448 с. 7. Епанешников А.М., Епанешников В.А. Delphi. Программирование СУБД. М.: ДМК, 2003, 188 с. 8. Материалы сайта http://www.osp.ru 4. Задания на контрольные работы (для студентов специальности 150200) и курсовую работу (для студентов специальности 240100) Контрольные работы (курсовая работа) выполняется на стандартных листах писчей бумаги формата А4. В конце работы приводится список литературы, на которую, по мере необходимости, делаются ссылки в тексте. Рекомендуется оформлять контрольную (курсовую) работу на компьютере: шрифт – Times New Roman Cyr, размер основного шрифта – кг. 14, размеры поля со всех сторон – 20 мм. Абзац начинается отступом, равным 5 пробелам (15-17 мм), межстрочный интервал – 1,2-1,5. Примеры оформления титульного листа приведены в приложении 1 (для студентов специальности 150200) и 2 (для студентов специальности 240100.01). Все листы кроме титульного должны быть пронумерованы. Номер должен ставится в низу страницы, в центре. Листы обязательно должны быть сброшюрованы шнурком, скобками или с помощью специальной папки. Категорически запрещается соединять листы канцелярскими скрепками или временными зажимами. Все задания контрольной (курсовой) работы должны иметь сквозную нумерацию и обозначаются арабскими цифрами с точкой. Сокращение слов в тексте допускается согласно ГОСТ 7.12-70. Значения символов и числовых коэффициентов, входящих в формулы, должны быть приведены непосредственно под формулой. Первая строка расшифровки должна начинаться со слова «где» без двоеточия. Пример тестовых заданий для осуществления текущего и итогового контроля знаний студентов по дисциплине «Информационные технологии на автомобильном транспорте» («Информационные технологии на транспорте») приведен в приложении 3.

Контрольная работа №1 (Задача №1) Задача № 1 Требуется выбрать и дать техническое и экономическое обоснование выбора информационного оборудования (вычислительной техники, средств связи и т.д.) подразделения автотранспортного предприятия (табл.1). Вид рекомендуемой для закупки аппаратуры и ее технические характеристики должны быть обоснованы спецификой задач, для выполнения которых она приобретается, при этом следует учитывать финансовые возможности организации и число сотрудников рассматриваемого отдела (табл.2). В отделе должна быть установлена локальная сеть. Таблица 1 последняя цифра шифра № варианта 1 2 3 4 5 6 7 8 9 0 ПодразБухгалтерия ДиспетчерПроизв.Ремонтная Плановоделение ская технич. зона эконом. Таблица 2 предпоследняя цифра шифра № варианта 1 2 3 4 5 6 7 8 9 0 предельная сумма 6.5 7 8 9 10 11 12 13 14 16 расхода (тыс. у.е.) число 4 5 6 7 7 7 8 8 8 9 сотрудников В работе должны быть представлены: 1. Схема локальной сети с указанием ее составных элементов с обоснованием выбора той или иной топологии. 2. Состав технических средств и их основные характеристики (табл.3). 3. Перечень программного обеспечения. Должность сотрудника

Кол-во

Технические характеристики

Стоимость одного экземпляра

…

…

…

…

Таблица 3 Общая стоимость …

Предоставленные средства должны быть израсходованы полностью.

Задача № 2 Компьютерные сети и технологии 1. 2. 3. 4. 5.

Топологии компьютерных сетей, их преимущества и недостатки. История создания глобальной компьютерной сети Интернет. Протоколы сети Интернет. Адресация и система доменных имен сети Интернет. Программы для работы в сети.

Задача № 3 Системы управления базами данных 1. Функции реляционных баз данных. 2. Языки баз данных. 3. Типовая организация баз данных. Контрольная работа № 2 (Задача №4) Задача № 1 Решить транспортную задачу методом потенциалов. Потребителям Б1, Б2, Б3 и Б4 требуется песок в количествах соответственно б1, б2, б3 и б4 тонн. На складах имеется следующее количество песка: А1 = а1 т, А2 = а2 т и А3 = а3 т. Требуемое и имеющееся количество песка приведено в табл.4. Расстояния между поставщиками и получателями песка приведены в табл.5. Необходимо составить план перевозок песка (план закрепления потребителей за поставщиками) так, чтобы при минимальной транспортной работе были удовлетворены запросы всех потребителей.

Таблица 4 Предпоследняя цифра шифра

а1

а2

а3

б1

б2

б3

б4

0

90

60

50

40

70

50

40

1

110

70

60

50

80

60

50

2

120

90

70

60

90

70

60

3

130

100

90

70

100

80

70

4

150

110

100

80

110

90

80

5

160

120

120

90

120

100

90

6

170

140

130

100

130

110

100

7

190

150

140

110

140

120

110

8

200

160

160

120

150

130

120

9

210

180

170

130

160

140

130 Таблица 5

Последняя цифра шифра

X11

X12

X13

X14

X21

X22

X23

X24

X31

X32

X33

X34

0

10

25

6

9

5

21

13

6

18

22

11

28

1

11

24

7

10

6

20

14

8

19

23

13

27

2

12

23

8

11

7

19

15

10

20

24

14

26

3

13

22

9

12

8

18

16

12

21

25

16

25

4

14

21

10

13

9

17

17

14

22

26

17

24

5

15

20

11

14

10

16

18

16

23

27

19

23

6

16

19

12

15

11

15

19

18

24

28

20

22

7

17

18

13

16

12

14

20

17

25

29

21

21

8

18

17

14

17

13

13

21

15

26

30

22

20

9

19

16

15

18

14

12

22

13

27

31

24

19

Рассмотрим процедуру вычислений на конкретном примере. Пусть потребителям Б1, Б2, Б3 и Б4 требуется песок в количествах соответственно 30, 70, 40 и 30 тонн. На складах имеется следующее количество песка: А1 = 80 т, А2 = 50 т и А3 = 40 т. Расстояния между поставщиками и получателями песка приведены в табл.6. Необходимо составить план перевозок песка (план закрепления потребителей за поставщиками) так, чтобы при минимальной транспортной работе были удовлетворены запросы всех потребителей. Таблица 6 Пункт отправления

Б1 9 4 16

А1 А2 А3

Пункт назначения Б2 Б3 15 5 9 6 22 10

Б4 8 5 18

Очевидно, что транспортная работа будет минимальной, если доставлять песок каждому потребителю с ближайшего к нему склада. В таком случае решение было бы очевидным. Однако в рассматриваемой задаче это невозможно, так как для потребителей Б1, Б2 и Б4 с суммарной потребностью в 130 т ближайшим является склад А2, где имеется лишь 50 т песка. Поэтому для полного удовлетворения потребности этих потребителей неизбежны перевозки с других складов. При этом возможны различные варианты. 1. Составление матрицы условий. Запишем условия задачи в форме матрицы (табл.7). Пункт Вспомогатель отправле ные ния А1 А2 А3 Потребность в грузе, т

Пункт назначения Б2 Б3

Б1 10 20

Б4

9

15

4

9

6

5

22

10

18

16

30

Таблица 7 Наличие груза, т

30 40 70

40

40

5

8

30

30

80 50 40 170

В правых верхних углах клеток, представляющих собой реальные маршруты перевозок, указаны расстояния между соответствующими пунктами. В процессе решения задачи в средней части этих клеток записывают значения хij, которые делятся на основные и не основные. Не основные хij в таблице-матрице не пишутся и считаются равными нулю. К основным относятся все хij >0, а также те из хij =0, которые записываются в матрице. Основные хij записанные в

матрице, обычно называют загрузками, а клетки, в которых они находятся, занятыми. Клетки матрицы без загрузок называют незанятыми. 2. Составление допустимого исходного плана. Решение задачи начинается с составления допустимого плана. Производится это способом минимального элемента по строке следующим образом. Сначала планируем перевозки с первого склада, записывая их в соответствующие клетки первой строки. Производим это следующим образом. Сначала полностью удовлетворяем потребность ближайшего потребителя Б3, записав в клетку с наименьшим расстоянием 40 т. Поскольку в пункте А1 остается еще 40 т, удовлетворяем потребность следующего ближайшего потребителя Б4, записав в соответствующую клетку нужные ему 30 т. Оставшиеся 10 т заносим в клетку А1Б1 и переходим к следующей строке матрицы. Теперь груз второго отправителя А2 планируем к перевозке ближайшим из еще неудовлетворенных потребителей, записывая соответствующие объемы в клетки второй строки последовательно, начиная с клетки с наименьшим расстоянием:, в клетку А2Б1 20 т и в клетку А2Б2 - 30 т. Перейдя к третьей строке матрицы, видим, что остался неудовлетворенным только один потребитель Б2. Планируем ему перевозку из А3, записав в клетку А3Б2 40 т. Вычисления закончены. Полученный допустимый план представлен в табл. 8. По этому плану перевозок потребность всех потребителей удовлетворяется полностью, а транспортная работа составит Р = 10*9+40*5+30*8+20*4+30*9+40*22 = 1760 тонно-километров. 2. Проверка оптимальности плана производится с помощью индексов, которые рассчитывают прямо на матрице. Таблица 8 Пункт назначения Пункт Наличие Вспомогатель отправле Б1 Б2 Б3 Б4 груза ные ния V2 V3 V4 V1 15 А1 U1 10 9 40 5 30 8 80 4 9 6 5 А2 U2 20 30 50 16 22 10 18 А3 U3 40 40 Потребность, т 30 70 40 30 170 При этом индексы Ui, записывают в клетки вспомогательного столбца, а индексы Vj - в клетки вспомогательной строки (табл. 8). Для определения индексов используют следующие правила: 1) индекс первой клетки вспомогательного столбца всегда равен нулю (U1 = 0); 2) для каждой занятой клетки матрицы сумма соответствующих ей индексов U и V (записанных против нее сверху и сбоку во вспомогательных клетках) равна расстоянию, указанному в данной клетке.

Из последнего правила следует, что если у занятой клетки один из индексов известен, то другой равен разности ее расстояния и известного индекса, т.е. Ui = Lij – Vj и Vj = Lij – Ui (1) Запишем в матрицу индекс U1 = 0. Тогда у занятых клеток A1Б1, А1Б3 и А1Б4 один индекс известен и можно, используя равенство (1), определить индексы V1, V2 и V4 (табл.9): V1 = L11 – U1 = 9-0=9 V3 = L13 – U1 = 5-0=5 V4 = L14 – U1 = 8-0=8 Теперь у занятой клетки А2Б1 известен индекс V1 и можно найти индекс U2 = L22 – U2 = 4-9 = -5. После этого определяем индекс V2, а затем индекс U3: V2=L22 – U2 = 9 – (-5) = -5 и U3 = L32 – V2 = 22 – 14 = 8 Таблица 9 Пункт назначения Пункт Вспомога Наличие отправле Б1 Б2 Б3 Б4 тельные груза ния 9 14 5 8 15 А1 0 10 9 40 5 30 8 80 4 9 6 5 А2 -5 20 30 50 16 22 10 18 А3 8 40 40 Потребность, т 30 70 40 30 170 Таким образом, все индексы найдены (табл. 9) и можно приступить к проверке плана, которая сводится к сравнению расстояния каждой незанятой клетки матрицы с суммой соответствующих ей индексов с целью выявления клеток, в которых расстояние меньше указанной суммы. В нашем примере имеем: (U1 + V2 = 0 + 14) < (L12 = 15) (U2 + V3 = -5 + 5 = 0) < (L23 = 6) (U2 + V4 = -5 + 8 = 3) < (L24 = 5) (U3 + V1 = 8 + 9 =17) > (L31 = 16) (U3 + V3 = 8 + 5 = 13) > (L33 = 10) (U3 + V4 = 8 + 8) < (L34 = 18) У незанятых клеток А3Б1 и А3Б3 расстояние меньше суммы их индексов. Следовательно, составленный план не является оптимальным. 4. Улучшение неоптимального плана. Выявленные на предыдущем этапе вычислений клетки А3Б1 и А3Б3 являются резервом улучшения плана и потому их называют потенциальными, а превышение суммы индексов над расстоянием - потенциалом.

Процедура улучшения неоптимального плана сводится к перемещению загрузок в потенциальные клетки матрицы. Поскольку нельзя просто переставить в потенциальную клетку одну из загрузок, не нарушив итоги по строкам и столбцам, разработан специальный способ перемещения загрузок. Он состоит из составления цепочки возможных перемещений загрузок в матрице, определения величины загрузки, подлежащей перемещению, и собственно перемещения. Цепочку возможных перемещений определяют следующим образом. Для потенциальной клетки с наибольшим потенциалом строят замкнутую цепочку из горизонтальных и вертикальных отрезков так, чтобы одна ее вершина лежала в данной потенциальной клетке, а все остальные - в занятых клетках. Такую цепочку всегда можно построить и притом единственным способом. Ее вершины отмечают клетки матрицы, которые должны участвовать в перераспределении загрузок с целью улучшения плана. Возможны различные конфигурации цепочек. Составив цепочку, помечают знаком «+» ее нечетные вершины (считая первой вершину в потенциальной клетке), а четные знаком «—». Наименьшая из четных загрузок определяет величину перемещаемой загрузки. Уменьшив на эту величину объемы перевозок, записанные в клетках со знаком минус, и увеличив на ту же величину объемы клеток со знаком плюс, получают новый вариант плана с меньшей транспортной работой. В рассматриваемом примере построена цепочка для потенциальной клетки А3Б3 и расставлены знаки (табл. 10). Таблица 10 Пункт назначения Пункт Вспомогательные Наличи отправлен е груза, Б1 Б2 Б3 Б4 строка ия т столбец 9 14 5 8 15 5 8 +9 80 А1 0 30. 10 ⎯40. 4 + 9 6 5 50 А2 ⎯5 30 20 ⎯ 22 + 10 18 16 40 А3 8 1 ⎯40. 3 Потребность в грузе, т 30 70 40 30 170 Наименьшая среди четных загрузок (отмеченных знаком минус) равна 20 (в клетке А2Б1). Уменьшив на 20 загрузки клеток А1Б3, А2Б1 и А3Б2 и увеличив также на 20 загрузки клеток А3Б3, А1Б1 и А2Б2, получим новый план, представленный в табл. 11. По этому варианту плана транспортная работа составит 1700 тонно-километров, или на 60 тонно-километров меньше.

Таблица 11 Вспомогательные строка Пункт отправления столбец А1

Б1 9

15

30 4

Наличие груза, т

Б4

5 20

А2

8 30

9

6

5

22

10

18

50 16

А3 Потребность в грузе, т

Пункт назначения Б2 Б3

20

20 30

70

40

30

80 50 40 170

Полученный план лучше предыдущего, однако, неизвестно, является ли он оптимальным. Чтобы ответить на этот вопрос, необходимо исследовать его на оптимальность, повторив весь процесс вычислений. Из табл. 11 видно, что и этот план, как и предыдущий, не является оптимальным. Об этом говорит наличие в матрице потенциальной клетки А1Б2. Изменив уже известным способом загрузки в клетках, отмеченных вершинами вновь построенной цепочки, получаем новый план, представленный в табл.12 . Для его проверки на оптимальность приступаем к расчету индексов и убеждаемся, что все их определить не удается. Причиной этого является так называемое вырождение плана, т.е. уменьшение числа занятых клеток против необходимого. Дело в том, что все индексы могут быть найдены, и притом однозначно, только при строго определенном количестве занятых клеток, равном в общем случае m+n—1, где m—число пунктов отправления, n—число пунктов назначения. В нашей задаче m=3, а n=4. Следовательно, для определения всех индексов нужно иметь в матрице 3+4—1=6 занятых клеток. В табл. их только пять, поэтому индексы U3 V3 не удается определить. Таблица 12 Вспомогательные Пункт назначения Наличие строка Б1 Б2 Б3 Б4 Пункт груза, т отправления столбец 9 17 5 8 5 8 9 15 80 А1 0 30 30 2 + ⎯ 20 4 9 6 5 А2 -8 50 50 18 16 22 10 40 А3 5 +20 20⎯ Потребность в грузе, т 30 70 40 30 170

Таблица 13 Вспомогательные строка Пункт отправления столбец А1

0

А2

-6

А3 Потребность в грузе, т

Пункт назначения Наличие Б1 Б2 Б3 Б4 груза, т 9 15 9 15 5 8 80 30 20 30 4 9 6 5 50 50 18 16 22 10 40 40 30 70 40 30 170

Вырождение матрицы так же, как и излишнее количество занятых клеток, нарушают нормальную процедуру вычислений и их нужно устранять. Избавиться от вырождения можно путем записи в одной из незанятых клеток матрицы перевозки объемом 0 тонн. В табл. 13 нулевую загрузку можно поставить в одну из клеток А1Б3, А2Б3, А3Б1, А3Б2 и А3Б4. Легко проверить, что только эти клетки, став занятыми нулевой загрузкой, позволят найти недостающие индексы U3 и V3. Лучше всего поставить нулевую перевозку в клетку с меньшим расстоянием, т.е. в клетку А1Б3. Теперь определив недостающие индексы, убеждаемся, что последний план является оптимальным, поскольку у всех незанятых клеток матрицы расстояния больше суммы соответствующих им индексов (табл. 14). Транспортная работа по этому плану составит 1600 тоннокилометров. Таблица 14 Пункт отправления

Вспомогательные строка столбец

А1

0

А2

-6

А3

5

Потребность в грузе, т

Пункт назначения Наличие Б1 Б2 Б3 Б4 груза, т 9 15 5 8 9 15 5 8 80 30. 20 0 30 4 9 6 5 50 50 18 16 22 10 40 40 30 70 40 30 170

В случае если число занятых клеток в матрице больше, чем m+n—1, поступают следующим образом. В табл. 15 - семь занятых клеток вместо необходимых шести (m+n-1=3+4—1=6). Наличие лишней занятой клетки приводит к тому, что индексы определяются неоднозначно. В первом случае U2=9—15= - 6, во втором U2=6—5= 1. Таблица 15 Вспомогательные строка Пункт отправления столбец А1

0

А2

-6,1

А3 Потребность в грузе, т

Пункт назначения Наличие Б1 Б2 Б3 Б4 груза, т 15 5 8 8 5 9 15 80 + ⎯ 30 30 20 4 9 6 5 50 40 + ⎯10 18 16 22 10 40 30 10 30 70 40 30 170

Уменьшение числа занятых клеток производится следующим образом. В матрице строят замкнутую цепочку из горизонтальных и вертикальных отрезков так, чтобы все ее вершины находились в занятых клетках (см. табл. 16). Такая цепочка в матрице с числом занятых клеток более m+n -1 всегда имеется. На вершинах цепочки, начиная с клетки, имеющей наименьшую загрузку, расставляют попеременно знаки минус и плюс, после чего загрузки со знаком минус уменьшают, а со знаком плюс увеличивают на величину наименьшей из них. В результате число занятых клеток уменьшится не менее чем на одну (табл.17). При необходимости данную процедуру повторяют столько раз, сколько это необходимо для получения m+n -1 занятых клеток. Таблица 16 Вспомогательные строка Пункт отправления столбец

Б1 9

А1

Потребность в грузе, т

15 10

Наличи е груза, т

Б4

5 40

4

А2 А3

Пункт назначения Б2 Б3

8 30

9

6

5

22

10

18

50 16 30

10 30

70

40

30

80 50 40 170

Приложение 1 Министерство образования Российской Федерации Государственное образовательное учреждение высшего профессионального образования

СЕВЕРО-ЗАПАДНЫЙ ГОСУДАРСТВЕННЫЙ ЗАОЧНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Факультет экономики и управления на автомобильном транспорте Кафедра автомобильного транспорта

Контрольные работы по дисциплине «Информационные технологии на автомобильном транспорте»

__________________________________

(студент:

фамилия,

имя,

__________________________________

отчество) __________________________________

(специальность, курс) __________________________________ (шифр, форма обучения) __________________________________

(адрес проживания) __________________________________ __________________________________ __________________________________

г._________________ 200__ г.

Приложение 2 Министерство образования Российской Федерации Государственное образовательное учреждение высшего профессионального образования

СЕВЕРО-ЗАПАДНЫЙ ГОСУДАРСТВЕННЫЙ ЗАОЧНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Факультет экономики и управления на атомобильном транспорте Кафедра автомобильного транспорта

Курсовая работа по дисциплине «Информационные технологии на транспорте»

__________________________________

(студент:

фамилия,

имя,

__________________________________

отчество) __________________________________

(специальность, курс) __________________________________ (шифр, форма обучения) __________________________________

(адрес проживания) __________________________________ __________________________________ __________________________________

г._________________ 200__ г.

Приложение 3 Пример тестовых заданий для осуществления текущего и итогового контроля знаний студентов по дисциплине «Информационные технологии на автомобильном транспорте» («Информационные технологии на транспорте») Вопросы Концентратор это

К какому поколенью стандартов сотовой связи относится GSM 1900? В каких характеристиках сигнала закодирована полезная информация в стандартах сотовой связи первого поколенья? СУБД это

Третий уровень эталонной модели взаимодействия открытых систем обеспечивает

Варианты ответов 1.Устройство множественного доступа. 2.Многопортовое устройство, обеспечивающее высокоскоростную коммутацию пакетов между портами. 3.Устройство соединения нескольких локальных сетей. 4.Устройство подключения ПК в ЛС 1. Первому 2. Второму 3. Третьему 4. Четвертому 1. Частота и фаза 2. Частота и амплитуда 3. Амплитуда 4. Фаза и амплитуда 5. Фаза и частота 1. Система управления больших дистанций 2. Схема узла беспроводного доступа 3. Система управления базами данных 4. Схема усвоенных баз данных 1. Одинаковый синтаксис передаваемой информации 2. Маршрутизацию информации 3. Функциональные и процедурные средства для установления соединения. 4. Электрические и механические средства организации соединений

Содержание

Редактор А.В. Алехина

Сводный темплан 2004г. Лицензия ЛР № 020308 от 14.02.97 Санитарно-эпидемиологическое заключение № 78.01.07.953.П.005641.11.03 от 21.11.2003 г.

Подписано в печать Б. Кн . – журн. П. л.

Б. л.

Тираж 200

Формат 60х84 1/16 РТП РИО СЗТУ Заказ

Северо-Западный государственный заочный технический университет РИО СЗТУ, член Издательско-полиграфической ассоциации вузов Санкт-Петербурга 191186, Санкт-Петербург, ул. Миллионная, 5