Исследование моделей массового обслуживания

СОДЕРЖАНИЕ

Введение            4

1 Понятие исследования операций        5

1.1 Постановка задачи исследования операций      5

1.2 Основные задачи исследования операций      6

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

3 Задачи  целочисленного программирования            16

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

5 Задачи динамического программирования                               20

6 Задачи теории игр                         22

Заключение                  24

Литература                  25

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

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

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

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

Задачами данной курсовой работы являются:

• постановка и моделирование задач исследования операций;  
• рассмотрение основных задач исследования операций, задач линейного программирования, целочисленного программирования, нелинейного программирования, динамического программирования и задач теории игр.  

 

1 ПОНЯТИЕ  ИССЛЕДОВАНИЯ ОПЕРАЦИЙ

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

1.1 Постановка задачи исследования операций

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

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

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

Показатель эффективности - количественная мера, позволяющая сравнивать разные решения по эффективности.

Все решения принимаются  всегда на основе информации, которой  располагает лицо принимающее решение (ЛПР).

Каждая задача в своей  постановке должна отражать структуру  и динамику знаний ЛПР о множестве  допустимых решений и о показателе эффективности.

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

Информационные состояния  ЛПР могут по-разному характеризовать его физическое состояние:

• если информационное состояние состоит из единственного физического состояния, то задача называется определенной;
• если информационное состояние содержит несколько физических состояний и ЛПР кроме их множества знает еще и вероятности каждого из этих физических состояний, то задача называется стохастической (частично неопределенной);
• если информационное состояние содержит несколько физических состояний, но ЛПР кроме их множества ничего не знает о вероятности каждого из этих физических состояний, то задача называется неопределенной.

1.2 Основные задачи исследования операций

Математическое  программирование («планирование») – это раздел математики, занимающийся разработкой методов отыскания экстремальных значений функции, на аргументы которой наложены ограничения. Методы математического программирования используются в экономических, организационных, военных и др. системах для решения так называемых распределительных задач. Распределительные задачи  (РЗ) возникают в случае, когда имеющихся в наличии ресурсов не хватает для выполнения каждой из намеченных работ эффективным образом и необходимо наилучшим образом распределить ресурсы по работам в соответствии с выбранным критерием оптимальности.

Рассмотрим  графический метод решения одноиндексных задач. Графический метод довольно прост и нагляден для решения задач ЛП с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.

Каждое из неравенств задачи ЛП определяет на координатной плоскости   некоторую полуплоскость, а система неравенств в целом – пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи ОДР является пустым множеством.

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

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

Построение  моделей транспортной задачи. Задача о размещении (транспортная задача) – это РЗ, в которой работы и ресурсы измеряются в одних и тех же единицах. В таких задачах ресурсы могут быть разделены между работами, и отдельные работы могут быть выполнены с помощью различных комбинаций ресурсов. Примером типичной транспортной задачи (ТЗ) является распределение (транспортировка) продукции, находящейся на складах, по предприятиям-потребителям.

Стандартная ТЗ определяется как задача разработки наиболее экономичного плана перевозки  продукции одного вида из нескольких пунктов отправления в пункты назначения. При этом величина транспортных расходов прямо пропорциональна объему перевозимой продукции и задается с помощью тарифов на перевозку единицы продукции.

Методы нахождения опорных планов. Опорный план является допустимым решением ТЗ и используется в качестве начального базисного решения при нахождении оптимального решения методом потенциалов. Существует три метода нахождения опорных планов: метод северо-западного угла, метод минимального элемента и метод Фогеля. «Качество» опорных планов, полученных этими методами, различается: в общем случае метод Фогеля дает наилучшее решение (зачастую оптимальное), а метод северо-западного угла – наихудшее.

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

Общая распределительная  задача линейного программирования. Общая распределительная задача ЛП – это РЗ, в которой работы и ресурсы (исполнители) выражаются в различных единицах измерения. Типичным примером такой задачи является организация выпуска разнородной продукции на оборудовании различных типов.

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

• действительной (требующей затрат времени);
• фиктивной (формально не требующей затрат времени).

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

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

 

2 ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Линейное программирование  — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств. Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. 

Приведем  основные свойства задачи ЛП:

1. допустимое множество решений задачи ЛП либо пусто, либо является выпуклым многогранником в Rⁿ (как пересечение полупространств, описываемых ограничениями-неравенствами). Оно может быть как ограниченным, так и неограниченным; в любом случае это замкнутый многогранник;
2. если допустимое множество не пусто, а целевая функция ограничена сверху (для задачи максимизации, а для задачи минимизации - ограничена снизу) на этом множестве, то задача ЛП имеет оптимальное решение;
3. оптимальные решения задачи ЛП (если они существуют) всегда находятся на границе допустимого множества. Точнее, если существует единственное оптимальное решение, то им является какая-либо вершина многогранника допустимых решений; если две или несколько вершин являются оптимальными решениями, то любая их выпуклая комбинация также является оптимальным решением.

Для любой  задачи ЛП можно составить двойственную к ней задачу по следующим правилам:

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

Транспортная задача является частным  типом задачи линейного программирования и формулируется следующим образом. Имеется m пунктов отправления (или пунктов производства) А₁,…,А_m, в которых сосредоточены запасы однородных продуктов в количестве a₁, ..., а_m единиц.

Имеется n пунктов назначения (или пунктов потребления) В₁, ..., В_m, потребность которых в указанных продуктах составляет b₁, ..., b_n единиц. Известны также транспортные расходы С_ij, связанные с перевозкой единицы продукта из пункта A_i в пункт В_j, i 1,…, m; j 1, ..., n. Предположим, что