Исследование операций в экономике
Для проведения условной оптимизации расстояние от, А до В разделено в восточном направлении на 5 частей, а в северном — на 4 части. Тогда любой путь из, А в В состоит из m = 4 + 5 = 9 отрезков, направленных на восток или на север. Процедуру условной оптимизации будем разворачивать в обратном направлении — от конца к началу. Прежде всего, произведем условную оптимизацию последнего, 9-го шага… Читать ещё >
Исследование операций в экономике (реферат, курсовая, диплом, контрольная)
Задача № 1.
Решить транспортную задачу по данным таблицы 1.
Таблица 1 — Исходные данные.
C. | C2. | C21. | C22. | C23. | C24. | C2. | C31. | C32. | C33. | C34. | C35. | C36. | C40. | C43. | C44. | C. |
N. | A? | A2. | A3. | A? | B? | B? | B3. | B4. | B? | C? | C12. | C13. | ||||
В таблице 1 введены следующие обозначения:
Аi-запасы продукции на i-м пункте отправления (ПО);
Bj-заявки на продукцию от Bj пунктов назначения (ПН);
Cij-стоимость перевозки единицы продукции с i-го ПО в j-й ПН.
Сумма всех заявок должна быть равна сумме всех запасов. Общую стоимость перевозки обозначим Z.
Для сформированной задачи выполнить транспортную таблицу и применить к ней метод циклического переноса.
Решение задачи 1.
Исходя из данных таблицы 1 исходная транспортная таблица имеет вид, представленный в таблице 2.
Таблица 2 Исходная транспортная таблица.
Пункт отправления / Пункт назначения. | заявки на продукцию. | ||||||
b1. | b2. | b3. | b4. | b5. | |||
запасы продукции. | a1. | ||||||
a2. | |||||||
a3. | |||||||
a4. |
Шаг 1: При заполнении таблицы учитывалось условие закрытости транспортной задачи, т. е. сумма всех заявок равна сумме всех запасов: общее число заявок = 87, общие запасы = 87. Задача является сбалансированной (закрытой).
Шаг 2: Начальное опорное решение находится методом минимальной стоимости.
Для этого запасы в Аi пунктов отправления распределяются в соответствии с заявками Bj пунктов назначения и заполняются клетки с минимальными стоимостями перевозок. При этом все запасы должны быть распределены в соответствии с заявками. Хij — количество перевозимого груза.
Опорный план, полученный методом минимальной стоимости.
Вычислим затраты для этого опорного решения:
Zнач = C13? X13 + C14? X14 + C15? X15 + C25? X25 + C33? X33 + C41? X41 + C42? X42 +C44? X44 = 1? 2 + 6? 5 + 4? 4 + 27? 2 + 19? 1 + 14? 2 + 9? 13 + 7? 4 = 204.
Шаг 3: Проверим полученный опорный план на невырожденность. Количество заполненных клеток N должно удовлетворять условию N=n+m-1. В нашем случае N=8, n+m=5+4=9, что удовлетворяет условию невырожденности плана.
Шаг 4: Проведем поэтапное улучшение начального решения, используя метод потенциалов. Для определения сомножителя опорного решения необходимо найти потенциалы заполненных клеток. Сумма потенциалов равна стоимости перевозок.
(ai + bj)= cij.
a1 + b3 = 2.
a1 + b4 = 5.
a1 + b5 = 4.
a2 + b5 = 2.
a3 + b3 = 1.
a4 + b1 = 2.
a4 + b2 = 3.
a4 + b4 = 4.
Пусть a4 = 0. Тогда: a1 = 1; a2 = -1; a3 = 0; a4 = 0; b1 = 2; b2 = 3; b3 = 1; b4 = 4; b5 = 3.
Значение потенциалов записываем в таблицу рядом с Аi и Bj. Проверяем опорное решение на оптимальность для всех незаполненных клеток таблицы.
a1 + b3 — c13 = 1 + 1 — 2 = 0? 0 a1 + b4 — c14 = 1 + 4 — 5 = 0? 0.
a1 + b5 — c15 = 1 + 1 — 4 = -2 < 0 a2 + b5 — c25 = -1 + 3 — 2 = -4 < 0.
a3 + b3 — c33 = 0 + 1 — 1 = 0? 0 a4 + b1 — c41 = 0 + 2 — 2 = 0? 0.
a4 + b2 — c42 = 0 + 3 — 3 = 0? 0 a4 + b4 — c44 = 0 + 4 — 4 = 0? 0.
Начальное опорное решение является оптимальным, т.к. нет положительных оценок. Значение целевой функции: Zопт=204.
2. Задача № 2.
Соорудить траекторию движения ВС, соединяющую т. А и т. В. Затраты на перелет должны быть минимальны. Стоимость полета на каждом отрезке приведена внутри отрезка. Определить условное и безусловное оптимальные управления.
Решение задачи 2.
Динамическое программирование специально приспособлено к так называемым многошаговым операциям.
Процесс динамического программирования разворачивается от конца (т.В) к началу (т.А) — условная оптимизация (условно оптимальное управление и условно минимальные затраты). Затем производится оптимизация от начала (т.А) к концу (т.В) — безусловная оптимизация (безусловно оптимальное управление и безусловно оптимальные затраты).
Для проведения условной оптимизации расстояние от, А до В разделено в восточном направлении на 5 частей, а в северном — на 4 части. Тогда любой путь из, А в В состоит из m = 4 + 5 = 9 отрезков, направленных на восток или на север. Процедуру условной оптимизации будем разворачивать в обратном направлении — от конца к началу. Прежде всего, произведем условную оптимизацию последнего, 9-го шага. Рассмотрим отдельно правый верхний угол нашей прямоугольной сетки. После 8-го шага мы можем быть в точке с затратами либо 7 (В1), либо 8 (В2). Перемещаемся в точку В1, из которой можно двигаться вниз (6 единиц), либо влево (5 единиц). Аналогичные операции проводятся по всем точкам, причем передвигаются в сторону, где затраты меньше. Условно минимальные затраты составили 47, что представлено в таблице 1.
Таблица 3 Процедура условной оптимизации.
В. | ||||||||||
A. |
Затем проводиться безусловная оптимизация с движением из точки, А в точку В, выбирая направления минимальной стоимости, что представлено в таблице 2, траектория, ведущая из, А и В самым дешевым способом отмечена красным цветом.
Таблица 4 Безусловное оптимальное управление.
В. | ||||||||||
3. Задача № 3.
Определить комплексные показатели надежности нерезервированных средств связи. Исходные данные приведены в табл. 3.
Для решения задания 3 необходимо:
- — определить состояние средства;
- — построить размеченный граф состояний;
- — написать систему линейных алгебраических уравнений;
- -установить взаимосвязь между финальными вероятностями и определить их количественные значения.
Таблица 5.
То. | Тв. |
1.5. |
Решение задачи 3.
Наиболее простую структуру имеет нерезервированная система, состоящая из n элементов, у которой отказ одного из элементов приводит к отказу всей системы. В этом случае система S имеет логически последовательное соединение элементов (рисунок 1).
Схема логического соединения элементов нерезервированной системы Нерезервированная восстанавливаемая система в произвольный момент времени находится в одном из двух состояний: работоспособном G0 или неработоспособном G1. Процесс ее функционирования можно отразить графом состояний (рисунок 2):
Граф состояний нерезервированной системы Из состояния S0 в состояние S1 система переходит в результате отказов с интенсивностью л, а из S1 в S0 — в результате восстановления с интенсивностью µ. В дальнейшем будем считать, что потоки отказов и восстановлений являются простейшими: л = const, µ = const. Это значит, что производительность труда ремонтника постоянна и не зависит от времени. Поэтому время восстановления имеет экспоненциальный закон распределения.
;
.
Одним из основных показателей надежности системы является ремонтопригодность — это степень приспособленности системы к предупреждению, обнаружению и устранению отказов. Ремонтопригодность системы можно оценить, например, средним значением времени устранения неисправности, другими словами, средним значением времени восстановления работоспособности после отказа TB.
В задаче TB = 1,5, следовательно µ = 1 / 1,5? 0,667.
Основным показателем надежности нерезервированной восстанавливаемой системы является коэффициент готовности Кг.
Для его определения рассмотрим работу системы на интервале времени (t, t+?t). Обозначим через P0(t), P0(t+?t) и P1(t), P1(t+?t) — вероятности того, что в момент времени t и t+?t система находится в состоянии S0 и S1. Тогда.
P0(t)+P1(t)=1 и Kг=P0(t).
Обозначим также через P01(?t) и P10(?t) — условную вероятность того, что в момент времени t система находится или в состоянии S0 или в состоянии S1, а в момент времени t+?t или в состоянии S1 или в состоянии S0, т. е. за интервал времени? t произошел отказ (восстановление) системы.
Будем считать, что за время? t может произойти только один отказ или только одно восстановление. Тогда на интервале? t могут произойти четыре несовместимые события: A1(S0, S0) — в момент времени t система находилась в состоянии S0, в момент времени t+?t она осталась в том же состоянии, т. е. отказа не произошло;A2(S0, S1) — отказ произошел;A3(S1, S0) — восстановление произошло; A4(S1, S1) — восстановление не произошло.
.
Положим. Тогда получим систему дифференциальных уравнений.
.
которая дополняется условием P0(t)+P1(t).
Решение системы при начальных условиях P0(t)=1 и P1(t)=0, т. е. в начальный момент времени система работоспособна, имеет вид.
.
Если в начальный момент времени система неработоспособна, то P0(0)=0, P1(0)=1 и решение системы имеет вид.
.
При независимо от начального состояния системы (S0 или S1) вероятности Po (t)=Kг, P1(t) стремятся к постоянным значениям.
; .
Это означает, что при экспоненциальных законах распределения времени наработки на отказ и времени восстановления, случайный процесс работы восстанавливаемой системы стабилизируется, и вероятность застать систему работоспособной в произвольный момент времени остается постоянной. Учитывая, что данный процесс является марковским, в системе дифференциальных уравнений при можно положить.
и получить систему линейных алгебраических уравнений, откуда непосредственно находятся P0=Kг и P1:
Для нашего случая нам известно значение µ? 0,667.
В вероятностной трактовке коэффициент готовности определяют по формуле:
.
где To — наработка на отказ (по условию задачи равна 3000),.
TB — среднее время восстановления (по условию задачи равно 1,5).
Следовательно, коэффициент готовности равен Кг = 3000 / (3000 + 1,5) = 0,9995.
Откуда можно определить значение л (по формуле.
? 0,33.
Зная значения л и µ из последней системы уравнений можно определить финальные вероятности Р0 и Р1, которые равны 0,9995 и 0,0005 соответственно.
4. Задача № 4.
Определить показатели надежности резервированных средств связи. Исходные данные приведены в табл. 4.
Для решения задачи 4 необходимо:
- — определить состояние резервированной системы;
- — построить размеченный граф состояний;
- — написать систему линейных алгебраических уравнений Колмогорова;
- — установить взаимосвязь между финальными вероятностями и определить их количественные значения;
- — определить показатели надежности (среднее время безотказной работы и коэффициент готовности резервированной системы).
транспортный затрата нерезервированный алгебраический Таблица 6.
То, ч. | Тв, ч. | Тп, с. |
1.5. |
Решение задачи 4.
В резервированной системе отказ какого-либо элемента не обязательно приводит к отказу всей системы. Типичным случаем является логически параллельное соединение элементов (рисунок 1), при котором система отказывает тогда, когда отказывают все ее элементы. Такой тип резервирования называют постоянным или нагруженным (m-1)-кратным резервированием. В этом случае все элементы выполняют одну и ту же функцию, работают одновременно и равнонадежны.
Схема логического соединения элементов резервированной системы Резервированная восстанавливаемая система описывается графом состояний (рисyнок 2).
Граф состояний резервированной системы В отличие от нерезервированной системы резервированная система имеет 4 состояния: S0 — исправное; S1 — первый полукомплект работоспособен, а второй неисправен (ремонтируется); S2 — второй полукомплект работоспособен, а первый неисправен (ремонтируется); S3 — неработоспособное (оба комплекта ремонтируются).
С учетом условий задачи линейные алгебраические уравнения Колмогорова имеют вид:
- 2 · л · Р0 = µп · (Р1 + Р2) (1)
- (л+ µп) · Р1 = л · Р0 + µв · Р3 (2)
- (л+ µп)· Р2 = л · Р0 + µв · Р3 (3)
- 2 · µв · Р3 = л · (Р1 + Р2) (4) ,
где л и µв — интенсивность отказа и восстановления;
µп — интенсивность переключения.
Система дополняется нормировочным уравнением Р0+Р1+Р2+Р3=1. (5).
Из уравнений (2) и (3) видно, что Р1 = Р2. Тогда уравнение (1) запишется в виде:
или .
Уравнение (4) имеет вид:
.
Уравнение (5) имеет вид:
. .
Р0 = Т0 / (Т0 + 2Тп) = 3000 / (3000+2· 45/3600) = 0,999 991 667.
Р1 = Р0 · Тп / Т0 = 0,999 991 667 · (45/3600) / 3000 = 0,417.
Р2 = Р0 · Тп / Т0 = 0,999 991 667 · (45/3600) / 3000 = 0,417.
Р3 = Р0 · ((Тп· Тв)/ Т0) = 0,999 991 667 · ((45/3600· 1,5)/3000) = 0,625.
Определим среднее время безотказной работы резервированной системы:
Т01 = (Р0 · Тв) / (1- Р0) = (0,999 991 667 · 1,5) / (1 — 0,999 991 667) = 180 000 часов.
В вероятностной трактовке коэффициент готовности определяют по формуле:
.
где To — наработка на отказ (по условию задачи равна 3000),.
TB — среднее время восстановления (по условию задачи равно 1,5).
Следовательно, коэффициент готовности равен Кг = 3000 / (3000 + 1,5) = 0,9995.
Список использованных источников
.
- 1. Вентцель Е. С. Исследование операций. Задачи, принципы, методология / Е. С. Вентцель. — М.: Наука, 1986.
- 2. Кремер Н. Ш. Исследование операций в экономике. Учебное пособие для вузов / Н. Ш. Кремер, Б. А. Путко, И. М. Тришин, М. Н. Фридман. — М.: ЮНИТИ, 2002.
- 3. Демидов Ю. М. Исследование операций. Пособие по выполнению контрольной работы.- М.: МГТУ ГА, 2010; 20 стр.
- 4. Волков И.K., Загоруйко Е. А. Исследование операций. Учебное пособие для вузов / под ред. B.C. Зарубина, A.П. Крищенко. — М.: Изд-во MГТУ им. Н. Э. Баумана, 2002.
- 5. Афанасьев М. Ю., Суворов Б. П. Исследование операций в экономике: модели, задачи, решения. Учебное пособие / М. Ю. Афанасьев, Б. П. Суворов. — М.: ИНФРА-М, 2003.
Размещено на Аllbest.ru.