|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕСтр 1 из 17Следующая ⇒
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ Во многих ситуациях, встречающихся в промышленности, сельском хозяйстве, экономической деятельности и т.д., задача оптимизации плана некоторых экономико-производственных действий может быть записана в виде линейных уравнений и неравенств с линейным же, относительно искомых, определяющих этот план, переменных целевой функцией. К задачам этого же вида сводятся очень многие задачи оптимизации и принятия решений из некоторых других самостоятельных направлений прикладной математики. Соответственно возникает потребность в математической теории, позволяющей решать такие задачи. Такая теория существует и называется линейным программированием. Данное название возникло в 30-е годы, когда представления о программировании на компьютере ещё не существовало. Под программированием фактически подразумевается планирование. Однако, этот термин уже укоренился, и не только в линейном случае. Имеются так же и такие названия математических теорий решения задач оптимизации, как нелинейное программирование и динамическое программирование. В общем виде задача линейного программирования (ЛП) заключается в отыскании таких неотрицательных чисел x1, x2..., хn которые максимизируют (минимизируют) линейную функцию:
при условии выполнения системы неравенств:
При описании реальной ситуации с помощью линейной модели следует проверять наличие у модели таких свойств, как пропорциональность и аддитивность. Пропорциональность означает, что вклад каждой переменной в целевую функцию (ЦФ) и общий объем потребления соответствующих ресурсов должен быть прямо пропорционален величине этой переменной. Например, если продавая какой либо товар в общем случае по одной цене рублей, фирма будет делать скидку при определенном уровне закупки, то будет отсутствовать прямая пропорциональность между доходом фирмы и величиной переменной. Т.е. в разных ситуациях одна единица товара будет приносить разный доход. Аддитивность означает, что ЦФ и ограничения должны представлять собой сумму вкладов от различных переменных. Примером нарушения аддитивности служит ситуация, когда увеличение сбыта одного из конкурирующих видов продукции, производимых одной фирмой, влияет на объем реализации другого. При решении задачи линейного программирования целесообразно бывает введение следующих определений. Допустимое решение – это совокупность чисел (план) Оптимальное решение – это план, при котором ЦФ принимает свое максимальное (минимальное) значение. Прежде чем построить математическую модель задачи, т.е. записать ее с помощью математических соотношений, необходимо четко разобраться с экономической ситуацией, описанной в условии. Для этого необходимо с точки зрения экономики, а не математики, ответить на следующие вопросы: 1) Что является искомыми величинами задачи? 2) Какой параметр задачи служит критерием эффективности (оптимальности) решения? (это может быть: прибыль, время, количество отходов и т.д.) 3) В каком направлении должно изменяться значение этого параметра (к max или к min) для достижения наилучших результатов? 4) Какие условия в отношении искомых величин и ресурсов задачи должны быть выполнены? Эти условия устанавливают, как должны соотноситься друг с другом различные параметры задачи, например, количество ресурса, затраченного при производстве, и его запас на складе; количество выпускаемой продукции и емкость склада, где она будет храниться; количество выпускаемой продукции и рыночный спрос на эту продукцию и т.д. Только после экономического ответа на все эти вопросы можно приступать к записи этих ответов в математическом виде, т.е. к записи математической модели. а) Искомые величины являются переменными задачи, которые как правило обозначаются малыми латинскими буквами с индексами, например, однотипные переменные удобно представлять в виде б) Цель решения записывается в виде целевой функции, обозначаемой, например, в) Условия, налагаемые на переменные и ресурсы задачи, записываются в виде системы равенств или неравенств, т.е. ограничений. Левые и правые части ограничений отражают способ получения (расчет или численные значения из условия задачи) значений тех параметров задачи, на которые были наложены соответствующие условия. В процессе записи математической модели целесообразно указывать единицы измерения переменных задачи, целевой функции и всех ограничений. Задача Фабрика производит два вида красок: первый – для наружных, а второй – для внутренних работ. Для производства красок используются два ингредиента: А и В. Известны расходы ингредиентов А и В на 1 т соответствующих красок и максимально возможные суточные запасы этих ингредиентов на складе. Данные по расходам ингредиентов на краски первого и второго вида представлены в таблице.
Изучение рынка сбыта показало, что суточный спрос на краску 2-го вида никогда не превышает спроса на краску 1-го вида более, чем на 1 т. Кроме того, установлено, что спрос на краску 2-го вида никогда не превышает 2 т в сутки. Оптовые цены одной тонны красок равны: 3 тыс. руб. для краски 1-го вида; 2 тыс. руб. для краски 2-го вида. Необходимо построить математическую модель, позволяющую установить, какое количество краски каждого вида надо производить, чтобы доход от реализации продукции был максимальным. Решение В задаче требуется установить, сколько краски каждого вида надо производить. Поэтому искомыми величинами, а значит, и переменными задачи являются суточные объемы производства каждого вида красок:
В условии задачи сформулирована цель – добиться максимального дохода от реализации продукции. Т.е. критерием эффективности служит параметр суточного дохода, который должен стремиться к максимуму. Чтобы рассчитать величину суточного дохода от продажи красок обоих видов, необходимо знать объемы производства красок, т.е.
Возможные объемы производства красок · количество ингредиентов А и В, израсходованное в течение суток на производство красок обоих видов, не может превышать суточного запаса этих ингредиентов на складе; · согласно результатам изучения рыночного спроса суточный объем производства краски 2-го вида может превышать объем производства краски 1-го вида, но не более, чем на 1 т краски; · объем производства краски 2-го вида не должен превышать 2 т в сутки, что также следует из результатов изучения рынков сбыта; · объемы производства красок не могут быть отрицательными. Таким образом, все ограничения задачи делятся на 3 группы, обусловленные: 1) расходом ингредиентов; 2) рыночным спросом на краску; 3) неотрицательностью объемов производства. Ограничения по расходу любого из ингредиентов имеют следующую содержательную форму записи:
Запишем эти ограничения в математической форме. Левая часть ограничения – это формула расчета суточного расхода конкретного ингредиента на производство красок. Так из условия известен расход ингредиента А на производство 1 т краски 1-го вида (1 т ингр. А) и 1 т краски 2-го вида (2 т ингр. А). Тогда на производство Правая часть ограничения – это величина суточного запаса ингредиента на складе, например, 6 т ингредиента А в сутки. Таким образом, ограничение по расходу А имеет вид
Аналогична математическая запись ограничения по расходу В
Примечание. Следует всегда проверять размерность левой и правой частей каждого из ограничений, поскольку их несовпадение свидетельствует о принципиальной ошибке при составлении ограничений. Ограничение по суточному объему производства краски 1-го вида по сравнению с объемом производства краски 2-го вида имеет содержательную форму
и математическую форму
Ограничение по суточному объему производства краски 1-го вида имеет содержательную форму
и математическую форму
Неотрицательность объемов производства задается как
Таким образом, математическая модель этой задачи имеет вид
Для задач линейного программирования, содержащих только две переменные Задача Найдем оптимальное решение задачи о красках, математическая модель которой имеет вид:
Построим прямые ограничений (рис. 1).
Рис. 1. Графическое решение задачи
Определим ОДР. Например, подставим точку (0;0) в исходное ограничение (3), получим 0 ≤ 1 , что является истинным неравенством, поэтому стрелкой (или штрихованием) обозначим полуплоскость, содержащую точку (0;0), т.е. расположенную правее и ниже прямой (3). Аналогично определим допустимые полуплоскости для остальных ограничений и укажем их стрелками у соответствующих прямых ограничений (см. рис. 1). Общей областью, разрешенной всеми ограничениями, т.е. ОДР является многоугольник ABCDEF. Найдем координаты точек пересечения прямых ограничений, т.е. координаты угловых точек. В некоторых случаях хороший рисунок позволяет сразу определять координаты угловых точек.
Для определения координаты точки Е решим систему уравнений с ограничениями (5) и (6).
Решая данную систему получаем:
Найдем значение целевой функции в угловых точках, т.е. подставим их координаты в уравнение
Е – это точка максимума ЦФ. Таким образом, наилучшим режимом работы фирмы является ежесуточное производство краски 1-го вида в объеме 3 1/3 т и краски 2-го вида в объеме 1 1/3 т. Доход от продажи красок составит 12 2/3 тыс. руб. в сутки. Решая графическим методом, предполагающим построение целевого вектора, проводим вектор, координатами которого служат коэффициенты в уравнении с целевой функцией В более общем случае разработан и широко применяется универсальный метод решения любой задачи ЛП, называемый симплекс-методом. Симплекс – метод, как метод решения задач ЛП был предложен американским математиком-экономистом Данцигом в 1951 году. Графически симплекс метод представляет из себя передвижение по выпуклому многограннику от вершины к вершине, при этом значение целевой функции на каждом шаге улучшается до тех пор, пока не достигается оптимум. Идея симплекс – метода состоит в том, чтобы преобразовать уравнение содержащее целевую функцию к виду: Решение Введем свободные переменные x3, x4, x5, x6, для того, чтобы систему неравенств превратить в систему уравнений.
Выбираем переменную, входящую в целевую функцию с максимальным коэффициентом, это x1. Сравниваем частные от деления свободных членов на коэффициенты при x1 6; 4; -1; +¥. Выбираем строку с min > 0 частным от деления и нормируем ее, из остальных строк исключаем x1 методом Гаусса.
Выбираем переменную, входящую в целевую функцию с max коэффициентом, это x2. Сравниваем частные от деления свободных членов на коэффициенты при x2 4/3; 8; 10/3; 2. Выбираем строку с min > 0 частным от деления и нормируем ее, из остальных строк исключаем x2 методом Гаусса.
Так как все коэффициенты перед переменными в уравнении с целевой функцией < 0, то решение законченно. В силу не отрицательности переменных из уравнения, содержащего целевую функцию следует, что она достигает максимального значения, в случае, когда x3 = 0 и x4 = 0, в этом случае
АНАЛИЗ ЧУВСТВИТЕЛЬНОСТИ Теоретическое введение Неизбежное колебание значений таких экономических параметров, как цены на продукцию и сырье, запасы сырья, спрос на рынке и т.д. может привести к неоптимальности или непригодности прежнего режима работы. Для учета подобных ситуаций проводится анализ чувствительности, т.е. анализ того, как возможные изменения параметров исходной модели повлияют на полученное ранее оптимальное решение задачи ЛП. Для решения задач анализа чувствительности ограничения линейной модели классифицируются следующим образом. Связывающие ограничения проходят через оптимальную точку. Несвязывающие ограничения не проходят через оптимальную точку. Аналогично ресурс, представляемый связывающим ограничением, называют дефицитным, а ресурс, представляемый несвязывающим ограничением – недефицитным. Ограничение называют избыточным в том случае, если его исключение не влияет на ОДР и, следовательно, на оптимальное решение. Выделяют следующие три задачи анализа на чувствительность. 1. Анализ сокращения или увеличения ресурсов: • на сколько можно увеличить (ограничения типа ≤) запас дефицитного ресурса для улучшения оптимального значения ЦФ? • на сколько можно уменьшить (ограничения типа ≤) запас недефицитного ресурса при сохранении оптимального значения ЦФ? 2. Увеличение (ограничения типа ≤) запаса какого из ресурсов наиболее выгодно? 3. Анализ изменения коэффициентов ЦФ: каков диапазон изменения коэффициентов ЦФ, при котором не меняется оптимальное решение?
Правило № 1 Чтобы графически определить максимальное увеличение запаса дефицитного ресурса, вызывающее улучшение оптимального решения, необходимо передвигать соответствующую прямую в направлении улучшения ЦФ до тех пор, пока это ограничение не станет избыточным. При прохождении прямой (1) через точку К (рис. 2) многоугольник ABCKF становится ОДР, а ограничение (1) – избыточным. Действительно, если удалить прямую (1), проходящую через точку К, то ОДР ABCKF не изменится. Точка К становится оптимальной, в этой точке ограничения (2) и (4) становятся связывающими.
Рис. 2 Анализ увеличения ресурса А.
Правило № 2 Чтобы численно определить максимальную величину запаса дефицитного ресурса, вызывающую улучшение оптимального решения, необходимо: 1) определить координаты точки (x1;x2), в которой соответствующее ограничение становится избыточным; 2) подставить координаты (x1;x2)в левую часть соответствующего ограничения.
Координаты точки К(3;2) находятся путем решения системы уравнений прямых (2) и (4). Т.е. в этой точке фирма будет производить 3 т краски 1-го вида и 2 т краски 2-го вида. Подставим x1=3 и x2=2 в левую часть ограничения (1) и получим максимально допустимый запас ингредиента А.
Дальнейшее увеличение запаса ингредиента А нецелесообразно, потому что это не изменит ОДР и не приведет к другому оптимальному решению (см. рис. 2). Доход от продажи красок в объеме, соответствующем точке К, можно рассчитать, подставив ее координаты (3;2) в выражение ЦФ
Рассмотрим вопрос о целесообразности увеличения запаса ингредиента В. Согласно правилу № 1, соответствующее ограничение (2) становится избыточным в точке J, в которой пересекаются прямая (1) и ось переменной x1 (рис. 3). Многоугольник ABCDJ становится ОДР, а точка J(6;0) – оптимальным решением.
Рис. 3 Анализ увеличения ресурса В.
В точке J выгодно производить только краску 1-го вида (6 т в сутки). Доход от продажи при этом составит:
Чтобы обеспечить такой режим работы, согласно правилу № 2, запас ингредиента В надо увеличить до величины:
Ограничения (3) и (4) являются не связывающими, т.к. не проходят через оптимальную точку E (см. рис. 1). Соответствующие им ресурсы (спрос на краски) являются недефицитными. С экономической точки зрения это означает, что в данный момент уровень спроса на краски непосредственно не определяет объемы производства. Поэтому некоторое его колебание может никак не повлиять на оптимальный режим производства в точке E. Например, увеличение (уменьшение) спроса на краску 2-го вида будет соответствовать перемещению прямой ограничения x2≤2 (4) вверх (вниз). Перемещение прямой (4) вверх никак не может изменить точку Е максимума ЦФ. Перемещение же прямой (4) вниз не влияет на существующее оптимальное решение только до пересечения с точкой Е (см. правило № 3.3). Из рис. 1 видно, что дальнейшее перемещение (4) приведет к тому, что точка Е будет за пределами новой ОДР, выделенной более темным цветом. Кроме того, любое оптимальное решение для этой новой ОДР будет хуже точки Е. Правило № 3 Чтобы определить максимальное уменьшение запаса недефицитного ресурса, не меняющее оптимальное решение, необходимо передвигать соответствующую прямую до пересечения с оптимальной точкой. Правило № 4 Чтобы численно определить минимальную величину запаса недефицитного ресурса, не меняющую оптимальное решение, необходимо подставить координаты оптимальной точки в левую часть соответствующего ограничения. Чтобы выяснить, до каких пределов падение спроса на краску 2-го вида не повлияет на производство в точке E Делаем вывод: предельный уровень, до которого может упасть спрос на краску 2-го вида и при котором не изменится оптимальность полученного ранее решения, равен 1 1/3 т краски в сутки. Экономический смысл ограничения (3)
в том, что объем продаж краски 2-го вида может превысить объем продаж краски 1-го вида максимум на 1 т. Дальнейшее увеличение продаж краски 2-го вида по сравнению с краской 1-го вида графически отобразится перемещением прямой (3) влево и вверх, но никак не повлияет на оптимальность точки Е. Но если разность спросов на краску 2-го и 1-го видов будет уменьшаться, то прямая (3) будет перемещаться ниже и правее. Последним положением прямой (3), при котором точка Е остается оптимальной, является пересечение с точкой Е (см. рис. 3.1). Согласно правилу № 4, подставим координаты точки E
Получаем, что разность спросов на краску 2-го и 1-го вида в точке стала отрицательной. То есть, прохождение прямой (3) через точку Е означает, что краску 2-го вида будут покупать в меньшем объеме, чем краску 1-го вида
Делаем вывод: максимальное превышение спроса на краску 1-го вида над спросом на краску 2-го вида, при котором оптимальное решение в точке Е не изменится, составляет 2 т краски в сутки. Результаты решения первой задачи анализа оптимального решения на чувствительность представлены в табл. Правило 5 Чтобы определить границы допустимого диапазона изменения коэффициента ЦФ, например min c1 и max c1, необходимо приравнять тангенс угла наклона целевой прямой ЦФ tgα поочередно к тангенсам углов наклона прямых связывающих ограничений, например tgα(1) и tgα(2) (рис. 5 и 6)
Рис. 5. Определение min c1
Рис. 6. Определение max c1
Определим насколько максимально может снизиться цена на краску 1-го вида, не изменяя оптимальную точку Е. Для этого применим правило № 5 и формулу расчета тангенса угла наклона прямой (рис. 7).
Рис. 7. Определение тангенса угла наклона tgα прямой Y1x1+ Y2x2=Z
Определим тангенсы углов наклона: 1) целевой прямой L(X)=3x1+2x2 → max, учитывая, что c2=2 фиксировано
2) связывающего ограничения x1+2x2 ≤ 6 (1)
3) связывающего ограничения 2x1+x2 ≤ 8 (2)
Для нахождения min c1 целевая прямая должна совпасть с прямой (1) (рис. 5):
Для нахождения max c1 целевая прямая должна совпасть с прямой (2) (рис. 6):
Теории игр. Теория игр – это теория математических моделей принятия оптимальных решений в условиях конфликта или неопределённости. При этом конфликт не обязательно должен быть антагонистическим, в качестве конфликта можно рассматривать любое разногласие. Рассмотрим следующий экономический пример. Пусть требуется принять решение о выпуске на рынок некоторого товара. Может случиться, что объём спроса на этот товар известен точно; может быть, что известно лишь статистическое распределение возможных значений спроса; наконец, может оказаться, что известны лишь границы, в которых заключен спрос, но ни каких даже вероятностных соображений о его предстоящих значениях нет. Последний случай квалифицируется как неопределённость. Такая неопределённость может возникнуть, когда спрос (например, на сезонные товары) зависит от метеорологических условий (конфликт с природой) или в условиях рынка от деятельности конкурента, уже удовлетворившего неизвестную часть спроса. Приведённые примеры при определённых условиях могут быть приведены к игре. Всякая теоретико-игровая модель должна отражать, кто и как конфликтует, а также, кто и в какой форме заинтересован в том или ином исходе конфликта. Действующие в конфликте стороны называются игроками, а решения, которые способны принимать игроки, стратегии. Содержание математической теории игр состоит, во-первых, в установлении принципов оптимального поведения игроков в играх, во-вторых, в доказательстве существования ситуации, которые складываются в результате применения этих принципов, и, в-третьих, в разработке методов фактического нахождения таких ситуаций. Для игр с одной коалицией действия множество всех ситуаций можно принять за множество стратегий этой единственной коалиции действия и далее о стратегиях не упоминать. По этому такие игры называются нестратегическими, важным классом которых являются игры с природой, применяемые для анализа экономических ситуаций, оценки эффективности принимаемых решений и выбора наиболее предпочтительных альтернатив, в которых риск связан с совокупностью неопределённых фактов окружающей среды, именуемых «природа». Поэтому термин «природа» характеризует некоторую объективную действительность, которую не следует понимать буквально, хотя вполне могут встретиться ситуации в которых игроком действительно может выступить природа (например, обстоятельства, связанные с погодными условиями или с природными стихийными силами). В отличие от нестратегических игр, все остальные игры с двумя или более коалициями действия называются стратегическими. В практических ситуациях часто появляется необходимость согласования действий компании, объединений, министерств и других участников проектов в случаях, когда их интересы не совпадают. В подобных ситуациях теория стратегических игр позволяет найти оптимальное решение для поведения всех участников проекта, обязанных согласовывать свои действия при столкновении интересов. Далее будут рассмотрены матричные игры. Под матричной игрой
где Задачей теории игр является определение оптимальных стратегий игроков. В матричной игре оптимальной для игрока А называется стратегия, которая при многократном повторении игры обеспечивает максимально возможный средний выигрыш, а для игрока В под оптимальной понимается стратегия, обеспечивающая ему минимальный средний проигрыш. При этом предполагается, что противник является по меньшей мере таким же разумным и делает всё для того, чтобы помешать нам добиться своей цели. Вполне определённые игры. Вполне определённая игра является наиболее простым случаем матричной игры. Вполне определённой игрой или игрой с седловой точкой называется игра, у которой совпадают нижняя и верхняя цены игры, то есть выполняется равенство:
При этом Простота решения игры с седловой точкой заключается в том, что оптимальные стратегии обоих игроков находятся сразу. Для игрока А это стратегия Действительно, пусть игрок А выбрал оптимальную стратегию соответствующую Решением игры в примере является выбор стратегий Упрощение игр Если игра m× n не имеет седловой точки, то найти её решение, особенно при больших m и n, трудно. Иногда эту задачу можно упростить, сократив число стратегий, вычёркивая некоторые лишние: дублирующие и заведомо невыгодные. В случае если у какого–либо из игроков две стратегии имеют в матрице только совпадающие элементы, то эти стратегии называются дублирующими. При этом неважно, какую из них игрок предпочтет для решения игры. Рассмотрим две стратегии первого игрока – i – ю и k – ю. При этом пусть для всех элементов соответствующих строк матрицы выполняются условия: Аналогично рассмотрим две стратегии второго игрока - j - ю и l – ю, и при этом для элементов соответствующих столбцов матрицы выполняются условия: В результате при наличии доминирующих и дублирующих стратегий часть стратегий можно не рассматривать, что приведет в ряде случаев к значительному упрощению платежной матрицы. Пример 3. Упростить игру, заданную матрицей: Решение. Начнём упрощение с игрока А. Стратегия А3 «дублирует» А1 (А3 = А1). Следовательно, любую из них можно вычеркнуть (например, А3). Далее сравнивая А1 и А2, видим, что элементы А2 меньше или равны А1 (А2 ≤ А1). Т.е. стратегия А2 для игрока А желающего выиграть как можно больше, невыгодна. Т.о. Получаем матрицу Для игрока В, который стремится как можно меньше проиграть, В3 невыгодна по сравнению с В4 (В3 > В4). Вычёркиваем В3. Т.о. игра 4×4 свелась к игре 2×3: Эквивалентное преобразование платежной матрицы применяется для облегчения расчетов, и при этом оптимальные смешанные стратегии игроков не изменяются. Теорема. Оптимальные смешанные стратегии
Стратегия называется активной, если входит в оптимальное решение с отличной от нуля вероятностью, т.е. Теорема (об активных стратегиях): Если один игрок придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры
Упрощение игр Если игра m× n не имеет седловой точки, то найти её решение, особенно при больших m и n, трудно. Иногда эту задачу можно упростить, сократив число стратегий, вычёркивая некоторые лишние: дублирующие и заведомо невыгодные. В случае если у какого–либо из игроков две стратегии имеют в матрице только совпадающие элементы, то эти стратегии называются дублирующими. При этом неважно, какую из них игрок предпочтет для решения игры. Рассмотрим две стратегии первого игрока – i – ю и k – ю. При этом пусть для всех элементов соответствующих строк матрицы выполняются условия: Аналогично рассмотрим две стратегии второго игрока - j - ю и l – ю, и при этом для элементов соответствующих столбцов матрицы выполняются условия: В результате при наличии доминирующих и дублирующих стратегий часть стратегий можно не рассматривать, что приведет в ряде случаев к значительному упрощению платежной матрицы. Пример 4. Упростить игру, заданную матрицей: Решение. Начнём упрощение с игрока А. Стратегия А3 «дублирует» А1 (А3 = А1). Следовательно, любую из них можно вычеркнуть (например, А3). Далее сравнивая А1 и А2, видим, что элементы А2 меньше или равны А1 (А2 ≤ А1). Т.е. стратегия А2 для игрока А желающего выиграть как можно больше, невыгодна. Т.о. Получаем матрицу Для игрока В, который стремится как можно меньше проиграть, В3 невыгодна по сравнению с В4 (В3 > В4). Вычёркиваем В3. Т.о. игра 4×4 свелась к игре 2×3: Эквивалентное преобразование платежной матрицы применяется для облегчения расчетов, и при этом оптимальные смешанные стратегии игроков не изменяются. Теорема. Оптимальные смешанные стратегии Пример 5. В матричной игре с платежной матрицей Запись ответа Как было нами оговорено, в качестве ответа записываем ту стратегию, которая чаще всего выделяется как лучшая по перечисленным критериям. Выпишем оптимальные результаты по разным критериям:
Как видно, стратегия Ответ: по совокупности критериев выбираем стратегию ПОНЯТИЕ О ЦЕНЕ ИНФОРМАЦИИ В игре с природой часто возникает возможность получения информации или уточнения данных о реализации состояний природы. Такая информация «предоставляется» не «бесплатно» – для ее получения необходимо затратить определенные усилия, вложить средства и т.п. Встает вопрос о максимальной «цене» такой информации. Сколько мы можем «заплатить» за информацию, чтобы выигрыш при обладании ей за вычетом платы за информацию был не меньше выигрыша без учета этой информации? При этом необходимо сравнивать, очевидно, случаи оптимального поведения при дополнительной информации и без нее. Проще всего данный вопрос осветить на примере игры с природой, имеющей частые повторения (партии) в одинаковых условиях. В этом случае для выбора оптимальной стратегии предпочтительно использовать критерий Байеса. В качестве примера рассмотрим следующую ситуацию. Коммерсант ежедневно возит молочную продукцию на своем автомобиле для продажи в дачном поселке. Он закупает молоко ящиками по 20 бутылок по мелкооптовой цене 20 рублей за бутылку и продает в розницу по 35 рублей за бутылку. За день может быть реализовано от 1 до 5 ящиков. Так как в автомобиле нет холодильника, то все нереализованное молоко портится и выбрасывается. По предварительным опросам дачников, коммерсант делает предположение о вероятностях спроса: спрос в 1 ящик имеет вероятность 10%, в 2 ящика – 20%, в 3 ящика – 30%, в 4 ящика – 30%, в 5 ящиков – 10% (для простоты рассмотрения будем считать, что ежедневно продается целое количество ящиков молока). Таким образом, ежедневно коммерсант должен принять решение, сколько ящиков молока закупить и привезти на продажу. Запишем матрицу игры с природой для этой задачи. Выигрышем будем считать прибыль, которую получит коммерсант в каждой ситуации. Строки матрицы будут соответствовать возможным стратегиям коммерсанта – купить 1, 2, 3, 4 или 5 ящиков. Столбцы будут соответствовать спросу на молоко: 1, 2, 3, 4 или 5 ящиков. Матрица игры с природой будет иметь представлена в табл. 5. Поясним, как получились значения в таблице. Как следует из условия, при покупке одного ящика коммерсант тратит 400 руб., а при продаже получает 700 руб. Таким образом, каждый проданный ящик приносит прибыль 300 руб., а каждый пропавший приносит убыток 400 руб. (то есть прибыль минус 400 руб.). Рассмотрим ситуацию, когда коммерсант привез 4 ящика. Если спрос равен 4 ящикам, то прибыль будет равна 1200 руб. При спросе 3 ящика прибыль составит 500 руб. Для спроса 2 ящика получаем убытки 200 руб. (результат игры равен – 200). Для спроса 1 ящик результат равен – 900 руб. Если же спрос равен 5 ящикам, то продается только 4, так как больше товара нет, и спрос остается неудовлетворенным. В этом случае, как и при спросе, равном 4, результат игры равен 1200 руб. Для других вариантов завоза результаты получаются аналогично. Таблица 5. Игра с природой для примера Исполнитель – Заказчик
Если другой информации у коммерсанта нет, то ему лучше применять для выбора стратегии критерий Байеса – в этом случае он сможет оптимизировать среднюю прибыль и добиться наилучшего результата за многодневный период торговли.
Таким образом, лучше возить по 3 ящика молока. Тогда средняя дневная прибыль составит 620 рублей. Рассмотрим две возможности дополнительной информации: 1. Имеется возможность знать состояние природы перед каждой следующей партией в игре. В данном случае – знать спрос на следующий день (например, можно провести мониторинг спроса на следующий день, организовать продажи по записи и т.п.). 2. Имеется возможность уточнить значения вероятностей состояний природы (например, собрать информацию об аналогичных объектах, провести подробное изучение спроса и т.п.). Описанные возможности требуют дополнительных затрат средств и времени. Каковы максимально допустимые удельные затраты (затраты в пересчете на один день торговли)? Изучим первую возможность. Если коммерсант будет точно знать спрос на следующий день, то он привезет оптимально количество молока – ровно столько ящиков, сколько будет закуплено. При этом прибыль составит по 300 руб. с 1 ящика, 600 руб. с 2-х, 900 руб. с 3-х, 1200 руб. с 4-х и 1500 руб. с 5-ти ящиков. Так как знание спроса не влияет на частоту его реализации, то 1 ящик он будет возить 10% дней, 2 ящика – 20%, 3 ящика – 30%, 4 ящика – 30% и 5 ящиков – 10%. В итоге коммерсант получит среднюю прибыль, равную:
Таким образом, владея информацией о спросе, коммерсант увеличил свою среднюю прибыль на 310 руб. в день. Именно это и есть удельная стоимость точной информации о спросе. Важно заметить, что в результате получения информации коммерсант принципиально поменял свою деятельность: вместо ежедневного завоза по 3 ящика молока он должен возить различное количество, строго определенное дополнительной информацией. Изучим второй вид дополнительной информации. Представим, что у коммерсанта имеется противоречивая информация о вероятностях спроса. Первая версия описана выше (0,1; 0,2; 0,3; 0,3; 0,1). По второй версии спрос равновероятен, то есть вероятность спроса равна 0,2 для всех вариантов. Третьи источники утверждают, что спрос в 1, 2, 3, 4 и 5 ящиков имеет вероятности соответственно 0,1; 0,1; 0,1; 0,4; 0,3. Если мы можем провести серию мероприятий по уточнению этой информации, то какова максимальная удельная стоимость таких мероприятий? Оптимальный выбор стратегии при первом варианте мы уже сделали – нужно возить по 3 ящика и получим в среднем 620 руб. в день. Для второго варианта вероятностей:
Не смотря на то, что среднее значение прибыли заметно изменилось, выбор стратегии не поменялся. Можно сделать вывод, что уточнение между первым и вторым вариантами вероятностей состояний ничего не стоит. (Это справедливо лишь для поставленной цели определения количества завозимого ежедневно молока. Если же главной целью является оценка рентабельности бизнеса, то цена такой информации может быть совсем ненулевой. Подумайте, почему?). Для третьего варианта вероятностей:
В данном случае лучше возить по 4 ящика молока и получим в среднем 780 руб. в день прибыли. То есть такая информация побуждает нас сменить решение. Однако посмотрим, сколько же стоит информация с учетом «разумности» нашего поведения при потенциальной возможности первого или третьего вариантов распределения. Предполагая возможность всех вариантов распределения (а не точную уверенность в одном из них), коммерсант находится в дилемме выбора между 3 и 4 ящиками. Выбрав 4 ящика, в первом случае он получит 500 руб. в день вместо 620 (потеря 120 руб.). Во втором случае он получит 360 руб. вместо 480 (потеря 120 руб.). Выбрав же 3 ящика при третьей возможности вероятностей, он получит 710 руб. вместо 780 (потеря 70 руб.). Таким образом, минимальная потеря достигается выбором 3 ящиков и равна 70 рублям. Это и есть максимальная удельная цена данного уточнения. Интересно заметить, что оценивая разные варианты, мы фактически применили критерий Сэвиджа к новой матричной игре, в которой состояниями природы являются уже варианты распределения вероятностей, а результатами – средние результаты при данных вероятностях:
Максимальная удельная стоимость информации в таком случае оказалась равна минимаксу матрицы рисков для такой игры:
Заметим, что все приведенные рассуждения справедливы в предположении, что уточняя информацию о вероятностях, мы получим один из известных вариантов распределения. Таким образом, выбирая решение без точной информации, мы все же учитывали ее потенциальные возможности. Получение же неожиданного нового варианта распределения считалось невозможным. Оценка стоимости информации о вероятностях состояний природы без фиксации предварительных вариантов – гораздо более сложная задача. В общем случае можно определить стоимость информации так: стоимость точной информации не может превышать разницу выигрышей, полученную за счет изменения стратегии в результате обладания данной информацией относительно лучшего варианта стратегии при рассмотрении всех возможных вариантов как потенциально реализуемых.
ТРАНСПОРТНАЯ ЗАДАЧА Задача о размещении (транспортная задача) – это распределительная задача, в которой работы и ресурсы измеряются в одних и тех же единицах. В таких задачах ресурсы могут быть разделены между работами, и отдельные работы могут быть выполнены с помощью различных комбинаций ресурсов. Примером типичной транспортной задачи (ТЗ) является распределение (транспортировка) продукции, находящейся на складах, по предприятиям-потребителям. Стандартная ТЗ определяется как задача разработки наиболее экономичного плана перевозки продукции одного вида из нескольких пунктов отправления в пункты назначения. При этом величина транспортных расходов прямо пропорциональна объему перевозимой продукции и задается с помощью тарифов на перевозку единицы продукции. Исходными параметрами при построении модели для решения транспортной задачи являются: 1) n – количество пунктов отправления, m – количество пунктов назначения. 2) a i – запас продукции в пункте отправления Ai (i = 1, n ) [ед. прод.]. 3) b j – спрос на продукцию в пункте назначения Bj (j =1, m) [ед. прод.]. 4) c ij – тариф (стоимость) перевозки единицы продукции из пункта отправления Ai в пункт назначения Bj [руб. / ед. прод.]. Искомыми параметрами при построении модели для решения транспортной задачи являются: 1) x ij – количество продукции, перевозимой из пункта отправления Ai в пункт назначения Bj [ед. прод.]. 2) L(X) – транспортные расходы на перевозку всей продукции [руб.]. Основными этапами построения модели для решения транспортной задачи являются: I. Определение переменных. (Этот этап весьма формален, т.к. переменными как правило служат x ij – количество продукции, перевозимой из пункта отправления Ai в пункт назначения Bj). II. Проверка сбалансированности задачи. (Задача называется сбалансированной, если сумма запасов продукции во всех пунктах отправления равна суммарной потребности во всех пунктах потребления, т.е. Если суммарные потребности превышают суммарные запасы, то необходим дополнительный фиктивный пункт отправления, формально восполняющий существующий недостаток продукции в пунктах отправления: Для фиктивных перевозок вводятся фиктивные тарифы cф, величина которых обычно приравнивается к нулю cф =0 . Но в некоторых ситуациях величину фиктивного тарифа можно интерпретировать как штраф, которым облагается каждая единица недопоставленной продукции. В этом случае величина cф может быть любым положительным числом. Задача Найти тремя методами опорный план транспортной задачи, в которой запасы на трех складах равны 210, 170, 65 ед. продукции, потребности четырех магазинов равны 110, 90, 130, 100 ед. продукции, тарифы перевозки в рублях за единицу продукции следующие:
Решение Проверка сбалансированности задачи показывает, что суммарный объем запасов Результаты нахождения опорного плана различными методами представлены в следующих таблицах. Транспортная таблица с опорным планом, найденным методом северо-западного угла.
Затраты на транспортировку при перемещении товара согласно полученному опорному плану равны:
Транспортная таблица с опорным планом, найденным методом минимального элемента.
Затраты на транспортировку при перемещении товара согласно полученному опорному плану равны:
Транспортная таблица с опорным планом, найденным методом Фогеля.
Затраты на транспортировку при перемещении товара согласно полученному опорному плану равны:
Отметим, что хотя введенные фиктивные строки или столбцы и считаются равноправными, но в случае задания в них нулевых тарифов эти тарифы не считаются как минимальные при построении опорных планов. Отметим, что опорный план, найденный методом северо-западного угла дает в общем случае наихудшее приближение, т.к. является «слепым», т.е. совершенно не зависит от тарифов. Метод минимального элемента предполагает перевозки в первую очередь в те пункты назначения, доставка в которые обойдется дешевле. В силу этого в общем случае суммарные затраты на транспортировку при применении этого метода несколько меньше. Метод Фогеля путем введения понятия штрафов выбирает для перевозок те маршруты, не выбрав которые мы могли бы увеличить расходы на транспорт в дальнейшем, из-за отсутствия выбора места назначения или места отправления. Начав решать транспортную задачу и получив опорный план, необходимо приступить непосредственно к оптимизации этого плана. Данная оптимизация может быть проведена методом потенциалов. Потенциал удобно воспринимать как себестоимость продукции. Задача Найдем оптимальное решение транспортной задачи опорный план которой представлен следующей транспортной матрицей:
Решение Проверяем условие Данцига: 7 = 5 + 3 – 1. Строим систему потенциалов. Задаем первой строке потенциал равный 100.
Через заполненные клетки определяем потенциалы первого, второго, и третьего столбцов. Далее через клетку (A2,B3) определяем потенциал второй строки, через клетку (A2,B4) определяем потенциал четвертого столбца. После чего через клетку (A3,B4) определяем потенциал третей строки и через клетку (A3,Bф) потенциал последнего столбца. Проверяем условие оптимальности. Оно не выполнено в клетках (A1,B4), где нарушение составляет 4, (A1,Bф), где нарушение составляет 4, (A2,B1), где нарушение составляет 6, (A2,B2), где нарушение составляет 6, (A2,Bф), где нарушение составляет 7 и (A3,B2), в которой нарушение составляет 2. Применим формальное правило улучшение плана для клетки (A2,Bф), т.к. в ней выявлено наибольшее нарушение.
Получили следующий вид транспортной матрицы:
Проверяем условие Данцига и строим систему потенциалов. Задаем первой строке потенциал, равный 100.
Проверяем условие оптимальности. Оно не выполнено в клетках (A1,B4), где нарушение составляет 4, (A2,B1), где нарушение составляет 6, (A2,B2), где нарушение составляет 6 и (A3,B2), в которой нарушение составляет 2. Применим формальное правило улучшения плана для клетки (A2,B1), т.к. в ней выявлено наибольшее нарушение.
Получили следующий вид транспортной матрицы:
Проверяем условие Данцига и строим систему потенциалов. Задаем второй строке потенциал равный 100.
Проверяем условие оптимальности. Оно не выполнено в клетках (A1,B4), где нарушение составляет 4, (A2,B2), где нарушение составляет 6 и (A3,B2), в которой нарушение составляет 2. Применим формальное правило улучшение плана для клетки (A2,B2), т.к. в ней выявлено наибольшее нарушение.
Получили следующий вид транспортной матрицы:
Проверяем условие Данцига и строим систему потенциалов. Задаем второй строке потенциал равный 100.
Проверяем условие оптимальности. Оно не выполнено в клетке (A1,B4), где нарушение составляет 4. Применим формальное правило улучшения плана для клетки (A1,B4).
Получили следующий вид транспортной матрицы:
Проверяем условие Данцига и строим систему потенциалов. Задаем второй строке потенциал равный 100.
Проверяем условие оптимальности. Оно не выполнено в клетках (A1,Bф), где нарушение составляет 2, (A3,B2), где нарушение составляет 5 и (A3,Bф), в которой нарушение составляет 2. Применим формальное правило улучшение плана для клетки (A3,B2), т.к. в ней выявлено наибольшее нарушение.
Получили следующий вид транспортной матрицы:
Проверяем условие Данцига и строим систему потенциалов. Задаем второй строке потенциал равный 100.
Проверяем условие оптимальности. Оно выполнено во всех клетках, следовательно получен оптимальный план перевозок. Суммарные затраты за транспортировку составит:
Отметим, что мы за нулевое приближение; мы выбрали опорный план, полученный методом «северо-западного угла», в силу чего нам и пришлось производить большое количество итераций. Если бы в качестве начального приближения был выбран опорный план, полученный методом «минимального элемента», то необходимое количество итераций было бы существенно меньше, а при выборе в качестве исходного опорного плана построенного «методом Фогеля», в данном примере вообще не пришлось бы производить итерации.
Отметим также, что при решении данного примера контуры которые мы строили, получались прямоугольные; это не всегда так, контуры могут быть различных форм, но строятся они всегда по одному принципу и в каждом случае могут быть получены единственным образом.
Системы массового обслуживания
ТЕОРИЯ
Основные параметры систем массового обслуживания
Этот параметр, как и
Итак, параметры Параметры, которые получим в дальнейшем, определяются взаимодействием обслуживающей системы и потока.
Заметим, что в результате расчета по формулам, Например: Важно понимать, что все эти величины носят средне статистический характер, то есть реализуются «в среднем» при продолжительном времени устойчивой работы системы массового обслуживания. Формулы определения параметров различаются для разных типов СМО (связи между параметрами, определенные по формулам (1)–(8) остаются справедливыми для всех СМО). Приведем полный набор формул для СМО четырех типов. Для удобства повторим формулы (1)–(8) в каждом случае. СМО с ограниченной очередью ( где где СМО с неограниченной очередью ( СМО с неограниченной очередью имеет стационарный режим работы только при условии При нарушении этого условия очередь неограниченно возрастает и стационарных значений параметров СМО определить не удается. При СМО без очереди (без ожидания, с отказами) ( Формулы для основных параметров данной СМО могут быть получены из формул для СМО с ограниченной очередью, если в них положить Задачи Задача 1. В пункте круглосуточной охраны 4 бригады. На пульте имеется 6 мест для запоминания поступившего вызова. В услугах бригады нуждается в среднем 4000 клиентов в месяц Бригада тратит на выезд в среднем 40 минут (выезд, проверка, задержание, возвращение). Найти параметры работы системы. Определить, сколько клиентов будут «ограблены» – получат отказ. Сколько времени «ожидает» приезда бригады грабитель? Определить, что оптимальнее с точки зрения для интенсификации работы системы, нанять еще одну бригаду или увеличить число мест на пульте до 10? Задача 2. На шоссе проверяет скорость патруль ГИБДД, состоящий из двух инспекторов. Инспектор оформляет протокол в среднем 10 минут. Инспекторы останавливают машину, если ожидают оформления не более трех машин. Статистически установлено, что за час на данном участке шоссе пытаются превысить скорость в среднем 70 водителей. Определить параметры работы системы. Найти процент оштрафованных нарушителей. Каково среднее время, которое тратит водитель в ожидании оформления протокола? Сколько, в среднем, машин ожидает оформления? Определить, что оптимальнее (с точки зрения наказания нарушителей), оформлять протокол в два раза быстрее или увеличить число инспекторов в два раза? Задача 3. В офисе туристической фирмы два многоканальных телефона. По первому, имеющему четыре канала, менеджеры дают информацию о предлагаемых круизах (назовем этих менеджеров и эти телефоны «рекламными»). По второму, с двумя каналами, проводится консультирование клиентов по правилам оформления документов (их назовем «оформительскими»). В час на фирму поступает в среднем 30 звонков с целью получить рекламную информацию и 10 звонков для получения консультации по оформлению. Один рекламный менеджер дает рекламную информацию в среднем за 10 минут, а оформительскую мог бы дать за 30 минут. Менеджер-оформитель отвечает на любой звонок в среднем 15 минут. Заметим, что если все телефоны заняты, то звонок, а следовательно и клиент теряются. Рассмотреть работу двух раздельных систем массового обслуживания и работу объединенной системы. Найти параметры работы задачи об офисе туристической фирмы. Дать трактовку всем найденным параметрам. Определить, выгодно ли объединение менеджеров. Задача 4. В лесу работает 5 лесников. Лесник производит задержание и оформление браконьера в среднем за 10 часов. За день (световой день летом равен 15 часов) пытаются вести незаконную охоту в среднем 9 человек. Очевидно, браконьеры не дожидаются «занятого» лесника. Определить, сколько браконьеров будет наказано, а какой процент окажется непойманными. Что эффективнее, взять лишнего лесника или ускорить работу лесников до 7,5 часов на браконьера? Задача 5. В диспетчерской крупной брокерской фирмы 4 диспетчера. Диспетчер передает информацию в среднем за 20 секунд. Вся поступающая информация неограниченно скапливается в единой базе до момента передачи. Вовремя (сразу) переданное сообщение приносит прибыль 2 руб. с сообщения, задержка в передаче сообщения приносит убытки в среднем по 50 копеек за минуту задержки. За час в диспетчерскую поступает в среднем 630 информационных сообщений. Зарплата диспетчера равна 15000 руб. в месяц. Рабочее время – 10 часов, в месяце 22 рабочих дня. Определить параметры работы системы и прибыль компании. Определить оптимальное число диспетчеров с точки зрения получения прибыли.
Решения Решение задачи 1. Входные параметры исходной задачи: В результате решения получаем следующие значения параметров: Таким образом, будет ограблено 308 клиентов в месяц (очень много!). Грабитель «ожидает» приезда бригады в среднем 21,6 минут (тоже очень много). При При Очевидно, что наем еще одной бригады намного эффективнее наращивания очереди. Решение задачи 2. На шоссе проверяет скорость патруль ГИБДД, состоящий из двух инспекторов. Инспектор оформляет протокол в среднем 10 минут. Инспекторы останавливают машину, если ожидают оформления не более трех машин. Статистически установлено, что за час на данном участке шоссе пытаются превысить скорость в среднем 70 водителей. Входные параметры исходной задачи: В результате решения получаем следующие значения параметров: Процент оштрафованных нарушителей равен При При Очевидно, что в обоих случаях интенсивность практически совпадает (система работает близко к максимальному пределу скорости). Незначительно интенсивнее увеличить число инспекторов. Если сравнивать по времени ожидания, то за счет большей скорости оформления оно заметно ниже во втором случае. Решение задачи 3. Схема для систем в отдельности не представляет труда. Вычислим только интенсивности работы каждого менеджера.
Найдем среднюю интенсивность менеджера в объединенной системе. Введем обозначения:
Среднее время, затрачиваемое «рекламщиком» на звонок из общего потока равно:
Интенсивность работы «рекламщика» равна Среднее время, затрачиваемое «оформителем» на звонок из общего потока равно:
Интенсивность работы «оформителя» равна То есть все менеджеры начинают работать с одинаковой интенсивностью. Очевидно, что и интенсивность работы «объединенного» менеджера
Запишем полученные нами исходные данные для каждой СМО отдельно в таблицу для лучшего восприятия.
А) Система рекламных менеджеров. Таким образом, будет обслужено 18 рекламных звонков в час. В среднем один рекламный менеджер из четырех постоянно не работает, то есть менеджер занят работой 75% рабочего времени. Б) Система менеджеров по оформлению. Таким образом, будет обслужено 5,3 звонков-консультаций по оформлению в час. В среднем работает только 1,32 менеджера из двух, то есть менеджер занят работой Всего двумя системами будет обслужено В) Объединенная система. Таким образом, будет обслужено всего 20,62 звонков в час. В среднем менеджер будет занят работой В объединенной системе при значительно большей загрузке менеджеров получаем сильное снижение общей интенсивности работы. Очевидно, объединение не выгодно! Решение задачи 4. Решение (лучше решать задачу по очереди, для каждой СМО отдельно).
Из результатов расчета осредненных параметров работы системы видно, что оптимальнее увеличить интенсивность работы каждого лесника. Решение задачи 5. Средний доход с одного сообщения равен:
где время ожидания Общий доход за месяц равен:
Месячные расходы системы равны суммарной зарплате
Прибыль системы равна разнице дохода и расхода:
Определяем параметры работы системы:
Доход равен:
Расход равен:
Прибыль равна:
Попробуем изменить число диспетчеров. Уменьшать число диспетчеров нельзя – нарушится условие Рассмотрим Доход равен:
Расход равен:
Прибыль равна:
Прибыль увеличилась. Рассмотрим Доход равен:
Расход равен:
Прибыль равна:
Прибыль меньше, чем при пяти диспетчерах. При незначительном увеличении дохода заметно возросли расходы. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ Во многих ситуациях, встречающихся в промышленности, сельском хозяйстве, экономической деятельности и т.д., задача оптимизации плана некоторых экономико-производственных действий может быть записана в виде линейных уравнений и неравенств с линейным же, относительно искомых, определяющих этот план, переменных целевой функцией. К задачам этого же вида сводятся очень многие задачи оптимизации и принятия решений из некоторых других самостоятельных направлений прикладной математики. Соответственно возникает потребность в математической теории, позволяющей решать такие задачи. Такая теория существует и называется линейным программированием. Данное название возникло в 30-е годы, когда представления о программировании на компьютере ещё не существовало. Под программированием фактически подразумевается планирование. Однако, этот термин уже укоренился, и не только в линейном случае. Имеются так же и такие названия математических теорий решения задач оптимизации, как нелинейное программирование и динамическое программирование. В общем виде задача линейного программирования (ЛП) заключается в отыскании таких неотрицательных чисел x1, x2..., хn которые максимизируют (минимизируют) линейную функцию:
при условии выполнения системы неравенств:
При описании реальной ситуации с помощью линейной модели следует проверять наличие у модели таких свойств, как пропорциональность и аддитивность. Пропорциональность означает, что вклад каждой переменной в целевую функцию (ЦФ) и общий объем потребления соответствующих ресурсов должен быть прямо пропорционален величине этой переменной. Например, если продавая какой либо товар в общем случае по одной цене рублей, фирма будет делать скидку при определенном уровне закупки, то будет отсутствовать прямая пропорциональность между доходом фирмы и величиной переменной. Т.е. в разных ситуациях одна единица товара будет приносить разный доход. Аддитивность означает, что ЦФ и ограничения должны представлять собой сумму вкладов от различных переменных. Примером нарушения аддитивности служит ситуация, когда увеличение сбыта одного из конкурирующих видов продукции, производимых одной фирмой, влияет на объем реализации другого. При решении задачи линейного программирования целесообразно бывает введение следующих определений. Допустимое решение – это совокупность чисел (план) Оптимальное решение – это план, при котором ЦФ принимает свое максимальное (минимальное) значение. Прежде чем построить математическую модель задачи, т.е. записать ее с помощью математических соотношений, необходимо четко разобраться с экономической ситуацией, описанной в условии. Для этого необходимо с точки зрения экономики, а не математики, ответить на следующие вопросы: 1) Что является искомыми величинами задачи? 2) Какой параметр задачи служит критерием эффективности (оптимальности) решения? (это может быть: прибыль, время, количество отходов и т.д.) 3) В каком направлении должно изменяться значение этого параметра (к max или к min) для достижения наилучших результатов? 4) Какие условия в отношении искомых величин и ресурсов задачи должны быть выполнены? Эти условия устанавливают, как должны соотноситься друг с другом различные параметры задачи, например, количество ресурса, затраченного при производстве, и его запас на складе; количество выпускаемой продукции и емкость склада, где она будет храниться; количество выпускаемой продукции и рыночный спрос на эту продукцию и т.д. Только после экономического ответа на все эти вопросы можно приступать к записи этих ответов в математическом виде, т.е. к записи математической модели. а) Искомые величины являются переменными задачи, которые как правило обозначаются малыми латинскими буквами с индексами, например, однотипные переменные удобно представлять в виде б) Цель решения записывается в виде целевой функции, обозначаемой, например, в) Условия, налагаемые на переменные и ресурсы задачи, записываются в виде системы равенств или неравенств, т.е. ограничений. Левые и правые части ограничений отражают способ получения (расчет или численные значения из условия задачи) значений тех параметров задачи, на которые были наложены соответствующие условия. В процессе записи математической модели целесообразно указывать единицы измерения переменных задачи, целевой функции и всех ограничений. Задача Фабрика производит два вида красок: первый – для наружных, а второй – для внутренних работ. Для производства красок используются два ингредиента: А и В. Известны расходы ингредиентов А и В на 1 т соответствующих красок и максимально возможные суточные запасы этих ингредиентов на складе. Данные по расходам ингредиентов на краски первого и второго вида представлены в таблице.
Изучение рынка сбыта показало, что суточный спрос на краску 2-го вида никогда не превышает спроса на краску 1-го вида более, чем на 1 т. Кроме того, установлено, что спрос на краску 2-го вида никогда не превышает 2 т в сутки. Оптовые цены одной тонны красок равны: 3 тыс. руб. для краски 1-го вида; 2 тыс. руб. для краски 2-го вида. Необходимо построить математическую модель, позволяющую установить, какое количество краски каждого вида надо производить, чтобы доход от реализации продукции был максимальным. Решение В задаче требуется установить, сколько краски каждого вида надо производить. Поэтому искомыми величинами, а значит, и переменными задачи являются суточные объемы производства каждого вида красок:
В условии задачи сформулирована цель – добиться максимального дохода от реализации продукции. Т.е. критерием эффективности служит параметр суточного дохода, который должен стремиться к максимуму. Чтобы рассчитать величину суточного дохода от продажи красок обоих видов, необходимо знать объемы производства красок, т.е.
Возможные объемы производства красок · количество ингредиентов А и В, израсходованное в течение суток на производство красок обоих видов, не может превышать суточного запаса этих ингредиентов на складе; · согласно результатам изучения рыночного спроса суточный объем производства краски 2-го вида может превышать объем производства краски 1-го вида, но не более, чем на 1 т краски; · объем производства краски 2-го вида не должен превышать 2 т в сутки, что также следует из результатов изучения рынков сбыта; · объемы производства красок не могут быть отрицательными. Таким образом, все ограничения задачи делятся на 3 группы, обусловленные: 1) расходом ингредиентов; 2) рыночным спросом на краску; 3) неотрицательностью объемов производства. Ограничения по расходу любого из ингредиентов имеют следующую содержательную форму записи:
Запишем эти ограничения в математической форме. Левая часть ограничения – это формула расчета суточного расхода конкретного ингредиента на производство красок. Так из условия известен расход ингредиента А на производство 1 т краски 1-го вида (1 т ингр. А) и 1 т краски 2-го вида (2 т ингр. А). Тогда на производство Правая часть ограничения – это величина суточного запаса ингредиента на складе, например, 6 т ингредиента А в сутки. Таким образом, ограничение по расходу А имеет вид
Аналогична математическая запись ограничения по расходу В
Примечание. Следует всегда проверять размерность левой и правой частей каждого из ограничений, поскольку их несовпадение свидетельствует о принципиальной ошибке при составлении ограничений. Ограничение по суточному объему производства краски 1-го вида по сравнению с объемом производства краски 2-го вида имеет содержательную форму
и математическую форму
Ограничение по суточному объему производства краски 1-го вида имеет содержательную форму
и математическую форму
Неотрицательность объемов производства задается как
Таким образом, математическая модель этой задачи имеет вид
Для задач линейного программирования, содержащих только две переменные |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2019-06-10; Просмотров: 448; Нарушение авторского права страницы
, удовлетворяющих ограничениям исходной задачи.
. Математическая формула ЦФ 
– суточный объем производства краски 1-го вида, [т краски/сутки];
– суточный объем производства краски 2-го вида, [т краски/сутки].
тыс. руб. в сутки, а от продажи краски 2-го вида – 
тыс. руб. в сутки. Поэтому запишем ЦФ в виде суммы дохода от продажи красок 1-го и 2-го видов (при допущении независимости объемов сбыта каждой из красок)
[тыс. руб./сутки],
.
.
т краски 1-го вида и 
т краски 2-го вида потребуется 
т ингр. А.
.
.
.
.
.
и 
применим графический способ решения. Этот способ основан на том факте, что в случае двух переменных множество допустимых решений можно построить на двухмерной плоскости.
;
;
;
;
.
.
; сдвигая прямую, перпендикулярную построенному вектору (от начала к концу), найдем точку, являющуюся последней в пересечении сдвигаемой прямой с ОДР (это точка Е), ее координаты, найденные из решения системы соответствующих уравнений, будут являться оптимальным планом, а значение целевой функции в ней будет max.
, т.к. в этом случае становиться возможным выразить 
, а в силу того что перед нами ставится задача максимизировать L, то эта задача достигается в случае, когда все переменные, присутствующие в данном уравнении, принимают нулевые значения (т.к. переменные не отрицательны по условию).
используем правило № 4. Подставляем в левую часть ограничения (4) координаты точки Е, получаем 
понимается такая игра двух игроков, при которой каждый игрок имеет конечное число возможных ходов – чистых стратегий. При этом выигрыш одного игрока и проигрыш другого при применении ими определённых чистых стратегий выражается числом. Перечисленные условия позволяют записать стратегии в матрицу
(1)
– равен выигрышу первого (будем обозначать его А) и проигрышу второго (игрока В) при применении ими i-й и j-й чистых стратегий соответственно.
(3)
называется ценой игры, элемента 
соответствующий равенству, называют седловой точкой.
для игрока В – 
. Причём, такое решение обладает свойством устойчивости в том смысле, что если один из игроков применяет свою оптимальную стратегию, то любое отклонение другого игрока от оптимальной стратегии может оказаться не выгодным для него.
, то есть игрок А обеспечивает себе выигрыш , равный одному из элементов 
строки, причём, элемент в 
столбце наименьший среди них 
. И если игрок В выберет j-ю стратегию отличную от 
, то он проиграет сумму, равную 
, а игрок А соответственно выиграет её. Аналогичные рассуждения показывают не выгодность стратегии, отличной от оптимальной, для игрока А, когда В придерживается своей оптимальной стратегии.
игроком 
и 
игроком 
, при этом цена игры V = 3.
. В этом случае говорят, что i – я стратегия первого игрока доминирует над его j – й стратегией. Если каждое неравенство выполняется как строгое, то говорят, что одна стратегия строго доминирует над другой. В любом случае из двух стратегий первый игрок предпочтет доминирующую, поскольку при использовании доминируемой стратегии его выигрыш по меньшей мере не увеличится. В этом случае можно принять 
.
. Для второго игрока, как известно, более выгодной является стратегия, дающая меньший проигрыш, поэтому говорят, что j - я стратегия доминирует над l - й. Если попарные неравенства являются строгими, то говорят, что одна стратегия строго доминирует над другой. При этом, естественно, 
.
.
.
.
соответственно 1 – го и 2 – го игроков в матричной игре 
с ценой v будут оптимальными и в матричной игре 
с ценой 
, где 
.
.
, если другой игрок не выходит за пределы своих активных стратегий (т.е. пользуется любой из них в чистом виде или смешивает их в любых пропорциях).
. В этом случае говорят, что i – я стратегия первого игрока доминирует над его j – й стратегией. Если каждое неравенство выполняется как строгое, то говорят, что одна стратегия строго доминирует над другой. В любом случае из двух стратегий первый игрок предпочтет доминирующую, поскольку при использовании доминируемой стратегии его выигрыш по меньшей мере не увеличится. В этом случае можно принять 
. Для второго игрока, как известно, более выгодной является стратегия, дающая меньший проигрыш, поэтому говорят, что j - я стратегия доминирует над l - й. Если попарные неравенства являются строгими, то говорят, что одна стратегия строго доминирует над другой. При этом, естественно, 
.
.
.
соответственно 1 – го и 2 – го игроков в матричной игре 
с ценой v будут оптимальными и в матричной игре 
с ценой 
, где 
.
примем b=10, C=-6 . Применим преобразование bA+ c, тогда получим игру с теми же оптимальными стратегиями, но с другой эквивалентной матрицей: 
.
чаще всего встречается в лучших результатах. Она и будет записана нами в ответ как самая оптимальная.
– привлечь к выполнению работ только финансовых консультантов.
руб.
. В случае, когда суммарные запасы превышают суммарные потребности, необходим дополнительный фиктивный (реально не существующий) пункт потребления, который будет формально потреблять существующий излишек запасов, т.е.: 
больше суммарного объема потребностей 
, т.е. введение необходимо введение фиктивного столбца 
, после чего задача становится сбалансированной 
.
.
.
.
– число каналов обслуживания (мастеров, врачей, барменов и т.п.). Измеряется в «штуках». Например, в парикмахерской работает 4 мастера, значит 
.
– максимальная длина очереди (максимальное количество мест для ожидания обслуживания). В СМО без очереди ( 
) и с неограниченной очередью ( 
) этот параметр явно не участвует. Измеряется в «штуках». Например, в парикмахерской есть 3 кресла для ожидания, тогда 
– среднее время обслуживания одной заявки одним каналом (среднее время, которое тратит мастер, врач и т.п. на одного клиента, пациента; среднее время, которое тратится станцией техобслуживания на один автомобиль и т.д.). Измеряется в единицах времени. Пример: парикмахер обслуживает клиента в среднем за 40 минут: 
мин. Этот параметр зависит только от свойств системы массового обслуживания и не зависит от входящего потока (например, если большинство клиентов уедет в отпуск, скорость работы парикмахера не поменяется).
– интенсивность обслуживания одним каналом (среднее число заявок, которые обслуживает один канал за единицу времени; число заказов, обслуживаемых за единицу времени). Измеряется в «штуках» за единицу времени. Связан со среднем временем обслуживания соотношением:
.
, зависит только от свойств системы массового обслуживания и не зависит от входящего потока. Для нашего примера: интенсивность работы парикмахера 
клиента за минуту. Важно следить, за какую единицу времени происходит обслуживание. Нужно, чтобы 
и 
клиентов в день.
человек в раб. день. Этот параметр зависит только от свойств входящего потока и не зависит от свойств самой системы массового обслуживания (например, при болезни парикмахера поток клиентов, приходящих на обслуживание, не меняется).
– максимальное время ожидания требованием начала обслуживания (время, после которого портится не обслуженный продукт, уходит нетерпеливый клиент, станивится неактуальным выполнение заказа и т.п.). Измеряется в единицах времени. СМО в этом случае носят название систем массового обслуживания с ограниченным временем ожидания. Необходимо, чтобы время 
и 
– интенсивность нагрузки. Безразмерная величина. До вычисления 
(1)
– вероятность того, что занято ровно 
каналов обслуживания или доля общего времени работы СМО в течении которого заняты ровно 
– доля времени, когда все каналы свободны. Безразмерная величина, находится в диапазоне от 0 до 1. Является промежуточной величиной расчета всех СМО. Через нее выражаются многие остальные параметры. Безразмерная величина, находится в диапазоне от 0 до 1.
– вероятность того, что все каналы обслуживания заняты (заняты все мастера, врачи и т.д.). Безразмерная величина, находится в диапазоне от 0 до 1. Иначе говоря, это доля времени, в которое поступившая заявка попадает в очередь или получает отказ, если очереди нет или она максимально заполнена.
– вероятность отказа в обслуживании или доля из общего числа требований, которым будет отказано в обслуживании из-за занятости всех каналов и мест ожидания или из-за превышения максимального времени ожидания. Безразмерная величина, находится в диапазоне от 0 до 1.
– вероятность обслуживания или доля из общего числа требований, которые будут обслужены. Безразмерная величина, находится в диапазоне от 0 до 1. Еще одно название – относительная эффективность обслуживания.
(2)
– абсолютная эффективность обслуживания (абсолютная пропускная способность). Количество требований, которые будут обслужены в единицу времени (число обслуженных за день, за час, за минуту заявок, клиентов и т.п.). Измеряется в «штуках».
(3)
– абсолютная эффективность отказа. Количество требований, получивших отказ в обслуживании в единицу времени (число клиентов, заявок и т.п., которым будет отказано в течении дня, часа, минуты). Измеряется в «штуках».
(4)
– среднее число занятых каналов обслуживания (число работающих мастеров, занятых телефонов и т.п.). Измеряется в «штуках».
(5)
– средняя длина очереди (среднее число клиентов, заявок, ожидающих начала обслуживания в очереди). Измеряется в «штуках».
– среднее количество требований в системе (среднее число клиентов, заявок, ожидающих начала обслуживания в очереди и обслуживаемых в СМО). Измеряется в «штуках».
(6)
– среднее время, которое проводит требование в очереди (общее время, которое, в среднем, один клиент проводит в ожидании начала обслуживания и во время обслуживания). Измеряется в единицах времени. Иногда обозначается 
или 
.
(7)
– среднее время, которое проводит требование в системе (время, которое, в среднем, один клиент проводит в ожидании начала обслуживания). Измеряется в единицах времени. Иногда обозначается 
или 
.
(8)
).
, (9)
(10)
, (11)
– факториал числа 
.
(12)
(13)
(14)
(15)
(17)
(18)
(19)
(20)
(21)
.
.
, (22)
(23)
(24)
(26)
(27)
(28)
(29)
(31)
(32)
).
, (33)
(34)
(35)
(36)
(37)
(38)
(39)
(40)
(41)
(42)
(43)
;
;
;
;
;
;
;
;
;
;
;
;
;
;
и остальных неизменных параметрах имеем:
; 
.
и остальных неизменных параметрах имеем:
; 
.
;
;
;
;
;
; (Нужна именно такая точность!!!)
;
;
;
;
, (практически все время инспекторы заняты);
;
;
;
(эффективность работы системы мала). Среднее время, которое тратит водитель в ожидании оформления протокола равно 19 минут. В среднем 3,8 машин ожидает оформления.
; 
; 
и остальных неизменных параметрах имеем:
; 
; 
, 
.
– долю звонков с целью получить рекламу,
– доля звонков с целью получить консультацию по оформлению; 
– доля «рекламных» менеджеров,
– доля «оформителей»;
– время, которое тратит «рекламщик» на «рекламный» звонок,
– время, которое тратит «рекламщик» на «оформительский» звонок.
– время, которое тратит «оформитель» на «оформительский» звонок,
– время, которое тратит «оформитель» на «рекламный» звонок.
.
.
. Тот же результат получим по общей формуле:
.
;
;
;
;
;
;
;
;
;
;
;
;
;
;
рабочего времени.
.
;
;
;
;
;
;
;
рабочего времени.
10 ч.)
, наруш./мес.
, наруш./мес.
, час
,
диспетчеров:
;
;
.
, значит система допускает анализ стационарного режима.
;
;
;
;
;
;
.
;
. Тогда после вычислений получим:
;
