Задача №14.
Построить критический путь по данному проекту II. Методические указания по изучению Методические указания студентам должны раскрывать рекомендуемый режим и характер учебной работы по изучению теоретического курса (или его раздела/части), практических и/или семинарских занятий, и практическому применению изученного материала, по выполнению заданий для самостоятельной работы, по использованию информационных технологий и т.д. Методические указания должны мотивировать студента к самостоятельной работе и не подменять учебную литературу. 1. Методические указания по составлению и решению Самостоятельное составление и решение различного рода задач позволяют подготовить студента к решению реальных задач и проблем с которыми он столкнется в практической деятельности. Как правило, реальные задачи первоначально выглядят не как те задачи, с которыми студент встречается на занятиях – ключевые параметры приходится выделять самим, самим же искать связи между ними, отслеживать массивы данных и строить разрешающие алгоритмы. Иными словами, и постановку (формулирование) задачи, и поиск ее решения приходится проводить самостоятельно, без подсказки. К подобной работе нужно подготовиться заранее. То обстоятельство, что поставленную задачу придется решать своими силами, только поможет при ее формулировании, и вот почему. Решая задачу, поставленную в задачнике, который содержит наряду с этой еще множество других задач, как правило, не ставится под сомнение квалификация его составителя. При обращении к условиям задачи в процессе решения существует уверенность, что составитель задачника позаботился о том, чтобы этих условий хватило для получения ответа. Иное дело, когда задачу поставили самостоятельно. Первые формулировки вообще редко бывают удачными — припопытке решения возникают вопросы, ответы на которые требуют тем или иным образом подкорректировать первоначальную формулировку. Порой это приходится делать несколько раз. Все дело в том, что окончательная, до конца продуманная и хорошо уравновешенная, формулировка задачи появляется лишь тогда, когда уже совершенно ясен и процесс ее решения, и вполне осязаем ответ. Обычно задача помещается в задачник только после этого. Для того чтобы сделать поиск рабочих материалов более осмысленным и определенным, сначала обозначается тема (например, сети, линейные задачи или игры). Сами материалы разрешается выбирать из печатных изданий (газет, журналов, справочников, атласов, альбомов, книг) или из всемирной паутины. Использовать учебники и/или учебные пособия не рекомендуется — это лишит студента столь необходимой самостоятельности и заметно снизит эффект от предлагаемого занятия. В отдельных случаях допускается предложение собственных условий заданий (разумеется, при непременной ее содержательности). Ограничения на количественные показатели в заданиях подобраны так, чтобы поиск их решений не был чрезмерно утомителен. Задание 1 (эйлеров цикл). 1. Построить конечный связный граф без петель с числом вершин не менее 12, причем так, чтобы все вершины графа были четными и имели степень не ниже 4. 2. Построить пошагово эйлеров цикл (замкнутый путь). 3. Предложить реальную задачу, рассмотрение которой приводит к эйлеровому графу указанного типа. Задание 2 (эйлеров путь), 1. Построить конечный связный граф без петель с числом вершин не менее 11, причем так, чтобы все вершины графа, кроме двух нечетных вершин А и В, были четными и имели степень не ниже 4. 2. Построить пошагово эйлеров путь. 3. Предложить реальную задачу, рассмотрение которой приводит к эйлеровому графу указанного типа. Задание 3 (минимальное порождающее дерево). Пользуясь печатным или электронным источником, отыскать задачу, приводящую к сети, веса ребер которой определяются их протяженностью, стоимостью и т. п.; при этом число узлов в сети должно быть не меньше восьми, а каждое ребро должно быть нагружено определенным, но не очень большим числом (например, от 1 до 20). Затем требуется: 1. составить таблицу, описывающую выбранные данные, и нарисовать саму сеть, 2. построить пошагово минимальное порождающее дерево и 3. правильно оформить полученный ответ — выделить найденный граф, выписать сумму длин его ребер, сделать необходимые выводы и проинтерпретировать полученные результаты. Задание 4 (максимальный поток). Пользуясь печатным или электронным источником, отыскать задачу, приводящую к сети, веса ребер которой определяются их пропускной способностью; при этом число узлов в сети должно быть не меньше восьми, а каждое ребро должно быть нагружено определенным, но не очень большим числом (например, от 1 до 20). Затем необходимо: 1. составить таблицу, описывающую выбранные данные, с указанием начального (источника) и конечного (стока) узлов и построить саму сеть, 2. посредством серии последовательных шагов найти способ переноса максимального потока, допускаемого выбранной сетью, из источника к стоку, 3. методом разделяющих сечений найти величину максимального потока из начального узла в конечный и убедиться в том, что результаты этих двух пунктов совпадают, 4. правильно оформить полученный ответ — указать соответствующее (минимальное) сечение, его пропускную способность, выделить в сети ребра, обеспечивающие пропуск этого максимального потока через заданную сеть с указанием соответствующей нагрузки каждого из них, сделать необходимые выводы и проинтерпретировать полученные результаты. Задание 5 (кратчайший маршрут). Пользуясь печатным или электронным источником, отыскать задачу, приводящую к сети, веса ребер которой определяются их пропускной способностью; при этом число узлов в сети должно быть не меньше восьми, а каждое ребро должно быть нагружено определенным, но не очень большим числом (например, от 1 до 20). Затем необходимо: 1. составить таблицу, описывающую выбранные данные, с указанием начального узла и построить саму сеть, 2. пошагово найти кратчайшие маршруты из начального узла во все остальные узлы сети, 3. правильно оформить полученный ответ – указать соответствующие маршруты, их протяженность, привести рисунок, на котором все найденные маршруты выделены (например, фломастером), сделать необходимые выводы и проинтерпретировать полученные результаты. Задание 6 (критический путь). Пользуясь печатным или электронным источником, отыскать задачу, приводящую к необходимости проведения комплекса работ за возможно более короткое время с не менее чем десятью видами работ разной продолжительности. Затем необходимо: 1. упорядочить работы, 2. составить рабочую таблицу, описывающую работы, их последовательность и продолжительность, 3. пользуясь созданной таблицей, построить ориентированную сеть, 4. найти критический путь в построенной сети и выделить критические работы, 5. правильно оформить полученный ответ — указать найденный критический путь (например, выделить фломастером), выписать критические работы, найти общую временную протяженность критического пути, сделать необходимые выводы и проинтерпретировать полученные результаты Задание 7 (задача линейного программирования). 1. Пользуясь печатным или электронным источником, отыскать задачу (с вполне конкретными данными), приводящую к задаче линейного программирования. Число п неизвестных, подлежащих определению, должно подчиняться условию п ≥ 2, а число т линейных неравенств –условию т ≥ 2. 2. Составить соответствующую систему линейных неравенств. 3. Наглядно-графическим способом найти экстремальное значение заданной целевой функции и соответствующие значения неизвестных. 4. Правильно оформить полученный ответ, сделать необходимые выводы и проинтерпретировать полученные результаты. Задание 8 (транспортная задача). 1. Пользуясь печатным или электронным источником, отыскать задачу (с вполне конкретными данными), приводящую к сбалансированной транспортной задаче. Число т пунктов отправления должно подчиняться неравенству т ≥ 4, а число п пунктов назначения — неравенству ≥ 5. 2. Составить соответствующую таблицу. 3. Найти какое-нибудь опорное решение. 4. Действуя пошагово, преобразовать найденное опорное решение в оптимальное. 5. Правильно оформить полученный ответ, сделать необходимые выводы и проинтерпретировать полученные результаты. Задание 9 (задача целочисленного программирования). 1. Пользуясь печатным или электронным источником, отыскать задачу (с вполне конкретными данными), приводящую к задаче целочисленного программирования. Число п неизвестных, подлежащих определению, должно подчиняться условию п ≥ 2, а число т линейных неравенств – условию т ≥ 3. 2. Составить соответствующую систему линейных неравенств. 3. Методом ветвей и границ (сопровождаемым аккуратно выполненными чертежами) найти экстремальное значение заданной целевой функции и соответствующие целочисленные значения неизвестных. 4. Правильно оформить полученный ответ, сделать необходимые выводы и проинтерпретировать полученные результаты. Задание 10 (матричные и/или биматричные игры). Пользуясь печатным или электронным источником, отыскать задачу, в которой описывается конфликтная ситуация с участием двух заинтересованных сторон. (Размеры т х п -матриц могут быть произвольными, при условии, что т ≥ 3 и п ≥ 3.) Далее нужно: 1. описать все возможные стратегии обоих игроков, 2. составить одну (если интересы игроков противоположны) или две (если интересы игроков не совпадают) таблицы, в которых вербально описываются выигрыши игроков в каждой из ситуаций, 3. обоснованно перейти к количественному описанию выигрышей игроков и записать полученный результат. Ответом в этом задании является формализация конфликтной ситуации. Задание 11 (матричные игры с седловой точкой). 1. Построить m х л-матрицу с седловой точкой, считая, что т ≥ 5 и п ≥ 7. 2. Убедиться в том, что построенная матрица имеет седловую точку. 3. Найти оптимальные стратегии и значение (цену) игры. Задание 12 (2 х п- и/или т х 2-матричные игры). Пользуясь печатным или электронным источником, отыскать задачу, в которой описывается конфликтная ситуация с участием двух заинтересованных сторон, интересы которых противоположны. Затем: 1. описать все возможные стратегии каждого из игроков (у одного из игроков должно быть ровно две стратегии, у другого не меньше трех), 2. составить таблицу, в которой вербально описывались бы выигрыши (проигрыши) игроков в каждой из ситуаций, и выписать матрицу, в которой эти выигрыши описаны количественно, 3. методом огибающей найти оптимальное решение рассматриваемой игры в смешанных стратегиях, 4. правильно оформить полученный ответ – указать смешанные стратегии каждого из игроков, выписать их средние выигрыши, сделать необходимые выводы и проинтерпретировать полученные результаты. Задание 13 (матричная игра с матрицей произвольного размера (итерационный метод)). Пользуясь печатным или электронным источником, отыскать задачу, в которой описывается конфликтная ситуация с участием двух заинтересованных сторон, интересы которых противоположны. Затем: 1. описать все возможные стратегии каждого из игроков, 2. составить таблицу, в которой вербально описывались бы выигрыши (проигрыши) игроков в каждой из ситуаций, и выписать матрицу, в которой эти выигрыши описаны количественно, 3. методом итераций найти приближенное к оптимальному решение рассматриваемой игры в смешанных стратегиях, 4. правильно оформить полученный ответ — указать смешанные стратегии каждого из игроков, выписать их средние выигрыши, сделать необходимые выводы и проинтерпретировать полученные результаты. Задание 14 (2 х 2-биматричные игры). Пользуясь печатным или электронным источником, отыскать задачу, в которой описывается конфликтная ситуация с участием двух заинтересованных сторон. Затем: 1. описать все возможные стратегии каждого из игроков (у каждого должно быть ровно две стратегии), 2. составить две таблицы, в которых вербально описывались бы выигрыши игроков в каждой из ситуаций, и выписать две матрицы, в которых эти выигрыши описаны количественно, 3. найти оптимальное решение рассматриваемой игры в смешанных стратегиях (наглядно-графическим методом зигзага), 4. правильно оформить полученный ответ — указать смешанные стратегии каждого из игроков, выписать их средние выигрыши, сделать необходимые выводы и проинтерпретировать полученные результаты. Задание 15 (позиционные игры). Пользуясь печатным или электронным источником, отыскать задачу, в которой описывается конфликтная ситуация с участием двух или трех заинтересованных сторон, разрешаемая путем последовательного принятия решений в условиях изменяющейся во времени и, вообще говоря, неполной информации. Затем требуется: 1.описать шаги и альтернативы сторон, 2.построить дерево игры и 3.указать информационные множества. Ответом в этом задании является формализация конфликтной ситуации. Задание 16 (игры дележа). Пользуясь печатным или электронным источником, отыскать задачу, в которой описывается конфликтная ситуация с участием не менее трех заинтересованных сторон, и требуется разделить между ними заданную сумму, пользуясь каким-нибудь принципом оптимальности. Затем: 1. задать характеристическую функцию (указать доход каждой коалиции игроков), 2. найти ядро игры, 3. правильно оформить полученный ответ — выписать доход каждого из игроков, сделать необходимые выводы и проинтерпретировать полученные результаты. Задание 17 (многокритериальные задачи). 1. Пользуясь печатным или электронным источником, отыскать задачу (с вполне конкретными данными), приводящую к многокритериальной задаче линейного программирования. Число п неизвестных, подлежащих определению, должно подчиняться условию п ≥; 2, а число т линейных неравенств – условию т ≥ 2. 2. Составить соответствующую систему линейных неравенств. 3. Методом идеальной точки и/или методом ограничений найти оптимальное решение поставленной задачи, соответствующие значения заданных целевых функций и неизвестных. 4. Правильно оформить полученный ответ, сделать необходимые выводы и проинтерпретировать полученные результаты.
|
