какие решения математических моделей называются оптимальными

Оптимизационные модели

4.1. Постановка оптимизационной задачи

Принятию любого экономического или финансового решения предшествует перебор и оценка вариантов. Экономико-математические задачи, цель которых состоит в нахождении наилучшего (оптимального) с точки зрения некоторого критерия или критериев варианта использования имеющихся ресурсов (труда, капитала и пр.), называются оптимизационными [18, 19].

Типы оптимизационных задач в экономике:

В общем виде задача линейного программирования ЗЛП ставится следующим образом: найти вектор , максимизирующий (минимизирующий) линейную форму , удовлетворяющий условиям:

( 4.1)

( 4.2)

где — заданная функции, — некоторые действительные числа.

Приведем примеры экономико-математического моделирования оптимизационных задач средствами Mathcad.

4.2.Оптимальное планирование выпуска продукции

Определение переменных. Введем обозначения:

–видов продукции, – текущий номер вида продукции.

— прибыль от реализации единицы -го вида продукции.

— переменные затраты производства единицы -го вида продукции

— запасы -го ресурса – текущий номер вида ресурса, — количество ресурсов.

— норма затрат го ресурса для производства -го вида продукции

– требуемое количество выпуска продукции каждого вида по плану,

Выходные показатели – суммарная прибыль ,

Управляемые переменные. — искомый объем продукции -го вида.

( 4.3)

( 4.4)

Ограничения. условия, налагаемые на данные задачи, определяющие исследуемую величину, которая оптимизируется. Различают три типа ограничений:

– планируемые затраты ресурса для производства продукции ,

– планируемые затраты ресурса на производство всех видов продукции,

— условие ограниченности ресурсов

— условие ограниченности по плану

технологические соотношения между группами управляемых переменных, здесь

Уравнения. В результате имеем систему уравнений, которую надо решить.

( 4.5)

Решение, если получено, представляется в виде оптимального решения. Это:

количество управляемых переменных, не равных нулю,

числовые значения управляемых переменных,

полученное значение целевой функции

Рассмотрим решение модели на примере следующей задачи.

Источник

Графический метод оптимизации линейных моделей

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

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

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

Параметры задач ограничиваются такими предельными показателями:

Алгоритм поиска оптимальных решений включает в себя несколько этапов:

область переменных ;

область исходных нормированных коэффициентов ;

область целевых коэффициентов ;

область задания ресурсов ;

область целевой функции .

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

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

Таким образом, в диалоговом окне оптимизационной программы » Поиск решения» мы должны задать следующий целевой алгоритм :

— целевая функция равна произведению вектора искомых значений переменных на вектор целевых коэффициентов

— нормированных коэффициентов на вектор искомых значений переменных не должен превышать значения заданного вектора ресурсов

— значения переменной должны находиться в заданных пределах число исходных элементов системы

— число исходных элементов системы

— число заданных видов ресурсов

Отладка решения необходима в случае, когда программа выдает сообщение об отрицательных результатах (рисунок 1.7):

При отладке рекомендуется возвращаться к заданию новых начальных условий:

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

Экономический анализ ставит перед собой следующие цели [2]:

Возможные методы анализа представлены в схеме на рисунке 1.8.

После получения оптимального решения проводится его анализ по полученным отчетам. Анализ устойчивости — изучение влияния изменений отдельно взятых параметров модели на показатели оптимального решения. Анализ пределов — анализ допустимых изменений в оптимальном плане, при котором план остается оптимальным.

Учитывая ответственность принятия экономического управленческого решения, руководитель должен убедиться, что полученный оптимальный план является единственно верным. Для этого надо на основе модели получить ответы на следующие вопросы:

Анализ с целью ответа на первый вопрос называется вариантным анализом; анализ с целью ответа на второй вопрос называется решениями по заказу.

Вариантный анализ бывает следующих видов:

После проведения анализа следует представить результаты в графической форме и составить отчет с рекомендациями о принятии решения с учетом конкретной экономической ситуации.

Ключевые термины

Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

Математическая модель — приближенное описание объекта, выраженное с помощью математической символики, отражающее количественные соотношения между его элементами.

Симплекс-метод — вычислительная процедура, основанная на принципе последовательного улучшения решений.

Матрица нормированных коэффициентов — постоянные параметры объекта моделирования.

Ресурс— количественная мера возможности выполнения какой-либо деятельности; условия, позволяющие с помощью определённых преобразований получить желаемый результат.

Область допустимых решений — все решения, которые удовлетворяют заданным ограничениям задачи.

Оптимальное решение — допустимое решение, для которого значение целевой функции максимально.

Анализ решения — заключительный этап математического моделирования экономических процессов.

Краткие итоги

Графическое решение задач оптимизации удобно применять в случае двух искомых переменных. Тогда за декартовые координаты и принимают значения этих переменных. Если по физическому смыслу переменные могут быть только положительными, то решение ищется только в первом квадранте. Линейные ограничения на заданные ресурсы выражаются в виде прямых линий. Эти линии вместе с осями координат ограничивают область допустимых решений в виде выпуклого многоугольника. Оптимальное решение с экстремумом целевой функции находится в одной из вершин многоугольника. Координаты этой вершины являются искомыми значениями переменных.

Источник

Общая математическая модель формирования оптимальных решений

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

Обозначим через a, b, c вектора соответствующих размерностей, описывающие количественные характеристики неконтролируемых факторов.

Для оценки эффективности различных вариантов решений будем использовать специальным образом сформированную функцию:

которая называется критерием оптимальности решений или целевой функцией задачи ПР.

Тогда выбор оптимального решения Х_опт будем осуществлять, исходя из требования .

Множество Х должно быть допустимым с точки зрения учета условий принятия решений (ограничений).

Пусть ЛПР обладает для достижения цели вектором ресурсов b. Представим в виде вектор-функции j(а, Х) фактический расход ресурсов при использовании вектора решений Х и вектора некоторых факторов а.

Тогда j(а, Х) £ b есть ограничение.

Во многих задачах ПР учитывается условие Х ³0.

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

(4.1)

(4.2)

(4.3)

Постановка задачи в этом случае выглядит следующим образом:

Найти значение вектора Х, доставляющего максимум (минимум) критерию оптимальности решений (4.1) и удовлетворяющего при этом условиям (4.2) и (4.3).

Математическая модель ПР (4.1) – (4.3) является однокритериальной моделью.

Если ЛПР должен учитывать m целей, то, формализуя их в виде критериев оптимальности, получим:

(4.4)

Математическая модель (4.4), (4.2), (4.3) является многокритериальной моделью.

В реальных задачах ПР ограничения вида (4.2) могут включать в себя как неравенства вида «£», «³», «=», так и их различные сочетания.

4.3. Построение и решение оптимизационной
задачи принятия решения
(Задача о баке)

Пусть требуется выбрать геометрические размеры цилиндрического бака объемом V из условия минимального расхода материала на его изготовление.

Для построения математической модели введем в рассмотрение вектор проектных решений Х = (r, h), где 2r, h – диаметр и высота бака (Рис. 4.3).

Если предположить, что бак изготавливается сваркой из трех деталей, то расход материала при произвольном векторе решений Х будет равен площади поверхности бака:

. (4.5)

Согласно условиям задачи выражение (4.5) является целевой функцией (критерий оптимальности проектных решений).

Условие того, что бак должен иметь объем заданного значения V, представим в виде:

На компоненты вектора решений X необходимо наложить дополнительные условия:

Выражения (4.5) – (4.7) описывают нелинейную однокритериальную модель формирования оптимальных решений, при n = 2, m = 1.

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

, (4.8)

где с – затраты времени на сварку единицы длины.

Выражения (4.5), (4.8), (4.6), (4.7) описывают двухкритериальную нелинейную модель формирования оптимальных решений.

При построении математической модели в этой задаче принятия решений были использованы известные геометрические закономерности.

Аналитическое решение задачи ПР возможно, если соответствующая математическая модель включает в себя ограничения типа равенств, то есть имеет вид:

Такие задачи решаются обычно классическими методами условной оптимизации, которые предусматривают построение функции Лагранжа вида

(4.9)

Точки экстремума этой функции определяются из решения системы уравнений вида

(4.10)

Решая эту систему, получим решение вида

(4.11)

Используем этот метод для решения однокритериальной задачи (4.8), (4.6) (без учета (4.5), (4.7)).

Функция Лагранжа имеет вид:

.

Система уравнений (4.17) относительно переменных r, h, l:

Имеем систему алгебраических уравнений, решая которую, получим значения неизвестных r, h (l находить необязательно):

; .

Таким образом, оптимальные размеры бака, найденные с помощью аналитического метода условной оптимизации, не зависят от затрат времени с на сварку единицы длины, но зависят от требуемого объема бака V. Требование (4.8) при этих значениях r и h выполняется, то есть трудоемкость будет минимальной.

Недостатками этого метода являются:

1) Не учитываются в явном виде условия неотрицательности (4.7).

2) Система уравнений (4.10) позволяет получить решение в форме (4.11) только для простых функций (4.5), (4.6).

Контрольные вопросы к лекции 11

1. Что включает в себя простейшая схема принятия решений?

3. Что такое критерий оптимальности?

4. Что такое однокритериальная ЗПР?

5. Что такое многокритериальная ЗПР?

6. Возможно ли получение единственного оптимального решения в многокритериальных задачах?

7. Напишите общий вид математической модели формирования оптимальных решений.

8. Сформулируйте задачу принятия решений.

9. Запишите критерий минимального расхода материала для задачи о баке.

10. Запишите критерий минимальной трудоемкости для задачи о баке.

11. Запишите общий вид функции Лагранжа.

12. Перечислите недостатки аналитического метода условной оптимизации.

4.4. Многокритериальные задачи принятия решений

Во многих задачах принятия решений имеется несколько целей, которые хочет достичь ЛПР. Такие задачи сводятся к многокритериальным задачам вида:

Наибольшее распространение на практике решения таких задач получил подход, связанный с работами итальянского математика-экономиста Викторио Парето. Он обеспечивает ЛПР возможность гибкого принятия решений. При оптимизации по Парето строится множество «неулучшаемых» решений, изменение каждого из которых ухудшает значение целевых функций f₁(X), f₂(X),…, f_k(X).

Рассмотрим наиболее распространенную на практике двухкритериальную задачу оптимизации вида:

(4.12)

(4.13)

Условия (4.13) определяют множество допустимых решений и образуют на плоскости х₁Ох₂ некоторую область, каждой точке С которой соответствует точка С* в пространстве значений критериев W₁OW₂ (Рис. 4.4). Ее координаты вычисляются по формулам (4.12) при х₁ = х₁ С ; х₂ = х₂ С :

.

Рассмотрим в множестве значений критериев четыре точки A*, B*, D* и С*
(см. рис. 4.4). Точка А* является оптимальной для критерия W₂ = f(x₁,x₂), так как в этой точке критерий W₂ имеет максимальное значение. Аналогично точка В* является оптимальной для критерия W₁ = f(x₁, x₂). Точка С* является «заведомо плохой» точкой, она не является оптимальной ни для одного критерия, так как в области значений критериев можно найти «более лучшую» точку D* такую, что Для точек A*, B*, D* более «лучших» точек в пространстве значений критериев не существует. Такие точки составляют множество решений, оптимальных по Парето в пространстве значений критериев. В нашем случае это точки кривой A*D*B*. Для выделения «лучших» (неулучшаемых) точек используется понятие конуса K_i с вершиной в точке ( )
(Рис. 4.5). Уравнения этого конуса имеют вид:

Правило выделения «лучших» точек:

Если в конусе K_i лежит хотя бы одна точка ( ), то она является более предпочтительной, чем точка ( ) (см. рис. 4.5).

Тогда все точки множества значений критериев, для которых соответствующие конусы являются пустыми, являются парето-оптимальными решениями в пространстве значений критериев.

Для нашего примера конусы, построенные во всех точках кривой A*D*B*
(см. рис. 4.4), являются пустыми. Строя обратное отображение этих точек в пространство решений Х, можно получить множество искомых решений (кривая АВ на рис 4.4), оптимальных по Парето. Такое множество называется множеством компромиссов, множеством эффективных точек или множеством Парето. Построив множество компромиссов, ЛПР выбирает в нем из неформальных соображений некоторую точку, которая является наилучшим компромиссом, по мнению ЛПР.

4.5. Построение решений, оптимальных по Парето
(Двухкритериальная задача о баке)

Вернемся к рассмотренной в п. 4.5 задаче о баке, описанную формулами (4.5) – (4.8), и попробуем найти паретооптимальное ее решение. Для этого введем параметры
a₁ > 0 и a₂ > 0, удовлетворяющие условию a₁ + a₂ = 1, и построим линейную свертку критериев (4.5) и (4.8):

. (4.14)

Положим a₁ = 1, тогда a₂ обращается в ноль, свертка (4.14) принимает вид
F(X) = S(X) и задача превращается в однокритериальную. Решив эту задачу, найдем оптимальную точку X_S для обеспечения минимального расхода материала. Теперь положим
a₁ = 0, тогда a₂ = 1, свертка (4.14) примет вид F(X) = T(X). Решив эту однокритериальную задачу, найдем оптимальную точку X_T, обеспечивающую минимальную трудоемкость изготовления бака. Если провести аналогию с рис. 7.4, то X_S соответствует точке А, X_T соответствует точке В. Чтобы определить промежуточные точки (остальные компромиссные решения), введем обозначение a = a₁. Тогда a₂ = 1 – a. Формула (4.14) примет вид . Или:

.

Функция Лагранжа запишется в виде

.

Распишем функцию Лагранжа подробнее:

.

Чтобы найти минимум функции Лагранжа, нужно взять от нее производные по искомым переменным r, h, l и приравнять их к нулю.

(4.15)

Получили систему трех алгебраических уравнений, решив которую найдем зависимость r, h, l от a. Задавая a от 0 до 1, получим множество решений, оптимальных по Парето. Поскольку аналитически решить систему (4.15) довольно сложно, можно воспользоваться любым численным методом, задавая предварительно значения a с любым приемлемым шагом.

Для примера эта задача была решена с шагом 0,1 в пакете MathCad. На рис. 4.6 показано полученное множество паретооптимальных решений.

ЛПР выбрал из этого множества точку при a = 0,4, при котором S = 2601; T = 802;
r = 10,44; h = 29,2. Эта точка устроила его потому, что при дальнейшем увеличении a
S уменьшается уже незначительно и Т имеет наименьшее значение из всех последующих.

Контрольные вопросы к лекции 12

1. Какие решения называются паретооптимальными?

2. Сформулируйте правило выделения лучших точек.

3. Что такое множество компромиссных решений?

4. Как получить множество компромиссных решений?

5. Запишите функцию Лагранжа для двухкритериальной задачи о баке.

6. Как найти минимум функции Лагранжа?

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ И ВСЕОБЩАЯ КОМПЬЮТЕРИЗАЦИЯ ИЛИ ИМИТАЦИОННЫЕ МОДЕЛИ

Сейчас, когда в стране происходит чуть ли не всеобщая компьютеризация, от специалистов различных профессий приходится слышать высказывания: «Вот внедрим у себя ЭВМ, тогда все задачи сразу же будут решены». Эта точка зрения совершенно не верна, сами по себе ЭВМ без математических моделей тех или иных процессов ничего сделать не смогут и о всеобщей компьютеризации можно лишь мечтать.

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

Прежде всего, ответим на вопрос: что такое модель?

Модель – это материальный или мысленно представленный объект, который в процессе познания (изучения) замещает оригинал, сохраняя некоторые важные для данного исследования типичные свойства.

Хорошо построенная модель доступнее для исследования – нежели реальный объект. Например, недопустимы эксперименты с экономикой страны в познавательных целях, здесь без модели не обойтись.

Резюмируя сказанное можно ответить на вопрос: для чего нужны модели? Для того, чтобы

Что положительного в любой модели? Она позволяет получить новые знания об объекте, но, к сожалению, в той или иной степени не полна.

Модель сформулированная на языке математики с использованием математических методов называется математической моделью.

Исходным пунктом ее построения обычно является некоторая задача, например экономическая. Широко распространены, как дескриптивные, так и оптимизационные математические, характеризующие различные экономические процессы и явления, например:

Каким образом происходит построение математической модели?

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

Приведем пример. Теория массового обслуживания – проблема образования очередей. Нужно уравновесить два фактора – затраты на содержание обслуживающих устройств и затраты на пребывание в очереди. Построив формальное описание модели производят расчеты, используя аналитические и вычислительные методы. Если модель хороша, то ответы найденные с ее помощью адекватны моделирующей системе, если плоха, то подлежит улучшению и замене. Критерием адекватности служит практика.

Оптимизационные модели, в том числе многокритериальные, имеют общее свойство– известна цель(или несколько целей) для достижения которой часто приходится иметь дело со сложными системами, где речь идет не столько о решении оптимизационных задач, сколько об исследовании и прогнозировании состояний в зависимости от избираемых стратегий управления. И здесь мы сталкиваемся с трудностями реализации прежнего плана. Они состоят в следующем:

В связи с перечисленными трудностями, возникающими при изучении сложных систем, практика потребовала более гибкий метод, и он появился – имитационное моделирование «Simujation modeling».

Обычно под имитационной моделью понимается комплекс программ для ЭВМ, описывающий функционирование отдельных блоков систем и правил взаимодействия между ними. Использование случайных величин делает необходимым многократное проведение экспериментов с имитационной системой (на ЭВМ) и последующий статистический анализ полученных результатов. Весьма распространенным примером использования имитационных моделей является решение задачи массового обслуживания методом МОНТЕ–КАРЛО.

Таким образом, работа с имитационной системой представляет собой эксперимент, осуществляемый на ЭВМ. В чем же заключаются преимущества?

–Большая близость к реальной системе, чем у математических моделей;

–Блочный принцип дает возможность верифицировать каждый блок до его включения в общую систему;

–Использование зависимостей более сложного характера, не описываемых простыми математическими соотношениями.

Перечисленные достоинства определяют недостатки

–построить имитационную модель дольше, труднее и дороже;

–для работы с имитационной системой необходимо наличие подходящей по классу ЭВМ;

–взаимодействие пользователя и имитационной модели (интерфейс) должно быть не слишком сложным, удобным и хорошо известным;

–построение имитационной модели требует более глубокого изучения реального процесса, нежели математическое моделирование.

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

Итак, ни ЭВМ, ни математическая модель, ни алгоритм для ее исследования порознь не могут решить достаточно сложную задачу. Но вместе они представляют ту силу, которая позволяет познавать окружающий мир, управлять им в интересах человека.

Дата добавления: 2018-09-24 ; просмотров: 612 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

Источник