Теория и методы принятия управленческих решенийСавченко Яна Валерьевна
 Скачать 1.04 Mb.
|
|
Теория и методы принятия управленческих решений Савченко Яна Валерьевна к.э.н., доцент Тема 3 Методы и технологии разработки управленческих решений в условиях определенности Концепция определенности Определенность понимается как такое состояние знания, когда лицо, принимающее решение, заранее знает конкретный исход для каждой альтернативы. Иначе говоря, ЛПР обладает исчерпывающим знанием состояния среды и результатов каждого возможного решения. Методы принятия управленческих решений, в которых параметры управляемой системы определены и не подвержены случайным воздействиям, называются «детерминированными» или «методами принятия решений в условиях полной определенности». В общем случае выработка решений в условиях определенности направлена на поиск максимальной отдачи либо в виде максимизации выгоды (дохода, прибыли иди полезности), либо минимизации затрат. Такой поиск называется оптимизационным анализом. Три метода оптимизации, используются лицом, принимающим решение: предельный анализ, линейное программирование приростной анализ прибыли. Предельный анализ В условиях определенности доходы и затраты будут известны для любого уровня производства и продаж. Задача состоит в том, чтобы найти их оптимальное соотношение, позволяющее максимизировать прибыль. Предельный анализ позволяет сделать это. В нем используются концепции предельных затрат и предельного дохода. Концепции предельных затрат и предельного дохода Предельный анализ Предельный доход (MR) определяется как дополнительный доход (изменение общего дохода), получаемый от продажи дополнительной единицы продукта. Графически он выражается наклоном кривой общего дохода (TR). Предельные затраты (MC) определяются как дополнительные затраты (изменение величины общих затрат) на приобретение или производство дополнительной единицы продукции. Графически они выражаются наклоном кривой общих затрат (TС). Концепции предельных затрат и предельного дохода Предельный анализ Отметим также следующее: 1. При уровнях производства Q1 и Q4 TR в точности равно ТС, так что прибыль равна нулю. Объем производства меньше Q1 или больше Q4 ведет к убыткам (т.е. характеризуется отрицательной прибылью). 2. При уровнях производства больше Q1 или меньше Q4 – прибыль положительная. 3. Предельный анализ показывает, что до тех пор, пока предельный доход MR превышает предельные затраты МС, производство и продажа дополнительной единицы продукции будут повышать прибыль. Прибыль, соответственно, максимизируется при том уровне производства, при котором MR =МС. Концепции предельных затрат и предельного дохода Предельный анализ Равенство MR = МС верно при Q3. При этом уровне производства, если мы проведем одну касательную для кривой ТС, а другую – для кривой МС, то мы увидим, что они будут параллельны, т.е. наклоны обеих кривых будут равны между собой. Это означает, что при уровне производства, равном Q3, MR = МС. При таком уровне производства наклон функции прибыли, или предельна прибыль (МР), будет равна нулю. Концепции предельных затрат и предельного дохода Предельный анализ Следует напомнить, что предельный анализ имеет дело с изменениями значений взаимосвязанных, но неизменных функций. В реальном мире функции спроса, дохода, производства и затрат не могут быть известны достаточно точно и подвергаются изменениям. Тем не менее, эти задачи могут быть решены методом приростного анализа прибыли, развивающим концепцию предельного анализа применительно к более широким практическим задачам. Концепции предельных затрат и предельного дохода Приростной анализ Приростной анализ прибыли оперирует с любыми и всеми изменениями в доходах, затратах и прибылях, явившимися следствием определенного решения. Таким образом, концепция приростного анализа охватывает изменения как самих функций, так и их значений. Основное правило решения состоит в том, чтобы принять любое предложение, повышающее прибыль, или отвергнуть любое предложение, ее уменьшающее. Приростной анализ Поскольку в приростном решении рассматривается только переменные, подвергающиеся изменениям, постоянные слагающие затрат (такие, как страхование и обесценение денег) не рассматриваются. Таким образом, приростные решения относятся к краткосрочной концепции. К сожалению, многие управляющие не используют приростные термины; напротив, они принимают решения исходя из средних значений общих затрат, включая в них постоянные и переменные слагающие (полностью распределенные затраты). Почти всегда краткосрочные решения, основанные на средних значениях полностью распределенных затрат, неверны, если целью фирмы будет максимизация прибыли. Приростной анализ. Пример Дано: Предприятие производит и продает 100 000 шин/мес по 240 руб/шт. Переменные затраты - 140 руб/шт. Постоянные затраты – 6 000 000 руб. Себестоимость - 200 руб/шт. Предложен дополнительный контракт: 25 000 шин/мес. по цене 180 руб/шт. За счет сверхурочных работ переменные затраты увеличатся на 20 руб. и составят 160 руб/шт. Вопрос: Принимать ли это предложение? Для принятия решения воспользуемся методом приростного анализа прибыли. Подсчитаем дополнительную прибыль от контракта. Прирост затрат: 25000 шт/мес * 160 руб/шт = 4 000 000 руб/мес. Прирост дохода: 25000 шт/мес * 180 руб/шт = 4 500 000 руб/мес. Доп. прибыль: 500 000 руб/мес. Согласно методу приростного анализа контракт принимается. Принятие решения традиционным методом (для сравнения) Подсчитаем себестоимость. Переменные затраты: 100000 шт * 140 руб/шт + 25000 шт * 160 руб/шт = 18000000 руб. Постоянные затраты: 6000000 руб. Полные затраты: 24000000 руб. Себестоимость: 192 руб/шт > 180 руб/шт. Предложение отклоняется. Приростной анализ. Пример Дано: Предприятие производит и продает 100 000 шин/мес по 240 руб/шт. Переменные затраты - 140 руб/шт. Постоянные затраты – 6 000 000 руб. Себестоимость - 200 руб/шт. Предложен дополнительный контракт: 25 000 шин/мес. по цене 180 руб/шт. За счет сверхурочных работ переменные затраты увеличатся на 20 руб. и составят 160 руб/шт. Вопрос: Принимать ли это предложение? Для принятия решения воспользуемся методом приростного анализа прибыли. Подсчитаем дополнительную прибыль от контракта. Прирост затрат: 25000 шт/мес * 160 руб/шт = 4 000 000 руб/мес. Прирост дохода: 25000 шт/мес * 180 руб/шт = 4 500 000 руб/мес. Доп. прибыль: 500 000 руб/мес. Согласно методу приростного анализа контракт принимается. Принятие решения традиционным методом (для сравнения) Подсчитаем себестоимость. Переменные затраты: 100000 шт * 140 руб/шт + 25000 шт * 160 руб/шт = 18000000 руб. Постоянные затраты: 6000000 руб. Полные затраты: 24000000 руб. Себестоимость: 192 руб/шт > 180 руб/шт. Предложение отклоняется. Линейное программирование Модели линейного программирования отличаются наглядностью и относительной простотой. Их использование во многих практически важных задачах, связанных с принятием решений, оказалось высокоэффективным, в связи с чем они получили довольно широкое распространение. К числу наиболее известных задач линейного программирования относятся: задачи о распределении ограниченных ресурсов (задачи оптимального планирования); задачи об оптимальной корзине продуктов (задачи о диете, задачи оптимального смешения); задачи оптимального раскроя (материалов, заготовок); транспортные задачи; задачи о назначениях; задачи оптимизации финансовых потоков; задачи оптимизации графиков платежей. Линейное программирование. Пример Предприятие может выпускать n видов продукции Р1, Р2,..., Рn, располагая для этого m различными ресурсами R1, R2,..., Rm в количествах b1, b2,...bm соответственно. Известно, что для выпуска единицы продукции Pj необходимо затратить аij единиц ресурса Rij, i = 1, 2,..., m; j = 1, 2,..., n. Кроме того, известен доход от продажи единицы каждого вида продукции – с1, с2,..., сn соответственно, где cj— стоимость единицы продукта Рj например 1 штуки, 1 тонны и т.п. Требуется так спланировать производственную программу – объемы выпуска каждого вида продукции (в штуках, тоннах и т.п.), – чтобы максимизировать доход предприятия. Формализованное описание задач линейного программирования Для удобства дальнейших выводов и рассуждений сведем исходную ин- формацию в единую таблицу, где через xj обозначим объемы продукции Рj, вы-пускаемой предприятием. Тогда набор переменных {х1,..., xn} представляет собой не что иное, как производственную программу предприятия. Формализованное описание задач линейного программирования Доход, полученный предприятием при производстве продукта Р j в количестве x j составит c j x j , а при реализации производственной программы {x 1 , x 2 ,..., х n } будет равен величине Z=C 1 X 1 + C 2 X 2 + … + C n X n Подсчитаем, какое количество ресурсов будет израсходовано, если выбрать некоторый план {x 1 , x 2 ,..., х n }. Ресурса R 1 потребуется: а 11 x 1 + a 1 2x 1 + ... + а 1n х n , в то время как в наличии имеется b 1 Ресурса R 2 потребуется: а 21 x 1 + a 22 x 2 + ... + а 2n х n , в то время как в наличии имеется b 2 …….. Ресурса R m потребуется: a ml x 1 + a m2 x 2 + ... + а mn х n , в то время как в наличии имеется b m Формализованное описание задач линейного программирования Этапы решения задач детерминированными методами Использование детерминированных методов включает следующие основные этапы (1): 1. Формализация исходной задачи. Этот этап требует исследования предметной области и возникшей проблемы. Выделение ключевых элементов рассматриваемой задачи (перечня альтернатив, ограничений, целевой функции). 2. Построение математической модели. На данном этапе происходит перевод словесного описания в математическую модель одного из стандартных типов. Если модель получилась достаточно сложной, то требуется упрощение. 3. Решение модели. Использование алгоритмов оптимизации для получения решения модели. В рамках данного этапа важно провести анализ «чувствительности»: поведения полученного решения при изменении параметров модели. Этапы решения задач детерминированными методами Использование детерминированных методов включает следующие основные этапы (2): 4. Проверка адекватности модели. Данный этап подразумевает проверку соответствия поведения модели поведению реальной системы, то есть требуется убедиться, что решение имеет смысл. Проводится математический анализ полученных решений и содержательный анализ, в рамках которого проверяется соответствие полученных значений смыслу задачи. 5 Реализация решения. Перевод результатов решения модели в рекомендации для лиц, принимающих решение. Пример решения задачи методом линейного программирования Задача. Предприятие изготавливает два вида краски для наружных и внутренних работ. Для изготовления каждого вида краски используется три типа ресурсов. Расход сырья и доход от продажи единицы краски представлен в таблице. Требуется определить соотношение между видами выпускаемой продукции, максимизирующее ежедневный доход. Расход сырья на тонну краски, т Краска для внутренних работ Краска для наружных работ Максимально возможный ежедневный расход сырья Сырье 1 3,5 1 350 Сырье 2 1 2 240 Сырье 3 1 1 150 Доход на тонну краски, тыс. д.е. 20 10 Пример решения задачи методом линейного программирования Формирование математической модели будет включать несколько этапов: Определение переменных. В данном случае требуется определить ежедневные объемы производства каждой краски. X 1 – ежедневный объем производства краски для внутренних работ; X 2 – ежедневный объем производства краски для наружных работ; Формирование целевой функции. Суммарный доход от реализации всей краски. F(X) = 20 X 1 +10 X 2 →maх Пример решения задачи методом линейного программирования Формирование системы ограничений. В общем виде ограничения на расход сырья можно записать в следующем виде. Используемый объем сырья для производства обоих видов краски ≤ (Максимально возможный ежедневный расход сырья) Что приводит к получению следующей системы неравенств: ቐ 3,5𝑋 1 + 1𝑋 2 ≤ 350, 1𝑋 1 + 2𝑋 2 ≤ 240, 1𝑋 1 + 1𝑋 2 ≤ 150. Кроме того, переменные должны быть неотрицательными: 𝑋 1 ≥ 0, 𝑋 2 ≥ 0. Решение задачи линейного программирования состоит в переборе всех допустимых решений и нахождении оптимального. Поскольку область допустимых решений может быть обширной, целесообразно использовать специальные методы решения задач. Среди методов можно выделить графический и симплекс-метод решения задач линейного программирования. Пример решения задачи методом линейного программирования. Графический способ. Графический способ решения задачи состоит из двух основных этапов: 1. Построение пространства допустимых решений. Каждой переменной модели соответствует ось графика, на горизонтальной - 𝑋 1 , вертикальной - 𝑋 2 . Учитывая требование не отрицательности переменных, на графике будет отображен только один квадрант системы координат 0 50 100 150 200 250 300 350 400 0 50 100 150 200 250 300 X2 X1 1 2 3 1)3,5𝑋 1 + 1𝑋 2 ≤ 350, 2)1𝑋 1 + 2𝑋 2 ≤ 240, 3)1𝑋 1 + 1𝑋 2 ≤ 150. Построение области допустимых решений для задачи Пример решения задачи методом линейного программирования. Графический способ. Для построения области допустимых решений необходимо неравенства заменить на равенства, провести прямые. Затем необходимо определить необходимую полуплоскость: каждое неравенство делит плоскость на две полуплоскости, которые располагаются по обе стороны от прямой. Точки одной полуплоскости удовлетворяют неравенству, образуя допустимое пространство. Как правило, используется какая-то «тестовая» точка, например, точка (0,0). Проверяется удовлетворяет ли данная точка неравенству, если да – полуплоскость с тестовой точкой входит в искомую полуплоскость, если нет – допустимому пространству соответствует вторая полуплоскость. Например, для графического отображения полуплоскости первого неравенства 3,5𝑋 1 + 1𝑋 2 ≤ 350, следует заменить его равенством 3,5𝑋 1 + 1𝑋 2 = 350, которому на графике соответствует прямая. На рисунке (предыдущий слайд) допустимые полуплоскости показаны стрелками. Подобным образом строится вся система ограничений. Область допустимых решений, удовлетворяющая всей системе неравенств, выделена штриховкой. Пример решения задачи методом линейного программирования. Графический способ. Для построения области допустимых решений необходимо неравенства заменить на равенства, провести прямые. Затем необходимо определить необходимую полуплоскость: каждое неравенство делит плоскость на две полуплоскости, которые располагаются по обе стороны от прямой. Точки одной полуплоскости удовлетворяют неравенству, образуя допустимое пространство. Как правило, используется какая-то «тестовая» точка, например, точка (0,0). Проверяется удовлетворяет ли данная точка неравенству, если да – полуплоскость с тестовой точкой входит в искомую полуплоскость, если нет – допустимому пространству соответствует вторая полуплоскость. Например, для графического отображения полуплоскости первого неравенства 3,5𝑋 1 + 1𝑋 2 ≤ 350, следует заменить его равенством 3,5𝑋 1 + 1𝑋 2 = 350, которому на графике соответствует прямая. На рисунке (предыдущий слайд) допустимые полуплоскости показаны стрелками. Подобным образом строится вся система ограничений. Область допустимых решений, удовлетворяющая всей системе неравенств, выделена штриховкой. Пример решения задачи методом линейного программирования. Графический способ. 2. Поиск оптимального решения (1) Для определения оптимального решения среди множества допустимых необходимо построить направляющий вектор (градиент), который показывает направление наибольшего возрастания целевой функции F(x). Как правило вектор строится из начала координат. Вектор строится на основе значения переменных при целевой функции 𝑛=(20, 10) Линия уровня F(х)=С строится перпендикулярно градиенту. На рисунке линии уровня изображены линиями со штриховкой. 0 20 40 60 80 100 120 140 0 20 40 60 80 100 120 140 160 180 200 X2 X1 1 2 3 A Пример решения задачи методом линейного программирования. Графический способ. 2. Поиск оптимального решения (2) Далее линия уровня перемещается параллельно самой себе по направлению градиента до тех пор, пока у неё не окажется одна общая точка с областью допустимых решений. Данная точка и будет решением модели. В данном случае это точка A (80, 70). Соответственно следует производить 80 т. краски для внутренних работ и 70 т. краски для наружных. При этом ежедневный доход составит, очевидно, 2300 ден. ед. Подобное графическое решение очень трудно осуществить для модели с тремя переменными, поскольку область допустимых решений будет представлять собой многогранник в трехмерном пространстве. 0 20 40 60 80 100 120 140 0 50 100 150 200 X2 X1 1 2 3 A Решения задач методом линейного программирования. Графический способ. Возможные варианты решений при использовании графического способа а) решения не существует, то есть область допустимых решений не возможно выделить, ограничения противоречивы, полученная модель - несовместна. Необходимо перейти на второй этап, пересмотреть ограничения. Решения задач методом линейного программирования. Графический способ. Возможные варианты решений при использовании графического способа б) решение не может быть найдено, поскольку область допустимых решений не замкнута и, соответственно, при сдвиге линии уровня оптимальное решение не может быть найдено. При решении задачи при помощи информационных систем после некоторого числа итераций, если решение не получено, система выдает сообщение о том, что решение не найдено. Скорее всего это происходит из-за того, что при выборе системы ограничений было упущено одно или несколько существенных ограничений. Необходимо уточнить ограничения. Решения задач методом линейного программирования. Графический способ. Возможные варианты решений при использовании графического способа в) решение единственное или из ограниченного множества. В случае совпадения линии уровня с одной из прямых ограничивающих область допустимых решений. В этом случае решение может быть отрезком или лучом (отрезок АВ). Если решение существует в дальнейшем оно анализируется в терминах содержательной постановки задачи. Решения задач методом линейного программирования при помощи средств MS Excel симплекс-методом Исходные данные из формализованного описания задачи представлены на рисунке. В ячейки, содержащие левые части системы неравенств ቐ 3,5𝑋 1 + 1𝑋 2 ≤ 350, 1𝑋 1 + 2𝑋 2 ≤ 240, 1𝑋 1 + 1𝑋 2 ≤ 150. добавлены формулы. Добавлена формула целевой функции F(X) = 20 X 1 +10 X 2 →maх Решения задач методом линейного программирования при помощи средств MS Excel симплекс-методом Решение осуществляется при помощи надстройки «Поиск решения», которая находится в пункте меню «Данные» (рис). В основном окне надстройки необходимо ввести ссылки на ячейки, содержащие целевую функцию, переменные решения, а также ввести ограничения. При нажатии на кнопку «Найти решение» запускается алгоритм вычислений, итогом работы которого является окно «Результаты поиска решения». В окне может содержаться одно из следующих сообщений: «Решение найдено. Все ограничения и условия оптимальности выполнены» либо «Значения целевой ячейки не сходятся» или «Поиск не может найти решения» или «Условия линейной модели не выполняются». Решения задач методом линейного программирования при помощи средств MS Excel симплекс-методом В случае, если решение существует, результат принятия решения представлен на рисунке. Решения задач методом линейного программирования при помощи средств MS Excel симплекс-методом. Двойственная задача. Для принятия управленческих решений, провести анализ полученных результатов не менее важно, чем получить результат. Анализ в основном касается изменения параметров модели с целью поиска путей совершенствования результата. В основном анализ полученного решения основывается на чувствительности полученного результата к неточностям в ограничениях и целевой функции. Как видно из рисунка на месте пустых ячеек с переменной и целевой функцией появляются значения. Также появились значения расхода сырья на производство ресурсов. Решения задач методом линейного программирования при помощи средств MS Excel симплекс-методом. Двойственная задача. Анализ решения позволит ответить на ряд вопросов, имеющих непосредственное отношение к содержательной постановке задачи: как изменение коэффициентов при переменных целевой функции повлияет на величину оптимального решения, другими словами насколько решение устойчиво к неточностям; какое ограничение (наличие ресурса) оказывает наиболее сильное влияние на изменение целевой функции; какой ресурс является наиболее дефицитным, а какой избыточным; как следует изменить коэффициент при переменной целевой функции, чтобы включить некую переменную в оптимальный план, если сейчас она в такой план не входит. Решения задач методом линейного программирования при помощи средств MS Excel симплекс-методом. Двойственная задача. Методически большая часть ответов на подобные вопросы может быть получена через решение так называемой двойственной задачи, которая является «зеркальным отражением» исходной задачи, которая часто называется прямой и может быть из неё получена. При решении задачи симплекс-методом решаются обе задачи – прямая и двойственная. Переменные двойственной задачи называют «теневыми» ценами, симплексными мультипликаторами или двойственными оценками. Теневая цена ресурса показывает на сколько измениться целевая функция при добавлении единицы ресурса. Другими словами, она показывает внутреннюю ценность ресурсов каждого вида. Решения задач методом линейного программирования при помощи средств MS Excel симплекс-методом. Двойственная задача. Содержательная формулировка двойственной задачи, полученная из прямой для нашего примера будет выглядеть следующим образом: Вместо того, чтобы производить продукцию, руководство решает распродать сырье, используемое при производстве краски. Какие цены на сырье следует назначить, чтобы продать его было не менее выгодно, чем производить краску. Какова минимальная сумма, полученная за сырье в этом случае. Решения задач методом линейного программирования при помощи средств MS Excel симплекс-методом. Двойственная задача. На основании содержательной формулировки можно выделить основные компоненты математической модели: 1. Переменные решения. Поскольку в задаче используются три типа сырья, то очевидно, что переменных будет тоже три – Y 1 , Y 2 , Y 3 . Это теневые цены ресурсов каждого вида. 2. Целевая функция. Минимальная сумма, полученная за сырье, которая определяет нижнюю границу цен на ресурсы. G(Y) = 350 Y 1 +240 Y 2 +150 Y 3 →min 3. Ограничения. Набор сырья для производства тонны краски одного вида по условию должен принести не меньший доход, чем производство краски. ቊ 3,5𝑌 1 + 1𝑌 2 + 1𝑌 3 ≥ 20, 1𝑌 1 + 2𝑌 2 + 1𝑌 3 ≥ 10. При этом все переменные, как и в исходной задаче неотрицательны: 𝑌 1 ≥ 0, 𝑌 2 ≥ 0, 𝑌 3 ≥ 0. Решения задач методом линейного программирования при помощи средств MS Excel симплекс-методом Перед тем как задача будет преобразована в двойственную она должна быть приведена к стандартному (каноническому) виду. Это означает следующее: все переменные модели неотрицательны; оптимизация (максимизация или минимизация целевой функции); ограничения модели записаны в виде равенств с правой неотрицательной частью. Можно выделить основные правила преобразования прямой задачи в двойственную: Экстремум целевой функции и знак неравенства ограничений меняются на противоположный; Количество переменных в двойственной задаче равно количеству ограничений прямой и наоборот; В качестве коэффициентов при переменных целевой функции двойственной задачи используются правые части ограничений прямой и и наоборот; Коэффициенты при переменных в ограничениях двойственной задачи получаются транспонированием матрицы коэффициентов прямой задачи. Решения задач методом линейного программирования при помощи средств MS Excel симплекс-методом. Двойственная задача. Двойственная задача может быть решена подобно прямой задаче. При использовании информационных систем сразу решаются обе задачи. В частности, при использовании надстройки «Поиск решения» в MS Eхcel решение двойственной задачи содержится в отчёте «Устойчивость». Открытие отчета возможно при появлении окна «Результаты поиска решения» (рис). Решения задач методом линейного программирования при помощи средств MS Excel симплекс-методом. Двойственная задача. Общий вид отчета для задачи примера представлен на рисунке. Отчет разделен на две части. Верхняя часть отчета позволяет провести анализ чувствительности целевой функции. Столбец «Окончательное Значение» содержит результаты расчета математической модели. Столбец «Приведенн. Стоимость» содержит 0 для переменных, значения которых являются не нулевыми в оптимальном решении, как в данном случае. Если данная переменная является нулевой в оптимальном решении (не входит в оптимальный план), то в этом столбце содержится отрицательная величина, на которую нужно увеличить коэффициент при целевой функции, чтобы переменная приобрела ненулевое значение в оптимальном плане. Решения задач методом линейного программирования при помощи средств MS Excel симплекс-методом. Двойственная задача. Например, по результатам решения задачи получен результат, из которого следует, что производить необходимо только краску для внутренних работ. А в столбце «Приведенн. Стоимость» в строке «Х2 Краска для наружных работ» содержится «-5». Это значит, что коэффициент целевой функции, в данном случае доход от производства краски для наружных работ должен быть увеличен как минимум на 5 ден. ед., что должно привести к пересмотру ценовой политики. Столбец «Целевая функция Коэффициент» как следует из названия содержит коэффициенты целевой функции исходной математической модели. Столбцы «Допустимое Увеличение» и «Допустимое Уменьшение» содержат возможные изменения коэффициента целевой функции, при котором полученное оптимальное решение сохраняется. В данном случае при изменении дохода от продажи 1 тонны краски для внутренних работ в диапазоне (20-10; 20+15) полученный оптимальный план ежедневного производства сохраняется. То же верно для диапазона изменений коэффициента целевой функции X 2 при изменении в диапазоне (5,715; 20). Решения задач методом линейного программирования при помощи средств MS Excel симплекс-методом. Двойственная задача. Нижняя часть отчета содержит анализ ограничений. Аналогично верхней части таблицы столбцы «Окончательное Значение» и «Ограничение Правая сторона» содержат результат расчета модели и исходные данные соответственно, столбцы с увеличением и уменьшением показывают диапазон изменения правых сторон ограничений при котором данное решение сохраняется. Как видно из таблицы «Сырье 2» находится в избытке, поэтому при добавлении сколь угодно много данного ресурса решение не изменится. Результаты расчета теневых цен двойственной задачи показывает столбец «Тень Цена». Как видно из данного примера наиболее ценным является единица «Сырья 3», при увеличении запаса этого вида сырья на одну единицу, целевая функция возрастет на 6 ден. ед., при добавлении единицы первого сырья только на 4 ден. единицы, а поскольку второй вид сырья в избытке, то теневая цена этого ресурса равна 0. Транспортная задача Транспортная задача - частный вид задачи линейного программирования. Несмотря на то, что транспортные задачи могут быть решены как задачи линейного программирования, рассмотренные ранее, их особенности позволяют использовать способы решения, более эффективные для данного типа задач. В общем виде цель транспортной задачи - минимизация суммарных издержек (или максимизация дохода) при перевозках однотипных грузов от нескольких пунктов назначения (поставщиков) в различные пункты назначения (потребителям). Для принятия управленческих решений на основе транспортной модели следует учитывать два момента: каждая модель составляется только на груз одного типа; в расчет принимаются только транспортные расходы пропорциональные единицам перевезенного груза, то есть переменные. Транспортная задача Общий вид транспортной задачи представлен в таблице. Модель содержит n пунктов отправления и m пунктов назначения. c ij представляет собой тариф по которому одна единица груза может быть перевезена из пункта отправления i в пункт назначения j. Переменные X ij – показывают количество перевезенного груза из пункта отправления i в пункт назначения j. Пункты отправления Пункты назначения Предложения D 1 D 2 … D m S 1 c 11 X 11 c 12 X 12 … c 1m X 1m L 1 S 2 c 2 X 21 c 22 X 22 … c 2m X 2m L 2 … … … … … S n c n1 X n1 c n2 X n2 … c nm X nm L n Потребности O 1 O 2 … O m Транспортная задача Очевидно, что целевая функция будет представлять собой сумму произведений объемов перевозки на тарифы и будет стремиться к минимуму в случае минимизации издержек на перевозку. Ограничениями модели являются объемы потребностей и предложений, представленные в последнем столбце и строке таблицы. Пункты отправления Пункты назначения Предложения D 1 D 2 … D m S 1 c 11 X 11 c 12 X 12 … c 1m X 1m L 1 S 2 c 2 X 21 c 22 X 22 … c 2m X 2m L 2 … … … … … S n c n1 X n1 c n2 X n2 … c nm X nm L n Потребности O 1 O 2 … O m Транспортная задача Существует два основных осложнения транспортных задач (1): Несбалансированность. Транспортная задача называется сбалансированной или закрытой, если совокупный объем потребностей равен совокупному объему предложения. 𝑖=1 𝑛 𝐿 𝑖 = 𝑗=1 𝑚 𝑂 𝑗 , В случае отсутствия равенства задача считается несбалансированной или открытой. В этом случае в модель вводится фиктивный пункт отправления или назначения. Объем предложения или потребности фиктивного пункта равен модулю разницы между совокупным объемом потребности и предложения. Тарифы на перевозку фиктивного пункта равны нулю, в случае минимизации целевой функции. При расчете оптимального плана, потребность/предложение фиктивного пункта будет закрыто в первую очередь, что выведет излишки из дальнейшего расчета модели. Транспортная задача Существует два основных осложнения транспортных задач (2): «Запрещенный маршрут» В обобщенном представлении транспортной задачи груз может быть перевезен из каждого пункта отправления в каждый пункт назначения, что, очевидно, противоречит реальной ситуации, когда какие-то маршруты не возможны в силу различных причин. Такого рода ситуация разрешается введением максимально большого тарифа на перевозку (M). В практике использования алгоритмов информационных систем рекомендуется использовать число, на несколько порядков превосходящее основную массу тарифов в модели. При поиске оптимального решения, очевидно, что ячейка с избыточно большим тарифом останется пустой, что обеспечит «запрещенность» данного маршрута. Транспортная задача Решение транспортной задачи осуществляется в два этапа: 1. Заполнение опорного плана транспортной задачи. Опорный план является аналогом допустимого решения в классической задаче линейного программирования и определяет решение, которое соответствует всем ограничениям модели, но не удовлетворяет условию оптимальности. Для получения опорного плана могут быть использованы различные методы: северо-западного угла, минимального элемента, метод аппроксимации Фогеля. 2. Нахождение оптимального решения: при помощи специальных методов (метод потенциалов, венгерский метод) состоит в итерационном переходе от опорного плана к оптимальному. Решение транспортной задачи при помощи средств MS Excel Пример У фирмы имеется четыре филиала и получает продукцию от трех поставщиков. Известны: спрос на продукцию в каждом филиале, и наличие продукции у каждого из поставщиков. Также известны расходы на перевозку от каждого из поставщиков в каждый из филиалов (таблица). Требуется определить сколько продукции от каждого из поставщиков нужно перевезти в каждый из филиалов для минимизации транспортных расходов. Поставщики Потребители Объем возможных поставок А B C D Р 10 2 20 11 15 Q 12 7 9 20 25 R 4 14 16 18 10 Спрос у потребителя 5 15 15 15 Задача является сбалансированной совокупный возможных поставок равен совокупному спросу и составляет 50 ед. Запрещенных маршрутов также нет, поэтому дополнительные преобразования модели не нужны. Решение транспортной задачи при помощи средств MS Excel Организация исходных данных представлена на рисунке. Данные организованы в виде двух таблиц, в верхней представлены исходные данные с тарифами. В нижней – переменные и целевая функция. Решение транспортной задачи при помощи средств MS Excel В окне надстройки «Поиск решения» добавлены ссылки на переменные, ограничения и целевую функцию (рис.). Решение транспортной задачи при помощи средств MS Excel Результат расчета представлен на рисунке. В результате решения в нижней таблице появились объемы перевозок и целевая функция, значение которой составит 435 ден. ед. Задачи о назначениях Общий вид задачи о назначениях чрезвычайно близок транспортной задаче, где вместо пунктов отправления - работники, а вместо пунктов назначения- работы. Объемы запасов и потребностей (последняя строка и столбец) равны единицам, поскольку нужно одного работника распределить на одну работу. |