Исследование математических операций 2 (стр. 3 из 28)
Должно существовать точно определяемое количество операций,
Множество операций по комплексу упорядочено так, что должно быть известно для каждой операции какие операции ей предшествуют, а какие следуют за ней,
В пределах заданного упорядочивания операций, операции можно начинать и заканчивать независимо друг от друга,
Известна взаимосвязь между ресурсами на выполнение операции и ее продолжительностью.
Если все условия выполнены, возможны следующие постановки задачи:
а) задана продолжительность выполнения всего комплекса операций. Требуется определить сроки каждой операции, при которых:
минимизируются общие затраты на выполнение всего комплекса операций,
определяется вероятность невыполнения комплекса работ в установленные сроки,
определяется среднеквартальные отклонения требуемых ресурсов от наличных.
б) заданы общие ресурсы. Определить сроки начала каждой операции, чтобы минимизировать время на выполнение всего комплекса операций.
7. Задачи маршрутизации.
Эти задачи возникают при исследовании разнообразных процессов на транспорте и в системах связи. Типичной задачей является задача выбора оптимального маршрута: имеется несколько маршрутов, из них нужно выбрать один. Стоимость прохождения и время на прохождение зависит от выбранного маршрута. При рассмотрении ряда маршрутов вводятся следующие ограничения:
- запрещается возвращаться в уже пройденный пункт,
- в пунктах сети возможны задержки (например, из-за ограниченной пропускной способности). Задержки носят случайный характер.
Критерии оптимизации: минимизация общего времени прохождения маршрута или минимизация общих затрат.
Данные задачи наиболее изучены и в литературе носят специфические названия – задача о коммивояжере или задача о максимальном потоке.
8. Комбинированные задачи.
Включают в себя несколько типовых задач одновременно.
Пример: при планировании и управлении производством необходимо решить комплекс задач:
1) сколько изделий каждого наименования необходимо выпустить и каковы оптимальные размеры партии изделий – задача планирования производства;
2) распределить заказы или детали по видам оборудования, причем оптимальный план производства задан – задача распределения;
3) определить в какой последовательности следует выполнить производственные заказы – календарное планирование.
Эти задачи нельзя решать независимо друг от друга. Критерии эффективности этих задач часто противоречат друг другу. Поэтому при решении задач часто используют:
Метод последовательного приближения – с помощью этого метода можно очень близко подойти к оптимальному решению.
Метод имитационного моделирования – основан на методе Монте-Карло (использование случайных чисел) и требует огромного количества вычислений, так как рассматривается очень много вариантов решений.
1.4. Методы отыскания оптимальных решений в задачах Исследования Операций. Классификация методов
К основным методам отыскания оптимальных решений относятся:
математическое программирование. В свою очередь методы математического программирования делятся на следующие:
линейное программирование,
нелинейное программирование,
динамическое программирование,
целочисленное программирование,
стохастическое программирование,
эвристическое программирование
теория массового обслуживания,
сетевые модели планирования и управления,
имитационное моделирование.
Рассмотренные выше классы задач можно решать указанными методами. Методами математического программирования решаются следующие классы задач:
задачи управления запасами,
задачи распределения ресурсов,
задачи замены и ремонта оборудования,
задачи выбора маршрута.
С помощью теории массового обслуживания решаются задачи массового обслуживания.
С использованием сетевых моделей планирования и управления можно решать:
задачи массового обслуживания,
задачи упорядочивания,
задачи сетевого планирования.
Методом имитационного моделирования решаются комбинированные задачи. Данным методом можно решить задачу любого класса, однако, данный метод не является универсальным. Его применение ограничено следующими факторами:
1) требуется наличие высококвалифицированных специалистов, т.к. он содержит в себе элементы всех вышеперечисленных методов;
2) решение обходится дороже, чем при использовании других методов.
Однако идеи Л.В.Канторовича не встретили понимания в момент их зарождения, были объявлены ересью, и его работа была прервана. Концепции Леонида Витальевича вскоре после войны были переоткрыты на западе. Американский экономист Т.Купманс в течение многих лет привлекал внимание математиков к ряду задач, связанных с военной тематикой. Он активно способствовал тому, чтобы был организован математический коллектив для разработки этих проблем. В итоге было осознано, что надо научиться решать задачи о нахождении экстремумов линейных функций на многогранниках, задаваемых линейными неравенствами. По предложению Купманса этот раздел математики получил название линейного программирования.
Американский математик А.Данциг в 1947 году разработал весьма эффективный конкретный метод численного решения задач линейного программирования (он получил название симплекс метода). Идеи линейного программирования в течение пяти шести лет получили грандиозное распространение в мире, и имена Купманса и Данцига стали повсюду широко известны.
Свое второе рождение линейное программирование получило в начале пятидесятых годов с появлением ЭВМ. Тогда началось всеобщее увлечение линейным программированием, вызвавшее в свою очередь развитие других разделов математического программирования. В 1975 году академик Л.В.Канторович и американец профессор Т.Купманс получили Нобелевскую премию по экономическим наукам за "вклад в разработку теории и оптимального использования ресурсов в экономике".
Оптимизационная задача – это экономико-математическая задача, которая состоит в нахождении оптимального (максимального или минимального) значения целевой функции, причем значения переменных должны принадлежать некоторой области допустимых значений.
В самом общем виде задача математически записывается следующим образом:
; 
, (2.1)
W – область допустимых значений переменных x1, x2 , ... , xn ;
f(Х) – целевая функция.
Для того, чтобы решить задачу оптимизации, достаточно найти ее оптимальное решение, т.е. указать
такое, что 
при любом .Оптимизационная задача является неразрешимой, если она не имеет оптимального решения. В частности, задача максимизации будет неразрешимой, если целевая функция f(Х) не ограничена сверху на допустимом множестве W.
Методы решения оптимизационных задач зависят как от вида целевой функции f(Х), так и от строения допустимого множества W. Если целевая функция в задаче является функцией n переменных, то методы решения называют методами математического программирования.
2.1. Задачи линейного программирования
Линейное программирование является наиболее простым и лучше всего изученным разделом математического программирования. Характерные черты задач линейного программирования следующие:
1) показатель оптимальности f(X) представляет собой линейную функцию от элементов решения X = (x1, x2 , ... , xn);
2) ограничительные условия, налагаемые на возможные решения, имеют вид линейных равенств или неравенств.
Задачей линейного программирования называется задача исследования операций, математическая модель которой имеет вид:
(2.2) 
(2.3)
(2.4) 
. (2.5)При этом система линейных уравнений (2.3) и неравенств (2.4), (2.5), определяющая допустимое множество решений задачи W, называется системой ограничений задачи линейного программирования, а линейная функция f(Х) называется целевой функцией или критерием оптимальности.
В частном случае, если I = Ø, то система (2.3) – (2.4) состоит только из линейных неравенств, а если I = M, то – из линейных уравнений.