Математические методы принятия решений

На втором этапе происходит процесс назначения:

первым шагом назначаем как можно больше работ тем исполнителям, которые могут их выполнить за нулевую стоимость. № 1№ 2№ 3№ 4№ 5№ 6№ 7№ 1 5 731 250№ 2 333 011№ 3 9 234 402№ 4 953 411№ 5 139 910 130№ 6 116 023 610№ 7 24 500 110

Назначение невозможно (в столбце № 5 нет выделенных нулей), т. е. на маршрут № 5 нет кандидатов с нулевой стоимостью. вторым шагом проводим модификацию таблицы. Отметим все строки без назначения и минимальное количество строк и столбцов, содержащих выделенные нули:№ 1№ 2№ 3№ 4№ 5№ 6№ 7№ 1 5 731 250№ 2 333 011№ 3 9 234 402№ 4 953 411№ 5 139 910 130№ 6 116 023 610№ 7 24 500 110

Из неокрашенных элементов находим наименьший, вычитаем его из всех неокрашенных и прибавляем ко всем дважды окрашенным элементам.№ 1№ 2№ 3№ 4№ 5№ 6№ 7№ 1 4 630 150№ 2 433 112№ 3 8 133 302№ 4 1 053 512№ 5 2 989 130№ 6 15 012 610№ 7 24 600 121

Далее повторяем шаги второго этапа. Назначаем как можно больше работ тем исполнителям, которые могут их выполнить за нулевую стоимость. № 1№ 2№ 3№ 4№ 5№ 6№ 7№ 14 630 150№ 2 433 112№ 3 8 133 302№ 4 1 053 512№ 5 2 989 130№ 6 15 012 610№ 7 24 600 121

Назначение возможно, т.к. в каждой строке и в каждом столбце ровно один выделенный ноль. В исходной таблице назначение отметим следующим образом:

Маршруты

Водители№ 1№ 2№ 3№ 4№ 5№ 6№ 7№ 1 (Абрикосов)

7 843 561№ 2 (Бананов)

32 567 213№ 3 (Виноградов)

12 457 824№ 4 (Грушин)

211 076 512№ 5 (Дынин)

56 121 315 163№ 6 (Клюквин)

418 257 812№ 7 (Лимонов)

Вычислим суммарные затраты транспортной компании на зарплату водителям:.Вывод: чтобы минимизировать суммарные затраты транспортной компании на зарплату водителям, необходимо распределить водителей по маршрутам в соответствии со следующей таблицей:

Маршрут

Водитель№ 1Бананов№ 2Грушин№ 3Клюквин№ 4Абрикосов№ 5Лимонов№ 6Виноградов№ 7Дынин

При этом минимальные суммарные затраты на зарплату водителям составят 17 у.е.Заметим, что на последнем шаге алгоритма можно выбрать другой вариант назначения:№ 1№ 2№ 3№ 4№ 5№ 6№ 7№ 14 630 150№ 2 433 112№ 3 8 133 302№ 4 1 053 512№ 5 2 989 130№ 6 15 012 610№ 7 24 600 121

Суммарные затраты. Таким образом, можно задать еще один вариант распределения водителей по маршрутам:№ 1Грушин№ 2 Бананов№ 3 Клюквин№ 4 Абрикосов№ 5 Лимонов№ 6 Виноградов№ 7 Дынин

Суммарные затраты при этом не изменятся. Динамическое программирование

Производственная компания собирается вложить 50 млн. рублей в развитие своих подразделений. Данные по доходам в зависимости от размера инвестиций представлены таблицей (в млн. руб.):Доход подразделений

ИнвестицииИсследова-тельская лаборатория

Отдел информаци-онных систем

Проектный отдел

Технологи-ческий отдел10 201 815 162 022 211 594 532 910 520 468 463 056 276 271 661 056

Требуется распределить инвестиции таким образом, чтобы доход был максимальным. Выделим этапы оптимизации: добавление подразделение в распределение денежных средств. Запишем рекуррентное соотношение Беллмана:;;;.Шаг 1. Начнем распределение средств, предполагая, что вся сумма идет на развитие подразделения № 1 (лаборатория). Тогда значения совпадают со значениями, т.к. функция возрастает. Запишем их в таблицу:

Шаг 2. Добавим к рассмотрению подразделение № 2. Вычислим значения функции :;;Запишем значения функции в таблицу:

Шаг 3. Добавим к рассмотрению подразделение № 3. Вычислим значения функции :;;Запишем значения функции в таблицу:

Шаг 4. Добавим к рассмотрению подразделение № 4. Вычислим значения функции :;;Запишем значения функции в таблицу:

Поскольку все инвестиции должны быть освоены, то оптимальному плану распределения соответствует значение функции. Выполним обратный проход для получения оптимального решения:;;;.Таким образом, оптимальное решение имеет вид:. Максимальный доход равен

Вывод: чтобы получить максимальный доход от вложения денежных средств в размере 50 млн.

руб. в развитие компании, необходимо распределить их по подразделениям в соответствии со следующей таблицей. Инвестиции, млн.

руб

Исследова-тельская лаборатория

Отдел информаци-онных систем

Проектный отдел

Технологи-ческий отдел5 010 201 010

При этом максимальный доход составит 72 млн.

руб.Заключение

В работе рассмотрены некоторые математические методы, используемые при решении управленческих задач. При исследовании транспортной задачи даны математические модели замкнутого и открытого типа, рассмотрены задачи с ограничениями. Решена транспортная задача с ограничениями на пропускную способность, что усложнило применение стандартных методов. Возникла необходимость приводить задачу к замкнутой модели, чтобы иметь возможность решить ее методом потенциалов. Для решения задачи о назначениях, которая является моделью разного типа проблем, был использован венгерский алгоритм, специально разработанный для решений задач этого класса. Отметим, что в работе приведена матричная интерпретация этого метода. Оказалось, что задача о назначениях может быть решена неоднозначно. В нашем случае получилось два распределения, приводящих к минимальным затратам. Таким образом, при принятии окончательного решения нужно учитывать дополнительные факторы реальной задачи либо выбирать вариант случайным образом. Метод динамического программирования применяется для решения задач разных классов.

В работе рассмотрен общий подход, описан принцип оптимальности Беллмана. Практическая часть работы выполнена для модели динамического распределения ресурсов. Вычислено значение функции эффективности с использованием рекуррентных соотношений Беллмана. По каждой задаче сделаны выводы, позволяющие принять управленческое решение. Литература

Красс М.С., Чупрынов Б. П. Основы математики и ее приложения в экономическом образовании: Учебник. — М.: Дело, 2003. — 688с. Вентцель Е. С. Исследование операций. М.: Высшая школа, 2007. — 208с. Вентцель Е. С. Исследование операций: задачи, принципы, методология: учебное пособие / Е. С. Вентцель.

М.: КНОРУС, 2010. — 192с. Исследование операций в экономике: Учеб.

пособие для вузов / Н. Ш. Кремер, Б. А. Путко, И. М. Тришин, М. Н. Фридман; под ред. проф. Н. Ш. Кремера. -

М.: ЮНИТИ, 2000. — 407с. Акулич И. Л. Математическое программирование: Учебное пособие. — Лань, 2011. — 352с. Прикладные задачи исследования операций: Учеб.

пособие / М. Ю. Афанасьев, К. А. Багриновский, В. М. Матюшок. — М.: ИНФРА-М, 2006. — 352с. Волков И. К., Загоруйко Е. А. Исследование операций: Учеб.

для вузов / под ред. В. С. Зарубина, А. П. Крищенко. — М.:Изд-во МГТУ им. Н. Э. Баумана, 2000. — 436с. Партыка Т. Л., Попов И. И. Математические методы: учебник. -

М: ФОРУМ: ИНФРА-М, 2005. — 464с. Шикин Е. В., Шикина Г. Е. Исследование операций. М.: Проспект, 2006. — 280 с. Косоруков О. А., Мищенко А. В. Исследование операций.

Учебник для вузов. — М.: Экзамен, 2003. — 448с. Банди Б.

Основы линейного программирования: Пер. сангл. — М.: Радио и связь, 1989. -

176с.Таха, Хемди А.

Введение

в исследование операций: Пер. с англ. — М.: Вильямс, 2005. — 912с. Конюховский П. В.

Математические методы исследования операций в экономике — СПб: Питер, 2000. — 208с.