Задача замены оборудования реферат

Обновлено: 05.07.2024

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

Содержание

Введение
3
Постановка задачи и описание модели
4
Контрольный пример
6
Разработка алгоритма

Разработка блок схем

Оформление пояснительной записки

Вложенные файлы: 1 файл

курсовик.doc

Постановка задачи и описание модели

Разработка блок схем

Оформление пояснительной записки

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

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

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

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

Переход системы S из одного состояния в другое за 1 год в зависимости от принятого решения можно изобразить графически (рис. 1).

Введем в рассмотрение функцию – величину суммарного дохода (прибыли) за последние n лет планового периода при условии, что в начале этого периода из n лет имеется машина возраста t.

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

Введем условные обозначения:

Возраст машины: t = 0, 1, 2, … (t = 0 – соответствует использованию новой машины, t = 1 – соответствует использованию машины возраста 1 год и так далее);

Стоимость продукции, производимой за 1 год на машине возраста t;

Эксплутационные затраты за 1 год на машину возраста t;

Остаточная стоимость машины возраста t;

Текущее время в плановом периоде;

Цена новой машины в году t;

Начальный возраст машины;

Длина планового периода.

Предположим, что к началу последнего года планового периода n = 1 у нас имеется машина возраста t. В нашем распоряжении две возможности. Рассмотрим их.

Возможность первая: сохранить машину и, следовательно, получить за последний год доход

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

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

В случае замены машины аналогичной имеем:

Для принятия решения необходимо вычислить функцию Беллмана, которая имеет вид:

        1. N – длина планового периода;
        2. Z(N) – стоимость продукции, производимой в t – м году на машине возраста t;
        3. U(N) – эксплуатационные затраты за один год на машину возраста t;
        4. S(N) – остаточная стоимость машины возраста t;
        5. P(N) – цена новой машины в t-м году.
              1. проверка корректности входных данных
                1. все входные данные не должны быть отрицательными
                2. Z(N) – строго убывает
                3. U(N) – строго возрастает
                  1. таблица решения(матрица f), где черным цветом обозначена политика сохранения машины и красным – замена.

                  Save = f(1, t) + f(i, t+1) – промежуточный результат, характерезующая сохранение оборудования;

                  Zam = s(t) – p(t) +f(1,0)+f(i,1) – промежуточный результат, характерезующая замену оборудования.

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

                  Содержание

                  1. Введение………………………………………………………………. стр.3
                  2.Динамическое программирование……………………………………. стр.4
                  2.1. Целочисленное программирование…………………………………. стр.5
                  2.2. Идеи и алгоритм решения задач динамического программирования.стр.6
                  2.3. Достоинства динамического программирования……………. стр.11
                  3. Задача о замене оборудования. Постановка задачи в общем виде……стр.12
                  3.1.Задача 1…………………………………………………………………..стр.16
                  3.2.Задача 2…………………………………………………………………..стр.19
                  3.3. Задача 3………………………………………………………………. стр.23
                  3.4. Задача 4………………………………………………………………….стр.26
                  4. Заключение………………………………………………………………..стр.29
                  5. Список литературы……………………………………………………….стр.31

                  Прикрепленные файлы: 1 файл

                  Динамическое программмирование. Задача о замене оборудования..doc

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

                  Подзадачи решаются делением их на подзадачи ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти n!, то тривиальной задачей будет 1! = 1 (или 0! = 1). 3

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

                  1. Описать строение оптимальных решений.
                  2. Выписать рекуррентное соотношение, связывающие оптимальные значения параметра для подзадач.
                  3. Двигаясь снизу вверх, вычислить оптимальное значение параметра для подзадач.
                  4. Пользуясь полученной информацией, построить оптимальное решение.

                  Для решения задач оптимизации существует специальная теория, большая заслуга в ее создании принадлежит Р. Беллману, в общем виде она достаточна сложна. 4

                  Метод динамического программирования может применяться только для определенного класса задач. Эти задачи должны удовлетворять таким требованиям:

                  1. Задача оптимизации интерпретируется как n-шаговый процесс управления.
                  2. Целевая функция равна сумме целевых функций каждого шага.
                  3. Выбор управления на i-м шаге зависит только о состояния системы к этому шаге, не влияет на предшествующие шаги (нет обратной связи).
                  4. Состояние после i-го шага управления зависит только от предшествующего состояния управления (отсутствие последействия).
                  5. На каждом шаге управление зависит от конечного числа управляющих переменных, а состояние от конечного числа параметров.

                  В основе решения всех задач динамического программирования лежит "принцип оптимальности" Беллмана, который выглядит следующим образом:
                  Каково бы ни было состояние системы S в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный.
                  Этот принцип впервые был сформулирован Р. Беллманом в 1953 г. Им же четко были сформулированы и условия, при которых принцип верен. Основное требование - процесс управления должен быть без обратной связи, т.е. управление на данном шаге не должно оказывать влияния на предшествующие шаги.

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

                  2.3. Достоинства динамического программирования:

                  1. Идея и метод динамического программирования наиболее приспособлены к дискретным задачам, каковыми являются задачи из экономики.

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

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

                  4. Метод динамического программирования дает возможность анализа чувствительности к изменению исходных данных Si и n. Фактически здесь решается не одна задача, а множество однотипных задач для различных состояний Si и различных на каждом шаге. Поэтому при изменении исходных данных можно не решать задачу заново, а сделать лишь несложные добавления к уже выполненным расчетам, т.е. продолжить уже решенную задачу за счет увеличения числа шагов n или числа значений Si. 6

                  1. Задача о замене оборудования. Постановка задачи в общем виде.

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

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

                  Обозначим через r(t) и c(t) прибыль от эксплуатации t–летнего механизма на протяжении года и затраты на его обслуживание за тот же период. Далее пусть s(t) - стоимость продажи механизма, который эксплуатировался t лет. Стоимость приобретения нового механизма остается неизменной на протяжении всех лет и равна I.

                  Элементы модели динамического программирования таковы :

                  1. Этап і представляется порядковым номером года і, і=1,2. n
                  2. Вариантами решения на i–м этапе ( т. е. для i–го года) являются альтернативы: продолжить эксплуатацию или заменить механизм в начале i–го года.
                  3. Состоянием на i–ом этапе является срок эксплуатации (возраст) механизма к началу i–го года.

                  Пусть fi(t)– максимальная прибыль, получаемая за годы от i до n при условии, что в начале i–го года имеется механизм t– летнего возраста.

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

                  1. – если эксплуатировать механизм
                  2. – если заменить механизм. 7

                  Постановка задачи в общем виде.

                  Рассмотрим задачу в общей постановке.

                  Пусть в течение периода, состоящего из n этапов, предприятие использует оборудование, которое вместе с установкой имеет стоимость I. Со временем оборудование изнашивается. При этом:

                  1. суммарная производительность оборудования r(t) снижается, так как увеличивается время, необходимое для его профилактики и ремонта;

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

                  по остаточной стоимости не учитывается. Это допущение не является принципиальным и введено для упрощения анализа.

                  Обозначим моменты начала каждого этапа через ;

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

                  — сохранить установленное оборудование и продолжать его эксплуатацию;

                  — приобрести новое оборудование и заменить старое.

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

                  Оптимальной инвестиционной политикой (стратегией управления) U* называется совокупность таких решений , в результате реализации которых рассматриваемое производство за n шагов переходит из начального состояния в конечное и при этом суммарная прибыль от эксплуатации оборудования достигает максимального значения. Состояние процесса на i-ом этапе характеризуется возрастом оборудования. Максимально возможный возраст оборудования в момент равен i, а минимальный равен 1, если на предыдущем этапе произошла замена оборудования.

                  Прибыль ,получаемая на i-м этапе, зависит от состояния оборудования и сделанного нами выбора (управления) :

                  где r(0) — стоимость продукции, выпускаемой на новом оборудовании;

                  s(t) – стоимость продажи оборудования, который эксплуатировался t лет;

                  I — полная стоимость нового оборудования.

                  Очевидно, что суммарная прибыль F, которую требуется максимизировать для разработки оптимальной инвестиционной политики, равна сумме прибылей на каждом из этапов производства. Таким образом, суммарная прибыль будет определяться по формуле:

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

                  Таким образом, суть разработки оптимальной инвестиционной политики — это получение максимального значения суммарной прибыли F. Она зависит от результатов управления процессом эксплуатации оборудования на каждом шаге. Особенностью динамического программирования является рассмотрение процесса от конца к началу, то есть сначала анализируется n-1 этап, ищется здесь оптимальное решение, затем то же делается на n-2 этапе и т.д. Таким образом, основой математического аппарата для нахождения оптимального решения является принцип оптимальности Беллмана:

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

                  Управление выбирают следующим образом:

                  1) для всех возможных управлений определяются значения сумм

                  которые сравниваются между собой;

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

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

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

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

                  Вектор оптимального управления U* всего процесса будет получен при объединении найденных в ходе вычислений условно оптимальных управлений U*:

                  Пусть требуется выработать оптимальную стратегию для эксплуатации оборудования на 6-ти летнем периоде (табл. 1).

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

                  Содержание работы

                  Введение………………………………………………………………….
                  1. Характеристика состояния хозяйствующего субъекта и выявление тенденций его развития………………………………………………….
                  2. Информационно-методическое обеспечение экономического моделирования.
                  2.1 Методическая база решения модели.
                  2.2 Информационно-методическое обеспечение метода.
                  3. Расчет показателей экономико-математической модели и экономическая интерпретация результатов.
                  Заключение.
                  Список литературы.

                  Содержимое работы - 1 файл

                  Реферат о замене оборудования.docx

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

                  Костанайский государственный университет имени А.Байтурсынова

                  Кафедра программного обеспечения

                  Специальность 050704 – Вычислительная техника и программное обеспечение

                  Выполнила: Золотухина И., студентка 2 курса

                  очной формы обучения

                  Руководитель: Байманкулов А.Т., доцент

                  1. Характеристика состояния хозяйствующего субъекта и выявление тенденций его развития……………………………………………… ….

                  2. Информационно-методическое обеспечение экономического моделирования.

                  2.1 Методическая база решения модели.

                  2.2 Информационно-методическое обеспечение метода.

                  3. Расчет показателей экономико- математической модели и экономическая интерпретация результатов.

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

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

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

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

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

                  При постановке задач динамического программирования следует руководствоваться следующими принципами:

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

                  Этому выигрышу соответствует условное оптимальное управление на i-м шаге xi(S) (причем в уже известную функцию Wi+1(S) надо вместо S подставить измененное состояние )

                    1. Произвести условную оптимизацию последнего (m-го) шага, задаваясь гаммой состояний S, из которых можно за один шаг дойти до конечного состояния, вычисляя для каждого из них условный оптимальный выигрыш по формуле
                    2. Произвести условную оптимизацию (m-1)-го, (m-2)-го и т.д. шагов по формуле (1.2), полагая в ней i=(m-1),(m-2),…, и для каждого из шагов указать условное оптимальное управление xi(S), при котором максимум достигается.

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

                  Задачи о замене

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

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

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

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

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

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

                  Метод ДП обеспечивает единый подход к решению всех видов задач о замене.

                  При составлении модели ДП мы рассматриваем процесс замены как n-шаговый, разбив весь плановый период на n промежутков. Так как в начале каждого из этих промежутков принимается решение либо о сохранении оборудования, либо о его замене, то управление на k-м шаге (k=1, . n) содержит всего лишь две альтернативные переменные. Обозначим через u с решение, состоящее в сохранении старого оборудования, а через u з решение, состоящее в замене старого оборудования новым. Функциональные уравнения, благодаря наличию двух альтернативных управлений на каждом шаге, содержат лишь две величины: одна выражает условную прибыль (условные затраты) при управлении u с , другая—тот же показатель при управлении u з . Условная оптимизация на каждом шаге состоит в вычислении двух величин и в выборе из них наибольшей (наименьшей). Это значительно упрощает расчеты на стадии условной оптимизации и позволяет решать вручную задачи о замене с большим числом шагов.

                  Построение модели ДП для задачи о замене

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

                  Задача 1. Определить оптимальные сроки замены оборудования в течение n лет, при которых прибыль от эксплуатации оборудования максимальна, если известны:

                  p — начальная стоимость оборудования;

                  f(t) — стоимость производимой продукции на оборудовании возраста t лет;

                  r(t) — ежегодные затраты на эксплуатацию оборудования возраста t лет;

                  j(t) —ликвидная стоимость оборудования возраста t лет.

                  Рассмотрим n-шаговый процесс, считая k-м шагом номер k-го года от начала эксплуатации (k=1, 2, . , n). Выше указывалось, что управление на k-м шаге выбирается из двух возможных решений: u с — сохранить и продолжать использование старого оборудования или u з — заменить оборудование новым.

                  Будем считать, что в начале планового периода возраст оборудования равен t0. Состояние Sk-1 системы (оборудования) в начале k-гo шага характеризуется одним параметром Sk-1 = t — возрастом оборудования. Для k-гo шага параметр состояния t может принимать значения 0,1, 2, . k-1, т. е. t ≤ k-1.

                  Если к началу k-гo шага система находилась в состоянии Sk-1 = t, то под влиянием управления u с в конце k-гo шага она перейдет в состояние Sk=t+1; возраст оборудования увеличится на один год. Под влиянием управления u з , принятого на k-м шаге, система перейдет в состояние Sk=1 (замену произвели в начале k-гo года; в конце k-гo года возраст нового оборудования равен одному году).

                  Уравнение состояния для данного процесса имеет вид

                  На рис. 1 состояние системы изображается точкой плоскости в системе координат k, t сплошными стрелками указаны переходы из данного состояния в состояние, соответствующее управлению u с , а пунктирными — управлению u з .

                  Определим прибыль на k-м шаге (показатель эффективности k-гo шага), соответствующую каждому из альтернативных управлений u с и u з . Выбирая на k-м шаге управление u с , мы сможем произвести продукции стоимостью f(t) на старом оборудовании, что потребует затрат r(t), поэтому прибыль равна f(t)—r(t). Обозначим ее через

                  При управлении u з получим доход j(t) от продажи старого оборудования (ликвидную стоимость) и f(0) от произведенной на новом оборудовании продукции, затратив p на приобретение нового оборудования и r(0) на содержание нового оборудования. В этом случае прибыль (обозначим ее через Zk з ) составляет

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

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

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

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

                  Для достижения поставленной цели, необходимо решить ряд следующих задач:

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

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

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

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

                  1.1 Понятия динамического программирования. Составление математической модели динамического программирования

                  O Л. В. Канторовиче и линейном программировании

                  . и о придуманном им методе разрешающих множителей для решения задач, которые позже стали называть задачами линейного программирования. Все это я узнал чуть позже. Сам по себе курс . сказать, "ленинградский" функциональный анализ, у истоков которого стояли В.И.Смирнов, Г.М.Фихтенгольц и, как основной мотор, - Л.В., а позже Г.П.Акилов, имел свою специфику: влияние математической физики .

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

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

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

                  Информация в процессе принятия управленческих решений

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

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

                  Под этапом обычно понимают хозяйственный год.

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

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

                  Однако динамическое программирование имеет и свои недостатки. В отличие от линейного программирования, в котором симплексный метод является универсальным, в динамическом программировании такого метода не существует. Каждая задача имеет свои трудности, и в каждом случае необходимо найти наиболее подходящую методику решения. Недостаток динамического программирования заключается также в трудоемкости решения многомерных задач. При очень большом числе переменных решение задачи даже на современных ЭВМ ограничивается памятью и быстродействием машины. Например, если для исследования каждой переменной одномерной задачи требуется 10 шагов, то в двумерной задаче их количество увеличивается до 100, в трехмерной -до 1000 и т.д.

                  Составление математической модели динамического программирования:

                  Дополнительно введем следующие условные обозначения:

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

                  W i — выигрыш с i-го шага до конца процесса, i=

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

                  1. Разбиение задачи на шаги (этапы).

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

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

                  3. Определение множества шаговых управлений xi , i= и налагаемых на них ограничений, т.е. области допустимых управлений x.

                  4. Определение выигрыша

                  который принесет на i-м шаге управление x i , если система перед этим находилась в состоянии s.

                  5. Определение состояния s’, в которое переходит система из состояния s под влиянием управления xi ,

                  где f i — функция перехода на i-м шаге из состояния s в состояние s’.

                  Сущность и задачи кассационного производства в уголовном процессе

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

                  6. Составление уравнения, определяющего условный оптимальный выигрыш на последнем шаге, для составления s моделируемого процесса

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

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

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

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

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

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

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

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

                  1.2 Этапы решения задачи динамического программирования. Формулировка задачи о замене оборудования

                  После того как выполнены пункты 1-7, и математическая модель составлена, приступают к ее расчету.

                  Основные этапы решения задачи динамического программирования:

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

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

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

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

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

                  6. Проведение безусловной оптимизации управления. Для проведения безусловной оптимизации необходимо найденное на первом шаге оптимальное управление x1 *=x1 (s1 ) подставить в формулу (1.2) и определить следующее состояние системы s1 =f1 (s1 ,x1 ).

                  Для измененного состояния найти оптимальное управление x2 *=x2 (s2 ), подставить в формулу (1.2) и т.д. Для i-го состояния s1 найти si+1 =fi+1 (si ,xi *) и x*i+1 (si+1 ) и т.д.

                  Динамическое программирование обычно придерживается двух подходов к решению задач:

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

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

                  Задача о замене оборудования состоит в определении оптимальных сроков замены старого оборудования. Критерием оптимальности являются либо доход от эксплуатации оборудования (задача максимизации), либо суммарные затраты на эксплуатацию (задача минимизации) в течение планируемого периода. Мы будем рассматривать задачу максимизации, и критерием оптимальности будет доход от эксплуатации оборудования.

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

                  Следовательно, если имеется оптимальная траектория, то и любой ее участок представляет собой оптимальную траекторию.

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

                  Под функцией Беллмана в текущий момент времени понимаем минимальное значение критерия качества в текущий момент времени: Если t=0, то

                  Таким образом, значение функции Беллмана S(x,t) определяет минимальную величину функционала для любого начального состояния x(t) в любой момент времени t . С другой стороны, значение функции Беллмана совпадает со значением, так называемых текущих потерь на управление:

                  Эксплуатация оборудования планируется в течение n лет, но оборудование имеет тенденцию с течением времени стареть и приносить все меньшую годовую прибыль r(t) , где t — возраст оборудования. При этом есть выбор: либо в начале любого года продать устаревшее оборудование за цену S(t) , которая также зависит от возраста, и купить новое оборудование за цену P , либо оставить оборудование в эксплуатации. Требуется найти оптимальный план замены оборудования с тем, чтобы суммарная прибыль за все n лет была максимальной, учитывая, что к началу эксплуатационного периода возраст оборудования составляет t 0 лет.

                  r(t) — доход от эксплуатации в течение одного года оборудования возраста t лет;

                  S(t) — остаточная стоимость оборудования;

                  P — цена нового оборудования;

                  t 0 — начальный возраст оборудования.

                  Переменной управления на k -м шаге является логическая переменная, которая может принимать два значения: С — сохранить , З — заменить оборудование в начале k -го года. Переменной состояния системы на k -м шаге является переменная t .

                  Функцию Беллмана F k (t) определим как максимально возможную прибыль от эксплуатации оборудования за годы с k -го по n -й, если к началу k -го года возраст оборудования составлял t лет. Применяя то или иное управление, мы переводим систему в некоторое новое состояние, а именно, если в начале k -го года мы оборудование сохраняем, то к началу следующего (k+1) -го года его возраст увеличится на 1 (состояние системы станет равно t +1), за год оно принесет прибыль r(t) , и максимально возможная прибыль за оставшиеся годы (с (k+1) -го по n -й) составит F k+1 (t+1) . Если же в начале k -го года принимаем решение на замену оборудования, то мы продаем старое оборудование возраста t лет за цену S(t) , покупаем новое оборудование за цену P и эксплуатируем его в течение k -го года, что приносит за этот год прибыль r(0) . К началу следующего года возраст оборудования составит 1 год, и за все годы с (k+1) -го по n -й максимально возможная прибыль будет F k+1 (1) .

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

                  Функцию Беллмана для первого шага ( k=n ) легко вычислить — это максимально возможная прибыль только за последний n -й год:

                  Вычислив значение функции F n (t) по формуле (2), далее можно посчитать F n-1 (t) , затем F n-2 (t) и так далее до F 1 (t 0 ) . Функция F 1 (t 0 ) представляет собой максимально возможную прибыль за все годы (с 1-го по n -й).

                  Этот максимум достигается при некотором управлении, применяя которое в течение первого года, мы определяем возраст оборудования к началу второго года (в зависимости от того, какое управление является для первого года оптимальным, это будет 1 или t 0 +1).

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

                  2.1 Постановка и условие задачи. Решение задачи о замене оборудования

                  Тогда уравнение (12) интерпретируется как объем вывоза из первого узла, равный запасу продукции в этом узле, т. е. аналогично уравнению для истока транспортной сети. Уравнение (13) интерпретируется как объем продукции, привозимой в размере потребности в узел n, т. е. аналогичное уравнению для стока транспортной сети. Рассматривается функционирование предприятия в условиях сурового климата, его… Читать ещё >

                  Задача о замене оборудования ( реферат , курсовая , диплом , контрольная )

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

                  Пример такого типа задачи ;

                  Задача о замене оборудования.

                  Задача о замене оборудования.

                  Пусть промышленное предприятие функционирует в течение некоторых промежутков времени с номерами. Для выполнения производственной программы предприятие арендует необходимое оборудование. Через какие-то промежутки времени оборудование заменяется на новое. Если оборудование эксплуатируется в промежутке времени (i, j), т. е. начинается эксплуатация в начале i-того периода и заменяется в начале j-того промежутка времени, то предприятие несет затраты (на аренду, тех. обслуживание, ремонт и т. п. ).

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

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

                  Здесь узлы графа соответствуют номерам начала периодов. Если оборудование эксплуатируется в течение промежутка (i, j), то на графе ставится соответствующая дуга, взвешенная числом. Оборудование арендуется в начале 1-го периода, а процесс функционирования предприятия завершается в начале периода времени n.

                  Допустим, в процессе эксплуатации оборудование заменяется при i=2 и i=7, т. е. оборудование заменяется в начале первого, второго и седьмого периодов: и эксплуатируется до узла n. Тогда, очевидно, общая сумма затрат будет равна. А это выражение есть ни что иное, как длина пути (1,2,7,n).Таким, образом, каждому варианту замены оборудования можно поставить в соответствие некоторый путь из узла 1 в узел n. Т. е. множество вариантов замены оборудования отражается множеством путей на рассматриваемом графе. Следовательно, задача оптимального плана замены оборудования эквивалентна задаче поиска кратчайшего пути из узла 1 в узел n на рассматриваемой сети. (Предложить студентам записать ММ самостоятельно.)

                  Одна задача календарного планирования трудовых ресурсов.

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

                  Задача о замене оборудования.

                  Пусть рассматривается функционирование предприятия в течение n-1 промежутка времени, причем известно потребное количество бригад рабочих Rk () для выполнения производственной программы в течение к-того промежутка времени (периода). Если одна бригада рабочих на7имается в начале i-того промежутка и увольняется в начале j-того, т. е. используется в интервале (i, j), то затраты на содержание этой бригады равны .

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

                  Всевозможные варианты найма и увольнения бригад можно изобразить в виде сети, в которой дуга (i, j) означает найм в начале i-того и увольнение в начале j-того периода.

                  Пусть — количество бригад, нанимаемых в начале i-того и увольняемых в начале j-того промежутков. Тогда ММ запишется:

                  Задача о замене оборудования.

                  Задача о замене оборудования.

                  Задача о замене оборудования.

                  Задача о замене оборудования.

                  Задача о замене оборудования.

                  — целые В модели целевая функция (1) отражает суммарные затраты на содержание рабочих бригад. Ограничение (2) требует, чтобы в первом промежутке времени было ровно столько бригад, сколько требуется для выполнения работ на первом промежутке времени. Неравенство (3) допускает целесообразность содержания резервных бригад, т.к. они могут в конечном счете обойтись дешевле. Равенство (4) обеспечивает в последнем промежутке наличие ровно стольких бригад, сколько требуется. Условие (5) вытекает из физического смысла.

                  Модель (1)-(5) относится к классу задач линейного целочисленного программирования. Однако она тождественными преобразованиями сводится к модели транспортной задачи в сетевой постановке.

                  Неравенство (3) приводится к равенству введением доп. переменных:

                  Идея последующих тождественных преобразований заключается в следующем: из уравнений (7) и (4) соответственно вычитаем уравнения (2) и (7), записанные для участка с номером на единицу меньше. Запишем уравнение (7) для участка с номером к-1:

                  Задача о замене оборудования.

                  Задача о замене оборудования.

                  Далее, вычтем (8) из (7):

                  Задача о замене оборудования.

                  Задача о замене оборудования.

                  Задача о замене оборудования.

                  Задача о замене оборудования.

                  Задача о замене оборудования.

                  Задача о замене оборудования.

                  Проведя сокращения, можно записать:

                  Задача о замене оборудования.

                  Задача о замене оборудования.

                  Если вычесть из уравнения (7) с номером к=2 уравнение (2), то получим: ориентированный календарный транспортный сетевой.

                  Задача о замене оборудования.

                  Теперь из уравнения (4) вычтем уравнение (7) с номером. Т.к. уравнение (4) аналогично (7) при и, то результат вычитания следует из формулы (9) при :

                  Задача о замене оборудования.

                  К полученной системе уравнений (9)-(11) присоединим уравнения (2) и (4), умножив (4) слева и с права на -1:

                  Задача о замене оборудования.

                  Полученные уравнения (9)-(13) эквивалентны уравнениям исходной задачи, которая теперь свелась к задаче (1), (9)-(13) с условиями.

                  — целые Далее можно условно интерпретировать:

                  — объем перевозки по дуге (i, j).

                  R1— запас продукции в первом узле,.

                  RкRк-1 — запас продукции k-того узла ,.

                  Rn-1 — запас продукции n-ого узла.

                  Тогда уравнение (12) интерпретируется как объем вывоза из первого узла, равный запасу продукции в этом узле, т. е. аналогично уравнению для истока транспортной сети. Уравнение (13) интерпретируется как объем продукции, привозимой в размере потребности в узел n, т. е. аналогичное уравнению для стока транспортной сети.

                  Рассмотрим уравнение (10):

                  Задача о замене оборудования.

                  — определяет объем продукции, вывозимый из узла 2,.

                  — объем продукции, ввозимый в узел 2 по дуге (1,2).

                  В сеть вводится дополнительная дуга (3,2), по которой перевозится продукция в объеме. Тогда — суммарный объем продукции, привозимой в узел 2. Следовательно уравнение (10) можно интерпретировать как уравнение баланса для промежуточных узлов транспортной задачи в сетевой постановке.

                  Аналогично в сеть добавляются дуги (k, k-1) для всех с объемами перевозок .

                  Задача о замене оборудования.

                  Тогда уравнения (9) интерпретируются как уравнения баланса для промежуточных пунктов ТЗ в сетевой постановке: суммарный объем вывозимой продукции минус суммарный объем ввозимой продукции равняется запасу продукции в этих узлах.

                  Таким образом, задача календарного планирования трудовых ресурсов (1)-(5) тождественными преобразованиями и добавлением новых дуг свелась к модели транспортной задачи в сетевой постановке (1), (9)-(13).

                  Читайте также: