Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Нахождение исходного (опорного) базисного решения задачи ЛП.





Вырожденный случай.

Рассмотрим задачу:

z=3x1 + 9x2 max

x1 + 4x2 8,

x1 + 2x2 4,

x1, x2 0.

Введя балансовые переменные x3и x4, решим обычный симплекс метод:

  Х1 Х2 Х3 Х4 Ci
X3          
X4          
L -3 -9      

 

  Х1 Х2 Х3 Х4 Ci
X2 1/4   1/4    
X4 1/2   -1/2    
L -3/4   9/4    

 

  Х1 Х2 Х3 Х4 Ci
X2     1/2 -1/2  
X1     -1    
L     3/2 3/2  

 

На начальной итерации в качестве исключаемой переменной можно выбрать как x3, так и x4. Выбрана переменная x3, тогда переменная x4, оставаясь базисной на итерации 1, принимает нулевое значение, а это приводит к получению вырожденного базисного решения. Оптимальное решение задачи получается на следующей итерации. Сравнивая итерации 1 и 2, заметим следующее: хотя состав базисных и небазисных переменных на этих итерациях различен, значения всех переменных и целевой функции не изменяются:

x1 = 0, x2 = 2, x3 = 0, x4 = 0, L= 18.

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

Нахождение исходного (опорного) базисного решения задачи ЛП.

Каноническая задача линейного программирования в векторной форме имеет вид:

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

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

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

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

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

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

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

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

Свойство двойственности задач ЛП.

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

Несимметричные двойственные задачи.

Исходная задача имеет вид:

(5)

,

или, в матричной форме,

(6)

Двойственная задача в несимметричной форме имеет вид

(7)

или, в матричной форме,

(8)

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

Симметричные двойственные задачи

Рассмотрим задачу линейного программирования в стандартной форме

(1)

,

или, в матричной форме,

(2)

Рассмотрим теперь следующую задачу

(3)

,

или, в матричной форме,

(4)

Пара задач (1) и (3) (или, в матричной форме, пара задач (2) и (4)) называются двойственными друг другу задачами в симметричной форме.

Теоремы двойственности.

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

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

Теорема 2: Для оптимальности допустимых решений и пары двойственных задач необходимо и достаточно, чтобы они удовлетворяли системе уравнений

=0

0

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

Транспортная задача.

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

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

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

. (3.1)

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

Открытая ТЗ имеет место в двух случаях.

Первый случай. Суммарный объем производства меньше суммарного объема потребления:

. (3.2)

Известно, что для существования допустимого решения транспортной задачи необходимо и достаточно, чтобы задача была закрытой. Поэтому транспортную задачу открытого типа предварительно необходимо свести к закрытой, для чего вводится фиктивный пункт производства с номером m+1 с объемом производства:

, (3.3)

при этом полагают .

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

. (3.4)

Для сведения ТЗ к закрытому типу вводят фиктивный пункт потребления с номером n+1 с объемом потребления:

, (3.5)

при этом полагают .

 

Задача о назначениях.

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

Искомые параметры

  1. xij – факт назначения или неназначения ресурса Аi на работу Bj:

  1. L (X) – общая (суммарная) характеристика качества распределения ресурсов по работам.

 

Задача о назначениях является типичным примером оптимального

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

распределить объекты из некоторого множества по группе субъектов

из другого множества и это распределение должно соответствовать

оптимальности одного или нескольких итоговых показателей.

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

Для построения математической модели введем переменные , принимающие значения 0 или 1 в зависимости от того, назначен или нет i-ый механизм на j-ую работу. Получаем следующую задачу:

=1 (j=1,2,…,n)

=1 (i=1,2,…,n)

84. Нахождение опорного плана.

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

1) Метод северо-западного угла.

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

2) Метод минимальной стоимости.

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

3) Метод двойного предпочтения.

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

Метод потенциалов.

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

1) Построение системы потенциалов.

Для построения системы потенциалов используем условие (5)

2) Проверка выполнения условия оптимальности для незанятых клеток.

Просматриваем строки и для каждой незанятой клетки проверяем выполнение условия

(6) Если для всех незанятых клеток условие (6) выполняется, то план является оптимальным. Если для некоторых клеток , то план является неоптимальным.

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

Алгоритм

Метод потенциалов является модификацией симплекс-метода, в котором базисная матрица представлена в виде дерева.

Двойственные переменные симплекс-метода для транспортной задачи называются потенциалами.

Потенциалы вычисляются по формуле , что эквивалентно

Для дуги потенциалы дуг связаны формулой .

Таким образом, потенциал потребителя равна потенциалу производителя + стоимость перевозки. С экономической точки зрения это можно трактовать как стоимость продукта в точке потребления.

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

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

Остается только пересчитать потенциалы - добавить (или вычесть - зависит от направления дуги) ко всем вершинам "повисшей ветки" величину невязки

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

Открытая модель ТЗ.

Открытая и закрытая транспортные задачи. Выделяют два типа ТЗ: открытая ТЗ и закрытая ТЗ. Транспортная задача называется закрытой, если выполняется условие баланса: суммарный объем производства равен суммарному объему потребления:

. (3.1)

Открытая ТЗ имеет место в двух случаях. Первый случай. Суммарный объем производства меньше суммарного объема потребления:

. (3.2)

Известно, что для существования допустимого решения транспортной задачи необходимо и достаточно, чтобы задача была закрытой. Поэтому транспортную задачу открытого типа предварительно необходимо свести к закрытой, для чего вводится фиктивный пункт производства с номером m+1 с объемом производства:

, (3.3)

при этом полагают .

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

. (3.4)

Для сведения ТЗ к закрытому типу вводят фиктивный пункт потребления с номером n+1 с объемом потребления:

, (3.5)

при этом полагают .

Венгерский метод

 

Метод ветвей и границ

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

 

L = 11x1 + 12x2 →max

12x1 + 11x2 ≤ 132;

10x1 + 15x2 ≤ 150;

x1 ≥ 0, x2 ≥ 0,

x1, x2 Z

 

 

L = 134 ; x1 = 4 ; x2 = 6 .

 

 

Начинаем вводить ограничения:

x2 12 x1 + 11*6 = 132; x1 = 5 ; x2 = 6; L = 132 ; Решений нет x2 10 x1 +15*7 = 150 x1=4 ; x2 = 7; L = 133 >132 , значит продолжаем ветвление здесь.  

 

x1 10*4 +15x2 = 150; x1 = 4; x2 = 7 ; L=132; Продолжаем ветвление здесь. x1 15х2=100 х1=5; х2=6 ; L=135; Решений нет  

 

х2 Решений нет.   x2 10х1 + 15*8 = 150 х1 = 3; х2 = 8; L=129 Получено целочисленное решение, прекращаем ветвление..

 

Итак, оптимальное целочисленное решение равно 129 при x1 = 3; x2 = 8.

 

Задача коммивояжёра

Постановка задачи. Коммивояжер должен объехать N городов. Известны затраты (стоимостные, временные, расстояния) на переезд между i – м и j – м городом, которые заданы в виде матрицы . Коммивояжер, выехав из исходного города, должен объехать все города, посетив каждый один раз, и вернуться в исходный. Требуется определить в каком порядке следует объезжать города, чтобы суммарные затраты были минимальными.

Если затраты на переезд между каждой парой городов не зависят от направления движения, то задача называется симметричной, в противном случае – несимметричной.

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

Модель. В качестве переменных выбираются элементы матрицы переездов:

.

Пусть .

- переезд из i-го города в j-ый включается в маршрут;

- в противном случае.

Ограничения группы (а) задают условие: в каждый город коммивояжер въезжает только один раз. Ограничения группы (b) задают условие: из каждого города коммивояжер выезжает только один раз.

Задача управления запасами

Постановка задачи

Пусть месячная потребность предприятия в каком-либо материале (песок, щебень, цемент,...) составляет Q единиц (м^ т,...). Расход его во времени происходит равномерно. Необходимо определить, какова должна быть величина поставляемой партии материалов, чтобы суммарные затраты на создание и хранение запаса были минимальны.

Можно выделить четыре основные причины, приводящие к необходимости образования запасов:

• необходимость гарантирования бесперебойности питания производственного процесса с целью обеспечения его непрерывности;

• периодичность производства отдельных видов ресурсов у поставщиков:

• особенности доставки ресурсов от поставщика до потребителя (несо ответствие грузоподъемности транспортных средств и размеров по требления);

• несовпадение ритма производства и поставок производственных ре сурсов с ритмом их потребления.

Любая модель управления запасами, в конечном счете, должна дать ответ на

два вопроса:

1. Какое количество продукции заказывать?

2. Когда заказывать?

Ответ на первый вопрос выражается через размер заказа, определяющего

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

когда происходит размещение заказа. В зависимости от рассматриваемой

ситуации размер заказа может меняться во времени. Ответ на второй вопрос

зависит от типа системы управления запасами. Если система предусматривает

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

(например, еженедельно или ежемесячно), момент поступления нового заказа

обычно совпадает с началом каждого интервала времени. Если же в системе

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

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

Таким образом, решение обобщённой задачи управления запасами

определяется следующим образом;

1. В случае периодического контроля состояния запаса следует обеспечивать

поставку нового количества ресурсов в объеме размера заказа через равные

интервалы времени.

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

новый заказ в размере объема запаса, когда его уровень достигает точки

заказа.

Размер и точка заказа обычно определяются из условий минимизации

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

функции этих двух переменных. Суммарные затраты системы управления запасами

выражаются в виде функции их основных компонент

 

 

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

Пусть имеется некоторая система снабжения (склад, оптовая база и т. п.), планирующая свою работу на п периодов. Ее деятельность сводится к обеспечению спроса конечных потребителей на некоторый продукт, для чего она осуществляет заказы производителю данного продукта. Спрос клиентов (конечных потребителей) в данной модели рассматривается как некоторая интегрированная величина, принимающая заданные значения для каждого из периодов, и он должен всегда удовлетворяться (т. е. не допускаются задолженности и отказы). Также предполагается, что заказ, посылаемый производителю, удовлетворяется им полностью, и временем между заказом и его выполнением можно пренебречь (т. е. рассматривается система с мгновенным выполнением заказа). Введем обозначения:

yk — остаток запаса после (k-1)-го периода;

dk — заранее известный суммарный спрос в k-м периоде;

хk — заказ (поставка от производителя) в k-м периоде;

сk (хk) —затраты на выполнение заказа объема xk в k-м периоде;

sk (ξk) — затраты на хранение запаса объема ξk в k-м периоде.

После получения поставки и удовлетворения спроса объем товара, подлежащего хранению в период k, составит ξk = yk + хk - dk. Учитывая смысл параметра yk, можно записать соотношение:

Расходы на получение и хранение товара в период k описываются функцией

Планом задачи можно считать вектор х = (х1, х2,..., хn), компонентами которого являются последовательные заказы в течение рассматриваемого промежутка времени. Соотношение между запасами (5.24) в сочетании с некоторым начальным условием связывает состояния системы с выбранным планом и позволяет выразить суммарные расходы за все п периодов функционирования управляемой системы снабжения в форме аддитивной целевой функции:

Естественной в рамках сформулированной модели представляется задача нахождения последовательности оптимальных управлений (заказов) x*k и связанных с ними оптимальных состояний (запасов) ξ*k, которые обращают в минимум (5.25). В качестве начального условияиспользуем требование о сохранении после завершения управления заданного количества товара yn+1, а именно

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

поскольку

Система рекуррентных соотношений (5.27)-(5.28) позволяет найти последовательность функций состояния Λ1(ξ), Λ2(ξ), …, Λn(ξ) и условных оптимальных управлений 1(ξ), 2(ξ), …, n(ξ). На n-м шаге с помощью начального условия (5.26) можно определить х*n = n (yn+1). Остальные значения оптимальных управлений x*k определяются по формуле:

Особый интерес представляет частный случай задачи (5.24)-(5.25), при котором предполагается, что функции затрат на пополнение запаса сk(хk) являются вогнутыми по хk, а функции затрат на хранение sk(ξk) являются линейными относительно объема хранимого запаса, т. е. sk(ξk) = skξk. Параллельно заметим, что обе предпосылки являются достаточно реалистичными.

Обозначим функцию затрат в течение k-ro периода через

или, что то же самое,

В силу сделанных предположений все функции затрат fk (xk, yk+1) являются вогнутыми (как суммы вогнутой и линейной функций). Данное свойство значительно упрощает процесс решения, так как для поиска минимума вогнутых функций fk (xk, yk+1) достаточно рассмотреть только две крайние точки множества, на котором отыскивается минимум. С учетом введенного обозначения задачу (5.24)-(5.25) можно записать в виде:

при условиях

Рассмотрим процедуру решения (5.32)-(5.33). Так как ищется минимум суммы вогнутых функцийfk(xk, yk+1), то решение будет достигаться на одной из крайних точек множества, определяемого условиями (5.33). Общее число переменных xk и yk в системе (5.33) равно 2п. Однако, учитывая то, что в ней только п уравнений, в оптимальном плане будет не более п ненулевых компонент, причем для каждого периода k значения xk и yk не могут равняться нулю одновременно (в силу необходимости удовлетворения спроса либо за счет заказа, либо за счет запаса). Формально это утверждение можно представить в виде условия дополняющей нежесткости:

где

С точки зрения содержательной интерпретации условия (5.34)-(5.35) означают, что приоптимальном управлении заказ поставщику на новую партию не должен поступать, если в начале периода имеется ненулевой запас, или размер заказа должен равняться величине спроса за целое число периодов. Отсюда следует, что запас на конец последнего периода должен равняться нулю: у*n+1=0. Последнее позволяет решать задачу в прямом направлении, применяя рекуррентное соотношение

где ξ = уk+1= хk + уk - dk.

Учитывая (5.34)-(5.35) и вогнутость fk (xk, ξ), заключаем, что минимум (5.36) достигается в одной из крайних точек xk =0 или xk = ξ + dk поэтому

тогда для предыдущего периода функция состояния может быть выражена как

на oснове чего в общем виде получаем модифицированную форму для рекуррентного соотношения

При дальнейших конкретизирующих предположениях о виде функций fk (xk, уk+1) можно получить еще более компактные формы для рекуррентных соотношений. Однако эти вопросы носят достаточно частный характер, и мы их рассматривать не будем. Отметим лишь, что приведенные в данном пункте преобразования неплохо иллюстрируют общие подходы, применяемые в динамическом программировании, а также те свойства задач, которые открывают возможности, для эффективного и плодотворного использования соответствующих методов.

101. Математическое описание задач динамического программирования

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

;

выбор управления Xk на каждом шаге зависит только от состояния системы к этому шагу Sk-1 и не влияет на предшествующие шаги (нет обратной связи); состояние системы Sk после каждого шага управления зависит только от предшествующего состояния системы Sk-1 и этого управляющего воздействия Xk (отсутствие последействия) и может быть записано в виде уравнения состояния:

;

на каждом шаге управление Xk зависит от конечного числа управляющих переменных, а состояние системы Sk зависит от конечного числа переменных; оптимальное управление X* представляет собой вектор, определяемый последовательностью оптимальных пошаговых управлений, число которых и определяет количество шагов задачи.

X*=(X*1, X*2, …, X*k, …, X*n),

Условная оптимизация. Как уже отмечалось выше, на данном этапе отыскиваются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем n-м шаге найти оптимальное управление X*n и значение функции Беллмана Fn(S) не сложно, так как

Fn(S)=max{Wn(S,Xn)},

где максимум ищется по всем возможным значениям Xn.

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

Fk(S)=max{Wk(S,Xk)+Fk+1(S"(S,Xk))}. (1)

Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления X.

Безусловная оптимизация. После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый (на первом шаге k=1 состояние системы равно ее начальному состоянию S0), осуществляется второй этап решения задачи. Находится оптимальное управление на первом шаге X1, применение которого приведет систему в состояние S1(S,x1*), зная которое можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге, и так далее до последнего n-го шага.

102. Алгоритм решения методом динамического программирования

Очевидно, последний — после него других шагов нет. Этот шаг, единственный из всех, можно планировать так, чтобы он как таковой принес наибольшую выгоду. Спланировав оптимально этот последний шаг, можно к нему пристраивать предпоследний, к предпоследнему — предпредпоследний и т.д.
Поэтому процесс динамического программирования на 1-м этапе разворачивается от конца к началу, то есть раньше всех планируется последний,
N-й шаг. А как его спланировать, если мы не знаем, чем кончился







Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

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





Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2024 zdamsam.ru Размещенные материалы защищены законодательством РФ.