Задание 3. Задача о назначениях
Имеются n рабочих и m видов работ. Стоимость Сij выполнения i-м рабочим j-й работы приведена в таблице, где рабочему соответствует строка, работе - столбец.
Необходимо составить план работ так, чтобы все работы были выполнены, каждый рабочий был занят на только одной работе, а суммарная стоимость всех работ была минимальной.
| i\j | ||||||
Решение.
Математическая модель задачи:
Данная задача является несбалансированной, т.е. число работ больше числа работников. Вводим фиктивное число строк (одну) числа работников стоимости выполнения работ в которой будут равняться нулю.
| i\j | ||||||
Если i-м рабочим выполняется j-ая работа, то обозначим факт выполнения Xij=1 и Xij=0 если работа не выполняется. Тогда математическая модель задачи имеет вид
Задаем ограничения
Для решения задачи с помощью Поиск решения в MS Excel под неизвестные отведем диапазон B14:F18. В ячейку G20 введем значение целевой функции = СУММПРОИЗВ(B4:F8;B14:F18) - вычисляющую стоимость работ. Введем формулы задающие левые части ограничений
Используя надстройку MS Excel «Поиск решения» (инструмент для поиска и решения уравнений и задач оптимизации) на вкладке «Данные» группы «Анализ»
заполняем диалоговое окно
В диалоговом окне параметры Поиска решения включаем checkbox Линейная модель
Далее OK, кнопка Выполнить.
Получаем результат решения задачи
Таким образом, получаем оптимальный план работ где
1-й работник выполняет 4-ую работу;
2-й работник выполняет 5-ую работу;
3-й работник выполняет 1-ую работу;
4-й работник выполняет 2-ую работу;
5-й работник выполняет 3-ую работу;
При этом суммарная стоимость выполняемых работ будет минимальной и равна 10 ед.
Покажем полученный результат в отчете по результатам MS Excel
Материалы тестовой системы
Материалы тестовой системы для проведения текущего, промежуточного и итогового контроля представлены в электронном приложении в банке данных кафедры, учебно-методического отдела и учебной библиотеки Волгоградского филиала Образовательного учреждения профсоюзов высшего профессионального образования «Академия труда и социальных отношений».
Перечень вопросов к экзамену по дисциплине
1. Методы оптимальных решений.
2. Постановка задачи для построения модели задачи оптимизации.
3. Критерий оптимизации и целевая функция.
4. Что такое линии уровня целевой функции?
5. Дайте формулировку детерминированной статической задачи оптимизации.
6. Назовите причины неопределенности в параметрах математической модели и объясните ее влияние на решение.
7. Что такое рациональное поведение с точки зрения теории оптимизации?
8. Как методы оптимизации используются при принятии экономических решений?
9. Расскажите об использовании оптимизации в задачах идентификации параметров математических моделей.
10. Сформулируйте общую задачу нелинейного программирования.
11. Сформулируй те необходимое условие локального максимума в общей задаче нелинейного программирования
12. Что такое функция Лагранжа?
13. Сформулируйте и докажите достаточное условие оптимальности с помощью функции Лагранжа.
14. Сформулируйте условие дополняющей нежесткости и дайте его экономическую интерпретацию.
15. Дай те экономическую интерпретацию множителей Лагранжа.
16. С сформулируйте задач у линейного программирования.
17. Приведите содержательные примеры задачи линейного программирования.
18. Что такое нормальная (стандартная) и каноническая формы задачи линейного программирования?
19. Сформулируйте двойственную задачу линейного программирования.
20. Сформулируйте теоремы двойственности в задаче линейного программирования.
21. Примените графический метод для решения конкретной задачи линейного программирования
22. Симплекс-методы решения задач линейного программирования.
23. Возможности среды MS Excel для решения задач линейного программирования?
24. Сформулируйте задачу выбора решений в условиях неопределенности.
25. Назовите и сформулируйте критерии выбора решений в условиях неопределенности (принцип гарантированного результата, критерий Гурвица, критерий Байеса- Лаиласа, критерий Сэвиджа).
26. Как используется вероятностная информация о параметрах в задачах принятия решений при случайных параметрах.
27. В чем состоит принятие решений на основе математического ожидания?
28. Как учитывается склонность к риску?
29. Приведи те примеры многошаговых систем в экономике.
30. В чем состоя т особенности динамических задач оптимизации?
31. Приведите примеры динамической задачи оптимизации.
32. В чем состоит метод динамического программирования в многошаговых задачах оптимизации?
Список основной и дополнительной литературы,
Сайтов сети Интернет
Основная литература:
1. Акулич, Иван Людвигович. Математическое программирование в примерах и задачах : учеб. пособие / И. Л. Акулич. - Изд. 2-е, испр. - СПб. [и др.] : Лань, 2009. - 347 с. : ил. - (Учебники для вузов. Специальная литература). - Библиогр.: с. 346-347. - ISBN 978-5-8114-0916-7
2. Балдин, К. В. Математическое программирование : учебник / К. В. Балдин, Н. А. Брызгалов, А. В. Рукосуев ; под общ. ред. К. В. Балдина. - М. : Дашков и К, 2009. - 218 с. : рис., табл. - Библиогр.: с. 199-202 (62 назв.). - ISBN 978-5-91131-924
3. Высшая математика для экономических специальностей. Учебник и практикум : учеб. для студентов вузов, обучающихся по экон. специальностям... / , Борис Александрович Путко, Иван Михайлович Три- шин, Мира Насоновна Фридман; авт., ред. Наум Шевелевич Кремер. - 2-е изд., перераб. и доп. - М. : Высшее образование, 2008 - .Ч. I и II. - 2-е изд., пе- рераб. и доп. - 893 с. : ил. - (Основы наук). - ISBN 978-5-9692-02 02
4. Красс, Максим Семенович. Математические методы и модели для магистрантов экономики [Текст] : учеб. пособие для студентов, обучающихся в магистратуре по направлению "Экономика" и др. экон. специальностям / М. С. Красс, Б. П. Чупрынов. - 2-е изд., доп. - СПб. [и др.] : Питер, 2010. - 496 с. : рис., табл. - (Учебное пособие). - Библиогр.: с. 486-492. - Предм. указ.: с. 493-496. - ISBN 978-5-49807-811-3 : 203.42 р.
5. Красс, Максим Семенович. Математика для экономистов : учеб. пособие для студентов вузов, обучающихся по специальностям 060400 " Финансы и кредит", 060500 "Бухгалт. учет, анализ и аудит", 060600 "Мировая экономика", 351200 "Налоги и налогообложение" / М. С. Красс, Б. П. Чупрынов. - СПб. [и др.] : Питер, 2008. - 464 с. : граф., рис., табл. - (Учебное пособие). - Библиогр.: с. 461 (13 назв.). - ISBN 978-5-94723-672-9
6. Математика для экономистов. Задачник : учеб. -практ. пособие для студентов вузов, обучающихся по специальности "Прикладная информатика (по обл.)" и др. специальностям / [Р. И. Горбунова [и др.]; под ред. С. И. Макарова и М. В. Мищенко. - М. : КноРус, 2008. - 358 с. : рис. - ISBN 978-5-85971-903-7ББК В11я73
7. Общий курс высшей математики для экономистов : учеб. для студентов вузов, обучающихся по экон. специальностям / [Б. М. Рудык [и др.]; под ред. В. И. Ермакова ; Рос. экон. акад. им. Г. В. Плеханова. - М. : ИНФРА-М, 2008. - 657 с. : рис., граф. - (100 лет РЭА им. Г. В. Плеханова). - Библиогр. в конце гл. - ISBN 978-5-16-002870-5ББК В11я73
8. Высшая математика в упражнениях и задачах : в 2 ч.: [учеб. пособие для вузов] / П. Е. Данко [и др.]. - 7-е изд., испр. - М. : ОНИКС: Мир и Образование, 2009.Ч. 2. - 448 с. : рис. - ISBN 978-5-488-02280-5. - ISBN 978-5488-02449-6. - ISBN 978-5-94666-565-0. - ISBN 978-5-94666-567-4
9. Кремер, Наум Шевелевич. Математика для экономистов: от Арифметики до Эконометрики : учеб. -справ. пособие для студентов вузов, обучающихся по специальности 080116(061800) "Мат. методы в экономике" и др. экон. специальностям / Н. Ш. Кремер, Б. А. Путко, И. М. Тришин; под ред. Н. Ш. Кремера. - М. : Высшее образование, 2009. - 646 с. : рис., табл. - (Основы наук). - Библиогр.: с. 597-602 (79 назв.). - Предм. указ.: с. 613-646. - ISBN 978-5-9692-0385-3
10. Высшая математика для экономистов. Практикум : учеб. пособие для студентов вузов, обучающихся по экон. специальностям / [Н. Ш. Кремер [и др.]; под ред. Н. Ш. Кремера. - 2-е изд., перераб. и доп. - М. : ЮНИТИ, 2010. - 478 с. : рис. - (Золотой фонд российских учебников). - ISBN 978-5-238-01122-6
Дополнительная литература:
1. Акулич И. Л. Математическое программирование в примерах и задачах. М.: Высшая школа, 1993
2. В. Б. Грахов Линейное программирование в упражнениях и задачах. Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2006
3. Ермаков В. И. и другие. Высшая математика для экономистов, М.: Инфра-М, 2008
4. Калихман И. А. Линейная алгебра и программирование. М.: Высшая школа, 1967
5. Карпелевич Ф. М., Садовский Я. И. Элементы линейной алгебры и линейного программирования. М.: Наука, 1967
6. Лунгу К. Н. Линейное программирование: руководство к решению задач. М.: Физматлит, 2005.