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

МИНИСТЕРСТВО КУЛЬТУРЫ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

Quot; САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

КИНО И ТЕЛЕВИДЕНИЯ"

Кафедра математического моделирования

ПРИМЕНЕНИЕ ЭКОНОМИКО-МАТЕМАТИЧЕСКИХ МЕТОДОВ В ПЛАНИРОВАНИИ ДЕЯТЕЛЬНОСТИ ПРЕДПРИЯТИЯ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

по выполнению курсовой работы

по дисциплине

«ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ»

Раздел «Динамическое программирование»

Для студентов ФМК специальности 080507 «Менеджмент организации» и

ФУП специальности 080502 «Экономика и управление на предприятии (социально-культурной сферы)» дневного, вечернего и заочного отделений

Санкт-Петербург

Составители: Веселова С.В., доцент;

Волчанинова В.В. доцент;

Шутов В.И., доцент

Рецензенты: Янсон Э.Ж. профессор

Применение экономико-математических методов в планировании деятельности предприятия: методические указания по выполнению курсовой работы/ составители: Веселова С.В., Волчанинова В.В., Шутов В.И. – СПб.: СПбГУКиТ, 2005. – 18с.

В методических указании рассмотрена одна из задач динамического программирования – задача управления запасами и изложены рекомендации по выполнению курсовой работы. Предназначены для студентов дневного отделения специальностей: 060800 «Экономика и управление на предприятии (социально-культурной сферы)» и 061100 «Менеджмент организации».

Рекомендовано к изданию в качестве методических указаний кафедрой математического моделирования.

Протокол № 1 от 30 августа 2005г.

© СПбГУКиТ, 2005

СОДЕРЖАНИЕ

Введение………………………………………………………………………...2

1. Задача управления запасами как пример задачи динамического программирования……………………………………………………..........2

1.1. Общая постановка задачи управления запасами……………………..2

1.2. Задача управления запасами в динамической форме………………...3

2. Пример решения задачи управления запасами…………………………….6

2.1. Нахождение оптимальной производственной программы...………...6

2.2. Анализ решения задачи управления запасами……………………….10

3. Содержание курсовой работы……………………………………………...13

4. Варианты заданий для курсовой работы…………………………………..14

5. Список рекомендуемой литературы……………………………………….18

ВВЕДЕНИЕ

Данные методические указания посвящены изучению такого раздела динамического программирования как задача управления запасами.

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

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

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

1. ЗАДАЧА УПРАВЛЕНИЯ ЗАПАСАМИ КАК ПРИМЕР ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

1.1.Общая постановка задачи управления запасами

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

Эта задача по сути является задачей разработки календарной программы выпуска изделия на плановый период, состоящий из N отрезков времени.

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

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

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

Построим математическую модель этой задачи.

Обозначим x_t – выпуск продукции в отрезке времени t.

I_t – уровень запасов на конец отрезка t.

D_t – спрос на продукцию в отрезке времени t, D_t > 0.

Затраты для каждого периода t зависят от выпуска продукции x_t, а также зависят от уровня запасов i_t и от периода t.

Обозначим все эти затраты как C_t (x_t, i_t).

Тогда, целевая функция будет выглядеть так:

(1)

Составим ограничения:

1) Будем считать, что объем выпуска целочисленная величина

x_t = 0, 1, 2, 3, … (2)

для t = .

2) Предполагается, что на конец последнего отрезка времени N уровень запасов равен 0.

(3)

3) Условие полного и своевременного удовлетворения спроса в пределах каждого отрезка времени обеспечивается двумя следующими ограничениями:

Первое — балансовое: уровень запасов на конец отрезка t, равен уровню запасов на начало отрезка t плюс выпуск продукции в течение отрезка t и минус спрос на продукцию в течение отрезка времени t:

(4)

Тогда спрос

Второе – целочисленность уровня запасов:

i_t = 0, 1, 2, 3… (5)

для t =

Таким образом, модель адекватна поставленной задаче.

Заметим, что на практике функция затрат C_t (x_t, i_t) чаще всего бывает нелинейна. Так, при выпуске партии изделий могут потребоваться дорогостоящие затраты, например затраты на пуск и наладку оборудования, поэтому затраты на производство первой единицы партии могут превышать затраты на производство остальных единиц партии. Например, если объем производства превышает мощность производственного участка, то дополнительные затраты на единицу изделия увеличиваются за счет использования сверхурочных работ.

1.2. Задача управления запасами в динамической форме

Рассмотрим N – количество отрезков времени. N = 6, Плановый период —это: Январь, Февраль, … Июнь. В этой постановке конечное состояние – это начало последнего отрезка планового периода, для нас 1 июня. Исходное состояние – начало первого отрезка (когда впереди N шагов).

Будем использовать систему индексов, при которой подстрочный индекс «1» соответствует конечному состоянию, а подстрочный индекс «N» соответствует начальному состоянию.

Обозначим «d_n» - спрос на продукцию на отрезке времени, отстоящем от конца планового периода на n шагов, включая рассматриваемый:

d ₁ – спрос на июнь,

d ₃ – спрос на апрель.

Обозначим C_n (х, i) – затраты на отрезке времени, отстоящем от конца на n шагов, связанные с выпуском х единиц продукции и затратами на хранение запасов, уровень которых на конец отрезка равен i единиц. Так, С ₃ (10, 15) – затраты на производство в апреле 10 единиц продукции и хранение запасов, уровень которых на 30 апреля составит 15 единиц.

В этой системе обозначений

d₁ = D_N, d_N = D₁,

C₁ (х, i) = C_N (х, i)

Например, N =4 тогда, если рассматриваем программу с начала год, то

d₄ = D₁ – январский спрос;

d₁ = D₄ – апрельский спрос.

Состояние системы в начале любого отрезка, определяется уровнем запаса на начало отрезка. Для принятия решения об объеме выпуска в текущем отрезке времени не требуется знать, каким образом достигнут уровень запасов на начало отрезка. Учитывая это, введем обозначения:

- минимальные затраты на n оставшихся отрезков, при начальном уровне запасов i.

Например, f ₂ (10) – минимальные затраты на май и июнь, при условии, что на 1 мая у нас 10 единиц запасов.

- выпуск продукции, обеспечивающий достижение .

Согласно условию (3) уровень запасов на конец планового периода равен нулю. Поэтому

f ₀ (0) = 0 (6) (здесь n = 0)

Рассмотрим случай n = 1 – это начало последнего отрезка времени. Начальный уровень запасов здесь i, может быть любым неотрицательным целым числом не большим чем d ₁ (спрос на этом отрезке), чтобы запас на конец отрезка был равен нулю.

Запишем условие (4) для этого отрезка:

(4')

(т.е. 0 = i₁ + x₁ − d₁)

Независимо от значения i спрос в последнем отрезке времени полностью удовлетворяется при объеме выпуска равным .

Тогда затраты (7)

(i = 0, 1, 2…d₁)

Перейдем к n = 2. Если начальный уровень запасов равен i (для 1 мая) n = 2, то общие затраты для двух последних месяцев (с 1 мая по 30 июня) составят:

, где

С₂ – затраты в мае;

х – выпуск в мае;

i – запасы на 1 мая;

d ₂ – спрос за май;

- оптимальные затраты на июнь

- уровень запасов на конец предпоследнего или начало последнего периода.

Величина запаса i для n = 2 (запас на 1 мая) может принимать любые неотрицательные целые значения не превосходящие d ₁ + d ₂, чтобы на конец планового периода уровень i был равен 0.

При заданном i величина х должна быть не меньше чем (d ₂ – i), что обеспечивает полное удовлетворение спроса на предпоследнем отрезке. В то же время величина х не должна быть больше чем , т.к. конечный запас равен нулю.

Тогда, ,

Где .

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

Аналогично вычисляется - если известно и в конце концов мы вычислим , где i ₀ – уровень запасов на начало всего планового периода i ₀ в рассматриваемом примере – на 1 января.

Рекуррентное соотношение для вычисления оптимальной стоимости затрат можно записать так:

(8)

где n = 1, 2, 3, …, N;

;

х – неотрицательная целочисленная величина, лежащая в пределах

.

Замечание: Так как начальный уровень запасов i рассматривается как переменная величина, полностью характеризующая состояние системы, то единственной независимой управляющей переменной в рекуррентном соотношении (8) является х, так как уровень запасов на конец отрезка равен (i = x - d_n).

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

1. f ₀ (0) и вычисляются по формулам (6) и (7).

2. Непосредственно и поочередно вычисляются

, , …,

3. Вычисляются

, , …,

N -1. Вычисляются

, , …..

N. Вычисляется .

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

В этом случае уровень запасов на начало второго отрезка равен

Далее находим объем выпуска для второго отрезка и т.д.

Таким образом можно сделать следующие выводы:

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

2. N обозначает число шагов (число отрезков планового периода)

Если N = 4, то n = 1 – это апрель

n = 4 – это январь

d ₄ – спрос на январь

3. Уровень запасов на начало отрезка времени является характеристикой системы за n шагов до конца планового периода.

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

2. ПРИМЕР РЕШЕНИЯ ЗАДАЧИ УПРАВЛЕНИЯ ЗАПАСАМИ

2.1. Нахождение оптимальной производственной программы

Рассмотрим следующий пример:

Пусть количество отрезков времени N = 6 (Январь – Июнь), спрос D_t = 3, для t = . Затраты определяются по формуле:

, где

x_t – выпуск продукции;

- запасы на конец отрезка t;

h∙ i_t – затраты на хранение;

h = 1 – затраты на хранение единицы продукции;

- производственные затраты

, где t = ;

, где t = .

Производственные затраты – это сумма условно постоянных затрат на переналадку оборудования – 13 и затрат пропорциональных выпуску продукции - .

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

;

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

Обозначим:

- минимальные затраты на n последних отрезков при начальном уровне запасов i.

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

Пусть n = 1.

Рассмотрим программу на последний месяц (на июнь)

D ₆ = D _июня = 3 – спрос на июнь.

Запишем условие (4) для рассмотренного примера:

Где - уровень запасов на конец всего планового периода (для нас ), - спрос на июнь.

Тогда .

Следовательно , т.е.

Уровень запасов для n =1 не превышает 3.

Тогда выпуск x ₁ неотрицательный, целая величина лежит в пределах:

, т.е.

Выпуск в июне , где i - запас на начало последнего периода, (на 1 июня).

Теперь можно составить таблицу.

= 13 + 2(3 – i).

Таблица 1

Возможные значения запаса

Для каждого шага n будем строить одну таблицу, в которой предусмотрено:

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

2) по одному столбцу для каждого возможного значения объема выпуска продукции х.

Будем записывать минимальные затраты для соответствующих сочетаний выпуска х и начального запаса i.

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

Для n = 2 формула для заполнения клеток таблицы:

, где

- затраты на хранение единицы продукции

13 + 2 х – затраты на производство

– затраты на хранение

– минимальные затраты на июнь

Ограничения для уровня запасов

Тогда для данной задачи , но по условию ; следовательно .

Ограничения для выпуска продукции: ,

Так, например,

, следовательно , но по условию и тогда

, и т.д.

Согласно указанным ограничениям можно отметить запрещенные клетки: для это клетки (1; 0) и (1; 1).

Таблица 2

х
	* х	*	*
	*	*
	*					*
					*	*
				*	*	*

кл. (0; 3):

кл. (1; 2):

кл. (1; 3):

Для n = 3 формула для заполнения таблицы следующая:

(для нашего примера )

Таблица 3

х
	*	*	*	19 + 38	22 + 26	25 + 24
	*	*	17 + 38	20 + 26	23 + 24	26 + 19
	*	15 + 38	18 + 26	21 + 24	24 + 19	27 + 18
	0 + 38	16 + 26	19 + 24	22 + 19	25 + 18	*
	1 + 26	17 + 24	20 + 19	23 + 18	*	*

Примечание: х – в клетке, ставится знак «*», значит клетка запрещена, например кл. (0; 0): спрос в данном случае 3, а выпуск 0, данный объем выпуска не может обеспечить такой спрос, следовательно, клетка запрещена.

Аналогично составляем таблицы для n = 4, n = 5 и n = 6.

Для получения оптимальной программы составляем сводную таблицу.

Таблица 4

Начальный запас на период

3 или 4

*

*

Найдем оптимальную программу выпуска продукции.

Пусть запас на начало всего планового периода будет равен 0, тогда получим таблицу 5.

Таблица 5

Оптимальная программа выпуска

Число шагов до конца планового периода	Запас на начало месяца	месяц	Оптимальный выпуск	Запас на конец месяца
		Январь
		Февраль
		Март
		Апрель
		Май
		июнь

2.2. Анализ решения задачи управления запасами

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

Рассмотрим параметр «длительность планового периода». Для определенности будем считать, что плановый период начинается в январе.

Таблица 6

Влияние длительности планового периода на затраты

Предположим, что начальный уровень запасов равен 0.

Заполним первую строку.

N = 1. Это означает, что плановый период состоит из одного месяца.

Берем данные из сводной таблицы.

Для N = 1 январь отстоит от конца периода на один шаг, значит n = 1.

Для определения выпуска в сводной таблице выбираем столбцы соответствующие n = 1.

N = 2, значит n = 2 выпуск в январе 3, далее выпуск в феврале, отстоит от конца на 1 шаг значение n = 1 и запасов 0. 3 выпуск и 3 продали в январе, выпуск в феврале 3 для = 0, n = 1.

Вторая строка: Плановый период состоит из двух месяцев:

Январь – февраль. В этом случае январь отстоит от конца планового периода на два шага, поэтому в сводной таблице выбираем столбик n = 2. Это выпуск x = 3. Запас на начало февраля = 0 + 3 – 3 = 0. Февраль в этом случае отстоит от конца планового периода на один шаг. Поэтому, в сводной таблице выбираем столбец соответствующий n = 1.

Март N = 3. Январь n = 3 выпуск = 4, а спрос = 3, февраль = 1, n = 2, выпуск = 5, а спрос 3 + 3 = 6, следовательно, 9 – 6 = 3 значит Март = 3, выпуск = 0, т.к. n = 1, а запас = 3.

N = 4, Январь, n = 4, х = 3 или 4; вывод х ₁ = 3.

Для N = 6 январь = 0, n = 6, х = 4. Следовательно, т.к. спрос = 3, то , а n = 5, пересечение строк дает х _{февраль}= 5. Тогда запасы на март будут:

= 3 n = 4, тогда х _март = 0.

Анализ оптимальных вариантов производственной программы показывает, что январский выпуск зависит от длительности планов периода, (см. столбец январь). При возрастании числа месяцев N с 1 до 5, январский выпуск возрастает, но при n = 6 выпуск в январе падает; т.о. удлинение планового периода может вызвать как увеличение, так и уменьшение январского объема производства. Таким же образом испытывают колебания среднемесячные затраты.

Рассмотрим случай N = 5. Здесь уровень запасов возрастает в январе и в феврале, а также в апреле. Другими словами, спрос на май удовлетворяется двумя единицами апрельского выпуска и одной единицей февральского выпуска. При подобных условиях оптимальным оказывается значение уровня запасов как на начало февраля так и апреля.

Рассмотрим параметр «уровень начальных запасов». Данные также берем из сводной таблицы.

Влияние этого параметра на оптимальный выпуск рассматривается на примере январского выпуска.

Таблица 7

Влияние уровня начальных запасов на оптимальный выпуск

Длительность планового периода N	Оптимальный выпуск при	Цена единичного приращения общих затрат, при изменении начального запаса
			С до	С до
	3 или 4

Для N = 1 весь плановый период – 1 месяц, т.е. январь, следовательно, число шагов до конца планового периода n =1, тогда в сводной таблице 4 смотрим столбец n =1 и заполняем первую строку:

Для и n =1 на пересечении находим оптимальный выпуск ;

Для и n =1 на пересечении находим ;

Для и n =1 .

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

Заполним два последних столбца для N = 1:

Цена единичного приращения при изменении от 0 до 1 рассчитывается так:

Для оптимальный выпуск , а затраты ; а для оптимальный выпуск ; а затраты , тогда .

Аналогично рассчитывается цена единичного приращения при изменении от 1 до 2.

Для , а затраты ;

Для и затраты , тогда .

Таким образом, при N = 2, 4 и 6 увеличение начального запаса от 0 до 1 приводит не к сокращению, а к увеличению январского выпуска. А увеличение начального запаса с 1 до 2 приводит к различным результатам. Цена единичного приращения (последние два столбика) существенно зависит от длительности планового периода и от того, является ли приращение первым или вторым.

3. СОДЕРЖАНИЕ КУРСОВОЙ РАБОТЫ

В курсовой работе необходимо разработать оптимальную производственную программу на период N месяцев.

Спрос на продукцию D_t, .

Функция затрат:

То есть, функция затрат представляет собой сумму затрат на производство и хранение.

Выпуск продукции в периоде (месяце) t – x_t.

Уровень (количество) запасов продукции на конец периода t – i_t.

Производственные мощности и складские площади ограничены. Это вызывает ограничения на верхнюю границу значений переменных x_t и i_t.

Уровень запасов на начало всего планового периода – i ₀.

Уровень запасов на конец планового периода – i _кон.

Таким образом, требуется разработать план выпуска продукции по месяцам (т.е., определить x_t) так, чтобы суммарные затраты были минимальны.

Курсовая работа включает в себя следующие разделы:

- Введение, представляющее собой краткий обзор экономико-математических методов и моделей;

- Постановка задачи, которая включает описание исходных данных для конкретного варианта;

- Составление математической модели;

- Нахождение оптимального плана;

- Анализ чувствительности решения;

- Заключение, в котором будут представлены выводы по изменению структуры модели в зависимости от вариации исходных данных;

- Список использованной литературы.

4. ВАРИАНТЫ ЗАДАНИЙ ДЛЯ КУРСОВОЙ РАБОТЫ
№ варианта	Количество периодов N	Спрос Dt	Затраты на хранение единицы продукции h	Функция затрат C (xt)	Запасы на конец планового периода i кон	Ограничения на it	Ограничения на xt
	N = 6	Dt = 3,	h = 1		i кон = 0
	N = 6	D 1 = 4 Dt = 3	h = 2		i кон = 1
	N = 6	Dt = 3	h = 4		i кон = 0
	N = 6	Dt = 3	h = 1		i кон = 1
	N = 6	D 1 = 3 D 2 = 4 Dt = 3	h = 2		i кон = 0
	N = 6	Dt = 3	h = 4		i кон = 1
	N = 6	Dt = 3	h = 1		i кон = 0
	N = 6	D 1 = 2 Dt = 3	h = 2		i кон = 1
	N = 6	D 6 = 4 Dt = 3	h = 4		i кон = 0
	N = 6	Dt = 3	h = 1		i кон = 1
	N = 6	D 1 = 3 D 2 = 4 Dt = 3	h = 2		i кон = 2
	N = 6	D 6 = 4 Dt = 3	h = 4		i кон = 1
	N = 6	D 1 = 2 D 2 = 3 D 3 = 4 Dt = 3	h = 0		i кон = 1
	N = 6	D 1 = 3 D 2 = 3 D 3 = 2 D 4 = 4 D 5 = 3 D 6 = 3	h = 0		i кон = 1
	N = 6	Dt = 3 D 4 = 2 D 5 = 3 D 6 = 4	h = 4		i кон = 1
	N = 6	D 1 = 2 D 5 = 3 D 2 = 3 D 6 = 3 D 3 = 4 D 4 = 3	h = 0		i кон = 0
	N = 6	D 1 = 3 D 2 = 3 D 3 = 2 D 4 = 4 D 5 = 3 D 6 = 3	h = 3		i кон = 1
	N = 6	D 1 = 3 D 2 = 3 D 3 = 3 D 4 = 2 D 5 = 3 D 6 = 4	h = 4		i кон = 2
	N = 6	D 1 = 4 Dt = 3 D 6 = 2	h = 2		i кон = 2
	N = 6	Dt = 3	h = 1		i кон = 2
	N = 6	Dt = 3	h = 4		i кон = 2
	N = 6	Dt = 3	h = 1		i кон = 2
	N = 6	D 1 = 2 Dt = 3	h = 2		i кон = 2
	N = 6	Dt = 3 D 6 = 4	h = 4		i кон = 2
	N = 6	Dt = 3	h = 1		i кон = 2
	N = 6	D 1 = 3 D 2 = 4 Dt = 3	h = 2		i кон = 2
	N = 6	Dt = 3 D 6 = 2	h = 4		i кон = 2
	N = 6	D 1 = 2 D 2 = 3