Задача о кратчайшем маршруте на графе

1) В таблице указаны расстояния в километрах между населенными пунктами . Составить граф схемы автомобильных дорог районы и найти кратчайший путь из райцентра в отдаленное село . Вычислить его длину.

 

 

3.2.2. 1) Туристическая компания “Супертранс” предлагает билеты на авиарейсы:

Рейс Цена (в условных единицах)

1. Москва — Новосибирск 105

2. Москва — Иркутск 175

3. Москва — Алма-Ата 210

4. Москва — Рим 200

5. Новосибирск — Якутск 85

6. Новосибирск — Иркутск 75

7. Новосибирск — Хабаровск 80

8. Новосибирск — Владивосток 130

9. Иркутск — Якутск 80

10. Иркутск — Хабаровск 35

11. Якутск — Хабаровск 40

12. Якутск — Владивосток 50

13. Хабаровск — Владивосток 25

14. Хабаровск — Пекин 120

15. Алма-Ата — Иркутск 60

16. Алма-Ата — Токио 280

17. Алма-Ата — Пекин 150

18. Рим — Пекин 250

19. Рим — Токио 300

20. Пекин — Токио 110

21. Владивосток — Токио 160

 

Начертите граф авиалиний компании и найдите в нём минимальный по стоимости маршрут из Москвы в Токио.

2) Туристическая компания «Супертранс» предлагает билеты на авиарейсы:

Рейс Цена (в условных единицах)

1. Москва — Новосибирск 110

2. Москва — Иркутск 180

3. Новосибирск — Якутск 70

4. Новосибирск — Иркутск 60

5. Новосибирск — Хабаровск 120

6. Новосибирск — Владивосток 170

7. Иркутск — Якутск 60

8. Иркутск — Хабаровск 50

9. Якутск — Хабаровск 40

10. Якутск — Владивосток 80

11. Хабаровск — Владивосток 20

 

Начертите граф авиалиний компании и найдите в нём минимальный по стоимости маршрут из Москвы во Владивосток.

 

 

3) Туристическая компания «Супертранс» предлагает билеты на авиарейсы:

Рейс Цена (в условных единицах)

1. Москва — Новосибирск 95

2. Москва — Иркутск 155

3. Новосибирск — Якутск 85

4. Новосибирск — Иркутск 45

5. Новосибирск — Хабаровск 105

6. Новосибирск — Владивосток 145

7. Иркутск — Якутск 35

8. Иркутск — Хабаровск 45

9. Якутск — Хабаровск 45

10. Якутск — Владивосток 75

11. Хабаровск — Владивосток 25

 

Начертите граф авиалиний компании и найдите в нём минимальный по стоимости маршрут из Москвы во Владивосток.

 

Элементы сетевого планирования.

1) Построить сетевую модель задачи планирования поставки товаров оптовым покупателям. Провести оптимизацию по критерию времени, определить критический путь и резервы времени, определить экономию.

 

Содержание работ	Работа	Длительность
Коэффициент	Обоз-наче-ние	Опорная	Варианты
Отбор товара	0,1		–	2	4	5	6	3
Подготовка к отправке	0,2			3	2	4	5	6
Выписка накладных	0,3			1	2	3	4	3
Определение объема отгрузки	0,4			1	2	3	4	3
Проверка цен	0,5			1	2	2	2	2
Оформление счета	0,6			1	2	4	3	2
Заказ автомашин	0,7			3	1	1	2	2
Отправление счета покупателю	0,8			1	4	4	3	3
Проверка товара по счету	0,9			2	3	3	4	4
Оплата счета	1,0			12	10	8	6	14
Погрузка товара и проверка количества	1,1			2	3	3	4	4
Перевозка товара	1,2			4	4	5	6	7
Выгрузка и сверка с документами	1,3			4	4	5	4	5

2) Построить сетевую модель задачи планирования торговой деятельности района. Провести оптимизацию по критерию времени, определить критический путь и резервы времени, определить экономию.

Содержание работ	Работа	Длительность
Коэффициент	Обоз-наче-ние	Опор-ная	Варианты
Изучение отчетных данных	0,1		–	3	2	3	4	5
Изучение перспектив развития экономики	0,2		–	2	3	2	3	3
Планирование общего объема товарооборота	0,3			2	1	3	2	3
Планирование торгового обеспечения в общем объеме	0,4			1	2	3	4	5
Планирование товарооборота в ассортименте	0,5			3	2	3	2	4
Составление плана по труду	0,6			3	2	2	3	2
Планирование товарооборота по магазину	0,7			2	3	4	5	6
Расчет доходов	0,8			3	2	3	4	5
Планирование запасов по магазинам	0,9			3	3	2	1	4
Планирование товарного обеспечения в ассортименте	1,0			2	2	3	4	5

Продолжение табл.

Составление плана издержек обращения по предприятиям	1,1			4	5	4	2	3
Планирование запасов в ассортименте	1,2			2	3	4	5	6
Экономический анализ	1,3			3	2	7	8	6

3) Построить сетевую модель задачи планирования строительства контейнерных площадок. Провести оптимизацию по критерию времени, определить критический путь и резервы времени, определить экономию.

Содержание работ	Работа	Длительность
Коэф-ент	Обозначение	Опор-ная	Варианты
Экон. обоснование целесообразности строи-ва	0,1		–	5	6	7	8	9
Разработка проектно-сметной документации	0,2			20	24	30	26	28
Строительство контейнерных площадок	0,3			30	32	34	35	36
Подбор кадров для раб.на контейнерных площадках	0,4			10	15	20	25	30

Продолжение табл.

Заявка на оборудование	0,5			2	3	4	5	6
Строительство склада перевалки	0,6			20	25	30	35	40
Строит-во контейн. площадок при ж/д станции	0,7			40	45	50	55	60
Изгот-ие необходимого кол-ва контейнеров	0,8			15	20	25	20	25
Завоз контейнеров	0,9			5	6	7	8	9
Обучение кадров	1,0			15	14	16	18	20
Завоз оборудования	1,1			3	4	5	6	7
Строительство склада для контейнеров	1,2			20	25	30	35	40
Строит-во участка ж/д от конт. площадки до склада	1,3			30	35	40	45	50
Монтаж оборудования	1,4			10	12	14	16	18