Лекции. Исследование операций и методы оптимизаций - файл n1.doc

Лекции. Исследование операций и методы оптимизаций
скачать (355 kb.)
Доступные файлы (1):
n1.doc355kb.29.05.2012 21:38скачать

n1.doc

  1   2   3   4   5   6   7   8   9   10
Исследование операций
Обобщенная формулировка задачи исследования операций
Исследование операций – научный метод, который дает в распоряжение инженера или руководителя количественные методы для принятия решений по управлению процессов оптимизации и видами человеческой деятельности.
Операция – совокупность взаимосвязанных действий, направленных на достижение поставленной цели.
Дискретное программирование – раздел математического программирования, в котором изучаются методы решения оптимизационных задач с не связанной областью допустимых решений. Эта область распадается на ряд несвязанных друг с другом подмножеств, и в частном случае являются отдельными точками подмножеств.

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

Математическая формулировка задач дискретного программирования


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

Получить экстремальное значение целевой функции (F):

F: extrem z = f(x, w)

x,w

При ограничениях (D):

X є Rn, w є zp

D = gi(x,w)<=0



I=1,m

Где:

Z – целевая функция

X – вектор непрерывных оптимизационных переменных размерности n

W – вектор целочисленных оптимизационных переменных размерностью p

D - множество допустимых решений

Rn - n-мерное евклидовое пространство

Zp - p-мерное множество целых чисел.

gi - условие ограничения, накладываемое на оптимизационные переменные.

I - порядковый номер и, соответственно, общее количество оптимизационных переменных.
Можно предположить, что ЗДП можно решить зная общие методы решения непрерывных оптимизационных задач, а именно:


Графический метод. Основные понятия. Алгоритм метода
Графический метод решения задач всегда обладал для специалистов прикладников большой привлекательностью.
Не смотря на большую погрешность результатов графический метод по сравнению с аналитическим остается полезным. И на это имеются веские причины:

Во 1-х их наглядность дает наилучшее представление о структуре задачи и ее решении.

Во 2-х эти методы, несмотря на ограниченную точность можно использовать для

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

затем решают задачу более точными методами.

В 3-х часто в графике содержится значительная информация, которая позволяет

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

f(x)=(∂f/∂x1; ∂f/∂x2;.. ∂f/∂xn) , который указывает направление наиболее быстрого возрастания функции, и следовательно ориентирован перпендикулярно линии уровня этой функции.
Алгоритм решения задач графическим методом

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

знаки неравенств на знаки точных равенств.

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

  2. определяют область допустимых нецелочисленных решений, Dнц.

  3. наносят координатную сетку с узлами точками имеющими целочисленные значения х1, х2.

  4. определяем область допустимых целочисленных решений.

  5. строят вектор с координатами (с1,с2).

  6. строят линию уровня целевой функции, приравняв выражение для целевой функции к нулю.

  7. перемещают линию уровня параллельно самой себе в направлении вектора из п. 6.

  8. В результате находят точку, в которой целевая функция принимает max значение.

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



Метод отсечений. Формулирование верного отсечения. Алгоритм метода
Сущность метода отсекающих плоскостей заключается в следующем:

  1. Вначале решается задача с отброшенным условием целочисленности.

  2. По полученным результатам делаются следующие выводы:

- если Dнц=0, то на основании того, что область допустимых Dц є Dнц, то делают вывод, что множество Dц=0 тоже пустое.

- если целевая функция задачи неограниченна на множестве Dнц, то делается вывод что она тоже неограниченна на множестве Dц. Объясняется это тем, что в области содержащей бесконечно удаленную точку всегда можно найти аналогичного рода точку принадлежащую Dц.

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

- Если решение на области Dнц является нецелочисленным, то осуществляется переход к 3-му этапу.


  1. Составляется дополнительное ограничение , которое называется правильным

отсечением. Правильное отсечение должно удовлетворять следующим

требованиям:

- быть линейным

- отсекать найденное оптимальное нецелочисленное решение задачи.

4. Осуществляется возращение к задачи линейного программирования с

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

будет опять нецелым, то формируем новое дополнительное ограничение и процесс повторяем.

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

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

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





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

1.Ветвление множества допустимых решений.

2.Определение нижних и верхних границ целевой функции.
Формирование нижних и верхних оценок целевой функции

Общепринятым считается применение данного метода для задачи в которой направление оптимизации приведено к виду минимизации целевой функции.

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

Min f(x)

x є D

В этой формуле х-вектор допустимых оптимизационных переменных , среди которых часть переменных действительные числа и часть - целочисленные переменные.
Нижней оценки целевой функции в зависимости от выбранного способа ветвления могут определятся либо для подобластей Di є D либо для подобластей Di є Dٰ , где Di и Dٰ получены из соответствующих множеств Di и D путем снятия условия целочисленности на переменные.
Нижней оценкой целевой функции f(x) на некотором множестве Di или Diٰ будем называть величину Σi=min Σij , где Σij – значение целевой функции f(x) на множестве Di для решений подзадачи j .
Если при решении подзадачи установлено , Di – пустое множество , то нижнюю оценку принимают равной бесконечности.
Нижние оценки имеют важное свойство.Их значение для образовавшихся при ветвлении подмножеств не могут быть меньше нижней оценки целевой функции на множестве которое подвергалось ветвлению.
Для большинства задач вычисляют только одно значение верхней оценки на множестве Di. ŋ (Di).

Ее определяют как значение целевой функции для найденного допустимого_лучшего решения исходной задачи.
Если для решаемой задачи можно просто и точно получить верхние оценки для отдельных множеств , образующихся при ветвлении, то их необходимо использовать для уменьшения вычислительной сложности процесса.
На начальном этапе решения задачи значение верхней оценки обычно принимают равной бесконечности ŋ (Di) = ∞ .
При нахождении первого допустимого решения , которое пренадлежит множеству D, xдоп є D, рассчитывают верхнюю оценку на множестве D , как значение целевой функции от найденного допустимого решения - ŋ (D) = f(xдоп).
Затем при определении лучшего допустимого решения x ٰдоп (f(x ٰдоп )< f(xдоп)) ,

ŋ (D)= f(x ٰдоп ).
Значение верхней оценки в процессе решения задачи может только уменьшаться.
Алгоритм метода ветвей и границ.
1 этап. Ветвлению в первую очередь подвергается подмножество S (S є I ), которому соответствует наименьшее значение нижней оценки целевой функции. I- это множество включающее номера всех подмножеств Di или Di’ , которые находятся на концах ветвления и ветвление которых не прекращено.
2 этап. Если для некоторого подмножества i Σi≥ŋ(D) то ветвление его необходимо прекратить, т. к. потенциальные возможности нахождения лучшего решения в этом подмножестве оказывается хуже, чем значение целевой функции для найденного к данному моменту времени лучшего допустимого решения.
3 этап. Ветвление подмножества Di’ прекращается, если найденное оптимальное решение Є D обосновывается это тем, что значение целевой функции от этого решения равно нижней границе на множестве Di. Следовательно, лучшего допустимого решения на данном множестве не существует. В этом случае рассматривают возможность корректировки верхней оценки целевой функции.
4 этап. Если выполняется соотношение Σ≥ŋ(D), где Σ=min Σi, то выполняется условие i є I оптимальности для найденного допустимого решения.
5 этап. После нахождения хотя-бы одного допустимого решения может быть рассмотрена возможность остановки работы алгоритма с их подсчетом погрешности найденного решения по отношению к оптимальному. ∆= Σ- ŋ(D) разница между нижней и верхней оценкой целевой функции.

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

Пусть задана матрица С=|| Cij || расстояний между городами. Если от некоторой строки i или некоторого столбца j вычесть минимальный из них, то получим матрицу, у которой в каждой строке и в каждом столбце будет хотя бы один нулевой элемент. Такая матрица называется приведенной, а процесс получения нулей – приведением. Сумма вычитаемых в процессе приведения элементов называется приводящей const обозначается hk, где к – порядковый номер приведения.

Для описания процедуры ветвления используем геометрическую интерпретацию метода. Разбиение множества всех циклов на не пересекаемые подмножества будет изображать дерево с вершинами, состоящими из пар допустимых(i,j) и запрещенных (i,j) городов.

Пара (i,j) содержит все маршруты, которые позволяют переход из города i в j(i,j) – все маршруты, запрещающие переход

из города i в j. Пара (к,l) – содержит все маршруты, в которых разрешен переход не только с к в l, но из i в j.
Обозначим вершину, из которой осуществляется ветвление, k,l k,lчерез х. Вершину, которая наиболее вероятно принадлежит

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

границу w(x). Процесс ветвления опишем следующим образом: процесс выбора пары городов для ветвления как игру 2-х лиц.

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

Поскольку каждая строка и столбец приведенной матрицы содержат хотя бы один нулевой элемент, то претендентов на ветвление на 1-м шаге для множества y будет не меньше, чем n.

Неоднозначность выбора пары затрудняет процесс игрока y. Поэтому для выбора однозначной стратегии он накладывает ограничивающие факторы для игрока y : если y для объезда выбирает пару городов (i,j), то y должен выехать из любого города, но не в j и въехать в любой город, но не из i. Y ÷ (i,j).

Игрок y будет стремиться выбрать такой допустимый переезд, чтобы суммарный путь был минимальным. Поэтому в строке i приведенной матрицы он выбирает тот город (исключая j), которому соответствует минимальное расстояние. А в столбце j – город (исключая i), которому соответствует минимальный элемент.

Зная о стратегии y , игрок y выбирает из всех допустимых пар городов ту пару, у которой будет наибольшее расстояние.
  1   2   3   4   5   6   7   8   9   10


Исследование операций
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации