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

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

 

 

 

 

 

 

 

 

 

 

ГЛАВА 2

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

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

В реальных задачах управления приходится принимать и реализовывать решения по нескольким этапам. Такие задачи многоэтапной оптимизации называют задачами динамического программирования (ДП), в том числе: 

1) распределение  ресурсов, например, ограниченного  объема капиталовложений между возможными направлениями их использования по объему и времени;

2) разработка  правил управления запасами, устанавливающих момент пополнения и размер пополняемого запаса;

3) выбор транспортных  маршрутов или технологических  способов изготовления изделий;

4) разработка  принципов календарного планирования  производства.

Пример 1.

Пусть установлены возможные варианты транспортной сети из маршрутов, соединяющих исходный пункт 1 с конечным пунктом 10. Все 10 пунктов можно отнести к пяти зонам (этапам). На линиях, соединяющих пункты, поставлено время проезда между соседними пунктами (рис. 1).

 

Рисунок 1.

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

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

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

Допустим, мы оказались в зоне IV (пп. 8, 9), из которой надо продвинуться в зону V (п. 10) (табл. 1).

Таблица 1

Из пп. IV зоны	В п. 10 зоны V	min Tiv-v
8	1	1
9	4	4

 

Таким образом, следуя от конца маршрутов, мы сначала определили, через какой пункт двигаться при условии, чтобы оказаться в зоне III, затем при условии, чтобы оказаться в зоне II  и наконец - в зоне I. Следовательно, на первом цикле решения определилось условно-оптимальное решение. Во втором - следуя от начала к концу маршрута по таблицам 2 - 4 где условно-оптимальные решения не затемнены, находим действительно оптимальное решение:

 

1) из таблицы 4: п. 1 -> п. 3;

2) из таблицы 3: п. 3 -> п. 7;

3) из таблицы 2: п. 7 -» п. 9;

4) из таблицы 1: п. 9 -» п. 10.

 

Таблица 2

Из пп. Ш зоны	Через пп. IV зоны		min TIII-v
	8	9
5	7 + 1	5 + 4	8
6	3+1	4 + 4	4
7	7 + 1	1 + 4	5

Таблица 3

	Через пп. Ш зоны
Из пп. П зоны	Б	6	7	min T П-v
2	10 + 8	12 + 4	—	16
3	5 + 8	10 + 4	7 + 5	12
4	—	15 + 4	13 + 5	18

Таблица 4

	Через пп. III зоны
Из пп. II зоны	2	3	4	Min TI-v
1	2 + 16	5 + 12	1 + 18	17

 

2.2 Обобщенная  схема задачи распределения ресурсов

Пусть имеется ресурс K, который требуется вложить в m объектов в течение n этапов. В результате вложения в i-й объект (i = 1,…,m) на j-м этапе (j = 1, ..., n) ресурса в размере xij образуется доход, определяемый функцией дохода ). Часть ресурса при этом остается неизрасходованной. Эта часть определяется функцией остатка jij (xij). Известна величина ресурса Kj распределяемая на каждом j-м этапе.

Требуется определить значения вложения ресурсов на каждом этапе в каждый объект, чтобы на всех объектах и на всех этапах он был максимальным (рис. 2).

 

 

 

 

 

 

Рисунок 2.

 

 

Данная задача аналитически формулируется:

 

maxF

j

Принцип оптимальности Беллмана: на каждом этапе необходимо так распределять ресурс, чтобы, начиная с этого этапа и до конца процесса распределения, доход был максимальным.

 

2.3 Задачи динамического  программирования

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

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

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

Предположим, что есть некоторые ресурсы х, которые распределяются на два предприятия: на первое у, на второе х - у. Пусть в течение определенного периода (например, года) количество у приносит доход (прибыль) g(y), а количество х-у доход h(x - у). Общий доход от вложенных ресурсов составит

 

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

Тогда

(1)

Теперь рассмотрим двухшаговый процесс, состоящий из двух периодов (этапов). Так как доход получается вследствие выпуска и реализации продукции, что связано с определенными издержками (затратами ресурсов), то к началу второго периода первоначальная сумма y уменьшится до величины а* у (0 а 1), а сумма х - у до величины b* (х- у) (0 b 1). Наибольший доход, который можно получить от суммарного остатка а* у + b* (х — у) в течение второго этапа, равен

Обозначим через Fz(x) наибольший доход, который может быть получен от суммы х за оба периода. Этот доход равен максимальному значению суммы доходов первого и второго периодов при условии, что начальные для каждого периода ресурсы распределялись наилучшим образом. Иначе

(2)

Равенство (2) устанавливает связь между функциями

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

Fn(x) =  (3)

Определив по равенству (1) пользуясь (2),вычисляем затем F3(x) и т. д. Значение Fn(х) является доходом, полученным за n шагов.

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

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

Это означает, как следует из уравнения Беллмана, что максимальный доход от n-шагового процесса равен сумме доходов от 1-го и (n - 1) последующих шагов при условии наилучшего распределения в последующих шагах оставшихся после 1-го шага ресурсов.

 

 

 

 

 

 

 

 

 

 

 

ГЛАВА 3

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

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

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

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

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

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

3.2 Задача динамического программирования на примере распределения  ресурсов между 4-мя ювелирными мастерскими

Задача:

Входе разработки нового месторождения золота, были получены ресурсы в виде 200кг золота в год. Задача составить план распределения  ресурсов между 4-мя ювелирными мастерскими ( 1-Алмаз Холдинг; 2-Ювелирцентр; 3-Аквамарин; 4- Александрит), максимизирующий прибыль. Если известны производственные данные (таблица1).

Таблица 1

Капитало-вложения	Прибыль от выпуска продукции i-го предприятия (x), кг./т.р.
	1	2	3	4
0	0	0	0	0
50	25	30	30	28
100	60	70	70	56
150	100	90	95	110
200	140	122	130	142

Требуется составить план распределения ограниченных капиталовложений золота по этим предприятиям (К = 200 кг.), максимизирующий общий прирост выпуска при заданной номенклатуре и структуре отраслевого плана производства продукции.

Решение. Данная задача может быть решена методом динамического программирования.

Обозначим: (x) – прибыль от выпуска продукции (кг./т.р.) на i-м предприятии при х кг. капиталовложений; F(K) - максимально возможная прибыль от выпуска продукции (кг./т.р.) при распределении суммы К между четырьмя предприятиями.

Тогда согласно основному функциональному уравнению Беллмана: