Менеджмент в машиностроительных предприятиях.

Содержание

Теоретические основы динамического программирования
Задача 1. Задача распределения капиталовложений
Задача 2. Задача календарного планирования трудовых ресурсов
Задача 3. Задача о замене оборудования
Список литературы

Менеджмент в машиностроительных предприятиях.

Это позволяет находить решение поэтапно, на каждом из этапов используя информацию, полученную на предыдущих этапах, причем эффективность этого алгоритма прямо зависит от структуры графа взаимосвязей переменных. Если этот граф достаточно разрежен, то объем вычислений на каждом этапе может сохраняться в разумных пределах. Классические задачи динамического программирования: Задача о наибольшей общей подпоследовательности Задача о выборе траектории Задача последовательного принятия решения Задача об использовании рабочей силы Задача управления запасами Задача о ранце Задача поиска кратчайшего пути в сети Динамическое программирование представляет собой математический аппарат, разработанный для эффективного решения некоторого класса задач математического программирования. Этот класс характеризуется возможностью естественного (а иногда и искусственного) разбиения всей операции на ряд взаимосвязанных этапов. Термин "динамическое" в названии метода возник, видимо, потому что этапы предполагаются разделенными во времени. Однако этапами могут быть элементы операции, никак не связанные друг с другом показателем времени. Тем не менее, метод решения подобных многоэтапных задач применяется один и тот же, и его название стало общепринятым, хотя в некоторых источниках его называют многоэтапным программированием. Модели динамического программирования могут применяться, например, при разработке правил управления запасами, устанавливающими момент пополнения запасов и размер пополняющего заказа; при разработке принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию; при распределении дефицитных капиталовложений между возможными новыми направлениями их использования; при составлении календарных планов текущего и капитального ремонта сложного оборудования и его замены; при разработке долгосрочных правил замены выбывающих из эксплуатации основных фондов и т.д. Для определения сущности динамического программирования рассмотрим задачу: Представим себе некоторую операцию О, состоящую из ряда последовательных "шагов" или этапов, например, деятельность отрасли промышленности в течение ряда хозяйственных лет. Пусть число шагов равно m. Выигрыш (эффективность операции) Z за всю операцию складывается из выигрышей на отдельных шагах:Z=i=1nziгде zi- выигрыш на i-м шаге.Если Z обладает таким свойством, то его называют аддитивным критерием. Операция О является управляемым процессом, то есть мы можем выбирать какие-то параметры, которые влияют на его ход и исход, причем на каждом шаге выбирается решение, от которого зависит выигрыш и на данном шаге, и выигрыш за операцию в целом. Эти решения называются шаговыми.Совокупность всех шаговых управлений является управлением операцией в целом. Обозначим его буквой х, а шаговые управления - буквами х1, х2, ... , хm: х=х(х1, х2, ... , хm). Требуется найти такое управление х, при котором выигрыш Z обращается в максимум: Z=i=1nzi→maxТо управление х*, при котором этот максимум достигается, называется оптимальным управлением. Оно состоит из совокупности оптимальных шаговых управлений: х*=х*(х1*, х2*, ... , хm*). Максимальный выигрыш, который достигается при этом управлении, обозначим следующим образом:Z*=maxx∈XZ(x)где Х- множество допустимых (возможных) управлений. Самый простой способ решения задачи - полный перебор всех вариантов. Когда количество вариантов невелико, этот способ вполне приемлем. Однако на практике задачи с небольшим числом вариантов встречаются весьма редко, поэтому полный перебор, как правило, неприемлем из-за чрезмерных затрат вычислительных ресурсов. Поэтому в таких случаях на помощь приходит динамическое программирование. Динамическое программирование часто помогает решить задачу, переборный алгоритм для которой потребовал бы очень много времени. Этот метод использует идею пошаговой оптимизации. В этой идее есть принципиальная тонкость: каждый шаг оптимизируется не сам по себе, а с "оглядкой на будущее", на последствия принимаемого "шагового" решения. Оно должно обеспечить максимальный выигрыш не на данном конкретном шаге, а на всей совокупности шагов, входящих в операцию. Метод динамического программирования может применяться только для определенного класса задач. Эти задачи должны удовлетворять таким требованиям:- Задача оптимизации интерпретируется как n-шаговый процесс управления. - Целевая функция равна сумме целевых функций каждого шага. - Выбор управления на k-м шаге зависит только о состояния системы к этому шаге, не влияет на предшествующие шаги (нет обратной связи). - Состояние sk после k-го шага управления зависит только от предшествующего состояния sk-1 и управления xk (отсутствие последействия). На каждом шаге управление Xk зависит от конечного числа управляющих переменных, а состояние sk- от конечного числа параметров. В основе решения всех задач динамического программирования лежит "принцип оптимальности" Беллмана, который выглядит следующим образом: Каково бы ни было состояние системы S в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный. Этот принцип впервые был сформулирован Р. Беллманом в 1953 г. Беллманом четко были сформулированы и условия, при которых принцип верен. Основное требование - процесс управления должен быть без обратной связи, т.е. управление на данном шаге не должно оказывать влияния на предшествующие шаги. Принцип оптимальности утверждает, что для любого процесса без обратной связи оптимальное управление таково, что оно является оптимальным для любого подпроцесса по отношению к исходному состоянию этого подпроцесса. Поэтому решение на каждом шаге оказывается наилучшим с точки зрения управления в целом.Задача 1. Задача распределения капиталовложенийНайдите оптимальное решение задачи распределения капиталовложений при условии, что суммарный объем инвестиций равен 8 млн.руб.ПроектПредприятие 1Предприятие 2Предприятие 3C1R1C2R2C3R3135340024645233--58354----69Совет директоров фирмы изучает предложения по наращиванию производственных мощностей на трех принадлежащих фирме предприятиях. Для расширения всех трех предприятий фирма выделяет средства в объеме 8 млн.руб. Каждое предприятие представляет на рассмотрение проекты, которые характеризуются величинами суммарных затрат (С) и доходов (R), связанных с реализацией каждого из проектов. В таблице включены также проекты с нулевыми затратами. Это позволяет предусмотреть возможность отказаться от расширения какого-либо предприятия.Цель фирмы состоит в получении максимального дохода от инвестиций.В задаче каждому предприятию ставится в соответствие некоторый этап, поскольку требуется выбрать оптимальный проект для каждого предприятия. Известно, что этапы связаны между собой посредством ограничения на суммарный объем капиталовложений. При построении модели учитываем эту взаимосвязь таким образом, чтобы получить возможность по отдельности решать подзадачи, соответствующие каждому этапу, не нарушая при этом допустимости.Введем следующие обозначения:Х1 – объем капиталовложений, распределенных на этапе 1.Х2 – объем капиталовложений, распределенных на этапе 1 и 2.Х3 – объем капиталовложений, распределенных на этапе 1,2,3.Конкретные значения Х1 и Х2 заранее не известны, однако эти значения лежат в интервале от 0 до 8. Таким образом, значения Х1 и Х2 могут быть равны 0,1,2,3,4,5,6,7,8. С другой стороны значение переменной Х3 равно 8.Пусть - f1*X1 – максимальный доход, полученный на этапе 1, при заданном значении Х1.- f1*X2 – максимальный доход, полученный на этапе 1 и 2, при заданном значении Х2.- f1*X3 – максимальный доход, полученный на этапе 1, 2,3 при заданном значении Х3.Тогда рекуррентное соотношение динамического программирования будет иметь следующий вид:f0*X0=0fj*Xj=maxRjkj+fj-1*Xj-1, j=1,2,3, где максимум берется по допустимым проектам kj.Так как сjkj=Xj-Xj-1, следовательно, Xj-1=Xj-сj, kj≥0.Откуда сjkj≤Xj.Приведем результаты поэтапных расчетов на основе рекуррентного соотношения для рассматриваемой задачи.Этап 1. f1*X1=maxR1k1, с1k1≤X1, k1=1,2Х1R1k1Оптимальное решение k1=1 k1=2 f1*X1 k135-514566255662656627566285662Этап 2. f2*X2=maxR2k2+f1*X2-с2, k2, с2k2≤X2, k2=1,2,3Х2R2k2+f1*X2-с2, k2Оптимальное решениеk1=1k1=2k1=3f2*X2k264+5=9--9174+6=105+5=10-101,284+6=105+6=118+5=13133Этап 3. f3*X3=maxR3k3+f2*X3-с3, k3, с3k3≤X3, k3=1,2,3,4Х3R3k3+f2*X3-с3, k3Оптимальное решениеk3=1k3=2k3=3k3=4f3*X3k380+13=133+9=12--131Максимальный доход от инвестиций в объеме 8 млн.руб. составит 13 млн.руб. оптимальное решение можно найти непосредственно из таблицы. Причем сначала рассматривается третья таблица (полученная на этапе 3), затем на этапах 2 и 1. В нашей задаче оптимальным решением является следующее сочетание проектов: {1,3,1}.Таким образом, на первом этапе мы расширяем первое предприятие, вкладывая в него 3 млн.руб., на втором этапе – второе предприятие, вкладывая в него 5 млн.руб. На третьем этапе принимаем к третьему предприятию первый проект с нулевыми затратами, т.е. отказываемся от расширения предприятия.Задача 2.