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

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

Содержание
Введение 3
1. Теоретические основы математических методов принятия решений 4
1.1. Транспортная задача с ограничением на пропускную способность 4
1.2. Задача о назначениях 7
1.3. Динамическое программирование 9
2. Решение задач 11
2.1. Транспортная задача с ограничением на пропускную способность 11
2.2. Задача о назначениях 21
2.3. Динамическое программирование 27
Заключение 32
Литература 33

Введение

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

Выбирается (окрашивается) минимально возможно количество строк и столбцов, содержащих нули. Из неокрашенных элементов находится наименьший, его значение вычитается из всех неокрашенных и прибавляем ко всем дважды окрашенным элементам.Далее повторяются все шаги второго этапа, пока назначение не выполнится.Динамическое программированиеДля решения любой многошаговой задачи можно применять разные методы. Можно искать сразу все элементы решения на всех этапах. Другой вариант – строить оптимальное решение по шагам и проводить оптимизацию решения на каждом этапе расчета.Метод динамического программирования специально приспособлен к многошаговым операциям. В его основу заложена идея пошаговой оптимизации. Это могут быть этапы развития предприятия, последовательности испытаний оборудования, задачираспределения инвестиций и т.д. Деление на этапы можно выполнить принудительно, выбирая в качестве шага некоторый интервал времениМатематическая модель задачи динамического программирования имеет вид:Здесь – выигрыш операции, – локальная функция выигрыша на каждом этапе, – распределяемый ресурс, – переменная, объем ресурсов на этапе i.При решении задач методом динамического программирования используется принцип оптимальности Беллмана. Он заключается в том, что каково бы ни было состояние системы перед очередным шагом, надо решение выбирать так, чтобы полезный эффект на данном шаге в сумме с оптимальным полезным эффектом на всех предыдущих шагах был максимальным.Исходя их этого принципа, строятся рекуррентные соотношения для определения функции полезности:;;…;….В результате первого прохода метода находятся условные оптимальные решения на всех шагах и условный выигрыш на каждом шаге. Второй проход в обратном направлении позволяет определить безусловные решения и оптимальное решение всей задачи в целом.Глава 2.Транспортная задача с ограничением на пропускную способностьТранспортная компания в городе обслуживает 4 хлебозавода и 4 магазина хлебобулочных изделий. Количество производимой продукции, объем поставок в магазины и затраты на доставку приведены в транспортной таблице:Магазин №1Магазин №2Магазин №3Магазин №418090270180Х/з №1901341Х/з №29032913Х/з №31803458Х/з №41804564Требуется найти такие способы перевозки продукции в магазины, чтобы суммарные затраты были минимальны при заданных ограничениях: .Условие баланса не выполняется: .Таким образом, имеется открытая модель с дефицитом. Чтобы задача имела решение, вводится фиктивный поставщик с запасами . Стоимость перевозок от фиктивного поставщика . Тогда транспортная таблица будет иметь вид:180902701809013419032913180345818045641800000Так как , то вместо 1 потребителя с величиной спроса вводим двух других: 1 потребителя с величиной спроса и потребителя с величиной спроса . Стоимость перевозки не меняется, а стоимость устанавливается очень большим числом. Так как , то величина предложения в пункте 4 и величина спроса в пункте 4 уменьшается на эту величину , . Тогда транспортная таблица будет иметь вид:909027090909013411903291331803458100904564418000000Построим опорное решение методом северо-западного угла. В транспортной матрице выбираем клетку в левом верхнем углу. В нее заносим минимальное значение из двух величин (поставка и потребление). Остальные клетки строки или столбца, для которых выполнен баланс, вычеркиваем. Пересчитываем поставки и потребление с учетом выбранного элемента.90-90=090270909090-90=0190341190х29133180х45810090х5644180х0000Переходя к соседней клетке по строке, заполняем перевозки. В данном случае перевозка будет равна нулю.90-90=090270909090-90=01903041190х29133180х45810090х5644180х0000Переходим к соседней клетке по столбцу, аналогично выбирая минимум между поставкой и потреблением. Аналогично заполняем всю таблицу:909027090909019030ххх90х29090хх180хх5180хх90хх69040х180ххх090090Количество занятых клеток в таблице должно быть равно . Условие выполняется, следовательно, получено опорное решение. Вычислим значение целевой функции (затраты на перевозку) при этом решении, скорректировав его с учетом ограничения – добавим зарезервированные 90 единиц продукции:Построим опорное решение методом минимальной стоимости. В транспортной матрице выбираем клетку, в которой записана минимальная стоимость. В нее заносим минимум из двух величин (поставка и потребление). Запасы фиктивного поставщика распределяются в последнюю очередь, хотя стоимость перевозок нулевая. Остальные клетки строки или столбца, для которых выполнен баланс мощности, вычеркиваем.90-90=090270909090-90=0190341190х29133180х45810090х5644180х0000Далее выбираем минимальную из оставшихся стоимостей:90-90=090270909090-90=0190хх10х90х29133180х45810090х5644180х0000Далее выбираем минимальную из оставшихся стоимостей и аналогично заполняем всю таблицу:9090270909090190хх10х90х290хх30180хх5180хх90ххх49040180хх090х090Вычислим значение целевой функции (затраты на перевозку) при этом решении, скорректировав его с учетом ограничения :Построим оптимальное решение методом потенциалов. В качестве опорного выберем решение, полученное методом минимальной стоимости.9090270909090190341019032909133018034518081009045649040180000900090Шаг 1. Составим систему потенциалов по заполненным клеткам транспортной матрицы:V1V2V3V4V5U119034101U2329091330U33451808100U445649040U5000900090Количество неизвестных потенциалов больше количества уравнений, значит, система имеет бесконечное множество решений. Чтобы получить одно из них зададим произвольное значение одной из переменных, например, . Тогда однозначно найдем остальные:Для полученной системы потенциалов проверим неравенства для свободных клеток матрицы и отметим нарушения неравенств:Выберем клетку, для которой неравенство нарушается:. Из клетки строим цикл пересчета, чередуя знаки «+» и «–»:V1V2V3V4V5U11 –90341 +01U232909133 0U33 +45 –1808100U44564 –904 +0U5000 +9000 –90Из клеток, отмеченных знаком «–», выбираем минимальное значение переменной – 90. Производим пересчет, вычитая 90 из «отрицательных» клеток, и прибавляя к «положительным» клеткам:V1V2V3V4V5U11 –341 +901U232909133 0U33 +9045 –908100U44564 –04 +90U5000 +18000 –0В результате получили новое решение, которое нужно проверить на оптимальность методом потенциалов.Шаг 2. Составим систему потенциалов по заполненным клеткам транспортной матрицы:Положим . Тогда однозначно найдем остальные:Для полученной системы потенциалов проверим неравенства для свободных клеток матрицы и отметим нарушения неравенств:Все неравенства выполняются, значит, полученное решение является оптимальным.90902709090901 341 9019032909133 01803 9045 908100904564 04 90180000 18000 0Скорректируем решение с учетом ограничения . Для этого объем продукции, поставляемой 5 потребителю, прибавляем к величинам перевозок 1 потребителя. Учитывая ограничение , восстанавливаем резерв 4 потребителя и 4 производителя. Тогда решение будет иметь вид:9090270180901 341 90903 02909131803 9045 9081804 90564 901800 000 1800Вычислим значение целевой функции (затраты на перевозку:Вывод: Магазин №1Магазин №2Магазин №3Магазин №418090270180Х/з №1901 341 90Х/з №2903 0290913Х/з №31803 9045 908Х/з №41804 90564 901800 000 1800С хлебозавода №1 всю продукцию (90 единиц) следует поставлять в магазин №4. С хлебозавода №2 всю продукцию (90 единиц) следует поставлять в магазин №2. С хлебозавода №3 90 единиц продукции следует поставлять в магазин №1 и 90 единиц продукции – в магазин №3. С хлебозавода №4 90 единиц продукции следует поставлять в магазин №1 и 90 единиц продукции – в магазин №4.Магазин №3 недополучит 180 единиц продукции.Минимальные совокупные транспортные расходы составят 1710 единиц.