Задачу о надежности

Шаг.

Шаг.

Шаг.

Шаг.

1) Зафиксируем y₄=0. Тогда допустимые значения x₄Î[0, 4-0]=[0,1,2,3,4].

1.1) x₄=0. Тогда F₄(0)=0.

1.2) x₄=1. F₄(1)=9.

1.3) x₄=2. F₄(2)=19.

1.4) x₄=3. F₄(3)=26

1.5) x₄=4. F₄(4)=35.

Максимальное значение , и достигается оно при x₄=4. Таким образом, заполняется первая строчка таблицы.

2) Зафиксируем y₄=1. Тогда допустимые значения x₄Î[0, 4-1]= [0,1,2,3].

2.1) x₄=0. Тогда F₄(0)=0.

2.2) x₄=1. F₄(1)=9.

2.3) x₄=2. F₄(2)=19.

2.4) x₄=3. F₄(3)=26

Максимальное значение , и достигается оно при x₄=3. Таким образом, заполняется вторая строка таблицы.

Далее аналогично фиксируем y₄=2, y₄=3, y₄=4. Заполняем оставшиеся строки таблицы.

Таблица шага №1.

y4 x4
					-
				-	-
			-	-	-
		-	-	-	-

1) Зафиксируем y₃=0. Тогда допустимые значения x₃Î[0, 4-0]=[0,1,2,3,4].

1.1) x₃=0. Тогда F₃(0)=0. Определим значение второго слагаемого: при y₃=0 и x₃=0. Найдем y₄=0+0=0. Тогда, обратившись к таблице шага 1, увидим, что . Следовательно, F₃(0)+ =0+35=35. Этот результат заносим в таблицу шага 2 в ячейку, соответствующую y₃=0 и x₃=0.

1.2) x₃=1. Аналогично: F₃(1)=10. Найдем y₄= y₃+ x₃=0+1=1. Из таблицы шага 1 определим: =. Сумма

F₃(1)+ =10+26=36.

1.3) x₃=2. F₃(2)=18. y₄=0+2=2. Þ ==19. Тогда F₃(2)+ =18+19=37.

1.4) x₃=3. F₃(3)=24, y₄=0+3=3. Þ ==9. Тогда

F₃(3)+ =24+9=33.

1.5) x₃=4. F₃(4)=34. y₄=0+4=4. Þ ==0. Тогда

F₃(4)+ =34+0=34.

Максимальное значение =37, и достигается оно при x₃=2. Первая строчка таблицы заполнена.

2) Зафиксируем y₃=1. Тогда допустимые значения x₃Î[0, 4-1]= [0,1,2,3].

2.1) x₃=0. F₃(0)=0. y₄=1+0=1. Þ ==26. Тогда

F₃(0)+ =0+26=26.

2.2) x₃=1. F₃(1)=10. y₄=1+1=2. Þ ==19. Тогда

F₃(1)+ =10+19=29.

2.3) x₃=2. F₃(2)=18. y₄=1+2=3. Þ ==9. Тогда

F₃(2)+ =18+9=27.

2.4) x₃=3. F₃(3)=24 y₄=1+3=4. Þ ==0. Тогда

F₃(3)+ =24+0=24.

Максимальное значение , и достигается оно при x₃=1. Таким образом, заполняется вторая строка таблицы.

3) Зафиксируем y₃=2. Тогда допустимые значения x₃Î[0, 4-2]= [0,1,2].

3.1) x₃=0. F₃(0)=0. y₄=2+0=2. Þ f₄ (2) =19. F₃(0)+ f₄ (2)=0+19=19.

3.2) x₃=1. F₃(1)=10. y₄=2+1=3. Þ =9. F₃(1)+ =10+9=19.

3.3) x₃=2. F₃(2)=18. y₄=2+2=3. Þ =0. F₃(2)+ =18+0=18.

Максимальное значение достигается при двух возможных значениях x₃: x₃=1 и x₃=0. В таблицу можно занести любое из них. Таким образом, заполняется третья строка таблицы.

Далее аналогично фиксируем y₃=3, y₃=4. Заполняем оставшиеся строки таблицы.

Таблица шага №2.

y3 x3
					-
				-	-		0 (или 1)
			-	-	-
		-	-	-	-

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

Таблица шага №3.

y2 x2
					-
				-	-
			-	-	-
		-	-	-	-

Последний шаг интересен тем, что здесь решается единственная задача максимизации при заданном y₁=0.

y₁=0. Следовательно x₁Î[0, 4-0]= [0,1,2,3,4]. Выполняя все действия, аналогично предыдущим шагам, получим таблицу последнего шага, состоящую из единственной строки, соответствующей y₁=0.

Таблица шага №4.

y1 x1
							0 (или 1)

Далее проводим обратное движение алгоритма:

1) y₁=0, x₁*=0, Þ y₂*= y₁+ x₁*=0+0=0.

2) Определяем значение x₂* из таблицы шага № 3 по найденному y₂*=0. Значению y₂= y₂*=0 соответствует значение x₂(y₂)=1. Следовательно, x₂*=1. Далее можно определить y₃*= y₂*+ x₂*=0+1=1.

3) Аналогично, обращаясь к таблице шага №2, найдем: x₃*= x₃(1)=1, Þ

y₄*= y₃*+ x₃*=1+1=2.

4) Из таблицы шага №1: x₄*= x₄(2)=2.

Окончательно имеем: первому предприятию средства не выделяются (x₁*=0), второму выделяется 1 млн. у.е. (x₂*=1), третьему предприятию – 1 млн. у.е. (x₃*=1), и четвертому – 2 млн. у.е. (x₄*=2). При этом значение целевой функции (общая прибыль по всем 4-м предприятиям) составит:

==40.

Метод динамического программирования для ЗНП с мультипликативной целевой функцией. Задача о надёжности.

Пусть имеется оптимизационная задача вида:

(1)

(2)

(3)

-задан (4)

Здесь предполагается, что F_j(x_j,y_j)>0 для всех допустимых значений x_j,y_j. В этом случае для решения задачи (1)-(4) рекуррентные соотношения Беллмана имеют вид:

(5)

, (6)

При j=1 величина y₁ задана, поэтому в этом случае решается только одна задача максимизации.

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

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

В качестве примера рассмотрим

Пусть конструируется электронный прибор, состоящий из трех основных компонентов. Все компоненты соединены последовательно, поэтому выход из строя одной из них приводит к отказу всего прибора. Надежность (вероятность безотказной работы) прибора можно повысить путем дублирования каждого компонента. Конструкция прибора позволяет использовать запасных блоков для каждого j-того компонента, т.е. каждый компонент может содержать до блоков, соединенных параллельно. Общая стоимость прибора не должна превышать С долларов. Если j-тый компонент имеет штук соединенных параллельно блоков, то его надежность составляет и стоимость . Требуется определить количество блоков в каждом j-том компоненте , при котором надежность прибора максимальна, а стоимость прибора не превышает заданной величины С.

Построение ММ. По определению, надежность F прибора, состоящего из N последовательно соединенных компонентов, каждый из которых включает параллельно соединенных блоков, равна произведению надежности компонент. Тогда ММ имеет вид:

(7)

(8)

, (9)

Из физического смысла задачи следует, что , >0 для всех допустимых .

Введем дополнительную переменную - количество средств, израсходованных на дублирование компонент 1,2,… j-1. Тогда можно записать:

(10)

(11)

Из (10) следует: . Тогда с учетом (9) область допустимых значений будет иметь вид , а рекуррентные соотношения Беллмана принимают вид:

(12).

(13)

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

Здесь , есть область изменения при фиксированном .

Дата добавления: 2014-01-11