СодержаниеТема: Экономико-математическое моделирование. Решение задач на примере задачи о назначениях.
Введение………………………………………………………………………3
1. Основные методы решения задач экономико-математического моделирования……………………………………..…………………..…….6
2. Формулировка задачи о назначениях………………………………..9
3. Решение задачи о назначениях с использованием Mathcad………..11
Заключение…………………………………………………………………...16
Литература……………………………………………………………………17
Введение.
В определенной мере создание математического программирования и его прикладной аспект связаны с выходом в 1939 г. монографии Л.В. Канторовича "Математические методы в организации и планировании производства", где впервые была поставлена и решена задача линейного программирования - частный случай общей задачи математического программирования [4].
Однако интенсивные исследования в этой области начались лишь в конце сороковых годов, когда американским математиком Д. Данцигом был построен изящный алгоритм симплексного метода для линейных программ. Значительный вклад в теорию и методы линейного программирования внесли С. Гасс, А. Таккер, Р. Гомори, Г. Кун, Т. Саати, Г. Ваг-нер, Д.Б. Юдин, Е.Г. Гольштейн, В.А. Булавский, Г.Ш. Рубинштейн, С.И. Черников, С.И. Зуховицкий и другие. В эти же годы в работах Л.Форда и Д.Фалкерсона развиты методы решения частного случая линейных программ - задач транспортного типа (классическая транспортная задача была сформулирована Ф.Хичкоком в 1941 г.).
В пятидесятые годы в работах Г. Куна, А. Таккера, Г. Зойтендейка, Л. Гурвица и других получают развитие методы нелинейного программирования.
В 1957 г. появляется монография выдающегося американского математика Р. Беллмана, положившая начало одному из оригинальных методов исследования многошаговых процессов принятия решений - методу динамического программирования. Большой вклад в развитие методов оптимизации подобных задач внесла группа советских математиков во главе с Л.С. Понтрягиным.
В те же годы начинается интенсивное развитие другого крупного раздела исследования операций - теории игр, история которой связана с именем Джона фон-Неймана, сформулировавшего в 1927 г. основную теорему этой теории.
Создание электронных вычислительных машин оказалось немаловажным стимулом развития численных методов оптимального планирования и управления, ставших обычным инструментом исследования в различных областях человеческой деятельности. Резко увеличив вычислительные возможности человека, ЭВМ стимулировали появление методов стохастического моделирования (методов Монте-Карло), совершенно нереальных при ручных вычислениях и "подающих надежду на спасение" при решении задач большой размерности.
Не затрагивая пока других методов исследования операций, остановимся на задачах математического программирования.
Вообразите себя одним из руководителей крупного производства, показатели работы которого вас не устраивают. Вы хотели бы осуществить мероприятия по увеличению объема выпуска продукции, повышению качества, снижению себестоимости, обеспечению ритмичности и многие другие.
Если поставить перед собой задачу достижения всех этих целей, то окажетесь в положении охотника за многими зайцами - такая задача некорректна. Равно как у человека развитие мускулатуры не должно входить в противоречие с его умственным развитием (хотя и говорят: сила есть - ума не надо), так и для производства нужна некоторая глобальная цель, гармонично сочетающая локальные цели на основе выбранной системы уровней значимости или требующая поддержания всех целей на каком-то предельном уровне.
Очевидно, что достижение цели зависит от множества различных факторов (количества рабочих, уровня их квалификации, фондовооруженности, запасов сырья и т.п.).
Если вам известны формы зависимостей целей от факторов, которыми можно управлять, то возникает задача поиска сочетания значений производственных факторов, обеспечивающего оптимум для поставленной цели.
Задача поиска экстремума (максимума или минимума) некоторой функции при наличии ограничений на значения ее переменных и составляет общую задачу математического программирования.
1. Основные методы решения задач математического программирования.
Пусть стоит задача поиска максимума функции F(x) при простейших условиях A≤ X ≤ B .
Классическая математика предлагает взять производную от F(x), приравнять нулю, решить полученное уравнение и затем, например, выбрать максимальное из значений F(x), вычисленных на концах интервала и в "критических" точках, попавших в этот интервал.Введение2. Формулировка задачи о назначениях.
Задача.
Рассмотрим такую задачу. Фирме необходимо заполнить m вакантных должностей, на которые имеются n претендентов. Каждый из них может занять любую, но одну из предлагаемых должностей. Пусть претенденты и должности пронумерованы соответственно последовательными числами от 0 до n-1 и от 0 до m-1. В силу многих обстоятельств (способности, образование, опыт, коммуникабельность и т.п.) полезность каждого кандидата для фирмы зависит от должности, на которую он будет назначен. Пусть возможный доход фирмы за конкретный промежуток времени при принятии претендента j (j=0,1,…,n-1) на должность i (i=0,1,…,m-1) известен и равен Ui,j. Матрицу U = || Ui,j || (i = 0,1,…,m-1; j = 0,1,…,n-1) назовем матрицей доходов. Если nm, то n-m претендентов работу не получат. Определить такое назначение работников на должности, при котором фирма будет иметь наибольший доход. Подобное назначение называют оптимальным, а саму задачу задачей о назначении.
Для данной задачи требуется определить наименьшее время, за которое будет разработано пять программ каждым из пяти программистами. Остальные условия соответствуют условиям задачи о назначениях.
Задача 4. Фирма получила заказы на разработку пяти программных продуктов. На фирме работают пять квалифицированных программистов, которым можно поручить выполнение этих заказов. Каждый программист дал оценку времени (в днях), которое ему требуется для разработки программ. Эти оценки приведены в таблице.
Программа 1 2 3 4 5
Программист
Волков 46 59 24 62 67
Лисицын 47 56 32 55 70
Медведев 44 52 19 61 60
Зайцев 47 59 17 64 73
Барсуков 43 65 20 60 75
Выполнение каждого из пяти заказов фирма решила поручить одному программисту. Требуется распределить работу между программистами так, чтобы суммарное время, затраченное ими на разработку всех программ, было минимальным.
Решение данной задачи рассмотрим в следующем пункте.
3. Решение задачи о назначениях с использованием Mathcad.
Пусть претенденты и должности пронумерованы соответственно последовательными числами от 0 до n-1 и от 0 до m-1 (см. рис.7). В силу многих обстоятельств (способности, образование, опыт, коммуникабельность и т.п.) полезность каждого кандидата для фирмы зависит от должности, на которую он будет назначен [3,4]. Пусть возможный доход фирмы за конкретный промежуток времени при принятии претендента j (j=0,1,…,n-1) на должность i (i=0,1,…,m-1) известен и равен Ui,j. Матрицу U = || Ui,j || (i = 0,1,…,m-1; j = 0,1,…,n-1) назовем матрицей доходов. Если nm, то n-m претендентов работу не получат. Определить такое назначение работников на должности, при котором фирма будет иметь наибольший доход. Подобное назначение называют оптимальным, а саму задачу задачей о назначении []. Ясно, что оптимальное решение может оказаться не единственным.
Написать рекурсивную программу-функцию, находящую одно из оптимальных решений задачи о назначениях при n претендентах, m должностях и матрице доходов U = || Ui,j || (i = 0,1,…,m-1; j = 0,1,…,n-1).
Пусть матрица доходов U определена вне программы, то есть искомые функции могут считать её глобальным параметром.
Рассмотрим сначала случай n=m. Решением задачи могут служить функция assign() с рекурсией по номерам работников и программа-константа assign. Поскольку в данной ситуации и рекурсия, и возвраты назад реализуются по той же самой схеме, что и в предыдущих задачах, ограничимся лишь описанием параметров функции assign() и их начальных значений, подготавливаемых программой-константой assign. Решение задачи возвращается в виде вектора ot = (ot0, ot1 ,..., otn-1, otn)T, где otj номер должности для работника с номером j (j = 0, 1, …, n-1), а otn доход от данного оптимального назначения.Литература. Алексеев В.Р., Чеснокова О.В. Mathcad 12. – М.: НТ Пресс, 2005. – 345с.
2. Плис А.И., Сливина Н.А. Mathcad: Математический практикум для экономистов и инженеров. – М.: Финансы и статистика, 1999. – 656с.
3. http://www.mgopu.ru/PVU/2.1/Recurs/BacketTm/CnReturn/task_set.htm
4. http://vtit.kuzstu.ru/books/shelf/book1/sod/sod.html
|
|
