Реферат: Исследование математических операций 2

 задачи массового обслуживания,

 задачи упорядочивания,

 задачи сетевого планирования.

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

1) требуется наличие высококвалифицированных специалистов, т.к. он содержит в себе элементы всех вышеперечисленных методов;

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

2. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

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

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

Американский математик А.Данциг в 1947 году разработал весьма эффективный конкретный метод численного решения задач линейного программирования (он получил название симплекс метода). Идеи линейного программирования в течение пяти шести лет получили грандиозное распространение в мире, и имена Купманса и Данцига стали повсюду широко известны.

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

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

В самом общем виде задача математически записывается следующим образом:

; , (2.1)

где X = (x₁ , x₂ , ... , x_n );

W – область допустимых значений переменных x₁ , x₂ , ... , x_n ;

f (Х ) – целевая функция.

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

Оптимизационная задача является неразрешимой, если она не имеет оптимального решения. В частности, задача максимизации будет неразрешимой, если целевая функция f (Х ) не ограничена сверху на допустимом множестве W .

Методы решения оптимизационных задач зависят как от вида целевой функции f (Х ), так и от строения допустимого множества W . Если целевая функция в задаче является функцией n переменных, то методы решения называют методами математического программирования.

2.1. Задачи линейного программирования

Линейное программирование является наиболее простым и лучше всего изученным разделом математического программирования. Характерные черты задач линейного программирования следующие:

1) показатель оптимальности f (X ) представляет собой линейную функцию от элементов решения X = (x₁ , x₂ , ... , x_n );

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

Задачей линейного программирования называется задача исследования операций, математическая модель которой имеет вид:

(2.2)

(2.3)

(2.4)

. (2.5)

При этом система линейных уравнений (2.3) и неравенств (2.4), (2.5), определяющая допустимое множество решений задачи W , называется системой ограничений задачи линейного программирования , а линейная функция f (Х ) называется целевой функцией или критерием оптимальности .

В частном случае, если I = Ø, то система (2.3) – (2.4) состоит только из линейных неравенств, а если I = M , то – из линейных уравнений.

При описании реальной ситуации с помощью линейной модели следует проверять наличие у модели таких свойств, как пропорциональность и аддитивность. Пропорциональность означает, что вклад каждой переменной в целевой функции и общий объем потребления соответствующих ресурсов должен быть прямо пропорционален величине этой переменной. Например, если, продавая j -й товар в общем случае по цене 100 рублей, фирма будет делать скидку при определенном уровне закупки до уровня цены 95 рублей, то будет отсутствовать прямая пропорциональность между доходом фирмы и величиной переменной x_j . Т.е. в разных ситуациях одна единица j -го товара будет приносить разный доход. Аддитивность означает, что целевая функция и ограничения должны представлять собой сумму вкладов от различных переменных.