Рекомендации методические по организации и защите курсовой работы по дисциплине для специальности «Математические методы» Федеральное государственное образовательное учреждение среднего профессионального образования «Омский промышленно-экономический колледж» Методические рекомендации по организации и защите курсовой работы по дисциплине для специальности «Математические методы» 2203 Программное обеспечение вычислительной техники и автоматизированных систем 2008 ОДОБРЕНО Предметной (цикловой) комиссией Председатель ______________Москалёв Г. Н. Составитель: Н. А. Белгородцева Составлено в соответствии с рекомендациями по организации выполнения и защиты курсовой работы в образовательных учреждениях СПО Преподаватель Омского промышленно-экономического колледжа Введение Методические указания по выполнению курсовой работы по дисциплине «Математические методы» для специальности 230105 Программное обеспечение вычислительной техники и автоматизированных систем состоят из пояснительной записки, общих рекомендаций, порядка выполнения и структуры курсовой работы, требований к содержанию и оформлению курсовой работы, приложений, в которых содержатся примеры оформления курсовой работы. Содержание: 1. Пояснительная записка 4 2. Порядок выполнения курсовой работы 5 3. Структура курсовой работы 5 4. Тематика курсовых работ 7 5. Содержание основной части курсовой работы (по темам) 9 6. Требования к оформлению курсовой работы 50 7. Порядок защиты курсовой работы по дисциплине 52 «Математические методы» 8. Список литературы для написания курсовой работы 53 9. Приложения 55 Пояснительная записка Методические указания по выполнению курсовой работы составлены в соответствии с рабочей программой по дисциплине «Математические методы» для специальности 230105 Программное обеспечение вычислительной техники и автоматизированных систем. занимает важное место при изучении дисциплины «Математические методы». Целью её выполнения является: - систематизация и закрепление полученных знаний и практических умений; - углубление теоретических знаний в соответствии с заданной темой; - формирование умения применять теоретические знания при решении поставленных задач; - формирование умений использовать справочную литературу; - развитие творческой инициативы, самостоятельности, ответственности и организованности; - подготовка к итоговой государственной аттестации. В результате выполнения курсовой работы студент должен: знать: - методы решения задач; уметь: - работать с научной литературой; - строить математическую модель; - выбирать метод решения задач; - использовать программный продукт при решении задач. Методические указания предназначены для оказания помощи студентам в организации работы по написанию курсовой работы. Методические указания снабжены подробным планом раскрытия теоретического материала по каждой теме и примерами задач, требующих обязательного решения. Формой отчётности при выполнении является план-график выполнения курсовой работы. Порядок выполнения курсовой работы Студенты выполняют курсовую работу по утверждённой теме в соответствии с заданием и планом-графиком. План-график выполнения курсовой работы содержит сведения об этапах, результатах, сроках выполнения задания, отметки руководителя курсового проекта о выполнении объёмов работ (дата, подпись). Образец плана-графика приведён в приложении 2. Структура курсовой работы 2.1. Структурными элементами курсовой работы являются: титульный лист, задание, оглавление, введение, основная часть, заключение, список литературы, приложения. 2.2. Титульный лист курсовой работы должен содержать следующие сведения: - полное наименование учебного заведения, отделение; - название темы курсовой работы; - название вида документа; - сведения об исполнителе (ФИО студента, номер группы, подпись), сведения о преподавателе (руководителе) (ФИО, подпись); - сведения о допуске курсового проекта к защите (дата допуска); - наименование места и года выполнения. Образец титульного листа приведён в приложении 3. 2.4. В задании указывают: - тему курсового проекта; - перечень основных вопросов, подлежащих изучению и разработке; - срок сдачи курсового проекта. Образец задания приведён в приложении 1. 2.5. Оглавление должно содержать перечень структурных элементов курсового проекта с указанием номеров страниц, с которых начинается их местоположение в тексте, в том числе: - введение; - обзор литературы; - главы, параграфы, пункты; - заключение; - список литературы; - приложения. 2.6. Текст введения должен кратко раскрывать актуальность и значение темы. 2.7. Основная часть должна содержать обзор литературы по изучаемому вопросу, развёрнутые ответы на поставленные вопросы, подробное решение предложенных задач, а также дополнительные сведения. 2.8. В заключении должны быть приведены выводы о положительных и отрицательных моментах, которые были подмечены при изучении поставленного вопроса, о сильных и слабых сторонах рассматриваемых методов решения задач. 2.9. Список литературы должен содержать библиографический перечень источников (включая и Интернет-ресурсы), информация из которых использовалась при выполнении курсовой работы. 2.10. В случае необходимости в курсовую работу допускается включать приложения. Приложения должны содержать дополнительную информацию по изучаемой предметной области, не вошедшую в основную часть. Тематика курсовых работ 1. Исторический обзор экономико-математических методов и моделей 2. Классификация экономико-математических методов и моделей 3. Линейное программирование (Постановка задачи линейного программирования; Экономическая интерпретация задач линейного программирования; Проверка сбалансированности планов; Требования совместности условий) 4. Линейное программирование (Графический метод решения задач линейного программирования; Идея симплекс-метода; Двойственные задачи линейного программирования; Устойчивость оптимизационного решения) 5. Специальные задачи линейного программирования (Целочисленное программирование; Метод ветвей и границ; Задача выбора вариантов) 6. Специальные задачи линейного программирования (Дискретное программирование; Методы решения дискретных задач; Параметрическое программирование) 7. Специальные задачи линейного программирования (Дробно-линейное программирование; Блочное программирование) 8. Оптимизация на графах (Элементы теории графов; Задача коммивояжёра; Транспортная задача) 9. Оптимизация на графах (Оптимизация сетевого графика; Задача о максимальном потоке; Задача о кратчайшем пути) 10. Комбинаторные задачи 11. Нелинейное программирование 12. Динамическое программирование (Постановка задач динамического программирования; Обобщённая схема задачи распределения ресурсов; Задачи динамического программирования) 13. Динамическое программирование (Балансирование производственных мощностей и программы предприятия; Задачи о правилах остановки) 14. Элементы теории вероятностей 15. Стохастическое программирование 16. Управление в условиях неопределённости 17. Оценка риска в «играх с природой» 18. Теория игр 19. Основные понятия теории очередей 20. Система с отказами 21. Теория очередей (Система с неограниченной длиной очереди; Система с постоянным временем обслуживания) 22. Теория очередей (Система с ограниченной длиной очереди; Система с ограниченным потоком требований; Двухфазная система) 23. Общие сведения о QSB 24. Решение задач линейного программирования в QSB 25. Решение задач в QSB (Решение задач целочисленного программирования; Решение транспортной задачи) 26. Решение задач в QSB (Решение задачи о назначениях; Решение сетевых задач (NET)) 27. Решение сетевых задач ( CPM ) 28. Решение задач в QSB (Решение задач динамического программирования; Решение вероятностных моделей) 29. Решение задач линейного программирования в Excel 30. Решение задач в Excel Студент имеет право предложить собственную тему курсовой работы при условии обоснованности её разработки. Содержание основной части курсового проекта (по темам) 1. Исторический обзор экономико-математических методов и моделей Рассмотреть вопросы: - описание Евклидом способов построения наибольшего и наименьшего из отрезков, соединяющих данную точку с окружностью, а также способов нахождения среди параллелограммов с заданным параметром параллелограмма максимальной площади; - математика в Древнем Вавилоне и Древнем Египте как наука о количественных отношениях и пространственных формах действительного мира, а также как система практических навыков, крайне важных для работы государственных чиновников; - акцентирование внимания в «Диалогах» Архимеда на необходимость нематематических следствий как «очередного шага» после математических выводов; - одна из первых попыток экономико-математического моделирования механизма движения финансов, предпринятая во Франции врачом и экономистом Франсуа Кенэ; - введение Карлом Марксом алгебраических формул с помощью таблиц Кенэ и его мечта «вывести главные законы кризисов»; - книга французского математика Антуана Курно «Исследование математических принципов теории богатства», выпущенная в 1838 г.; - статистическая модель системы экономического равновесия, введённая в 1874 г. Швейцарским экономистом Л. Вальрасом, и модель распределения доходов населения, предложенная итальянским экономистом В. Парето. - «задача о землекопе» - одна из первых задач, решенных на основе математического подхода, сформулированная Фредериком Тейлором в 1885 г.; - описание в 1911 г. русским экономистом И. Дмитриевым балансовых соотношений «продукты-ресурсы» с помощью линейных алгебраических выражений; - идея о составлении плана как результата решения оптимизационной задачи, сформулированная в 1920-х гг. С. Г. Струмилиным; - необходимость плавного изменения показателей, согласованности элементов системы, кратчайшего пути к цели, как требования к плану, отмеченные В. А. Базаровым; - основы экономико-математических моделей «затраты-выпуск» для межотраслевых связей, введённые в 1930-х гг. профессором Массачусетсткого технологического института В. Леонтьевым; - задача: как наилучшим образом распределить работу восьми станков фанерного треста при условии, что известна производительность каждого станка по каждому из пяти видов обрабатываемых материалов, поставленная в 1938 г перед двадцатипятилетним профессором ЛГУ Л. В. Канторовичем; - исторически общая задача линейного программирования, поставленная в 1947 г. Дж. Данцигом и М. Вудом в департаменте ВВС США; - транспортная задача, сформулированная в 1941 г. Хичкоком и независимо от него Купмансом в 1947 г., задача о диете, сформулированная Стиглером в 1945 г.; - успешное решение задачи линейного программирования на ЭВМ «Seac » в 1952 г. в Национальном бюро стандартов; - интенсификация исследований в трудах Гасса, Баранкина и Дорфмана (квадратичное программирование), Беллмана и Дрейфуса (нелинейное программирование); - значительные работы в 1950-1960-х гг. в области экономико-математического моделирования в России: «Экономический расчёт наилучшего исследования ресурсов» Л. В. Канторовича (1959), «Применение математических методов в вопросах анализа грузопотоков» Л. В. Канторовича, М. К. Гавурина (1949), работы В. В. Новожилова по оптимальному планированию народного хозяйства. - создание в 1960 г. академиком В. С. Немчиновым при Новосибирском отделении АН СССР лаборатории экономико-математического моделирования, организация в Киеве института кибернетики, возглавляемой академиком В. М. Глушковым; - объяснить, в каком случае существуют задачи математического программирования; - объяснить, в каком случае не возникает проблемы поиска допустимого решения. 2. Классификация экономико-математических методов и моделей План: А) Этапы принятия решений Б) Классификация задач оптимизации В данном пункте плана рассмотреть вопросы: - в каком случае применяют волевой выбор; - в чём заключается критериальный выбор; - какой вариант называют оптимальным, какую задачу называют задачей оптимизации; - что такое целевая функция; - к чему сводится решение задачи оптимизации; - какие данные называют детерминированными; - какие данные называют случайными величинами; - что предполагает оценка максимин; - на что ориентирует оценка минимакс; - что такое непрерывные величины; - что такое дискретные, или целочисленные величины; - какие зависимости называют линейными; - какие зависимости называют нелинейными; В) Классификация экономико-математических методов В данном пункте плана рассмотреть вопросы: - что такое задача линейного программирования; - что такое задача нелинейного программирования; - что такое задача выпуклого программирования; - что такое задача квадратичного программирования; - что такое задача целочисленного программирования; - что такое задача параметрического программирования; - что такое задача динамического программирования; - что такое задача стохастического программирования; 3. Линейное программирование План: А) Постановка задачи линейного программирования В данном пункте плана рассмотреть вопросы: - задачи распределения ресурсов; - что такое задачи линейного программирования; - что содержит каждая задача линейного программирования; Б) Экономическая интерпретация задач линейного программирования В данном пункте плана составить математические модели задачи и найти оптимальные решения. Требуется определить план выпуска четырёх видов продукции А, В, С, D, для изготовления которых используются ресурсы трёх видов: трудовые, материальные, финансовые. Количество каждого i -го вида ресурса для производства каждого j - го вида продукции называют нормой расхода и обозначают aij . Количество каждого вида ресурса, которое имеется в наличии, обозначают bi (табл.). Ресурсы (i ) Вид продукции (j ) Запас ресурса (bi ) А В С D Удельный расход ресурсов (aij ) Трудовые 6 4 2 1 800 Материальные 7 9 11 5 2000 Финансовые 3 4 5 6 12000 Граница нижняя 1 - 3 - - Граница верхняя 12 2 - - - План х1 х2 х3 х4 - Пусть для продукции видов А, В, С, D прибыль от реализации единицы продукции каждого вида составит соответственно 5, 6, 7 и 8 денежных единиц, а суммарная прибыль от всего производства должна быть не менее 3000 денежных единиц. Пусть F – ресурсы, R – результат их применения. При заданных зависимостях результата и потребных ресурсов от количества выпускаемой продукции R = R ( xj ), F = F ( xj ) сформулировать две постановки распределения ресурсов. Для каждой постановки найти своё оптимальное решение. Сделать важные для эффективного менеджмента предприятия выводы. В) Проверка сбалансированности планов В данном пункте плана показать, как можно обеспечить условие сбалансированности на примере первой постановки задачи из пункта Б плана. Только теперь в связи с изменением рыночной ситуации продукцию А необходимо выпускать в количестве не менее 15, В – не менее 5, С – не менее 2 единиц. Изделия D с производства снимаются как не пользующиеся спросом. Взамен планируется запустить технологически подобные, но более совершенные изделия S, на которые потенциальные потребители могут предъявить, по пессимистическим оценкам, платёжеспособный спрос в объёме 500 единиц. Это позволяет предприятию планировать получение прибыли в размере не менее 5000 денежных единиц. Новое условие задачи представлено в таблице Ресурсы (i ) Вид продукции (j ) Запас ресурса (bi ) А В С S Удельный расход ресурсов (aij ) Прибыль на единицу продукции 5 6 7 8 - Трудовые 6 4 2 3 800 Материальные 7 9 11 5 2000 Финансовые 3 4 5 6 12000 Граница нижняя 15 5 2 500 - Граница верхняя - - - - - План х1 х2 х3 х4 - Для обеспечения условия сбалансированности нужно: - убедиться, что данная задача не имеет решения, так как она не сбалансирована по ресурсам; - поскольку задача оказалась несбалансированной, то составить модель с учётом возможной нехватки ресурсов, введя переменные d 1 , d 2 , d 3 – количество ресурсов каждого вида, необходимое дополнительно для выполнения скорректированного плана производства; - решить задачу и проверить, какие di = 0, т. е. выяснить, каких дополнительных ресурсов i -го вида не потребуется. Из проведённого анализа сделать выводы. Г) Требования совместности условий В данном пункте плана разобрать следующие вопросы: - число неизвестных меньше, чем число уравнений; - сделать вывод, в каком случае система не имеет решения и является несовместной; - число неизвестных равно числу уравнений; - сделать вывод, в каком случае система имеет одно решение; - для каких уравнений справедливо рассмотренное выше наличие или отсутствие решений при различных соотношениях числа переменных и числа уравнений; - число неизвестных больше числа уравнений; - сделать вывод, в каком случае система имеет бесчисленное множество решений. 4. Линейное программирование План: А) Графический метод решения задач линейного программирования В данном пункте плана разобрать вопросы: - уравнение прямой в отрезках; - область допустимых решений; - координаты каких точек являются решением системы неравенств; - выяснить, любая ли система линейных неравенств имеет допустимые решения; - плоскость в трёхмерном пространстве, полупространство, многогранник; - начиная с какого количества переменных невозможна геометрическая интерпретация системы неравенств; - геометрическая интерпретация оптимального решения; - суть графического метода решения задач линейного программирования; Б) Идея симплекс-метода В данном пункте плана решить следующую задачу. Оптимизировать план производства с целью получения максимальной прибыли (табл.) Ресурсы Норма расхода ресурсов Запас ресурса П1 П2 П3 П4 Трудовые 1 1 1 1 16 Сырьё 6 5 4 3 110 Оборудование 4 6 10 13 100 Прибыль 60 70 120 130 - План х1 х2 х3 Х4 - Разобрать следующие вопросы: - какой элемент выбирается в индексной строке при отыскании максимума, и какой – при отыскании минимума; - на что делятся компоненты вектора свободных членов; - какое отношение выбирается из полученных; - какая вектор-строка является ключевой и что с ней происходит; - где находится разрешающий элемент; - в каком случае полученное решение является допустимым; - в каком случае полученное решение является оптимальным, что это значит; В) Двойственные задачи линейного программирования В данном пункте плана разобрать следующие вопросы: - какую задачу можно сопоставить с любой задачей линейного программирования; - согласно чему составляется двойственная задача по отношению к прямой задаче; - что можно сказать о решении и о нахождении решения двойственных задач, чему равны значения целевых функций этих задач; - какую обычно решаю задачу для нахождения решения двойственных задач; Решить задачу . Для производства изделий А, В, С используются три различных вида ресурсов. Каждый из видов ресурсов может быть использован в количестве, соответственно не большем 180, 210, 244 ед. Известны затраты каждого из видов ресурсов на ед. продукции и цена ед. продукции каждого вида (табл.). Определить план производства, при котором обеспечивается максимальный доход, и оценить дефицитность каждого вида ресурсов, используемых для производства продукции. Оценки, приписываемые каждому виду ресурсов, должны быть такими, чтобы оценка всех используемых ресурсов была минимальной, а суммарная оценка ресурсов на производство единицы продукции каждого вида – не меньше цены единицы продукции каждого вида. Составить и решить прямую и двойственную задачи. Сделать выводы. Вид ресурса Норма расхода ресурса на единицу продукции А В С 1 4 2 1 2 3 1 3 3 1 2 5 Цена продукции 10 14 12 Ответить на вопросы: - что определяют двойственные оценки; - что показывает величина двойственной оценки; Г) Устойчивость оптимизационного решения 5. Специальные задачи линейного программирования План: А) Целочисленное программирование В данном пункте плана рассмотреть следующие вопросы: - формулирование в Древней Греции Диофантом (II-III вв.) уравнения, в котором искомые переменные целые; - какие задачи называют задачами целочисленного программирования; - какую задачу называют целочисленной задачей линейного программирования, а какую – целочисленной задачей нелинейного программирования; - привести примеры задач целочисленного или дискретного программирования; - в каком случае задачу называют полностью целочисленной, а в каком – частично целочисленной; - методы отсечений и методы возврата, метод ветвей и границ; Б) Метод ветвей и границ В данном пункте плана рассмотреть следующие вопросы: - какая задача называется непрерывной; - методом ветвей и границ решить задачу : После получения нецелочисленного решения составить две новые задачи с различными граничными условиями. В) Задача выбора вариантов В данном пункте плана рассмотреть следующие вопросы: - какие переменные называют булевыми, в честь кого они получили такое название; - составить математическую модель и решить задачу выбора вариантов : Для получения результата в виде максимально возможной прибыли необходимы два вида ресурсов: материальные и трудовые. Возможны четыре варианта расхода ресурсов и получения прибыли (табл.) Требуется выбрать, какие варианты принять для реализации при условии, чтобы общее число принятых вариантов не превышало трёх ( ). Показатели Варианты Наличие 1 2 3 4 Прибыль, д. е./ед. 65 80 90 210 - Материальные ресурсы 200 180 240 250 800 Трудовые ресурсы 10 15 22 28 50 6. Специальные задачи линейного программирования План: А) Дискретное программирование В данном пункте плана решить задачу : Мебельная фабрика выпускает диваны, кресла и стулья. Требуется определить, сколько можно изготовить спинок диванов, подлокотников кресел и ножек стульев при известном удельном расходе ресурсов (табл.), чтобы доход был максимальным. Показатели Изделия Наличие ресурса спинка дивана подлокотники кресла Ножка стула Цена, д. е./ед. 20 6 8 - Древесина 10 5 3 206 Трудозатраты 2 7 4 100 Спрос 10 8 12 - х1 х2 х3 bi Причём выпуск спинок дивана может принимать любое значение, подлокотники изготавливаются парами, т. е. их количество должно быть кратно двум, а количество ножек стульев – четырём. Б) Методы решения дискретных задач В данном пункте плана разобрать следующие вопросы: - как решаются задачи дискретного программирования методом ветвей и границ; - решить систему методом сплошного перебора: - какую последовательность действий предполагает метод фильтрующего ограничения; - что такое фильтр; - какой фильтр называют адаптивным; В) Параметрическое программирование В данном пункте разобрать следующие вопросы: - какие задачи называют задачами параметрического программирования; - решить задачу : Пусть предприятие изготавливает два вида продукции А и В, для которых использует три вида ресурсов. Известны нормы расхода и запасы каждого вида (см. табл.). Из анализа спроса установлено, что цена единицы продукции для изделия А может изменяться от 2 до 12 руб., а для изделия В – от 13 до 3 руб., причём эти изменения определяются соотношениями c 1 = 2 + t , c 2 = 13 – t , где Требуется для каждого из возможных значений цены каждого вида изделий найти такой план их производства, при котором обеспечивается максимальная выручка. Ресурсы Удельный расход ресурсов на изделие Наличие ресурсов А В 1 4 1 16 2 2 2 22 3 6 3 36 Цена изделия 2 + t 13 - t - 7. Специальные задачи линейного программирования А) Дробно-линейное программирование В данном пункте плана решить следующие задачи: 1. Пусть для производства двух видов изделий А и В используется три типа технологического оборудования. Известны затраты времени и других ресурсов на производство единицы изделия каждого вида (табл.). Тип оборудования Нормы времени Ограничения по фонду времени ра- боты оборудования А В верхний нижний I 2 8 26 - II 1 1 - 4 III 12 3 39 - Затраты на производство 2 3 - - Требуется определить, сколько изделий каждого вида необходимо изготовить, чтобы себестоимость одного изделия была минимальной. 2. Здесь х3 , х4 , x 5 – фиктивные переменные, преобразующие неравенства в равенства. Б) Блочное программирование. 8. Оптимизация на графах План: А) Элементы теории графов В данном пункте плана разобрать следующие вопросы: - что такое граф; - какой граф описывает блок-схему (или структурограмму) технической системы; - что такое граф-дерево; - что такое сеть; - что показывает структура (топология) сети; - какую вершину сети называют источником, а какую – стоком; - какие характеристики могут иметь дуги; Б) Задача коммивояжёра В данном пункте плана решить задачу: Пусть имеются пять пунктов, соединённых между собой дорогами так, что из любого пункта можно проехать в любой другой пункт (рис.). Известно время перевозки из пункта i в пункт j (табл.). Требуется найти такой маршрут, начинающийся в данном пункте, проходящий через все пункты и заканчивающийся в пункте выезда, чтобы его продолжительность была наименьшей. Из пункта i В пункт j 1 2 3 4 5 1 0 10 25 25 10 2 1 0 10 15 2 3 8 9 0 20 10 4 14 10 24 0 15 5 10 8 25 27 0 В) Транспортная задача В данном пункте плана разобрать следующие вопросы: - какая задача называется транспортной; - какая модель называется открытой; - какие этапы включает алгоритм решения задачи методом потенциалов; - решить задачу: Пусть имеется 3 поставщика и 4 потребителя. Запасы продукта у поставщиков, спрос потребителей и транспортные расходы на доставку единицы продукта от i -го поставщика к j -му потребителю заданы (табл.). - какая модель называется закрытой; Поставщик Потребитель Запас 1 2 3 4 1 3 5 6 2 170 2 6 4 7 5 250 3 5 4 6 5 180 Спрос 150 230 160 60 600 Требуется составить такой план перевозки, чтобы обеспечить минимум общей суммы транспортных расходов. Начальный план перевозок определить с помощью метода северо-западного угла. 9. Оптимизация на графах План: А) Оптимизация сетевого графика В данном пункте плана разобрать следующие вопросы: - что за методы CPM и PERT и когда они были разработаны; - в каком году и для чего появился CPM ; - в каком году и для чего появился PERT ; - алгоритм методов CPM и PERT ; - в чём состоит главное различие этих методов; - какие временные оценки используются в PERT ; - что в сетевом графике соответствует дуге, а что вершине; - начальное событие, конечное событие; - путь; - критический путь; - резерв; - что должен чётко знать и особо контролировать руководитель; - первая постановка задачи оптимизации; - вторая постановка задачи оптимизации; Б) Задача о максимальном потоке В данном пункте плана определить максимальный поток в сети (рис.): Решение задачи проводить с помощью программы «Сетевое моделирование (NET )». В) Задача о кратчайшем пути В данном пункте плана определить кратчайшее расстояние в сети (смотри рис. выше) между первым и пятым пунктами. Решение задачи проводить с помощью программы «Сетевое моделирование (NET )». 10. Комбинаторные задачи План: А) Задача о назначениях В данном пункте плана сформулировать задачу о назначениях в общем виде; Б) Венгерский метод В данном пункте плана рассмотреть следующие вопросы: - идея венгерского метода; - решить задачу данным методом: Пусть для монтажа четырёх объектов (п = 4 ) требуется четыре крана (п = 4 ). Известно время монтажа каждым i - м краном каждого j -го объекта (табл.). Код крана (i ) Затраты времени на монтаж по объектам (cij ) di 1 2 3 4 1 3 7 5 8 3 2 2 4 4 5 2 3 4 7 2 8 2 4 9 7 3 8 3 Необходимо так распределить краны по объектам, чтобы суммарное время монтажа всех объектов было минимально. При решении задачи использовать алгоритм: Шаг 1. Получение нулей в каждой строке. Шаг 2. Поиск оптимального решения. Шаг 3. Поиск минимального набора строк и столбцов, содержащих нули. Шаг 4. Перестановка некоторых нулей. 11. Нелинейное программирование План: А) Классификация и общая постановка задач нелинейного программирования В данном пункте плана рассмотреть вопрос: - какие задачи называются задачами нелинейного программирования; Б) Метод множителей Лагранжа В данном пункте плана рассмотреть следующие вопросы: - множители Лагранжа, функция Лагранжа; - решить задачу методом Лагранжа: Известен рыночный спрос на определённое изделие в количестве 180 штук. Это изделие может быть изготовлено двумя предприятиями одного концерна по различным технологиям. При производстве х1 изделий первым предприятием его затраты составят руб.. а при изготовлении х2 изделий вторым предприятием они составляют руб. Определить, сколько изделий, изготовленных по каждой технологии, может предложить концерн, чтобы общие издержки его производства были минимальны. В) Метод кусочно-линейной аппроксимации В данном пункте плана решить задачу нелинейного программирования методом кусочно-линейной аппроксимации: 12. Динамическое программирование План: А) Постановка задач динамического программирования В данном пункте плана разобрать следующие вопросы: - что такое задачи динамического программирования (ДП), примеры таких задач; - решить задачу ДП: Пусть установлены возможные варианты транспортной сети из маршрутов, соединяющих исходный пункт 1 с конечным пунктом 10. Все 10 пунктов можно отнести к пяти зонам (этапам). На линиях, соединяющих пункты, поставлено время проезда между соседними пунктами (рис.). Требуется выбрать путь от начального пункта до конечного с минимальным временем. - суть принцип оптимальности; - откуда надо начинать анализ вариантов; - какое решение определяется на первом цикле решения задач ДП; - какое решение определяется во втором цикле, как оно находится (на примере предложенной выше задачи); Б) Обобщённая схема задачи распределения ресурсов В данном пункте плана рассмотреть вопрос: - принцип оптимальности Беллмана; В) Задачи динамического программирования В данном пункте плана разобрать следующие вопросы: - основное функциональное уравнение Беллмана, его суть; - каким свойством обладает оптимальное поведение (управление); 13. Динамическое программирование План: А) Балансирование производственных мощностей и программы предприятия В данном пункте плана решить следующую задачу: Пусть известны возможные значения эффективности (например, прирост прибыли, выпуск продукции и др.) на каждом из четырёх предприятий отрасли в результате расширения действующих мощностей (табл.). Капитало- вложения (х ), д. е. Прирост выпуска продукции i -го предприятия gi (x) , д. е./год 1 2 3 4 0 0 0 0 0 50 25 30 36 28 100 60 70 64 56 150 100 90 95 110 200 140 122 130 142 Требуется составить план распределения ограниченных капиталовложений по этим предприятиям (К = 200 д. е.), максимизирующий общий прирост выпуска при заданной номенклатуре и структуре отраслевого плана производства продукции. Б) Задачи о правилах остановки В данном пункте плана разобрать следующие вопросы: - задача о разборчивой невесте; - марковская цепь; - в чём состоит оптимальная стратегия решения задачи о правилах остановки при больших N; - в чём состоит оптимальная стратегия решения задачи о правилах остановки при малых N; - формулировка общей задачи об оптимальной остановке марковской цепи; - решить задачу о бросании монеты при неограниченном капитале; 14. Элементы теории вероятностей Разобрать вопросы: - утверждение Джероламо Кардано (1506-1576) – итальянского математика, философа и врача, с именем которого связывают формулу решения неполного кубического уравнения, создание кардана и гироскопа, о том, что во время осады Трои (ок. 1260 г. до н. э.) для развлечения томящихся от скуки воинов некто Галамед изобрёл игральные кости в виде кубиков с числом точек на каждой стороне от 1 до 6; - от какого арабского слова произошло слово азарт , что оно означает; - одно из первых исследований по теории вероятностей, принадлежащее итальянцу Николо Тарталье (ок. 1499-1557), называемое «Общее правило данного автора, найденное в первый день поста 1523 г. в Вероне, чтобы уметь найти, сколькими способами можно варьировать положение какого угодно количества костей при их метании»; - нормальный закон распределения вероятностей (впервые описан в книге Муавра «Учение о случаях» в XVIII в., затем у Гаусса через 100 лет, и этот закон назвали его именем), играющий исключительно важную роль в описании случайных явлений; - кто впервые назвал науку Теория вероятностей именно так; - что такое событие; - что такое достоверное событие, привести примеры; - что такое невозможное событие, привести примеры; - что такое возможное событие, привести примеры; - что такое вероятность; - для чего используют понятие частоты; - какие события называют несовместными; - какие числа называют случайными величинами; - что такое реализация; - что характеризует математическое ожидание и как оно вычисляется; - что характеризует дисперсия и как она вычисляется; - что показывает коэффициент вариабельности и как он вычисляется; - решить задачу: Пусть наличие некоторого i -го ресурса в каждом квартале bi – случайная величина. Реализация этой случайной величины – фактический объём ресурса в каждом квартале (по отчёту прошлого года и трёх кварталов текущего) (табл.). Квартал I II III IV I II III bi 90 100 105 111 89 95 110 Определить математическое ожидание случайной величины bi , среднеквадратичное отклонение, коэффициент вариабельности; - что показывает закон распределения случайной величины; - между чем устанавливает связь закон распределения случайной величины; - какие задачи решают с помощью нормального закона распределения; - сколько форм представления имеет нормальный закон распределения, назвать их и изобразить графически; 15. Стохастическое программирование План: А) Понятие о стохастическом программировании В данном пункте плана разобрать следующие вопросы: - какие задачи относятся к задачам стохастического программирования; - суть стохастической М-постановки целевой функции; - вид целевой функции при Р-постановке, что обозначает maxL при максимизации целевой функции, что обозначает minL при минимизации целевой функции; - как можно записать задачу СТП при М-постановке для случая, когда вероятностные ограничения представлены в виде ; - как можно записать задачу СТП при Р-постановке в случае максимизации и в случае минимизации целевой функции для случая, когда вероятностные ограничения представлены в виде ; Б) Детерминированная постановка задач стохастического программирования В) Решение задач СТП В данном пункте плана рассмотреть следующие вопросы: - какая функция называется сепарабельной; - каким методом можно найти приближённое решение задачи нелинейного программирования, если целевая функция и функции в системе ограничений сепарабельные; - рассмотреть задачу распределения двух видов ресурсов для выпуска двух наименований изделий: где aij , bi , cj – случайные. 16. Управление в условиях неопределённости Разобрать вопросы: - чем занимается математическая теория игр; - что такое конфликтные ситуации; - что такое игра; - как условно можно выразить результат игры; - какая игра называется игрой с нулевой суммой; - как представляется развитие игры во времени; - что такое случайный ход; - что такое сознательный ход; - для чего нужна платёжная матрица, чему в ней соответствуют строки и столбцы, что означают элементы матрицы; - цель теории игр; - какая стратегия является предпочтительной для первого игрока А; - что такое цена игры; - как находится минимаксный выигрыш; - в каком случае цена игры называется чистой, как её ещё называют по-другому; - разрешить следующую конфликтную ситуацию: Конструктор получил задание разработать определённое новое изделие. В результате исследований он определил три возможных варианта изделия V1 , V2 , V3 , каждый из которых может быть реализован каким-либо из трёх техпроцессов Т1 , Т2 , Т3 . Если первый вариант конструкции V1 реализуется по первой технологии Т1 , то внешний вид изделия оказывается наилучшим и оценивается экспертами в 9 баллов, а при реализации по второй технологии – в 6 баллов, по третьей – в 5 баллов и т. д. (табл.). Конструкция Технология Т1 Т2 Т3 V1 9 6 5 5 (Т3 ) V2 8 7 7 7 (Т2 или Т3 ) V3 7 5 8 5 (Т2 ) 9 7 8 Конфликтная ситуация возникает из-за того, что затраты на реализацию каждого конструкторско-технологического решения (варианта) не одинаковы. Для простоты полагаем, что затраты пропорциональны внешнему виду (чем выше балл, тем больше затраты). Конструктор должен представить только один вариант, конечно, самый красивый. Но он понимает, что тогда найдутся сторонники самого дешёвого варианта (экономисты). Поэтому его задача – выбрать оптимальный вариант по внешнему виду и стоимости. - в каком случае применяют смешанные стратегии, как называется такая тактика; - что такое смешанная стратегия данного игрока; - как находится цена игры при смешанных стратегиях; - найти решение игры, заданной матрицей 17. Оценка риска в «играх с природой» Разобрать вопросы: - какие ситуации называют играми с природой; - как по платёжной матрице можно оценить возможные исходы: минимальный выигрыш и максимальный проигрыш; - какой показатель называют риском; - максимальный критерий Вальда; - критерий пессимизма-оптимизма Гурвица; - критерий минимаксного риска Сэвиджа; - определить наиболее выигрышную политику продаж, если известна матрица условных вероятностей Pij продажи старых товаров С1 , С2 , С3 при наличии новых товаров Н1 , Н2 , Н3 (табл.). Старые товары Новые товары Н1 Н2 Н3 С1 0,6 9 0,3 6 0,1 4 С2 0,2 8 0,7 3 0,1 7 С3 0,1 5 0,4 5 0,5 8 При принятии решения: 1) вычислить показатели риска; 2) проанализировать критерий по известным вероятностным состояниям «природы»; 3) проанализировать критерий пессимизма-оптимизма Гурвица; 4) проанализировать критерий минимаксного риска Сэвиджа. 18. Теория игр План: А) Геометрическая интерпретация игровых задач В данном пункте плана решить задачи: 1) Решить игру, заданную матрицей ; В1 В2 2) Решить игру, заданную матрицей 3) Решить игру, заданную матрицей ; 4) Пусть предприятие планирует производство на массовый рынок нового изделия. Спрос на это изделие не может быть точно определён. Однако можно предположить, что его величина будет характеризоваться тремя возможными состояниями (I, II, III). С учётом этих состояний анализируются три возможных варианта (модификации) конструкции изделия (А, Б, В), каждый из которых требует своих затрат и обеспечивает различный эффект (цену, прибыль). Прибыль, которую получит предприятие при данном объёме производства и соответствующем состоянии спроса, определяется матрицей: I II III Требуется выбрать такой вариант изделия, величина предложения которого обеспечит среднюю прибыль при любом уровне спроса; 5) Предприятие планирует производство двух изделий А, Б с неопределённым спросом, предполагаемый уровень которого характеризуется двумя состояниями I, II. В зависимости от этих состояний прибыль предприятия различна и определяется платёжной матрицей