Оптимизация планирования потребностей ресурсов организации (с затратами на оформление заказа)

    Содержание

    Введение 5

    1 Расчётная часть 6

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

    1.2 Математическая модель 6

    1.3 Описание метода нахождения решения задачи 7

    2 Описательная часть 10

    2.1 Описание алгоритма задачи 10

    2.2 Описание программы MathCAD 13

    2.3 Контрольный пример 15

    2.4 Инструкции пользователя 20

    Заключение 21

    Список  сокращений 22

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

    Приложение  А 24

    Введение

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

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

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

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

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

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

    1    Расчетная часть

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

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

    Дана  информация о количестве этапов, затраты  на оформление заказа K_i, спрос D_i и хранение продукции h_i на каждом этапе i в виде таблицы, подобной таблице 1.

    Таблица 1- примерный вид таблицы данных о задаче

    Задача  управления запасами сводится к вычислению такого управления (значений z_i) системой  S, при котором суммарные затраты, связанные с размещением заказов, закупкой и хранением продукции на протяжении N этапов, минимизируются.

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

    Дадим общее описание модели динамического  программирования.

    Рассматривается управляемая система, которая под  влиянием управления переходит из начального состояния S₁ в конечное состояние S_n. Предположим, что процесс управления системой можно разбить на N шагов. Пусть S₁, S₂, …, S_n, — состояния системы после первого, второго, …, п-го шага.

    Состояние S_k системы после k-го шага (k = 1,2 …,n) характеризуется параметрами , , . Последовательное преобразование системы (по шагам) достигается с помощью некоторых мероприятий , , …, , которые составляют управление системой , где — управление на k-м шаге, переводящее систему из состояния S_k-1 в состояние S_k. Управление на k-ом шаге заключается в выборе значений определенных управляющих переменных

    Предполагаем  впредь, что состояние системы  в конце k-го шага зависит только от предшествующего состояния системы S_k-1 и управления на данном шаге. Обозначим эту зависимость в виде .

    Функции полагаем заданными.

    Варьируя  управление U, получим различную «эффективность» процесса, которую будем оценивать количественно целевой функцией f, зависящей от начального состояния системы и от выбранного управления U:

    .

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

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

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

    1.3 Описание метода решения задачи

    Динамическое  программирование применяется при  оптимизации как детерминированных, так и стохастических процессов.

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

    Задача  управления запасами является частным  случаем задачи динамического программирования. Состоянием системы задачи управления запасами считаются значения переменных: стоимость хранения единицы продукции, переходящей из этапа i в i+1, величина спроса на продукцию в этапе i, затраты на оформление заказа на этапе i, объем запаса на начало этапа i. Управлением U системой S называется совокупность решений (управлений) . Управлением является величина заказа z_i на этапе i. Целевой функцией f является функция расходов на закупку, хранение и оформление заказа, ее нужно минимизировать.

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

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

    Введем  некоторые обозначения:

    N – количество этапов в задаче;

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

    h_i – стоимость хранения единицы продукции, переходящей из этапа i в этап i+1;

    D_i – величина спроса на продукцию на i-ом этапе;

    K_i – затраты на оформление заказа на i-ом этапе;

    x_i– объем запаса на начало этапа i;

    z_i– объем заказа на i-ом этапе.

    Тогда функция производственных затрат для  этапа i будет описана формулой 

    Где - функция предельных производственных затрат при заданном значении .

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

    Для рекуррентного уравнения процедуры  прямой прогонки состояние S_i на этапе i определяется как объем запаса x_i+1 на конец этапа, где . Это неравенство означает, что в предельном случае запас x_i+1 может удовлетворить спрос на всех последующих этапах.

    Целевая функция  – общие затраты на этапах 1,2, …, i при заданной величине запаса на конец этапа i. Требуется найти минимум целевой функции. Тогда рекуррентное уравнение алгоритма прямой прогонки будет записано следующим образом.

    ,

    , .

    2    Описательная часть

    2.1 Описание алгоритма задачи

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

    Составленный  алгоритм MathCAD можно разделить на 5 частей:

1. Раздел ввода информации содержит краткое описание входных данных. Ниже описания расположены переменная x1 (запас ресурсов на начало первого этапа), и таблица переменных каждого этапа. Раздел ввода информации приведен на рисунке 1.

    Рисунок 1 – Раздел ввода информации

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

    x – массив остатков запаса на всех этапах;

    z – массив значений заказа на всех этапах;

    zf – массив значений заказа, при которых целевая функция f принимает минимальное значение;

    f – массив значений целевой функции при принятии разных стратегий управления запасами;

    Раздел  нахождения затрат при принятии разных стратегий управления запасами приведен на рисунке 2.

    Рисунок 2 – Раздел нахождения затрат при принятии разных стратегий управления запасами

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

    Рисунок 3 – Раздел анализа

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

    Рисунок 4 - Раздел применения оптимального управления и подсчета значения целевой функции

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

    Рисунок 5 – Раздел выходных данных

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

    2.2 Описание программы MathCAD

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

    При запуске MathCAD открывается окно приложения. В строке заголовка следует имя рабочего документа. После строки заголовка располагается панель меню. Она содержит 9 пунктов (file, edit, view, format, tools, symbolic, window, help).

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

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

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

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

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

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

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

    Существует  два способа вставки встроенной функции в рабочий документ.

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

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

    В MathCAD предусмотрены широкие возможности для работы с матрицами и векторами. Два этих объекта реализуются в виде массивов. Каждый массив имеет размерность. В этом смысле матрица является массивом размерностью два, а вектор – один. Для создания массива вызывают команду Insert/Matrix.  Альтернативный вариант – воспользоваться палитрой Matrix.

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

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

    Чтобы в MathCAD вычислить определенный интеграл, существует специальный оператор, который выглядит также, как стандартное математическое обозначение для определенного интеграла. Вставка существующего оператора осуществляется нажатием комбинации <Shift>+<7>. Можно воспользоваться пиктограммой на палитре Calculus.

    Очень просто создаются двумерные графики. Для вставки в рабочий документ двумерного графика вызывают команду  Insert/Graph/X-YPlot.

    Также MathCAD предоставляет возможность строить графики в полярной системе координат. В таком случае координата точки задается с помощью двух параметров: расстояние от точки до начала координат и угла между горизонтальной координатной осью и линией, соединяющей точку с началом координат.

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

    Главная проблема решения дифференциальных уравнений в MathCAD связана с отсутствием универсального способа решения.

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

    2.3 Контрольный пример

    Дана  задача:

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

    Таблица 2 – Данные о спросе, затратах на оформление заказа и стоимости хранения товара на каждом этапе

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

                                                          (1)

                             (2)

    Объем запаса, переходящего из этапа i в этап i+1 высчитывается по формуле:

    . Значение  в предельном случае может удовлетворить спрос на всех последующих этапах.

    Этап 1. Спрос на этапе 1 равен 10. Вычисляем значения целевой функции по формуле (1). Вычисленные данные отражены в таблице 3.

    Таблица 3 – Вычисления  на этапе 1