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

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

1. В ряде случаев кроме начального состояния s ⁰ и числа шагов N задаётся финальное со-стояние s *. Это означает, что φ (s_{N −1}, v_N) = s *. При переходе к графу это означает, что искомый максимальный путь должен кончаться в соответствующей состоянию s * вершине x *. Модифи-кация алгоритма в этом случае практически очевидна. На итерации 1 в правом столбце для каж-дой вершины x слева пишется вес дуги (x, x *), а справа – номер x (напомним, что все вершины графа занумерованы числами 1, 2, …, n). Начиная с итерации 2, алгоритм полностью совпадает с рассмотренным в примере 1 (см. таблицы 1.2 – 1.6).

2. Иногда требуется найти не оптимальный путь длины N, а оптимальный путь длины не более N, с заданной или не заданной конечной вершиной. В этих случаях применяются точно те же самые алгоритмы. Ведь суть динамического программирования как раз в том, что последо-вательно находятся оптимальные пути из всех вершин длины 1, длины 2, …, длины N. После этого надо просмотреть числа из строки, соответствующей начальному состоянию, и выбрать из них максимальное или минимальное. В примере 1 путём с максимальным весом среди всех путей длины не более 6-и с началом в вершине 1 оказывается путь длины 6 (см. таблицу 1.6). А в примере 2 на минимизацию оптимальным при тех же условиях оказывается не путь длины 6, вес которого равен –3, а путь длины 1, вес которого равен –4. Естественно, это может случиться только в случае, когда имеются дуги с весами разных знаков. В противном случае вес любого пути при добавлении дуги увеличивается (если веса всех дуг положительны) или уменьшается (если веса всех дуг отрицательны). В этих случаях такие постановки не имеют смысла.

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

4. Если не задавать число шагов N в многошаговом процессе, то тем самым не будет зада-ваться и число дуг (т.е. длина пути) в соответствующем графе. Понятно, что если отсутствуют какие бы то ни было требования к графу и ∕ или к виду искомых путей, то задача оптимизации просто может не иметь решения. В частности, если в графе есть цикл положительной длины, а пути могут содержать циклы, понятно, что вес пути при многократном прохождении такого по-ложительного цикла может быть сделан сколь угодно большим. В то же время ограничения на вид пути (например, запрет на повторяющиеся вершины или дуги) просто «не встраиваются» в алгоритм динамического программирования (в том смысле, что найденные при ограничениях пути не обязаны быть оптимальными). Наиболее естественно в этих случаях выглядят такие ус-ловия на граф, при котором длины любых путей будут ограниченными (напомним, что речь в этой главе идёт только об ориентированных графах и путях). Именно такие постановки рассмотрены в следующем разделе.

3.1. Ацикличные задачи многошаговой оптимизации. Под такими задачами будут по-ниматься задачи, в которых под действием любого многошагового управления никогда нельзя вернуться в начальное состояние. Такие задачи часто связаны с тем, что время, которое всегда течёт в одну сторону, является одним из параметров, определяющих состояние системы. Соот-ветствующий граф будет ацикличным. В силу утверждения 5.8 множество вершин графа распа-дается на подмножества (которые можно называть слоями), такие, что любая дуга ведёт из слоя с бóльшим номером в слой с мéньшим номером. Для упрощения обозначений будем считать, что 0-ой слой состоит из единственной вершины x * и что рассматриваются пути, оканчивающи-еся в этой вершине. Обычно такая вершина соответствует окончанию рассматриваемого много-шагового процесса. Напомним, что число шагов N в данной модификации не задаётся.

Обозначим через W (x) вес оптимального пути, ведущего из вершины x в вершину x *. Ос-новное уравнение Беллмана можно записать в виде

W (x) = max_y{ w (x, y) + W (y)}, (8)

где максимум берётся по всем вершинам y, в которые ведёт дуга из вершины x. Учитывая, что все дуги ведут в слои с мéньшими номерами, знание оптимальных путей для всех вершин из слоёв V_r, V_{r −1}, …, V ₁ в вершину x *, образующую слой V ₀ позволяет по формуле (8) легко найти оптимальные пути для всех вершин из слоя V_{r +1}. Можно сказать, что в отличие от общего слу-чая, переход здесь делается не по шагам для всех вершин, а по слоям, которых обычно значи-тельно меньше, чем вершин. Соответственно, таблицы, заполнение которых позволяет найти оптимальный путь, также меняются и становятся значительно более обозримыми.

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

На рис.2 приведён пример сетевого графика, на котором показаны работы, необходимые для изготовления некоторого прибора. Сетевой график даёт наглядное представление о порядке выполнения работ, что даёт возможность наиболее рационально распорядиться имеющимися ресурсами. Сам граф отражает ограничения, связанные с выполнением данного комплекса ра-бот. Ясно, что производство деталей может быть начато только после подготовки чертежей и т.д.

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

контрольные испытания

производство деталей

отгрузка

сборка

поставка деталей

Выдача заказов на детали

проектирование

подготовка и составление инструкции

подготовка чертежей

 

 

Рис.2

Проведём дальнейшую формализацию задачи. Естественно считать, что граф G, описыва-ющий последовательность работ, является ацикличным, поскольку наличие цикла означает, на-пример, что работа Б должна выполняться после окончания работы A, работа В – после работы Б, а работа А – после работы В. Можно считать также, что в графе G есть ровно одна вершина, в которую не входит ни одна дуга, и ровно одна вершина, из которой не выходит ни одна дуга. Эти вершины соответствуют началу и завершению всего комплекса работ. Каждой дуге графа приписано положительное (не обязательно целое) число (длина дуги), которое интерпретирует-ся как длительность операции (работы), условно представляемой данной дугой.

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

Т_об ≥

Таким образом, возникает задача поиска пути максимальной длины (такой путь в сетевом графике называется критическим). Эта задача в общем виде рассматривалась в начале раздела 3.1. Начальная вершина x ⁰ и конечная вершина x* – это входная и выходная вершины сетевого графика. Число дуг в пути не фиксируется. Основная идея заключается в разделении множества вершин графа на слои. При этом начальный слой состоит из единственной выходной вершины, а последний слой состоит из единственной входной вершины. Основой для перехода от слоя к слоя служит уравнение Беллмана (8).

Пример 3. Рассмотрим сетевой график, показанный на рис. 3. Пунктирная линия не соот-ветствует никакой конкретной работе и её длина равна 0. Вводятся такие «псевдоработы» толь-ко для того, чтобы правильно отражать последовательность реальных работ. В рассматривае-мом случае включение псевдоработы Р означает, что работа З не может быть начата до оконча-ния работы В. Использование псевдоработ не меняет последовательности любых других опера-ций и не изменяет длины критического пути.

Рис.3. Пример сетевого графика

 

Построим разбиение множества вершин графа, показанного на рис.3, в соответствии с доказательством утверждения 5.8:

1. Положим G ₀ = G, V ₀={7}.

2. Удалим из графа G ₀ вершину 7 и ведущие в неё дуги И и К. Оставшийся граф G ₁ показан на рис.4а. В этом графе из вершин 5 и 6 не выходит дуг, и в соответствии с процедурой из упомянутого доказательства V ₁={5,6}.

Рис.4

3. Удалим из графа G ₁ (см. рис.4а) вершины 5, 6 и ведущие в них дуги Ж, З и Г. Остав-шийся граф G ₂ показан на рис.4b. В этом графе из вершины 4 не выходит дуг, и в соответствии с той же процедурой V ₂={4}.

4. Удалим из графа G ₂ (см. рис.4b) вершину 4 и ведущие в неё дуги Р, Е и Д. Оставшийся граф G ₃ показан на рис.4с. В этом графе из вершин 1, 2, 3 не выходит дуг, и в соответствии с процедурой V ₃={1, 2, 3}.

5. Удалим из графа G ₃ (см. рис.4с) вершины 1, 2, 3 и ведущие в них дуги А, Б и В. Остав-шийся граф G ₄ показан на рис.4d. В этом графе имеется только одна вершина 0 и в соответствии с той же процедурой V ₄={0}.

6. Процедура окончена, поскольку других вершин больше нет. Построено следующее раз-биение:

V ₀={7}, V ₁={5, 6}, V ₂= {4}, V ₃={1, 2, 3}, V ₄={0} (9)

и любая дуга ведёт из слоя с бóльшим номером в слой с мéньшим номером. Задача состоит в том, чтобы определить путь максимальной длины из вершины 0 в вершину 7.

Инициализация и итерация 1. Составим таблицу, столбцы которой соответствуют верши-нам заданного графа G. Расположим эти столбцы слева направо в соответствии с разбиением (9): сначала идёт столбец, соответствующий вершине 0, потом (в произвольном порядке) – столбцы, соответствующие вершинам 1, 2, 3 и т.д., вплоть до вершины 7. Число ячеек в каждом столбце равно числу дуг, выходящих из данной вершины, плюс одна строка (на следующую вершину в искомом максимальном пути).

Таблица 3.1. Нахождение критического пути. Инициализация и итерация 1

Каждая ячейка соответствует одной дуге, выходящей из вершины. В правую верхнюю клетку ячейки пишется номер вершины, в которую идёт дуга; в левую верхнюю – её длина. Так, из вершины выходят две дуги: в вершину 4 длины 0 (псевдоработа) и в вершину 5 длины 2. Эти данные полностью описывают исходный сетевой график и далее не меняются.

На итерации 1 определяются максимальные пути из вершин из 1-го слоя. По самой конструкции ясно, что такие пути совпадают с дугами, ведущими из этих вершин в конечную вершину 7. Длина максимального пути и следующая вершина на нём пишутся в нижние две клетки каждого столбца. Поэтому на итерации 1 туда просто копируются числа из верхних двух клеток.

Итерация 2. На итерации 2 определяются максимальные пути для вершин из слоя V ₂= {4}.

Таблица 3.2. Итерация 2

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

Итерация 3. На итерации 3 определяются максимальные пути для вершин из слоя V ₃= {1,2, 3}.

Таблица 3.3. Итерация 3

Начинаем для определённости с правого (из этого слоя) столбца 3. 1-ая сверху ячейка в этом столбце соответствует дуге (3,4) длины 0. В левую нижнюю клетку этой же ячейки запи-сываем сумму длины 0 и длины 12 из нижней строчки столбца 4 (максимальной длины пути из 4 в 7). Далее, в следующей сверху ячейке столбца 3 записываем сумму длины 2 дуги (3,5) и дли-ны 5 максимального пути из вершины 5 в вершину 7 (взятую из нижней строки столбца 5). Ко-пируем в нижнюю строку столбца 5 ту из двух полученных строк – (12,4) и (7,5) – в которой длина (1-ое число) больше. Поэтому копируем (12,4). Заметим, что именно здесь реализуется уравнение Беллмана (8).

Столбец 2 содержит только одну ячейку, которая соответствует дуге (2,4) длины 7. Запи-сываем в нижнюю половину этой ячейки длину 19 = 7+12 и вершину 4; ту же пару копируем в нижнюю строку.

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

Итерация 4. На итерации 4 определяются максимальные пути для вершин из последнего слоя V ₄= {0}. Столбец 1 содержит 3 ячейки, соответствующие дугам (0,1), (0,2) и (0,3). В верхнюю ячейку запишем длину 20 = 5 + 15 и номер 1.В следующую ячейку запишем сумму 23 = 4 + 19 и номер 2. В нижнюю ячейку запишем сумму 18 = 6 + 12 и номер 3. В нижнюю строку запишем пару с максимальной длтной 23.

На этом итерации закончены. Искомый путь выделен подсветкой в нижних строчках. Он таков: 0→2→4→6→7. Его длина равна 23.

 

Таблица 3.4. Итерация 4

■

Особенно простым алгоритм динамического программирования становится в случае, ког-да каждая дуга ведёт из слоя в слой с предыдущим номером, а число выходящих дуг всегда равно 2. Именно такой случай рассмотрен в следующем подразделе.

3.1.2. Задача о замене машины. В настоящем разделе приводится конкретный пример, иллюстрирующий введенные понятия и рассматриваемую модификацию алгоритма динами-ческого программирования. Одной из основных проблем индустрии является проблема замены старого парка машин новым, устаревших орудий современными устройствами. Оборудование со временем изнашивается как в буквальном смысле слова, так и «морально», т.е. устаревает по сравнению с более современным модернизированным оборудованием. Наступает момент, когда большие затраты на новое оборудование, убытки вследствие остановки производства и расходы на переподготовку кадров - всё это компенсируется увеличением производительности и умень-шением производственных затрат.

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

суммарную прибыль.

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

Рассмотрим процесс, длящийся 6 лет. Затраты на замену машины, доход и затраты на со-держание новых машин, появляющихся к началу каждого из этих 6 лет, в зависимости от воз-раста машины (т.е. числа полных лет, которые она уже проработала), приведены в таблице 4 (в условных единицах). Мы начинаем процесс, имея машину, называемую исходной, прослужив-шую уже 3 года; её характеристики представлены в таблице.

Общий (суммарный) доход равен сумме доходов, полученных на каждом году работы. До-ход за каждый год может быть получен из дохода (указанного в таблицах 4 и 5) путём вычи-тания затрат на содержание машины и (в случае замены в начале этого года) затрат на замену.

Таблица 4. Данные о новых машинах

Машина, новая в начале 1-го года Возраст машины             Доход             Затраты на содержание             Затраты на замену               Машина, новая в начале 2-го года Возраст машины           Доход           Затраты на содержание           Затраты на замену

Машина, новая в начале 4-го года Возраст машины       Доход       Затраты на содержание       Затраты на замену         Машина, новая в начале 5-го года Возраст машины     Доход     Затраты на содержание     Затраты на замену

Машина, новая в начале 3-го года Возраст машины         Доход         Затраты на содержание         Затраты на замену

Машина, новая в начале 6-го года Возраст машины   Доход   Затраты на содержание   Затраты на замену

Таблица 5. Данные об исходной машине

Возраст машины
Доход
Затраты на содержание
Затраты на замену

 

Выбор оптимальной последовательности замен можно осуществить в результате примене-ния метода динамического программирования. Для этого, в соответствии с тем, что излагалось в этом разделе 3.1, надо определить:

множество S состояний;

множества Q_s воздействий для всех s Î S;

функцию переходов φ (s, v);

функцию дохода ψ (s, v);

начальное состояние s ⁰Î S;

число шагов N.

Определим указанные параметры задачи.

1. Элементами множества S естественно считать пары вида (t, t), где t - текущий год (t = 1, 2,..., 6), t - возраст машины на начало года t. Обратим внимание на следующее. В последний (шестой) год есть пара (6,8) (она соответствует старой машине, у которой в начале 6-го года возраст 8 лет), есть пара (6,5) (она соответствует машине, новой в начале 1-го года, у которой в начале 6-го года возраст 5 лет), пара (6,4) (она соответствует машине, новой в начале 2-го года, у которой в начале 6-го года возраст 4 года) и т.д. Состояний (6,7) и (6,6) в множестве S просто нет! Точно также нет пар (5,6) и (5,5), (4,5) и (4,4) и т.д. Обратим внимание, что пар вида (t,0) также нет. В начале года у нас ещё нет новой машины, поэтому возраст имеющейся не меньше 1-го года. Если же мы приняли решение о покупке новой машины, то через год её возраст также будет не меньше 1-го года. Наконец, необходимо ввести «финальное» состояние (обозначим его через s *), соответствующее завершению процесса после окончания 6-го года.

2. Множество воздействий Q_s для любого состояния s Î S, кроме состояния s *, состоит из двух элементов: С и Н (оставить старую машину еще на один год или заменить ее новой). Для состояния s * множество Q_s пусто.

3. Функция переходов φ (s, v) определяется формулами

φ ((t, t),С) = (t +1, t +1) (t = 1,..., 5),

φ ((t, t),Н) = (t +1,1) (t = 1,..., 5),

φ ((6, t),С) = φ ((6, t),Н) = s *.

Действительно, если в начале года t решено оставить старую машину (v = С), то её возраст t через год увеличивается на 1; если же решено заменить машину новой (v = Н), то её возраст через год равен 1. Поскольку 6-й год является последним, то и соответствующее состояние сов-падает с s *.

4. Для определения функции доходов требуется использовать данные из таблиц 4 и 5. Вычислим (в качестве примера) ψ ((5,3),С) и ψ ((5,3),Н). Состояние (5,3) означает, что имеющая-ся на данный момент машина к началу 5-го года проработала 3 года. Но это означает, что она была новой в начале 2-го года. Из таблицы 3 для этой машины находим, что она (при возрасте 3 года) дает за год доход 110 при затратах 15, откуда ψ ((5,3),С) = 110 - 15 = 95. Если принять решение Н (заменить машину новой), то расходы на её замену (из таблицы 3 для этой же маши-ны) составляют в начале 5-го года (т.е. 3-го года её работы) 110; новая же машина (новая в на-чале 5-го года) приносит в течение 1-го года своей работы (при возрасте 0) доход 150 при затратах 5. Таким образом, ψ ((5,3),Н) = -110 +150 -5 = 35. Аналогично подсчитываются значе-ния этой же функции ψ ((t, t), v) при всех состояниях (t, t) и воздействиях v. Эти данные собраны в таблице 6.

Таблица 6. Функция доходов

(t, τ)	ψ ((t, τ),C)	(t, τ)	ψ ((t, τ),C)	(t, τ)	ψ ((t, τ),H)	(t, τ)	ψ (t, τ),H)
(6,8)	−15	(4,6)	−10	(6,8)	−10	(4,6)	−15
(6,5)		(4,3)		(6,5)		(4,3)
(6,4)		(4,2)		(6,4)		(4,2)
(6,3)		(4,1)		(6,3)		(4,1)
(6,2)		(3,5)	−5	(6,2)		(3,5)	−15
(6,1)		(3,2)		(6,1)		(3,2)
(5,7)	−10	(3,1)		(5,7)	−5	(3,1)
(5,4)		(2,4)		(5,4)		(2,4)	−15
(5,3)		(2,1)		(5,3)		(2,1)
(5,2)		(1,3)		(5,2)		(1,3)	−10
(5,1)				(5,1)

 

5. Начальное состояние s ⁰ = (1, 3) (по условию мы начинаем процесс при исходной машине, прослужившей 3 года).

6. Описанный процесс начинается в начале 1-го года, а заканчивается в начале 7-го года, т.е. сразу после окончания 6-го года. В каждом следующем состоянии (t, τ) 1-ая компонента t увеличивается на 1 независимо от выбранного управления С или Н. Поэтому любой из возмож-ных процессов состоит из 6 шагов, т.е. N = 6.

Приведём теперь разбиение всех состояний на слои (см. материал из раздела 3.1 до начала раздела 3.1.1. По построению, все состояния (t, τ), образующие один слой, содержат одну и ту же компоненту t. Итак:

S ₀ = s *; S ₁ = {(6,8), (6,5), (6,4), (6,3), (6,2), (6,1)}; S ₂ = {(5,7), (5,4), (5,3), (5,2), (5,1)};

S ₃ = {(4,6), (4,3), (4,2), (4,1)}; S ₄ = {(3,5), (3,2), (3,1)}; S ₅ = {(2,4), (2,1)}; S ₆ = {(1,3)}.

Итерация 1. Образуем таблицу 7.1, в которую при инициализации занесём исходные дан-ные. Таблица содержит 12 столбцов с разным числом строк. На этот раз ячейки состоят из 4-ёх клеток. В левой верхней клетке записано состояние (t, t), где t - текущий год (t = 1, 2,..., 6), t -

Таблица 7.1. Инициализация и итерация 1

(1,3)		(2,4)		(3,5)	−5	(4,6)	−10	(5,7)	−10	(6,8)	−15	s *
	−10		−15		−15		−15		−5	−10 Н	−10
		(2,1)		(3,2)		(4,3)		(5,4)		(6,5)
										80 С
				(3,1)		(4,2)		(5,3)		(6,4)
										90 С
						(4,1)		(5,2)		(6,3)
										95 С
								(5,1)		(6,2)
										115 С
										(6,1)
										130 С

возраст машины на начало года t. В верхней правой клетке записан доход за один год при вы-боре управления С (т.е. при продолжении работы на старой машине), в нижней правой клетке записан доход за один год при выборе управления Н (при покупке новой машины). Эти данные взяты из таблицы 6. Важной особенностью таблицы 7.1 является следующее: при t < 6 для каж-дого состояния (t, t) при выборе управления С следующим состоянием является то, которое за-писано в ячейке справа от (t, t); при выборе управления Н следующим состоянием является то, которое записано в нижней ячейке столбца справа от (t, t). При t = 6 следующим состоянием яв-ляется состояние s * (завершение процесса), независимо от выбора управления.

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

Итерация 2. Заполним оставшиеся пустыми клетки во 2-ом слое. В основе лежит уравне-ние Беллмана (8). В правую верхнюю клетку каждой ячейки из 2-го слоя таблицы 6.2 запишем сумму того, что там было, и числа из левой нижней клетки из ячейки справа. В соответствии с методом динамического программирования, это будет максимальный доход, если принять ре-шение С. В правую нижнюю клетку каждой ячейки из 2-го слоя таблицы 6.2 запишем сумму то-го, что там было, и числа из левой нижней клетки нижней ячейки из слоя справа. В соответст-вии с методом динамического программирования, это будет максимальный доход, если принять решение Н.

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

Таблица 7.2. Итерация 2

(1,3)		(2,4)		(3,5)	−5	(4,6)	−10	(5,7)	−25	(6,8)	−15	s *
	−10		−15		−15		−15	125 Н		−10 Н	−10
		(2,1)		(3,2)		(4,3)		(5,4)		(6,5)
								175 Н		80 С
				(3,1)		(4,2)		(5,3)		(6,4)
								185 С		90 С
						(4,1)		(5,2)		(6,3)
								185 С		95 С
								(5,1)		(6,2)
								240 С		115 С
										(6,1)
										130 С

Итерация 3. Заполним оставшиеся пустыми клетки во 3-ьем слое. Поступаем также, как на итерации 2. В правую верхнюю клетку каждой ячейки из 3-го слоя таблицы 7.3 запишем сумму того, что там было, и числа из левой нижней клетки из ячейки справа. В правую нижнюю клетку каждой ячейки из 3-го слоя таблицы 7.3 запишем сумму того, что там было, и числа из левой нижней клетки нижней ячейки из слоя справа. В остававшуюся до сих пор пустой левую левую нижнюю клетку каждой ячейки 3-го слоя запишем наибольшее из двух чисел в правых клетках этой же ячейки и букву С, если бóльшим оказалось верхнее число (букву Н, в против-ном случае). Таким образом, оптимальные действия для всех состояний из 3-го слоя (т.е в начале 4-го года) стали известными.

Таблица 7.3. Итерация 3

(1,3)		(2,4)		(3,5)	−5	(4,6)	−35	(5,7)	−25	(6,8)	−15	s *
	−10		−15		−15	225 Н		125 Н		−10 Н	−10
		(2,1)		(3,2)		(4,3)		(5,4)		(6,5)
						280 Н		175 Н		80 С
				(3,1)		(4,2)		(5,3)		(6,4)
						285 С		185 С		90 С
						(4,1)		(5,2)		(6,3)
						300 С		185 С		95 С
								(5,1)		(6,2)
								240 С		115 С
										(6,1)
										130 С

 

 

Далее аналогично выполняются итерации 4, 5 и 6.

Итерация 4:

Таблица 7.4. Итерация 4

(1,3)		(2,4)		(3,5)	−40	(4,6)	−35	(5,7)	−25	(6,8)	−15	s *
	−10		−15	285 Н		225 Н		125 Н		−10 Н	−10
		(2,1)		(3,2)		(4,3)		(5,4)		(6,5)
				360 С		280 Н		175 Н		80 С
				(3,1)		(4,2)		(5,3)		(6,4)
				395 С		285 С		185 С		90 С
						(4,1)		(5,2)		(6,3)
						300 С		185 С		95 С
								(5,1)		(6,2)
								240 С		115 С
										(6,1)
										130 С

 

Итерация 5:

Таблица 7.5. Итерация 5

(1,3)		(2,4)	−35	(3,5)	−40	(4,6)	−35	(5,7)	−25	(6,8)	−15	s *
	−10	380 Н		285 Н		225 Н		125 Н		−10 Н	−10
		(2,1)		(3,2)		(4,3)		(5,4)		(6,5)
		465 С		360 С		280 Н		175 Н		80 С
				(3,1)		(4,2)		(5,3)		(6,4)
				395 С		285 С		185 С		90 С
						(4,1)		(5,2)		(6,3)
						300 С		185 С		95 С
								(5,1)		(6,2)
								240 С		115 С
										(6,1)
										130 С

Итерация 6:

Таблица 7.6. Итерация 6

(1,3)	−30	(2,4)	−35	(3,5)	−40	(4,6)	−35	(5,7)	−25	(6,8)	−15	s *
455 Н		380 Н		285 Н		225 Н		125 Н		−10 Н	−10
		(2,1)		(3,2)		(4,3)		(5,4)		(6,5)
		465 С		360 С		280 Н		175 Н		80 С
				(3,1)		(4,2)		(5,3)		(6,4)
				395 С		285 С		185 С		90 С
						(4,1)		(5,2)		(6,3)
						300 С		185 С		95 С
								(5,1)		(6,2)
								240 С		115 С
										(6,1)
										130 С

Таким образом, оптимальная политика замен такова. Сразу, в начале 1-го года, меняем ис-ходную машину, проработавшую 3 года, на новую. Тем самым следующим является состояние (2,1). На этой машине работаем до начала 4-го года (состояние (4,3)), и опять меняем машину на новую, т.е. переходим в состояние (5,1). На последней машине работаем до конца срока, т.е. в течение 4-го, 5-го и 6-го годов. Переходы определяются буквами С и Н в левом нижнем столбце каждой ячейки. Максимальный доход составляет 455 единиц.

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

Задание 1. Решить указанным в разделе 3.1.2 методом задачу о замене машины при следу-ющих данных о новых машинах:

Машина, новая в начале 1-го года Возраст машины             Доход             Затраты на содержание             Затраты на замену             Машина, новая в начале 2-го года Возраст машины           Доход           Затраты на содержание           Затраты на замену           Машина, новая в начале 3-го года Возраст машины         Доход         Затраты на содержание         Затраты на замену

Машина, новая в начале 4-го года Возраст машины       Доход       Затраты на содержание       Затраты на замену       Машина, новая в начале 5-го года Возраст машины     Доход     Затраты на содержание     Затраты на замену     Машина, новая в начале 6-го года Возраст машины   Доход   Затраты на содержание   Затраты на замену

и различных данных об исходной машине:

Данные об исходной машине 1

Возраст машины
Доход
Затраты на содержание
Затраты на замену

 

Данные об исходной машине 2

Возраст машины
Доход
Затраты на содержание
Затраты на замену

 

Данные об исходной машине 1

<

Возраст машины
Доход

---

⇐ Предыдущая24252627282930313233Следующая ⇒

Поделиться с друзьями:

---

Дата добавления: 2016-10-07; Мы поможем в написании ваших работ!; просмотров: 578 | Нарушение авторских прав

---

Лучшие изречения:

© 2015-2024 lektsii.org - Контакты - Последнее добавление