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

СОДЕРЖАНИЕ

 

ВВЕДЕНИЕ………………………………………………………………………….2

1 МНОГОШАГОВЫЕ ПРОЦЕССЫ В ДИНАМИЧЕСКИХ ЗАДАЧАХ……4

 1.1 Принцип Беллмана…………………………………………………………….6

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

2 РЕШЕНИЕ ЗАДАЧИ ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ СРЕДСТВ НА РАСШИРЕНИЕ ПРОИЗВОДСТВА…………………………………………9

 2.1 Решение задачи оптимального распределения средств на расширение производства без применения компьютера………………………………………9

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

ЗАКЛЮЧЕНИЕ…………………………………………………………………..26

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ…………………………28

 

ВВЕДЕНИЕ

 

В настоящее время многие организации в своей деятельности сталкиваются с математическими  моделями. Математическая модель –  это система математических уравнений, неравенств, формул и различных математических выражений, описывающих поведение  реального объекта, составляющих его  характеристики взаимосвязи между  ними. Процесс построения математической модели называется математическим моделированием. Моделирование и построение математической модели экономического объекта позволяют  свести экономический анализ производственных процессов к математическому  анализу и принятию эффективных  решений. Для этого в планировании и управлении производством необходимо экономическую сущность исследуемого экономического объекта формализовать  экономико-математической моделью, т. е. экономическую задачу представить  математически.

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

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

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

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

Задачами данной курсовой работы являются:

1)определить рекуррентную природу задач динамического программирования,

2) изучить принцип Беллмана, его вычислительную схему,

3) решить задачу с использованием среды Microsoft Excel.

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

 

1. МНОГОШАГОВЫЕ ПРОЦЕССЫ В ДИНАМИЧЕСКИХ ЗАДАЧАХ

 

  В экономической практике встречается несколько типов задач, которые по постановке или способу решения относятся к задачам динамического программирования. Например, задачи оптимального перспективного и текущего планирования во времени, которые решают либо путем составления системы взаимосвязанных статических моделей для каждого периода, либо путем составления единой динамической задачи оптимального программирования с применением многошаговой процедуры принятия решений. К задачам динамического программирования следует отнести задачи многошагового нахождения оптимального размещения производительных сил, а также оптимального быстродействия. Смысл задач последнего типа состоит в следующем. Известна некоторая оптимальная структура производства с эффективностью Z₁. В начальный момент времени существует неоптимальная структура с эффективностью Z₀. Необходимо определить такие управляющие воздействия, которые за кратчайший период переведут структуру из начального положения в оптимальное (задача оптимальной перестройки).

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

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

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

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

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

(1.1)

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

(1.2)

где x_j — количество груза j-гo типа, позволяющее достичь max .

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

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

 

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

 

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

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

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

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

 (1.3)

где — оптимальное значение эффекта, достигаемого за шагов;

 n — количество шагов (этапов);

 — состояние системы на  - м шаге; — решение (управление), выбранное на - м шаге;

 — непосредственный эффект, достигаемый на - м шаге.

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

 

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

 

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

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

; (1.4)

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

; (1.5)

4. Найти условно-оптимальное решение на основе выражения (1.5);
5. Проверить, чему равно значение . Если расчет условно-оптимальных решений закончен, при этом найдено оптимальное решение задачи для первого состояния процесса. Если перейти к выполнению п. 3;
6. Вычислить оптимальное решение задачи для каждого последующего шага процесса, двигаясь от конца расчетов к началу.[1, с. 244]

 

 

 

 

 

 

 

 

 

2. РЕШЕНИЕ ЗАДАЧИ ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ СРЕДСТВ НА РАСШИРЕНИЕ ПРОИЗВОДСТВА

 

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

средств на расширение производства без применения компьютера

 

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

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

 

Таблица 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, т.е. предположим, что все имеющиеся средства выделяются на реконструкцию и модернизацию одного предприятия. Обозначим через ¦₁(x) максимально возможный дополнительный доход на этом предприятии, соответствующий выделенной сумме x. Каждому значению x отвечает вполне определенное (единственное) значение дополнительного дохода, поэтому можно записать, что:

 (2.1)

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

 

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

 

0	0
20	9
40	18
60	24

 

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

 (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 млн. ден. ед.

Рассмотрим ещё одну задачу. Для увеличения объемов выпуска пользующейся повышенным спросом продукции трем предприятиям выделены капиталовложения в размере 700 млн. руб. Каждому из предприятий может быть выделено капиталовложений: 0, 100, 200, 300, 400, 500, 600, 700 млн. руб. При этом прирост выпуска продукции каждым из предприятий в зависимости от капиталовложений дается таблицей 2.7.

 

Таблица 2.7 – Прирост выпуска продукции предприятием в зависимости от капиталовложений

 

Объем кап.влож. (млн. руб.)	Прирост выпуска продукции  (млн. руб.), в зависимости  от объема капиталовложений
	1	2	3
100	30	50	40
200	50	80	50
300	90	90	110
400	110	150	120
500	170	190	180
600	180	210	220
700	210	220	240

 

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

Решение. Задача состоит в определении наибольшего значения функции

при условии, что  . Рекуррентное соотношение Беллмана в нашем случае приводит к следующим функциональным уравнениям:

 

где – максимальный прирост выпуска продукции при выделении X млн. рублей 1 предприятию;

 – максимальный выпуск продукции при распределении X млн. рублей между первым и вторым предприятиями;

 – максимальный прирост при выделении всем трем предприятиям X=700 млн. рублей.

Находим :

При X=100 имеем

При X=200 имеем

При X=300 имеем

При X=400 имеем

При X=500 имеем

23

При X=600 имеем

При ,

Результаты вычислений записываем в таблицу 2.8.

 

Таблица 2.8 – Оптимальный объем капиталовложений, выделяемых предприятию

 

Объем кап. вложений X, выделяемых 1предприятию  (млн. руб.)	Максим. прирост (млн. руб.)	Условно оптимальный объем кап. вложений , выделяемых предприятию (млн. руб.)
100	30	100
200	50	200
300	90	300
400	110	400
500	170	500
600	180	600
700	210	700

 

Определим условно  оптимальные объемы капиталовложений, выделенных второму предприятию

_{При X=100 возможны только две комбинации вложения средств. Если в первое предприятие вложены все 100 млн.руб., то во второе предприятие ничего не вкладывается. Наоборот, если в первое предприятие ничего не вкладывалось, то все средства 100 млн.руб. вкладываются во второе предприятие.}

24

_{Обе комбинации дают определенные приросты выпуска продукции 30 и 50 млн.руб. Наибольший прирост 50 млн.руб. соответствует второй комбинации.}

_{При X=200 число комбинаций возрастает до трех. Если в первое предприятие вложить все средства 200 млн.руб., то во второе предприятие вкладываться ничего не будет. Можно вложить в два предприятия средства поровну по 100 млн.руб. наконец, можно вложить все средства во второе предприятия, так как в первое предприятие ничего не было вложено.}

_{В данном случае выбираем вторую и третью комбинации, так как обе  имеет прирост  продукции – 80.}

_{При X=300 возможны уже четыре комбинации}

_{Имеем третью комбинацию, при которой в  первое предприятие  вложено 100 млн.руб., а во второе – 200 млн.руб. Прирост продукции данной комбинации составляет 110 млн.руб.}

_{При X=400}

_{Среди пяти возможных комбинации выбирается последняя, при которой все средства вложены во второе предприятие, а в первое предприятие ничего не вкладывается.}

_{При X=500,}

_{При распределении 500 млн.руб. необходимо выбрать шестую комбинацию, так она приносит наибольший прирост продукции, равный 190 млн.руб.}

_{Все средства должны быть вложены  во второе предприятие.}

_{При X=600 имеем}

_{В данном случае выбираются вторая и шестая комбинации, у которых одинаковое количество наибольшего  прироста выпуска  продукции – 220 млн.руб. По одной комбинации в первое предприятие необходимо вложить 500 млн.руб., а во второе – 100 млн.руб. А по другой комбинации, наоборот, в первое – 500 млн.руб., а во второе – 100 млн.руб.}

_{При X=700 имеем}

При распределении 700 млн.руб выбирается третья комбинации, при которой 500 млн.руб. вкладываются в первое предприятие, а 200 млн.руб. во второе предприятие. Данная комбинации принесет наибольший прирост выпуска продукции равной 250 млн.руб.

 Полученные результаты записываем в таблицу 2.9.

 

Таблица 2.9 – Условно оптимальный объем капиталовложений, выделяемых предприятию

 

Объем кап. вложений X, выделенных двум предприятиям (млн. руб.)	Максимальный прирост  выпуска продукции первым и вторым предприятиями вместе (млн. руб.)	Условно оптимальный объем капиталовложений , выделяемых 2 предприятию (млн. руб.)
100	50	100
200	80	100,200
300	110	200
400	150	400
500	190	500
600	220	100,500
700	250	200

 

Пусть теперь рассматриваются  одновременно три предприятий, тогда  им будет выделяться весь объем капиталовложений, то есть X=700.

.

По седьмой комбинации получен максимальный прирост выпуска  продукции, который составляет 270 млн. руб. при этом третьему предприятию  будет выделено 600 млн.руб. Остальные 100 млн.руб. распределяются между первым и вторым предприятиями.

Тогда таблице 2.9. находим при , следовательно .

Итак, максимальный прирост  выпуска продукции можно ожидать, выделив третьему предприятию 600 млн. руб., второму 100 млн. руб., а первому предприятию дополнительных капиталовложений выделять не надо.

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

 на расширение производства  средствами Microsoft Exсel

 

Приведём пример решения  одной из задач с помощью электронных  таблиц Excel.

Производственному объединению из трёх предприятий (m=3) выделяются финансовые средства общим объемом В на четыре года (n=4).

Известны  общие потребности объединения в финансовых ресурсах d_j по каждому j-му периоду (j=1…4).

По каждому  i-тому предприятию (i=1…3) имеются нижние k_ij и верхние K_ij ограничения на объем финансирования в каждом j-том периоде (j=1…4).

Заданы величины эффекта c_ij от вложения единицы средств в i-тое предприятие в j-том периоде.

Найти оптимальное  распределение финансовых средств  между предприятиями по периодам, обеспечивающее максимальный эффект от вложенных средств.

Рассмотрим следующий  вариант исходных данных:

Составим  математическую модель задачи оптимального финансирования:

Пусть x_ij – объем финансирования i-того предприятия в j-том периоде, тогда – суммарное финансирование всех объектов в j-том периоде.

В общем виде математическая модель может  иметь вид:

Целевая функция: максимизировать суммарный эффект от финансирования всех предприятий за весь период

Ограничения:

1. на общий объем финансирования:
2. на потребности в финансировании в каждом периоде по всем объектам в целом: для j=1, 2, 3, 4.
3. на нижние и верхние пределы финансирования по некоторым предприятиям:

Для приведенного варианта исходных данных математическая модель будет  иметь вид:

ЦФ: 4x₁₁+ 5x₁₂+ 6x₁₃+ 3x₁₄+ 7x₂₁+ 8x₂₂+ 9x₂₃+ 10x₂₄+ 6x₃₁+ 5x₃₂+ 8x₃₃+ 6x₃₄ à max

Огр: 1) x₁₁+ x₁₂+ x₁₃+ x₁₄+ x₂₁+ x₂₂+ x₂₃+ x₂₄+ x₃₁+ x₃₂+ x₃₃+ x₃₄ <=200