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

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

Оглавление

Введение

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

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

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

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

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

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

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

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

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

Под исследованием операций понимается применение количественных математических методов для обоснования решений во всех областях целенаправленной человеческой деятельности. Таким образом, можно смело сказать, что экономико-математическое моделирование - это важнейший инструмент менеджера и экономиста. Орехов Н.А., Лёвин А.Г., Горбунов Е.А. Математические методы и модели в экономике: Учебное пособие для вузов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

· В этих задачах объемы требующихся и наличных ресурсов равны 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-м станке.

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

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

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

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

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

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

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

Таблица 1

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

при (8)

при (9)

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

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

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

(10)

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

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

.

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

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

1) 2) 3)

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

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

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

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

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

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

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

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

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

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

Находят опорный план. При этом число заполненных клеток должно быть равным п + m -- 1.

Находят потенциалы b_j и а_i соответственно пунктов назначения и отправления.

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

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

Полученный опорный план проверяют на оптимальность, т. е. снова повторят все действия начиная с этапа 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. Время выполнения каждой операции (матрица оценок)

Станки	Операции	Запасы
	1	2	3	4	5
1	2	4	1	3	3	1
2	1	5	4	1	2	1
3	3	5	2	2	4	1 1
4	1	4	3	1	4
5	3	2	5	3	5
Потр.	1	1	1	1	1

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

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

Таблица 3

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

Станки	Операции	Запасы
	1	2	3	4	5
1	2	4	1 1	3	3	1
2	1	5	4	1	2	1
3	3	5	2	2	4 1	1 1 1
4	1	4	3	1 1	4
5	3	2 1	5	1	5
Пот-и	1	1	1	1	1

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

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

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

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

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

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

Таблица 4

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

Станки	Операции	Запасы
	1	2	3	4	5
1	2 0	4 0	1 1	3 0	3 0	1
2	1	5	4	1	2	1
3	3	5	2	2	4 1	1 1 1
4	1	4	3	1 1	4
5	3	2 1	5	1	5
Потреб.	1	1	1	1	1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 5

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

Станки	Операции	Запасы
	1	2	3	4	5
1	2 0	4 0	1 1	3 0 «-»	3 0 «+»	1
2	1 1	5	4	1	2	1
3	3	5	2	2 «+»	4 1 «-»	1 1 1
4	1	4	3	1 1	4
5	3	2 1	5	1	5
Потреб.	1	1	1	1	1

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

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

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

Таблица 6

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

Станки	Операции	Запасы
	1	2	3	4	5
1	2 0	4 0	1 1	3	3 0	1
2	1 1	5	4	1	2	1
3	3	5	2	2 0	4 1	1 1 1
4	1	4	3	1 1	4
5	3	2 1	5	1	5
Потреб.	1	1	1	1	1

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

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

Таблица 7

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

Станки	Операции	Запасы
	1	2	3	4	5
1	2 0 «-»	4 0	1 1	3	3 0 «+»	1
2	1 1	5	4	1	2	1
3	3	5	2	2 0 «+»	4 1 «-»	1 1 1
4	1 «+»	4	3	1 1 «-»	4
5	3	2 1	5	1	5
Потреб.	1	1	1	1	1

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

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

Таблица 8

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

Станки	Операции	Запасы
	1	2	3	4	5
1	2	4 0	1 1	3	3 0	1
2	1 1	5	4	1	2	1
3	3	5	2	2 0	4 1	1 1 1
4	1 0	4	3	1 1	4
5	3	2 1	5	1	5
Потреб.	1	1	1	1	1

Проверим полученный план на оптимальность. План вновь не является оптимальным, так как существуют оценки свободных клеток, содержащие отрицательные значения. Выбираем максимальную оценку свободной клетки (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

Станки	Операции	Запасы
	1	2	3	4	5
1	2	4 0	1 1	3	3 0 «-»	1
2	1 1«-»	5	4	1	2 «+»	1
3	3	5	2	2 0 «+»	4 1 «-»	1 1 1
4	1 0 «+»	4	3	1 1 «-»	4
5	3	2 1	5	1	5
Потреб.	1	1	1	1	1

Таблица 10

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

Станки	Операции	Запасы
	1	2	3	4	5
1	2	4 0	1 1	3	3 0	1
2	1	5	4	1	2 1	1
3	3	5	2	2 1	4 0	1 1 1
4	1 1	4	3	1 0	4
5	3	2 1	5	1	5
Потреб.	1	1	1	1	1

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

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

Таблица 11

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

Станки	Операции	Запасы
	1	2	3	4	5
1	2	4	1	3	3	1
2	1	5	4	1	2	1
3	3	5	2	2	4	1 1 1
4	1	4	3	1	4
5	3	2	5	3	5
Потребности	1	1	1	1	1

Расположим данные таблицы на листе 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 часа рабочего времени.

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложение 1

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

Подобные документы

• Экономико-математические методы и прикладные модели

  Построение экономико-математической модели задачи, комментарии к ней и получение решения графическим методом. Использование аппарата теории двойственности для экономико-математического анализа оптимального плана задачи линейного программирования.
  
  контрольная работа [2,2 M], добавлен 27.03.2008
  

• Разработка модели и решение задачи линейного программирования (на примере задачи о составлении графика работы персонала)

  Математическая формулировка экономико-математической задачи. Вербальная постановка и разработка задачи о составлении графика персонала. Решение задачи о составлении графика персонала с помощью программы Microsoft Excel. Выработка управленческого решения.
  
  курсовая работа [1,2 M], добавлен 12.01.2018
  

• Решение транспортной задачи распределения методом потенциалов

  Формулировка проблемы в практической области. Построение моделей и особенности экономико-математической модели транспортной задачи. Задачи линейного программирования. Анализ постановки задач и обоснования метода решения. Реализация алгоритма программы.
  
  курсовая работа [56,9 K], добавлен 04.05.2011
  

• Исследование операций

  Составление математической модели, целевой функции, построение системы ограничений и симплекс-таблиц для решения задач линейного программирования. Решение транспортной задачи: определение опорного и оптимального плана, проверка методом потенциалов.
  
  курсовая работа [54,1 K], добавлен 05.03.2010
  

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

  Построение и обоснование математической модели решения задачи по составлению оптимального графика ремонта инструмента. Использование табличного симплекс-метода, метода искусственных переменных и проверка достоверности результата. Алгоритм решения задачи.
  
  курсовая работа [693,1 K], добавлен 04.05.2011
  

• Использование симплексного метода для решения задач линейного программирования. Способы решения транспортной задачи

  Составление математической модели задачи. Расчёт оптимального плана перевозок с минимальной стоимостью с использованием метода потенциалов. Оптимальный вариант специального передвижного оборудования для технического обеспечения управления производством.
  
  контрольная работа [135,3 K], добавлен 01.06.2014
  

• Методы линейного программирования для решения транспортной задачи

  Применение линейного программирования для решения транспортной задачи. Свойство системы ограничений, опорное решение задачи. Методы построения начального опорного решения. Распределительный метод, алгоритм решения транспортной задачи методом потенциалов.
  
  реферат [4,1 M], добавлен 09.03.2011
  

• Метод потенциалов для решения транспортной задачи в матричной форме. Задача оптимального распределения ресурсов

  Графический метод решения задачи оптимизации производственных процессов. Применение симплекс-алгоритма для решения экономической оптимизированной задачи управления производством. Метод динамического программирования для выбора оптимального профиля пути.
  
  контрольная работа [158,7 K], добавлен 15.10.2010
  

• Линейное программирование, теория игр

  Составление математической модели и решение задачи планирования выпуска продукции, обеспечивающего получение максимальной прибыли. Нахождение оптимального решения двойственной задачи с указанием дефицитной продукции при помощи теорем двойственности.
  
  контрольная работа [232,3 K], добавлен 02.01.2012
  

• Разработка производственных и управленческих решений

  Пример решения задачи симплексным методом, приведение ее к каноническому виду. Составление экономико-математической модели задачи. Расчеты оптимального объёма производства предприятия при достижении максимальной прибыли. Построение симплексной таблицы.
  
  практическая работа [58,0 K], добавлен 08.01.2011
  

• главная
• рубрики
• по алфавиту
• вернуться в начало страницы
• вернуться к началу текста
• вернуться к подобным работам