Распределение ресурсов по трем отраслям
Предположим, что имеется N технологических процессов, занумерованных в определенном порядке числами 1, 2, …, N, и каждому такому процессу поставлена в соответствие некоторая функция, оценивающая его эффективность, а именно: величина дохода в зависимости от количества выделенного ресурса для этого процесса. Пусть xi — количество выделенного ресурса i-му процессу (i = 1, 2, …, N), а величина… Читать ещё >
Распределение ресурсов по трем отраслям (реферат, курсовая, диплом, контрольная)
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
" САРОВСКИЙ ГОСУДАРСТВЕННЫЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ"
ЭКОНОМИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
К КУРСОВОЙ РАБОТЕ
На тему:
СТУДЕНТ (группа ИС-45Д)
РУКОВОДИТЕЛЬБеляев С.П.
г. Саров 2008 г
- ВВЕДЕНИЕ 3
- ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 4
- Исходные параметры 5
- Искомые параметры 6
- МЕТОД РЕШЕНИЯ 6
- ОБОСНОВАНИЕ ВЫБОРА ПРОГРАММНЫХ СРЕДСТВ 9
- ОПИСАНИЕ ИНТЕРФЕЙСА ПОЛЬЗОВАТЕЛЯ 10
- СПИСОК ЛИТЕРАТУРЫ 11
Основная часть данной работы направлена на практическое освоение метода динамического программирования на примере решения хорошо изученных задач, а именно: простейшей задачи оптимального распределения ресурсов и задачи управления запасами продукта при случайном спросе на него.
Кроме теоретических основ и практических рекомендаций, необходимых для численного решения указанных задач, связанных с простым классом одномерных процессов распределения [1], дополнительно рассматриваются задачи оптимального распределения при наличии двух типов ресурсов и двух типов ограничений, в рамках которых возможны не только постановка и решение большого числа прикладных задач [1, 5], но также выявление существенных и качественных особенностей, связанных с применением метода динамического программирования, при переходе к задачам с многомерными процессами распределения.
Цель работы: знакомство с постановкой задачи оптимального распределения ограниченного ресурса и методом множителей Лагранжа в задачах условной оптимизации, изучение принципа оптимальности Беллмана и вычислительной схемы решения задачи оптимального распределения ограниченного ресурса методом динамического программирования, разработка программы для численного решения задачи и проведение расчетов.
ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
Постановка простейшей задачи оптимального распределения
ограниченного ресурса
В различных производственно-экономических системах значительное число решаемых задач тесно связано с эффективным использованием и распределением ограниченных ресурсов, необходимых для нормального функционирования таких систем. Переходя к формулировке одной из простейшей задач такого класса, вначале опишем кратко процессы, обусловливающие возникновение этого типа задач.
Пусть некоторая производственно-экономическая система располагает заданным количеством какого-либо экономического ресурса, под которым подразумеваются материальные, трудовые, финансовые либо иные ресурсы, необходимые для функционирования системы. В случае нескольких потребителей указанного ресурса или далее соответствующих технологических процессов возникает следующая задача: разделить имеющееся количество ресурса между ними так, чтобы максимизировать их суммарную эффективность или получаемый доход от этих процессов.
Для математической постановки этой задачи требуется принять следующие основные предположения [1]:
1) эффективности каждого из рассматриваемых технологических процессов, например в виде соответствующих доходов, могут быть измерены общей единицей: либо в виде валового выпуска однородного продукта, либо в стоимостной форме;
2) эффективность каждого технологического процесса не зависит от
того, какие количества ресурсов были выделены для других технологических процессов;
3) общая эффективность или, что-то же самое, суммарный доход от всех технологических процессов — аддитивная величина, то есть величина, равная сумме доходов, получаемых от каждого процесса в отдельности.
Тогда математическая постановка задачи оптимального распределения ограниченного ресурса формулируется следующим образом.
Предположим, что имеется 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) — к прямым ограничениям. Значения 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Д ) — искомый максимум функции R
2. 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 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