Принцип оптимальности Беллмана

1.1 Принцип оптимальности Беллмана

Метод динамического программирования позволяет одну задачу со многими переменными заменить рядом последовательно решаемых задач с меньшим числом переменных. Процесс решения задачи разбивается на шаги. При этом нумерация шагов, как правило, осуществляется от конца к началу.

Основным принципом, на котором базируются оптимизация многошагового процесса, а также особенности вычислительного метода, динамического программирования, является принцип оптимальности Р. Беллмана.

Оптимальное поведение обладает тем свойством, что каковы бы ни были начальное состояние и начальное решение, последующие решения должны быть оптимальными относительно состояния, полученного в результате первоначального решения.

Принцип оптимальности имеет конструктивный характер и непосредственно указывает процедуру нахождения оптимального решения. Математически он записывается выражением вида:

 (1.3)

где  — оптимальное значение эффекта, достигаемого за  шагов; n — количество шагов (этапов);  — состояние системы на - м шаге; — решение (управление), выбранное на - м шаге;  — непосредственный эффект, достигаемый на - м шаге.

"Optimum" в выражении (1.3) означает максимум или минимум в зависимости от условия задачи. Все вычисления, дающие возможность найти оптимальное значение эффекта, достигаемого за n шагов, ¦n(So), проводятся по формуле (1.3), которая носит название основного функционального уравнения Беллмана или рекуррентного соотношения. Действительно, при вычислении очередного значения функции  используются значение функции , полученное на предыдущем шаге, и непосредственное значение эффекта , достигаемого в результате выбора решения  при заданном состоянии системы . Процесс вычисления значений функции   осуществляется при естественном начальном условии , которое означает, что за пределами конечного состояния системы эффект равен нулю.[1, с 243]

1.2 Вычислительная схема

Оптимальное решение задачи методом динамического программирования находится на основе функционального уравнения (1.3). Чтобы определить его, необходимо:

1)         Записать функциональное уравнение для последнего состояния процесса (ему соответствует ):

; (1.4)

2)         Найти  из дискретного набора его значений при некоторых фиксированных  и  из соответствующих допустимых областей ( так как , то ). В результате после первого шага известно решение  и соответствующее значение функции ;

3)         Уменьшить значение  на единицу и записать соответствующее функциональное уравнение. При оно имеет вид:

; (1.5)

4)         Найти условно-оптимальное решение на основе выражения (1.5);

5)         Проверить, чему равно значение . Если  расчет условно-оптимальных решений закончен, при этом найдено оптимальное решение задачи для первого состояния процесса. Если перейти к выполнению п. 3;

6)         Вычислить оптимальное решение задачи для каждого последующего шага процесса, двигаясь от конца расчетов к началу.[1, с 244]

2. Решение задачи оптимального распределения средств на расширение производства 2.1 Решение задачи оптимального распределения средств на расширение производства ручным способом

Широкий класс составляют задачи, в которых речь идет о наиболее целесообразном распределении во времени тех или иных ресурсов (денежных средств, рабочей силы, сырья и т.п.). Рассмотрим пример задачи такого рода.

Производственному объединению из четырех предприятий выделяется банковский кредит в сумме 60 млн. ден. ед. для реконструкции и модернизации производства с целью увеличения выпуска продукции. Значения  дополнительного дохода, получаемого на предприятиях объединения в зависимости от выделенной суммы xi, приведены в табл. 2.1. Распределить выделенный кредит между предприятиями так, чтобы дополнительный доход объединения был максимальным.[1, с 261]

Таблица 2.1 – Значения дополнительного дохода

Выделенные средства xi, млн. ден. ед.	Предприятие
	Получаемый доход, млн. ден. ед.
0 20 40 60	0 9 18 24	0 11 19 30	0 16 32 40	0 13 27 44

Решение. Пусть n=1. В соответствии с вычислительной схемой динамического программирования рассмотрим сначала случай n=1, т.е. предположим, что все имеющиеся средства выделяются на реконструкцию и модернизацию одного предприятия. Обозначим через ¦1(x) максимально возможный дополнительный доход на этом предприятии, соответствующий выделенной сумме x. Каждому значению x отвечает вполне определенное (единственное) значение  дополнительного дохода, поэтому можно записать, что:

 (2.1)

В соответствии с формулой (2.1) в зависимости от начальной суммы с поучаем с учетом табл. 2.1 значения ¦1(с), помещенные в табл. 2.2.

Таблица 2.2 – Значения максимально возможного дополнительного дохода в зависимости от выделенных средств

0	0
20	9
40	18
60	24

Пусть теперь n=2, т.е. средства распределяются между двумя предприятиями. Если второму предприятию выделена сумма x, то дополнительный доход на нем составит g2(x). Оставшиеся другому предприятию средства (c-x) в зависимости от величины x (а значит, и c-x) позволят увеличить дополнительный доход до максимально возможного значения ¦1(c-x). При этом условии общий дополнительный доход на двух предприятиях:

 (2.2)

Оптимальному значению ¦2(с) дополнительного дохода при распределении суммы с между двумя предприятиями соответствует такое x, при котором сумма (2.2) максимальна.

Это можно выразить записью:

 (2.3)

Значение можно вычислить, если известны значения , и т.д.

Функциональное уравнение Беллмана для рассматриваемой задачи запишется в следующем виде:

 (2.4)

Очередная задача – найти значения функции (2.3) для всех допустимых комбинаций с и x. Для упрощения расчетов значения x будем принимать кратными 20 тыс. ден. ед. и для большей наглядности записи оформлять в виде таблиц. Каждому шагу будет соответствовать своя таблица. Рассматриваемому шагу соответствует табл. 2.3.

Таблица 2.3 – Значения функции на втором шаге

с\x	0	20	40	60
20	0+9	11+0			11	20
40	0+18	11+9	19+0		20	20
60	0+24	11+18	19+9	30+0	30	60

Для каждого значения (20,40,60) начальной суммы с распределяемых средств в табл. 2.2 предусмотрена отдельная строка, а для каждого возможного значения x (0,20,40,60) распределяемой суммы – столбец. Некоторые клетки таблицы останутся незаполненными, так как соответствуют недопустимым сочетаниям с и x.

В каждую клетку таблицы будем вписывать значение суммы (2.2). Первое слагаемое берем из условий задачи (см.табл.2.1), второе – из табл.2.2.

В двух последних столбцах таблицы проставлены максимальный по строке дополнительный доход (в столбце ) и соответствующая ему оптимальная сумма средств, выделенная второму предприятию (в столбце ).

Расчет значений  приведен в табл. 2.4. Здесь использована формула, получающаяся из (2.4) при n=3:

Первое слагаемое в табл. 2.4 взято из табл. 2.1, второе из табл. 2.3.

Таблица 2.4 – Значения функции на третьем шаге

с\x	0	20	40	60
20	0+11	16+0			16	20
40	0+20	16+11	32+0		32	40
60	0+30	16+20	32+11	40+0	43	40

Расчёт значений  приведен в табл. 2.5. Здесь использована формула, получающаяся из (2.4) при n=4:

Первое слагаемое в табл.2.5 взято из табл.2.1, второе из табл. 2.4.

Таблица 2.5 – Значения функции на четвертом шаге

с\x	0	20	40	60
20	0+16	13+0			16	0
40	0+32	13+16	27+0		32	0
60	0+43	13+32	27+16	44+0	45	20

Составим сводную таблицу, на основе расчетов таблиц, начиная с 2.2.

Таблица 2.6 – Сводная таблица

20	9	11	20	16	20	16	0
40	18	20	20	32	40	32	0
60	24	30	60	43	40	45	20

Из табл. 2.6 видно, что наибольший дополнительный доход, который могут дать четыре предприятия при распределении 60 млн. ден. ед. (с=60), составляет 45 млн. ден. ед. (). При этом четвертому предприятию должно быть выделено 20 млн. ден. ед. (), а остальным трем – 60-20=40 млн. ден. ед. Из этой же таблицы видно, что оптимальное распределение оставшихся 40 млн. ден. ед. (с=40) между тремя предприятиями обеспечит общий дополнительный доход на них на сумму 32 млн. ден. ед. () при условии, что третьему предприятию будет выделено 40 млн. ден. ед. (), а на долю второго и третьего средств не останется (40-40=0).

Ответ: максимальный дополнительный доход на четырех предприятиях при распределении между ними 60 млн. ден. ед. составляет 45 млн. ден. ед. и будет получен, если первому и второму предприятию средств не выделять, третьему 40 млн. ден. ед., а четвертому 20 млн. ден. ед.

  2.2 Решение задачи оптимального распределения средств на расширение производства в среде Microsoft Exсel

Microsoft Excel, является мощнейшим средством для работы с данными. Таблицы и работа с ними есть главная задача программы. Главными достоинствами программы Excel являются:

-           Простое и удобное создание таблиц

-           Упрощенный ввод данных и заполнение таблиц

-           Умение программы автоматически угадывать содержание ячеек на основании анализа соседних и предыдущих. Это дает возможность автоматически заполнять целые области таблицы, выполнив всего несколько щелчков мышкой.

-           Возможность отображения текста и чисел не только в простом текстовом виде, но и с использованием цветов, шрифтов, цветного фона и т.д.

-           Удобные и понятные функции создания диаграмм на основе значений ячеек таблицы

-           Создание сложных форм и других элементов, позволяющих автоматизировать и ускорить выполнение постоянно повторяющихся действий пользователя

-           Расширенные возможности сортировки таблиц

-           Выполнение арифметических расчетов и работа с формулами

-           Автоматическая проверка ошибок в формулах, данных и тексте

-           Возможность добавления в таблицы рисунков и графики

-           Возможность использования в таблицах ссылок на страницы Интернета

-           Возможность совместной работы над документами

-           Сохранение таблиц в виде страниц Интернета

Решение задачи оптимального распределения средств на расширение производства в среде Microsoft Excel, представлено в приложении.

В процессе решения задачи в среде Microsoft Excel были использованы следующие функции:

-           МАКС(число1;число2;…) – возвращает наибольшее значение из списка аргументов. Логические и текстовые значения игнорируются.

-           ЕСЛИ(лог_выражение;значение_если_истина;значение_если_ложь) – проверяет, выполняется ли условие, и возвращает одно значение, если оно выполняется, и другое значение, если нет.

Для защиты данных от изменения другими пользователями была использована функция редактора защита листа, кроме ячеек для ввода исходных данных.

Результаты решения задачи, полученные в Microsoft Excel идентичны результатам, полученным в предыдущем подразделе.

Заключение

В данной курсовой работе мы ознакомились с применением принципа оптимальности Беллмана в задачах на оптимальное распределение средств на расширение производства.

В первой части курсовой работы мы рассмотрели основные понятия динамического программирования, теоретические основы принципа оптимальности Беллмана, определили рекуррентную природу данного принципа, а также рассмотрели вычислительную схему Беллмана.

Основным принципом, на котором базируются оптимизация многошагового процесса, а также особенности вычислительного метода, динамического программирования, является принцип оптимальности Р. Беллмана.

Вычисления в динамическом программировании выполняются рекуррентно в том смысле, что оптимальное решение одной подзадачи используется в качестве исходных данных для следующей. Решив последнюю подзадачу, мы получим оптимальное решение исходной задачи. Способ выполнения рекуррентных вычислений зависит от того, как производится декомпозиция исходной задачи. В частности, подзадачи обычно связаны между собой некоторыми общими ограничениями. Если осуществляется переход от одной подзадачи к другой, то должны учитываться эти ограничения.

Во второй части была решена задача оптимального распределения средств на расширение производства, а также решена задача оптимального распределения средств на расширение производства в среде Microsoft Excel. Максимальный дополнительный доход на четырех предприятиях при распределении между ними 60 млн. ден. ед. составил 45 млн. ден. ед. и был получен, при условии что первому и второму предприятию средств не выделили, третьему 40 млн. ден. ед., а четвертому 20 млн. ден. ед.

Список использованных источников

1.         Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию. – 2-е изд., перераб. и доп. – Мн.: Выш. Шк., 2001.-448 с.

2.         Таха Х.А. Введение в исследование операций, 7-е издание.: Пер. с англ. – М., 2005.-912 с.

3.         Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. – М.,1965.-458 с.