Задача с мультипликативным критерием

Возьмем задачу с неаддитивной целевой. В качестве примера рассмотрим задачу о надежности некоторого устройства, состоящего из N последовательно соединенных блоков. Повышение надежности устройства обеспечивается включением дублирующих элементов в отдельные блоки. В общем случае ограничивающими факторами могут выступать затраты на дублирование, вес и/или объем устройства, надежность переключательных схем и др. Пусть основным ограничением являются затраты на дублирование Q и, кроме того, известны С_j - стоимость одного дублирующего элемента для блока j и j_j (m_j) - вероятность безотказной работы j -го блока с m_j дублирующими элементами. Задача состоит в определении оптимальной стратегии дублирования в пределах выделенных средств. В качестве критерия следует взять вероятность безотказной работы всего устройства P, которая при последовательном соединении блоков равна произведению вероятностей этих блоков. Поэтому модель задачи будет иметь вид

, . В этой модели целевая функция - мультипликативная, не мешает применению метода ДП. Задача представима как многошаговая, а шаг - определение числа дублирующих элементов для одного блока. В последовательности шагов расположение блоков может не соответствовать реальной схеме их соединения в устройстве. Пронумеруем шаги справа налево. Параметр состояния - допустимый уровень затрат на дублирование q, который на любом шаге может принимать любые значения из диапазона [0,Q]. Теперь можно ввести последовательность функций { f_k (q)}, k =1, N. Каждая функция имеет смысл максимальной вероятности безотказной работы k оставшихся блоков при допустимом уровне затрат на дублирование q: .

Для получения функционального уравнения рассмотрим k блоков, на дублирование которых можно затратить q средств. Если в k -й блок включить m _k дублирующих элементов, а оставшиеся после этого средства (q-С_km_k) использовать оптимально на дублирование k -1 блоков, вероятность безотказной работы k блоков будет равна

[ j_k (m_k) f_{k -1}(q-С_km_k)]. Максимизируя это выражение по m _k, приходим к искомому рекуррентному соотношению

где [ q / С_k ] означает целую часть от q / С_k. Условная оптимизация начинается с вычисления первой функции последовательности . Безусловная оптимизация проводится в обратном порядке, то есть от f_N к f ₁, с исходного состояния q_N =Q и последующим пересчетом по уравнению состояния q_{k -1} = q_k - С_km_k.

Таким образом, мультипликативность целевой функции не изменяет процедуру ДП. Отличие от ранее рассмотренных задач лишь в том, что выражение в правой части рекуррентного соотношения не аддитивное, а мультипликативное. Мультипликативность ограничения или одновременно ограничения и целевой функции также не вызовет осложнений.

50. ДП: организация выпуска m видов продукции.

Фирма ежемесячно выпускает m видов продукции, на которые имеется равномерный спрос. По каждому виду продукции известны: С _{1 i} - затраты на хранение единицы продукции i -го вида в единицу времени; С _{2 i} - затраты на запуск в производство одной партии i -го вида; R_i - месячный спрос на продукцию i -го вида. Для выпуска одной партии требуется один цикл производства. Изменение числа партий приводит к изменению затрат на производство одного и того же количества продукции. В течение месяца фирма может организовать не более N циклов. В этих условиях нужно так организовать производство, чтобы при полном удовлетворении спроса обеспечить минимальные затраты фирмы.

Допущение: время выпуска партии много меньше продолжительности цикла и поэтому им можно пренебречь. График изменения уровня готовой продукции на фирме представлен на рис

где - объем партии продукции i -го вида; t_i - продолжительность цикла по i -му виду продукции (в долях месяца).

 

Затраты на хранение и выпуск партии i -го вида продукции за время 1 цикла - а т.к кол-во циклов, необх. для выпуска продукции в объеме R_i: то затраты на весь объем продукции i -го вида: .

Критерий задачи . Ограничения

Параметр состояния - n - максимальное количество циклов, которое может быть организовано для выпуска продукции (1£ n £ N), Шаг - организация выпуска одного вида продукции. Введем последовательность функций { f_n (n)}, так, что каждая функция определяется как минимальные затраты на выпуск k видов продукции в заданных количествах при условии, что можно организовать до n циклов, то есть Опущен индекс у n, так как он совпадает с индексом функции. Затраты на k видов: Q _k (u_k) + f_{k -1}(n-u_k). Уравнение состояния n_{k -1}= n_k – u_k. Рекуррентное соотношение .

Выпуск продукции оговорен величиной R_i, поэтому, чтобы обеспечить выпуск k -1 видов продукции, нужно иметь хотя бы по одному циклу на каждый вид и, следовательно, максимальное число циклов на k -й вид равно n -(k -1). Первая функция: . Пример: 3 вида продукции, N =7. Условная оптимизация начинается с вычисления функции f ₁. При этом можно воспользоваться классическим методом, так как требуется найти минимум дифференцируемой функции на интервале. Приравняв первую производную выражения в скобках правой части нулю, найдем стационарную точку . С учетом ограничений на u ₁ оптимальное решение будет иметь вид:

n
			83,3

где [ ] - целая часть . По исходным данным получаем = 9. Расчетная формула: , по которой составляем табл.

 

На втором шаге расчет ведем по рекуррентной формуле: где .

		n
U 2	Q2 (u 2 )
		f 1(n)
				83,3
		-	170 378	100	83,3 291,3	80	80	80
			-	170	100	83,3 199,3	80	80
	90,7			-	90,7 170 260,7	90,7 100 190,7	90,7 83,3 174,0	90,7 80 170,7
					-	170	100	83,3 165,3
						-	170	100
	81,3						-	81,3 170 251,3
		-
		-				190,7		165,3

Находить минимум будем перебором допустимых u ₂. Для удобства ручных расчетов в промежуточную таблицу предварительно внесем во второй столбец значения Q₂(u ₂) для всех возможных u ₂ и во вторую строку значения f ₁(n), взятые из 1. Для отыскания минимума сначала фиксируем состояние, то есть значение n, а затем ведем перебор u ₂. Начнем с n =1. Расчет выпуска двух видов продукции в этом случае теряет смысл, так как на 2-й вид не остается ни одного цикла - во всех клетках столбца с этим значением n ставим прочерк. Берем n =2. При этом возможен только один вариант: на 2-й вид продукции отводится один цикл. Соответствующие затраты составят

Q₂(1) + f ₁(2-1)=208+170=378,

Эти значения затрат и числа циклов являются оптимальными относительно состояния n =2 и поэтому их записываем в клетки нижних строк как значения u ₂^* и f ₂(n). Теперь фиксируем n =3 и вычисляем затраты u ₂: при u ₂=1 Q₂(1) + f ₁(3-1)=208 + 100=308, при u ₂=2 Q₂(2) + f ₁(3-2)=116 + 170=286.

		n
U 3	Q3(u 3)
		f 2(n)
					190,7		165,3
		-	378 628	286	216	190,7 440,7	174
	132,5		-	132,5 378 510,5	132,5 286 418,5	132,5 216 348,5	132,5 190,7 323,2
	96,7			-	96,7 378 474,7	96,7 286 382,7	96,7 216 312,7
	81,2				-	81,2 378 459,2	81,2 286 367,2
						-	378
		-
		-		510,5	418,5	348,5	312,7

Теперь переходим к третьему шагу расчета, Рекуррентная формула:

.

Схема расчета полностью идентична 2-му шагу, но расчет по трем видам продукции приобретает смысл начиная с n =3.

Далее следует безусловная оптимизация. Пусть для выпуска трех видов продукции можно организовать 5 циклов (N =5). Тогда по начальному состоянию n =5 входим в табл. 3 Из нее устанавливаем, что минимальные затраты на три вида продукции составляют 418,5, при этом по 3-му виду должно быть организовано 2 цикла, то есть весь заказ выполняется двумя запусками. На остальные два вида остается 3 цикла. Поэтому по состоянию n =3 входим в табл. 2, и извлекаем из нее u ₂^*=2,. Соответствующая величина f ₂(3)=286 означает затраты на 1-й и 2-й виды продукции при оптимальной организации производства. Новое состояние n =3-2=1 определяет вход в табл. 1, из которой берем u ₂^*=1, и тем самым завершаем нахождение оптимального решения.

51. ДП: задача об инвестициях.

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

Нужно рассчитать план инвестиций на n периодов.

На начало периода имеются средства в количестве Х.

В начале периода акции покупаются, в конце продаются.

Доходность на единицу вложения является случайной величиной. Есть m возможных ситуаций, каждой из которых соответствуют своя вероятности , того что доход будет .

– это доход в j -ый период на i -ой ситуации, которому соответствует вероятность .

Переменными в задаче будут тот объём средств , который мы можем вложить в j -ый период, причём , т.е. объём инвестиций в периоде не может превысить объём средств имеющихся на начало периода.

Критерием является ожидаемый доход.

Нумеровать будем с конца.

Переменная состояния: количество средств на начало периода.

Ожидаемый доход за последние k шагов.

 

 

 

Для учёта инфляции (дисконтирования дохода) можно ввести коэффициент в формулу, который показывает инфляцию в j-ый период:

52. ДП: многомерные задачи и проблемы решения.

Если размерность вектора S (число параметров состояния) больше 1, то говорят, что задача многомерна в смысле ДП. Многомерные задачи порождают определенные проблемы при реализации вычислительной схемы метода ДП. Примеры.

Задача 1. Необходимо распределить два вида ресурсов в объеме X и Y соответственно между N производствами при известных функциях прибыли R_j (x_j, y_j), j =1, N. Здесь x_j, y_j - количество ресурса 1-го и 2-го вида, потребляемое j -м производством.

Запишем модель задачи:

Задача представима как N -шаговая (по числу производств). При выделении ресурсов одному из производств изменяется объем ресурсов, направляемых на остальные производства. Поэтому состояние характеризуется двумя параметрами: количеством ресурса 1-го вида V и 2-го вида U (V Ј X, U Ј Y). Введем последовательность функций:

и рассмотрим k оставшихся производств (шагов), между которыми нужно распределить ресурсы в количестве V и U. Приняв решение о выделении k -му производству произвольного допустимого количества ресурсов x_k и y_k, будем иметь прибыль от этого производства R_k (x_k, y_k), а на остальные k -1 шагов останется ресурсов V - x_k 1-го вида и U - y_k 2-го вида. Следуя принципу оптимальности, распределим оставшиеся ресурсы оптимальным образом f_{k -1}(V - x_k, U - y_k). Прибыль от всех k шагов составит R_k (x_k, y_k)+ f_{k -1}(V - x_k, U - y_k). Рекуррентное соотношение:

Задача 2. Распределению подлежит один вид ресурса, но в системе имеются ограничения, связанные с его использованием. Это могут быть ограничения на общий объем, вес, габариты, стоимость и др. Рассмотрим случай двух ограничений, согласно которым фактические значения учитываемых показателей использования ресурса не могут превышать величин A и B. Тогда модель задачи можно представить в виде:

где x_i - количество ресурса, выделяемое i -му потребителю; Z_i (x_i) - показатель эффективности i -го потребителя; j_i (x_i), y_i (x_i) - функции ограничиваемых показателей. Ограничивающие показатели a и b выступают в качестве параметров состояния (a Ј A, b Ј B). Определим функции последовательности:

Рекуррентное соотношение:

Увеличение числа параметров состояния для задачи 1: Решение уравнения проводится для всех возможных состояний. Число таких состояний зависит от шага дискретности и числа параметров состояния. Пусть m_x и m_y - число возможных значений ресурсов X и Y соответственно, тогда число возможных состояний будет равно m_xm_y. Для каждого из них в результирующей таблице решения уравнения на k -м шаге должны быть представлены V, U, , и f_k (V, U). Вынос этих таблиц во внешнюю память сделает метод ДП практически малопригодным, так как затраты времени на решение задачи многократно увеличатся. Решение многомерных задач наталкивается на проблему реализации вычислений по рекуррентным соотношениям. Одним из путей решения возникшей проблемы является использование множителей Лагранжа.

53. ДП: снижение размерности с помощью множителей Лагранжа

(Примеры из билета 52) Пример: В задаче 1 состояние описывалось двумя параметрами, что обусловливалось наличием двух ограничений. Для уменьшения размерности на 1 достаточно из модели убрать одно из ограничений, удаляемое ограничение включить в критерий задачи с неопределенным множителем Лагранжа l. Модель задачи:

Так как 1 ограничения не связывают между собой переменные y_j, то есть они стали независимыми, то справедлива следующая цепочка равенств:

где . Функции h_j (x_j) имеют смысл, если максимум достигается при конечных значениях y_j. Вычисление функции h_j (x_j) при фиксированном значении заключается в нахождении максимума функции одной переменной для всех возможных значений x_j, что не вызывает особых затруднений (для дифференцируемых R_j (x_j, y_j) максимум можно найти аналитически). При известных h_j (x_j), j =1, N задача сводится к следующей: Получили задачу распределения одного ресурса. Для решения ее методом ДП введем последовательность функций , где V - параметр состояния, значения которого не превосходят X. Рекуррентное соотношение: f_k (V) = max[ h_k (x_k)+ f_{k -1}(V - x_k)],

в котором f ₁(V)= h ₁(V), = V. Вычисления проводятся, как обычно, от f ₁ к f_N, затем в обратном порядке - безусловная оптимизация, начиная с V = X, которая дает значения . По последним из функций h_j (x_j) находятся значения . Если å = Y, то найденное решение , является оптимальным решением задачи. В противном случае придется продолжить расчеты. При невыполнении условия нужно изменить значение и повторить весь расчет, начиная с вычисления функций h_j (x_j).

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

. (1) Так как е = Y по условию исходной задачи, а е = Y по алгоритму решения измененной задачи, то е =е . Вычитание одной и той же величины, умноженной на , из левой и правой частей выражения (1) не меняет знак неравенства:

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

Для задачи 2 применение метода множителей Лагранжа реализуется проще. Модель измененной задачи можно записать по аналогии с вышеприведенным случаем в виде:

Для функций последовательности, определенных как

справедливо следующее рекуррентное соотношение

Как видно, здесь нет дополнительных функций h_j и вычисления можно проводить сразу по рекуррентной формуле, задавшись предварительно значением . После нахождения решения проверяется условие е )Ј B и, если оно не выполняется, то необходимо изменить значение и повторить расчет. Таким способом достигается эквивалентность исходной и измененной задач и получение оптимального решения с помощью последовательности функций, зависящих только от одного параметра состояния.

В общем случае, когда вектор состояния исходной задачи имеет размерность m, можно использовать q множителей Лагранжа (q < m), что позволит снизить размерность вектора состояния измененной задачи до m-q. При этом выполнение исключенных из условий исходной задачи q ограничений может быть обеспечено управлением таким же числом множителей Лагранжа. Однако увеличение размерности вектора состояния и соответственно числа множителей Лагранжа ведет к значительно более быстрому росту трудоемкости решения измененной задачи. Поэтому проблема "проклятия размерности" остается, ограничивая применение метода ДП задачами с небольшим числом параметров состояния.

54. Задачи СПУ: построение сети и временной анализ.

СПУ - сложный комплекс взаимосвязанных работ; они состоят из ряда отдельных, элементарных работ. Выполнение некоторых работ не может быть начато раньше, чем завершены некоторые другие. Различают детерминированные (заранее известно, какие работы надо будет сделать), стохастические (неизвестно количество работ) и вероятностные (неизвестно, какие работы надо будет сделать) задачи. Основные понятия:

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

Событие - момент времени, когда завершаются одни работы и начинаются другие. Событие не имеет протяженности во времени. Начало и окончание любой работы описываются парой событий, которые называются начальным и конечным событиями. Для идентификации конкретной работы используют код работы (i,j), состоящий из номеров начального (i-го) и конечного (j-го) событий.

Если на работу тратится только время, она обозначается (точка -тире). Если на работу ничего не тратится (даже время) – фиктивная работа (- - ->)

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