Учебно-методическое обеспечение и календарный график самостоятельной работы студентов
Планируемые результаты обучения по дисциплине
Цель и задачи дисциплины
Цель дисциплины.
Целями освоения дисциплины "Методы оптимальных решений" являются: развитие у студентов логического и алгоритмического мышления путем детального анализа подходов к математическому моделированию и сравнительного анализа разных типов моделей.
Задачи дисциплины.
Задачи данного курса:
Ознакомить слушателей с математическими свойствами моделей и методов оптимизации, которые могут использоваться при анализе и решении широкого спектра экономических задач. Научить студентов использовать компьютерные программы для обработки данных. Формирование у обучаемых математических знаний для успешного овладения общенаучными дисциплинами на необходимом научном уровне. Приобретение умения студентами самостоятельно расширять математические знания и проводить математический анализ прикладных экономических задач.
Требования к уровню освоения и содержания дисциплины
В результате изучения дисциплины студент должен
знать
основные математические модели оптимальных решений;
уметь
- решать типовые математические задачи, используемые оптимизации решения;
- использовать математический язык и математическую символику при построении моделей;
- обрабатывать эмпирические и экспериментальные данные
владеть
математическими, статистическими и количественными методами решения типовых экономико-математических задач.
Компетенции обучающегося, формируемые в результате освоения дисциплины (модуля) согласно ФГОС ВПО
Процесс изучения дисциплины направлен на формирование следующих компетенций
( ПК-4, ПК-5):
- способен осуществлять сбор, анализ и обработку данных, необходимых для решения поставленных экономических задач (ПК-4);
- способен выбрать инструментальные средства для обработки экономических данных в соответствии с поставленной задачей, проанализировать результаты расчетов и обосновать полученные выводы (ПК-5);
Место дисциплины в структуре профессиональной подготовки выпускника
Дисциплина «Методы оптимальных решений» является базовой дисциплиной математического и естественно научного цикла дисциплин Федерального государственного образовательного стандарта высшего профессионального образования (ФГОС ВПО) по направлению 080100 «Экономика». Для успешного овладения курсом необходимы знания по дисциплинам: «Линейная алгебра», «Математический анализ» «Микроэкономика», «Макроэкономика», «Экономическая информатика», «Компьютерные технологии в экономике». Основные положения дисциплины должны быть использованы в дальнейшем при изучении и решении задач математического и информационного обеспечения экономической деятельности (методы сбора, обработки и представления экономической информации, математического прогнозирования в экономике). Знания и умения, приобретенные студентами в результате изучения дисциплины, будут использоваться при изучении курсов математического моделирования, вычислительного практикума, при выполнении курсовых и дипломных работ, связанных с математическими методами моделирования, обработкой наборов данных, проверкой адекватности построенных моделей, прогнозированием, решением конкретных задач экономики.
3. Тематический план учебной дисциплины по очной форме обучения
Очная форма обучения
Общая трудоемкость дисциплины составляет 4 зачетных единиц 144 часа.
Аудиторных – 48 ч.
Самостоятельная работа (СРС) – 65 ч.
Контроль самостоятельной работы (КСР) – 4 ч.
Форма промежуточной аттестации: экзамен – 3 семестр
| № п/п | Раздел дисциплины | Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах) | Формы текущего контроля успеваемости | Компетенции (ОК.ПК) | ||||
| лекции | практ.з. | лаб.р. | СРС (КСР) | в интеракт.ф. | ||||
| 1. | Введение в методы оптимальных решений | Устный опрос | ПК-4, ПК-5 | |||||
| 2. | Линейное программирование. | 14(1) | Блиц-опрос, защита самостоятельной работы | ПК-4, ПК-5 | ||||
| 3. | Целочисленное программирование | 14(1) | Блиц-опрос, контрольная работа | ПК-4, ПК-5 | ||||
| 4. | Динамическое программирование. | 14(1) | Блиц-опрос, защита самостоятельной работы | ПК-4, ПК-5 | ||||
| 5. | Математическая теория оптимального управления. | 14(1) | Тестирование | ПК-4, ПК-5 | ||||
| Экзамен - 3 семестр | 65(4) |
Тематическое содержание дисциплины
Тема 1. Введение в методы оптимальных решений.
Предмет, история и перспективы развития методов оптимальных управленческих решений. Основные этапы принятия оптимальных управленческих решений. Общая постановка и классификация задач оптимизации. Методы математического программирования.
Тема 2. Линейное программирование.
Постановка и формы записи задачи линейного программирования. Этапы построения моделей. Примеры моделей. Построение моделей задач линейного программирования. Графический метод решения задач линейного программирования. Геометрическая интерпретация задачи. Графический анализ оптимальности решения на чувствительность. Симплекс-метод решения задач линейного программирования. Основная схема алгоритма симплекс-метода. Экономическая интерпретация итоговой симплекс-таблицы. Метод искусственного базиса. Особые случаи применения симплекс – метода (вырожденность, альтернативные оптимальные решения, неограниченные решения, отсутствие допустимых решений). Двойственная модель. Предпосылки к рассмотрению двойственной задачи. Двойственность задач в линейном программировании. Первая теорема двойственности. Вторая теорема двойственности.
Тема 3. Целочисленное программирование
Целочисленные переменные в задачах экономического планирования. Общая задача целочисленного программирования, общая задача целочисленного линейного программирования, задача частично-целочисленного программирования. Геометрическая интерпретация задачи целочисленного программирования. Общая постановка транспортной задачи. Открытая и закрытая ТЗ. Нахождение исходного допустимого базисного решения методом северо-западного угла и методом минимального элемента. Понятие цикла. Метод потенциалов решения транспортной задачи. Алгоритм Гомори. Метод ветвей и границ. Задача о назначениях.
Тема 4. Динамическое программирование.
Модели динамического программирования. Выпуклые множества и их свойства. Экономическая и геометрическая интерпретации. Теорема Вейерштрасса и следствие из неё. Метод множителей Лагранжа в гладких экстремальных задачах с ограничениями типа равенств и неравенств. Задачи выпуклого программирования. Теорема Куна-Таккера. Понятие марковского процесса. Рекуррентные соотношения Беллмана. Принцип оптимальности и математическое описание динамического процесса управления. Оптимальное распределение инвестиций. Выбор оптимальной стратегии обновления оборудования. Модели сетевого планирования и управления. Модели сетевого планирования и управления в условиях неопределенности. Плоские графы; эйлеровы графы; гамильтоновы графы; орграфы; сетевые графики; сети Петри.
Тема 5. Математическая теория оптимального управления.
Математическая теория оптимального управления. Постановка и методы решения задач многокритериальной оптимизации. Примеры многокритериальных задач в экономике. Матричные игры; кооперативные игры; игры с природой. Задачи анализа замкнутых и разомкнутых систем массового обслуживания. Модели систем массового обслуживания в коммерческой деятельности. СМО с отказами. СМО с ожиданием (очередью).
Учебно-методическое обеспечение и календарный график самостоятельной работы студентов
Неотъемлемой частью при изучении дисциплины является самостоятельная работа студента. Ведь умение оригинально, творчески мыслить приходит лишь в результате самостоятельной работы, которая должна начинаться на лекциях, продолжаться на практических, лабораторных занятиях и завершаться самостоятельной работой, в том числе работой с литературой.
Самостоятельная работа содержит:
- самостоятельная работа №1 (конспект по темам №1 -5 указанных в пункте "Задания по самостоятельной работе" или оформленная статья (5-8 стр.) – 10 баллов);
(срок сдачи – до 15 октября текущего года)
- самостоятельная работа №2 (решить задания №1-5 указанных в пункте "Задания по самостоятельной работе" либо принятая на публикацию статья в изданиях Российского уровня, Международного уровня– 20 баллов).
(срок сдачи – до 20 ноября текущего года)
- принятая на публикацию статья в изданиях (журналах) индексируемых в базах Web of Science, Scopus, РИНЦ и в изданиях списка ВАК – оценка «отлично» по дисциплине.
(срок сдачи – до предпоследнего семинарского занятия)
Задания для самостоятельной работы
Самостоятельная работа №1
Необходимо самостоятельно изучить и сделать краткий конспект следующих тем:
Тема 1. Основные этапы принятия оптимальных управленческих решений. Графический анализ оптимальности решения на чувствительность.
Тема 2. Экономическая интерпретация итоговой симплекс-таблицы. Двойственная модель. Предпосылки к рассмотрению двойственной задачи. Двойственность задач в линейном программировании. Первая теорема двойственности. Вторая теорема двойственности.
Тема 3. Общая задача целочисленного программирования, общая задача целочисленного линейного программирования, задача частично-целочисленного программирования. Геометрическая интерпретация задачи целочисленного программирования. Алгоритм Гомори. Метод ветвей и границ. Задача о назначениях.
Тема 4. Выпуклые множества и их свойства. Экономическая и геометрическая интерпретации. Теорема Вейерштрасса и следствие из неё. Задачи выпуклого программирования. Теорема Куна-Таккера. Плоские графы; эйлеровы графы; гамильтоновы графы; орграфы; сетевые графики; сети Петри.
Тема 5. Математическая теория оптимального управления. Примеры многокритериальных задач в экономике. Матричные игры; кооперативные игры; игры с природой. Модели систем массового обслуживания в коммерческой деятельности. СМО с отказами. СМО с ожиданием (очередью).
Самостоятельная работа №2
Необходимо самостоятельно решить следующих 7 заданий по вариантам. Всего вариантов 30. Номер варианта соответсвует номеру списка в группе.
Задание. 1
Решить графическим методом задачи с двумя переменными. Провести полный графический анализ чувствительности. (табл. 1).
Задание. 2
Решить симплексным методом задачи (табл. 2).
Задание. 3
Решить методом потенциалов транспортные задачи (опорное решение использовать найденное методом северо-западного угла) (табл. 3).
Таблица 1. Варианты задания 1
Таблица 2. Варианты задания 2
Таблица 3. Варианты задания 3 
Задание 4.
4.1. Система управления запасами некоторого вида товара подчиняется условиям основной модели. Каждый год с постоянной интенсивностью поступает спрос на 15 тыс. единиц товара, издержки на организацию поставки составляют 10 долл. за одну партию, цена единицы товара — 3 долл., а издержки на ее хранение — 0,75 долл. в год. Найдите оптимальный размер партии, продолжительность цикла, число поставок за год, если стратегия управления запасами в предыдущей задаче является оптимальной?
4.2.Система управления запасами описывается моделью производственных поставок и имеет следующие значения параметров. Спрос равен 1,5 тыс. единиц в год, цена 2 долл., издержки хранения единицы товара в течение года — 0,2 долл., организационные издержки —10 долл. В течение года может быть произведено 4,5 тыс. единиц товара при полной загрузке производственной линии. Нарисуйте график изменения запасов, вычислите оптимальный размер партии, продолжительность поставки, продолжительность цикла и средний уровень запасов.
4.3.Интенсивность спроса в модели производственных поставок составляет четверть скорости производства, которая равна 20 тыс. единиц товара в год. Организационные издержки для одной партии равны 150 долл., а издержки хранения единицы товара в течение года —0,3 долл. Определите оптимальный размер партии.
4.4.Мебельной фирме требуется 1000 штук дверных ручек в год, расходуемых с постоянной интенсивностью. Организационные издержки составляют 30 долл. за партию, издержки на хранение одной ручки оценены в 1 долл. Цена дверной ручки составляет 2 долл., а при закупке партиями объемом не менее 750 штук — 1,9 долл. за штуку. Найдите оптимальный размер партии поставок.
4.5.Торговец имеет стабильный спрос на некоторый товар в количестве 500 единиц в год. Товар он покупает у поставщика по цене 6 долл. за штуку, причем издержки на оформление поставки и другие подготовительные операции составляют в каждом случае
10 долл. Если торговец покупает сразу партию в количестве 150 единиц товара или более, цена сбавляется до 5 долл. за штуку. Каков оптимальный размер партии, если годовые затраты на хранение единицы товара равны 1 долл.?
4.6. Система управления запасами некоторого вида товара подчиняется условиям основной модели. Каждый год с постоянной интенсивностью поступает спрос на 20 тыс. единиц товара, издержки на организацию поставки составляют 10 долл. за одну партию, цена единицы товара — 3 долл., а издержки на ее хранение — 1 долл. в год. Найдите оптимальный размер партии. Каковы будут а) продолжительность цикла и б) число поставок за год, если стратегия управления запасами в предыдущей задаче является оптимальной?
4.7.Система управления запасами описывается моделью производственных поставок и имеет следующие значения параметров. Спрос равен 1,5 тыс. единиц в год, цена 3 долл., издержки хранения единицы товара в течение года — 2 долл., организационные издержки —10 долл. В течение года может быть произведено 4,5 тыс. единиц товара при полной загрузке производственной линии. Нарисуйте график изменения запасов, вычислите оптимальный размер партии, продолжительность поставки, продолжительность цикла и средний уровень запасов.
4.8.Интенсивность спроса в модели производственных поставок составляет треть скорости производства, которая равна 21 тыс. единиц товара в год. Организационные издержки для одной партии равны 150 долл., а издержки хранения единицы товара в течение года —0,3 долл. Определите оптимальный размер партии.
4.9.Фирме требуется 2000 штук единиц товара в год, расходуемых с постоянной интенсивностью. Организационные издержки составляют 30 долл. за партию, издержки на хранение одной единицы товара оценены в 1 долл. Цена единицы товара составляет 2 долл., а при закупке партиями объемом не менее 750 штук — 1,9 долл. за штуку. Найдите оптимальный размер партии поставок.
4.10.Торговец имеет стабильный спрос на некоторый товар в количестве 1500 единиц в год. Товар он покупает у поставщика по цене 5 долл. за штуку, причем издержки на оформление поставки и другие подготовительные операции составляют в каждом случае
10 долл. Если торговец покупает сразу партию в количестве 150 единиц товара или более, цена сбавляется до 4 долл. за штуку. Каков оптимальный размер партии, если годовые затраты на хранение единицы товара равны 1 долл.?
4.11.Система управления запасами некоторого вида товара подчиняется условиям основной модели. Каждый год с постоянной интенсивностью поступает спрос на 25 тыс. единиц товара, издержки на организацию поставки составляют 5 долл. за одну партию, цена единицы товара — 3 долл., а издержки на ее хранение — 1 долл. в год. Найдите оптимальный размер партии. Каковы будут а) продолжительность цикла и б) число поставок за год, если стратегия управления запасами в предыдущей задаче является оптимальной?
4.12.Система управления запасами описывается моделью производственных поставок и имеет следующие значения параметров. Спрос равен 3,5 тыс. единиц в год, цена 2 долл., издержки хранения единицы товара в течение года — 1 долл., организационные издержки —5 долл. В течение года может быть произведено 4 тыс. единиц товара при полной загрузке производственной линии. Нарисуйте график изменения запасов, вычислите оптимальный размер партии, продолжительность поставки, продолжительность цикла и средний уровень запасов.
4.13.Интенсивность спроса в модели производственных поставок составляет одну пятую скорости производства, которая равна 20 тыс. единиц товара в год. Организационные издержки для одной партии равны 150 долл., а издержки хранения единицы товара в течение года —0,3 долл. Определите оптимальный размер партии.
4.14.Фирме требуется 2500 штук ручек в год, расходуемых с постоянной интенсивностью. Организационные издержки составляют 30 долл. за партию, издержки на хранение одной ручки оценены в 1 долл. Цена дверной ручки составляет 2 долл., а при закупке партиями объемом не менее 750 штук — 1,9 долл. за штуку. Найдите оптимальный размер партии поставок.
4.15.Торговец имеет стабильный спрос на некоторый товар в количестве 2500 единиц в год. Товар он покупает у поставщика по цене 10 долл. за штуку, причем издержки на оформление поставки и другие подготовительные операции составляют в каждом случае
8 долл. Если торговец покупает сразу партию в количестве 550 единиц товара или более, цена сбавляется до 9 долл. за штуку. Каков оптимальный размер партии, если годовые затраты на хранение единицы товара равны 3 долл.?
4.16.Система управления запасами некоторого вида товара подчиняется условиям основной модели. Каждый год с постоянной интенсивностью поступает спрос на 10 тыс. единиц товара, издержки на организацию поставки составляют 7 долл. за одну партию, цена единицы товара — 2 долл., а издержки на ее хранение — 3 долл. в год. Найдите оптимальный размер партии. Каковы будут а) продолжительность цикла и б) число поставок за год, если стратегия управления запасами в предыдущей задаче является оптимальной?
4.17.Система управления запасами описывается моделью производственных поставок и имеет следующие значения параметров. Спрос равен 1,5 тыс. единиц в год, цена 2 долл., издержки хранения единицы товара в течение года — 0,2 долл., организационные издержки —10 долл. В течение года может быть произведено 4,5 тыс. единиц товара при полной загрузке производственной линии. Нарисуйте график изменения запасов, вычислите оптимальный размер партии, продолжительность поставки, продолжительность цикла и средний уровень запасов.
4.18.Система управления запасами некоторого вида товара подчиняется условиям основной модели. Каждый год с постоянной интенсивностью поступает спрос на 45 тыс. единиц товара, издержки на организацию поставки составляют 10 долл. за одну партию, цена единицы товара — 3 долл., а издержки на ее хранение — 4 долл. в год. Найдите оптимальный размер партии. Каковы будут а) продолжительность цикла и б) число поставок за год, если стратегия управления запасами в предыдущей задаче является оптимальной?
4.19.Система управления запасами описывается моделью производственных поставок и имеет следующие значения параметров. Спрос равен 2,5 тыс. единиц в год, цена 2 долл., издержки хранения единицы товара в течение года — 2,2 долл., организационные издержки —10 долл. В течение года может быть произведено 6,5 тыс. единиц товара при полной загрузке производственной линии. Нарисуйте график изменения запасов, вычислите оптимальный размер партии, продолжительность поставки, продолжительность цикла и средний уровень запасов.
4.20.Интенсивность спроса в модели производственных поставок составляет четверть скорости производства, которая равна 28 тыс. единиц товара в год. Организационные издержки для одной партии равны 250 долл., а издержки хранения единицы товара в течение года —3 долл. Определите оптимальный размер партии.
4.21.Мебельной фирме требуется 4000 штук дверных ручек в год, расходуемых с постоянной интенсивностью. Организационные издержки составляют 30 долл. за партию, издержки на хранение одной ручки оценены в 10 долл. Цена дверной ручки составляет 5 долл., а при закупке партиями объемом не менее 1000 штук — 4 долл. за штуку. Найдите оптимальный размер партии поставок.
4.22.Торговец имеет стабильный спрос на некоторый товар в количестве 3500 единиц в год. Товар он покупает у поставщика по цене 7 долл. за штуку, причем издержки на оформление поставки и другие подготовительные операции составляют в каждом случае
10 долл. Если торговец покупает сразу партию в количестве 650 единиц товара или более, цена сбавляется до 5 долл. за штуку. Каков оптимальный размер партии, если годовые затраты на хранение единицы товара равны 3 долл.?
4.23.Система управления запасами некоторого вида товара подчиняется условиям основной модели. Каждый год с постоянной интенсивностью поступает спрос на 35 тыс. единиц товара, издержки на организацию поставки составляют 10 долл. за одну партию, цена единицы товара — 4 долл., а издержки на ее хранение — 1,5 долл. в год. Найдите оптимальный размер партии. Каковы будут а) продолжительность цикла и б) число поставок за год, если стратегия управления запасами в предыдущей задаче является оптимальной?
4.24.Система управления запасами описывается моделью производственных поставок и имеет следующие значения параметров. Спрос равен 2,5 тыс. единиц в год, цена 2 долл., издержки хранения единицы товара в течение года — 2 долл., организационные издержки —12 долл. В течение года может быть произведено 3,5 тыс. единиц товара при полной загрузке производственной линии. Нарисуйте график изменения запасов, вычислите оптимальный размер партии, продолжительность поставки, продолжительность цикла и средний уровень запасов.
4.25.Интенсивность спроса в модели производственных поставок составляет четверть скорости производства, которая равна 24 тыс. единиц товара в год. Организационные издержки для одной партии равны 150 долл., а издержки хранения единицы товара в течение года —0,3 долл. Определите оптимальный размер партии.
4.26.Мебельной фирме требуется 3000 штук дверных ручек в год, расходуемых с постоянной интенсивностью. Организационные издержки составляют 10 долл. за партию, издержки на хранение одной ручки оценены в 2 долл. Цена дверной ручки составляет 2 долл., а при закупке партиями объемом не менее 850 штук — 1,5 долл. за штуку. Найдите оптимальный размер партии поставок.
4.27.Торговец имеет стабильный спрос на некоторый товар в количестве 4500 единиц в год. Товар он покупает у поставщика по цене 6 долл. за штуку, причем издержки на оформление поставки и другие подготовительные операции составляют в каждом случае
10 долл. Если торговец покупает сразу партию в количестве 950 единиц товара или более, цена сбавляется до 5 долл. за штуку. Каков оптимальный размер партии, если годовые затраты на хранение единицы товара равны 3 долл.?
4.28.Система управления запасами некоторого вида товара подчиняется условиям основной модели. Каждый год с постоянной интенсивностью поступает спрос на 35 тыс. единиц товара, издержки на организацию поставки составляют 10 долл. за одну партию, цена единицы товара — 4 долл., а издержки на ее хранение — 1,5 долл. в год. Найдите оптимальный размер партии. Каковы будут а) продолжительность цикла и б) число поставок за год, если стратегия управления запасами в предыдущей задаче является оптимальной?
4.29.Система управления запасами описывается моделью производственных поставок и имеет следующие значения параметров. Спрос равен 2,5 тыс. единиц в год, цена 2 долл., издержки хранения единицы товара в течение года — 2 долл., организационные издержки —12 долл. В течение года может быть произведено 3,5 тыс. единиц товара при полной загрузке производственной линии. Нарисуйте график изменения запасов, вычислите оптимальный размер партии, продолжительность поставки, продолжительность цикла и средний уровень запасов.
4.30.Система управления запасами некоторого вида товара подчиняется условиям основной модели. Каждый год с постоянной интенсивностью поступает спрос на 30 тыс. единиц товара, издержки на организацию поставки составляют 6 долл. за одну партию, цена единицы товара — 4 долл., а издержки на ее хранение — 2,5 долл. в год. Найдите оптимальный размер партии. Каковы будут а) продолжительность цикла и б) число поставок за год, если стратегия управления запасами в предыдущей задаче является оптимальной?
Задание 5
5.1.Телефонная компания планирует соединить подземным кабелем шесть городов, расстояния между которыми заданы при помощи таблицы:
| А | В | С | D | Е | F | |
| А | — | |||||
| В | — | |||||
| С | — | |||||
| D | — | |||||
| Е | — | |||||
| F | — |
Найдите минимальную длину кабеля, позволяющего жителям любых двух городов связаться друг с другом по телефону.
Рис. 1
5.2.Найдите кратчайшие маршруты, ведущие из узла А во все другие узлы сети, представленной на рис. 1.
Рис. 2
5.3.Найдите максимальный поток в сети, представленной на рис. 2
(исходный узел — 1, конечный узел — 7).
5.4.Найдите критический путь для цикла работ А(3), В(6), С(12), D(9), E(11), F(3), G(5), Н(7) и I(3) (в скобках указана продолжительность соответствующего вида работы в днях) и минимальное время, необходимое для выполнения всего цикла, если последовательность операций подчинена следующим требованиям: работа D должна следовать за работой Е, Е— за А и В, F — за D и G, G —за Е, Н — за G, I — за С и F.
5.5.Телефонная компания планирует соединить подземным кабелем шесть городов, расстояния между которыми заданы при помощи таблицы:
| А | В | С | D | Е | |
| А | — | ||||
| В | — | ||||
| С | — | ||||
| D | — | ||||
| Е | — |
Найдите минимальную длину кабеля, позволяющего жителям любых двух городов связаться друг с другом по телефону.
Рис. 3
5.6.Найдите кратчайшие маршруты, ведущие из узла А во все другие узлы сети, представленной на рис. 3.
5.7.Найдите максимальный поток в сети, представленной на рис. 4
Рис. 4
(исходный узел — 1, конечный узел — 7).
5.8.Найдите критический путь для цикла работ А(5), B(9), С(11), D(9), E(10), F(3), G(5), Н(7) и I(3) (в скобках указана продолжительность соответствующего вида работы в днях) и минимальное время, необходимое для выполнения всего цикла, если последовательность операций подчинена следующим требованиям: работа D должна следовать за работой Е, Е— за А и В, F — за D и G, G —за Е, Н — за G, I — за С и F.
5.9.Телефонная компания планирует соединить подземным кабелем шесть городов, расстояния между которыми заданы при помощи таблицы:
| А | В | С | D | |
| А | — | |||
| В | — | |||
| С | — | |||
| D | — |
Найдите минимальную длину кабеля, позволяющего жителям любых двух городов связаться друг с другом по телефону.
Рис. 5
5.10.Найдите кратчайшие маршруты, ведущие из узла А во все другие узлы сети, представленной на рис. 5.
Рис. 6
5.11.Найдите максимальный поток в сети, представленной на рис. 6
(исходный узел — 1, конечный узел — 7).
5.12.Найдите критический путь для цикла работ А(12), В(16), С(2), D(9), E(12), F(3), G(5), Н(7) и 1(3) (в скобках указана продолжительность соответствующего вида работы в днях) и минимальное время, необходимое для выполнения всего цикла, если последовательность операций подчинена следующим требованиям: работа D должна следовать за работой Е, Е— за А и В, F — за D и G, G —за Е, Н — за G, I — за С и F.
5.13.Телефонная компания планирует соединить подземным кабелем шесть городов, расстояния между которыми заданы при помощи таблицы:
| А | В | С | D | Е | |
| А | — | ||||
| В | — | ||||
| С | — | ||||
| D | — | ||||
| Е | — |
Найдите минимальную длину кабеля, позволяющего жителям любых двух городов связаться друг с другом по телефону.
Рис. 7
5.14.Найдите кратчайшие маршруты, ведущие из узла А во все другие узлы сети, представленной на рис. 7.
Рис. 8
5.15.Найдите максимальный поток в сети, представленной на рис. 8
(исходный узел — 1, конечный узел — 7).
5.16.Найдите критический путь для цикла работ А(7), B(9), С(13), D(11), E(10), F(4), G(5), Н(7) и I(3) (в скобках указана продолжительность соответствующего вида работы в днях) и минимальное время, необходимое для выполнения всего цикла, если последовательность операций подчинена следующим требованиям: работа D должна следовать за работой Е, Е— за А и В, F — за D и G, G —за Е, Н — за G, I — за С и F.
5.17.Телефонная компания планирует соединить подземным кабелем шесть городов, расстояния между которыми заданы при помощи таблицы:
| А | В | С | D | Е | F | |
| А | — | |||||
| В | — | |||||
| С | — | |||||
| D | — | |||||
| Е | — | |||||
| F | — |
Найдите минимальную длину кабеля, позволяющего жителям любых двух городов связаться друг с другом по телефону.
Рис. 9
5.18.Найдите кратчайшие маршруты, ведущие из узла А во все другие узлы сети, представленной на рис. 9.
Рис. 33
5.19. Найдите максимальный поток в сети, представленной на рис. 33
(исходный узел — 1, конечный узел — 7).
5.20.Найдите критический путь для цикла работ А(3), В(6), С(16), D(9), E(15), F(3), G(4), Н(7) и 1(3) (в скобках указана продолжительность соответствующего вида работы в днях) и минимальное время, необходимое для выполнения всего цикла, если последовательность операций подчинена следующим требованиям: работа D должна следовать за работой Е, Е— за А и В, F — за D и G, G —за Е, Н — за G, I — за С и F.
5.21.Телефонная компания планирует соединить подземным кабелем шесть городов, расстояния между которыми заданы при помощи таблицы:
| А | В | С | D | Е | |
| А | — | ||||
| В | — | ||||
| С | — | ||||
| D | — | ||||
| Е | — |
Найдите минимальную длину кабеля, позволяющего жителям любых двух городов связаться друг с другом по телефону.
Рис. 10
5.22.Найдите кратчайшие маршруты, ведущие из узла А во все другие узлы сети, представленной на рис. 10.
Рис. 11
5.23.Найдите максимальный поток в сети, представленной на рис. 11
(исходный узел — 1, конечный узел — 7).
5.24.Найдите критический путь для цикла работ А(7), B(9), С(8), D(4), E(10), F(3), G(5), Н(12) и I(3) (в скобках указана продолжительность соответствующего вида работы в днях) и минимальное время, необходимое для выполнения всего цикла, если последовательность операций подчинена следующим требованиям: работа D должна следовать за работой Е, Е— за А и В, F — за D и G, G —за Е, Н — за G, I — за С и F.
5.25.Телефонная компания планирует соединить подземным кабелем шесть городов, расстояния между которыми заданы при помощи таблицы:
| А | В | С | D | Е | |
| А | — | ||||
| В | — | ||||
| С | — | ||||
| D | — | ||||
| Е | — |
Найдите минимальную длину кабеля, позволяющего жителям любых двух городов связаться друг с другом по телефону.
Рис. 12
5.26.Найдите кратчайшие маршруты, ведущие из узла А во все другие узлы сети, представленной на рис. 12.
Рис. 13
5.27.Найдите максимальный поток в сети, представленной на рис. 13
(исходный узел — 1, конечный узел — 7).
5.28.Найдите критический путь для цикла работ А(6), 5(19), С(10), D(9), E(11), F(3), G(5), Н(7) и 1(3) (в скобках указана продолжительность соответствующего вида работы в днях) и минимальное время, необходимое для выполнения всего цикла, если последовательность операций подчинена следующим требованиям: работа D должна следовать за работой Е, Е— за А и В, F — за D и G, G —за Е, Н — за G, I — за С и F.
5.29.Телефонная компания планирует соединить подземным кабелем шесть городов, расстояния между которыми заданы при помощи таблицы: