Задание 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-5­488-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.