Тема: Модели и методы принятия решений
3.1. Простые методы принятия решений
3.2. ЗАДАЧИ ОПТИМИЗАЦИИ ПРИ ПРИНЯТИИ РЕШЕНИЙ
Орлов Теория принятия решений Учебное пособие. Среди оптимизационных задач в теории принятия решений наиболее известны задачи линейного программирования, в которых максимизируемая функция F X является линейной, а ограничения А задаются линейными неравенствами. Цех может производить стулья и столы. На производство стула идет 5 единиц материала, на производство стола - 20 единиц футов красного дерева. Стул требует 10 человеко-часов, стол - Имеется единиц материала и человеко-часов. Прибыль при производстве стула - 45 долларов США, при производстве стола - 80 долларов США. Сколько надо сделать стульев и столов, чтобы получить максимальную прибыль? Х 1 - число изготовленных стульев, Х 2 - число сделанных столов. Задача оптимизации имеет вид:. В первой строке выписана целевая функция - прибыль при выпуске Х 1 стульев и Х 2 столов. Ее требуется максимизировать, выбирая оптимальные значения переменных Х 1 и Х 2. При этом должны быть выполнены ограничения по материалу вторая строчка - истрачено не более футов красного дерева. А также и ограничения по труду третья строчка - затрачено не более часов. Кроме того, нельзя забывать, что число столов и число стульев неотрицательны. Если же хоть один стул сделан, то Х 1 положительно. Но невозможно представить себе отрицательный выпуск - Х 1 не может быть отрицательным с экономической точки зрения, хотя с математической точки зрения такого ограничения усмотреть нельзя. В четвертой и пятой строчках задачи и констатируется, что переменные неотрицательны. Условия производственной задачи можно изобразить на координатной плоскости. Будем по горизонтальной оси абсцисс откладывать значения Х 1 , а по вертикальной оси ординат - значения Х 2. Тогда ограничения по материалу и последние две строчки оптимизационной задачи выделяют возможные значения Х 1 , Х 2 объемов выпуска в виде треугольника рис. Таким образом, ограничения по материалу изображаются в виде выпуклого многоугольника, конкретно, треугольника. Этот треугольник получается путем отсечения от первого квадранта примыкающей к началу координат зоны. Отсечение проводится прямой, соответствующей второй строке исходной задачи, с заменой неравенства на равенство. Прямая пересекает ось Х 1 , соответствующую стульям, в точке 80,0. Это означает, что если весь материал пустить на изготовление стульев, то будет изготовлено 80 стульев. Та же прямая пересекает ось Х 2 , соответствующую столам, в точке 0, Это означает, что если весь материал пустить на. Для всех точек внутри треугольника выполнено неравенство, а не равенство - материал останется. Таким образом, ограничения по труду, как и ограничения по материалу, изображаются в виде треугольника. Этот треугольник также получается путем отсечения от первого квадранта примыкающей к началу координат зоны. Отсечение проводится прямой, соответствующей третьей строке исходной задачи, с заменой неравенства на равенство. Прямая пересекает ось Х 1 , соответствующую стульям, в точке 45,0. Это означает, что если все трудовые ресурсы пустить на изготовление стульев, то будет сделано 45 стульев. Это означает, что если всех рабочих поставить на изготовление столов, то будет сделано 30 столов. Для всех точек внутри треугольника выполнено неравенство, а не равенство - часть рабочих будет простаивать. Но в каком соотношении? Чтобы ответить на этот вопрос, надо "совместить" рис. Таким образом, множество возможных значений объемов выпуска стульев и столов Х 1 , Х 2 , или, в других терминах, множество А , задающее ограничения на параметр управления в общей оптимизационной задаче, представляет собой пересечение двух треугольников, то есть выпуклый четырехугольник, показанный на рис. Три его вершины очевидны - это 0,0 , 45,0 и 0, Четвертая - это пересечение двух прямых - границ треугольников на рис. Подставляем во второе уравнение:. Надо найти максимум линейной функции на выпуклом многоугольнике. В общем случае линейного программирования - максимум линейной функции на выпуклом многограннике, лежащем в конечномерном линейном пространстве. В общем случае - в одной вершине, и это - единственная точка максимума. В частном - в двух, и тогда отрезок, их соединяющий, тоже состоит из точек максимума. При увеличении аргументов эта функция увеличивается. В вершине 24,14 она принимает значение Отсюда, как и из непосредственной проверки двух оставшихся вершин, вытекает, что максимум целевой функции, равный , достигается в вершине 24, Таким образом, оптимальный выпуск таков: При этом используется весь материал и все трудовые ресурсы, а прибыль равна долларам США. Каждой задаче линейного программирования соответствует так называемая двойственная задача. Задача, двойственная к двойственной - эта сама исходная задача. Сравним исходную задачу слева и двойственную к ней справа:. Почему двойственная задача столь важна? Можно доказать, что оптимальные значения целевых функций в исходной и двойственной задачах совпадают то есть максимум в исходной задаче совпадает с минимумом в двойственной. При этом оптимальные значения W 1 и W 2 показывают стоимость материала и труда соответственно, если их оценивать по вкладу в целевую функцию. Чтобы не путать с рыночными ценами этих факторов производства, W 1 и W 2 называют "объективно обусловленными оценками" сырья и рабочей силы. Линейное программирование как научно-практическая дисциплина. Из всех задач оптимизации задачи линейного программирования выделяются тем, что в них ограничения - системы линейных неравенств или равенств. Ограничения задают выпуклые линейные многогранники в конечном линейном пространстве. Целевые функции также линейны. Впервые такие задачи решались советским математиком Л. Канторовичем в х годах как задачи производственного менеджмента с целью оптимизации организации производства и производственных процессов, например, процессов загрузки станков и раскройки листов материалов. После второй мировой войны аналогичными задачами занялись в США. Купманс , родился в Нидерландах, работал в основном в США и академик АН СССР Л. Канторович были награждены Нобелевскими премиями по экономике. Задача о диете упрощенный вариант. Предположим для определенности, что необходимо составить самый дешевый рацион питания цыплят, содержащий необходимое количество определенных питательных веществ для простоты, тиамина Т и ниацина Н. Пищевая ценность рациона в калориях должна быть не менее заданной. Пусть для простоты смесь для цыплят изготавливается из двух продуктов - К и С. Известно содержание тиамина и ниацина в этих продуктах, а. Сколько К и С надо взять для одной порции куриного корма, чтобы цыплята получили необходимую им дозу веществ Н и Т и калорий или больше , а стоимость порции была минимальна? Исходные данные для расчетов приведены в табл. Она проходит, как и показано на рисунке, через точки 5,0 на оси абсцисс и 0,20 на оси ординат. Обратите внимание, что допустимые значения параметров К, С лежат выше прямой 1 или на ней, в отличие от ранее рассмотренных случаев в предыдущей производственной задаче линейного программирования. Обратим внимание, что в области неотрицательных С она расположена всюду ниже прямой 1. Точка пересечения двух прямых находится при решении системы уравнений. Это и означает, что при всех положительных С прямая 2 лежит ниже прямой 1. Значит, если выполнено ограничения по Н, то обязательно выполнено и ограничение по калориям. Мы столкнулись с новым явлением - некоторые ограничения с математической точки зрения могут оказаться лишними. С экономической точки зрения они необходимы, отражают существенные черты постановки задачи, но в данном случае внутренняя структура задачи оказалась такова, что ограничение по калориям не участвует в формировании допустимой области параметров и нахождении решения. Она проходит, как и показано на рисунке, через точки 10,0 на оси абсцисс и 0,4 на оси ординат. Обратите внимание, что допустимые значения параметров К , С лежат выше прямой 4 или на ней, как и для прямой 1. Следовательно, область допустимых значений параметров К , С является неограниченной сверху. Из всей плоскости она выделяется осями координат лежит в первом квадранте и прямыми 1 и 4 лежит выше этих прямых, а также включает граничные отрезки. Область допустимых значений параметров, то есть точек К , С , можно назвать "неограниченным многоугольником". Третья вершина - это точка А пересечения прямых 1 и 4 , координаты которой находятся при решении системы уравнений. Прямая 3 на рис. Она проходит между прямыми 1 и 4 , задающими ограничения, и минимум достигается в точке А , через которую и проходит прямая 3. Задача об оптимизации смеси полностью решена. Двойственная задача, построенная по описанным выше правилам, имеет приведенный ниже вид мы повторяем здесь и исходную задачу об оптимизации смеси, чтобы наглядно продемонстрировать технологию построения двойственной задачи:. W 1 - "стоимость" единицы вещества Т, а W 2 - "стоимость" единицы вещества Н, измеренные "по их вкладу" в целевую функцию. Канторовичу ресурсов веществ Т и Н, калорий. Планирование номенклатуры и объемов выпуска. Вернемся к организации производства. Предприятие может выпускать автоматические кухни вид кастрюль , кофеварки и самовары [2]. При этом штамповка и отделка проводятся на одном и том же оборудовании. Оно позволяет штамповать за заданное время или кухонь, либо кофеварок, либо и то, и другое, не в меньшем количестве. А вот сборка проводится на отдельных участках. Заметим, что неравенство 3 вытекает из неравенства 1 , а неравенство 4 - из 2. Поэтому неравенства 3 и 4 можно из формулировки задачи линейного программирования ислючить. Отметим сразу любопытный факт. Методы решения задач линейного программирования. Методы решения задач линейного программирования относятся к вычислительной математике, а не к экономике. Однако экономисту полезно знать о свойствах интеллектуального инструмента, которым он пользуется. С ростом мощности компьютеров необходимость применения изощренных математических методов снижается, поскольку во многих случаях время счета перестает быть лимитирующим фактором, оно весьма мало доли секунд. Поэтому разберем лишь три метода. Возьмем некоторый многомерный параллелепипед, в котором лежит многогранник, задаваемый ограничениями. Аналогичным образом от линейных ограничений общего вида можно перейти к ограничениям на отдельные переменные. Остается взять максимальные границы по каждой переменной. Если многогранник, задаваемый ограничениями, неограничен, как было в задаче о диете, можно похожим, но несколько более сложным образом выделить его "обращенную" к началу координат часть, содержащую решение, и заключить ее в многомерный параллелепипед. Из всех точек, удовлетворяющих ограничениям, возьмем ту, в которой целевая функция максимальна. Начнем с точки, удовлетворяющей ограничениям ее можно найти простым перебором. Будем последовательно или случайно — с помощью т. Если выйдем на плоскость ограничения, будем двигаться по ней находя одну из координат по уравнению ограничения. Затем движение по ребру когда два ограничения-неравенства переходят в равенства … Остановка - в вершине линейного многогранника. Этот один из первых специализированных методов оптимизации, нацеленный на решение задач линейного программирования, в то время как методы простого и направленного перебора могут быть применены для решения практически любой задачи оптимизации. Симплекс-метод был предложен американцем Г. Данцигом в г. Основная его идея состоит в продвижении по выпуклому многограннику ограничений от вершины к вершине, при котором на каждом шаге значение целевой функции улучшается до тех пор, пока не будет достигнут оптимум. Разберем пример на основе данных табл. Рассмотрим задачу линейного программирования, сформулированную выше при рассмотрении оптимизации номенклатуры и объемов выпуска:. Неотрицательность переменных не будем специально указывать, поскольку в задачах линейного программирования это предположение всегда принимается. В соответствии с симплекс-методом введем т. У этой системы имеется очевидное решение, соответствующее одной из вершин многогранника допустимых значений переменных:. В терминах исходной задачи это означает, что ничего не надо выпускать. Такое решение приемлемо только на период летних отпусков. В соответствии с симплекс-методом выбираем переменную, которая входит в целевую функцию F с самым большим положительным коэффициентом. Сравниваем частные от деления свободных членов в первых трех уравнениях на коэффициенты при только что выбранной переменной Х Выбираем строку из системы уравнений, которой соответствует минимальное из всех положительных отношений. Ту же преобразованную первую строку умножим на и сложим со строкой, в правой части которой стоит F , получим:. Очевидно, у новой системы имеется улучшенное по сравнению с исходным решение, соответствующее другой вершине выпуклого многогранника в шестимерном пространстве:. В терминах исходной задачи это решение означает, что надо выпускать только кухни. Такое решение приемлемо, если допустимо выпускать только один вид продукции. Повторим описанную выше операцию. При этом прибыль будет максимальной и равной Все производственное оборудование будет полностью загружено, за исключением линии по сборке самоваров. Различные технико-экономические и экономические задачи производственного менеджмента, от оптимальной загрузки станка и раскройки стального листа или полотна ткани до анализа межотраслевого баланса и оценки темпов роста экономики страны в целом, приводят к необходимости решения тех или иных задач линейного программирования. В качестве очередного примера рассмотрим т. Имеются склады, запасы на которых известны. Известны потребители и объемы их потребностей. Необходимо доставить товар со складов потребителям. Можно по-разному организовать "прикрепление" потребителей к складам, то есть установить, с какого склада какому потребителю и сколько вести. Кроме того, известна стоимость доставки единицы товара с определенного склада определенному потребителю. Требуется минимизировать издержки по перевозке. Например, может идти речь о перевозке песка - сырья для производства кирпичей. В Москву песок обычно доставляется самым дешевым транспортом - водным. Поэтому в качестве складов можно рассматривать порты, а в качестве запасов - их суточную пропускную способность. Потребителями являются кирпичные заводы, а их потребности определяются суточным производством в соответствии с имеющимися заказами. Для доставки необходимо загрузить автотранспорт, проехать по определенному маршруту и разгрузить его. Стоимость этих операций рассчитывается по известным правилам, на которых не имеет смысла останавливаться. Поэтому затраты на доставку товара с определенного склада тому или иному потребителю можно считать известными. Например, самая дешевая доставка - со склада 2 потребителям 1 и 3, а также со склада 3 потребителю 2. Обратите внимание, что в табл. Для примера с доставкой песка кирпичным заводам это вполне естественное ограничение - при невыполнении такого ограничения либо порты будут засыпаны горами песка, либо кирпичные заводы не выполнят заказы. Таким образом, всего в задаче имеется 12 переменных. Они удовлетворяют двум группам ограничений. Во-первых, заданы запасы на складах:. Итак, всего 7 ограничений типа равенств. Кроме того, все переменные неотрицательны - еще 12 ограничений. Кроме обсуждаемой, рассматриваются также различные иные варианты транспортной задачи. Например, если доставка производится вагонами, то объемы поставок должны быть кратны вместимости вагона. Количество переменных и ограничений в транспортной задаче таково, что для ее решения не обойтись без компьютера и соответствующего программного продукта. Задачи оптимизации, в которых переменные принимают целочисленные значения, относятся к целочисленному программированию. Рассмотрим несколько таких задач. Задача о выборе оборудования. На приобретение оборудования для нового участка цеха выделено долларов США. При этом можно занять площадь не более 38 м 2. Имеется возможность приобрести станки типа А и станки типа Б. При этом станки типа А стоят долларов США, занимают площадь 8 м 2 включая необходимые технологические проходы и имеют производительность 7 тыс. Станки типа Б стоят долларов США, занимают площадь 4 м 2 и имеют производительность 3 тыс. Необходимо рассчитать оптимальный вариант приобретения оборудования, обеспечивающий при заданных ограничениях максимум общей производительности участка. Пусть Х - количество станков типа А, а У - количество станков типа Б, входящих в комплект оборудования. Требуется выбрать комплект оборудования так, чтобы максимизировать производительность С участка в тыс. Сформулированная математическая задача отличается от задачи линейного программирования только последним условием целочисленности. Однако наличие этого условия позволяет в данном конкретном случае легко решить задачу перебором. Значит, Х может принимать лишь одно из 5 значений: Все возможные случаи рассмотрены. Следовательно, надо покупать 2 станка типа А и 5 станков типа Б. Общий вес ранца заранее ограничен. Какие предметы положить в ранец, чтобы общая полезность отобранных предметов была максимальна? Вес каждого предмета известен. Есть много эквивалентных формулировок. Например, можно вместо ранца рассматривать космический аппарат — спутник Земли, а в качестве предметов - научные приборы. Тогда задача интерпретируется как отбор приборов для запуска на орбиту. Правда, при этом предполагается решенной предварительная задача - оценка сравнительной ценности исследований, для которых нужны те или иные приборы. Перейдем к математической постановке. Предполагается, что имеется n предметов, и для каждого из них необходимо решить, класть его в ранец или не класть. Для каждого предмета известны две константы: Максимально возможную вместимость ранца обозначим В. Оптимизационная задача имеет вид. Метод приближения непрерывными задачами. В соответствии с ним сначала решается задача линейного программирования без учета целочисленности, а затем в окрестности оптимального решения ищутся целочисленные точки. Из них наиболее известен метод ветвей и границ. Каждому подмножеству Х множества возможных решений Х 0 ставится в соответствие число - "граница" А Х. Алгоритм прекращает работу, когда диаметр вновь выделенной ветви оказывается меньше заранее заданного малого числа. Для каждой конкретной задачи целочисленного программирования другими словами, дискретной оптимизации метод ветвей и границ реализуется по-своему. Есть много модификаций этого метода. Один из разделов дискретной математики, часто используемый при принятии решений - теория графов см. Граф - это совокупность точек, называемых вершинами графа, некоторые из которых соединены дугами дуги назыыают также ребрами. Примеры графов приведены на рис. На только что введенное понятие графа "навешиваются" новые свойства. Исходному объекту приписывают новые качества. Например, вводится и используется понятие ориентированного графа. В таком графе дуги имеют стрелки, направленные от одной вершины к другой. Примеры ориентированных графов даны на рис. Ориентированный граф был бы полезен, например, для иллюстрации организации перевозок в транспортной задаче. В экономике дугам ориентированного или обычного графа часто приписывают числа, например, стоимость проезда или перевозки груза из пункта А начальная вершина дуги в пункт Б конечная вершина дуги. Требуется посетить все вершины графа и вернуться в исходную вершину, минимизировав затраты на проезд или минимизировав время. Исходные данные здесь - это граф, дугам которого приписаны положительные числа - затраты на проезд или время, необходимое для продвижения из одной вершины в другую. В общем случае граф является ориентированным, и каждые две вершины соединяют две дуги - туда и обратно. Действительно, если пункт А расположен на горе, а пункт Б - в низине, то время на проезд из А в Б, очевидно, меньше времени на обратный проезд из Б в А. Задача о кратчайшем пути. Как кратчайшим путем попасть из одной вершины графа в другую? В терминах производственного менеджмента: Для решения этой задачи каждой дуге ориентированного графа должно быть сопоставлено число - время движения по этой дуге от начальной вершины до конечной. Ситуацию можно описать не только ориентированным графом с весами, приписанными дугам, но и таблицей табл. Более сложные маршруты составляются из элементарных отрезков, перечисленных в табл. С Т - длина кратчайшего пути из вершины 1 в вершину Т. Поскольку любой путь, который надо рассмотреть, состоит из дуг, а дуг конечное число, и каждая входит не более одного раза, то претендентов на кратчайший путь конечное число, и минимум из конечного числа элементов всегда достигается. Рассматриваемая задача состоит в вычислении С 4 и указании пути, на котором этот минимум достигается. Для исходных данных, представленных на рис. В вершину 4 можно попасть либо из вершины 2, пройдя путь, равный 4, либо из вершины 5, пройдя путь, равный 5. Таким образом, проведена реструктуризация упрощение задачи - нахождение С 4 сведено к нахождению С 2 и С 5. В вершину 5 можно попасть либо из вершины 3, пройдя путь, равный 2, либо из вершины 6, пройдя путь, равный 3. В вершину 2 можно попасть либо из вершины 1, пройдя путь, равный 7, либо из вершины 3, пройдя путь, равный 5, либо из вершины 5, пройдя путь, равный 2. Таким образом, длина кратчайшего пути равна 8. Из последнего соотношения ясно, что в вершину 4 надо идти через вершину 5. Возвращаясь к вычислению С 5 , видим, что в вершину 5 надо идти через вершину 3. А в вершину 3 можно попасть только из вершины 1. Итак, кратчайший путь таков:. Оптимизационные задачи на графах, возникающие при подготовке управленческих решений в производственном менеджменте, весьма многообразны. Рассмотрим в качестве примера еще одну задачу, связанную с перевозками. Задача о максимальном потоке. Как то есть по каким маршрутам послать максимально возможное количество грузов из начального пункта в конечный пункт, если пропускная способность путей между пунктами ограничена? Исходные данные о транспортной системе, например, внутризаводской, приведенные на рис. Далее надо добиться, чтобы все 6 вышедших из пункта 0 единиц груза достигли конечного пункта 4. Очевидно, 2 единицы груза, пришедшие в пункт 1, можно непосредственно направить в пункт 4. Пришедшие в пункт 2 грузы придется разделить: В пункт 3 доставлены такие грузы: Их направляем в пункт 4. Итак, максимальная пропускная способность рассматриваемой транспортной системы - 6 единиц груза. При этом не используются внутренние участки ветки между пунктами 1 и 2, а также между пунктами 1 и 3. Не догружена ветка между пунктами 1 и 4 - по ней направлены 2 единицы груза при пропускной способности в 3 единицы. Задача линейного программирования при максимизации потока. Дадим формулировку задачи о максимальном потоке в терминах линейного программирования. Пусть Х KM - объем перевозок из пункта К в пункт М. Задача линейного программирования, нацеленная на максимизацию потока, имеет вид:. Здесь F - целевая функция, условие 0 описывает вхождение грузов в транспортную систему. Условия 1 - 3 задают балансовые соотношения для узлов 1- 3 системы. Другими словами, для каждого из внутренних узлов входящий поток грузов равен выходящему потоку, грузы не скапливаются внутри и системы и не "рождаются" в ней. Условие 4 - это условие "выхода" грузов из системы. Вместе с условием 0 оно составляет балансовое соотношение для системы в целом "вход" равен "выходу". Следующие девять неравенств задают ограничения на пропускную способность отдельных "веток" транспортной системы. Затем в системе ограничений задачи линейного программирования указана неотрицательность объемов перевозок и целевой функции. Ясно, что последнее неравенство вытекает из вида целевой функции соотношения 0 или 4 и неотрицательности объемов перевозок. О многообразии оптимизационных задач. В различных проблемах принятия решений возникают самые разнообразные задачи оптимизации. Для их решения применяются те или иные методы, точные или приближенные. Задачи оптимизации часто используются в теоретико-экономических исследованиях. Достаточно вспомнить оптимизацию экономического роста страны с помощью матрицы межотраслевого баланса Василия Леонтьева или микроэкономические задачи определения оптимального объема выпуска по функции издержек при фиксированной цене или в условиях монополии или минимизации издержек при заданном объеме выпуска путем выбора оптимального соотношения факторов производства с учетом платы за них. Кроме затронутых выше методов решения задач оптимизации, напомним о том, что гладкие функции оптимизируют, приравнивая 0 производную для функций нескольких переменных - частные производные. При наличии ограничений используют множители Лагранжа. Эти методы обычно излагаются в курсах высшей математики и потому опущены здесь. Они рассматриваются в соответствующей литературе. Теория графов в управлении организационными системами. Изобразите на плоскости ограничения задачи линейного программирования и решите графически эту задачу:. Транспортная сеть с указанием расстояний приведена на рис. Найдите кратчайший путь из пункта 1 в пункт 4. Решите задачу коммивояжера для четырех городов маршрут должен быть замкнутым и не содержать повторных посещений. Затраты на проезд приведены в табл. Как послать максимальное количество грузов из начального пункта 1 в конечный пункт 8, если пропускная способность путей между пунктами транспортной сети рис. Классификация оптимизационных задач принятия решений. Решения, оптимальные по Парето. Многокритериальные задачи принятия решений: Задачи оптимизации и нечеткие переменные на основе работы [5]. Моделирование и экспертные оценки при принятии решений. Интерактивные системы принятия решений. Методы учета неопределенностей принятия решений: Эконометрические методы принятия решений на основе монографии [6]. Имитационное моделировании и метод статистических испытаний Монте-Карло при принятии решений. Методы теории игр теория конфликтов , роль информации и равновесие по Нэшу в теории принятия решений. Проблемы комбинированного применения различных методов в конкретных прикладных работах. Информационные технологии поддержки принятия решений. Ru Библиотека Исследования Форумы. Потреби-тель 1 Потреби-тель 2 Потреби-тель 3 Потреби-тель 4 Запасы на складах Склад 1 2 5 5 5 60 Склад 2 1 2 1 4 80 Склад 3 3 1 5 2 60 Потреб-ности 50 40 70 40 Содержание в 1 унции К. Содержание в 1 унции С. Стоимость 1 унции, в центах.
Короткие стихис днем рожденияот коллектива
Структура отдела продаж схема
Кредитная карта куб магнитогорск
Где больше всего золота
Дадут ли кредитесли испорчена кредитная история
Штатное расписание т 3 пример заполнения