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

СОДЕРЖАНИЕ

Введение            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. Предположим, что

т. е. общий  объем производства равен общему объему потребления. Требуется составить такой план перевозок (откуда, куда и сколько единиц продукта везти), чтобы удовлетворить спрос всех пунктов потребления за счет реализации всего продукта, произведенного всеми пунктами производства, при минимальной общей стоимости всех перевозок. Приведенная формулировка транспортной задачи называется замкнутой транспортной моделью. Формализуем эту задачу: Пусть х_ij - количество единиц продукта, поставляемого из пункта А_i в пункт В_j. Подлежащие минимизации суммарные затраты на перевозку продуктов из всех пунктов производства во все пункты потребления выражаются формулой

                                                     (1)          Суммарное количество продукта, направляемого из каждого пункта

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

, i 1, ..., m              (2)

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

 

, j 1, ..., n              (3)

Объемы перевозок - неотрицательные числа, так как  перевозки из пунктов потребления в пункты производства исключены

  x_ij

0, i 1, ..., m; j 1, ..., n                             (4)

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

Определение 1: всякое неотрицательное решение системы линейных уравнений , j 1, ..., n; , i 1, ..., m, определяемое матрицей X=(x_ij)(i 1, ..., m; j 1, ..., n), называется планом транспортной задачи.

Определение 2: план X*=(x*_ij)(i 1, ..., m; j 1, ..., n), при котором функция принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Очевидно, общее наличие  груза у поставщиков равно  , а общая потребность в грузе в пунктах назначения равна единице. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т.е.

                      (5)

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

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

, i 1, ..., m.

Введение этого условия  приводит к открытой транспортной модели.

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

        Стандартная задача линейного программирования

или в матричной записи

где    x = (x₁, x₂, x₃, … , x_n), c = (c_1, c_2, c₃, … , c_n), b = (b₁, b₂, b₃, … , b_n),

A = a_ij – матрица коэффициентов.

Вектор  c – называется вектором коэффициентов линейной формы, b – вектором ограничений.

Каноническая  задача ЛП выглядит следующим образом

или в матричной записи

Основные  вычислительные схемы решения задач  ЛП разработаны именно для канонической задачи.

Общая задача ЛП ставится следующим образом

здесь . Ясно, что стандартная задача получается как частный случай общей при ; каноническая – при .

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

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

1) суммарные запасы превышают суммарные потребности ;

2) суммарные потребности превышают суммарные запасы .

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

Найти минимальное значение линейной функции при ограничениях , i = 1, 2, ..., m, (случай  1) , j = 1, 2, ..., n;    , i = 1, 2, ..., m, (случай 2) , j = 1, 2, ..., n, x_ij ³ 0 (i = 1, 2, ..., m; j = 1, 2, ..., n).

Открытая модель решается приведением к закрытой модели.

В случае 1, когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель B_n+1, потребности которого

b_n+1 =

.

В случае 2, когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик  A_m+1, запасы которого

a_m+1 =

.

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

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

 

3 ЗАДАЧИ ЦЕЛОЧИСЛЕННОГО  ПРОГРАММИРОВАНИЯ

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

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

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

Графический метод. При наличии в задаче линейного программирования двух переменных, задача может быть решена графическим методом.  
В системе координат X₁0X₂ находят область допустимых решений, строят вектор С и линию уровня. перемещая линию уровня по направлению С для задач на максимум, определяют наиболее удаленную от начала координат точку и ее координаты. 

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

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

 

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

Нелинейное программирование  — случай математического программирования, в котором целевой функцией или ограничением является нелинейная функция.

В задаче нелинейного программирования (НЛП) требуется найти значение многомерной переменной х=(х₁, х₂,..., х_n), минимизирующее целевую функцию f(x) при условиях, когда на переменную х наложены ограничения типа неравенств

h_i(x) ≥ 0,   i=1,2,…,m

переменные x_j (компоненты вектора х) неотрицательны

          x_j ≥ 0

Иногда в формулировке задачи ограничения имеют противоположные знаки неравенств. Учитывая, однако, что если h_i (x) ≥ 0 , то -h_i (x) ≤ 0 , всегда можно свести задачу к неравенствам одного знака. Если некоторые ограничения входят в задачу со знаком равенства, например φ(x) = 0, то их можно представить в виде пары неравенств φ(x) ≥ 0, -φ(x) ≤ 0, сохранив тем самым типовую формулировку задачи.

В общем виде классификация задач нелинейного программирования, соответствии с видом функции F(x), представлена в таблице 1.

Таблица1 – Классификация задач нелинейного программирования

Вид F(x)	Вид функции ограничений	Число      переменных	Название задачи
Нелинейная	Отсутствуют	1	Безусловная    однопараметрическая оптимизация
Нелинейная	Отсутствуют	Более 1	Безусловная многопараметрическая оптимизация
Нелинейная         или  линейная	Нелинейные или   нелинейные	Более 1	Условная  нелинейная оптимизация

 

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

Общая формулировка нелинейных задач: найти переменные х₁, х₂, …, х_n, удовлетворяющие системе уравнений

Ψ ( х₁ , х₂ , …, х_n ) = b_i , i = 1, 2, …, m

и обращающие в максимум ( минимум ) целевую функцию

Z = f ( х₁ , х₂ , …, х_n )

Пример простой нелинейной задачи: данное предприятие для производства какого-то продукта расходует два средства в количестве х₁ и х₂ соответственно. Это факторы производства, например, машины и труд, два различных сырья и т.п., а величины х₁ и х₂ – затраты факторов производства. Факторы производства впредь будем считать взаимозаменяемыми. Если это «труд» и «машины», то можно применять такие методы производства, при которых величина затрат машин в сопоставлении с величиной затрат труда оказывается больше или меньше (производство более или менее трудоемкое).

Объем производства (выраженный в  натуральных или стоимостных  единицах) является функцией затрат производства Z = f (х₁ , х₂). Эта зависимость называется производственной функцией. Издержки зависят от расхода обоих факторов (х₁ и х₂) и от цен этих факторов (c₁ и c₂). Совокупные издержки выражаются формулой b = c₁ х₁ + c₂ х₂. Требуется при данных совокупных издержках определить такое количество факторов производства, которое максимизирует объем продукции Z.

Понятие условного экстремума вводится для случая, когда число переменных n не меньше 2(n≥2). Будем полагать, что функция Z = f( х₁, х₂, …, х_n)=f(X) дважды дифференцируема в точке Х* = (х₁ *, х₂ *, …, х_n*), (Х* € D(f)) и в некоторой ее окрестности.

Если для всех точек Х этой окрестности f (X*) ≥ f (X) или f (X*) ≤ f (X), то говорят, что функция f (X) имеет экстремум в X* (соответственно максимум или минимум).

Точка X* , в которой все частные производные функции Z = f (Х) равны 0, называется стационарной точкой.

Необходимое условие экстремума. Если в точке X* функция Z=f(Х) имеет экстремум, то частные производные функции в этой точке равны 0

f '_x1 (X*) = 0, i = 1, 2, ..., n

Следовательно, точки экстремума функции Z = f (Х) удовлетворяют системе уравнений

 

Для получения достаточных условий  следует определить в стационарной точке знак дифференциала второго  порядка. Дифференциала второго  порядка обозначается d²f (х₁ , х₂ , …, х_n ) f '_x1 (X) найти частную производную по переменной х_j , то получим частную производную второго порядка по переменным х_i , х_j , которая обозначается f ''_{xi, xj} (X). В этом случае

Достаточные условия экстремума двух переменных:

• если Δ > 0 и а₁₁ < 0 (а₂₂ < 0), то в точке Х ⁰ функция имеет максимум:  
  если Δ>0 и а₁₁ >0 (а₂₂ >0), то в точке Х ⁰ – минимум (в этих случаях Х ⁰ = Х*);
• если Δ < 0, то экстремума нет;
• если Δ = 0, то вопрос об экстремуме остается открытым.

 

5 ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

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

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

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