Тема: Решение задач динамического программирования

Средствами ЭТ Excel

Цель:

1. Ознакомиться с основными понятиями динамического программирования

2. Освоить порядок решения задачи

3. Научиться оценивать полученные результаты

1 Теоретические сведения

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

Рассматривается управляемый процесс, например экономический процесс распределения средств между предприятиями в течение ряда лет. В результате управления система (объект управления) S переводится из начального состояния s₀ в состояние ŝ. Обозначим через s_k состояние системы после k-го шага управления. Получаем последовательность состояний s₀, s₁, …, s_k-1, …, s_n-1, s_n=ŝ, которая изображена на рисунке 8.1

Рисунок 8.1

Формулировка задачи динамического программирования:

Определить такое допустимое управление X, переводящее систему S из состояния s₀ в состояние ŝ, при котором целевая функция принимает наибольшее (наименьшее) значение.

Особенности модели динамического программирования:

1. Задача оптимизации интерпретируется как n – шаговый процесс управления.

2. Целевая функция равна сумме целевых функций каждого шага.

3. Выбор управления на k-м шаге зависит только от состояния системы к этому шагу , не влияет на предшествующие шаги (нет обратной связи).

4. Состояние s_k после k-го шага управления зависит только от предшествующего состояния s_k-1 и управления X_k (отсутствие последействия).

5. На каждом шаге управление X_k зависит от конечного числа управляющих переменных, а состояние s_k – от конечного числа параметров.

ПРИМЕР выполнения лабораторной работы

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

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

Таблица 8.1 – Ожидаемая прибыль в зависимости от капиталовложений

Филиалы	Млн. тг
		0,28	0,45	0,65	0,78	0,9
		0,25	0,41	0,55	0,65	0,75
		0,15	0,25	0,4	0,5	0,62
		0,2	0,33	0,742	0,48	0,53

Математическая модель:

- R(i,j) – прибыль, получаемая от вложения i млн. тг в j – й филиал, где i Î [0,5], j Î [1,4]

- F(A,1,2) – оптимальное распределение средств, когда А млн. тг вкладываются в 1 и 2-й филиалы вместе.

F(A,1,2)= max {R(A-i,1)+R(i,2): i Î[0,A]} (8.1)

- F(A,1,2,3) – оптимальное распределение средств, когда А млн. тг вкладываются в 1, 2 и 3-й филиалы вместе.

F(A,1,2,3)= max {F(A-i,1,2)+R(i,3): i Î[0,A]} (8.2)

- F(A,1,2,3,4) – оптимальное распределение средств, когда А млн. тг вкладываются в 1, 2, 3 и 4-й филиалы вместе.

F(A,1,2,3,4)= max {F(A-i,1,2,3)+R(i,4): i Î[0,A]} (8.3)

Значения i, при которых достигается максимум, определяют оптимальные капиталовложения в филиалы.

Порядок решения задачи

1. Откройте рабочую книгу Excel «Задача динамического программирования» или самостоятельно создайте рабочую книгу, содержащую исходные формы для решения задачи и модуль VBA ( текст программы).

2. Перейдите на лист «Решение задачи»

3. В ячейки B2, D3, B6:G13 (в рабочей книге – выделены голубым цветом) введите исходные данные:

- В2 – количество филиалов

- D3 – размер капиталовложений

- B6:E11 – ожидаемую прибыль

4. Нажмите кнопку “Вычислить”, расположенную на рабочем листе

Результат решения задачи приведен на рисунке 8.2.

В диапазон ячеек H6:J11 программа выводит значения F(A,1,2), F(A,1,2,3) и F(A,1,2,3,4). В диапазоне ячеек B17:G22 программа выводит оптимальное распределение капиталовложений по филиалам.

Вывод: Из рисунка 8.2 видно, что максимальная ожидаемая прибыль равна 1,1 млн. тг, а оптимальные капиталовложения состоят в выделении 1 –му филиалу 3 млн. тг, 2-му филиалу – 1 млн. тг и 4-му филиалу – 1 млн. тг.

Рисунок 8.2

ЗАДАНИЕ

- Решить задачу динамического программирования по приведенным исходным данным (приложение 8.1)

· Откройте рабочую книгу Excel «Задача динамического программирования»

· Перейдите на лист «Исходные данные»

· Скопируйте интервал таблицы Вариант 1, выделенный голубым цветом

· Перейдите на лист «Решение задачи»

· Вставьте в ячейку В6 скопированный интервал

· Введете в ячейку В2 количество филиалов для данного варианта

· Введите в ячейку D3 размер капиталовложений для данного варианта

· Нажмите кнопку “Вычислить”, расположенную на рабочем листе

· По результатам решения задачи сделайте выводы.

· Очистите содержимое ячеек B6:L13, B17:K24

· Решите задачу для других вариантов исходных данных, приведенных на листе «Исходные данные»

- Составить и решить задачу динамического программирования

Требования к отчету по лабораторной работе

Отчет должен содержать:

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

2. Результаты решения задач.

3. Выводы по решению задачи.

Приложение 8.1

Варианты задания

Приложение 8.2

Форма для решения задачи о размещении капитала.

Приложение 8.3

Текст программы для решения задачи о размещения капитала.

Программа написана на языке программирования VBA.

Option Explicit

Option Base 1

Sub DinProgr()

NN = Cells(2, 2)

AA = Cells(3, 4)

Dim aa,nn,nn1,kk1, i, j, k, n, p, l, t As Integer

Dim m, R(), A() As Double

ReDim R(k + 1, NN), A(k + 1)

For i = 1 To k + 1

For j = 2 To NN + 1

R(i, j - 1) = Cells(i + 5, j).Value

Next j

Next i

t = 2

For p = 2 To NN

If p = 2 Then

For j = 1 To k + 1

A(j) = Cells(j + 5, 2).Value

Next j

End If

If p > 2 Then

For j = 1 To k + 1

A(j) = Cells(j + 5, p + nn1 - 1).Value 'nn-1

Next j

End If

Продолжение приложения 8.3

For n = 1 To k + 1

m = -1

For j = 1 To n

If m < A(j) + R(n + 1 - j, p) Then

m = A(j) + R(n + 1 - j, p)

End If

Next j

Cells(n + 5, nn1 + p).Value = m

l = t

For j = 1 To n

If m = A(j) + R(n + 1 - j, p) Then

Cells(n + nn1 + 3 + kk1, l).Value = j - 1

Cells(n + nn1 + 3 + kk1, l + 1).Value = n - j

l = l + 2

End If

Next j

Next n

t = t + 2

Next p

End Sub

СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ

Основная:

1. Клименко И.С. Экономико-математическое моделирование. Курс лекций.//РИИ.-2002.-188с.

2. Вентцель Е.С. Исследование операций. – М: Р и С, 1984.- 208с.

3. Кофман А. Методы и модели исследование операций. - М.: Мир,1997.-209с.

4. Кудрявцев Е.М. Исследование операций в задачах, алгоритмах и программах.- М.:РиС,1984.- 184с.

5. Курицкий Б.Я. Поиск оптимальных решений средствами Excel 7.0. – СПб.:BHV – Санкт-Петербург, 1997.

Дополнительная:

1. Муртаф Б. Современное линейное программирование. - М.:Мир,1984.-224с.

2. Воробьев Н.Н. Теория игр для экономистов - кибернетиков. - М.: Наука, 1985.-272с.

3. Мулен Э. Теория игр с примерами из математической экономики. Пер. с франц.-М.:Мир,1985.- 200с.

6. Кофман А., Дебазей Г. Сетевые методы планирования и их применение. – М.: Прогресс, 1968.-182с.

7. Бурков В.Н. и др. Сетевые модели и задачи управления. - М. :Сов. Радио, 1967.- 144с.

8. Резниченко С.С. Математическое моделирование в горной промышленности. - М.: Недра,1981.-216с.

9. Крупенченко Р.Л. АСУ в строительстве. - Л.:Стройиздат,1979. – 207с.

10. Николь Н., Альбрехт Р. EXCEL 5.0 для профессионалов. - М.: Эком,1996.-304с.

11. Экономико-математические методы и прикладные модели //Под ред. Федосеева В.В., М. : Наука, 1999.- 391с.