Контрольное задание №15

1. Строится нефтепровод, соединяющий города х₁……x_11. Стоимость возможных участков строительства задана таблицей.

	х1	х2	х3	х4	х5	х6	х7	х8	х9	х10	х11
х1
х2
х3
х4
х5
х6
х7
х8
х9
х10
х11

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

2. Каждый из шести городов может быть соединен с другим участком газопровода, стоимость строительства которого указана в таблице.

	х1	х2	х3	х4	х5	х6
х1
х2
х3
х4
х5
х6

Как построить самый дешевый нефтепровод, какова стоимость его строительства?

3. 10 городов, обозначенных на графе вершинами х1…x10, необходимо соединить электролинией. Возможные соединения обозначены ребрами. Стоимость строительства на участке (хi,xj) обозначена соответствующим числом.

Определить стоимость строительства самой дешевой электролинии. Как она должна проходить?

4. На строительство электролинии между городами х1…..х7 отпущено 250 тысяч рублей. Стоимость строительства на возможных участках между городами хi,хj l (хi хj) в тыс. руб. задана следующим образом:

l (x1,x2)=40 l (x1,x3)=50 l (x1,x6)=60 l (x1,x7)=50 l (x2,x3)=30

l (x2,x6)=20 l (x2,x7)=30 l (x2,x4)=90 l (x3,x4)=60 l (x3,x7)=60

l (x4,x5)=90 l (x4,x7)=70 l (x5,x6)=80 l (x5,x7)=100 l (x6,x7)=10

Как построить электролинию, чтобы уложиться в эту смету?

5. Определить наименьшие затраты при перевозке груза из пункта х₀ в пункт х₆ через перевалочные пункты х₁,х₂,х₃,х₄,х₅. Стоимость перевозки груза из пункта х_i в х_j указана на графе. Определить путь, соответствующий минимальной стоимости.

6. Из пункта А в пункт N перевозят однородный груз, используя перевалочные пункты В, С, D, Е, F, G. Расстояние между пунктами, соединенными дорогами, указаны на графе.

Определить кратчайший путь и его длину, предварительно пронумеровав вершины графа.

7. Пункты А и В связаны сетью дорог, проходящих через пункты С, D, Е, М, N. Стоимость проезда из пункта x_i в x_j указана на графе. Какова минимальная стоимость проезда из А и В?. Как проходит путь, соответствующий минимальным затратам?

8. Для графов задач 6, 7 определить критический путь и критическое время.

9. Основу строительства объекта составляют 14 операций, последовательность выполнения которых задана графом. Продолжительность каждой из них указана на графе.

Определить скорейшее время завершения всего проекта. Какие операции не допускают запаздывания по времени?

10. Найти кратчайший и длиннейший пути, соединяющие вход и выход графа, предварительно правильно пронумеровав вершины.

Список рекомендуемой литературы

1. Александров, П.С. Введение в теорию множеств и теорию функций. – М.: Наука, 1977

2. Балюкевич, Э.Л., Ковалева Л.Ф. Математическая логика и теория алгоритмов: учебное пособие. – М.: МГУЭСИ, 2007.

3. Гаврилов, Г.П., Сапоженко, А.А. Задачи и упражнения по курсу «Дискретная математика». – М.: Наука, 1992

4. Грей, П. Логика, алгебра и базы данных. – М.: Машиностроение, 1989

5. Гиндикин, С.Г. Алгебра логики в задачах. – М.: Наука, 1972.

6. Ерусалимский, Я.М. Дискретная математика. – М.: Вузовская книга, 2000.

7. Колмогоров, А.Н., Фомин, С.В. Элементы теории функций и функционального анализа. – М.: Наука, 1989

8. Клини С. Математическая логика. – М.: Мир, 1973.

9. Ковалева, Л.Ф., Данков, О.Ю., Горбовцов Г.Я., Мокеева И.К. Дискретная математика. – М.: МЭСИ, 1988.

10. Нефедов, В.Н., Осипова В.А. Курс дискретной математики. – М.: МАИ, 1992.

11. Новиков, Н. С. Элементы математической логики. – М.: Наука, 1973.

12. Под редакцией Скорнякова Л.А. Общая алгебра. II. – М.: Наука, 1990г.

13. Эдельман, С.Л. Математическая логика. – М.: Высшая школа, 1975.

14. Яблонский, С.В. Введение в дискретную математику. – М.: Наука, 1979.

Интернет-ресурсы

1. www.osp.mesi.ru (сайт учебного процесса МЭСИ). Балюкевич Э.Л., Ковалева Л.Ф., Романников А.Н. Дискретная математика.

2. www.booka.ru/booka_topic_6114?id=97427 Дискретная математика. Курс лекций.

Руководство по изучению дисциплины