Исследование операций. 5

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И  НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ  ОБРАЗОВАТЕЛЬНОЕ  УЧРЕЖДЕНИЕ

СРЕДНЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ЧЕРЕМХОВСКИЙ ГОРНОТЕХНИЧЕСКИЙ КОЛЛЕДЖ»

 

 

 

МАТЕМАТИЧЕСКИЕ МЕТОДЫ

ТЕМА «Исследование операций»

 

Пояснительная записка

 

01.КР.230105.11.011.ПЗ

 

 

 

Приняла                                       Выполнила

      Н.Н.Толкачёва                     студентка гр. ПОВТ-08

22.12.11                                            В.В.Звягинцева

                                              21.12.11

 

 

 

 

 

 

 

 

 

 

 

2011

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ 

Исследование  операций — применение математических, количественных методов для обоснования решений во всех областях целенаправленной человеческой деятельности. Исследование операций начинается тогда, когда для обоснования решений применяется тот или другой математический аппарат. Операция — всякое мероприятие (система действий), объединённое единым замыслом и направленное к достижению какой-то цели (напр., мероприятия задач 1-8, указанных ниже, будут операциями). Операция всегда является управляемым мероприятием, то есть зависит от человека, каким способом выбрать параметры, характеризующие её организацию (в широком смысле, включая набор технических средств, применяемых в операции). Решение (удачное, неудачное, разумное, неразумное) — всякий определённый набор зависящих от человека параметров. Оптимальное — решение, которое по тем или другим признакам предпочтительнее других. Цель исследования операций — предварительное количественное обоснование оптимальных решений. Само принятие решения выходит за рамки исследования операций и относится к компетенции ответственного лица (лиц). Элементы решения — параметры, совокупность которых образует решение: числа, векторы, функции, физические признаки и т. д. Если элементами решения можно распоряжаться в определённых пределах, то заданные («дисциплинирующие») условия (ограничения) фиксированы сразу и нарушены быть не могут (грузоподъёмность, размеры, вес). К таким условиям относятся средства (материальные, технические, людские), которыми человек вправе распоряжаться, и иные ограничения, налагаемые на решение. Их совокупность формирует множество возможных решений.

В данную курсовую работу я включила главы, такие как: Особенности темы исследование операций; Основные понятия; Симплекс-метод; Теоремы, доказательства теорем Симплекс-метода; Двойственные задачи; Транспортная задача.

В целях более быстрого усвоения материала каждая глава содержит краткое теоретическое введение и примеры.

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

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

 

 

 

 

 

 

 

 

 

 

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ.

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

Особенности темы исследование операций

1.1 Исторический очерк

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

К этому периоду относятся  первые работы по исследованию в области  организации труда и управления - первые предвестники будущей науки.

Как самостоятельное научное  направление исследование операций оформилось в начале 40-х годов.

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

 

Возникла необходимость  в подготовке кадров специалистов по исследованию операций - операционистов. В ведущих университетах США и Англии впервые было начато систематическое преподавание курса исследование операцийю

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

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

1.2. Предмет и  цель исследования операций

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

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

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

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

1.3. Особенности  исследования операций

 Системный подход к  анализу поставленной проблемы.

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

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

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

Тогда приходится ограничиваться поиском достаточно хорошего или  субоптимального решения.

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

1.4. Основные этапы  операционного исследования

Постановка задачи.

 Первоначально задачу  формулируют с точки зрения  заказчика. Во время анализа  системы задача постепенно уточняется.

Формализация  задачи.

 Получив достаточно  строгую и логически непротиворечивую, содержательную постановку задачи, нужно построить ее математическую  модель.

Нахождение метода решения.

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

Проверка и  корректировка модели.

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

Реализация найденного решения на практике.

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

1.5. Классификация  задач исследования операций  по уровню информации о ситуации

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

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

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

 

Раздел 1. Линейное программирование

Глава 1. Основные понятия

1.1. Примеры моделей,  приводящих к задачам линейного  программирования

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

Имеются какие-то переменные и функция этих переменных , которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции при условии, что переменные x принадлежат некоторой области G:

В зависимости от вида функции  и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Подробнее об этом будет сказано в заключении.

Линейное программирование характеризуется тем, что

а) функция  является линейной функцией переменных ;

б) область G  определяется системой линейных равенств или неравенств.

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

Задача о диете

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

Предположим, что в нашем  распоряжении имеется n продуктов питания (сено, зерно, комбикорм, соль и т.д.). Обозначим эти продукты через . Предположим, что есть стоимость единицы веса (например, стоимость одного килограмма) продукта .

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

 

 

 

 

 

 

Таким образом, величина есть количество i-го компонента, содержащегося в единице веса j-го продукта. Матрица называется матрицей питательности.

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

Что же требуется от рациона? Во-первых, должны быть выполнены определенные медицинские требования, которые  заключаются в том, что за указанный  срок животное должно получить не менее  определенного количества каждого  компонента (не менее определенного  количества белков, жиров, витаминов  и т.д.). Обозначим через  то минимальное количество j-го компонента, которое должно получить животное. Тогда рацион кормления должен удовлетворять ограничениям

(1.1)

 Кроме того очевидно, что все переменные  неотрицательны, т.е. ... (1.2) Пусть стоимость единицы веса i-го продукта равна .<Тогда весь наш рацион будет стоить (1.3) <

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

(1.4)

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

1.2 Геометрическая интерпретация задач линейного программирования

Для понимания всего дальнейшего  полезно знать и представлять себе геометрическую интерпретацию  задач линейного программирования, которую можно дать для случаев  n =2 и n =3.

Наиболее наглядна эта  интерпретация для случая n =2, т.е. для случая двух переменных и . Пусть нам задана  задача линейного программирования в стандартной форме  

(1.19)

Возьмём на плоскости декартову  систему координат и каждой паре чисел  поставим в соответствие точку на этой плоскости.

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

 Пусть  . Если взять , то получится . Если взять , то получится . Таким образом, на прямой лежат две точки и . Дальше через эти две точки можно по линейке провести прямую линию (рисунок 2).

Если же b=0, то на прямой лежит точка (0,0). Чтобы найти другую точку, можно взять любое отличное от нуля значение и вычислить соответствующее ему значение  .

Эта построенная прямая разбивает  всю плоскость на две полуплоскости. В одной её части  , а в другой наоборот . Узнать, в какой полуплоскости какой знак имеет место проще всего посмотрев, какому неравенству удовлетворяет какая-то точка плоскости, например, начало координат, т.е. точка (0,0).

Глава 2. Симплекс-метод

2.1. Выпуклые множества  и многогранники 

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

Рассмотрим n - мерное евклидово пространство  и пусть - точка в этом пространстве.

Рассмотрим две точки  и , принадлежащие . Множество точек , которые могут быть представлены в виде (в координатах это записывается так:

,называется выпуклой комбинацией  точек  и , или отрезком, соединяющим точки и . Сами точки и   называются концами отрезка. В случаях n =2 и n =3 это - отрезок в обычном понимании этого слова на плоскости или в пространстве (см. рис. 12). Заметим, что при l =0 , а при l =1 , т.е. при l =0 и l =1 получаются концы отрезка.

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

Пусть есть некоторая область в пространстве (другими словами, G есть некоторое множество точек из  ).

Определение. Множество (область) называется выпуклым, если из того, что и следует, что для l Î [0,1].  Другими словами, G - выпуклое множество, если оно, вместе с любыми двумя своими точками, содержит в себе отрезок, соединяющий эти точки.

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

 

Теорема 1. Пусть G - выпуклое множество. Тогда любая выпуклая комбинация точек, принадлежащих этому множеству, также принадлежит этому множеству.

Доказательство Пусть  - точки, принадлежащие множеству G .

Докажем теорему методом  математической индукции. При k =2 теорема верна, так как она просто переходит в определение выпуклого множества.

Пусть теорема верна для  некоторого k. Возьмём точку и рассмотрим выпуклую комбинацию

,где все   и  .

Представим  в виде

Но коэффициенты  и ,

и, раз мы считаем, что  для k теорема верна, точка .

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

Теорема доказана.

 

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

Доказательство.

В стандартной форме в  матричных обозначениях допустимая область G определяется условием

Пусть  и .   принадлежат G , т.е. .

 Но тогда для   имеем

т.е. x принадлежит G и, следовательно, выпукло.

В канонической форме область  G определена условиями

Пусть  и   принадлежат G, т.е.

.Но тогда для   имеем

т.е. и, следовательно, G выпукло. Теорема доказана.

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

Теорема 3. Множество оптимальных  планов задачи линейного программирования выпукло (если оно не пусто).

Доказательство

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

Рассмотрим  . В силу выпуклости области

допустимых значений, . Но для этого плана

т.е. есть также оптимальный план и, в силу этого, множество оптимальный планов выпукло. Теорема доказана.

Теорема 4. Для того, чтобы задача линейного программирования имела решение, необходимо и достаточно, чтобы целевая функция на допустимом множестве была ограничена сверху (при решении задачи на максимум) или снизу (при решении задачи на минимум).

 

Глава 3. Двойственные задачи

3.1. Постановка  двойственных задач

Симметричные двойственные задачи

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

   (1)

или, в матричной форме,  

(2)

Рассмотрим теперь следующую  задачу

  (3)

или, в матричной форме,  

(4)

Пара задач (1) и (3) (или, в  матричной форме, пара задач (2) и (4) ) называются двойственными друг другу задачами в симметричной форме.

Несимметричная двойственная задача

Исходная задача  имеет  вид:

  (5)

или, в матричной форме,  

(6)

Двойственная задача в  несимметричной форме имеет вид

(7)

или, в матричной форме,

 (8)

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

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

Экономическая интерпретация  двойственной задачи в симметричной форме

Исходная задача:

Обычно эта задача связывается  с задачей максимизации дохода при  производстве некоторой продукции  при наличии ограничений на ресурсы. Коэффициенты имеют смысл дохода от единицы продукции j-го ресурса, — количество единиц продукции j-го вида. Коэффициенты имеют смысл затрат i-го ресурса на производство продукции j-го типа. Что же представляет двойственная задача по своему смыслу?

Целевая функция двойственной задачи:,

а ограничения: , где (1) — затраты i-го ресурса на производство единицы продукции j-го типа, а (2) — доход от продажи единицы продукта i-го типа. Поэтому в целевой функции на месте (?)получаем смысл стоимости всех ресурсов, т. е. Задача приобретает смысл: , при ограничениях: , где

(3) — запасы i-го ресурса;

(4) — стоимость единицы i-го ресурса;

(5) — общая стоимость всех ресурсов;

(6) — запасы i-го ресурса на производство единицы продукции j-го типа;

(7) — цена единицы i-го ресурса;

(8) — доход от продажи единицы продукции i-го вида.

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

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

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

Переменные  называется по-разному. Часто их называют учетными, неявными или фиктивными ценами.

 

Глава 4. Транспортная задача

4.1. Постановка  задачи 

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

Начнем с её содержательной формулировки.

Пусть имеется некоторый  однородный продукт, сосредоточенный  на m пунктах отправления (складах), так что на i-м складе находится единиц этого продукта.

Этот продукт необходимо доставить в n пунктов назначения (потребления), причем на j-й пункт необходимо доставить единиц продукта. Запасы и потребности сбалансированы, то есть

то есть наличие продукта равно потребности в нем.

Пусть стоимость перевозки  единицы продукта из i-го склада в j-й пункт назначения равна . Пусть есть то количество продукта, которое перевозится из i-го склада в j-й пункт потребления.

Тогда общие транспортные расходы составят величину

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

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

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

 

являющейся типичной задачей  линейного программирования.

Определение 3.1. Транспортная задача называется открытой транспортной задачей, если условие баланса нарушаются; в случае выполнения условия баланса  она называется сбалансированной транспортной задачей.

Однако у этой задачи есть одна очень существенная особенность: в ограничениях перед неизвестными всегда стоит 1. И именно это позволяет разработать гораздо более эффективные и простые алгоритмы решения транспортной задачи, чем симплекс-метод.

Сам же симплекс-метод был  бы не эффективен по двум причинам:

Большая размерность решаемой задачи. Общее число неизвестных  величин  равно mn , и даже при n =m = 10 размерность решаемой задачи уже будет равна 100. Даже ЭВМ будет решать такую задачу симплекс-методом достаточно долго.

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

Приведение открытой транспортной задачи к сбалансированной

Превышение запасов над  потребностями.

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