tem__1__2__3(______) ru

ТЕМА 1.

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

1 Типичные задачи

2 Основные понятия

3 Этапы проведения исследования операций

4 Математические модели операций

5 Задачи оптимизации – определения и классификация

1. Типичные задачи

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

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

Рассмотрим ряд типичных для исследования операций задач.

Пример 1. Составление плана снабжения предприятия (транспортная задача).

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

Пример 2. Определение оптимального ассортимента выпуска продукции.

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

Пример 3. Распределительная задача.

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

Пример 4. Задача об оптимальных назначениях или проблема выбора.

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

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

-речь идет о каком-то мероприятии, преследующем определенную цель;

-заданы некоторые условия, характеризующие обстановку (в частности, средства, которыми можно распоряжаться);

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

2. Основные понятия

Под термином исследование операций (ИО) будем понимать применение математических методов для обоснования решений в каких-либо областях человеческой деятельности.

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

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

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

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

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

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

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

Критерий эффективности выбирается так, чтобы он отражал целевую направленность операций, поэтому его ещё называют целевой функцией.

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

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

3. Этапы проведения исследования операций

Работа, выполняемая специалистом в процессе операционного исследования, состоит из следующих этапов:

1) Идентификация проблемы

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

2) Построение модели

Если y является векторной случайной величиной с известной вероятностной мерой, то недетерминированная модель называется стохастической моделью.(Под термином “случайное явление” в теории вероятностей принято понимать явление, относящееся к классу повторяемых и, главное, обладающее свойством статистической устойчивости (при повторении средние характеристики стабилизируются).)

Если операция проводится неоднократно и имеет смысл средний результат, то математическая модель имеет следующий вид:

M {F( x, y )}→ min

Py {x X ( y )}≥ 1 − ε

Если операция проводится однократно, либо не имеет смысла средний результат, то модель может принимать вид:

Py {x X ( y )}≥ 1 − ε

Эти задачи называются задачами стохастической оптимизации.

Если y не является случайной величиной, либо это случайная величина с неизвестной вероятностной мерой, то имеем модель в условиях неопределенности.

x I X ( y )

y

5.Задачи оптимизации – определения

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

def. Если неравенство в (2) или (3) выполняется как строгое при x ≠ x * , то говорят, что x * - точка строго минимума (строгое решение) в глобальном или локальном смысле соответственно.

Задачу максимизации функции f на X будем записывать в виде

x X

Ясно, что задача (4) эквивалентна задаче

-f(x)→min

x X

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

a) f*> − ∞ и f(x*)=f* при некотором x* X , то есть значение задачи конечно и достигается, при

этом f * = min f ( x ) ;

X

b) f * > −∞ и f ( x ) < f * при всех x X , то есть значение задачи конечно, но не достигается;

c) f * = −∞ , то есть значение задачи бесконечно.

В случае a) задача (1) имеет глобальное решение, в случаях b) и c) – не имеет.

Классификация задач оптимизации

def. Если X= R n , то задача (1) называется задачей безусловной оптимизации.

в) n-мерного шара.

def. Если X определяется из условия:

X = {x P g i ( x ) ≤ 0 ,i = 1,k , g i ( x ) = 0 ,i = k + 1,m}

где P- множество простой структуры P R n , то (1) –общая задача математического программирования и записывается в виде:

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

def Пусть даны две точки x1 , x 2 X , тогда их выпуклой линейной комбинацией будет любая точка x вида

x = λx1 + ( 1 − λ )x 2 ,λ R 1 ,0 ≤ λ ≤ 1

def Множество X R n выпукло, если оно содержит все выпуклые линейные комбинации любых пар точек x1 , x 2 X .

def Пусть X R n - выпуклое множество.Функция f : X → R 1 выпукла на X , если для любых двух точек x1 , x 2 X

f ( λx1 + ( 1 − λ )x 2 ) ≤ λf ( x1 ) + ( 1 − λ ) f ( x 2 ),

(*)

λ R 1 ,0 ≤ λ ≤ 1

если X = R n , просто говорят, что f выпукла.

Грубо говоря, выпуклая функция прогибается вниз.

Так, на рисунке функция f(x) выпукла на отрезке [0,1] R n (хорды всегда выше этой функции).

f ( x )′

λf ( x1 ) + ( 1 − λ ) f ( x 2 )

def. Если в (5)-(8) f(x)- квадратичная функция, функции gi ( x ),( i = 1,m ) - афинные функции,

P - неотрицательный октант, то (5)-(8)- задача квадратичного программирования.

def. Если в задаче (5)-(8) множество P- дискретное, то задача (5)- (8) – общая задача дискретного программирования (комбинаторная задача).

j =1

ТЕМА 2.

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

(эта версия темы №2 не полная, см. укр. вариант)

Векторы

В дальнейшем будем считать, что x R n всегда является вектором – столбцом

x1x2 x = ...

xn

x j - j-ый элемент (j-ая компонента ) вектора x.

Далее x R n в зависимости от контекста будем называть либо точкой, либо вектором.

Вектор – строку будем обозначать так: xT = [x1 , x2 ,Kxn ]

Скалярное произведение векторов запишем как xT y (д.б. одной размерности)

Def Множество векторов x1 , x 2 ,K, x m R n линейно независимо тогда и только тогда, когда

am*

def 1. Рангом матрицы А по столбцам называется наибольшее число линейно независимых

векторов среди n m-мерных столбцов a* j , j = 1,n .

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

def 2. Рангом матрицы А по минорам называется наибольший порядок минора среди миноров, отличных от нуля ( минор – это определитель подматрицы ).

Для произвольной матрицы А ранг по столбцам, ранг по строкам и ранг по минорам равны.

def .Матрица А называется невырожденной (неособенной), если она квадратная (m = n) и полного ранга ( rang A = n). Только невырожденная матрица имеет обратную.

Системы линейных уравнений

Система m линейных уравнений с n переменными x1 ,K, xn может быть записана в виде

a11 x1 + a12 x2 + K + a1n xn = b1

am1 x1 + am2 x2 + K + amn xn = bn

или в виде матричного уравнения

Единственное решение системы существует в том случае, если m = n и А – неособенная.

Тогда

A−1 Ax = A−1b

Ix = A−1b

x = A−1b

Используя наше обозначение a* j для j-го столбца А, матричное уравнение (1) можно переписать в виде

a*1 x1 + a*2 x2 + K + a* n xn = b

Таким образом решение системы уравнений можно свести к отысканию линейной комбинации векторов a*1a* 2Ka* n , которая равна вектору b. Коэффициенты этой линейной комбинации и есть элементы x1, x2 , ….. , xn вектора x. Если А – неособенная матрица, то векторы a*1a* 2Ka* n линейно-независимы, а значит существует одна и только одна такая комбинация.

Выпуклые множества

Пусть x1, x2 , ….. , x k – произвольные точки из R n .

Выпуклой линейной комбинацией (ВЛК) этих точек называется сумма вида:

λ1 x 1 + λ2 x 2 + K + λk x k ,

где λi , i = 1,k – произвольные неотрицательные числа, такие, что

k

∑λi = 1,λi ≥ 0,i = 1,k .

i=1

Теорема: Пусть Х – выпуклое множество, x1, x2 , ….. , x k – произвольные точки из Х. Тогда множество Х содержит любую выпуклую линейную комбинацию этих точек.

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

Доказательство проведем с помощью метода математической индукции (по числу точек k).

Ситуация, когда k = 1 тривиальна.

При k = 2 утверждение теоремы совпадает с определением выпуклого множества.

Пусть любая выпуклая линейная комбинация k – 1 точек множества Х принадлежит данному множеству.

Рассмотрим k точек x1, x2 , …..,xk -1 , x k .

Их линейная выпуклая комбинация: x = λ1 x 1 + λ2 x 2 + K + λk x k

точек из Х и, следовательно, x X .