ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«САРОВСКИЙ ГОСУДАРСТВЕННЫЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ»
ЭКОНОМИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
К КУРСОВОЙ РАБОТЕ
На тему:
СТУДЕНТ (группа ИС-45Д)
РУКОВОДИТЕЛЬБеляев С.П.
г. Саров 2008 г
Оглавление
ВВЕДЕНИЕ
ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
Исходные параметры
Искомые параметры
МЕТОД РЕШЕНИЯ
ОБОСНОВАНИЕ ВЫБОРА ПРОГРАММНЫХ СРЕДСТВ
ОПИСАНИЕ ИНТЕРФЕЙСА ПОЛЬЗОВАТЕЛЯ
СПИСОК ЛИТЕРАТУРЫ
ВВЕДЕНИЕ
Основная часть данной работы направлена на практическое освоение метода динамического программирования на примере решения хорошо изученных задач, а именно: простейшей задачи оптимального распределенияресурсов и задачи управления запасами продукта при случайном спросе на него.
Кроме теоретических основ и практических рекомендаций, необходимых для численного решения указанных задач, связанных с простым классом одномерных процессов распределения [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 ), – значением задачи. Если ограничения задачи, заданные в виде нестрогих неравенств, для ее решения обращаются в равенства, то такие ограничения тогда называют эффективными; иначе эти ограничения являются неэффективными, и в связи с этим их можно в процессе решения задачи отбрасывать.–PAGE_BREAK–
Исходные параметры
z– располагаемое количество ресурса,
n –мера квантования z
/>
/>
/>
Искомые параметры
fN(z) = fN(nΔ ) — искомый максимум функции R
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) продолжение
–PAGE_BREAK–
ОБОСНОВАНИЕ ВЫБОРА ПРОГРАММНЫХ СРЕДСТВ
Курсовая работа выполнена с помощью программы 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 Double
f_g1 = 2.5 * Sqr(x) / (Sqr(x) + 1)
End Function
Public Function f_g2(x As Double) As Double
f_g2 = 6 * x * (1 — Exp(-x / 4)) / (x + 4)
End Function
Public Function f_g3(x As Double) As Double
f_g3 = 2 * x / (x + 0.5)
End Function
Private Sub CommandButton1_Click()
Dim i As Integer
Dim n As Integer
Dim z As Double
Dim d As Double
Dim 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»).Select
End Sub
Private Sub CommandButton2_Click()
Hide
End Sub
Public 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 = maxs
End Function
Public 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 = maxp
End Function
Public 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 = maxs
End Function
Public 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 = maxp
End Function