47658 (Модель распределения ресурсов), страница 3
Описание файла
Документ из архива "Модель распределения ресурсов", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "47658"
Текст 3 страницы из документа "47658"
Будем рассматривать процесс распределения средств как n-шаговый, в котором номер шага соответствует номеру года. Управляемая система — два предприятия с вложенными в них средствами. Система характеризуется одним параметром состояния — количеством средств, которые следует перераспределить в начале k-го года. Переменных управления на каждом шаге две: и — количество средств, выделенных соответственно предприятию I и II. Так как средства ежегодно перераспределяются полностью, то . Для каждого шага задача становится одномерной. Обозначим через , тогда .
Показатель эффективности k-го шага равен . Это—доход, полученный от двух предприятий в течение k-го года.
Показатель эффективности задачи—доход, полученный от двух предприятий в течение n лет—составляет
. (2.5)
Уравнение состояния выражает остаток средств после k-го шага и имеет вид
. (2.6)
Пусть — условный оптимальный доход, полученный от распределения средств между двумя предприятиями за п—k+1 лет, начиная с k-го года до конца рассматриваемого периода. Запишем рекуррентные соотношения для этих функций:
; (2.7)
,
где - определяется из уравнения состояния (2.6).
Задача 3. Решить задачу 2 при следующих условиях: ; ; ; ; ; .
Если и - средства, выделенные соответственно предприятиям I и II в k-м году, то суммарный доход, полученный от обоих предприятий, равен
,
а уравнение состояния (2.6) принимает вид
.
Основные функциональные уравнения (2.7) запишутся следующим образом:
;
.
Проведем этап условной оптимизации.
4-й шаг. Условный оптимальный доход равен
,
так как линейная относительно функция достигает максимума в конце интервала, т.е. при .
3-й шаг:
.
Коэффициент при отрицателен, поэтому максимум в этой линейной относительно функции достигается в начале интервала, т.е.
; .
2-й шаг:
, откуда ; .
1-й шаг:
при .
Результат условной оптимизации:
; ; ; ;
; ; ;
Перейдем к безусловной оптимизации. Полагаем ; тогда , . Зная , находим ; используя , получаем и . Аналогично , . Наконец, . Следовательно, средства по годам нужно распределить так:
Год | |||||
Предприятие | 1 | 2 | 3 | 4 | |
I | 0 | 0 | 0 | 5120 | |
II | 10000 | 8000 | 6400 | 0 |
При таком распределении средств (10000 руб.) за четыре года будет получен доход, равный .
Непрерывные модели, примером которых служит задача 3, не являются типичными в практике распределения ресурсов. В дальнейшем большинство задач будет носить дискретный характер.
2.3 Дискретная динамическая модель оптимального распределения ресурсов
При дискретном вложении ресурсов может возникнуть вопрос о выборе шага в изменении переменных управления. Этот шаг может быть задан или определяется исходя из требуемой точности вычислений и точности исходных данных. В общем случае эта задача сложна, требует интерполирования по таблицам на предыдущих шагах вычисления. Иногда предварительный анализ уравнения состояния позволяет выбрать подходящий шаг , а также установить предельные значения , для которых на каждом шаге нужно выполнить табулирование.
Рассмотрим двумерную задачу, аналогичную предыдущей, в которой строится дискретная модель ДП процесса распределения ресурсов.
Задача 3. Составить оптимальный план ежегодного распределения средств между двумя предприятиями в течение трёхлетнего планового периода при следующих условиях: 1) начальная сумма составляет 400; 2) вложенные средства в размере x приносят на предприятии I доход и возвращаются в размере 60% от x, а на предприятии II—соответственно и 20%; 3) ежегодно распределяются все наличные средства, получаемые из возвращенных средств: 4) функции и заданы в табл. 1:
Таблица 1
x
| 50 | 100 | 150 | 200 | 250 | 300 | 350 | 400 |
| 6 | 10 | 15 | 26 | 28 | 38 | 45 | 49 |
| 8 | 12 | 20 | 28 | 35 | 40 | 46 | 48 |
Модель динамического программирования данной задачи аналогична модели, составленной в задаче 1.
Процесс управления является трехшаговым. Параметр — средства, подлежащие распределению в k-м году (k=1, 2, 3). Переменная управления — средства, вложенные в предприятие I в k-м году. Средства, вложенные в предприятие II в k-м году, составляют . Следовательно, процесс управления на k-м шаге зависит от одного параметра (модель одномерная). Уравнение состояния запишется в виде
, (2.8)
а функциональные уравнения – в виде
, (2.9)
. (2.10)
Попытаемся определить максимально возможные значения, для которых необходимо проводить табулирование на k-м шаге (k=1, 2, 3). При из уравнения (2.8) определяем максимально возможное значение ; имеем =0,6-400= 2400 (все средства вкладываются в предприятие I). Аналогично, для получаем предельное значение . Пусть интервал изменения совпадает с табличным, т. е. =50. Составим таблицу суммарной прибыли на данном шаге: (см. табл. 2). Это облегчит дальнейшие расчеты. Так как , то клетки, расположенные по диагонали таблицы, отвечают одному и тому же значению , указанному в 1-й строке (в 1-м столбце) табл. 2. Во 2-й строке таблицы записаны значения , а во 2-м столбце — значения , взятые из табл. 1. Значения в остальных клетках таблицы получены сложением чисел и . стоящих во 2-й строке и во 2-м столбце и соответствующих столбцу и строке, на пересечении которых находится данная клетка. Например, для =150 получаем ряд чисел: 20—для x=0, у=150; 18—для x=50, y==100; 18— для x=100, y=50; 15—для x=150, y=0.
Таблица 2
x y | 0 | 50 | 100 | 150 | 200 | 250 | 300 | 350 | 400 | ||
0 | 0 | 6 | 10 | 15 | 26 | 28 | 38 | 45 | 49 | ||
50 | 8 | 14 | 18 | 23 | 34 | 36 | 46 | 53 | |||
100 | 12 | 18 | 22 | 27 | 38 | 40 | 50 | ||||
150 | 20 | 26 | 30 | 35 | 46 | 48 | |||||
200 | 28 | 34 | 38 | 43 | 54 | ||||||
250 | 35 | 41 | 45 | 50 | |||||||
300 | 40 | 46 | 50 | ||||||||
350 | 46 | 52 | |||||||||
400 | 48 |
Аналогичную таблицу полезно подготовить и для расчетов по формуле (2.8). Расчет приведен в табл.3.
Таблица 3
x y | 0 | 50 | 100 | 150 | 200 | 250 | 300 | 350 | 400 | ||||
0 | 0 | 30 | 60 | 90 | 120 | 150 | 180 | 210 | 240 | ||||
50 | 10 | 40 | 70 | 100 | 130 | 160 | 190 | 220 | |||||
100 | 20 | 50 | 80 | 110 | 140 | 170 | 200 | ||||||
150 | 30 | 60 | 90 | 120 | 150 | 180 | |||||||
200 | 40 | 70 | 100 | 130 | 160 | ||||||||
250 | 50 | 80 | 110 | 140 | |||||||||
300 | 60 | 90 | 120 | ||||||||||
350 | 70 | 100 | |||||||||||
400 | 80 |
Проведем условную оптимизацию по обычной схеме.
3-й шаг. Основное уравнение (2.9)
решим с помощью табл. 2. Как указывалось выше, . Просмотрим числа на диагоналях, соответствующих ; 50; 100; 150 и на каждой диагонали выберем наибольшее. Это и есть . В 1-й строке находим соответствующее условное оптимальное управление. Данные оптимизации на 3-м шаге поместим в основную таблицу (табл. 4). В ней введен столбец , который в дальнейшем используется при интерполяции.
Оптимизация 2-го шага проведена в табл. 5 согласно уравнению вида (2.10):