Лекции Методы оптимальных решений. Методы оптимальных решений

• Название: Методы оптимальных решений
• Анкор: Лекции Методы оптимальных решений.doc
• Дата: 22.04.2017
• Размер: 466.5 Kb.
• Имя файла: Лекции Методы оптимальных решений.doc
• Тип: Решение; #5357
• страница: 3 из 9

ъ

Рис. 2.1. Основные этапы решения задачи принятия решения с помощью ЭВМ.
выбор задачи - важнейший вопрос. Какие основные требования должна удовлетворять задача? Таких требований два:
должно существовать, как минимум, два варианта ее решения (ведь если вариант один, значит и выбирать не из чего);

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

Хорошую модель составить не просто. Известный математик Р.Беллман сказал так: «Если мы попытаемся включить в нашу модель слишком много черт действительности, то захлебнемся в сложных уравнениях; если слишком упростим ее, то она перестанет удовлетворять нашим требованиям». Таким образом, исследователь должен пройти между западнями Переупрощения и болотом Переусложнения. Для выполнения успеха моделирования надо выполнить три правила, которые, по мнению древних, являются признаками мудрости. Эти правила применительно к задачам математического моделирования и формулируются так: учесть главные свойства моделируемого объекта; пренебрегать его второстепенными свойствами; уметь отделить главные свойства от второстепенных.

Составление модели - это искусство, творчество. Древние говорили: «Если двое смотрят на одно и то же, это не означает, что оба видят одно и то же». И слова древних греков: «Если двое делают одно и то же, это не значит, что получится одно и то же». Эти слова в полной мере относятся к составлению математических моделей. Если математическая модель - это диагноз заболевания, то алгоритм - это метод лечения.
Можно выделить следующие основные этапы операционного исследования:
 наблюдение явления и сбор исходных данных;

 постановка задачи;

 построение математической модели;

 расчет модели;

 тестирование модели и анализ выходных данных. Если полученные результаты не удовлетворяют исследователя, то следует либо вернуться на этап 3, т.e. предложить для решения задачи другую математическую модель; либо вернуться на этап 2, т.e. поставить задачу более корректно;

 применение результатов исследований.
Таким образом, операционное исследование является итерационным процессом, каждый следующий шаг которого приближает исследователя к решению стоящей перед ним проблемы. В центре операционного исследования находятся построение и расчет математической модели.
 Математическая модель - это система математических соотношений, приближенно, в абстрактной форме описывающих изучаемый процесс или систему.

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

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

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

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

 Определение пapaметров модели, т.е. заранее известных фиксированных факторов, на значения которых исследователь не влияет.

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

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

 Выявление неизвестных факторов, т.е. величин, которые могут изменяться случайным или неопределенным образом.

 Выражение цели через управляющие переменные, параметры и неизвестные факторы, т.e. формирование целевой функции, называемой также критерием эффективности или критерием оптимальности задачи.
Введем следующие условные обозначения:
 - параметры модели;

x - управляющие переменные или решения;

X - область допустимых решений;

 - случайные или неопределенные факторы;

W - целевая функция или критерий эффективности (критерий оптимальности).
W=W (x, , )
В соответствии с введенными терминами, математическая модель задачи имеет следующий вид:
W=W (x, , )  max (min) (2.1)

x  X
 Решить задачу - это значит найти такое оптимальное решение x^X, чтобы при данных фиксированных параметрах  и с учетом неизвестных факторов значения критерия эффективности W было по возможности максимальным (минимальным).
W^=W (x^, , ) = max (min) W (x, , )

x  X

 Таким образом, оптимальное решение - это решение, предпочтительное перед другими по определенному критерию эффективности (одному или нескольким).
Перечислим некоторые основные принципы построения математической модели:
 Необходимо соизмерять точность и подробность модели, во-первых, с точностью тex исходных данных, которыми располагает исследователь, и, во-вторых, с теми результатами, которые требуется получить.

 Математическая модель должна отражать существенные черты исследуемого явления и при этом не должна его сильно упрощать.

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

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

По учету неизвестных факторов математические модели делятся на детерминированные, стохастические и модели с элементами неопределенности.
 Встохастических моделях неизвестные факторы - это случайные величины, для которых известны функции распределения и различные статистические характеристики (математическое ожидание, дисперсия, среднеквадратическое отклонение и т.п.). Среди стохастических характеристик можно выделить:
- модели стохастического программирования, в которых либо в целевую функцию (2.1), либо в ограничения (2.2) входят случайные величины;

- модели теории случайных процессов, предназначенные для изучения процессов, состояние которых в каждый момент времени является случайной величиной;

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

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

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

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

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

 Hелинейные модели - это модели, в которых либо целевая функция, либо какое-нибудь из ограничений (либо все ограничения) нелинейны по управляющим переменным. Для нелинейных моделей нет единого метода расчета. В зависимости от вида нелинейности, свойств функции и ограничений можно предложить различные способы решения. Однако может случится и так, что для поставленной нелинейной задачи вообще не существует метода расчета. В этом случае задачу следует упростить, либо сведя ее к известным линейным моделям, либо просто линеаризовав модель.

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

 Графические модели-используются тогда, когда задачу удобно представить в виде графической структуры.

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

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

 выпуклой линейной комбинацией точек М₁, М₂, ... М_nназывается любая точка М такая, что:
М=a₁M₁+a₂M₂ + ... +a_nM_n,
где a_i 0 и a₁+a₂+ ... +a_n=1.
 Обобщая сказанное выше, можно сказать, что множество точек называется выпуклым, если вместе с любыми своими точками оно содержит и выпуклую произвольную комбинацию этих точек. Поскольку произвольная точка отрезка представляет собой выпуклую комбинацию его концов, то это и означает, что выпуклое множество вместе с двумя данными точками содержит весь соединяющий их отрезок.
Очевидно, что всякая точка выпуклого многоугольника, лежащая внутри его или на одной из сторон, за исключением вершин, может быть представлена как выпуклая линейная комбинация других точек этого многоугольника. Напротив, вершины многоугольника не представляются в виде выпуклой комбинации двух каких-нибудь других точек. В этом смысле вершины многоугольника называют экстремальными точками.
 прямая линия называется опорной, если она имеет с выпуклым многоугольником, по крайней мере, одну общую точку и весь многоугольник расположен по одну сторону от этой прямой. Через каждую из вершин многоугольника можно провести бесконечное множество опорных линий. В пространстве трех измерений, по аналогии с понятием опорной прямой вводится понятие опорной плоскости.

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



Для начала рассмотрим неравенство с одной переменной величиной x₁, напримерx₁4. Если на плоскости провести прямую х₁=4, то она разделит всю плоскость на две части - полуплоскости: в одной из них, а именно слева от прямой х₁=4, лежат точки, абсциссы которых меньше 4, а справа от прямой - точки, абсциссы которых больше 4. Таким образом, неравенство x₁4 геометрически определяет полуплоскость (Рис.1). Рассмотрим теперь неравенство с двумя переменными типа 3х₁+4х₂ 12. Построим прямую линию 3х₁+4х₂=12. Разделим обе части уравнения на 12:



из которого видно, что прямая отсекает по осям отрезки, равные 4 и 3.

Неравенство 3х₁+4х₂12 определяет собой совокупность всех точек плоскости, лежащих ниже прямой, т.е. в заштрихованной части (Рис. 2).


Чтобы легче было понять, какую именно полуплоскость определяет то или иное неравенство, мы в левую часть неравенства подставим координаты начала координат, т.е. х₁=0 и х₂=0. Если неравенство удовлетворяется, то оно определяет ту полуплоскость, в которой лежит начало координат, в противном случае - другую полуплоскость. Пользуясь геометрическими соображениями, найти возможные решения системы:
3х₁+4х₂  12

x₁2

х₁ 0 и х₂  0


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

Полученный многоугольник является выпуклым, ибо вместе с любыми двумя точками содержит весь соединяющий их отрезок. таким образом, мы видим, что выпуклый многоугольник можно задать аналитически, с помощью системы линейных неравенств. Линейное уравнение с тремя переменными:a₁₁x₁+a₁₂x₂+a₁₃x₃=b₁ определяет в пространстве некоторую плоскость, которая рассекает все пространство на два полупространства.

В связи с этим неравенствоa₁₁x₁+a₁₂x₂+a₁₃x₃b₁ определяет одно из полупространств, к которому принадлежит также и сама граничная плоскость. В общем случае, когда система неравенств совместна, пространство решений образует некоторый выпуклый многогранник - многогранник решений. Частным случаем его могут быть: отдельная грань, ребро или точка. Последнее имеет место, когда система неравенств имеет одно единственное решение. Дальнейшие обобщения приводят нас к рассмотрению m линейных неравенств с nнеизвестными. Каждое уравнение a_i1x₁+a_i2x₂+ ... +a_inx_n=b_i является уравнением некоторой гиперплоскости в n-мерном пространстве, которая как бы рассекает все пространство на два полупространства.
3.3. Значения линейной формы на выпуклом множестве
Предположим, что задана некоторая система из m-линейных неравенств (или уравнений) с n переменными х₁, х₂, ..., х_n. Система неравенств в случае совместности определяет некоторое выпуклое множество в n-мерном пространстве, ограниченное или бесконечное (многогранник решений).

Допустим далее, что нам задана некоторая линейная форма от этих переменных, определяющая функцию цели:
=c₁x₁+c₂x₂+ ... +c_nx_n
В каждой точке выпуклого множества, т.е. для каждого решения нашей системы, линейная форма  принимает определенное значение. Возникает вопрос: в каких точках выпуклого множества линейная форма  достигает своего наибольшего и наименьшего значения, если, конечно, такие существуют? Решение общей задачи линейного программирования сводится, таким образом, к нахождению точек выпуклого множества, в которых заданная линейная форма достигает оптимального значения, и мы ищем такие точки (х₁, х₂, ..., х_n), координаты которых неотрицательны. Сформулируем одно важное утверждение, облегчающее решение задачи.
 В тех случаях, когда множество решений задачи линейного программирования образует выпуклый многогранник, линейная форма достигает оптимального значения в одной из его вершин, в связи с чем последние и называются экстремальными точками.
В общем случае, линейная форма =c₁x₁+c₂x₂+ ... +c_nx_n задает гиперплоскость в n-мерном пространстве. При =0 эта гиперплоскость проходит через начало координат. Затем передвигаем эту плоскость параллельно самой себе в направлении вектора P перпендикулярно к этой плоскости. Первая из вершин, в которой линейная форма (гиперплоскость) встретит выпуклый многогранник, будет точкой, в которой линейная форма достигает наименьшего значения, а последняя из вершин - точкой, в которой линейная форма достигает наибольшего значения.

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

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