Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

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

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

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

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

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

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

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

§ Сначала отбросить условия дискретности и решить обычную непрерывную задачу.

§ Округлить полученное решение с целью обеспечения условия дискретности.

Графический метод. Основные понятия. Алгоритм метода

Графический метод решения задач всегда обладал для специалистов прикладников большой привлекательностью.

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

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

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

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

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

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

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

Градиентом функции f(x) называют вектор Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

f(x),

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

Алгоритм решения задач графическим методом

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

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

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

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

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

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

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

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

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

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

Метод отсечений. Формулирование верного отсечения. Алгоритм метода

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

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

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

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

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

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

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

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

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

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

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

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

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

- из пустоты допустимой области расширенной задачи следует пустота допустимой области исходной задачи.

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

Достоинства и недостатки алгоритма

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

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

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

§ отрицательной чертой алгоритма является также то, что первое допустимое решение исходной задачи в случае Dц=0 находится на последнем этапе ее решения.

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Метод ветвей и границ

Сущность метода заключается в направленном ветвлении области возможных решений оптимизационной задачи с целью локализации оптимального решения в одной из подобластей. При решении каждой задачи этим методом к ней должны быть применены следующие 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) разница между нижней и верхней оценкой целевой функции.

Размещено на Allbest.ru