Xreferat.com » Рефераты по информатике и программированию » Оптимальное распределение средств на расширение производства

Оптимальное распределение средств на расширение производства

Курсовая работа

Оптимальное распределение средств на расширение производства

Содержание


Введение

1. Рекуррентная природа задач динамического программирования

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

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

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

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

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

Заключение

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


Введение


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

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

Предложенный Р.Беллманом аппарат функциональных уравнений значительно расширяет возможности решения реальных проблем оптимизации. Его главным достоинством является хорошая "приспособленность" к использованию современной вычислительной техники.

Цель курсовой работы: решить задачу оптимального распределения средств на расширение производства.

Задачи: определить рекуррентную природу задач динамического программирования, изучить принцип Беллмана, его вычислительную схему, решить задачу в среде Microsoft Excel.

Курсовая работа состоит из 2-ух частей. В первом разделе рассмотрены теоретические основы задач динамического программирования. Во втором разделе приведен пример решения задачи оптимального распределения средств на расширение производства.


1 .Рекуррентная природа задач динамического программирования


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

Пусть на некоторый период времени Т, состоящий из m лет, планируется деятельность группы промышленных предприятий. В начале планируемого периода на развитие предприятий выделяются основные средства Qо, которые необходимо распределить между предприятиями. В процессе функционирования предприятий, выделенные им, средства частично расходуются. Однако каждое из этих предприятий за определенный период времени (хозяйственный год) получает прибыль, зависящую от объема вложенных средств. В начале каждого года имеющиеся средства могут перераспределяться между предприятиями. Требуется определить, сколько средств надо выделить каждому предприятию в начале каждого года, чтобы суммарный доход от всей группы предприятий за весь период времени Т был максимальным.

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

Пусть имеется груз, состоящий из неделимых предметов различных типов, который нужно погрузить в самолет грузоподъемностью Р. Стоимость и масса каждого предмета j-гo типа известны и составляют соответственно cj, и pj единиц (Оптимальное распределение средств на расширение производства). Требуется определить, сколько предметов каждого типа надо загрузить в самолет, чтобы суммарная стоимость груза была наибольшей, а масса не превышала грузоподъемности самолета.

Математически задача записывается следующим образом: найти такие целые неотрицательные значения хj (Оптимальное распределение средств на расширение производства), которые бы максимизировали функцию:


Оптимальное распределение средств на расширение производстваОптимальное распределение средств на расширение производства (1.1)


при ограничении


Оптимальное распределение средств на расширение производства (1.2)


где xj количество груза j-гo типа, позволяющее достичь maxОптимальное распределение средств на расширение производства.

Процесс решения рассматриваемой задачи не является многоэтапным. Она относится к классу задач целочисленного линейного программирования. Однако ее можно решить методом динамического программирования. Для этого весь процесс решения потребуется разбить на этапы искусственно. На первом этапе рассматривают всевозможные варианты загрузки самолета предметами первого типа и среди них находят оптимальный. На втором этапе определяют вариант загрузки самолета предметами первого и второго типов и т.д. Процесс решения задачи продолжается до тех пор, пока не будет найден оптимальный вариант загрузки самолета предметами n типов.[1, с 241]

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

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


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

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

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

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


Оптимальное распределение средств на расширение производства (1.3)

Оптимальное распределение средств на расширение производства


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

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


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


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

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


Оптимальное распределение средств на расширение производства; (1.4)


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

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


Оптимальное распределение средств на расширение производства; (1.5)


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

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

Вычислить оптимальное решение задачи для каждого последующего шага процесса, двигаясь от конца расчетов к началу.[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 млн. ден. ед.


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


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

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

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: