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

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

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

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

1.Математические модели и методы в экономике. Примеры.

2.Формализация принципов оптимального доведения в исследовании операций.

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

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

5.Математические модели задач потребления и производства как задачи математического программирования.

18.Экономическая интерпретация двойственности в задачах линейного программирования.

Экономическая интерпритация прямой и двойственной задач Двойств. задача: определить, какое количество ресурсов y_i (i=1..m) надо ис­пользовать, чтобы при заданных ценах c_j (j=1..m) на единицу продукции, за­траты были бы минимальными.

Двойственность в ЛП. Пусть задана задача ЛП в канонической форме:

(с,х) ®max (1); Ax=b (2); x³0 (3). Каж­дой задаче ЛП можно поставить в соот­ветствие др. задачу, которую будем на­зывать двойственной задачей: (с,x)=(c,x) +(y,-Ax+b)=(c,x)+(y,b)-(y,Ax)=(c,x)+(y, b)-(x,A^Ty)=(b,y)-(x,A^Ty-c) Если потре­буем, чтобы A^Ty³c, тогда (c,x)£(b,y). Тогда max(c,x)=min(b,y). Т.о. возникает двойственная задача: (b,y)®min (4); A^Ty³0 (5). Т.о задачу (1),(2) наз. пря­мой, а (4),(5) – двойственной.

Правило перехода от прямой задачи к двойственной. 1.Если исходная за­дача является задачей максимизации, то двойственная – минимизации, и наобо­рот. 2.Количество переменных двойст­венной задачи будет = числу ограниче­ний прямой, а число ограничений двой­ственной = количеству переменных прямой. 3.Матрица ограничений прямой задачи – танспонируется. 4.Если j-ая пе­ременная прямой задачи явл. ограни­ченной, то j-ое ограничение двойст. за­дачи будет неравенство, а если j-ая пе­рем. прямой задачинеограничена, то j-ое ограничение двойств. задачи будет ра­венство. Схема этого правила:

x₁³0…x_k³0

y₁³0 a₁₁ a_1k a_1k+1 a_1n £b₁

………………………………………

y_S³0 a_S1 a_Sk a_Sk+1 a_Sn £b_S

y_S+1³0 a_S+11 a_S+1k a_S+1k+1 a_S+1n £B_s+1

……………………………………….

y_m³0 a_m1 a_mk a_mk+1 a_mn £b_m

³ ³ = =

c₁ c_k c_k+1 c_n

Пр. прямых/ двойственных задач:

1) (c,x)®max (b,y) ®min

Ax=b A^Ty³c

x³0 "y

2) (c,x)®max (b,y) ®min

Ax£b A^Ty³c

x³0 y³0

3) (c,x)®min (b,y) ®max

Ax£b A^Ty=c

"x y³0

 

19.Транспортная задача. Математическая постановка и экономическая интерпретация.

Постановка задачи: Пусть имеется m пунктовпро­изводства однородного продукта A₁, …,A_m с объемами производств a₁,…,1_m и n пунктов потребления B₁,…,B_n с объ­емами потребления b₁,…,b_n. Необходимо составить план перевозки продуктоа изпунктов производства в пункты потребления так, чтобы суммарная стоимость перевозок была минимальной и при этом все потребности были удовлетворены. Стоимость перевозки из i –го пункта производства в j – ый пункт потребле­ния, известна: c_ij. Математическая по­становка задачи:

x_ij – количество продукт, перевозимого от i –го производитель к j –ому потре­бителю. Данная задача содержит m*n переменных и m+n ограничений. Задача (1)-(4) наз. открытой транспортной зада­чей, т.к. (2),(3) –ограничения в виде неравенств. Если выполняются условия: Sa_i=Sb_j (5) тогда ограничения (2),(3): Sх_ij=a_i, i=1..m (2’); Sх_ij=b_j, j=1..n (3’); Транспортная задача, для которой выполняется (5) и соответственно (2’) и (3’) наз. закрытой транспортной задачей. Закрытая транспортная задача всегда имеет решение. Поэтому, если задана открытая транспортная задача, ее при­водят к закрытой вводом фиктивного потребителя/производителя:

Sa_i<Sb_j производителя

Sa_i>Sb_j потребителя. При этом стоимости для фиктивных потребителей/произв. выбираются нулевыми.

Основные св-ва трансп. задачи: 1. Базисное решение будет содержать не бо­лее чем (m+n-1) положительную компо­ненту, т.к. ранг матрицы ограничений =m +n-1 в силу ограничения (5); 2. Если все коэф. в транспортной задаче цело­численны, то решение задачи также бу­дет целочисленным. Нахождение на­чального опорнрго решения: 1) метод северо-западного угла: все время начи­наем с левой верхней клетки Þ название метода. Для этого метода заносить в таблицу стоимости перевозок c_ij не нужно. Выбираем x₁₁=min(a₁,b₁). если x₁₁=a₁ Þ первая строка вычеркивается и далее не участвует в рассмотрении, а b₁ становится =x₁₁. Если x₁₁=b₁ Þ пер­вый столбец вычеркивается и не участ­вует в дальнейшем рассмотрении Þ a₁=x₁₁. Если x₁₁=a₁=b₁ Þ вычеркива­ется и первая строка и первый столбец. Этот случай соответствует вырожден­ному решению. В новой таблице начи­наем с того же угла и действуем анало­гично. Достоинства: простота и алго­ритмичность; Недостатки: не учитыва­ются стоимости перевозок. 2) метод ап­роксимации Фогеля: Для каждой строки и каждого столбца находится модуль разности между минимальным элемен­том и ближайшим к нему по значению. Среди всех найденных разностей нах. максимальная. В строке или столбце, соотв. этой макс. разности, находим ми­нимальный элемент и определяем соотв. объем перевозки x_ij как min(a_i,b_j). Далее действуем аналогично методу 1) и рабо­таем с таблицей меньшего размера. Дос­тоинства: позволяет найти решение близкое к оптимальному. Недостатки: сложная реализация. 3) метод мини­мального элемента: этот метод частично учитывает стоимости перевозок и достаточно прост в реализации. Варианты метода: м-д минимального элемента по столбцу, по строке, по всей таблице. Мы – по всей таблице. Среди всех Cij находим min элемент, для него рассматриваем a_i и b_j, в качестве x_ij=min(a_i,b_j) и далее как в методе северо-заподного угла вычеркиваем и повторяем процедуру для меньшей таблицы.

 

20.Методы отыскания начального опорного плана транспортной задачи.

Постановка задачи: Пусть имеется m пунктовпро­изводства однородного продукта A₁, …,A_m с объемами производств a₁,…,1_m и n пунктов потребления B₁,…,B_n с объ­емами потребления b₁,…,b_n. Необходимо составить план перевозки продуктоа изпунктов производства в пункты потребления так, чтобы суммарная стоимость перевозок была минимальной и при этом все потребности были удовлетворены. Стоимость перевозки из i –го пункта производства в j – ый пункт потребле­ния, известна: c_ij. Математическая по­становка задачи:

x_ij – количество продукт, перевозимого от i –го производитель к j –ому потре­бителю. Данная задача содержит m*n переменных и m+n ограничений. Задача (1)-(4) наз. открытой транспортной зада­чей, т.к. (2),(3) –ограничения в виде неравенств. Если выполняются условия: Sa_i=Sb_j (5) тогда ограничения (2),(3): Sх_ij=a_i, i=1..m (2’); Sх_ij=b_j, j=1..n (3’); Транспортная задача, для которой выполняется (5) и соответственно (2’) и (3’) наз. закрытой транспортной задачей. Закрытая транспортная задача всегда имеет решение. Поэтому, если задана открытая транспортная задача, ее при­водят к закрытой вводом фиктивного потребителя/производителя:

Sa_i<Sb_j производителя

Sa_i>Sb_j потребителя. При этом стоимости для фиктивных потребителей/произв. выбираются нулевыми.

Основные св-ва трансп. задачи: 1. Базисное решение будет содержать не бо­лее чем (m+n-1) положительную компо­ненту, т.к. ранг матрицы ограничений =m +n-1 в силу ограничения (5); 2. Если все коэф. в транспортной задаче цело­численны, то решение задачи также бу­дет целочисленным. Нахождение на­чального опорнрго решения: 1) метод северо-западного угла: все время начи­наем с левой верхней клетки Þ название метода. Для этого метода заносить в таблицу стоимости перевозок c_ij не нужно. Выбираем x₁₁=min(a₁,b₁). если x₁₁=a₁ Þ первая строка вычеркивается и далее не участвует в рассмотрении, а b₁ становится =x₁₁. Если x₁₁=b₁ Þ пер­вый столбец вычеркивается и не участ­вует в дальнейшем рассмотрении Þ a₁=x₁₁. Если x₁₁=a₁=b₁ Þ вычеркива­ется и первая строка и первый столбец. Этот случай соответствует вырожден­ному решению. В новой таблице начи­наем с того же угла и действуем анало­гично. Достоинства: простота и алго­ритмичность; Недостатки: не учитыва­ются стоимости перевозок. 2) метод ап­роксимации Фогеля: Для каждой строки и каждого столбца находится модуль разности между минимальным элемен­том и ближайшим к нему по значению. Среди всех найденных разностей нах. максимальная. В строке или столбце, соотв. этой макс. разности, находим ми­нимальный элемент и определяем соотв. объем перевозки x_ij как min(a_i,b_j). Далее действуем аналогично методу 1) и рабо­таем с таблицей меньшего размера. Дос­тоинства: позволяет найти решение близкое к оптимальному. Недостатки: сложная реализация. 3) метод мини­мального элемента: этот метод частично учитывает стоимости перевозок и достаточно прост в реализации. Варианты метода: м-д минимального элемента по столбцу, по строке, по всей таблице. Мы – по всей таблице. Среди всех Cij находим min элемент, для него рассматриваем a_i и b_j, в качестве x_ij=min(a_i,b_j) и далее как в методе северо-заподного угла вычеркиваем и повторяем процедуру для меньшей таблицы.