Управления запасами при помощи динамического программирования

Размещено на http://www.allbest.ru/

Содержание

Введение

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

1.1 Формализация задачи

1.2 Методы, используемые для решение задачи

2. Стратегия и алгоритм задачи

3. Решение задачи

3.1 Программа реализующая алгоритм задачи

3.2 Полученное решение задачи

3.3 Интерпретация полученных результатов

Выводы

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

Введение

В данной курсовой работе будет рассмотрена задача управления запасами при помощи динамического программирования. Задача управления запасами - это задача о поддержании баланса производства и сбыта продукции предприятия, минимизирующего расходы предприятия на производство и хранение продукции. Данная задача возникает, когда экономический объект не может работать без производственных или товарных запасов, поскольку их отсутствие приводит к простоям, штрафам, потери клиентов, катастрофам. Задачи управления запасами позволяют ответить на следующие актуальные вопросы: каковы оптимальные величины объема заказа на закупку или производство товара, периода поставок заказов, величины запаса, моментов подачи заказа товара, позволяющие минимизировать общие затраты на покупку, производство, доставку, хранение товара; что выгоднее производить товар или закупать его;
выгодно ли пользоваться скидками на покупку товара; В условиях рыночной экономики становится актуальным вопрос организации оперативного контроля и управления запасами материальных ресурсов на предприятии. Решению данной проблемы в определенной степени способствует внедрение автоматизированных систем управления предприятиями, которые позволяют наладить учет движения материальных ресурсов (поступление, расход, ежесуточные остатки). Результатом решения задачи по оперативному контролю является получение ежедневной (недельной, декадной, месячной или иной периодичности) информации о фактическом наличии запасов на складах предприятия и степени их соответствия установленным нормам. Это позволяет осуществлять непрерывный контроль за их величиной, своевременно и оперативно выявлять образование излишних остатков или дефицита по отдельным позициям, который может нарушить организацию бесперебойности функционирования потребителя. Запасы, являясь основным ресурсом торговых фирм, скрывают в себе большие резервы повышения рентабельности этого бизнеса. Наиболее важным в деле использования этих резервов является системный и комплексный подход. Что и будет применено в данной курсовой работе.

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

1.1 Формализация задачи

Для деятельности любой организации необходимы определенные запасы. Если их не будет, то при малейшем нарушении сбыта вся деятельность остановится. Хранить же слишком много запасов экономически невыгодно. Нахождению баланса между этими двумя крайностями посвящена задача управления запасами. Задача состоит в следующем: Необходимо составить план выпуска некоторого вида изделий на период, состоящий из N отрезков. Предполагается, что для каждого из этих отрезков имеется точный прогноз спроса на выпускаемую продукцию. Для разных отрезков спрос неодинаков. Причём, продукция, изготовляемая в течение отрезка времени t , может быть использована для полного или частичного покрытия спроса в течение этого отрезка. Кроме того, размеры изготовляемых партий продукции влияют на экономические показатели производства. В связи с этим бывает целесообразно изготовлять в течение некоторого периода объём продукции, превышающий его спрос в пределах этого периода и хранить эти излишки до удовлетворения последующего спроса. Однако, хранение запасов связано с затратами (плата за складские помещения, страховые взносы и расходы по содержанию запасов и т.п.). Цель предприятия - разработать такую программу, при которой общая сумма затрат на производство и содержание запасов минимизируется при условии полного и своевременного удовлетворения спроса на продукцию. Для обеспечения непрерывного и эффективного функционирования практически любой организации необходимо создание запасов, например, в производственном процессе, торговле, медицинском обслуживании и т.д. В зависимости от ситуации под запасами могут подразумеваться: готовая продукция, сырье, полуфабрикаты, станки, инструмент, транспортные средства, наличные деньги и др. Неверный расчет необходимых запасов может привести как к незначительному ущербу (потеря части дохода от дефицита товара), так и к катастрофическим последствиям (при ошибочной оценке запасов топлива на самолете). К экономическому ущербу приводит как чрезмерное наличие запасов, так и их недостаточность. Так, если некоторая компания имеет товарные запасы, то капитал, овеществленный в этих товарах, замораживается. Этот капитал, который нельзя использовать, представляет для компании потерянную стоимость в форме невыплаченных процентов или неиспользуемых возможностей инвестирования. Кроме того, запасы, особенно скоропортящиеся продукты, требуют создания специальных условий для хранения. Для этого необходимо выделить определенные площади, нанять персонал, застраховать запасы. Все это влечет определенные издержки. С другой стороны, чем меньше уровень запаса, тем больше вероятность возникновения дефицита, что может принести убытки вследствие потери клиентов, остановки производственного процесса и т.д. Кроме того, при малом уровне запасов приходится часто поставлять новые партии товара, что приводит к большим затратам на доставку заказов. Отсюда следует важность разработки и использования математических моделей, позволяющих найти оптимальный уровень запасов, минимизирующих сумму всех описанных видов издержек.

В данной курсовой работе будет рассмотрена и решена задача управления запасами на наглядном примере. Существует предприятие, которое может производить ежемесячно до 4-х единиц некоторой продукции. Затраты на производство xj единиц продукции в месяце j указаны в следующей таблице 1.1. Каждый месяц предприятие должно отгрузить 2 единицы продукции своим потребителям. Продукцию можно хранить на складах. Затраты на хранение 1 единицы продукции составляют 1 тысячу гривен. Оплата за хранение производится в конце месяца j. Склады могут вместить до 4 единиц продукции. Учитывая, что в начале на складах было 2 единицы продукции, определить оптимальный план производства на 4 месяца.

Таблица 1.1.- Затраты на производство xj единиц продукции.

xj	0	1	2	3	4	штук продукции.
C(xj)	0	7	9	11	113	млн.грн.

Введем обозначения для переменных и констант задачи.

n - количество месяцев планового отрезка,

- выпуск продукции в месяце j, j = 1, . . . , n (управление),

- запасы в конце месяца j, или в начале месяца j + 1 (состояние),

- спрос в месяце j, заданная величина.

Переменные xj и yj связаны следующим балансовым соотношением

=, j=1…n (1.1 )

запасы yj в конце текущего j-го месяца равны запасам в предыдущем месяце плюс xj произведенных в текущем месяце j изделийи минус dj проданных изделий. В числовом примере, который будет использоваться, n=4. Так как будет планироваться на 4 месяца: январь, февраль, март и апрель.

dj = 2, j = 1, . . . , n, xj , yj ? 0 : 4 (1.2 )

Математическая модель задачи выглядит следующим образом.

Найти оптимальный план производства x1 , . . . , xn , минимизирующий затраты.

(1.3 )

1.2 Методы, используемые для решения задачи

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

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

Рисунок 1.1 - Процесс управления системой

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

В задачах динамического программирования критерий эффективности называется доходом. Данные процессы управляемые, и от правильного выбора управления зависит величина дохода. Показатель эффективности задачи в целом обозначим через W, а показатели эффективности на отдельных шагах--через цi, i=1..m. Если W обладает свойством аддитивности, т.е.

W=? цi , (1.4)

Переменная Xi, от которой зависят выигрыши на i-м шаге и, следовательно, выигрыш в целом, называется шаговым управлением, i=1..m.

Управлением процесса в целом (x) называется последовательность шаговых управлений (вектор управлений) x=(x1, x2,…, xi,…, xm).

Оптимальное управление x--это значение управления x, при котором значение W(x*) является максимальным (или минимальным, если требуется уменьшить проигрыш).

W*=W(x*)=max{W(x)}, x € X, (1.5)

где X--область допустимых управлений.

Оптимальное управление x* определяется последовательностью оптимальных шаговых управлений x*=(x2*, x2*,…, xi*,…, xm*). В основе метода динамического программирования лежит принцип оптимальности Беллмана, формулирующийся следующим образом: управление на каждом шаге надо выбрать так, чтобы оптимальной была сумма выигрышей на всех оставшихся до конца процесса шагах, включая выигрыш на данном шаге. Объясняется это правило так: при решении задачи динамического программирования на каждом шаге выбирается управление, которое должно привести к оптимальному выигрышу. Если считать все шаги независимыми друг от друга, то оптимальным шаговым управлением будет то управление, которое приносит максимальный выигрыш именно на данном шаге. В многошаговых процессах все шаги зависят друг от друга, и, следовательно, управление на каждом конкретном шаге надо выбирать с учетом его будущих воздействий на этот процесс.

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

1. Возможные исходы предыдущего шага;

2. Влияние управления на все оставшиеся до конца процесса шаги.

В задачах динамического программирования первый пункт учитывают, делая на каждом шаге условные предположения о возможных вариантах окончания предыдущего шага и приводя для каждого из вариантов условную оптимизацию. Выполнение второго пункта обеспечивается тем, что в задачах динамического программирования условная оптимизация проводится от конца процесса к началу. Сперва оптимизируется последний m-й шаг, на котором не надо учитывать возможные воздействия выбранного управления xm на все последующие шаги, так как эти шаги просто отсутствуют. Делая предположения об условиях окончания (m-1)- го шага, делая предположения об исходах окончания (m-2)-го шага и определяя условное оптимальное управление на (m-1)-м шаге, приносящее оптимальный выигрыш на двух последних шагах--(m-1)-м и m-м. Так же действуют на всех остальных шагах до первого. На первом шаге, как правило, не надо делать условных предположений, так как состояние системы перед первым шагом обычно известно. Для этого состояния выбирают оптимальное шаговое управление, обеспечивающее оптимальный выигрыш на первом и всех последующих шагах. Это управление является безусловным оптимальным управлением на первом шаге и, зная его, определяются оптимальное значение выигрыша и безусловные оптимальные управления на всех шагах. Понятия этапа(шага), состояния, управления, дохода(выигрыша) целиком зависит от предметной ориентации исследуемой системы. Для организационно-экономической системы эти понятия имеют вид:

s--состояние процесса;

Si--множество возможных состояний процесса перед i-м шагом;

Wi--выигрыш с i-го шага до конца процесса, i=1..m.

Можно определить следующие основные этапы составления математической модели задачи динамического программирования. Разбиение задачи на шаги (этапы). Шаг не должен быть слишком мелким, чтобы не проводить лишних расчетов и не должен быть слишком большим, усложняющим процесс шаговой оптимизации[5]. Выбор переменных, характеризующих состояние s моделируемого процесса перед каждым шагом, и выявление налагаемых на них ограничений. В качестве таких переменных следует брать факторы, представляющие интерес для исследователя, например годовую прибыль при планировании деятельности предприятия. Определение множества шаговых управлений xi, i=1..m и налагаемых на них ограничений, т.е. области допустимых управлений X. Определение выигрыша ц(s, xi), который принесет на i-м шаге управление xi, если система перед этим находилась в состоянии s.

Определение состояния s', в которое переходит система из состояния s под влиянием управления xi : s'=fi(s, xi,), где fi--функция перехода на i-м шаге из состояния s в состояние s'. Составление уравнения, определяющего условный оптимальный выигрыш на последнем шаге, для состояния s моделируемого процесса

Wm(S)=max{цm(s, xm)}. (1.6)

Составление основного функционального уравнения динамического программирования, определяющего условный оптимальный выигрыш для данного состояния s с i-го шага и до конца процесса через уже известный оптимальный выигрыш с (i+1)-го шага и до конца:

Wi(S)=max{цi(s, xi)+Wi=1(fi(s, xi))}. (1.7)

В уравнении (1.7) в уже известную функцию Wi+1(s), характеризующую условный оптимальный выигрыш с (i+1)-го шага до конца процесса, вместо состояния s подставлено новое состояние s'=fi(s, xi), в которое система переходит на i-м шаге под влиянием управления xi.

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

1) Определение множества возможных состояний Sm для последнего шага.

2)Проведение условной оптимизации для каждого состояния s, принадлежащей Sm на последнем m-м шаге по формуле (1.6) и определение условного оптимального управления x(s), s принадлежит Sm.

3) Определение множества возможных состояний Si для i-го шага, i=2, 3,…m-1.

4) Проведение условной оптимизации для i-го шага, i=2, 3,…m-1 для каждого состояния s, принадлежащей Si,, по формуле (1.7) и определение условного оптимального управления xi(s), s принадлежит Si, i=2, 3,…m-1.

5) Определение начального состояния системы s1, оптимального выигрыша W1(S1) и оптимального управления x1(S1) по формуле (1.7) при i=1. Это есть оптимальный выигрыш для всей задачи W*=W1(x1*).

6) Проведение безусловной оптимизации управления. Для проведения безусловной оптимизации необходимо найденное на первом шаге оптимальное управление x1*=x1(s1) подставить в формулу (1.5) и определить следующее состояние системы s2=f2(s1, x1). Для измененного состояния найти оптимальное управление x2*=x2(s2), подставить в формулу (1.4) и т.д. Для i-го состояния si найти si+1=fi+1(si,xi*) и x*i+1(si+1) и т.д.

2. Стратегия и алгоритм решения задачи

запас задача уравнение решение

В данной курсовой работе был применен принцип оптимальности и уравнения Беллмана. Метод динамического программирования состоит в том, что оптимальное управление строится постепенно, шаг за шагом. На каждом шаге оптимизируется управление только этого шага. Вместе с тем на каждом шаге управление выбирается с учетом последствий, так как управление, оптимизирующее целевую функцию только для данного шага, может привести к неоптимальному эффекту всего процесса[2]. Управление на каждом шаге должно быть оптимальным с точки зрения процесса в целом. Оптимальное управление обладает таким свойством, что каково бы ни было начальное состояние на любом шаге и управление, выбранное на этом шаге, последующие управления должны выбираться оптимальными относительно состояния, к которому придет система в конце данного шага. Использование этого принципа гарантирует, что управление, выбранное на любом шаге, является не локально лучшим, а лучшим с точки зрения процесса в целом. Управление запасами состоит в определении, размеров необходимого выпуска продукции для удовлетворения заданного спроса. Цель -- минимизация суммарных затрат на хранение и пополнение запасов [3]. Если в задаче исходные данные определены однозначно, то задачи называются детерминированными; если же хотя бы часть данных носит случайный характер и заданы распределения вероятностей, то соответствующие задачи называются стохастическими.. Рассмотрим модель задачи управления запасами при заданном расходе. Управление в этих задачах будет сводиться к пополнению. Планируемый период разделен на n промежутков времени (дни, месяцы, кварталы и т. д.), в которых задан расход , производимый в конце каждого из промежутков. Известны начальный уровень запасов и зависимость суммарных затрат на хранение и пополнение запасов в данном периоде от среднего уровня хранимых запасов и их пополнения. Требуется определить размеры пополнения запасов в каждом промежутке времени для удовлетворения заданного расхода из условия минимизации суммарных затрат за весь планируемый период времени. Составим математическую модель задачи. Введем следующие обозначения:

N - число календарных этапов из которых состоит плановый период;

При этом каждый j-й этап (j=1,N) характеризуется параметрами:

y_j-1 - запас, оставшийся после окончания j-1-го этапа;

х_j - объем производства предприятия на j-м этапе;

d_j - величина спроса на продукцию предприятия на j-м этапе;

x_max - максимальный объем производства на одном этапе;

y_max - максимальный объем запасов на одном этапе;

С_j(x_j,y_j-1) - затраты на j-м этапе функционирования, связанные с выпуском х_j и хранением y_j-1 запасов.

Тогда критерий оптимизации имеет вид:

_N

F=? С_j(x_j,y_j-1) min (2.8)

^j=1

при ограничениях:

1) Ограничение на удовлетворение спроса на каждом этапе:

d_j y_j-1 + x_j , j=1,N ; (2.9)

2) Установление объема запаса в конце j-го периода:

y_j = y_j-1 + x_j - d_j , j=1,N , x_j = 0,x_max , y_j = 0,y_max ; (2.10)

Обозначение основных компонентов:

1. Этап - календарный период деятельности предприятия, j=1,N;

2. Состояние - объем запасов y_j в конце n периода;

3. Управление - планируемый объем производства x_j на j-м периоде;

4. Локальный доход - затраты на j-м этапе, связанные с хранением запасов и производством новой продукции С_j(x_j,y_j-1);

5. Оператор перехода - устанавливает связь между объемом запасов в конце j- 1-го и j-го этапов: y_j = y_j-1 + x_j - d_j .

Введем функцию:

f_j(y_j) = min? С_j(x_j,y_j-1) (2.11) .

Функциональное уравнение Беллмана для такой задачи:

f_j(y_n) = min(f_j(y_j-1) + С_j(x_j,y_j-1)). (2.12)

Если С_j(x_j,y_j-1) = c_j(x_j) + h*y_j-1 (2.13),

Где c_j(x_j) - затраты на производство продукции на j-ом этапе в x_j объеме;

h*y_j-1 - затраты на хранение продукции на j-ом этапе в объеме y₀.

Известно c₀(x₀) - затраты на формирование начального запаса.

Тогда на шаге 1 принятия решения уравнение Беллмана (2.12) примет вид:

f₁(y₁) = min(f₁(y₀) + С₁(x₁,y₀)) = min(f₁(y₀) + c₀(x₀) + h*y₀) (2.14)

все переменные в уравнении известны, а значит его можно решить.

На шаге j уравнение (2.12) имеет вид:

f_j(y_j) = min(f_j(y_j-1) + c_j(x) + h*y_j-1) (2.15)

Для получения оптимального решения необходимо разработать алгоритм решения уравнения Беллмана на произвольном шаге принятия решения. Для этого целесообразно воспользоваться 2 таблицами. Заполнение таблицы 1 проводится так: столбцы - величина запаса с предыдущего шага, строки - объем производства на текущем этапе. Число столбцов ограничивается y_max, а число строк x_max. Клетка таблицы делится на 2 части. В одной части записываются значения состояния в конце текущего этапа

(y_j = y_j-1 + x_j - d_j ). (2.16)

Если y_j < 0 ,то это недопустимое состояние, клетка вычеркивается из рассмотрения. Во второй части клетки записывается значение функции

f_j(y_j) = c_j-1(x_j-1) + c_j(x_j) + h*y_j-1 (2.17)

Среди допустимых клеток находятся клетки с одинаковыми значениями состояний, и выбирается клетка, для которой функция f_j(y_j) минимальна, для нее фиксируется оптимальный объем производства. Эти результаты записываются в таблицу 2. Такие шаги повторяются N раз.

Для нахождения оптимальных объемов производства x_j и оптимальных уровней запасов y_j производится решение задачи в обратном порядке. На последнем этапе (j = N) из таблицы 2 выбирается x_j и y_j , соответствующие оптимальной (минимальной) функции затрат f_j(y_j). На этапах j < N из таблицы 2 выбираются строки для которых x_j и y_j такие, что бы |d_j - x_j+1 | = y_j . Обратное решение задачи производится до j= 1 этапа.

3. Решение задачи

Для решения этой задачи следует записать уравнение Беллмана. Для этого надо сложить затраты в месяце j и затраты на временном отрезке j+1, . . . , n, а затем минимизировать суммарные затраты выбором xj :

(3.18 )

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

Этап 4: апрель.

f4 (y3 ) = {C(x4 ) + 1 · (y3 + x4 ? 2)} (3.19 )

x40:4

Таблица 3.2 Управление запасами, этап 4

y3	Оптимальное решение
	f4(3)
_0	__9	_2
1	7	1
2	0	0

В конце апреля запасы на складе должны быть равны нулю y3 +x4 ? 2 = y4; y4 = 0, отсюда y3 + x4 = 2 и все возможные значения y3 и x4 в таблице 3.2 перечислены. Таких пар всего три. Для каждого возможного значения (y3 , x4) вычислена целевая функция C(x4).

Этап 3: март, апрель.

f3 (y2 ) = min {C(x3 ) + 1 · (y2 + x3 ? 2) + f4 (y2 + x3 ? 2)}.(3.20 )

x3 ?0:4

Таблица 3.3 Управление запасами, этап 3

y2	C(x3 ) + 1 · (y2 + x3 ? 2) + f4 (y2 + x3 ? 2)	Оптим. решение
	x3=0	x3=1	x3=2	x3=3	x3=4	f3(y2)	x*3
0	_	_	9+0+9=18	11+1+7=19	13+2+0=15	15	4
1	_	7+0+9=16	9+1+7=17	11+2+0=13	_	13	3 33
2_	0+0+9=9	7+1+7=15	9+2+0=11	_	_	9_	00_
3	0+1+7=8	7+2+0=9	_	_	_	8	00
4	0+2+0=2	_	_	_	_	2	00

Для этапа 3 (март, апрель) из y3 ? 0 : 4, y3 = y2 + x3 ? 2 следует 0 ? y2 + x3 ? 2 ? 4. Левое ограничение 0 + 2 ? y2 + x3 дает запрещенные варианты в левой верхней части таблицы 3.3, правое ограничение y2 + x3 ? 4 + 2 соответствует черточкам в правой нижней части таблицы. В этой таблице уже перечислены все пять возможных значений состояния y2 ? 0 : 4

Этап 2: февраль, март, апрель.

f2 (y1 ) = min {C(x2 ) + 1 · (y1 + x2 ? 2) + f3 (y1 + x2 ? 2)}.(3.21)

x2 ?0:4

Таблица 3.4. Управление запасами, этап 2

yy1	C(x2 ) + 1 · (y1 + x2 ? 2) + f3 (y1 + x2 ? 2)	Оптим. решение
	x2=0	x2=1	x2=2	x2=3	x2=4	f2(y1)	x*2
_0	_	_	9+0+15=24	11+1+13=25	13+2+9=24	_24	2,4_
1	_	7+0+15=22	9+1+13=23	11+2+9=22	13+3+8=24	22	1,3
2	0+0+15=15	7+1+13=21	9+2+9=20	11+3+8=22	13+4+2=19	15	0
3	0+1+13=14	7+2+9=18	9+3+8=20	11+4+2=17	_	14	0
4	0+2+9=11	7+3+8=18	9+4+2=15	_	_	11	0

Нахождение оптимального решения, начиная с последнего этапа 1.

y0 = 2 из условий задачи, поэтому из таблицы 3.5 следует, что =0, y1 = y0 + ? 2 = 0. В таблице этапа 2 в строке y1 = 0 видно два оптимальных решения. Нужно рассмотреть сначала решение = 4. Это 2 решение подчеркнуто. Из уравнения y2 = y1 + ? 2 находится y2= 0+4?2; y2 = 2.

Этап 1: январь, февраль, март, апрель.

f1 (y0 ) = min {C(x1 ) + 1 · (y0 + x1 ? 2) + f2 (y0 + x1 ? 2)}. (3.22 )

x1 ?0:4

Таблица 3.5. Управление запасами, этап 1

y0	C(x1 ) + 1 · (y0 + x1 ? 2) + f2 (y0 + x1 ? 2)	Оптим. решение
	x1=0	x1=1	x1=2	x1=3	x1=4	f1(y0)	xx*1
00	_	_	9+0+24=33	11+1+22=34	13+2+15=30	30	44
01	_	7+0+24=31	9+1+22=32	11+2+15=28	13+3+14=30	28	3 3
_	0+0+24=24	7+1+22=30	9+2+15=26	11+3+14=28	13+4+11=28	24_	0 0_
3	0+1+22=23	7+2+15=24	9+3+14=26	11+4+11=26	_	23	0 0
4	0+2+15=17	7+3+14=24	9+4+11=24	_	_	17	0 0

Переход к таблице этапа 3 к строчке y2 = 2. Понятно, что соответствующая компонента решения x? = 0 и в таблице этапа 4 надо смотреть на строку y3 = y2 + 0 ? 2 = 0. Эта строка y2 = 0 дает последнюю компоненту решения = 2. Из этого следует окончательный ответ.

x = (0, 4, 0, 2), f1 (2) = 24.

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

3.1 Программа реализующая алгоритм задачи

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

format compact, clc

% x: 1 2 3 4 5

%Задаем свои условия задачи

c1 = [0 7 9 11 13]; % Затраты на пр-во x-1 ед. продукции

x9 = length(c1) - 1; % Максимум производства в штуках ; (длина массива c1) - 1

y0 = 2; % Запасы на складе в конце декабря

d = 2; % Отгрузка потребителям

y9 = 4; % Максимум запасов на складе в штуках

n = 4; % Количество месяцев в плановом периоде

s9 = y9 + 1; % Макс. количество состояний

u9 = x9 + 1; % Макс. количество управлений

F = inf * ones(y9 +1, n); % формирует массив единиц размера y9 +1 на n

X = F;

% Начальные вычисления для этапа n.

for s = 1 : s9 %входим в цикл, который выполняется с шага s=1 до шага s9

u = d -s +2;

if u >= 1 %если u больше или равно 1

F(s, n) = c1(u);

X(s, n) = u;

end %конец выполнения тела условия

end % закончили цикл

% Печать для этапа n

Tire = setstr(ones(1, 3*6 +2) * '='); %Устанавливаем объекты для отображения

Kepka = [' Y', int2str(n -1), ' F(:,j) Y(:,j)'];

s7 = sum(finite(F(:, n)));

disp(Tire) %Отображение объекта

disp(Kepka)

disp(Tire)

disp([(0: s7 -1)', F(1: s7, n), X(1: s7, n)-1])

disp(' ')

% Произвольный j-ый этап.

Fsu = inf * ones(s9, u9);

for j = n -1 : -1 : 1 %Начинаем убывающий цикл от n-1 до 1

for s = 1 : s9 % s = Yj_1 +1 от 1 до s9 , внешний цикл

for u = 1 : u9 % u = Xj +1 от 1 до u9 внутренний цикл

s1 = (s -1) + (u -1) -d +1;

if 1 <= s1 & s1 <= n +1 %если 1 меньше или равно s1 и s1 меньше или равно n+1, то:

Fsu(s, u) = c1(u) + (s1 -1) + F(s1, j+1); %тело условия

End %конец тела условия

end % конец тела внутреннего цикла

end % конец тела внешнего цикла

[fs, index] = min(Fsu');

% Обработка таблиц Fsu F(состояние, управление)

F(:, j) = fs';

X(:, j) = index';

% Печать таблиц

Tire = setstr(ones(1, (u9 +3) *6 + 3) *'='); %Устанавливаем объекты для отображения

Kepka = [' Y', int2str(j -1), ' '];

Frmt=['X', int2str(j), '=%-3.0f'];

for i = 0: u9 -1% цикл от 0 до u9

Kepka = [Kepka, sprintf(Frmt,i)];

end

Kepka = [Kepka, 'F(:,j) Y(:,j)'];

disp(Tire) %отображение объекта

disp(Kepka)

disp(Tire)

disp([(0: s9 -1)', Fsu, F(:,j), X(:,j)-1 ])

disp(' ')

end %конец убывающего цикла j

% печать результатов

% ==================

x_opt = zeros(1, n); %формирование массива нулей

s = y0 + 1;

for j = 1 : n %цикл от 1 до n

x_opt(j) = X(s,j);

s = (s -1) +X(s,j) -d ;

end % for j

x_opt = x_opt -1

f_opt = F(y0 +1, 1)

ZapasD

====================

Y3 F(:,j) Y(:,j)

====================

0 9 2

1 7 1

2 0 0

===================================================

Y2 X3=0 X3=1 X3=2 X3=3 X3=4 F(:,j) Y(:,j)

===================================================

0 Inf Inf 18 19 15 15 4

1 Inf 16 17 13 Inf 13 3

2 9 15 11 Inf Inf 9 0

3 8 9 Inf Inf Inf 8 0

4 2 Inf Inf Inf Inf 2 0

===================================================

Y1 X2=0 X2=1 X2=2 X2=3 X2=4 F(:,j) Y(:,j)

===================================================

0 Inf Inf 24 25 24 24 2

1 Inf 22 23 22 24 22 1

2 15 21 20 22 19 15 0

3 14 18 20 17 Inf 14 0

4 11 18 15 Inf Inf 11 0

===================================================

Y0 X1=0 X1=1 X1=2 X1=3 X1=4 F(:,j) Y(:,j)

===================================================

0 Inf Inf 33 34 30 30 4

1 Inf 31 32 28 30 28 3

2 24 30 26 28 28 24 0

3 23 24 26 26 Inf 23 0

4 17 24 24 Inf Inf 17 0

x_opt =

0 2 4 0

f_opt =

24

type ZapasP

format compact, clc

% x: 1 2 3 4 5

c1 = [0 7 9 11 13]; % Затраты на пр-во x-1 ед. продукции

x9 = length(c1) - 1; % Максимум производства в штуках

y0 = 2; % Запасы на складе в конце декабря

y9 = 4; % Максимум запасов на складе в штуках

k = 1; % Плата за единицу хранениЯ на складе

d = 2; % Отгрузка потребителям

n = 4; % Количество месяцев в плановом периоде

s9 = y9 + 1; % Макс. количество состояний

u9 = x9 + 1; % Макс. количество управлений

x = zeros(1, n);

f_opt = inf;

x_opt = x;

j = n;

while 1

if x(j) <= x9

y(1) = y0 + x(1) - d;

for j = 2 : n

y(j) = y(j-1) + x(j) - d;

end % for

if 0 <= min(y) & max(y) <= y9

f = 0;

for j = 1:n

f = f + c1(x(j) +1) + k * y(j);

end

if f_opt > f

f_opt = f

x_opt = x

y_opt = y;

elseif f_opt == f

f_opt = f

x_opt = [x_opt; x ]

y_opt = [y_opt; y ];

end

end % if

j = n;

else

x(j) = 0;

j = j - 1;

if j <= 0.0001 %если j меньше или равно 0.0001, то

break %прервать цикл

end % конец тела условия

end % конец тела условия

x(j) = x(j) + 1;

end

disp('========= Ответ: =========')

f_opt, x_opt, y_opt

ZapasP

f_opt =

27

x_opt =

0 2 2 2

f_opt =

24

x_opt =

0 2 4 0

f_opt =

24

x_opt =

0 2 4 0

0 4 0 2

========= Ответ: =========

f_opt =

24

x_opt =

0 2 4 0

0 4 0 2

y_opt =

0 0 2 0

0 2 0 0

diary off

3.2 Получение решения задачи

3.3 Интерпретация полученных результатов

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

f1(2)=24

x*=(0,4,0,2)

y*=(0,2,0,0)

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

Выводы

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

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

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

1.Катренко А.В. Дослідження операцій: Підручник / За наук.ред. В.В. Пасічника. - Львів: «Магнолія 2006», 2007.

2.Зайченко Ю.П. Исследование операций.- Киев: Вища школа, 1975.

3.Гермейер Ю.Б. Введение в теорию исследования операций.-М.: Наука, 1971.

4.Кини Р.Л., Райфа Х. Принятие решений при многих критериях: предпочтения и замещения. Под. ред. И.Ф. Шахнова.-М.: Радио и связь,1981.-560 с.

5.Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах. - М.: Высшая школа, 2005 г.

Размещено на Allbest.ru