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

14.03.2019

«Эталонной» задачей теории расписаний является проблема составления расписания работы технологической линии, известная в литературе под названием задачи Джонсона, по имени С.М.Джонсона, получившего основные аналитические результаты для простейших ситуаций (вариантов) – частных постановок этой задачи .

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

8.1.1 Постановка детерминированной задачи упорядочения,

построение и исследование математической модели

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

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

Традиционная постановка задачи Джонсона состоит в следующем: требуется выбрать порядок обработки деталей (изделий), сформировать (составить) расписание работы технологической линии, обеспечивающее минимальное суммарное время выполнения всего задания, а именно за минимальное время осуществить обработку группы из т деталей, каждая из которых должна последовательно пройти обработку на каждом из п станков, образующих технологическую линию. Предполагается заданным t ij - время обработки i -ой детали (i = 1,…, m ) на j -ом станке (j =1,…,n ).

Основными ограничениями задачи являются:

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

2) каждая деталь обрабатывается в строго определенном технологическом порядке;

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

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

Рассматриваемая задача – одна из типичных задач оперативно-календарного планирования для машиностроительных предприятий мелкосерийного и единичного производства.

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

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

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

Так, если предположить, что в задаче поиска оптимальной очередности, в случае всего 10 деталей затрачивается всего лишь одна минута, на построение каждого варианта расписания и вычисление соответствующего ему значения функции-критерия (критерия оптимальности). Тогда нетрудно подсчитать, что при использовании метода полного перебора (число вариантов равно 10!, то есть 3 628 800 вариантов) и даже при двадцатичетырехчасовом рабочем дне эту задачу пришлось бы решать... почти семь лет. В случае же 20 деталей (число вариантов равно 20!, то есть 2,433*1018 вариантов) даже с помощью современных, быстродействующих компьютеров такая задача методом полного перебора решалась бы более 77 тысяч лет!

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

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

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

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

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

Оставив пока в стороне вопрос об общих приемах сокращения объема перебора вариантов порядка (очередности) запуска, рассмотрим частный вариант постановки задачи Джонсона, когда число станковn =2. В этом частном случае удается установить простые приемы нахождения порядка запуска деталей, обеспечивающего наименьшую продолжительность выполнения задания (наименьшую длительность расписания), то есть минимальное суммарное время обработки группы из m деталей (m =6), каждая из которых должна последовательно пройти обработку на каждом из двух станков (сначала на первом, а затем на втором станках), образующих технологическую линию. Время обработки i -ой детали (i =1,…,m ) на j -ом станке (j =1,2) t ij предполагается заданным, и, как правило, для
. В таблице 8.1 представлены исходные данные рассматриваемого примера.

Таблица 8.1 - Исходные данные для задачи Джонсона и ее решение

детали, i	Время обработки i -ой детали на j -ом станке,(мин.)	очереди, k
детали, i		очереди, k

Изобразим графически процесс обработки деталей на двух станках для следующей произвольно выбранной очередности запуска деталей в обработку: А→Б→В→Г→Д→Е (рисунок 8.1) (нумерация деталей и последовательность их обработки совпадают).

Рисунок 8.1 – График процесса обработки группы деталей на двух станках

На рисунке 8.1
- суммарное время обработки группы изт деталей (т =6), то есть длительность совокупного производственного цикла – время, которое пройдет от момента начала обработки первой детали (i =А) на первом станке (j =1) до момента окончания обработки последней детали (i =Е) на втором станке (j =2) рассчитывается по формуле (8.1.1) и в рассматриваемом примере равно 41 мин.

где - время обработкиi -ой детали на втором станке,i = 1,…, m ;

- суммарное время обработки всех деталей на втором станке;

- суммарное время простоя второго станка (оборудования на второй операции);

- время простоя второго станка между окончанием выполнения работы по обработке (i -1)-ой детали на этом станке и началом обработкиi -ой детали на том же самом станке (для детали первой очереди запуска
);

- время обработки деталиk k = 1,…, m ;

- время обработки деталиk -ой очереди запуска на втором станке,k = 1,…, m -1;

Критерием оптимальности в данной постановке задачи и соответственно в экономико-математической модели является минимизация длительности совокупного производственного цикла

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

В нашем примере время простоя второго станка:

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

Известен весьма простой алгоритм для нахождения оптимальной последовательности (порядка) обработки т деталей на двух станках – алгоритм Джонсона.

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

1) выбирается деталь с наименьшей продолжительностью обработки на одном из станков; в нашем примере на первой итерации это деталь Б ;

2) выбранная деталь помещается в начало очереди, если наименьшая продолжительность обработки соответствует первому станку, или в конец очереди, если – второму станку; в нашем примере деталь Б помещается в конец очереди (k =6);

3) строка(и) таблицы 8.1, соответствующая(ие) выбранной(ым) детали(ям) исключается(ются) из дальнейшего рассмотрения (вычеркивается(ются));

4) выбирается деталь среди оставшихся со следующей наименьшей продолжительностью обработки на одном из станков; в нашем примере на второй итерации это деталь В , на третьей итерации это детальЕ , на четвертой итерации это деталиА иГ , на последней итерации это детальД ;

5) выбранная деталь помещается ближе к началу или к концу очереди по указанному в шаге 2 правилу; в нашем примере на второй итерации деталь В помещается ближе к концу очереди (k =5), перед детальюБ , на третьей итерации детальЕ помещается в начало очереди (k =1), на четвертой итерации детальА k =4), а детальГ помещается в начало очереди (k =2), на последней итерации детальД помещается ближе к концу очереди (k =3);

6) если определена очередность запуска для всех деталей, то решение получено, иначе переходим к шагу 3.

В итоге реализации данного алгоритма можно получить оптимальное расписание работы двух станков (рисунок 8.2). В нашем примере (см. таблицу 8.1) найдена оптимальная очередность запуска деталей в обработку - Е→Г→Д→А→В→Б . В последней графе таблицы 8.1 показан номер очереди запуска (k ) соответствующей детали в обработку на каждом станке технологической линии.

№ операции

Рисунок 8.2 – График оптимального расписания работы двух станков

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

(8.1.5)

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

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

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

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

Для пояснения алгоритма Джонсона представим матрицу Т как двухстолбцовую

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

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

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

Второй пример календарной задачи на оптимизацию заключается в построении графика , наилучшим образом согласующего сроки выпуска продукции на нескольких последовательных стадиях произ-ва (переделах) при различной длительности обработки изделия на каждой из них. Напр., в типографии надо согласовать работу наборного, печатного и переплетного цехов при условии различной трудо-станкоемкости по отдельным цехам разных видов изделий (бланочной продукции, книжной продукции простого или сложного набора, в переплете или без него и т. п.). Задача может решаться при различных критериях оптимизации и различных ограничениях. Так, можно решать задачу на минимальную длительность производств, цикла и, следовательно, минимальную величину среднего остатка изделий в незавершенном произ-ве (заделе) ограничения при этом должны определяться по наличной пропускной способности различных цехов (переделов). Возможна и другая постановка той же задачи, при к-рой критерием оптимизации является наибольшее использование наличной производств, мощности при ограничениях, наложенных на сроки выпуска отдельных видов продукции. Алгоритм для точного решения этой задачи (т. н. задачи Джонсон а) разработан для случаев, когда изделие проходит всего 2 операции, и для приближенного решения при трех операциях. При большем числе операций эти алгоритмы непригодны, что практически их обесценивает, т. к. потребность в решении задачи оптимизации календарного графика возникает гл. обр. в планировании многооперационных процессов (напр., в машиностроении). Е. Боуменом (США) в 1959 и А. Лурье (СССР) в 1960 предложены математически строгие алгоритмы, основанные на общих идеях линейного программирования и позволяющие в принципе решать задачу при любом числе операций. Однако в настоящее время (1965) практически применить эти алгоритмы нельзя они слишком громоздки в расчетном отношении даже для самых мощных из существующих электронных вычислительных машин . Поэтому указанные алгоритмы имеют лишь перспективное значение либо их удастся упростить, либо прогресс вычислительной техники позволит реализовать их на новых машинах.

Краткая теория

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

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

Типичные особенности многошаговых задач.

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

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

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

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

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

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

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

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

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

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

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

Дадим математическую формулировку принципа оптимальности для задач с аддитивным критерием оптимальности (сепарабельная функция цели). Для простоты будем считать, что начальное и конечное состояния системы заданы. Обозначим через значение функции цели на первом этапе при начальном состоянии системы и при управлении , через -соответствующее значение функции цели только на втором этапе, …., через - на этапе, …, через - на -м этапе. Очевидно, что

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

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

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

Начинаем с последнего этапа. Пусть - возможные состояния системы на начало -го этапа. Находим:

Для двух последних этапов получаем:

Аналогично:

…………………….

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

Пример решения задачи

Условие задачи

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

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

Выделяемые средства , млн.ден.ед.

Предприятие

№1

№2

№3

№4

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

100

Решение задачи

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

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

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

Выделяемые средства

100

Шаг 1

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

Шаг 2

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

Шаг 3

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

Шаг 4

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

0 0 0 0 0 20 10 12 12 16 40 31 31 36 37 60 42 43 48 52 80 62 62 67 73 100 76 76 79 85

Ответ

Оптимальный план распределения между 4 предприятиями 100 единиц ресурса:

При этом суммарный прирост продукции достигнет максимальной величины, равной 85.

Средняя стоимость решения контрольной работы 700 - 1200 рублей (но не менее 300 руб. за весь заказ). На цену сильно влияет срочность решения (от суток до нескольких часов). Стоимость онлайн-помощи на экзамене/зачете - от 1000 руб. за решение билета.

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

Примеры близких по теме задач

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

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

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

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

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

Для расширения производственных мощностей трех предприятий А, В и С выделяется некоторое количество единиц дополнительной электроэнергии в объеме х 0 =8 единиц. Электроэнергия может выделяться в виде 1, 2, 3, 4, 5, 6, 7 и 8 единиц. Вкладывая в развитие i-того предприятия х i единиц электроэнергии можно получить доход у i единиц на предприятии. Существуют разные варианты х i (к) выделения дополнительной электроэнергии. Они приносят доход у i (к), к=1,n. Возможные варианты развития предприятий приведены в табл.1. Суммарный доход по всем предприятиям должен быть максимальным, т.е у=? у i (к)>max

Табл. 1. Варианты развития предприятий

Вариант к	Предриятие А	Предприятие В	Предприятие С

Математическая постановка задачи:

у=? у i (к)> max

?х i (к)?х 0

Решение:

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

g C (S 2)=max k f c , x C (k)?S 2 , k=1,2,3,4

Табл. 2. Условно-оптимальные решения(шаг 3)

Состояние		Управление

Имеется четыре возможности вложения средств - четыре шаговых управления х С (1)=0ед., х С (2)=1ед., х С (3)=2ед., х С (4)=3ед. и девять теоретически возможных состояний системы S 2 , предшествующих выделению средств предприятию С, - объемы не распределенных к 3-му этапу инвестиций: 0,1,2,3,4,5,6,7,8.

Предположим, что система находилась в состоянии S 2 =2.Тогда, для шагового управления х С (2)=1 доход у С (2) будет равен 3ед. (Табл.3), а шаговое управление х С (3)=2 будет оптимальным для этого состояния, дающим условно-максимальный выигрыш g c (S 2)=5. Если система находилась в состоянии S 2 =3, то допустимы все шаговые управления х С (1)=0ед., х С (2)=1ед., х С (3)=2ед., х С (4)=3ед., а оптимальным будет управление х С (4)=3, которое обеспечивает условно максимальный выигрыш g c (S 2)=6.

Табл.3 динамический программирование распределение инвестиция

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

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

g А (S 1)=max k f А +g c ], x А (k)?S 1 , k=1,2,3,4

Так, для состояния S 1 =3 с шаговым управление х A (2)=1 получаем:

g А (S 1)=max k f А +g c ]

Max k 4+g c =4+5=9, где находим из таблицы 1, а g c из таблицы 3. Аналогично заполняются все состояния.

Табл. 4. Условно-оптимальные решения(шаг 2)

Состояние	f А +g c	Управление

Здесь возникают ситуации, при которых оптимальное решение будет не единственным, Так в состояние S 1 =3 условно оптимальными будут шаговые управления х A (2)=1 и х A (3)=2, дающие один и тот же выигрыш g A (S 1)=9

Табл. 5. Безусловно-оптимальные решения (шаг 1)

На первом этапе (Табл.5)-выделение инвестиций предприятию В - есть только одно предшествующее состояние системы, соответствующее начальному состоянию S 0 =8. Безусловно оптимальный выигрыш определяется выражением:

у * = g В (S 0)= max k {f А +g А } x в (k)?S 0 =x 0 , k=1,2,3,4,5

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

Схема нахождения всех оптимальных вариантов распределения инвестиций между предприятиями (Табл.6) представлена на рисунке 1.

Табл. 6. Оптимальные распределения инвестиций.

Рисунок 1. Схема оптимального распределения инвестиций между предприятиями

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

Размещено на Allbest.ru

...

Подобные документы

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

курсовая работа , добавлен 25.04.2015

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

курсовая работа , добавлен 30.12.2010

Метод динамического программирования и его основные этапы. Оптимальная стратегия замены оборудования. Минимизация затрат на строительство и эксплуатацию предприятий. Оптимальное распределение ресурсов в ООО "СТРОЙКРОВЛЯ" и инвестиций ПКТ "Химволокно".

курсовая работа , добавлен 08.01.2015

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

дипломная работа , добавлен 07.08.2013

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

курсовая работа , добавлен 14.01.2011

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

контрольная работа , добавлен 15.10.2010

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

курсовая работа , добавлен 16.12.2013

Характерные черты задач линейного программирования. Общая постановка задачи планирования производства. Построение математической модели распределения ресурсов фирмы. Анализ чувствительности оптимального решения. Составление отчета по устойчивости.

презентация , добавлен 02.12.2014

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

дипломная работа , добавлен 11.02.2017

Модель динамического программирования. Принцип оптимальности и уравнение Беллмана. Описание процесса моделирования и построения вычислительной схемы динамического программирования. Задача о минимизации затрат на строительство и эксплуатацию предприятий.

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

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

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

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

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

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

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

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

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

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

3.1. Задача оптимального распределения ресурсов

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

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

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

Воспользуемся рекуррентным соотношением Беллмана (3.1), которое для данной задачи приводит к следующим функциональным уравнениям при
:

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

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

Пример 3.1.

Для увеличения объемов выпуска пользующейся повышенным спросом продукции четырем предприятиям производственного объединения выделены средства в размере 50 млн. руб. Каждому из предприятий может быть выделено: 0, 10, 20, 30, 40 или 50 млн. руб. При этом ежегодный прирост выпуска продукции каждым из предприятий
в зависимости от капиталовложений известен и приведен в табл. 3.1.

Таблица 3.1

Объем выделенных средств x (млн. руб.)	Ежегодный прирост выпуска продукции (млн. руб.), в зависимости от объема выделенных средств
Объем выделенных средств x (млн. руб.)

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