Студопедия — Нормы расхода ресурсов
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Нормы расхода ресурсов






Ресурсы Ткани
I II III
Оборудование      
Сырье I   э
Электроэнергия      

Цена за один метр ткани вида I равна 80 денежным единицам, II - 70 денежным единицам, III - 60 денежным единицам.

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

Решение. Составим модель задачи. Введем следующие обозначения. Неизвестными в задаче являются объемы выпуска ткани каждого вида:

x 1 - количество метров ткани вида I;

х2 - количество метров ткани вида II;

х3 - количество метров ткани вида III.

С учетом имеющихся данных модель примет вид:

Ограничение по ресурсам

Плановое задание

В результате решения задачи симплексным методом получен следующий оптимальный план: максимум общей стоимости продукции = 19 075 ден. ед. достигается при

x 1 = 112,5 м - оптимальный объем выпуска ткани вида I;

x 2 = 70 м - оптимальный объем выпуска ткани вида II;

x 3 = 86,25 м - оптимальный объем выпуска ткани вида III.

Решение двойственной задачи получим с использованием теорем двойственности. Введем обозначения:

y 1 - двойственная оценка ресурса "оборудование";

y 2 - двойственная оценка ресурса "сырье";

y 3 - двойственная оценка ресурса "электроэнергия";

y 4 - двойственная оценка ткани вида I;

y 5 - двойственная оценка ткани вида II;

y 6 - двойственная оценка ткани вида III.

Модель двойственной задачи имеет вид:

Из соотношений второй теоремы двойственности вытекают следующие условия:

для каждого ресурса:

если ;

если

для задания по выпуску продукции:

если , то ;

если , то . (3.12)

Для нашего примера в этих соотношениях т = 3 (количество типов ресурсов).

Подставим значения x 1 = 112,5, x 2 = 70 и x 3 = 86,25 в ограничения прямой задачи:

Суточные ресурсы по оборудованию и электроэнергии использованы полностью. Сырье используется не полностью, имеется остаток в размере 850 - 823,75 = 26,25 (кг). План выпуска по тканям вида I и III перевыполнен.

Из второй теоремы двойственности вытекает, что y 2, y 4 и y 6 равны нулю. Остается найти значения y 1, y 3 и y 5. Так как x 1, x 2 и x 3 - больше нуля, то все три ограничения двойственной задачи выполняются как равенства:

Учитывая, что имеем:

откуда .

Подставив значения неизвестных в целевую функцию двойственной задачи, проверим, выполняется ли условие для оптимального плана:

Условие первой теоремы двойственности выполняется, следовательно, рассмотренный план выпуска тканей и соответствующая ему система оценок ресурсов и продукции оптимальны.

Экономическое истолкование оценок есть интерпретация их общих экономико-математических свойств применительно к конкретному содержанию задачи. По условию (3.10) не использованный полностью в оптимальном плане ресурс получает нулевую оценку. Нулевая оценка ресурса свидетельствует о его недефицитности. Ресурс недефицитен не из-за его неограниченных запасов (они ограничены величиной b i), а из-за невозможности его полного использования в оптимальном плане. Так как суммарный расход недефицитного ресурса меньше его общего количества, то план производства им не лимитируется. Данный ресурс не препятствует и дальше максимизировать целевую функцию .

Ограничивают целевую функцию дефицитные ресурсы, в данном примере - оборудование и электроэнергия. Они полностью использованы в оптимальном плане. По условию (3.10) оценка таких ресурсов положительна (y 1 = 2,5; y 3 = 25). Рассмотрим теперь понятие дефицитности продукции. По условию (3.12) нулевую оценку (y 4 = 0, y 6 = 0) получает продукция, задания по выпуску которой в оптимальном плане перевыполняются. Очевидно, перевыполнение плана целесообразно по выгодной продукции (ткани I и III видов), т.е. такой, производство которой способствует достижению максимума критерия оптимальности. Размеры производства такой выгодной продукции определяются не величиной задания на выпуск (Tj) (в оптимальном плане они перекрыты), а ограниченностью дефицитных ресурсов. Эту продукцию выпускают как можно больше, пока хватит ресурсов. Выпуск выгодной продукции лимитируется не только фактом ограниченности дефицитных ресурсов, но и тем, что часть дефицитных ресурсов требуется выделить на обеспечение выпуска невыгодной продукции в соответствии с плановыми заданиями. По условию (3.12) отрицательную оценку (y 5 = -37,5) получает продукция, задания, по выпуску которой, не перевыполняются. Так как по условию задачи (X j > T j) плановые задания должны быть обязательно выполнены, то продукция делится на выгодную (виды 1 и III ткани) и невыгодную (вид II ткани).

Если в ограничение двойственной задачи, относящееся к виду II ткани,

подставить полученные значения двойственных оценок, то получаем

т.е. стоимость ресурсов, затраченных на один метр ткани вида II, составляет 107,5 денежной единицы, и это на 37,5 денежной единицы больше цены одного метра ткани этого вида. Таким образом, вид II ткани убыточен для фабрики: на каждом выпущенном метре ткани этого вида фабрика теряет 37,5 денежной единицы.

В соответствии с критерием оптимальности плана, в зависимости от того перевыполняется план выпуска или нет, выпуск ткани вида II поглощает часть дефицитных ресурсов, чем сдерживает рост выпуска выгодной продукции, а тем самым и рост целевой функции.

Оценка ресурса показывает, насколько изменится критерий оптимальности при изменении количества данного ресурса на единицу. Для недефицитного ресурса оценка равна нулю, поэтому изменение его величины не повлияет на критерий оптимальности. Дефицитность ресурса измеряется вкладом единицы ресурса в изменение целевой функции.

Влияние ограничений по выпуску продукции на критерий оптимальности противоположно влиянию ограничений по ресурсам. Если продукция невыгодна (вид II ткани, y 5 = -37,5), то увеличение плановых заданий по ее выпуску ведет к уменьшению выпуска выгодной продукции и ухудшает план. Наоборот, уменьшение плановых заданий по невыгодной продукции позволяет снизить ее выпуск, перебросить сэкономленные ресурсы на дополнительный сверхплановый выпуск выгодных видов продукции, что увеличивает значение целевой функции. Изменение плановых заданий по выгодной продукции не изменяет значения целевой функции.

Перейдем к анализу модели на чувствительность.

Пример 3.3. На основании информации, приведенной в табл. 3.3, составить план производства, максимизирующий объем прибыли.

Таблица 3.3

Ресурсы Затраты ресурсов на единицу продукции Наличие ресурсов
А А
Труд      
Сырье 4    
Оборудование      
Прибыль на единицу продукции      

Решение. Экономико-математическая модель задачи будет иметь вид:

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

Соответствующий отчет об устойчивости решения представлен на рис. 3.2.

Ячейки переменных
Ячейка Имя Окончательное значение Приведенная стоимость Целевая функция Коэффициент Допустимое увеличение Допустимое уменьшение
$A$2            
$B$2            
Ограничения
Ячейка Имя Окончательное значение Теневая цена Ограничение Правая сторона Допустимое увеличение Допустимое уменьшение
$С$4     13.3333333337      
$С$5         1E+30  
$С$6     6.6666666667   85.71428571  
               

Рис. 3.2. Отчет об устойчивости

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

1. Увеличение объемов какого вида ресурсов наиболее выгодно?

2. Насколько можно увеличить запас сырья для улучшения полученного оптимального значения целевой функции?

3. Каков диапазон изменения того или иного коэффициента целевой функции, при котором не происходит изменения оптимального решения?

4. Целесообразность включения в план новых изделий.

Постараемся последовательно ответить на все поставленные вопросы.

1. Ценность ресурсов. В примере 3.3 объективно обусловленные оценки ресурса "труд" равны 40/3 (y 1 = 40/3), "сырье" - 0 (y 2 = 0), "оборудование" - 20/3 (y 3 = 20/3).

Дефицитный ресурс, полностью используемый в оптимальном плане (), имеет положительную оценку (y i > 0); недефицитный, не полностью используемый ресурс (для которого ), имеет нулевую оценку (y i = 0). В примере "сырье" не является дефицитным ресурсом:

а "труд" и "оборудование" - дефицитные ресурсы:

Чем выше величина оценки y i, тем острее дефицитность i -го ресурса. В примере "труд" более дефицитен, чем "оборудование": 40/3 > 20/3. Наиболее выгодно увеличение объемов ресурса труда.

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

2. Чувствительность решения к изменению запасов сырья. Предположим, что запас сырья ресурса "труд" изменился на 12 единиц, т.е. теперь он составляет 2000 + 12 = 2012 единиц.

Из теоремы об оценках известно, что колебание величины b j приводит к увеличению или уменьшению . Оно определяется величиной yi, в случае, когда при изменении величин bj значения переменных yi, в оптимальном плане соответствующей двойственной задачи, остаются неизменными. Поэтому необходимо найти такие интервалы изменения каждого из свободных членов системы ограничений исходной ЗЛП, в которых оптимальный план двойственной задачи не менялся бы.

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

Точной мерой влияния ограничений на функционал оценки являются лишь при малом приращении ограничения.

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

Рассмотрим модель исходной задачи (3.1)-(3.3) в матричной форме:

где X = (x 1, x 2,..., x n) - вектор неизвестных;

С = (с 1, с 2,..., с n) - вектор коэффициентов при неизвестных в целевой функции;

В = (b 1, b 2,..., bm) - вектор свободных членов ограничений исходной задачи;

- матрица коэффициентов в системе ограничений.

Приведем задачу к канонической форме, введем т дополнительных переменных. Задача примет вид:

где вектор неизвестных переменных X будет теперь иметь размерность п + т. Размерность матрицы А также изменится и будет равна т · (п + т).

Пусть известен оптимальный план. Разобьем вектор X на два подвектора: и . В первый включены неизвестные, вошедшие в базис оптимального решения (т.е. ненулевые в оптимальном плане). Соответственно матрицу А разобьем на две подматрицы: А* (размерность т x т) и A 0 (размерность т x n). Первую из них сформируют т.е. столбцы матрицы А, которые соответствуют ненулевым неизвестным в оптимальном плане. Тогда . Так как . Умножив обе части последнего равенства на матрицу, обратную матрице А, получим . Так как , где Е - единичная матрица, то . Обозначим через D, тогда .

Матрица D характеризует влияние ресурсов на величину выпуска продукции X. Изменим размер выделяемых ресурсов, т.е. дадим приращение вектору В. Тогда

С учетом X = DB можно записать:

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

Второе свойство двойственных оценок означает, что изменение значений величины bi приводит к увеличению или уменьшению . Это изменение, как выше уже отмечено, определяется величиной yi ; и может быть определено лишь тогда, когда при изменении величин bi значения переменных yi; в оптимальном плане соответствующей двойственной задачи остаются неизменными. Поэтому необходимо определить такие интервалы изменения каждого из свободных членов системы линейных уравнений АХ = В, в которых оптимальный план двойственной задачи не меняется. Это имеет место тогда, когда среди компонент вектора X = DB нет отрицательных.

Исходя из этого, получаем следующие оценки нижних и верхних пределов устойчивости двойственных оценок при изменении каждого ограничения в отдельности. Пределы уменьшения (нижняя граница) определяются по тем хk(k = 1 ,..., т), для которых соответствующие dkj>; 0:

(3.13)

Пределы увеличения (верхняя граница) определяются по тем хk, для которых dkj<; 0:

для (3.14)

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

Определим интервалы устойчивости двойственных оценок в примере 3.3. Матрица А имеет вид

После приведения задачи к канонической форме матрица А примет следующий вид:

С ненулевыми значениями в оптимальный план вошли и , следовательно, матрица А * будет составлена из первого, второго и четвертого столбцов матрицы А:

Для вычисления интервалов устойчивости необходимо найти матрицу (правила вычисления обратной матрицы приведены в главе 2.

При вычислении интервалов устойчивости по формулам (3.13) и (3.14) примем

Интервалы устойчивости первого ресурса - "труд":

При изменении запасов ресурса "труд" в пределах от 1400 до 3200 единиц двойственная оценка его не изменится.

Интервалы устойчивости второго ресурса - "сырье":

этот ресурс в оптимальном плане используется не полностью и поэтому не имеет верхней границы интервалов устойчивости:

нижняя граница определяется следующим образом:

Интервалы устойчивости третьего ресурса - "оборудование":

В нашем примере определим величину изменения объема прибыли от реализации продукции при увеличении ресурса "труд" на 12 единиц. Эти изменения находятся в интервалах устойчивости двойственных оценок, поэтому можно воспользоваться теоремой об оценках:

Объем прибыли увеличится на 160 единиц.

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

Структурных сдвигов в программе не произошло, но значения переменных в плане изменились: продукции вида Л может быть выпущено на 2 единицы меньше, а продукции вида Б - на 4 больше. Значение целевой функции при новых ограничениях увеличится на 160 единиц.

3. Чувствительность решения к изменению коэффициентов целевой функции. Так как любые изменения коэффициентов целевой функции оказывают влияние на оптимальность полученного ранее решения, то наша цель - найти такие диапазоны изменения коэффициентов в целевой функции (рассматривая каждый из коэффициентов отдельно), при которых оптимальные значения переменных остаются неизменными. Допустимые диапазоны изменения коэффициентов в целевой функции определятся из соотношений:

для

для

Используя эти соотношения в рассматриваемой задаче, получим для первого коэффициента целевой функции:

для второго коэффициента:

Таким образом, найденный оптимальный план выпуска продукции не будет меняться при изменении прибыли на единицу продукции А в диапазоне от 30 до 120 и прибыли на единицу второй продукции Б в диапазоне от 20 до 80.

4. Целесообразность включения в план новых изделий. Пусть в рассматриваемой нами задаче предприятию были предложены на выбор три новых изделия, за счет которых можно было бы расширить номенклатуру выпускаемой продукции при тех же запасах ресурсов. Нормы затрат ресурсов и прибыль от реализации единицы продукции для этих изделий представлены в табл. 3.4. Определим из предложенных видов изделий выгодные для предприятия с экономической точки зрения.

Таблица 3.4

Ресурсы Объективно обусловленные оценки ресурсов Затраты ресурсов на одно изделие
В Г Д
Труд 40/3      
Сырье        
Оборудование 20/3      
Прибыль на одно изделие      

Эту задачу можно решить на основании свойства 3 двойственных оценок: в оптимальный план задачи на получение максимума прибыли может быть включен лишь тот вариант, для которого прибыль, недополученная из-за отвлечения дефицитных ресурсов, т.е. величина , покрывается полученной прибылью сj. Таким образом, характеристикой того или иного варианта служит разность , при этом если , то вариант выгоден; если , то невыгоден.

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

Для изделия В:

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

Аналогично для изделия Г:

∆Г = 4 - 40/3 + 20/3 - 70 = 160/3 - 20/3 - 70 = 180/3 - 70 = 60 - 70 = -10 < 0 - выгодно;

для изделия Д:

;Д = 2 · 40/3 + 20/3 · 2 - 45 = 80/3 + 40/3 - 45 = 40 - 45 = -5 < 0 - выгодно.

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

Свойство 4 - оценки как инструмент балансирования суммарных затрат и результатов - вытекает из первой теоремы двойственности, в которой устанавливается связь между функционалами прямой и двойственной задач: max . В конкретных задачах такого рода соотношения "затраты - результаты", т.е. равновесие затрат и результатов в точке оптимума, могут иметь различное экономическое содержание.

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

18)

ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ. Общая формулировка задачи

 

. Некоторые задачи линейного программирования требуют целочисленного решения. К ним относятся задачи по произ­водству и распределению неделимой продукции (выпуск стан­ков, телевизоров, автомобилей и т. д.). В общем виде математи­ческая модель задачи целочисленного программирования име­ет вид При ограничениях: Оптимальное решение задачи, найденное симплексным ме­тодом, часто не является целочисленным. Его можно округлить до ближайших целых чисел. Однако такое округление может дать решение, не лучшее среди целочисленных решений, или привести к решению, не удовлетворяющему системе ограниче­ний. Поэтому для нахождения целочисленного решения нужен особый алгоритм. Такой алгоритм предложен Гомори и состо­ит в следующем. Симплексным методом находят оптимальное решение за­дачи. Если решение целочисленное, то задача решена. Если же оно содержит хотя бы одну дробную координату, то на­кладывают дополнительное ограничение по целочисленности и вычисления продолжают до получения нового решения. Ес­ли и оно является нецелочисленным, то вновь накладывают дополнительное ограничение по целочисленности. Вычисления продолжают до тех пор, пока не будет получено целочисленное решение или показано, что задача не имеет целочисленного ре­шения. Пусть получено оптимальное решение Опт = (F1, F2,..., Fr, 0,..., 0), которое не является целочисленным, тогда по­следний шаг симплексной таблицы имеет следующий вид: Где R — ранг системы ограничений; Hi,R+1 — коэффициент сим­плексной таблицы I-й строки, (R + 1)-го столбца; Fi— свобод­ный член I-й строки. Пусть Fi и хотя бы одно Hij (J = , r = ) — дроб­ные числа. Обозначим через [Fi] и [Hij] целые части чисел Fi и Hij. Определение 1. Целой частью числа Fi называют наибольшее целое число, не превосходящее числа Fi. Дробную часть чисел Fi и Hij обозначим {Fi} и {Hij}, она определяется следующим образом: Пример. Если Fi и хотя бы одно значение Hij дробны, то с учетом введенных обозначений целых и дробных чисел дополнитель­ное ограничение по целочисленности примет вид {hi, r+l} xr+1 + {hi, r+2} xr+2 + • • • + {hi, п} xп ≥ {fi}. Примечания. 1) Если Fi — дробное число, а все Hij — целые числа, то задача линейного программирования не имеет целочисленного решения. 2) Ограничение целочисленности может быть наложено не на все переменные, а лишь на их часть. В этом случае задача является частично целочисленной.

 

16. Вторая теорема двойственности (теорема о дополняющей нежесткости):

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

Эти условия устанавливают связь между оптимальными значениями прямой и двойственной задач и позволяют, зная решение одной из них, находить решение другой задачи.

19. Нелинейное программирование (NLP, англ. NonLinear Programming) — случай математического программирования, в котором целевой функцией или ограничением является нелинейная функция.

Задача нелинейного программирования ставится как задача нахождения оптимума определённой целевой функции при выполнении условий

где — параметры, — ограничения, — количество параметров, — количество ограничений.

В отличие от задачи линейного программирования, в задаче программирования нелинейного оптимум не обязательно лежит на границе области, определённой ограничениями.

Методы решения задач

Одним из методов, которые позволяют свести задачу нелинейного программирования к решению системы уравнений, является метод неопределенных множителейЛагранжа.

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

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

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

Существуют несколько методов для решения невыпуклых задач. Один подход заключается в использовании специальных формулировок задач линейного программирования. Другой метод предусматривает использование методов ветвей и границ, где задача делится на подклассы, чтобы быть решенной с выпуклыми (задача минимизации) или линейными аппроксимациями, которые образуют нижнюю границу общей стоимости в пределах раздела. При следующих разделах в определенный момент будет получено фактическое решение, стоимость которого равна лучшей нижней границе, полученной для любого из приближенных решений. Это решение является оптимальным, хотя, возможно, не единственным. Алгоритм можно прекратить на ранней стадии, с уверенностью, что оптимальное решение находится в рамках допустимого отклонения от найденной лучшей точки; такие точки называются ε-оптимальными. Завершение ε-оптимальных точек, как правило, необходимое для обеспечения конечности завершения. Это особенно полезно для больших, сложных задач и задач с неопределенными расходами или значениями, где неопределенность может быть определена из соответствующей оценки надежности.

Дифференцирование и условия регулярности, условия Каруша — Куна — Таккера (ККТ) обеспечивают необходимые условия оптимальности решения. При выпуклости, эти условия являются и достаточными.

20. Метод множителей Лагранжа,метод нахождения условного экстремума функции , где , относительно ограничений , где меняется от единицы до .

· Составим функцию Лагранжа в виде линейной комбинации функции и функций , взятых с коэффициентами, называемыми множителями Лагранжа:

где .

· Составим систему из уравнений, приравняв к нулю частные производные функции Лагранжа по и .

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

  • Метод множителей Лагранжа применяется при решении задач нелинейного программирования, возникающих во многих областях (например, в экономике).
  • Основной метод решения задачи об оптимизации качества кодирования аудио и видео информации при заданном среднем битрейте (оптимизация искажений —англ. Rate-Distortion optimization).

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

Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой (англ.), выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.

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

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







Дата добавления: 2015-06-12; просмотров: 1198. Нарушение авторских прав; Мы поможем в написании вашей работы!



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

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

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

Типовые примеры и методы их решения. Пример 2.5.1. На вклад начисляются сложные проценты: а) ежегодно; б) ежеквартально; в) ежемесячно Пример 2.5.1. На вклад начисляются сложные проценты: а) ежегодно; б) ежеквартально; в) ежемесячно. Какова должна быть годовая номинальная процентная ставка...

Выработка навыка зеркального письма (динамический стереотип) Цель работы: Проследить особенности образования любого навыка (динамического стереотипа) на примере выработки навыка зеркального письма...

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

Расчет концентрации титрованных растворов с помощью поправочного коэффициента При выполнении серийных анализов ГОСТ или ведомственная инструкция обычно предусматривают применение раствора заданной концентрации или заданного титра...

Психолого-педагогическая характеристика студенческой группы   Характеристика группы составляется по 407 группе очного отделения зооинженерного факультета, бакалавриата по направлению «Биология» РГАУ-МСХА имени К...

Общая и профессиональная культура педагога: сущность, специфика, взаимосвязь Педагогическая культура- часть общечеловеческих культуры, в которой запечатлил духовные и материальные ценности образования и воспитания, осуществляя образовательно-воспитательный процесс...

Studopedia.info - Студопедия - 2014-2024 год . (0.011 сек.) русская версия | украинская версия