Решение задачи о распределении ресурсов методом динамического программирования. Задача управления запасами. Пример: Оптимальное распределение ресурсов

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

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

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

1. Основные понятия

1.1. Модель динамического программирования

1.2. Принцип оптимальности. Уравнение Беллмана

2. Оптимальное распределение ресурсов

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

2.2 Двумерная модель распределения ресурсов

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

2.4 Учет последействия в задачах оптимального распределения ресурсов

Заключение

Список используемых источников

Приложение 1. Листинг программы для решения задачи оптимального распределения ресурсов с заданными параметрами. Результаты работы программы

Введение

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

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

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

Как раздел математического программирования, динамическое программирование (ДП) начало развиваться в 50-х годах XX в. благодаря работам Р. Беллмана и его сотрудников. Впервые этим методом решались задачи оптимального управления запасами, затем класс задач значительно расширился. Как практический метод оптимизации, метод динамического программирования стал возможен лишь при использовании современной вычислительной техники.

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

1. Основные понятия

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

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

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

Рисунок 1

Состояние

Предполагаем впредь, что состояние системы в конце k-го шага зависит только от предшествующего состояния системы

Равенства (1.1) получили название уравнений состояний. Функции

Варьируя управление U , получим различную «эффективность» процесса , которую будем оценивать количественно целевой функцией Z , зависящей от начального состояния системы

Показатель эффективности k-го шага процесса управления, который зависит от состояния

Если свойство аддитивности целевой функции Z не выполняется, то этого иногда можно добиться некоторыми преобразованиями функции. Например, если Z- мультипликативная функция, заданная в виде

Обычно условиями процесса на управление на каждом шаге

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

Инструкция . Выберите количество предприятий.

Пример №1 . Планируется работа двух предприятий на n лет. Начальные ресурсы равны s0. Средства x, вложенные в 1-е предприятие в начале года, дают в конце года прибыль f1(x), и возвращаются в размере g1(x). Средства y, вложенные в 2-е предприятие в начале года, дают в конце года прибыль f2(y) и возвращаются в размере g2(y). В конце года возвращенные средства заново перераспределяются между отраслями. Определить оптимальный план распределения средств и найти максимальную прибыль.

Задачу решим методом динамического программирования. Операцию управления производственным процессом разобьём на этапы. На каждом из них управление выберем так, чтобы оно приводило к выигрышу как на данном этапе, так и на всех последующих до конца операции. В этом состоит принцип оптимальности , сформулированный американским математиком А. Беллманом.
Разобьём весь период на три этапа по годам и будем нумеровать их, начиная с первого.
Обозначим через x k и y k количество средств выделяемых каждому предприятию на k-ом этапе, а через x k + y k = a k - общее количество средств на этом этапе. Тогда первое предприятие приносит на этом этапе 3 x k , а второе 4 y k единиц дохода. Общий доход на k-ом этапе 3x k + 4y k .
Обозначим через f k (a k) - максимальный доход, который получает отрасль от обоих предприятий на k-ом и всех последующих. Тогда функциональное уравнение, отражающее принцип оптимальности Беллмана, принимает вид:
f k (a k)= max{3 x k + 4 y k + f k +1 (a k +1)}. (1)
Так как x k + y k = a k , то y k = a k - x k и 3x k + 4y k = 3x k + 4(a k - x k) = - x k + 4a k . Поэтому f k (a k) = max{-x k + 4a k + f k+1 (ak+1)} . (2)
0 ≤ x k ≤ a k
Кроме того, ak - это средства выделяемые обои предприятиям на k-ом этапе, и они определяются остатком средств, получаемых на предыдущем (k-1)-ом этапе. Поэтому по условию задачи оптимальное управление на каждом этапе
a k = 0,5 x k -1 + 0,2 y k -1 = 0,5 x k -1 +0,2(a k -1 - x k -1) = 0,3 x k -1 +0,2 a k -1 . (3)

I.Условия оптимизации
Планирование начинаем с последнего третьего этапа

При k = 3 получаем из (2)
f 3 (a 3) = max {- x 3 + 4a 3 + f 4 (a 4)}
0 ≤ x 3 ≤ a 3
Так как четвёртого этапа нет, то f 4 (a 4)=0 и
f 3 (a 3) = max {- x 3 + 4a 3 }=4a 3
0 ≤ x 3 ≤ a 3
(максимум выражения (- x 3 + 4 a 3 ) будет при x 3 =0)).

Итак, для третьего последнего этапа имеем: f 3 (a 3) = 4 a 3 , x 3 = 0, y 3 = a 3 - x 3 = a 3 ,
где a 3 = 0,3x 2 + 0,2a 2 , что следует из формулы (3).

При k = 2 из (2) и (3) получаем:
f(a 2) = max {-x 2 + 4a 2 + f 3 (a 3)}=
0 ≤ x ≤ a 2
= max {-x 2 + 4a 2 + 4a 3 }= max {-x 2 + 4a 2 + 4(0,3x 2 + 0,2a 2)} max{0,2x 2 + 4,8a 2 } 5a
0 ≤ x ≤ a 2
т. к. максимум выражения (0,2 x 2 + 4,8 a 2 ) будет при x 2 = a 2 .
То для второго этапа имеем: f 2 (a 2) = 5a 2 , x 2 = a 2 , y 2 = a 2 x 2 = 0 , при этом
a 2 = 0,3x 1 + 0,2a 1 с учетом (3).
При k = 1 с учетом (2) и (3) получаем:
f 1 (a 1) = max {-x 1 + 4a 1 + f 2 (a 2)}=
0 ≤ x ≤ a 1
= max {-x 1 + 4a 1 + 5a 2 }= max {-x 1 + 4a 2 + 5(0,3x 1 + 0,2a 2)}= max {0,5x 1 + 5a 1 }=5,5a 1
0 ≤ x ≤ a 1
при x 1 = a 1 .
Итак, для первого этапа f 1 (a 1) = 5,5 a 1 , x 1 = a 1 , y 1 = 0.
Процесс закончен. На первом этапе общее количество распределяемых средств известно -a 1 = 900 ед. Тогда максимальный доход, получаемый обоими предприятиями за три года составит f 1 (a 1) = 5,5*900 = 4950 ден. ед.

II. Безусловная оптимизация
Выясним, каким должно быть оптимальное управление процессом выделения средств между первым и вторым предприятиями для получения максимального дохода в количестве 4950 ден. ед.
1-й год. Так как x 1 = a 1 и , y 1 = 0, то все средства в количестве 900 ден. ед. отдаются первому предприятию.
2-й год. Выделяются средства a 2 = 0,3x 1 + 0,2a 1 = 0,5 a 1 =450 ед., x 2 = a 2 , y 2 = 0.
Все они передаются первому предприятию.
3-й год . Выделяются средства a 3 = 0,3x 2 + 0,2a 2 = 0,5 a 2 = 225 ед., x 3 = 0, y 3 = a 3 . Все они передаются второму предприятию.
Результаты решения представим в виде таблицы.

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

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

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

Управляемая система S в данном случае - средства или ресурсы, которые распределяются. Состояние системы S перед каждым шагом характеризуется одним числом S - наличным запасом еще не вложенных средств. В этой задаче «шаговыми управлениями» являются средства выделяемые предприятиям. Требуется найти оптимальное управление, т. е. такую совокупность чисел при которой суммарный доход максимален:

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

Начнем оптимизацию с последнего, шага. Пусть мы подошли к этому шагу с остатком средств S. Что нам делать? Очевидно, вложить всю сумму S целиком в предприятие Поэтому условное оптимальное управление на -м шаге: отдать последнему предприятию все имеющиеся средства S, т. е.

а условный оптимальный выигрыш

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

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

и нужно найти такое , при котором этот выигрыш максимален:

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

и соответствующее ему условное оптимальное управление - то значение при котором этот максимум достигается.

Продолжая таким образом, дойдем, наконец, до предприятия Здесь нам не нужно будет варьировать значения S; мы точно знаем, что запас средств перед первым шагом равен К:

Итак, максимальный выигрыш (доход) от всех предприятий найден. Теперь остается только «прочесть рекомендации». То значение при котором достигается максимум (13.4), и есть оптимальное управление на 1-м шаге.

После того как мы вложим эти средства в 1-е предприятие, у нас их останется . «Читая» рекомендацию для этого значения S, выделяем второму предприятию оптимальное количество средств: и т. д. до конца.

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

Таблица 13.1

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

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

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

Таблица 13.2

В первом столбце каждой пары приводится значение условного оптимального управления, во втором - условного оптимального выигрыша. Таблица заполняется слева направо, сверху вниз. Решение на пятом - последнем - шаге вынужденное: выделяются все средства; на всех остальных шагах решение приходится оптимизировать. В результате последовательной оптимизации 5-го, 4-го, 3-го, 2-го и 1-го шагов мы получим полный список всех рекомендаций по оптимальному управлению и безусловный оптимальный выигрыш W за всю операцию - в данном случае он равен 5,6. В последних двух столбцах таблицы 13.2 заполнена только одна строка, так как состояние системы перед началом первого шага нам в точности известно: . Оптимальные управления на всех шагах выделены рамкой. Таким образом, мы получили окончательный вывод: надо выделить первому предприятию две единицы из десяти, второму - пять единиц, третьему - две, четвертому - ни одной, пятому - одну единицу. При этом распределении доход будет максимален и равен 5,6.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Аналогично:

…………………….

…………………….

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

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

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

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

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

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

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

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

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

Шаг 1

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

Шаг 2

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

Шаг 3

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

Шаг 4

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

Ответ

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

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

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

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

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

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

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

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