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

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

 

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

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

Математическая модель задачи ИСО включает в себя:

1) описание переменных, которые необходимо найти

2) описание критериев оптимальности

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

Цель ИСО количественно и качественно обосновать принимаемое решение. Окончательное решение принимает ответственное лицо (либо группа лиц), называемое лицо, принимающее решение (ЛПР). Математическая модель задачи ИСО составляется в соответствии с представлениями ЛПР об этой задаче, т.e. в соответствии с его информационным состоянием.

 

Классификация задач ИСО

 

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

 

1.Статическая задача. Принятие решения происходит при условии, что все параметры задачи заранее известны и не изменяются, но времени. Процедура принятия решения осуществляется один раз.

2. Динамическая задача. В процессе принятия решения параметры задачи изменяются по времени. Процедура принятия решения осуществляется поэтапно и может быть представлена и виде процесса, зависящего от времени, в том числе непрерывно. Пример–навигационная задача.

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

 

1. Детерминированная задача. Все параметры задачи заранее известны. Для решения детерминированных задач в основном применяются методы математического программирования.

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

а) Стохастическая задача. Не все параметры задачи заранее известны, но имеются статистические данные о неизвестных параметрах (вероятности, функции распределения, математические ожидания и т.д.).

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

1. искусственное сведение к детерминированной задаче (неизвестные параметры заменяются их средними значениями).

2. "оптимизация в среднем" (вводится и оптимизируется некоторый статистический критерий).

б) Задача в условиях (полной) неопределенности. Статистические данные о неизвестных параметрах отсутствуют. Задачи ИСО в условиях неопределенности в основном изучаются в рамках теории игр.

Классификация по виду критерия оптимальности.

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

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

· Задачи квадратичного программирования

· Задачи квадратичного программирования

· Задачи стохастического программирования

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

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

· Задачи булева программирования

 

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

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

 

Рассмотрим на конкретном примере.Для изготовления изделий A, B, C и D, фабрика расходует в качестве сырья сталь и цветные металлы, имеющиеся в ограниченном количестве. Указанные изделия производят спомощью токарных и фрезерных станков. Определить план выпуска продукции, при котором будет достигнута максимальная прибыль. Необходимые данные приведены в таблице:

 

 

 

Вид ресурса	Объем ресурса	Нормы расхода на одно изделие
A	B	C	D
Сталь, кг
Цв. Металлы, кг
Токарные станки, станко-час
Фрезерные станки, станко-час
Прибыль, ден. ед.

 

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

2) сформулировать в экономических терминах двойственную задачу и составить еематематическую модель;

3) используя решение исходной задачи и соответствие между двойственными переменными, найти компоненты оптимального плана двойственной задачи — двойственные оценки у*_i;

4) указать наиболее дефицитный и недефицитный (избыточный) ресурс, если он имеется;

5) с помощью двойственных оценок у_i* обосновать рациональность оптимального плана, сопоставив оценку затрат f_min израсходованных ресурсов и максимальный доход z_maxот реализации готовой продукции по всему оптимальному плану и по каждому виду продукции в отдельности;

6) построить матрицу взаимозаменяемости ресурсов;

7) оценить целесообразность приобретения ∆b_k = 3 единиц ресурса Р_kпо цене с_k=0,5 (к=3) за единицу;

8) установить размеры максимальной прибыли при изменении ресурса Р₁, на -20 единиц, Р₂— на 40 единиц, Р₃ — на -10 единиц, Р₄ — на 30 единиц. Оценить раздельное влияние этих изменений и суммарное их влияние на прибыль.

9) установить, целесообразно ли выпускать новую продукцию, на единицу которой ресурсы Р₁, Р₂и Р₃ ,Р₄ расходуются в количествах 12, 5, 17 и 9 единиц, а цена единицы готовой продукции составляет 5 ден. ед.

10) Компьютерная реализация:

10.1. Решить прямую и двойственную задачи. Построить диаграммы по полученным результатам (т.е. представить в виде диаграммы полученные прямое и двойственное решения)

10.2. Создать отчеты по результатам, пределам и устойчивости для прямой и двойственной задач. Дать пояснения к полученным в отчетах результатам и сравнить полученные результаты с результатами п. I. (т.е. с результатами, полученными без использования компьютера)

10.3. Решить задачи из п. I. 8) (4 задачи) и оценить раздельное и суммарное влияние этих изменений с помощью диаграммы.

Решить исходную задачу при условии, что решение должно быть целочисленным.

2.1. Обозначим через Х₁, Х₂, Х₃, Х₄ - количество изделий каждого вида соответственно, планируемого к выпуску, а через f – величину прибыли от реализации этих изделий. Тогда, учитывая значение прибыли от единицы продукции П₁ = 4 ден. ед., П₂= 2 ден. ед., П₃= 4 ден. ед., П₄= 3 ден. ед., запишем сум­марную величину прибыли – целевую функцию в следующем виде:

f = 4Х₁ + 2Х₂ +4Х₃ + 3Х₄ (мах) (2.1)

Переменные Х₁, Х₂, Х ₃, Х₄ должны удовлетворять ограничениям, наклады­ваемым на расход имеющихся в распоряжении предприятия ресурсов. Так, затраты ресурса P₁(сталь, кг) на выполнение плана (Х₁, Х₂, Х₃, Х₄) составят (10Х₁ + 20Х₂ +15Х₃+18Х₄) ед., где 10Х₁ – затраты ресурса P₁ на выпуск Х₁ ед. изделий А; 20Х₂- затраты ресурса P₂ на выпуск Х₂ ед. изделий Б и т.д. Понятно, что указанная сумма не может превышать имеющийся запас P₁ в 250 кг., т.е.

10Х₁ + 20Х₂ +15Х₃+18Х₄≤250 (2.2)

Аналогично получаем ограничение по расходу ресурса P₂ (цветные металлы, кг.)

0Х₁ + 5Х₂ + 8Х₃+ 7Х₄ ≤40 (2.3)

ограничение по расходу ресурсов P₃ (токарные станки, станко-час)

15Х₁ + 18Х₂ +12Х₃+ 20Х₄ ≤100 (2.4)

ограничение по расходу ресурсов P₄ (фрезерные станки, станко-час)

8Х₁ + 12Х₂ + 11Х₃+ 10Х₄ ≤80. (2.5)

По смыслу задачи переменные Х₁, Х₂, Х ₃, Х₄ не могут выражаться отрицатель­ными числами, т.е.

Х_j≥0 (j=1,4) (2.6)

Соотношения (2.1) - (2.6) образуют экономико-математическую модель данной задачи.

Итак, математически задача сводится к нахождению числовых значений Х₁*, Х₂*, Х ₃*, Х₄^* переменных Х₁, Х₂, Х ₃, Х₄, удовлетворяющих линейным нера­венствам (2.2) - (2.6) и доставляющих максимум линейной функции (2.1)

Прежде чем решать задачу линейного программирования симплекс-методом, ее модель приводят к канонической форме. Основным признаком канонической формы является запись ограничений задачи в виде равенств. В нашем же случае ограничения (2.2) - (2.5) имеют вид неравенств типа "≤". Чтобы преобразовать их в эквивалентные уравнения, введем в левые части неравенств дополнительные (балансовые) неотрицательные переменные Х₅, Х₆, Х₇, Х₈, обозначающие разности между правыми и левыми частями этих нера­венств. В результате модель можно записать в виде

f = 75Х₁ + 35Х₂ +40Х₃ +20Х₄ (мах) (2.7)

10Х₁ + 20Х₂ +15Х₃+18Х₄+ Х₅ = 250

0Х₁ + 5Х₂ + 8Х₃+ 7Х₄ + Х₆ = 40

15Х₁ + 18Х₂ +12Х₃+ 20Х₄ + Х₇ = 100 (2.8)

8Х₁ + 12Х₂ + 11Х₃+ 10Х₄ + Х₈ = 80

Х_j≥0 (j=1,8) (2.9)

Заметим здесь же, что дополнительные переменные Х₅, Х₆, Х₇, Х₈имеют вполне определенный экономический смысл - это возможные остатки ресур­сов соответственно P₁, P₂, P₃ ,Р₄. Их еще называют резервами.

Анализируя каноническую модель (2.7) - (2.9), замечаем, что каждая из переменных Х₅, Х₆, Х₇, Х₈ входит только в одно из уравнений системы (2.8). Это обстоятельство свидетельствует о том, что в системе (2.8) переменные Х₅, Х₆, Х₇, Х₈являются базисными, а остальные переменные Х₁, Х₂, Х₃, Х₄ - свободными. В связи с этим в первую симплекс-таблицу систему ограничительных урав­нений (2.7) можно записать в виде, разрешенном относительно базиса Х₅, Х₆, Х₇, Х₈(табл. 2.1).

Таблица 2.1

БП		СП
- Х1	- Х2	- Х3	- Х4
Х5=
Х6=
Х7=		15
Х8=
f		-4	-2	-4	-3

 

Все элементы столбца свободных членов положительны, поэтому со­держащийся в табл. 2.1 план (0; 0; 0; 0; 250; 40; 100; 80), является опорным. Однако этот план не является оптимальным: в f — строке имеются отрицательные элементы. Чтобы получить опорный план, более близкий к оптимальному, выпол­ним симплексное преобразование табл. 2.1. С этой целью выберем перемен­ные, участвующие в преобразовании базиса Х₅, Х₆, Х₇, Х₈в новый базис. Наи­больший по модулю отрицательный элемент (-4) f-строки указывает, что в новый базис следует ввести переменную Х₁,т.е. в качестве разрешающего в предстоящем симплексном преобразовании надо взять первый столбец. Что­бы определить переменную, выводимую из базиса, составляем симплексные отношения и выбираем наименьшее из них

min(250/10; 40/0; 100/15; 80/8)= 100/15 = 6,667

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

В f-строке табл. 2.2 есть отрицательные элементы, значит, опорный план оптимальным не является.

 

 

Таблица 2.2

БП		СП
- Х7	- Х2	- Х3	- Х4
Х5=	183,3	-0,667			4,667
Х6=				8
Х1=	6,667	0,067	1,2	0,8	1,333
Х8=	26,667	-0,533	2,4	4,6	0,667
F	26,667	0,267	2,8	-0,8	2,333

 

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

Таблица 2.3

БП		СП
- Х7	- Х2	- Х6	- Х4
Х5=	148,3	-0,667	3,625	-0,875	-1,46
Х3=			0,625	0,125	0,875
Х1=	2,667	0,0667	0,7	-0,1	0,633
Х8=	3,667	-0,5333	-0,475	-0,575	-4,69
F	30,667	0,2667	3,3	0,1	3,033

 

Следовательно, опорный план (2,667; 0; 5; 0; 148,3; 0; 0; 3,667) является опти­мальным, а соответствующее ему значение 30,667 целевой функции будет макси­мальным.

Итак, по оптимальному плану следует производить 2,667 ед. изделий А; 0 ед. изделий Б; 5 ед. изделий В; 0 ед. изделий С.

При этом предприятие получит максимальную прибыль в размере 30,667 ден. ед. Останут­ся неиспользованными 148,3 ед. ресурса P₁ (сталь, кг.), и 3,667 ед. ресурса Р₄ (фрезерные станки, станко-час), а ресурсы P₂ и Р₃ будут израсходо­ваны полностью.

2.2. Двойственная переменная Y_i. выступает коэффициентом при b_i,следовательно, определяет зависимость целевой функции от изменения ресурсов b_i на единицу.

Чтобы составить модель двойственной задачи, напишем матрицу ис­ходной

задачи (2.1)- (2.6) в следующем виде:

				fmax

 

Транспонируем матрицу (2.11). В результате получим матрицу (2.12) двойственной задачи:

				φ min

 

По матрице (2.12) легко написать модель задачи, двойственной к ис­ходной задаче:

φ = 250Y₁ + 40Y₂ +100Y₃+ 80Y₄ (min) (2.13)

 

10Y₁ + 0Y₂+ 15Y₃+ 8Y₄ ≥4

20Y₁ + 5Y₂ + 18Y₃+ 12Y₄ ≥2

15Y₁ + 8Y₂ +12Y₃+ 11Y₄ ≥4 (2.14)

18Y₁ + 7Y₂+ 20Y₃+ 10Y₄ ≥3

 

Y_i≥0 (j=1,3) (2.15)

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

В п. 1 мы нашли оптимальный план исходной задачи, его компоненты находятся в табл. 2.3. В f-строке этой же таблицы содержатся и компоненты Y_i* оптимального плана двойственной задачи (2.13) - (2.15). Выписать ком­поненты Y_i* поможет соответствие между переменными двойственных задач. Чтобы установить это соответствие, преобразуем ограничения-неравенства (2.14) в эквивалентные уравнения, вычитая из левых частей до­полнительные неотрицательные переменные Y₁, Y₂ и Y₃,Y₄ равные разностям между левыми и правыми частями этих неравенств. Тогда модель (2.13)-- (2.15) запишется в виде

φ = 250Y₁ + 40Y₂ +100Y₃+ 80Y₄ (min)

10Y₁ + 0Y₂+ 15Y₃+ 8Y₄ – Y₅= 4

20Y₁ + 5Y₂ + 18Y₃+ 12Y₄ – Y₆= 2

15Y₁ + 8Y₂ +12Y₃+ 11Y₄ - Y₇= 4

18Y₁ + 7Y₂+ 20Y₃+ 10Y₄ - Y₈= 3

Y_i≥0 (j=1,8)

В этой записи переменные Y₅, Y₆ и Y₇, Y₈ являются базисными, а Y₁, Y₂ и Y₃, Y₄ - свободными. В исходной задаче (2.7) - (2.9) переменные Х₁, Х₂ и Х₃, Х₄ яв­ляются свободными, a Х₅, Х₆ и Х₇, Х₈ - базисными.

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

 

Х₅ÛY₁, Х₆ÛY₂, Х₇ÛY₃, Х₈ÛY₄, Х₁ÛY₅, Х₂ÛY₆ , Х₃ÛY₇, Х₄ÛY₈.

 

(2.16)

 

Воспользуемся соответствием (2.16) следующим образом. Как видно, переменная Y₁ связана с переменной Х₅ (поэтому их называют двойственными переменными), а в табл.2.3 переменная Х₅ находится в базисе, значит, двой­ственная ей переменная Y₁ на этом этапе расчетов является свободной и, как свободная переменная, равна нулю (в любой двойственной паре всегда одна переменная базисная, а другая свободная). Итак, Y₁* = 0. Далее, Y₂ соответст­вует Х₆, а в табл.2.3 под Х₆ в f- строке находится элемент 0,1, следовательно, Y₂* = 0,1. Точно так же устанавливается, что Y₃* = 0,2667; Y₄* = 0; Y₅* = 0; Y₆* = 3,3; Y₇* = 0; Y₈* =3,033.

Из теорем двойственности следует, что экстремальные значения целе­вых функций разрешимых двойственных задач совпадают, поэтому φ_min = f_max = = 30,667.

2.4. Оценки ресурсов Р₂ и Р₃являются положительными, следовательно эти виды сырья используется постоянно и является дефицитным. Наиболее дефицитным ресурсом будет ресурс Р₃, так он имеет наибольшую оценку. Избыточным ресурсами является ресурсы Р₁и Р₄, так как их оценки равны нулю.

2.5. Чтобы определить изменение максимальной прибыли при изменении ресурсов, необходимо найти интервалы устойчивости двойственных оценок, в пределах которых они точно измеряют влияние ограничений на целевую функцию.Определим интервал устойчивости по отношению к ограничению по ресурсу 1-го вида. Для этого выпишем матрицу из коэффициентов при базисных неизвестных. Базисными переменными в оптимальном решении являются Х₄, Х₆, Х₇, Х₁. Матрица коэффициентов при этих переменных в системе ограничений имеет вид:

 

Обратная матрица

 

	-0,875	-0,667
	0,125
	-0,1	0,0667
	-0,575	-0,533

используя формулы ; , находим

min (148,3/1)= 148,3

∞

В соответствии с формулой: , интервал устойчивости оценок по отношению к первому ресурсу примет вид: (250 – 148,3; 250 + ∞) = (101,7; ∞)

Аналогично находим интервал устойчивости для остальных видов ресурсов.

5/0,125 = 40 3,667/0,575 = 6,377

Р₂:(40 – 40; 40 + 3,677) = (0; 43,677)

 

2,6667/0,06667 = 40 3,667/0,533 = 6,875

Р₃:(100 – 40; 100 + 6,875) = (60; 106,875)

 

3,667/1 = 3,667 ∞

Р₄:(80 – 3,667; 80 + ∞) = (76,333; +∞)

Величина двойственной оценки численно равна изменению целевой функции при изменении соответствующего ресурса на одну единицу.

При увеличении ресурса Р₂ на одну весовую единицу значение целевой функции оптимального плана увеличится на 0,1 ден. ед. При увеличении ресурса Р₃ на одну весовую единицу значение целевой функции оптимального плана увеличится на 0,2667 ден. ед. Оценки ресурсов Р₁ и Р₄ равны нулю, следовательно данные ресурсы не является дефицитным, при их увеличении значение целевой функции не изменится. Оценка изделий Б и С больше нуля, следовательно производство данных изделий не будет рентабельным и при производстве одной единицы изделия Б значение целевой функции оптимального плана уменьшится на 3,3 ден. ед., а при производстве одной единицы изделия С значение целевой функции оптимального плана уменьшится на 3,033ден. ед.

 

 

2.6. Матрица коэффициентов взаимозаменяемости ресурсов:

	-0,875	-0,667
	0,125
	-0,1	0,0667
	-0,575	-0,533

 

2.7. Оценим целесообразность приобретения Db= 3 единиц ресурса P₃по цене c₃=0,5 заединицу. Определим значение ∆ = y₃ – C₃ = 0,1 – 0,5 = -0,4. Увеличение прибыли при закупке 1 единицы ресурса Р₃ меньше цены данного ресурса, следовательно не имеет смысла закупать данный ресурс.

 

2.8. Изменение второго вида ресурса не находится в пределах устойчивости оценок, следовательно мы не можем оценить влияние изменения на целевую функцию. Изменения ресурсов 1, 3, 4 находятся в пределах устойчивости оценок, то их раздельное влияние на величину прибыли, Df_imax определяется произведением оценки y_i и величины изменения Db_i.

Df_1max=Db₁·y₁= -20· 0= 0 ден. ед.

Df_3max=Db₃·y₃= -10·0,2667 = -2,667 ден. ед.

Df_4max=Db₄·y₄= 30·0 = 0 ден. ед.

Суммарное влияние Df_max=Df_1max+Df_3max +Df_4max= 0 – 2,667 + 0= -2,667 ден. ед.

 

2.9. Установим, целесообразно ли выпускать новую продукцию, на единицу которой ресурсы Р₁, Р₂ и Р₃, Р₄ расходуются в количествах 12; 5; 17 и 9 единиц, а цена единицы готовой продукции составляет 5 ед. Для этого вычисляем характеристику:

(12·0+ 5·0,1+ 17·0,2667+ 9) – 5 = 0,0339 > 0

Так как прибыль не превышает затраты то введение в план производства нового изделия не целесообразно.

3.5.

 

Оптимальное значение целевой функции при целочисленном решении будет 28 ден.ед., что на 2,667 ден. ед. меньше, чем при нецелочисленном решении.

 

 

Заключение

По произведенным нами расчетам можем сказать следующее. Согласно оптимальному плану рассматриваемой нами задачи следует производить 2,667 ед. изделий А; 0 ед. изделий Б; 5 ед. изделий В; 0 ед. изделий С. При этом предприятие получит максимальную прибыль в размере 30,667 ден. ед. Останут­ся неиспользованными 148,3 ед. ресурса P₁ (сталь, кг.), и 3,667 ед. ресурса Р₄ (фрезерные станки, станко-час), а ресурсы P₂ и Р₃ будут израсходо­ваны полностью.

Основываясь на решении двойственной задачи, можем отметить, оценки ресурсов Р₂ и Р₃являются положительными, следовательно эти виды сырья используется постоянно и является дефицитным. Наиболее дефицитным ресурсом будет ресурс Р₃, так он имеет наибольшую оценку. Избыточным ресурсами является ресурсы Р₁и Р₄, так как их оценки равны нулю.

Величина двойственной оценки численно равна изменению целевой функции при изменении соответствующего ресурса на одну единицу. При увеличении ресурса Р₂ на одну весовую единицу значение целевой функции оптимального плана увеличится на 0,1 ден. ед. При увеличении ресурса Р₃ на одну весовую единицу значение целевой функции оптимального плана увеличится на 0,2667 ден. ед. Оценки ресурсов Р₁ и Р₄ равны нулю, следовательно данные ресурсы не является дефицитным, при их увеличении значение целевой функции не изменится. Оценка изделий Б и С больше нуля, следовательно производство данных изделий не будет рентабельным и при производстве одной единицы изделия Б значение целевой функции оптимального плана уменьшится на 3,3 ден. ед., а при производстве одной единицы изделия С значение целевой функции оптимального плана уменьшится на 3,033 ден. ед.

Реализовывать новую товарную группу, на единицу которой ресурсы Р₁, Р₂ и Р₃, Р₄ расходуются в количествах 14; 20; 25; 90 единиц, а цена реализации составляет 10 ден. ед. не целесообразно, так как затраты на её реализацию не превышают прибыль при её продаже.

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

Изменение второго вида ресурса не находится в пределах устойчивости оценок, следовательно мы не можем оценить влияние изменения на целевую функцию. Изменения ресурсов 1, 3, 4 находятся в пределах устойчивости оценок, то их раздельное влияние на величину прибыли, Df_imax определяется произведением оценки y_i и величины изменения Db_i.

Df_1max0ден. ед.; Df_3max= -2,667 ден. ед.; Df_4max= 0 ден. ед.

Суммарное влияние Df_max=Df_1max+Df_3max +Df_4max= 0 – 2,667 + 0= -2,667 ден. ед.

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

 

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

 

[1] Taha, Н. Operationsresearch

[2] Орлов А.И., Основы теории принятия решений. Учебное пособие. Москва, 2002.

[3] Новикова, Н.А. Исследование Операций, Минск.2010

[4] Лемешко Б.Ю., Теория игр и исследование операций. Новосибирский государственный технический университет, 2013

[5] Алексеев Е.Р., Павловская Е.В., Чеснокова О.В., Ломовцева О., Решение задач оптимизации и линейного программирования с помощью современных программных средств.

 

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

 

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

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

Математическая модель задачи ИСО включает в себя:

1) описание переменных, которые необходимо найти

2) описание критериев оптимальности

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

Цель ИСО количественно и качественно обосновать принимаемое решение. Окончательное решение принимает ответственное лицо (либо группа лиц), называемое лицо, принимающее решение (ЛПР). Математическая модель задачи ИСО составляется в соответствии с представлениями ЛПР об этой задаче, т.e. в соответствии с его информационным состоянием.

 

Классификация задач ИСО

 

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

 

1.Статическая задача. Принятие решения происходит при условии, что все параметры задачи заранее известны и не изменяются, но времени. Процедура принятия решения осуществляется один раз.

2. Динамическая задача. В процессе принятия решения параметры задачи изменяются по времени. Процедура принятия решения осуществляется поэтапно и может быть представлена и виде процесса, зависящего от времени, в том числе непрерывно. Пример–навигационная задача.

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

 

1. Детерминированная задача. Все параметры задачи заранее известны. Для решения детерминированных задач в основном применяются методы математического программирования.

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

а) Стохастическая задача. Не все параметры задачи заранее известны, но имеются статистические данные о неизвестных параметрах (вероятности, функции распределения, математические ожидания и т.д.).

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

1. искусственное сведение к детерминированной задаче (неизвестные параметры заменяются их средними значениями).

2. "оптимизация в среднем" (вводится и оптимизируется некоторый статистический критерий).

б) Задача в условиях (полной) неопределенности. Статистические данные о неизвестных параметрах отсутствуют. Задачи ИСО в условиях неопределенности в основном изучаются в рамках теории игр.

Классификация по виду критерия оптимальности.

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

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

· Задачи квадратичного программирования

· Задачи квадратичного программирования

· Задачи стохастического программирования

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

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

· Задачи булева программирования

 

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ