Распределение ресурсов по трем отраслям
17
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
"САРОВСКИЙ ГОСУДАРСТВЕННЫЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ"
ЭКОНОМИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
К КУРСОВОЙ РАБОТЕ
На тему:
СТУДЕНТ (группа ИС-45Д)
РУКОВОДИТЕЛЬБеляев С.П.
г. Саров 2008 г
Оглавление
- ВВЕДЕНИЕ 3
- ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 4
- Исходные параметры 5
- Искомые параметры 6
- МЕТОД РЕШЕНИЯ 6
- ОБОСНОВАНИЕ ВЫБОРА ПРОГРАММНЫХ СРЕДСТВ 9
- ОПИСАНИЕ ИНТЕРФЕЙСА ПОЛЬЗОВАТЕЛЯ 10
- СПИСОК ЛИТЕРАТУРЫ 11
ВВЕДЕНИЕОсновная часть данной работы направлена на практическое освоение метода динамического программирования на примере решения хорошо изученных задач, а именно: простейшей задачи оптимального распределения ресурсов и задачи управления запасами продукта при случайном спросе на него.Кроме теоретических основ и практических рекомендаций, необходимых для численного решения указанных задач, связанных с простым классом одномерных процессов распределения [1], дополнительно рассматриваются задачи оптимального распределения при наличии двух типов ресурсов и двух типов ограничений, в рамках которых возможны не только постановка и решение большого числа прикладных задач [1, 5], но также выявление существенных и качественных особенностей, связанных с применением метода динамического программирования, при переходе к задачам с многомерными процессами распределения.
Цель работы: знакомство с постановкой задачи оптимального распределения ограниченного ресурса и методом множителей Лагранжа в задачах условной оптимизации, изучение принципа оптимальности Беллмана и вычислительной схемы решения задачи оптимального распределения ограниченного ресурса методом динамического программирования, разработка программы для численного решения задачи и проведение расчетов.
ТЕОРЕТИЧЕСКАЯ ЧАСТЬПостановка простейшей задачи оптимального распределенияограниченного ресурсаВ различных производственно-экономических системах значительное число решаемых задач тесно связано с эффективным использованием и распределением ограниченных ресурсов, необходимых для нормального функционирования таких систем. Переходя к формулировке одной из простейшей задач такого класса, вначале опишем кратко процессы, обусловливающие возникновение этого типа задач.Пусть некоторая производственно-экономическая система располагает заданным количеством какого-либо экономического ресурса, под которым подразумеваются материальные, трудовые, финансовые либо иные ресурсы, необходимые для функционирования системы. В случае нескольких потребителей указанного ресурса или далее соответствующих технологических процессов возникает следующая задача: разделить имеющееся количество ресурса между ними так, чтобы максимизировать их суммарную эффективность или получаемый доход от этих процессов [1].Для математической постановки этой задачи требуется принять следующие основные предположения [1]:1) эффективности каждого из рассматриваемых технологических процессов, например в виде соответствующих доходов, могут быть измерены общей единицей: либо в виде валового выпуска однородного продукта, либо в стоимостной форме;2) эффективность каждого технологического процесса не зависит от того, какие количества ресурсов были выделены для других технологических процессов;3) общая эффективность или, что то же самое, суммарный доход от всех технологических процессов - аддитивная величина, то есть величина, равная сумме доходов, получаемых от каждого процесса в отдельности.Тогда математическая постановка
задачи оптимального распределения ограниченного ресурса формулируется следующим образом [1].Предположим, что имеется
N технологических процессов, занумерованных в определенном порядке числами 1, 2, ... ,
N , и каждому такому процессу поставлена в соответствие некоторая функция, оценивающая его эффективность, а именно: величина дохода в зависимости от количества выделенного ресурса для этого процесса. Пусть
xi - количество выделенного ресурса
i-му процессу (
i = 1, 2, ... ,
N ), а величина дохода, получаемого в этом процессе, задается функцией
gi =
gi (
xi ) . Отметим, что в качестве таких функций можно выбирать, например, производственные функции или функции полезности неоклассического типа [2, 3].С учетом второго и третьего предположения - о независимости процессов и аддитивности их общей эффективности - для суммарного дохода от распределения ограниченного ресурса между указанными
N технологическими процессами получим следующее выражение:
В силу ограниченности распределяемого ресурса, располагаемое количество которого здесь обозначим через
z, для переменных задачи
xi ,
i = 1, 2, ... ,
N , имеет место следующее ограничение:
которое вместе с условиям неотрицательности для этих же переменных
задает
допустимую область определения для функции (1.1). Таким образом, задача оптимального распределения ограниченного ресурса заключается в том, чтобы определить значения переменных
xi ,
i = 1, 2, ... ,
N , которые доставляют максимальное значение функции
R(
x1,
x2 , ... ,
xN ) (1.1), удовлетворяя при этом ограничениям (1.2), (1.3). Задача (1.1) - (1.3) относится к классу задач условной оптимизации. Ограничения, задающие в этих задачах допустимые множества, обычно в математической экономике разделяют на две группы, а именно: ограничения вида (1.2) относят к
функциональным ограничениям, а ограничения вида (1.3) - к
прямым ограничениям [2]. Значения
xi ,
i = 1, 2, ... ,
N , для которых доставляется максимальное значение функции (1.1) с учетом (1.2), (1.3), называют
решением задачи, а соответствующие значения функции (1.1), то есть
max R(
x1,
x2 , ... ,
xN ) , -
значением задачи. Если ограничения задачи, заданные в виде нестрогих неравенств, для ее решения обращаются в равенства, то такие ограничения тогда называют
эффективными; иначе эти ограничения являются
неэффективными, и в связи с этим их можно в процессе решения задачи отбрасывать.
Исходные параметры 1. z - располагаемое количество ресурса,
2. n - мера квантования z
3.
4.
5.
Искомые параметры1. fN (z) = fN (nД ) - искомый максимум функции R2. xN (z) - искомое оптимальное количество ресурсаМЕТОД РЕШЕНИЯПереходя к изложению вычислительной схемы решения задачи с применением основного функционального уравнения (1.15), предположим (а это существенно для дальнейшего изложения), что переменные задачи
N i xi , ... 2, 1, , = , а также количества распределяемого ресурса
как в (1.10), так и в (1.15) могут принимать только дискретные значения с некоторым выбранным шагом ѓў >0. То есть имеет место:где
nѓў =
z . Соответственно, функции (1.10) в рекуррентном соотношении (1.15) будут вычисляться только для указанных в (1.16) значений
или, что то же самое, только для таких точек:
Указанный подход позволяет избежать процедуры интерполирования при вычислении значений , исходя из вычисленных значений
fm?1(
y) в точках
y = 0, ѓў , 2ѓў , ... ,
z . Действительно, для вычисления под знаком максимума в (1.15) значения ? интерполирования не требуется, так как здесь с учетом (1.16) и (1.17) имеет место:
.Согласно (1.15), для вычисления вначале следует найти значения для всех значений
из (1.16) с помощью соотношений (1.12)или (1.13), которые доставляют множество всех требуемых значений. Затем для всех
(1.16) с учетом (1.15) вычисляются значения:где.Процедура максимизации (1.18) заключается в том, чтобы вначале для каждого
z ~ последовательно вычислить значения: а затем выбрать из них максимальное, то есть искомое значение ; при этом определяется и соответствующее ему оптимальное значение .Получив множество значений для , можно приступить к вычислению функции исходя из (1.15) при
m =3:
и т.д. для остальных
m = 4, 5, ... ,
N .Таким образом, в процессе решения уравнения (1.15) для
m = 2, 3, ... ,
Nпоследовательно заполняется таблица, подобная табл. 1.1.Таблица 1.1Оптимальные доходы в зависимости от количества процессови выделенного ресурса
С заполнением последних двух столбцов указанной таблицы решениезадачи фактически получено. Действительно, поскольку функция
по построению монотонно неубывающая по
, постольку
fN (
z) =
fN (
nѓў ) - искомый максимум функции
R (1.1), а
xN (
z) - искомое оптимальное количество ресурса, выделенное для
N-го процесса. Стало быть, оставшееся количество ресурса, равное
z ?
xN (
z) , должно быть распределено оптимальным образом между остальными процессами. Соответствующее решение, то есть оптимальный доход (1.10) для первых
N ?1 процессов, находится в столбце с заголовком
? , а именно: в строке, отвечающей значению . В этой же строке в столбце с заголовком ? находится величина оптимального количества ресурса, который выделяется для (
N ?1)-го процесса. Таким образом, перемещаясь по столбцам табл. 1.1 справа налево (это т.н. обратный ход [1, 3]), можно последовательно определить все значения
, которые доставляют абсолютный максимум функции
R(
x1,
x2 , ... ,
xN ) (1.1) в области (1.2), (1.3) для заданного количества распределяемого ресурса -
z, конечно же, с учетом дополнительных ограничений (1.16), (1.17)
ОБОСНОВАНИЕ ВЫБОРА ПРОГРАММНЫХ СРЕДСТВКурсовая работа выполнена с помощью программы Microsoft Office Excel, одной из наиболее передовых, мощных и современных сред разработки Windows-приложений и электронных таблиц. Встроенное средство поиска решений позволяет быстро справиться с задачей о распределения ресурсов.
ОПИСАНИЕ ИНТЕРФЕЙСА ПОЛЬЗОВАТЕЛЯДля начала работы с программой следует задать n и z и нажать кнопку определитьПосле этого программа создаст таблицы.
СПИСОК ЛИТЕРАТУРЫ1. Беллман, Р. Прикладные задачи динамического программирования /Р. Беллман, С. Дрейфус. - М.: Наука, 1965. - 460 с.2. Ланкастер, К. Математическая экономика / К. Ланкастер. - М.: Советское радио, 1972. - 464 с.3. Колемаев, В.А. Математическая экономика / В.А. Колемаев. - М.:ЮНИТИ, 1998. - 240 с.4. Беллман, Р. Процессы регулирования с адаптацией / Р. Беллман. - М.: Наука, 1964. - 360 с.5. Первозванский, А.А. Математические модели в управлении производством / А.А. Первозванский. - М.: Наука, 1975. - 616 с.6. Калихман, И.Л. Динамическое программирование в примерах и задачах / И. Л. Калихман, М. А. Войтенко. - М.: Высшая школа, 1979. - 125 с.ТЕКСТ ПРОГРАММЫPublic Function f_g1(x As Double) As Doublef_g1 = 2.5 * Sqr(x) / (Sqr(x) + 1)End FunctionPublic Function f_g2(x As Double) As Doublef_g2 = 6 * x * (1 - Exp(-x / 4)) / (x + 4)End FunctionPublic Function f_g3(x As Double) As Doublef_g3 = 2 * x / (x + 0.5)End FunctionPrivate Sub CommandButton1_Click()Dim i As IntegerDim n As IntegerDim z As DoubleDim d As DoubleDim m_str As String Range("A1").Select n = Val(TextBox1.Text) z = Val(TextBox2.Text) d = z / n ActiveCell.Cells(1, 2) = n ActiveCell.Cells(2, 2) = z Range("A11").Select For i = 1 To 100 For j = 1 To 10 ActiveCell.Cells(i, j) = "" Next Next For i = 1 To 10 ActiveCell.Cells(0, i) = 0 Next For i = 1 To n ActiveCell.Cells(i, 1) = i * d ActiveCell.Cells(i, 2) = f_g1(i + 0#) ActiveCell.Cells(i, 3) = f_g2(i + 0#) ActiveCell.Cells(i, 4) = f_g3(i + 0#) ActiveCell.Cells(i, 5) = f_g1(i + 0#) Next For i = 1 To n ActiveCell.Cells(i + 0, 7) = GetF2Val(i + 0, d) ActiveCell.Cells(i + 0, 8) = Int(GetF2Pos(i + 0, d) * d) ActiveCell.Cells(i + 0, 9) = GetF3Val(i + 0, d) ActiveCell.Cells(i + 0, 10) = Int(GetF3Pos(i + 0, d) * d) ActiveCell.Cells(i + 0, 6) = Abs(z - ActiveCell.Cells(i + 0, 8) - ActiveCell.Cells(i + 0, 10)) Next ListBox1.Clear For i = 1 To 3 m_str = Str(i) + ": X = " + Str(ActiveCell.Cells(n + 0, 4 + i * 2)) + " F = " + Str(ActiveCell.Cells(n + 0, 3 + i * 2)) ListBox1.AddItem (m_str) Next Range("A10:J10").SelectEnd SubPrivate Sub CommandButton2_Click()HideEnd SubPublic Function GetF2Val(n As Integer, d As Double) As Double Dim maxs As Double maxs = f_g2(0) + f_g1(n * d) For i = 1 To n If f_g2(i * d) + f_g1((n - i) * d) >= maxs Then maxs = f_g2(i * d) + f_g1((n - i) * d) End If Next GetF2Val = maxsEnd FunctionPublic Function GetF2Pos(n As Integer, d As Double) As Integer Dim maxs As Double Dim maxp As Integer Range("A11").Select maxs = f_g2(0) + f_g1(n * d) max_p = 0 For i = 1 To n If f_g2(i * d) + f_g1((n - i) * d) >= maxs Then maxs = f_g2(i * d) + f_g1((n - i) * d) maxp = i End If Next GetF2Pos = maxpEnd FunctionPublic Function GetF3Val(n As Integer, d As Double) As Double Dim maxs As Double maxs = f_g3(0) + f_g2(n * d) For i = 1 To n If f_g3(i * d) + f_g2((n - i) * d) >= maxs Then maxs = f_g3(i * d) + f_g2((n - i) * d) End If Next GetF3Val = maxsEnd FunctionPublic Function GetF3Pos(n As Integer, d As Double) As Integer Dim maxs As Double Dim maxp As Integer Range("A11").Select maxs = f_g3(0) + f_g2(n * d) max_p = 0 For i = 1 To n If f_g3(i * d) + f_g2((n - i) * d) >= maxs Then maxs = f_g3(i * d) + f_g2((n - i) * d) maxp = i End If Next GetF3Pos = maxpEnd Function