Телефонная компания планирует соединить подземным кабелем 6 городов,
расстояния между которыми заданы в таблице:
A B C D E F
A - 10 9 30 27 20
B 10 - 15 18 17 20
C 9 15 - 25 21 16
D 30 18 25 - 8 17
E 27 17 21 8 - 13
F 20 20 16 17 13 -
Найдите минимальную длину кабеля, позволяющую жителям любых городов
связаться друг с другом по телефону с объяснением шагов.
Пусть, согласно данным экономического прогноза, экономическая эффективность покупки лицензии №1 составит 18 млн. у.е., если выпуск автомобиля будет рентабельным в течение 10 лет и 21 млн у.е., если выпуск автомобиля будет рентабельным в течение 15 лет; экономическая эффективность покупки лицензии №2 составит 20 млн. у.е., в случае рентабельности в течение 10 лет и 22 млн у.е., при рентабельности в течение 15 лет; для лицензии №3 – 17 млн у.е. для 10 лет и 26 млн у.е. для 15 лет, а для лицензии №4 – 10 и 28 млн у.е., соответственно.
Пошаговое объяснение:
Пусть, согласно данным экономического прогноза, экономическая эффективность покупки лицензии №1 составит 18 млн. у.е., если выпуск автомобиля будет рентабельным в течение 10 лет и 21 млн у.е., если выпуск автомобиля будет рентабельным в течение 15 лет; экономическая эффективность покупки лицензии №2 составит 20 млн. у.е., в случае рентабельности в течение 10 лет и 22 млн у.е., при рентабельности в течение 15 лет; для лицензии №3 – 17 млн у.е. для 10 лет и 26 млн у.е. для 15 лет, а для лицензии №4 – 10 и 28 млн у.е., соответственно.
Как составить маршрут путешествия, как спроектировать городскую транспортную сеть, соединить компьютеры локальной сетью, составить график выполнения комплекса работ? На эти и другие вопросы позволяет ответить раздел прикладной математики, который называется « Методы сетевого планирования и управления», или « сетевой анализ».
Сетевой анализ берет свое начало с задачи Эйлера о кенигсбергских мостах: « Мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто 7 мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост…»,- из письма Л. Эйлера от 13 марта 1736 г. Спустя более века Джеймс Клерк Максвелл и Густав Роберт Кирхгофф, исследуя электрические сети, сформулировали некоторые принципы сетевого анализа. В настоящее время задачи подобного рода широко используются в теории и практике принятия управленческих решений., поэтому мы считаем целесообразным включить данный курс в образовательную программу летней физико-математической школы.
Математическим аппаратом для данных задач является теория графов, с которой учащиеся знакомы по материалам зимних сессий. Кроме того, благодаря специальной структуре сетевых задач, для их решения получено большое число эффективных алгоритмов, которые легко реализуются с ЭВМ.
Цель данного курса: дать понятие о задачах сетевого планирования и управления, опираясь на известный им теоретический материал, изучить алгоритмы решения сетевых задач, имеющих практическое содержание, подготовить базу для реализации этих алгоритмов в курсе информатики.
Тематическое планирование