Руководство по изучению дисциплины «Организационное управление» icon

Руководство по изучению дисциплины «Организационное управление»


Смотрите также:
Методические рекомендации по изучению дисциплины организационное поведение для студентов...
Руководство по самостоятельному изучению дисциплины «Математика» для специальностей: 130404...
Учебное пособие Руководство по изучению дисциплины Практикум...
Учебное пособие Руководство по изучению дисциплины Практикум...
Руководство по изучению дисциплины “Реинжиниринг и управление бизнес-процессами...
Руководство по изучению дисциплины «Разработка и стандартизация программных средств и...
Антикризисное управление пособие по изучению дисциплины и выполнению контрольных работ для...
Программа дисциплины опд. Ф. 09. Организационное поведение Цели и задачи дисциплины...
Руководство по изучению дисциплины «история отечественной литературы серебряный век»...
Рабочая программа дисциплина «Организационное поведение» Направление подготовки (специальность)...
Соколова М. М. Организационное поведение: Управление поведением людей организации...
Руководство по изучению Дисциплины...



Загрузка...
скачать
Руководство по изучению дисциплины

«Организационное управление»


1. Цель и задачи курса


Цель курса – познакомить студента с основами исследования операций и принятия оптимальных управленческих решений в проектной, производственной, экономической, финансовой и бизнес-сферах. Основные задачи изучения данного курса заключаются в приобретении студентами теоретических знаний и практических навыков по следующим направлениям:

  • основы теории и практики принятия управленческих решений;

  • методология системного анализа и исследования операций;

  • принципы построения математических моделей принятия решений;

  • особенности и возможности основных классов оптимизационных моделей;

  • основные подходы и методы решения задач оптимизации;

  • программные средства решения задач оптимизации.


2. Содержание курса

^

Тема 1. Организационное управление как наука о принятии оптимальных

управленческих решений


  • Примеры типовых задач организационного управления: Задача распределения ресурсов. Транспортная задача. Задача о назначении (управление персоналом). Управление товарными запасами. Минимальный остов графа. Кратчайший и критический пути в графе. Задача коммивояжёра. Максимальный поток в сети. Поток минимальной стоимости.

  • ^ Методология системного анализа задач организационного управления: Анализ проблемной ситуации. Построение математической модели. Анализ и классификация модели. Выбор методов решения. Выбор программных средств решения. Выполнение численных расчетов. Анализ и применение результатов оптимизации. Коррекция и доработка модели.

Литература: [1]: с.21-29, 69-94; [2]: с.9-57; [3]: с.15-81; [7]: с.6-11;

^

Тема 2. Математическое программирование в организационном управлении


  • Линейное программирование: Основные утверждения линейного программирования. Симплекс-метод при известном базисном решении. Модифицированный (матричный) симплекс-метод. Метод искусственного базиса для нахождения начального решения. Двухэтапный симплекс-метод.

  • ^ Целочисленное программирование: Примеры задач целочисленного программирования. Математическая постановка задачи целочисленного программирования. Метод ветвей и границ. Решение задач целочисленного программирования в MS Excel.

  • ^ Булево программирование: Примеры задач булева программирования. Математическая постановка задачи булева программирования. Решение задач булева программирования в MS Excel.

Литература: [1]: с.95-140, 397-428; [2]: с.142-146, 205-211, 294-297; [3]: с.82-187; [7]: с.11-134, 175-192;


^ Тема 3. Типовые модели организационного управления

  • Детерминированные модели управления запасами: Классические модели управления запасами. Многопродуктовая динамическая модель управления запасами. Решение задач управления запасами в MS Excel. Нестандартные задачи, сводящиеся к управлению запасами.

  • ^ Транспортные модели: Классическая транспортная задача. Многопродуктовая транспортная задача. Решение транспортных задач в MS Excel. Нестандартные задачи, сводящиеся к транспортным.

  • ^ Модели управления трудовыми ресурсами: Классическая задача о назначении. Решение задачи о назначении в MS Excel. Нестандартные задачи, сводящиеся к задаче о назначении.

Литература: [1]: с.193-242, 471-506; [2]: с.181-199, 238-247, 275-291; [3]: с.188-210, 215-238; [7]: с.134-174;


^ Тема 4. Кратчайшие пути в графах

  • Минимальный остов графа: Определение минимального остова графа. Задачи организационного управления, приводящие к минимальному остову графа. Алгоритм Прима поиска минимального остова графа. Минимальный остов графа как задача булева программирования. Способы представления графов в MS Excel. Нахождение минимального остова графа в MS Excel.

  • ^ Минимальный и максимальный пути в графе: Постановка задачи о минимальном пути в графе. Алгоритм Дейкстры поиска минимального пути. Нестандартные задачи, сводящиеся к минимальному пути. Постановка задачи о максимальном пути в графе. Алгоритм поиска максимального пути. Понятие о сетевом планировании и управлении. Минимальный и максимальный пути в графе как задачи булева программирования. Нахождение минимального и максимального путей средствами MS Excel.

  • ^ Задача коммивояжёра: Постановка задачи коммивояжёра в терминах булева программирования. Решение задачи коммивояжёра средствами MS Excel. Нестандартные задачи, сводящиеся к задаче коммивояжёра.

Литература: [1]: с.243-269, 299-320, 428-437; [2]: с.294-342, 358-377; [3]: с.210-215;


^ Тема 5. Потоки в сетях

  • Максимальный поток в сети: Постановка задачи о максимальном потоке в сети. Теорема Форда-Фалкерсона и алгоритм нахождения максимального потока. Максимальный поток как задача линейного программирования. Нахождение максимального потока средствами MS Excel. Нестандартные задачи, сводящиеся к максимальному потоку.

  • ^ Поток минимальной стоимости: Постановка задачи о потоке минимальной стоимости. Поток минимальной стоимости как задача математического программирования. Нахождение потока минимальной стоимости средствами MS Excel. Нестандартные задачи, сводящиеся к потоку минимальной стоимости.

Литература: [1]: с.269-299; [2]: с.342-357;


^ 3. Перечень рекомендуемой литературы


Основная литература:


  1. Таха Х. Введение в исследование операций, 7-е издание: Пер с англ. – М: Издательский дом «Вильямс», 2005. – 912с. (+ CD).




  1. Леоненков А.В. Решение задач оптимизации в среде MS Excel. – СПб: БХВ-Петербург, 2005. – 704с.




  1. Волков И.К., Загоруйко Е.А. Исследование операций: Учеб. для вузов. – М: Изд-во МГТУ им. Н.Э.Баумана, 2004. – 440с.




  1. Васин А.А., Краснощёков П.С., Морозов В.В. Исследование операций: Учеб. пособие для вузов. – М: Академия, 2008. – 464с.




  1. Исследование операций в экономике: Учеб. пособие для вузов / Под ред. Н.Ш.Кремера. – М: Маркет ДС, 2007. – 408с. – (Университетская серия).




  1. Афанасьев М.Ю., Суворов Б.П. Исследование операций в экономике: модели, задачи, решения: Учеб. пособие. – М: ИНФРА-М, 2003. – 444с.


Дополнительная литература:


  1. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для вузов. – 2-е изд., испр. – СПб: «Лань», 2009. – 352с.




  1. Давыдов Э.Г. Исследование операций: Учеб. пособие для вузов по спец. «Прикладная математика» и «Экон. кибернетика» - М: Высшая школа, 1990. – 383с.




  1. Дегтярёв Ю.И. Исследование операций: Учебник для вузов. – М: Высш. шк., 1986. – 320с.




  1. Вентцель Е.С. Исследование операций. – М: Сов. радио, 1972. – 543с.




  1. Коршунов Ю.М. Математические основы кибернетики: Учеб. пособие для вузов. – М: Энергоатомиздат, 1987. – 496с.




  1. Вагнер Г. Основы исследования операций / Пер. с англ. В 3-х томах. Т. 1. – М: Мир, 1972. – 336с.; Т. 2. – М: Мир, 1973. – 488с.; Т. 3 – М: Мир, 1973. – 504с.




  1. Род Стивенс. Delphi. Готовые алгоритмы. – М: ДМК Пресс; СПб: Питер, 2004. – 384с. (алгоритмы на графах).



4. Методические указания по изучению тем и вопросы для самопроверки

^

Тема 1. Организационное управление как наука о принятии оптимальных

управленческих решений


При изучении темы следует помнить, что исследование операций и принятие решений – это высший уровень в структуре автоматизированных систем управления, главным звеном которого является человек – Лицо, Принимающее Решения (ЛПР). Нужно чётко понимать различия функций автоматизированной системы, исследователя операций (системного аналитика) и ЛПР. Исследователь операций с помощью математических и программных средств подготавливает предложения по организационным мероприятиям, а ЛПР соглашается с ними или нет, а также вносит коррективы.


Характерные черты операционного подхода:

  1. ^ Ориентация на принятие решения. Основные результаты должны иметь непосредственное и полностью определённое отношение к выбору способа действий (т.е. стратегии или тактики).

  2. ^ Оценка технической или экономической эффективности. Сравнение различных вариантов действий должно основываться на количественных оценках, позволяющих однозначно определить полезность принятых решений для рассматриваемой организации.

  3. ^ Адекватность математической модели. Процедуры обработки параметров производственного или бизнес-процесса должны быть определены настолько точно, что при одних и тех же исходных данных различные специалисты-аналитики должны получать одинаковые результаты.

  4. ^ Необходимость использования ЭВМ. Это обусловливается сложностью используемых математических моделей, большими объёмами данных и громоздкостью вычислительных процедур, обеспечивающих системы управления и контроля.


Следует уяснить, что разработка моделей является квинтэссенцией опрационного подхода к решению организационных задач. Построение модели позволяет привести факторы, связанные с проблемой принятия решения, в логически стройную схему, доступную для детального анализа. Такая модель позволяет выявить альтернативы решения задачи и оценить результаты, а также даёт возможность определить данные, необходимые для оценки имеющихся альтернатив.


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


^ Контрольные вопросы для самопроверки:

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

  2. Перечислите основные этапы постановки и решения задач оптимизации.

  3. В чём заключается и какую цель преследует анализ проблемной ситуации?

  4. На каких принципах базируется процесс построения математической модели?

  5. Какие требования предъявляются к модели оптимизируемой системы?

  6. Какой степенью точности должна обладать модель оптимизируемой системы?

  7. Как определяются границы модели по охвату влияющих факторов?

  8. Перечислите и поясните основные элементы математической модели оптимизируемой системы.

  9. По каким признакам можно классифицировать математическую модель оптимизации?

  10. По каким соображениям выбирается метод решения задачи оптимизации?

  11. Какие Вы знаете программные средства оптимизации?

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

  13. Какими способами можно оценить достоверность найденного решения?

  14. Почему после решения задачи оптимизации может потребоваться коррекция модели и повторение процесса решения?



^

Тема 2. Математическое программирование в организационном управлении


При изучении темы следует обратить внимание на основные утверждения линейного программирования:

  • ограничения задачи образуют выпуклый многогранник, который называется симплексом;

  • решение задачи находится в одной из вершин симплекса и представляет собой одно из опорных (базисных) решений;

  • в каждой из вершин симплекса не равны нулю столько переменных, сколько ограничений-равенств в стандартной постановке задачи; остальные переменные равны нулю;

  • переменные, не равные нулю, называются базисными, а остальные (равные нулю) – небазисными (свободными).

Эти утверждения хорошо иллюстрируются графоаналитическим методом для двух переменных и лежат в основе симплекс-метода.


Следует хорошо уяснить основную идею симплекс-метода: начиная с некоторой угловой точки производится направленный перебор соседних вершин симплекса. При этом перебираются не все, а только ограниченное число вершин, ведущих к улучшению значения целевой функции. Для перехода к соседней вершине одна из свободных переменных вводится в базис, а одна из базисных – выводится из базиса и становится свободной (раной нулю). Координаты новой вершины получают решением системы N линейных уравнений (по числу ограничений-равенств) методом Гаусса-Жордана относительно базисных переменных.


Особое внимание в симплекс-методе следует обратить на условие оптимальности и условие допустимости, из которых вытекают правила для выбора переменной, вводимой в базис, и переменной, выводимой из базиса. Выполнение этих условий гарантирует переход к соседней вершине симплекса с улучшенным значением целевой функции.


Нужно уяснить, что в модифицированном (матричном) симплекс-методе в отличие от обычного на каждой итерации вместо процедуры Гаусса-Жордана используется обращение матрицы коэффициентов ограничений при базисных переменных. Поэтому данный метод имеет второе название – метод обратной матрицы.


Важно знать и понимать, что симплекс-метод начинает работу только с какого-либо базисного решения, которое, как правило, неизвестно. Для получения одного из базисных решений используется метод искусственного базиса, который позволяет запустить симплекс-метод из специально созданной искусственной вершины, удовлетворяющей ограничениям задачи, и в результате получить одну из реальных угловых точек. Таким образом, общая процедура решения задачи содержит два этапа (двухэтапный метод):

  • получение допустимого базисного решения методом искусственного базиса;

  • уточнение решения до оптимального симплекс-методом.


Очень важное значение имеют задачи целочисленного программирования, в которых фигурируют штучные материальные ресурсы. Математическая постановка таких задач содержит переменные, которые могут принимать только целые значения. Следует помнить, что такие задачи, с одной стороны, не могут быть решены обычными методами оптимизации, а с другой стороны, округление результатов совершенно неприемлемо по теоретическим и практическим соображениям. Для решения таких задач разработаны специальные методы, дополняющие процедуру оптимизации: метод ветвей и границ, метод Гомори и другие. Наиболее универсальным и эффективным в общем случае является метод ветвей и границ, или метод возврата.


Следует хорошо уяснить основные принципы метода ветвей и границ:

  1. При получении недопустимого (нецелочисленного) решения задача путём введения искусственных ограничений разбивается на две подзадачи («ветвление»), которые могут иметь целочисленное решение. Для запоминания и хранения подзадач формируется их список в виде дерева.

  2. Из списка поочередно выбираются подзадачи и решаются (симплекс-методом или методами НЛП) до получения допустимого целочисленного решения или выявления отсутствия допустимого решения. Если полученное целочисленное решение по значению целевой функции хуже ранее найденного («границы»), то дальнейшее ветвление прекращается («возврат»). В случае получения решения, по значению целевой функции лучшего границы, оно принимается за границу.


Важно знать и понимать, что метод ветвей и границ реализует ограниченный (часто почти полный) перебор допустимых решений и тем самым на несколько порядков увеличивает вычислительную сложность решения. Поэтому при постановке задачи следует придерживаться следующих рекомендаций [1]:

  1. По возможности аппроксимировать целочисленные переменные непрерывными.

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

  3. Избегать в модели задачи нелинейных функций.


Особо следует отметить, что метод ветвей и границ применим к задачам как линейного, так и нелинейного программирования.


Очень важное место в организационном управлении занимает булево программирование, к которому приводят задачи оптимизации на графах, задачи комбинаторной оптимизации и многие другие. Следует помнить, что термин «булево программирование» – не совсем точный, так как на самом деле в этих задачах переменные принимают не логические, а арифметические двоичные значения 0 и 1. В частности, это касается пакета Excel.


Задачи булева программирования можно рассматривать как частный случай целочисленных, поэтому к ним применим метод ветвей и границ с той особенностью, что ветвление по каждой переменной происходит по значениям 0 и 1 без введения дополнительных ограничений. Кажущаяся простота таких задач по сравнению с целочисленными привела к разработке многочисленных эвристических методов их решения, которые основаны на специально сконструированных тестах для определения целесообразности дальнейшего ветвления. Однако практика показала, что в большинстве случаев более эффективным оказывается метод ветвей и границ. Кроме того, эвристические методы годятся только для задач линейного программирования.


Метод ветвей и границ используется в MS Excel для решения задач целочисленного и булева программирования. Для подключения метода достаточно в окне «Поиск решения» добавить ограничение на целочисленность или двоичность переменных.


Контрольные вопросы для самопроверки:

  1. Перечислите основные утверждения линейного программирования.

  2. Какие переменные называются базисными и небазисными (свободными)?

  3. Как выразить целевую функцию и ограничения через свободные переменные?

  4. Поясните суть условия допустимости в симплекс-методе.

  5. В чём состоит условие оптимальности в симплекс-методе?

  6. Перечислите и поясните основные шаги симплекс-метода при известном базисном решении.

  7. Поясните назначение и суть метода искусственного базиса.

  8. В чём особенность математической постановки задачи целочисленного программирования?

  9. Поясните принцип ветвления в методе ветвей и границ.

  10. Как формируется последовательность подзадач в методе ветвей и границ?

  11. Поясните суть термина «граница» в методе ветвей и границ.

  12. Перечислите и поясните основные шаги метода ветвей и границ.

  13. Почему метод ветвей и границ имеет второе название «метод возврата»?

  14. В чём особенность математической постановки задачи булева программирования?

  15. Как применить метод ветвей и границ для решения задач булева программирования?

  16. В чём особенность решения задач целочисленного и булева программирования в MS Excel?


Тема 3. Типовые модели организационного управления

При изучении детерминированных моделей управления запасами следует уяснить ограниченность сфер применения классических моделей управления запасами. Так, многопродуктовая статическая модель не позволяет учесть изменение спроса на товары во времени, а динамические модели с переменным спросом описывают изменение запаса только по одному вида товара, причём для решения задачи используется метод динамического программирования, который требует огромных вычислительных затрат. Поэтому классические модели не позволяют решать реальные задачи организационного управления.


В связи с изложенным особое внимание следует обратить на многопродуктовую динамическую модель управления запасами, изложенную в лекциях по курсу. Нужно хорошо уяснить суть и назначение основных элементов модели:

  • динамика спроса по времени на каждый вид товара;

  • динамика закупки товаров;

  • величина остатков товаров на складе;

  • схема изменения уровня запаса каждого товара;

  • уравнения баланса товаров на складе;

  • составляющие затрат на поддержание запасов (закупка и хранение) с учётом оптовых скидок;

  • ограничения на размеры остатков, объёма склада, транспортной партии, оборотных средств.


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


Для реализации модели в Excel следует иметь в виду матричный и векторный характер всех пременных, в связи с чем рабочий лист должен содержать таблицы спроса, закупок, остатков и так далее.


Следует хорошо уяснить сферы применения многопродуктовой динамической модели управления запасами для решения нестандартных задач организационного управления:

  • управление товарными запасами;

  • планирование производства с учётом динамики спроса на продукцию;

  • управление трудовыми ресурсами.


Изучение транспортных моделей следует начинать с классической транспортной задачи как наиболее простой и хорошо иллюстрирующей основные подходы к решению.


Важно знать и понимать физический смысл и назначение основных элементов схемы транспортировки классической транспортной задачи:

  • нагруженный двудольный орграф;

  • непересекающиеся множество поставщиков и множество потребителей;

  • величина предложения (мощность) каждого поставщика;

  • величина спроса (ёмкость) каждого потребителя;

  • маршрут от каждого поставщика к каждому потребителю;

  • заданная удельная стоимость перевозки по каждому маршруту;

  • подлежащие определению оптимальные грузопотоки от поставщиков к потребителям;

  • транспортные таблицы грузопотоков и удельных стоимостей.


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


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


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


Полезно знать нестандартные задачи, сводящиеся к транспортным:

  • календарное планирование производства;

  • задача о назначении;

а также расширения транспортной модели:

  • многопродуктовая транспортная задача;

  • обобщённая транспортная задача с транзитными пунктами и перетоками груза (эквивалентна задаче о потоке минимальной стоимости).


При изучении классической задачи о назначении следует обратить внимание на её структурное сходство и различие с классической транспортной задачей. Для сравнения полезно сопоставить терминологию:

  • поставщик – кандидат;

  • потребитель – вакансия;

  • маршрут – назначение;

  • стоимость перевозки – зарплата;

Кроме того, структурно подобны схемы задач, целевые функции, левые части ограничений. Так же, как и транспортная, задача о назначении может быть закрытой и открытой. Отличия задачи о назначении заключаются в следующем:

  1. На каждую вакансию может быть назначен только один кандидат и наоборот, каждый кандидат может быть назначен только на одну вакансию.

  2. Варьируемые переменные выражают не количество груза, а факт назначения или неназначения кандидата на должность, и потому являются двоичными.


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


Полезно иметь представление о нестандартных задачах, сводящихся к задаче о назначении:

  • составление расписаний;

  • задача коммивояжёра;

а также расширениях задачи о назначении:

  • задача о множественном назначении.


Контрольные вопросы для самопроверки:

  1. Перечислите и поясните классические модели экономичного заказа. В чём их недостатки?

  2. Поясните назначение многопродуктовой динамической модели управления запасами.

  3. Какие переменные количественно определяют состояние и движение товара?

  4. Изобразите качественный вид изменения запаса при переменном спросе.

  5. Напишите уравнение баланса запаса на складе.

  6. Назовите и поясните основные стратегии управления товарными запасами.

  7. Из чего складываются и как вычисляются затраты на поддержание запаса?

  8. Приведите содержательную постановку многопродуктовой задачи управления запасами.

  9. Изобразите схему и сформулируйте содержательную постановку классической транспортной задачи.

  10. Напишите математическую постановку классической транспортной задачи.

  11. Какие величины являются исходными данными и какие – результатом решения классической транспортной задачи?

  12. Поясните особенности многопродуктовой транспортной задачи и её отличия от классической.

  13. Как многопродуктовую транспортную задачу свести к классической?

  14. Опишите структуру электронного шаблона Excel для решения классической транспортной задачи.

  15. Какие Вы знаете нестандартные задачи, сводящиеся к транспортным?

  16. Изобразите схему и сформулируйте содержательную постановку задачи о назначении.

  17. Напишите математическую постановку задачи о назначении.

  18. Что общего и в чём различия математической постановки задачи о назначении и классической транспортной задачи?

  19. Почему задача о назначении относится к классу булева программирования?

  20. Какие Вы знаете нестандартные задачи, сводящиеся к задаче о назначении?


Тема 4. Кратчайшие пути в графах

При изучении сетевых задач организационного управления (темы 4 и 5) следует иметь в виду, что для многих их них существуют специальные алгоритмы (Прима, Дейкстры, Форда-Фалкерсона и другие), которые эффективнее симплекс-метода, но требуют программирования. Полезно уяснить основную идею этих алгоритмов и провести сравнение с симплекс-методом.


Для решения сетевых задач в Excel следует по материалу лабораторной работы №1 уяснить различные способы представления графов:

  • векторный;

  • матричный;

  • веторно-матричный,

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


При изучении раздела «Минимальный остов графа» следует хорошо уяснить понятие остова графа и то, что во взвешенном графе может быть много остовов с различным и даже одинаковым весом. Таким образом, минимальный остов графа – это один из остовов с минимальным весом (безразлично, какой именно).


Нужно хорошо знать задачи организационного управления, приводящие к минимальному остову графа:

  • строительство сети автомобильных или железных дорог между городами;

  • строительство сети нефтепроводов и газопроводов;

  • прокладка кабельной сети между некоторыми географическими точками;

  • планирование авиарейсов

  • и многие другие.

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


При использовании методов математического программирования нужно хорошо уяснить булеву постановку задачи для неорграфа. При этом важно понять, что двоичные переменные, приписанные к рёбрам графа, показывают, входит (1) или не входит (0) данное ребро в искомый остов.


Особое внимание нужно обратить на проблему связности остова (отсутствия циклов) и хорошо уяснить способы её преодоления:

  1. Разрыв циклов;

  2. Заполнение «нулевых» сечений.


При изучении раздела «^ Минимальный и максимальный пути в графе» следует обратить внимание на сходство этих задач. Различие состоит только в операциях минимизации и максимизации.


При использовании методов математического программирования нужно хорошо уяснить булеву постановку задачи для орграфа. При этом важно понять, что двоичные переменные, приписанные к дугам графа, показывают, входит (1) или не входит (0) данная дуга в искомый путь.


Полезно иметь представление о нестандартных задачах, сводящихся к задаче о минимальном пути в графе:

  • календарное планирование производства;

  • планирование коллективной работы;

  • задача о разбиении;

  • и другие.

Решение задачи о максимальном пути в графе является основой специальной науки – «Сетевое планирование и управление» (СПУ), которая определяет критические сроки выполнения проектов, состоящих из множества различных работ.


При изучении раздела «^ Задача коммивояжёра» следует обратить внимание на комбинаторный характер этой задачи, который из-за огромных вычислительных затрат делает её одной из «труднорешаемых».


При использовании методов математического программирования нужно хорошо уяснить булеву постановку задачи для орграфа и неорграфа. При этом важно понять, что двоичные переменные, приписанные к дугам (рёбрам) графа, показывают, входит (1) или не входит (0) данная дуга (ребро) в искомый маршрут.


Нужно помнить, что постановка задачи для неорграфа требует во много раз меньше вычислительных затрат, но не всегда приводит к нужному результату. В связи с этим особое внимание нужно обратить на проблему связности маршрута (отсутствия подциклов) в постановке задачи для неорграфа и хорошо уяснить способы её преодоления:

  1. Разрыв подциклов;

  2. Заполнение «нулевых» сечений.


Полезно иметь представление о нестандартных задачах, сводящихся к задаче коммивояжёра:

  • составление расписаний.


Контрольные вопросы для самопроверки:

  1. Дайте определение термина «минимальный остов графа».

  2. Какие задачи организационного управления приводят к задаче нахождения минимального остова графа?

  3. Дайте содержательную (словесную) постановку задачи нахождения минимального остова графа.

  4. Перечислите и поясните основные шаги алгоритма Прима поиска минимального остова графа.

  5. Напишите математическую постановку задачи о минимальном остове графа в терминах булева программирования.

  6. Какую роль играют булевы переменные в задаче о минимальном остове графа?

  7. Дайте сравнительную характеристику известных Вам способов представления взвешенных графов в Excel.

  8. Опишите структуру электронного шаблона Excel для нахождения минимального остова графа.

  9. Какие задачи организационного управления приводят к задаче нахождения минимального и максимального путей в графе?

  10. Дайте содержательную (словесную) постановку задачи нахождения минимального и максимального путей в графе.

  11. Перечислите и поясните основные шаги алгоритма Дейкстры поиска минимального пути в графе.

  12. Перечислите и поясните основные шаги алгоритма поиска максимального пути в графе.

  13. Напишите математическую постановку задачи о минимальном и максимальном пути в терминах булева программирования.

  14. Какую роль играют булевы переменные в задаче о минимальном и максимальном путях в графе?

  15. Опишите структуру электронного шаблона Excel для нахождения минимального и максимального путей в графе.

  16. Какие задачи и какими методами решает сетевое планирование и управление (СПУ)?

  17. Дайте содержательную (словесную) постановку задачи коммивояжёра.

  18. Какие задачи организационного управления приводят к задаче коммивояжёра?

  19. Напишите математическую постановку задачи коммивояжёра в терминах булева программирования для орграфа и неорграфа.

  20. Опишите структуру электронного шаблона Excel для решения задачи коммивояжёра в орграфе.

  21. Опишите структуру электронного шаблона Excel для решения задачи коммивояжёра в неорграфе.


Тема 5. Потоки в сетях

При изучении темы «Потоки в сетях» следует обратить внимание на то, что в отличие от предыдущей темы эти задачи в терминах математического программирования не являются булевыми. При использовании математического программирования нужно помнить, что в задачах оптимизации на сетях основным ограничением является уравнение материального баланса для каждого узла сети, которое требует равенства суммы входящих и суммы выходящих потоков. Это вытекает из закона сохранения материи и физического состояния реального объекта, моделируемого узлом сети.


Для усвоения раздела «^ Максимальный поток в сети» следует хорошо уяснить понятие материального потока (вещества, энергии, информации и т.п.) и то, что во взвешенном графе может быть несколько потоков одинаковой величины с различным распределением по дугам. Таким образом, максимальный поток – это один из потоков с максимальной величиной (безразлично, какой именно).


При изучении теоремы и алгоритма Форда-Фалкерсона нахождения максимального потока нужно шорошо усвоить понятия разреза, частичного потока, остаточной пропускной способности, расширяющего (аугментального) пути в графе. Алгоритм пометок Форда-Фалкерсона является одним из самых простых и с помощью расширяющих путей итеративно увеличивает поток в сети до полного её насыщения. Существуют алгоритм Диница и алгоритм Карзанова, более эффективные, чем алгоритм пометок Форда-Фалкерсона.


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


При разработке электронного шаблона Excel для нахождения максимального потока следует помнить, что задание основного ограничения на баланс потоков в стандартной форме весьма затруднительно. В связи с этим рекомендуется использовать уравнение баланса в форме, приведённой в лекциях по курсу.


Нужно хорошо знать задачи организационного управления, приводящие к максимальному потоку:

  • строительство сети автомобильных или железных дорог;

  • строительство сети нефтепроводов и газопроводов;

  • прокладка кабельных сетей;

  • строительство линий электропередачи;

  • и многие другие.

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


Полезно также иметь представление о нестандартных задачах, сводящихся к максимальному потоку:

  • поиск непересекающихся путей в графе;

  • задача о множественном назначении;

  • календарное планирование трудовых ресурсов.


Задача о потоке минимальной стоимости эквивалентна обобщённой транспортной и является наиболее общей. Большинство сетевых задач (транспортная, о назначении, минимальный и максимальный пути и другие) могут быть сформулированы в терминах задачи о потоке минимальной стоимости. Показательно, что после определения величины максимального потока в сети, как правило, решается задача о нахождения максимального потока минимальной стоимости, который и принимается за окончательное решение.


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


Решение задачи о потоке минимальной стоимости в Excel аналогично максимальному потоку за исключением структуры целевой функции, при этом следует придерживаться рекомендаций, приведённых выше для задачи о максимальном потоке.


Нужно хорошо знать задачи организационного управления, приводящие к потоку минимальной стоимости:

  • управление транспортными потоками в сетях автомобильных или железных дорог;

  • управление транспортными потоками в сетях нефтепроводов и газопроводов;

  • управление потоками информации в информационных сетях;

  • управление потоками энергии в сетях электропередач;

  • и многие другие.

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


Полезно также иметь представление о нестандартных задачах, сводящихся к потоку минимальной стоимости:

  • многопродуктовый поток минимальной стоимости;

  • календарное планирование.


Контрольные вопросы для самопроверки:

  1. Дайте определения терминов «сеть» и «поток».

  2. Какие задачи организационного управления приводят к задаче нахождения максимального потока в сети?

  3. Дайте содержательную (словесную) постановку задачи нахождения максимального потока в сети.

  4. Почему в сети может существовать несколько максимальных потоков одинаковой величины и чем они отличаются друг от друга?

  5. Сформулируйте теорему Форда-Фалкерсона и поясните её использование для нахождения максимального потока в сети.

  6. Перечислите и поясните основные шаги алгоритма Форда-Фалкерсона нахождения максимального потока в сети.

  7. Напишите математическую постановку задачи о нахождения максимального потока в терминах математического программирования.

  8. Опишите структуру электронного шаблона Excel для нахождения максимального потока в сети.

  9. Какие задачи организационного управления приводят к задаче нахождения в сети потока минимальной стоимости?

  10. Дайте содержательную (словесную) постановку задачи нахождения в сети потока минимальной стоимости.

  11. Что общего и в чём различия задач о максимальном потоке и потоке минимальной стоимости?

  12. Напишите математическую постановку задачи о потоке минимальной стоимости в терминах математического программирования.

  13. Опишите структуру электронного шаблона Excel для нахождения потока минимальной стоимости.

  14. Дайте содержательную (словесную) постановку задачи нахождения максимального потока минимальной стоимости.

  15. Опишите общую методику нахождения максимального потока минимальной стоимости.


^ 5. Распределение часов дисциплины по темам и формам занятий

(для заочной формы обучения)




темы

Всего часов

Аудиторные занятия

Самостоятельная работа

Лекции

ПЗ

Лаб.работы

1




1










2




4

4







3




4




4




4




4




6




5




3




2




Итого

120

16

4

12

88



^ 6. График изучения дисциплины и прохождения контроля усвоения материала


Установочные лекции и одна лабораторная работа проводятся на сессии 10 семестра. Курсовая работа выполняется самостоятельно в период между сессиями. Остальные лабораторные работы, практические занятия, защита курсовой работы и экзамен проводятся на сессии 11 семестра в соответствии с учебным планом.


^ 7. Требования к объёму знаний при проведении итогового контроля


В результате изучения дисциплины студенты должны:

  • иметь представление о возможностях применения теории принятия решений в проектной, производственной, экономической, финансовой и бизнес-сферах;

  • уметь составлять оптимизационные модели типовых задач организационного управления;

  • знать основные подходы и методы решения задач организационного управления, а также программные средства их реализации;

  • иметь навык решения задач оптимизации в MS Excel.



Разработчик руководства ___________________ доцент Цыганов Ю.К.




Скачать 259,25 Kb.
оставить комментарий
Дата06.08.2012
Размер259,25 Kb.
ТипРуководство, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх