Letysite.ru

IT Новости с интернет пространства
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Метод динамического программирования онлайн калькулятор

Динамическое программирование для начинающих

    Статьи, 7 июня 2016 в 15:04

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

О чём вообще речь? Что такое динамическое программирование?

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

Хорошо, как это использовать?

Решение задачи динамическим программированием должно содержать следующее:

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

И что, мне для решения рекурсивный метод писать надо? Я слышал, они медленные.

Конечно, не надо, есть и другие подходы к реализации динамики. Разберём их на примере следующей задачи:

Идея решения

Здесь нам даны и начальные состояния (a = a1 = 1), и зависимости. Единственная сложность, которая может возникнуть — понимание того, что 2n — условие чётности числа, а 2n+1 — нечётности. Иными словами, нам нужно проверять, чётно ли число, и считать его в зависимости от этого по разным формулам.

Рекурсивное решение

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

И она отлично работает, но есть нюансы. Если мы захотим вычислить f(12) , то метод будет вычислять сумму f(6)+f(5) . В то же время, f(6)=f(3)+f(2) и f(5)=f(2)-f(1) , т.е. значение f(2) мы будем вычислять дважды. Спасение от этого есть — мемоизация (кеширование значений).

Рекурсивное решение с кэшированием значений

Идея мемоизации очень проста — единожды вычисляя значение, мы заносим его в какую-то структуру данных. Перед каждым вычислением мы проверяем, есть ли вычисляемое значение в этой структуре, и если есть, используем его. В качестве структуры данных можно использовать массив, заполненный флаговыми значениями. Если значение элемента по индексу N равно значению флага, значит, мы его ещё не вычисляли. Это создаёт определённые трудности, т.к. значение флага не должно принадлежать множеству значений функции, которое не всегда очевидно. Лично я предпочитаю использовать хэш-таблицу — все действия в ней выполняются за O(1), что очень удобно. Однако, при большом количестве значений два числа могут иметь одинаковый хэш, что, естественно, порождает проблемы. В таком случае стоит использовать, например, красно-чёрное дерево.

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

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

Последовательное вычисление

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

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

LATOKEN, Москва, от 200 000 до 360 000 ₽

Суть метода в следующем: мы создаём массив на N элементов и последовательно заполняем его значениями. Вы, наверное, уже догадались, что таким образом мы можем вычислять в том числе те значения, которые для ответа не нужны. В значительной части задач на динамику этот факт можно опустить, так как для ответа часто бывают нужны как раз все значения. Например, при поиске наименьшего пути мы не можем не вычислять путь до какой-то точки, нам нужно пересмотреть все варианты. Но в нашей задаче нам нужно вычислять приблизительно log2(N) значений (на практике больше), для 922337203685477580-го элемента (MaxLong/10) нам потребуется 172 вычисления.

Ещё одним минусом такого подхода является сравнительно большой расход памяти.

Создание стека индексов

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

Зависимости вычисляются следующим образом:

Полученный размер стека – то, сколько вычислений нам потребуется сделать. Именно так я получил упомянутое выше число 172.

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

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

Конечно, такое решение гораздо более трудоёмкое, однако это того стоит.

Хорошо, математика — это красиво. А что с задачами, в которых не всё дано?

Для больше ясности разберём следующую задачу на одномерную динамику:

На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через 2. (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.) Определить число всевозможных «маршрутов» мячика с вершины на землю.

Идея решения

На первую ступеньку можно попасть только одним образом — сделав прыжок с длиной равной единице. На вторую ступеньку можно попасть сделав прыжок длиной 2, или с первой ступеньки — всего 2 варианта. На третью ступеньку можно попасть сделав прыжок длиной три, с первой или со втрой ступенек. Т.е. всего 4 варианта (0->3; 0->1->3; 0->2->3; 0->1->2->3). Теперь рассмотрим четвёртую ступеньку. На неё можно попасть с первой ступеньки — по одному маршруту на каждый маршрут до неё, со второй или с третьей — аналогично. Иными словами, количество путей до 4-й ступеньки есть сумма маршрутов до 1-й, 2-й и 3-й ступенек. Математически выражаясь, F(N) = F(N-1)+F(N-2)+F(N-3). Первые три ступеньки будем считать начальными состояниями.

Читать еще:  Предикат в программировании это

Реализация через рекурсию

Здесь ничего хитрого нет.

Реализация через массив значений

Исходя из того, что, по большому счёту, простое решение на массиве из N элементов очевидно, я продемонстрирую тут решение на массиве всего из трёх.

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

Там вверху ещё было написано про какую-то двумерную динамику.

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

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

Идея решения

Логика решения полностью идентична таковой в задаче про мячик и лестницу — только теперь в клетку (x,y) можно попасть из клеток (x-1,y) или (x, y-1). Итого F(x,y) = F(x-1, y)+F(x,y-1). Дополнительно можно понять, что все клетки вида (1,y) и (x,1) имеют только один маршрут — по прямой вниз или по прямой вправо.

Реализация через рекурсию

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

Реализация через массив значений

Классическое решение динамикой, ничего необычного — проверяем, является ли клетка краем, и задаём её значение на основе соседних клеток.

Отлично, я всё понял. На чём мне проверить свои навыки?

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

Взрывоопасность

При переработке радиоактивных материалов образуются отходы двух видов — особо опасные (тип A) и неопасные (тип B). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Стопка считается безопасной, если она не является взрывоопасной. Для заданного количества контейнеров N определить количество возможных типов безопасных стопок.

Решение

Ответом является (N+1)-е число Фибоначчи. Догадаться можно было, просто вычислив 2-3 первых значения. Строго доказать можно было, построив дерево возможных построений.

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

Реализация

Подъём по лестнице

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

Решение

Очевидно, что сумма, которую мальчик отдаст на N-ой ступеньке, есть сумма, которую он отдал до этого плюс стоимость самой ступеньки. «Сумма, которую он отдал до этого» зависит от того, с какой ступеньки мальчик шагает на N-ую — с (N-1)-й или с (N-2)-й. Выбирать нужно наименьшую.

Реализация

Калькулятор

Имеется калькулятор, который выполняет три операции:

  • Прибавить к числу X единицу;
  • Умножить число X на 2;
  • Умножить число X на 3.

Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N. Выведите это число, и, на следующей строке, набор исполненных операций вида «111231».

Решение

Наивное решение состоит в том, чтобы делить число на 3, пока это возможно, иначе на 2, если это возможно, иначе вычитать единицу, и так до тех пор, пока оно не обратится в единицу. Это неверное решение, т.к. оно исключает, например, возможность убавить число на единицу, а затем разделить на три, из-за чего на больших числах (например, 32718) возникают ошибки.

Правильное решение заключается в нахождении для каждого числа от 2 до N минимального количества действий на основе предыдущих элементов, иначе говоря: F(N) = min(F(N-1), F(N/2), F(N/3)) + 1. Следует помнить, что все индексы должны быть целыми.

Для воссоздания списка действий необходимо идти в обратном направлении и искать такой индекс i, что F(i)=F(N), где N — номер рассматриваемого элемента. Если i=N-1, записываем в начало строки 1, если i=N/2 — двойку, иначе — тройку.

Реализация

Самый дешёвый путь

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

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

Решение

В любую клетку таблицы мы можем попасть либо из клетки, находящейся непосредственно над ней, либо из клетки, находящейся непосредственно слева. Таким образом, F(x,y) = min(F(x-1,y), F(x,y-1)). Чтобы не обрабатывать граничные случаи, можно добавить первую строку и столбец, заполненные некоторой константой — каким-то числом, заведомо большим содержимого любой из клеток.

Суть методов динамического программирования

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

Рассмотрим общее описание задачи динамического программирования.
Пусть многошаговый процесс принятия решений разбивается на n шагов. Обозначим через ε 0 – начальное состояние системы, через ε 1 , ε 2 , … ε n – состояния системы после первого, второго, n-го шага. В общем случае состояние ε k – вектор (ε k 1, …, ε k s).
Управлением в многошаговом процессе называется совокупность решений (управляющих переменных) u k = (u k 1, . u k r), принимаемых на каждом шаге k и переводящих систему из состояния ε k -1 = (ε k- 1 1, …, ε k -1 s) в состояние ε k = (ε k 1, …, ε k s).
В экономических процессах управление заключается в распределении и перераспределении средств на каждом этапе. Например, выпуск продукции любым предприятием – управляемый процесс, так как он определяется изменением состава оборудования, объемом поставок сырья, величиной финансирования и т. д. Совокупность решений, принимаемых в начале года, планируемого периода, по обеспечению предприятия сырьем, замене оборудования, размерам финансирования и т. д. является управлением. Казалось бы, для получения максимального объема выпускаемой продукции проще всего вложить максимально возможное количество средств и использовать на полную мощность оборудование. Но это привело бы к быстрому изнашиванию оборудования и, как следствие, к уменьшению выпуска продукции. Следовательно, выпуск продукции надо спланировать так, чтобы избежать нежелательных эффектов. Необходимо предусмотреть мероприятия, обеспечивающие пополнение оборудования по мере изнашивания, т. е. по периодам времени. Последнее хотя и приводит к уменьшению первоначального объема выпускаемой продукции, но обеспечивает в дальнейшем возможность расширения производства. Таким образом, экономический процесс выпуска продукции можно считать состоящим из нескольких этапов (шагов), на каждом из которых осуществляется влияние на его развитие.
Началом этапа (шага) управляемого процесса считается момент принятия решения (о величине капитальных вложений, о замене оборудования определенного вида и т. д.). Под этапом обычно понимают хозяйственный год.
Обычно на управление на каждом шаге u k накладываются некоторые ограничения. Управления, удовлетворяющие этим ограничениям, называются допустимыми.
Предполагая, что показатель эффективности k-го шага процесса зависит от начального состояния на этом шаге k -1 и от управления на этом шаге u k , получим целевую функцию всего многошагового процесса в виде:
.

Читать еще:  Типы задач линейного программирования

Сформулируем теперь задачу динамического программирования: «Определить совокупность допустимых управлений (u 1 , …, u n ), переводящих систему из начального состояния ε 0 в конечное состояние ε n и максимизирующих или минимизирующих показатель эффективности F».
Управление, при котором достигается максимум (минимум) функции F называется оптимальным управлением u * = (u 1* ,…, u n * ).
Если переменные управления u k принимают дискретные значения, то модель ДП называется дискретной. Если переменные u k изменяются непрерывно, то модель ДП называется непрерывной.
В зависимости от числа параметров состояния s и числа управляющих переменных r различают одномерные и многомерные задачи ДП.
Число шагов в задаче может быть конечным или бесконечным.

Динамическое программирование для основных групп

Условия задач на динамическое программирование для основных групп

Черепаха

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

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

Формат входных данных

В первой строке входных данных записаны два натуральных числа N и M, не превосходящих 100 — размеры таблицы. Далее идет N строк, каждая из которых содержит M чисел, разделенных пробелами — описание таблицы. Все числа в клетках таблицы целые и могут принимать значения от 0 до 100.

Формат выходных данных

Программа должна вывести единственное число: максимальную возможную стоимость маршрута черепашки.

Маршрут черепашки

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

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

Формат входных данных

В первой строке входных данных записаны два натуральных числа N и M, не превосходящих 100 — размеры таблицы. Далее идет N строк, каждая из которых содержит M чисел, разделенных пробелами — описание таблицы. Все числа в клетках таблицы целые и могут принимать значения от 0 до 100.

Формат выходных данных

Первая строка выходных данных содержит максимальную возможную сумму, вторая – маршрут, на котором достигается эта сумма. Маршрут выводится в виде последовательности, которая должна содержать N-1 букву D, означающую передвижение вниз и M-1 букву R, означающую передвижение направо. Если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них.

Взрывоопасность

При переработке радиоактивных материалов образуются отходы двух видов — особо опасные (тип A) и неопасные (тип B). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Для заданного количества контейнеров N определить число безопасных стопок.

Формат входных данных Одно число 1 ≤ N ≤ 20.

Формат выходных данных Одно число — количество безопасных вариантов формирования стопки.

Взрывоопасность-2

При переработке радиоактивных материалов образуются отходы трех видов — особо опасные (тип A), неопасные (тип B) и совсем не опасные (тип C). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Для заданного количества контейнеров N определить число безопасных стопок.

Формат входных данных Одно число 1 ≤ N ≤ 20.

Формат выходных данных Одно число — количество безопасных вариантов формирования стопки.

Без трех единиц

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

Формат входных данных Одно число 1 ≤ N ≤ 40.

Формат выходных данных Выведите количество искомых последовательностей. Гарантируется, что ответ не превосходит 2 31 − 1.

Подсказка: Рассмотрим последовательности длины N, на первом месте может стоять 0, таких будет f(N-1), при подстановке 1, второе может быть 0, таких будет f(N-2), и 1,таких f(N-3). Так как трех единиц не может быть, по условию, просто просуммируем полученные значения до нужного N, записывая каждый в массив: f[n] = f[n-1] + f[n-2] + f[n-3]; Ответ будет находиться в f[n];

Калькулятор

Имеется калькулятор, который выполняет три операции:

  1. Прибавить к числу X единицу.
  2. Умножить число X на 2.
  3. Умножить число X на 3.

Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N. Формат входных данных Одно число 1 ≤ N ≤ 10 6 .

Формат выходных данных Одно число: наименьшее количество искомых операций.

Подсказка: Предположим в массиве a[i] при i 6 .

Формат выходных данных Выведите строку, состоящую из цифр «1», «2» или «3», обозначающих одну из трех указанных операций, которая получает из числа 1 число N за минимальное число операций. Если возможных минимальных решений несколько, выведите любое из них.

Читать еще:  Программа языки программирования

Подсказка: Предположим в массиве a[i] при i

Как решить задачу динамического программирования

ЗАКАЗАТЬ РЕШЕНИЕ ЗАДАЧ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
Решение задач данного типа студентами осуществляется на дисциплинах, связанных с методами оптимизации, и высшей математикой. В целом динамическое программирование – это широкая тема в исследованиях операций. Его выделяют даже в самостоятельную науку, появившуюся в связи с потребностью находить наиболее выгодные способы действия в условиях неопределенности.

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

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

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

Виды задач

От вас может требоваться:

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

Способы решения

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

Вы можете скачать по этой ссылке учебник Красса и Чупрынова – высшая математика и её приложение в экономическом образовании. Когда откроете, нажмите сочетание клавиш Ctrl+F и введите в строке поиска тему, которая вам нужна. По ключевым словам вы всё найдёте. Так же можно пролистать в конец учебника и пройтись по оглавлению. Темы описаны доступным языком, изложена каждая деталь. Разбирайтесь и вникайте.

Можно применить онлайн-калькулятор. Многие из них сейчас предоставляют решения в развернутом виде. Однако если вы это сделаете, вам вряд ли удастся ответить на дополнительные вопросы преподавателя, которые, вероятнее всего, возникнут. Просто введите в Google или Яндекс «Онлайн калькулятор. Динамическое программирование».

Есть так же способы решения всего этого через программу Microsoft Excel. В статье на нашем сайте описано, как решить транспортную задачу таким методом. Это вам может помочь при проверке вашего решения, так как развернутого ответа тут не будет. Решение на бумаге происходит в несколько этапов и скорее наугад, потому что подходов существует много для проверки того, верно ли мы нашли оптимальный вариант. Ручного способа достоверно и сразу найти то, что нужно пока не существует.

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

Высшая математика и экономика

Образовательные онлайн сервисы: теория и практика

Примеры — Математическое программирование

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

Решение

Процесс распределения средств разобъем на 4 этапа – по соответствующим годам.
Обозначим — средства, которые распределяются на к–ом шаге как сумма средств по предприятиям.

Суммарный доход от обоих предприятий на к–ом шаге:

Остаток средств от обоих предприятий на к–ом шаге:

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

Проведем оптимизацию, начиная с четвертого шага:

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

3-й шаг.

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

2-й шаг.

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

1-й шаг.

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

Результаты оптимизации:



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

Т.к. , получаем


Представим распределение средств в виде таблицы:

При таком распределении средств за 4 года будет получен доход, равный

Задача 2. Предприятие изготавливает продукцию, спрос на которую в каждом из месяцев планируемого периода Dt (t =) тыс. ед. Запас продукции на складе на начало планируемого периода i0 тыс.ед. Затраты на производство продукции складываются из условно постоянных затрат, равных kден.ед., и пропорциональных затрат, равных Lxt. Затраты на хранение 1 тыс. ед. продукции составляют h ден.ед. Складские площади позволяют хранить не более М тыс.ед. продукции. Производственные мощности ограничены, и в каждом месяце предприятие может произвести не более В тыс.ед. продукции. Требуется разработать производственную программу изготовления продукции xt удовлетворяющую спрос в каждом из месяцев планируемого периода и обеспечивающую минимальные затраты на производство продукции и содержание запасов. Запас продукции на складе в конце планируемого периода должен быть равен нулю.
Все необходимые числовые данные приведены в таблице.

Решение
Для решения задачи методом динамического программирования и записи рекуррентного соотношения будем использовать следующие обозначения: n — номер планового отрезка времени периода; j — уровень запаса на конец отрезка; dn— спрос на продук­цию на n-м отрезке;

cn(x,j)= c(x)+j h — затраты, связанные с выпуском х единиц продукции на n-м отрезке и содержанием запасов, объем которых на конец n-го отрезка равен единицу j; fn(i)— значение функции, равное затратам на производство и хранение продук­ции за последние n месяцев при условии, что уровень запасов на начало n-гo месяца составляет i единиц; xn(i)— производство про­дукции на n-м отрезке, если уровень запасов на начало отрезка равен i единиц. Изобразим плановый период на рисунке и для на­глядности нанесем на него числовые данные

D1 = 3 D2 = 5 D3 = 4

i 0 = 2 n =3 n = 2 n = 1 j 4 = 0
d3 = 3 d2 = 5 d1 = 4
x3 x2 x1

Т.к. c(x)=k+Lxто c(0)=0; c(l)=5; c(2)=6; c(3)=7; c (4)=8; c(5)=9; c(6)=10; c(7)=11; Уровень запасов на конец планового периода должен быть равен нулю, то для n=0 имеем f0(0)=0. Перейдем к рассмотрению первого отрезка, т.е. n=1.
Тогда функциональные уравнения Беллмана для рассматриваемой задачи имеют следующий вид: для n =1
f1(i)=c1(d1-i, 0) = c1(d1-i, 0) , где i может принимать значения 0, 1, 2, 3, 4.
Расчет всех значений выполним в виде таблицы.

Ссылка на основную публикацию
Adblock
detector