Применение транспортной модели к решению задачи оптимального закрепления операций за станками

 

Оглавление

Введение

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

1.1.Общая формулировка решаемой задачи

.2.Методы решения задачи оптимального закрепления операций за станками

2.Практическая реализация задачи оптимального закрепления операций за станками

1.1.Вербальная постановка задачи

.2.Разработка экономико-математической модели задачи

2.3.Решение задачи «вручную», используя транспортную модель

2.4.Решение поставленной задачи в EXCEL

.5.Интерпретация результатов и выработка управленческого решения

Заключение

Библиографический список

Приложение

Введение

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

·экономией материальных ресурсов, требуемых для постановки и проведения физического эксперимента;

·возможность апробации системы в изменяющихся по воле экспериментатора условиях;

·оценкой работоспособности систем с длительными технологическими циклами в существенно сжатые сроки.

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

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

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

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

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

. Раскрыть теоретические основы темы курсовой работы.

. Разработать экономико-математическую модель.

. Провести анализ методов решения задачи.

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

.Интерпретировать полученные результаты.

Объектом исследования является планирование оптимального закрепления операций за станками.

Предметом исследования является возможность решения производственной задачи о назначении методами линейного программирования.

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

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

1.1Общая математическая формулировка решаемой задачи

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

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

.Как распределить операции за станками так, чтобы общая выработка была максимальной

Математически такие задачи относятся к тому же типу задач, что транспортные, но со следующими особенностями:

·В этих задачах объемы требующихся и наличных ресурсов равны 1 (Аj = Вj = 1)

Например: 10 операций по 10 станкам

·Все переменные хij =1, если операция закреплена за станком, либо хij =0 в любых других случаях.

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

Общая постановка задачи состоит в определении оптимального плана распределения некоторого количества операций по имеющимся в наличии станках. Таким образом, учитывая, что в решении задач может применяться транспортная модель мы имеем, что на предприятии имеется m видов станков, каждый из которых может выполнить n видов операций. При этом Аi - максимальное время работы станка i-го вида, Вj - время выполнения j-й операции, Сij -производительность i-го станка при выполнении j-й операции (число деталей в единицу времени), хij - время работы i-го станка на j-й операции. Сij хij - количество j -x деталей, обработанных на i-м станке.

Тогда целевая функция (количество деталей, обработанных на всех станках) будет иметь вид:

Так как ограничено время отведённое на выполнение - операции величиной , то получаем

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

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

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

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

Обычно исходные данные транспортной задачи записывают в виде таблице, ее структура имеет вид (табл.1):

Таблица 1

Определение оценок

СтанкиОперацииЗапасыВ1…Вj …ВnА1С11 X11 …С1j X1j...C1n X1n a1………………Аi Cj1 Xj1…Cij Xij…Cin Xinaj am………………АmCm1 Xm1…Cmj Xmj…Cmn XmnПотребностиb1bjbn

Очевидно, общее количество станков равно:

а общая потребность в операциях равна единице

Если общая потребность в операциях равна количеству станков, т. е.

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

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

вводится фиктивный (n + 1)-й станок с потребностью

и соответствующая производительность считается равной нулю:

.

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

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

2.1 Методы решения задачи оптимального закрепления операций за станками

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

А) Метод северо-западного угла

Б) Метод наименьших затрат

В) Метод аппроксимации Фогеля

Как нам известно, число переменных Хij в задаче с т количеством станков и п количеством операций равно пт, а число уравнений в системах равно п + т. Так как мы предполагаем, что выполняется условие равности потребности в операциях количеству станков, то число линейно независимых уравнений равно п + т - 1. Следовательно, опорный план задачи может иметь не более п + т - 1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонент равно в точности п + т - 1, то план является невырожденным, а если меньше - то вырожденным. транспортный задача оптимальный закрепление

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

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

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

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

Перейдем к характеристике каждого из методов нахождения оптимального плана закрепления операций за станками:

А) Метод северо - западного угла.

При нахождении опорного плана задачи методом северо-западного угла на каждом шаге рассматривают первую из оставшихся операций и первый из оставшихся станков. Заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного Х11 («северо-западный угол») и заканчивается клеткой для неизвестного хтп, т. е. идет как бы по диагонали таблицы.

Б) Метод минимального элемента.

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

В)Метод аппроксимации Фогеля.

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

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

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

А) Метод потенциалов

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

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

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

при (8)

при (9)

для всех и , то Х* = () - оптимальный план решаемой задачи.

Числа аi и bj; называются потенциалами.

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

(10)

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

Так как число заполненных клеток равно п+m-1, то система (10) с п + m неизвестными содержит n + m-1 уравнений. Поскольку число неизвестных превышает на единицу число уравнений, одно из неизвестных можно положить равным произвольному числу, например a1 = 0, и найти последовательно из уравнений (10) значения остальных неизвестных. После того как все потенциалы найдены, для каждой из свободных клеток определяют числа

.

Если среди чисел аij нет отрицательных, то найденный опорный план является оптимальным. Если же для некоторой свободной клетки аij > 0, то исходный опорный план не является оптимальным и необходимо перейти к новому опорному плану. Для этого рассматривают все свободные клетки, для которых aij > О, и среди данных чисел выбирают максимальное. Клетку, которой это число соответствует, следует заполнить.

Заполняя выбранную клетку, необходимо изменить объемы поставок, записанных в ряде других занятых клеток и связанных с заполненной так называемым циклом. Циклом в таблице условий транспортной задачи называется ломаная линия, вершины которой расположены в занятых клетках таблицы, а звенья-вдоль строк и столбцов, причем в каждой вершине цикла встречается ровно два звена, одно из которых находится в строке, а другое - в столбце, где линия совершает поворот на 90°. Примеры некоторых циклов показаны на рис.1.

1) 2) 3)

Рис.1. Возможные циклы

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

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

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

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

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

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

При сдвиге по циклу пересчета число занятых клеток остается неизменным, а именно остается равным п + m - 1. При этом если в минусовых клетках имеется два (или более) одинаковых числа xij , то освобождают лишь одну из таких клеток, а остальные оставляют занятыми.

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

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

1. Находят опорный план. При этом число заполненных клеток должно быть равным п + m - 1.
2. Находят потенциалы bj и аi соответственно пунктов назначения и отправления.
3. Для каждой свободной клетки определяют число аij. Если среди чисел аij нет положительных, то получен оптимальный план транспортной задачи; если же они имеются, то переходят к новому опорному плану.
4. Среди положительных чисел аij выбирают максимальное, строят для свободной клетки, которой оно соответствует, цикл пересчета и производят сдвиг по циклу пересчета.
5. Полученный опорный план проверяют на оптимальность, т. е. снова повторят все действия начиная с этапа 2.

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

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

Б) Распределительный метод

Распределительный метод является одним из вариантов базового симплексного метода. Поэтому идея распределительного метода (как и симплексного) содержит такие же три существенных момента.

Прежде всего, отыскивается какое-то решение задачи - исходный опорный план. Затем посредством специальных показателей опорный план проверяется на оптимальность. Если план оказывается не оптимальным, переходят к другому плану. При этом второй и последующие планы должны быть лучше предыдущего. Так за несколько последовательных переходов от не оптимального плана приходят к оптимальному. Первый опорный план может быть найден посредством различных способов: по правилу северо-западного угла, приоритету ближайших пунктов, способу минимального элемента С=(Сij), способу Фогеля и по способу Лебедева-Тихомирова. В результате получен первый опорный план, который является допустимым, так как потребность в операциях удовлетворена, а план соответствует системе ограничений задаче о распределении операций. Чтобы установить является ли опорный план оптимальным, надо проверить, как повлияет на величину целевой функции любое возможное перераспределение операций.

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

Проверим возможность уменьшения суммарных затрат времени на проведение операций. С этой целью для каждой свободной от операции клетки определяется величина ? ij, характеризующая изменение суммарных затрат, при условии включения в план операции Хij=1 от поставщика Аi к потребителю Вj.

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

Величина ? ij называется оценкой свободной клетки (или характеристика).

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

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

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

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

Следующий этап решения задачи заключается в улучшении опорного плана.

Если при каком-то опорном плане оказывается несколько свободных клеток с отрицательными оценками ?ij, то за один переход к лучшему плану можно занять поставкой только одну клетку - ту, которая обеспечивает наибольшее снижение целевой функции. Улучшение опорного плана происходит до тех пор, пока все оценки свободных клеток не станут положительными, то есть целевая функция не окажется минимальной.

2. Практическая реализация задачи оптимального закрепления операций за станками

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

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

·настольном токарном станке (1);

·токарно-револьверном (2);

·токарно-карусельном (3);

·трубонарезном станке (4);

·токарно-сверлильном станке (5);

можно выполнять пять операций по обработке деталей:

·обточку цилиндрических, конических и фасонных поверхностей (1);

·расточку цилиндрических, конических и фасонных поверхностей (2);

·нарезание резьбы (3);

·обработку торцов (4);

·сверление, зенкерование и развертывание отверстий (5);

При этом за каждым из станков может быть закреплена лишь одна операция и одна и та же операция может выполняться лишь за одним станком. Зная время выполнения каждой операции на каждом из станков, которое задается матрицей:

А=

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

2.2 Разработка экономико-математической модели задачи оптимального закрепления операций за станками

Составим математическую модель предложенной задачи. Обозначим через Хij (i= 1,5; j=1;5) переменную, значение которой равно 1, если на i-м станке j-я операция выполняется, и равно 0, в противном случае. Тогда закрепление за каждым станком только одной операции выражается равенством:

А закрепление каждой операции только за одним станком - следующим равенством:

Требуется найти такие значения переменных Хij (i= 1,5; j=1;5), удовлетворяющие системам уравнений, указанным выше, равные 0 или 1, при которых целевая функция:

принимает минимальное значение.

2.3 Решение задачи оптимального закрепления операций за станками «вручную», используя танспортную модель

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

при условиях:

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

Поскольку сумма операций равна сумме станков,

то получаем 5+5-1= 9 занятых клеток. Переходим к поиску оптимального решения

Таблица 2. Время выполнения каждой операции (матрица оценок)

СтанкиОперацииЗапасы12345124133121541213 352241 1414314532535Потр.11111

Этап 1. Поиск первого опорного плана

1.Используя метод наименьших затрат построим первый опорный план транспортной задачи (табл. 3)

Таблица 3

Поиск первого оптимального плана

СтанкиОперацииЗапасы123451241 133 121 541 213 3 5224 11 1 141431 14 53 2 151 5Пот-и11111

. Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 9. Следовательно, опорный план является вырожденным.

Значение целевой функции для этого опорного плана равно:

Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 9. Следовательно, опорный план является вырожденным.

Для получения невырожденного плана принудительно добавляем нуль (0) в клетку (1;1); (1;2); (1;4); (1;5);

Этап 2. Проверка опорного плана на оптимальность.

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

Таблица 4

Проверка опорного плана на оптимальность

СтанкиОперацииЗапасы1234512 04 01 13 03 0 121 541 213 3 5224 11 1 141431 14 53 2 151 5Потреб.11111

1.(2; 2) = 5-1+2-4=2

.(2; 3) = 4-1+2-1 = 4

3.(2; 4) = 1-1+2-3= -1

4.(2; 5) = 2-1+2-3 = 0

.(3; 1) = 3-2+3-4 = 0

.(3; 2) = 5-4+3-4 = 0

7.(3; 4) = 2-3+3-4 = -2

8.(4; 1) = 1-2+3-1 = 1

.(4;2) = 4-4+3-1 = 2

.(4; 3) = 3-1+3-1 = 4

. (4; 5) = 4-1+3-3 = 3

.(5; 1) = 3-2+4-2 = 3

.(5;3) = 5-2+4-1 = 6

.(5;4) = 3-2+4-3=2

.(5; 5) = 5-2+4-3 = 4

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

Выбираем минимальную оценку свободной клетки (3;4):- 2

Для этого в перспективную клетку (3;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». (табл.5)

Таблица 5

Перераспределение ресурсов

СтанкиОперацииЗапасы1234512 04 01 13 0 «-» 3 0 «+» 121 154 1 213 3 522 «+»4 1 «-»1 1 141431 14 53 2 151 5Потреб.11111

Цикл приведен в таблице (3,4; 3,5; 1,5; 1,4; ).

Из хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 4) = 0. Прибавляем 0 к объемам работ, стоящих в плюсовых клетках и вычитаем 0 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план (табл.6)

Повторим поиск оптимального плана, следуя алгоритму первого этапа, находя предварительные потенциалы. В итоге получаем, что опорный план не является оптимальным, так как существуют оценки свободных клеток, имеющие отрицательный знак. Выбираем минимальную оценку свободной клетки (4;1): - 1

Таблица 6

Новый опорный план

СтанкиОперацииЗапасы1234512 04 01 13 3 0 121 154 1 213 3 522 0 4 1 1 1 141431 14 53 2 151 5Потреб.11111

Повторим поиск оптимального плана, следуя алгоритму первого этапа, находя предварительные потенциалы. В итоге получаем, что опорный план не является оптимальным, так как существуют оценки свободных клеток, имеющие отрицательный знак. Выбираем минимальную оценку свободной клетки (4;1): - 1

Для этого в перспективную клетку (4;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». (табл.7)

Таблица 7

Второе перераспределение ресурсов

СтанкиОперацииЗапасы1234512 0 «-»4 01 13 3 0 «+»121 154 1 213 3 522 0 «+» 4 1 «-»1 1 141 «+»431 1 «-»4 53 2 151 5Потреб.11111

Цикл приведен в таблице (4,1; 4,4; 3,4; 3,5; 1,5; 1,1; ).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 0. Прибавляем 0 к объемам грузов, стоящих в плюсовых клетках и вычитаем 0 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план (табл.8)

Таблица 8

Опорный план №3

СтанкиОперацииЗапасы1234512 4 01 13 3 0 121 154 1 213 3 522 0 4 1 1 1 141 0431 1 4 53 2 151 5Потреб.11111

Проверим полученный план на оптимальность. План вновь не является оптимальным, так как существуют оценки свободных клеток, содержащие отрицательные значения. Выбираем максимальную оценку свободной клетки (2;5): - 2

Для этого в перспективную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». (табл.9)

Цикл приведен в таблице (2,5; 2,1; 4,1; 4,4; 3,4; 3,5; ).

Из хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 1) = 1. Прибавляем 1 к объемам грузов, стоящих в плюсовых клетках и вычитаем 1 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план (табл.10).

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

Таблица 9

Перераспределение ресурсов №2

СтанкиОперацииЗапасы1234512 4 01 13 3 0 «-»121 1«-»54 1 2 «+»13 3 522 0 «+»4 1 «-»1 1 141 0 «+»431 1 «-»4 53 2 151 5Потреб.11111

Таблица 10

Оптимальный план решения задачи

СтанкиОперацииЗапасы1234512 4 01 13 3 0 121 54 1 2 113 3 522 14 01 1 141 1 431 04 53 2 151 5Потреб.11111

2.4 Решение поставленной задачи в среде EXCEL

По условию рассмотренной выше задачи составляем таблицу (табл.11).

Таблица 11

Условие задачи

СтанкиОперацииЗапасы12345124133121541213 352241 1 1414314532535Потребности11111Расположим данные таблицы на листе Excel (рис.2)

Рис. 2. Ввод данных

В ячейки (B2: F6) занесем матрицу, далее в ячейки (B10:F14) поместим любые значения 0. В ячейках (G19:G14), вычисляются суммы ячеек (B10:F10; B11:F11; B12:F12; B13:F13, В14:F14). В ячейках (B15:F15), вычисляются суммы ячеек (B10:B14; C10:C14; D9:D14, E10:Е14). В ячейку С17 записывается следующая формула: «=СУММПРОИЗВ(В2:F6;В10:F14)», вычисляющая произведение соответствующих элементов массивов, а затем суммирует получившиеся значения.

Занесем значения для поиска решений. Установить целевую ячейку С17.

В появившемся окне установим:

·Максимальное значение;

·Изменяя ячейки В10:F14; В9:F9=В14:F14; A10:A14=G10:G1; В10:F14=целое, В10:F14=двоичное.

При нажатии кнопки: «Выполнить» лист Excelя выглядит следующим образом (рис.3):

Рис.3. Нахождение результатов

Отчеты по результатам приведены ниже (см. Приложение 1)

2.5 Интерпретация результатов и выработка управленческого решения

При интерпретации решений задачи оптимального закрепления операций за станками (как решения задачи «вручную, так и с помощью средств Excel), приходим к выводу, что для наилучшей организации рабочего процесса, а именно минимизации времени выполнения каждым рабочим определенной операции и общего суммарного минимизированного времени работы менеджеру фирмы «Макрос» необходимо проконтролировать, чтобы на следующих станках были выполнены следующие операции:

·на настольном токарном станке (1) выполнялась нарезание резьбы (3);

·на токарно-револьверном (2) выполнялось сверление отверстий (5);

·на токарно-карусельном (3) выполнялась обработка торцов (4);

·на трубонарезном станке (4) выполнялась обточка цилиндрических, конических и фасонных поверхностей (1);

·на токарно-сверлильном станке (5) выполнялась расточку цилиндрических, конических и фасонных поверхностей (2)

Данное распределение является оптимальным, поскольку суммарное выполнение заданных оперпций за представленнями станками является минимальным (что требовало условие задачи) и равно 8 часам рабочего времени. А именно на настольно-нарезном станке нарезание резьбы шло 1 час рабочего времнени персонала. На токарно-револьверном выполняется сверление отверстий за 2 часа. Работа на токарно-карусельном станке по обработке торцов потребует 2 час работы. На трубонарезном станке выполнится обточка цилиндрических, конических и фасонных поверхностей за 1 час рабочего времени и, наконец, на токарно-сверлильном станке мастер потратит на расточку цилиндрических, конических и фасонных поверхностей 2 часа рабочего времени.

Заключение

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

На основе выполненной курсовой работы, можно сделать следующие выводы:

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

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

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

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

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

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

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

1.Орехов Н.А., Лёвин А.Г., Горбунов Е.А. Математические методы и модели в экономике.

2.Карасев А.И., Кремер Н.Ш., Савельева Т.Н. Математические методы и модели в планировании.

.Шелобаев С.И. Математические методы и модели в экономике, финансах и бизнесе.

.Афанасьев М.Ю. Исследование операций в экономике.

.И.Г. Попова. Математические методы в планировании отраслей и предприятий.

.И.Н. Дрогобницкого. Экономико-математическое моделирование.

.Федосеев В.В. Экономико-математические методы и прикладные модели.

Приложение 1

Microsoft Excel 11.0 Отчет по результатамРабочий лист: [Книга2]Лист1Отчет создан: 25.11.2012 16:20:23Целевая ячейка (Минимум)ЯчейкаИмяИсходное значениеРезультат$C$17Целевая функция88Изменяемые ячейки$B$10Матрица назначений00$C$10 00$D$10 11$E$10 00$F$10 00$B$11Матрица назначений00$C$11 00$D$11 00$E$11 00$F$11 11$B$12Матрица назначений00$C$12 00$D$12 00$E$12 11$F$12 00$B$13Матрица назначений11$C$13 00$D$13 00$E$13 00$F$13 00$B$14Матрица назначений00$C$14 11$D$14 00$E$14 00$F$14 00ОграниченияЯчейкаИмяЗначениеФормулаСтатусРазница$B$9Матрица назначений1$B$9=$B$15не связан.0$C$9 1$C$9=$C$15не связан.0$D$9 1$D$9=$D$15не связан.0$E$9 1$E$9=$E$15не связан.0$F$9 1$F$9=$F$15не связан.0$A$10 1$A$10=$G$10не связан.0$A$11 1$A$11=$G$11не связан.0$A$12 1$A$12=$G$12не связан.0$A$13 1$A$13=$G$13не связан.0$A$14 1$A$14=$G$14не связан.0$B$10Матрица назначений0$B$10=целоесвязанное0$C$10 0$C$10=целоесвязанное0$D$10 1$D$10=целоесвязанное0$E$10 0$E$10=целоесвязанное0$F$10 0$F$10=целоесвязанное0$B$11Матрица назначений0$B$11=целоесвязанное0$C$11 0$C$11=целоесвязанное0$D$11 0$D$11=целоесвязанное0$E$11 0$E$11=целоесвязанное0$F$11 1$F$11=целоесвязанное0$B$12Матрица назначений0$B$12=целоесвязанное0$C$12 0$C$12=целоесвязанное0$D$12 0$D$12=целоесвязанное0$E$12 1$E$12=целоесвязанное0$F$12 0$F$12=целоесвязанное0$B$13Матрица назначений1$B$13=целоесвязанное0$C$13 0$C$13=целоесвязанное0$D$13 0$D$13=целоесвязанное0$E$13 0$E$13=целоесвязанное0$F$13 0$F$13=целоесвязанное0$B$14Матрица назначений0$B$14=целоесвязанное0$C$14 1$C$14=целоесвязанное0$D$14 0$D$14=целоесвязанное0$E$14 0$E$14=целоесвязанное0$F$14 0$F$14=целоесвязанное0$B$10Матрица назначений0$B$10=двоичноесвязанное0$C$10 0$C$10=двоичноесвязанное0$D$10 1$D$10=двоичноесвязанное0$E$10 0$E$10=двоичноесвязанное0$F$10 0$F$10=двоичноесвязанное0$B$11Матрица назначений0$B$11=двоичноесвязанное0$C$11 0$C$11=двоичноесвязанное0$D$11 0$D$11=двоичноесвязанное0$E$11 0$E$11=двоичноесвязанное0$F$11 1$F$11=двоичноесвязанное0$B$12Матрица назначений0$B$12=двоичноесвязанное0$C$12 0$C$12=двоичноесвязанное0$D$12 0$D$12=двоичноесвязанное0$E$12 1$E$12=двоичноесвязанное0$F$12 0$F$12=двоичноесвязанное0$B$13Матрица назначений1$B$13=двоичноесвязанное0$C$13 0$C$13=двоичноесвязанное0$D$13 0$D$13=двоичноесвязанное0$E$13 0$E$13=двоичноесвязанное0$F$13 0$F$13=двоичноесвязанное0$B$14Матрица назначений0$B$14=двоичноесвязанное0$C$14 1$C$14=двоичноесвязанное0$D$14 0$D$14=двоичноесвязанное0$E$14 0$E$14=двоичноесвязанное0$F$14 0$F$14=двоичноесвязанное0

Оглавление Введение 1.Теоретические основы задачи оптимального закрепления операций за станками 1.1.Общая формулировка решаемой задачи .2.Метод

Больше работ по теме: