Математические методы решения задачи

Министерство образования и науки Республики Казахстан

Колледж при Академии Экономики и Права

КУРСОВОЙ ПРОЕКТ

По дисциплине: «Моделирование производственных и экономических про­цессов»

На тему: Моделирование распределения задания между предприятиями

Выполнил: Давутов И.

Группа КПО-401

Проверила: Жәдік Ө. Л.

Алматы 2014

Содержание

Введение ………………………………………………………………3

1. Теоретическая часть ……………………………………………….. 5

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

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

4. Модель задачи

5. Практическая часть

Заключение

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

Введение

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

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

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

Общим для задач динамического программирования является то, что переменные рассматриваются не вместе, а последовательно, одна за другой. Сущность состоит в том, что строится такая вычислительная схема, когда вместо одной задачи со многими переменными строится много задач с малым числом переменных (обычно даже одной) в каждой. Это значительно сокращает объем вычислений. Однако такое преимущество достигается лишь при двух условиях: когда критерий оптимальности аддитивен, т. е. общее оптимальное решение является суммой оптимальных решений каждого шага, и когда будущие результаты не зависят от предыстории того состояния системы, при котором принимается решение. Это вытекает из принципа оптимальности Беллмана, лежащего в основе теории динамического программирования.

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

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

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

1. Теоретическая часть

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

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

Ставится вопрос: как распределять имеющиеся средства между предприятиями, чтобы суммарный доход от всех предприятий был максимальным?

Это типичная задача динамического программирования, в которой рассматривается управляемый процесс – функционирование группы предприятий. Управление процессом состоит в распределении (и перераспределении) средств. Управляющим воздействием (УВ) является выделение каких-то средств каждому из предприятий в начале года.

УВ на каждом шаге должно выбираться с учетом всех его последствий в дальнейшем. УВ должно быть дальновидным, с учетом перспективы. Нет смысла выбирать на рассматриваемом шаге наилучшее УВ, если в дальнейшем это помешает получить наилучшие результаты других шагов. УВ на каждом шаге надо выбирать “c заглядыванием в будущее”, иначе возможны серьезные ошибки.

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

Исходя из их узких интересов данного шага, нужно было бы все средства вложить в производство предметов потребления, пустить имеющиеся машины на полную мощность и добиться максимального объема прибыли. Но правильным ли будет такое решение в целом? Очевидно, нет. Имея в виду будущее, необходимо выделить какую-то долю средств и на производство машин. При этом объем продукции за первый год, естественно, снизится, зато будут созданы условия, позволяющие увеличивать ее производство в дальнейшем.

Математические методы решения задачи

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

Обозначим через X_k управление на k-м шаге (k=1, 2, …,n). Оно должно удовлетворять некоторым требованиям, т.е. быть допустимым. Пусть – управление, переводящее систему из начального состояния So в состояние . Обозначим как состояние системы после -го шага. Показатель эффективности рассматриваемой операции – целевая функция – зависит от начального состояния и управления:

Допускается ряд предположений.

1. Состояние системы зависит только от состояния на предыдущем шаге и управления (и не зависит от других предыдущих состояний и управлений).

Или

.

2. Является

как эффективность -го шага. Целевая функция является суммой показателей эффективности каждого шага.

Задача пошаговой оптимизации (задача ДП) формулируется так: определить такое допустимое управление переводится из начального состояния в состояние , при котором целевая функция принимает наибольшее (наименьшее) значение.

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

N – число шагов;

– вектор, описывающий состояние системы на k-м шаге;

– начальное состояние, т. е. состояние на 1-м шаге;

– конечное состояние, т. е. состояние на последнем шаге;

X_k – область допустимых состояний на k-ом шаге;

– вектор УВ на k-ом шаге, обеспечивающий переход системы из состояния x_k-1 в состояние x_k;

U_k – область допустимых УВ на k-ом шаге;

W_k – величина выигрыша, полученного в результате реализации k-го шага;

S – общий выигрыш за N шагов;

– вектор оптимальной стратегии управления или ОУВ за N шагов;

S_k+1( ) – максимальный выигрыш, получаемый при переходе из любого состояния в конечное состояние при оптимальной стратегии управления начиная с (k+1)-го шага;

S₁( ) – максимальный выигрыш, получаемый за N шагов при переходе системы из начального состояния в конечное при реализации оптимальной стратегии управления .

Очевидно, что S = S₁( ), если – фиксировано.

Метод динамического программирования опирается на условие отсутствия последействия и условие аддитивности целевой функции.

Условие отсутствия последействия. Состояние , в которое перешла система за один k-й шаг, зависит от состояния и выбранного УВ и не зависит от того, каким образом система пришла в состояние , то есть

математический метод программирование оптимизация

Аналогично, величина выигрыша W_k зависит от состояния и выбранного УВ , то есть

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

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

Условие отсутствия последствий позволяет сформулировать принцип оптимальности Беллмана.

Принцип оптимальности. Каково бы ни было допустимое состояние системы перед очередным i-м шагом, надо выбрать допустимое УВ на этом шаге так, чтобы выигрыш W_i на i-м шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным.

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

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

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

Таким образом, стоит задача: определить оптимальное управление на каждом шаге (i=1,2,...N) и, значит, оптимальное управление всем процессом .

Многошаговый процесс, необходимо выбирать УВ на каждом шаге с учетом его дальнейших последствий на еще предстоящих шагах. Однако, из этого правила есть исключение. Среди всех шагов существует один, который может планироваться без "заглядывания в будущее". Какой это шаг? Очевидно, последний — после него других шагов нет. Этот шаг, единственный из всех, можно планировать так, чтобы он как таковой принес наибольшую выгоду. Спланировав оптимально этот последний шаг, можно к нему пристраивать предпоследний, к предпоследнему — предпредпоследний и т.д.

Поэтому процесс динамического программирования на 1-м этапе раз­ворачивается от конца к началу, то есть раньше всех планируется последний, N-й шаг. А как его спланировать, если не очевидно, чем кончился предпоследний? Очевидно, нужно сделать все возможные предположения о том, чем кончился предпоследний, (N—1)-й шаг, и для каждого из них найти такое управление, при котором выигрыш (доход) на послед­нем шаге был бы максимален. Решив эту задачу, найдётся условно оптимальное управление (УОУ) на N-м шаге, т.е. управление, которое надо применить, если (N—1)-й шаг закончился определенным образом.

Допускается, что эта процедура выполнена, то есть для каждого исхода (N—1)-го шага имеется УОУ на N-м шаге и соответствующий ему условно оптимальный выигрыш (УОВ). Теперь можно оптимизировать управление на предпоследнем, (N — 1)-м шаге. Деалются все возможные предположения о том, чем кончился предпредпоследний, то есть (N—2)-й шаг, и для каждого из этих предположений находится такое управление на (N—1)-м шаге, чтобы выигрыш за последние два шага (из которых последний уже оптимизирован) был максимален. Далее оптимизируется управление на (N—2)-м шаге, и т.д.

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

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

Действительно, пусть известно начальное состояние процесса. Теперь уже ясно, что делать на первом шаге: надо применить УОУ, найденное для первого шага и начального состояния. В результате этого управления после первого шага система перейдет в другое состояние; но для этого состояния имеется УОУ и т д. Таким образом, ищется оптимальное управление процессом, приводящее к максимально возможному выигрышу.

Таким образом, в процессе оптимизации управления методом динамического программирования многошаговый процесс "проходится" дважды: первый раз — от конца к началу, в результате чего находятся УОУ на каждом шаге и оптимальный выигрыш (тоже условный) на всех шагах, начиная с данного и до конца процесса; второй раз — от начала к концу, в результате чего находятся оптимальные управления на всех шагах процесса.

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

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

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

Каждое предприятие при инвестировании в него средств X у.е. приносит прибыль Pi (x) у.е. (i = l, 2 и 3) последующим данным, приведённым в таблице 1.

Таблица 1 – Исходные данные.

Инвестируемые средства (у.е.)	Общая прибыль (у.е.)
Х	P1(x)	P2(x)	P3(x)
	3,22	3,33	4,27
	3,57	4,87	7,64
		5,26	10,25
	4,12	7,34	15,93
	4,85	9,49	16,12

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

Математическую модель задачи:

1. Число шагов в данной задаче равно 3;

2. Пусть S - количество средств, имеющихся в наличии перед данным шагом, и характеризующих состояние системы на каждом шаге;

3. Управление на i -ом шаге (i = l,2,3) выберем X, - количество средств, инвестируемых в i -ое предприятие;

4. Выигрыш Pi (Xi) на i -ом шаге - это прибыль, которую приносит I -oe предприятие при инвестировании в него средств Xi. Если через выигрыш в целом обозначить общую прибыль W, то

W = P₁ (x₁) + P₂ (x₂) + P₃(x₃);

5. Если в наличии имеются средства в количестве S у.е. и в i -oe предприятие инвестируется X у.е., то для дальнейшего инвестирования остается (S-X) у.е. Таким образом, если на i -ом шаге система находилась в состоянии S и выбрано управление X, то на (i + 1) -ом шаге система будет находиться в состоянии (S-X), и, следовательно, функция перехода в новое состояние имеет вид:

F_i (S-X) = S-X;

6. На последнем (i=3) шаге оптимальное управление соответствует количеству средств, имеющихся в наличии, а выигрыш равен доходу, приносимым последним предприятием:

X_i (S) = S. W_i (S) = P_i (S);

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

W_i (S) = max_x<=s {P_i (X) + W_i+1 (S - X)}

5.Практическая часть

Проводится пошаговая оптимизация, по результатам которой заполняется таблица 2.

Таблица 2 – Итоговые данные.

S	i = 3	i = 2	i = 1
X3 (s)	W3 (s)	X2 (s)	W2 (s)	X1 (s)	W1 (s)
		4,27		4,27	-	-
		7,64		7,64	-	-
		10,25		10,97	-	-
		15,93		15,93	-	-
		16,12		19,26		19,26

В первой колонке таблицы записываются возможные состояния системы, в верхней строке

- номера шагов с оптимальным управлением и выигрышем на каждом шаге, начиная с последнего.

Так как для последнего шага i = 3 функциональное уравнение имеет вид:

X₃ (S) = S,

W₃ (S) = P₃ (S),

то две колонки таблицы, соответствующие

i = 3, заполняются автоматически по таблице исходных данных.

На шаге i = 2 основное функциональное управление примет вид:

W₂ (S) = max_x<=s {P₂ (X) + W₃ (S - X)}

Поэтому для проведения оптимизации на этом шаге заполняется таблица 3 для различных состояний S при шаге i = 3.

Таблица 3 – Второй шаг обработки.

S	X	S-X	P2 (x)	W3 (s-x)	P2 (x) + W3 (s-x)	W2 (s)
				4,27	4,27	4,27
		3,33		3,33
				7,64	7,64	7,64
		3,33	4,27	7,6
		4,87		4,87
				10,25	10,25	10,97
		3,33	7,64	10,97
		4,87	4,27	9,14
		5,26		5,26
				15,93	15,93	15,93
		3,33	10,25	13,58
		4,87	7,64	12,51
		5,26	4,27	9,53
		7,34		7,34
				16,12	16,12	19,26
		3,33	15,93	19,26
		4,87	10,25	15,12
		5,26	7,64	12,9
		7,34	4,27	11,61
		9,49		9,49

На шаге i = 1 основное функциональное управление примет вид:

W₁ (S) = max_x<=s {P₁ (X) + W₂ (S - X)},

а состояние системы перед первым шагом S = 5, поэтому для проведения оптимизации на этом шаге заполняется таблица 4.

Таблица 4 – Первый шаг обработки.

S	X	S-X	P1 (x)	W2 (s-x)	P1 (x) + W2 (s-x)	W1 (s)
				19,26	19,26	19,26
		3,22	15,93	19,15
		3,57	10,97	14,54
			7,64	11,76
		4,12	4,27	8,27
		4,85		4,85

Наибольшее значение выигрыша составляет 19,26. При этом

оптимальное управление на первом шаге составляет X₁ (S₁)=при этом S₁=5, на втором шаге X₂ (S₂)=1 при этом S₂=S₁–X₁=5 и на третьем шаге X₃(S₃)=4

при этом

S₃=S₂–X₂=4.

Это означает, что (0, 1, 4) - оптимальный план распределения инвестиций между предприятиями.

Таким образом, для получения наибольшей обшей прибыли в размере 19,26 у.е., необходимо вложить 1 у.е. во второе предприятие и 4 у.е. в третье предприятие.

Заключение

В процессе написания данной курсовой работы были углублены знания в “Математические методы”. Также в процессе работы над курсовой работой изучены множественные информационные источники разной предметной направленности в таких сферах, как “Динамическое программирование” и “Экономической оптимизации”.

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