Материалы сайта
Это интересно
Применение линейного программирования в задачах оптимизации загрузки станочного оборудования
Российская Научно-Социальная Программа Для Молодежи и Школьников « Шаг В Будущее ». Применение линейного программирования в задачах оптимизации загрузки станочного оборудования. Исследовательская работа на Российскую научно-техническую конференцию молодых исследователей « Шаг В Будущее, Москва ». Автор: Сиротин А.Н. Российская Федерация г. Москва, УВК №1636. Научный руководитель: Васильев Г. Н. д.т.н., профессор МГТУ им. Н. Э. Баумана Москва 1998 г. 1 Применение линейного программирования в задачах оптимизации загрузки станочного оборудования. Автор: Сиротин А.Н Россия , г. Москва , УВК №1636. В докладе рассмотрена задача оптимальной загрузки оборудования станочной системы (СтС) из условия максимального суммарного времени его работы, путем подбора соответствующей партионности обрабатываемых деталей. Примем, что станочная система состоит из металлорежущих станков различного типа (токарных, фрезерных, сверлильных и т.д.). Задача оптимизации загрузки оборудования станочной системы (СтС) при заданном фонде времени его работы заключается в выборе числа деталей в партии (имеется N различных деталей). Рассмотрим решение этой задачи с помощью метода линейного программирования. Задача линейного программирования имеет следующий вид [ 1 ]: Найти Xi => 0 (i =1,2....,k), удовлетворяющие линейным ограничениям k gi = bij Xj { <= , = , => } Bi ( i =1,2....,m) j =1 и обеспечивающие экстремум целевой функции k F(Х) = aij Xij ( ехtr i =1 В качестве примера формулировки и решения задачи линейного программирования рассмотрим выбор оптимального размера партий деталей D1 и D2 из условия максимальной загрузки оборудования станочной системы. Пусть станочная система состоит из трех групп станков [ 2 ]: сверлильных, токарных и фрезерных. Известны фонды времени работы оборудования в месяц, а также нормы времени на обработки деталей на станках каждой группы. Необходимо определить X1 и Х2, т.е. число деталей D1 и D2, которые обеспечивает максимальную загрузки оборудования станочной системы. Эти данные сведены в табл. 1 2 Таблица 1. Исходные данные задачи максимальной загрузки оборудования. |Группа |Норма времени на |Месячный фонд времени | |оборудования |обработку деталей, ч |работы группы | | | |оборудования, ч | | |D1 |D2 | | |Сверлильное |0,1 |0,3 |200 | |Токарное |0,5 |0,9 |700 | |Фрезерное |0,3 |0,2 |330 | Сформулируем задачу линейного программирования. Запишем уравнения ограничений по фонду времени оборудования: 0,1 X1 + 0,3 Х2 <= 200 (1) 0,5 X1 + 0,9 X2 <= 700 (2) 0,3 Х1 + 0,2 Х2 <= 330 (3) Целевая функция равна суммарному времени работы всех групп оборудования F(Х1,X2) = 0,1X1 + 0,3Х2 + 0,5X1+ 0,9Х2 + 0,3 X1+ 0,2 Х2 = = 0,9X1 + 1,4Х2 ( max. (4) Требуется найти X1 и Х2, удовлетворяющие заданным ограничениям и обеспечивающие максимум целевой функции F( X1, Х2). Двухпараметрическую задачу линейного программирования можно решить графически. На рис. 1 показано графическое решение задачи о максимальной загрузке системы станочного оборудования . Сначала по уравнениям ограничений строится область допустимых значений параметров X1 Х2, которая получается в виде многоугольника. Его сторонами являются прямые, построенные по уравнениям ограничений. Так отрезок АВ соответствует ограничению (1), отрезок ВС - (2), а отрезок СD - (3).Целевая функция, согласно уравнению, имеет также вид прямой. На рис.1 построено уравнение целевой функции при F1 =1 80ч. Однако эта прямая не проходит через область допустимых значений X1 и Х2 и, следовательно, не может являться решением задачи линейного программирования. Прямые, построенные по уравнению целевой функции, при разных ее значениях, будут параллельны друг другу, поэтому, прямая, соответствующая оптимальному значению целевой функции, будет параллельна прямой П и долена касаться области допустимых значений X1, Х2. Оптимальное решение: F = 1201,47 ч; X1= 924 шт. : Х2 = 265 шт. Все другие прямые, построенные по уравнению целевой функции и лежащие ниже линии F , соответствуют меньшим значениям целевой функции. 3 Так линия, проходящая через начало координат, соответ-ствует минимальному значению целевой функции F=0, Данная задача относится к задаче целочисленного программирования [1], однако ее можно решать методами линейного программирования при непрерывном изменении параметров, так как погрешность округления в этом случае незначительна. В случае большей размерности задачи ее геометрическое реше-ние невозможно, так как необходимо найти точку касания в k -мерном пространстве (k > 2). Область допустимых значений параметров, построенная по уравнениям ограничений, получается в виде многогранника, а целевая функция в виде гиперплоскости. Из геометрической интерпретации задачи линейного программирования следует, что для ее решения необходимо вычислить значения целевой функции в вершинах многогранника ограничений (предварительно определив координаты его вершин). Сравнивая значения целевой функции (перебором), можно найти величину, где достигается extr F. В этом случае возникает трудности с построением многогранника ограничений, т.е. с определением координат вершин, которые являются внешними к области определения параметров. Кроме того, число вершин многогранника резко возрастает с увеличением k и m ,и такой перебор значений целевой функции будет слишком трудоемким. Аналитическое решение задач линейного программирования производится с помощью симплексного метода (метод последовательного улучшения плана). Этот метод обеспечивает большую эффективность, нежели метод перебора. Его суть заключается в том, что начиная с вычисления F в некоторой произвольной вершине многогранника ограничений, переходят к отысканию такой вершины. где значение целевой функции будет больше, чем в предыдущей (если отыскивается вершина с максимальным значением F). Другие вершины, лежащие на общих гранях, для вычисления F не используются. Это позволяет производить упорядоченный перебор вершин многогранника ограничений по критерию увеличения F. Отсюда следует объяснение другого названия данного метода (метод последовательного улучшения плана). Первый шаг решения задачи линейного программирования симплексным методом состоит в том, чтобы от заданной системы ограничений в виде неравенств перейти к системе ограничений в виде уравнений. Это осуществляется путем введения дополнительных переменных. Если ограничения имеют вид (Вi => 0). k gi = bij Xj <= Bi. J = 1 то вводятся дополнительные переменные ( Xk +1 => 0 ) k Xk +1 = Bi - bi Xj j = 0 или k bij Xj + Xk +1 = Bi j = 1 4 С помощью дополнительных переменных переходим к системе уравнений с r неизвестными ( k <= r <= k + m ). Число дополнительных переменных равно r - k. Обычно процесс решения задачи симплекс методом иллюстрируется последовательностью симплекс-таблиц. Общий вид исходной задачи можно представить табл. 2. Таким образом, задача линейного программирования сводится к следующей эквивалентной задаче ( ak +1 = ak +2 = ... = ar = 0 ); найти максимум F = C x , где С = ( а1,а2,...,ar ) при Bx = D, B = [bij], D = ( В1 ,В2 ,...,Вm ), Xi => 0. Задача определения min F может быть сведена к задаче нахождения max. F1 при F1 = -F. Если ограничения имеют вид k gi = bij Xj => bi , j+1 то каждому такому неравенству соответствует уравнение с двумя дополнительными переменными k bij Xj - Xk +1 + Xk +2. j =1 При Вi < 0 и неравенства типа «больше или равно» уравнение с дополнительной переменной имеет вид k - bij Xj +Xk+1 = - Bi . j =1 Если ограничение имеет заданно в виде равенства k gi = bij Xj = Bi j =1 необходимо ввести два уравнения с дополнительными переменными k bij Xj + Xk +1 = Bi ; j =1 5 Таблица 2. Общий вид исходной задачи линейного программирования при решении ее симплексным методом . |Основные |Независимые | Дополнительные |Посто- | |перемен- |переменные |переменные |янные | |ные | | | | | | | | | | | | | | | | | | | | | |X1 |Х2 |...|Хk |Хk+1 |Xk+2 |... |Хr |Вi | |Xk+1 |b11 |b12 |...|b1k |1 |0 |... |0 |B1 | |Xk+2 |b21 |b22 |...|b2k |0 |1 |... |0 |В2 | |. |. |. |...|. |. |. |... |. |. | |. |. |. |...|. |. |. |... |. |. | |. |. |. |. |. |. |. |... |. |. | |Xk+m |bm1 |bm2 |...|bmk |0 |0 |... |1 |Bm | |-F |а1 |а2 |...|ak |0 |0 |... |0 |0 | Примечание. В последней строке в правой крайней клетке вносится значение функции на каждой итерации с обратным знаком (-F). k bij Xj + Xk+2 - Xk+3 = Bi . j =1 При ограничениях, определяющих значения независимых переменных в интервале, например, при Вi <= Xj <= Bi+1 , вводится дополнительная переменная Хk+1 = Xj - Вi и ограничение примет вид Хk+1 <= Вi+1 - Вi. Алгоритм симплексного метода показан на рис.2 . Решение задачи получается в виде итерационной последовательности таблиц . Исходная симплекс-таблица имеет вид табл. 2 ( блок 2 на рис. 2 ). На каждой последующей итерации (номер итерации п) определяется максимальное значение коэффициента aj в целевой функции F. Таким образом, определяется переменная Хv (независимая или дополнительная), которая будет вводится в список основных (базисных) переменных. Если все коэффициенты столбца соответствующего переменной Хj , нулевые или отрицательные задача решения не имеет. В противном случае определяется строка q и базисная переменная, которую заменит переменная Xnj , Определение номера строки осуществляется в блоке 5 по минимальному отношению постоянной Вi к соответствующему коэффициенту v-го столбца. После того, как q -я строка найдена, все ее элементы делятся на коэффициент bqv , находящийся на пересечении q-й строки и v-го столбца (блок 6). Далее вычисляются 6 коэффициенты с помощью которых все элементы v-го столбца, кроме Bqv (который равен 1), приводятся к нулю (блок 7). Соответственно в блоках 11,12 и 13 осуществляется преобразование строк симплексной таблицы путем прибавления к каждой строке q-й строки, умноженной на коэффициент ki (или коэффициент kj для преобразования строки целевой функции). Преобразование таблицы заканчивается введением переменной Xv в список базисных переменных (блок 10). Если после преобразования симплексной таблицы все коэффициенты уравнения целевой функции становятся нулевыми или отрицательными (блок 9), процесс решения заканчивается. На печать выводятся значения основных переменных равные соответствующим значениям постоянных Bi (блок 8). Процесс решения продолжается в том случае, когда условие aj <= 0 не выполняется и производится следующее итерационное преобразование симплексной таблицы. В качестве примера использования симплексного метода рассмотрим решение задачи оптимальной загрузки оборудования (1-4). Внесем данные задачи в табл. 3 (исходные данные приведены для нулевого номера итерации). Так как имеется три уравнения ограничений типа «меньше - равно», то и дополнительных переменных тоже три (Х3, Х4, Х5). Возьмем дополнительные переменные в качестве основных. Выбираем столбец коэффициентов при Х2, так как коэффициент целевой функции в этом столбце равен 1,4 и является наибольшим (0,9; 1,4: 0; 0; 0:). При этом значение целевой функции равно нулю. Делим постоянные Вi на соответствующие коэффициенты столбца для Х2 : 200 / 0.3; 700 / 0,9; 330 / 0,2. Наименьшее из этих значений соответствует первой строке. Значит переменную Х2 необходимо ввести в список базисных переменных вместо переменной Х3, которая находится в первой строке таблицы. Делим все коэффициенты первой строки, включая B1, на коэффициент K1 = 0,3. Для второй строки коэффициент Кi = K2 = 0,9, для третьей строки К3 = 0,2 и для четвертой строки К4 = 1,4. Умножая приведенную первую строку, в которой коэффициент B12 = 1, на коэффициенты Кi, Кj и складывая ее поочередно с другими строками, получаем в результате первой итерации базисный вид переменной Х2 и значение целевой функции 933,33 ч. Первая итерация (1) соответствует выбору точки A (см. рис. 16.6), координаты которой Х2 =666,6 шт. X1 = 0 берем в качестве опорного плана. При второй итерации (2) выбирается первый столбец и вторая строка. Вместо базисной переменной Х4 вводится переменная X1. Эта итерация соответствует точке B с координатами Х1 = Х2 = 500. Значение целевой функции в точке В равно 1150. На третьей итерации (3) выбирается третий столбец и третья строка. Переменная Х5 выводится из списка основных переменных и вместо нее вводится Х3. Один коэффициент целевой функции отрицателен, остальные равны нулю, значит процесс решения закончен. Получена точка с оптимальными координатами X1 = 924 шт., Х2 = 265 шт. Максимальное значение целевой функции F = 1201,76 ч. Рассмотренный алгоритм симплексного метода является универсальным для задач линейного программирования. Однако в большинстве случаев не удается свести модель проектирования, допускающую использование стандартного метода синтеза станочных систем и приходится прибегать к их имитационному моделированию и простому перебору вариантов [3]. 7 Таблица 3. Пример решения задачи симплексным методом : |Номер |Основ- |Независимые |Дополнительные |Посто- | |итерац|ные пе- |переменные |переменные |янные - Вi| |ии |ременные | | | | | | |X1 |Х2 |Х3 |Х4 |Х5 | | | |Х3 |0,1 |0,3 |1 |0 |0 |200 | | |X4 |0,5 |0,9 |0 |1 |0 |700 | |0 |Х5 |0.3 |0,2 |0 |0 |1 |330 | | |- F |0.9 |1,4 |0 |0 |0 |0 | | |Х2 |0,333 |1 |3,333 |0 |0 |666.6 | |1 |Х4 |0.2 |0 |-3 |1 |0 |100 | | |Х5 |0,2333 |0 |-0,666 |0 |1 |196.967 | | |-F |0,4333 |0 |-4,666 |0 |0 |- 933,33 | | |Х2 |0 |1 |8,333 |-1.667 |0 |500 | | |X1 |1 |0 |- 15 |5 |0 |500 | |2 |Х5 |0 |0 |2.83 |-1,16? |0 |80,02 | | |- F |0 |0 |1,833 |-2,167 |0 |- 1150 | | |Х2 |0 |1 |0 |2,5 |0 |264,6 | | |X1 |1 |0 |0 |- 2,5 |0 |923,72 | |3 |Х3 |0 |0 |1 |- 0,5 |1 |28.248 | | |- F |0 |0 |0 |-1.251 |0 |- 1201,5 | 8 А вот ещё один пример использования линейного программирования в задачах загрузки станочного оборудования . 1. Выбор порядка выполнения заказов В условиях многономенклатурного производства, когда одни и те же изделия можно обрабатывать на различных станках, могут возникать задачи распределения заказов по станкам. Целевой функцией при этом является минимизация общих затрат. Для точного решения подобной задачи требуется большой объем информации, значительные затраты времени и большой объем вычислений, особенно если задача решается вручную. Однако если предположить, что затраты па изделие пропорциональны времени его обработки, то можно применить простой метод решения задачи, получивший название «индикаторного». Поясним этот метод вновь на примере. Предположим, что цех должен выполнить следующие четыре заказа: Заказ 1 — 100 изделий, Заказ 2 — 200 изделий, Заказ 3 — 50 изделий, Заказ 4 — 75 изделий. Изделия любого заказа можно обрабатывать на любом из четырех станков, но при этом время выполнения заказов будет различным. Каждый из четырех станков, естественно, располагает ограниченным ресурсом времени для выполнения заказов. Исходных Данные задачи приведены в табл. 4. Таблица 4 Нормативы часовой обработки изделии по каждому заказу на каждом станке. | |Станок | |Заказ |A |B |C |D | |1 |1 |2/3 |4/5 |4/3 | |2 |2 |1 |10/11 |5/3 | |3 |2 |4/3 |1 |5/2 | |4 |1 |4/5 |2/3 |5/4 | |Ресурс , | | | | | |Станко-Часы . |80 |150 |250 |100 | Рассмотрим решение задачи распределения заказов по станкам. Прежде всего определяется время, требующееся для выполнения каждого заказа на определенном станке. Эти данные приведены в табл. 5. в столбце «затраты времени на заказ». Далее нужно выбрать критерий эффективности для каждого станка при выполнении каждого заказа. Этот критерий определяется с помощью специальной оценки (индикатора). Станку, имеющему наибольшую производительность при обработке изделий данного заказа, приписывается оценка 1,00. Следующему станку в порядке убывания производительности приписывается оценка, равная отношению числа часов работы рассматриваемого станка к числу часов работы по выполнению данного заказа станком с максимальной производительностью. Для заказа 1 станок D является наилучшим, поэтому ему присваивается оценка 1,00, станок A получает оценку 1,33 и т. д. Эти данные приведены в соответствующих столбцах табл.5. 9 Таблица 5. Пример индикаторного метода заказов по станкам . | | |Станок A |Станок B |Станок C |Станок D | | | |Норматив|Оценка|Затрат|Норматив|Оценк|Затрат|Норматив|Оценка|Затрат|Норматив|Оценка|Затрат| |За|Объём |часовой |(индик|ы |часовой |а |ы |часовой |(индик|ы |часовой |(индик|ы | |ка|заказа|обработк|атор) |времен|обработк|(инди|времен|обработк|атор) |времен|обработк|атор) |времен| |з | |и | |и на |и |катор|и на |и | |и на |и | |и на | | | |изделий | |заказ |изделий |) |заказ |изделий | |заказ |изделий | |заказ | | | | | |,ч | | |,ч | | |,ч | | |,ч | |1 |100 |1 |1,33 |100 |2/3 |2,00 |150 |4/5 |1,67 |125 |4/3 |1,00 |75 | |2 |200 |2 |1,00 |100 |1 |2,00 |200 |10/11 |2,20 |220 |5/3 |1,20 |120 | |3 |50 |2 |1,25 |25 |4/3 |1,88 |37,5 |1 |2,50 |50 |5/2 |1,00 |20 | |4 |75 |1 |1,25 |75 |4/5 |1,56 |93,75 |2/3 |1,87 |112,5 |5/4 |1,00 |60 | |Ресурс | | | | | | | | | | | | | |времени | |80 | | |150 | | |250 | | |100 | | |станка, ч| | | | | | | | | | | | | |Использов| | | | | | | | | | | | | |анное | |75 | | |0 | | |220 | | |95 | | |время | | | | | | | | | | | | | |работы | | | | | | | | | | | | | |станка, ч| | | | | | | | | | | | | 10 Таблица 6 Данные для распределения заказов по станкам по методу МОДИ. | | | |Станок A |Станок B |Станок C |Станок D | |Заказ|Объём |Продаж|Часовой|Время |Затрат|Часовой|Время |Затрат|Часово|Время |Затрат|Часово|Время |Затраты| | |заказа|ная |нормати|выполн|ы на |нормати|выполн|ы на |й |выполн|ы на |й |выполне|на | | |. |цена 1|в |ения |издели|в |ения |издели|нормат|ения |издели|нормат|ния |изделие| | |Число |издели|обработ|заказа|е |обработ|заказа|е |ив |заказа|е |ив |заказа | | | |издели|я |ки | | |ки | | |обрабо| | |обрабо| | | | |й |долл. |изделий| | |изделий| | |тки | | |тки | | | | | | | | | | | | |издели| | |издели| | | | | | | | | | | | |й | | |й | | | |1 |100 |10,00 |1 |100 |7,00 |2/3 |150 |7,50 |4/5 |125 |7,20 |4/3 |75 |6,00 | |2 |200 |6,00 |2 |100 |3,50 |1 |200 |5,00 |10/11 |220 |6,6 |5/3 |120 |4,80 | |3 |50 |7,00 |2 |25 |3,50 |4/3 |37 1/2|3,75 |1 |50 |6,00 |5/2 |20 |3,20 | |4 |75 |11,00 |1 |75 |7,00 |4/5 | |6,25 |2/3 |112 |9,00 |5/4 |60 |6,40 | | | | | | | | |93 3/4| | |1/2 | | | | | |Ресурс времени |80 |150 |250 |100 | |станка, ч | | | | | 11 Заказы должны распределяться по станкам в соответствии с минимальными оценками при условии, что станки имеют достаточные ресурсы времени. Анализ табл. 5 показывает, что некоторые варианты распределения заказов по станкам недопустимы (если предполагать, что заказ должен быть выполнен только на одном станке). Заказы 1и 2 не могут быть выполнены па станке A. Их выполнение требует 100 ч па каждый, а ресурс машинного времени составляет всего 80 ч. Аналогично заказ 2 нельзя выполнять ни на станке B, ни на станке D. Следовательно, заказ 2 приходится выполнять на станке C, несмотря на то, что этому станку соответствует наиболее высокая (наименее выгодная) оценка. Если станок выбран. то требуемое число часов на выполнение заказа должно быть зафиксировано (например, 220 ч для выполнения заказа 2 па станке С). Заказ 1 нельзя выполнять на станке А, поскольку после закрепления заказа 2 за .станком С для выполнения заказа 1 на станке С не хватает времени. Но заказ 1 для станка D имеет оценку 1,00 и закрепляется за этим станком. Заказ 3 можно также закрепить за станком D. Теперь заказ 4 можно закрепить как за станком А, так и за станком В. Поскольку оценка этого заказа для станка А меньше, заказ 4 закрепляется именно за этим станком. Таким образом, все заказы распределены. Составление таблицы распределения заканчивается определением данных для строки «использованное время работы станка». При полученном распределении заказов по станкам суммарное время работы станков составляет 390 ч. При любом другом распределении потребуется большее время. Индикаторный метод прост и его можно легко реализовать на практике, но в нем не учитываются непосредственно затраты на обработку деталей на станках. Косвенно эти затраты учитываются, поскольку принятые оценки определяют относительную эффективность работы станков по выполнению каждого заказа. 2.Применение модифицированного распределительного метода (МОДИ) к решению задачи распределения заказов по станкам. Для иллюстрации возможности использования МОДИ-метода для решения этого типа задач воспользуемся данными задачи, решенной индикаторным методом , введя в рассмотрение данные о затратах продажных цен. Так как для решения этой задачи требуется использование некоторых средних, то решение является приближенным. Сведения об издержках и ценах вместе с ранее использованными данными приведены в табл. 6. Объемы заказов, часовые нормативы обработки изделий и ресурсы времени станков взяты из табл. 4. Из табл. 6 определяются усредненные часовые нормативы обработки изделий для каждого станка и для всех стон кон вместе. Усредненные нормативы затрат времени на изделие для станков А, В, С и D равны 0,750, 1,125, 1,213 и 0,638 соответственно. Общий усредненный норматив составляет 0,93 ч на изделие. Зная эти величины, можно определить так называемые эквивалентные нормативные ресурсы времени для каждого станка. Этот показатель для каждого станка определяется как произведение фактического ресурса времени на эквивалентный средний часовой норматив обработки изделий, деленное на средний по всем станкам часовой норматив обработки изделий. Вычисленные таким образом эквивалентные нормативные ресурсы времени станков равны: Станок А 99 Станок В 124 Станок С 192 Станок В 146 Умножая размеры заказов изделий па среднее по всем станкам время обработки изделия, получим нормативы затрат времени на выполнение заказа. 12 Таким образом, в рассматриваемом примере эти нормативы равны: Заказ 1 93 Заказ 2 186 Заказ 3 47 Заказ 4 70 Прибыль, отнесенная к нормативному часу по каждому заказу на каждом станке, определяется как произведение прибыли на изделие и часового норматив обработки изделий. Значения этого показателя по каждому заказу на каждый станок приведены в табл. 7. Таблица 7 Матрица прибылей (в долл.) | |Станок | |Заказ |A |B |C |D | |1 |3,30 |1,67 |2,24 |5,33 | |2 |5,00 |1,00 |0,55 |2,00 | |3 |7,00 |4,33 |1,00 |9,50 | |4 |4,00 |3,80 |1,33 |5,75 | Оптимальное решение показано в табл. 8. В этом решении предполагалось, что заказ может быть разделен, т. е. может выполняться более чем на одном станке. Поскольку при использовании метода МОДИ требуется, чтобы «общие потребности» были равны «общим возможностям», то при решении этой задачи необходимо добавить фиктивный заказ. Распределение фиктивного заказа отображает продукцию, которая не будет произведена. Если же ресурсы мощности меньше, чем потребности, то необходимо ввести фиктивные станки, и любое распределение по таким станкам будет отображать не поставляемые заказы. Таблица 8 Оптимальное распределение заказов по станкам. | |Станок | | | |2,05 |-1,95 |-3,09 |0,00 |Общая | |Заказ | | | | |потребность | | |A |B |C |D |в | | | | | | |станко-часах| |5,33 |7,38 |3,38 |2,24 |5,33 | | |1 | | |27 |66 |93 | |2,95 |5,00 |1,00 |-0,14 |2,95 | | |2 |99 |87 | | |186 | |9,50 |11,55 |7,55 |6,41 |9,50 | | |3 | | | |47 |47 | |5,75 |7,80 |3,80 |2,66 |5,75 | | |4 | |37 | |33 |70 | |3,09 |5,14 |1,14 |0,00 |3,09 | | |Фиктивный | | |165 | |165 | |Общий | | | | | | |наличный | | | | | | |ресурс |99 |124 |192 |146 |561 | |станко-часов| | | | | | |. | | | | | | 13 Оптимальное решение, приведенное в табл. 8, определяется методами, использующимися при решении транспортных задач, но с одним отличием: поскольку используемые величины представляют собой прибыль, а не затраты, разность между «затратами» и «прибылью» должна быть нулем или положительной величиной. Решение, выраженное в числе изделий, приведено в табл. 9. Величины в правом верхнем углу каждой клетки определяются делением числа нормативных часов табл. 8 по каждому станку на среднее нормативное время по всем станкам. Поскольку норматив затрат времени на обработку изделия основан на усреднении, то необходимо внести некоторые поправки. Скорректированные величины приведены в нижнем левом углу каждой клетки табл. 9. Общая прибыль (в долл.) равна Заказ 1 00 Х 4,00 = 400,00 Заказ 2 160 Х 2,50 = 400,00 32 Х 1,00 = 32,00 8 Х 1,20 = 9,60 Заказ 3 50 X 3,80 = 190,00 Заказ 4 75 X 4,75 = 356,25 . Общая прибыль 1387,85 При этом не учитываются затраты на наладку. Таблица 9 Окончательное распределение заказов. | | |Объем | | |Станок |выпуска | |Заказ | |продукции, | | | | | | |включаемый | | |A |B |C |D |вплан | |1 | | | |75 | | | | | | |100 |100 | |2 |80 |32 | |4 8/10 | | | |160 |32 | |8 |200 | |3 | | | |20 | | | | | | |50 |50 | |4 | |93 3/4 | | | | | | |75 | | |75 | |Затраты | | | | | | |машинного |80 |125 3/4 | |99 8/10 | | |времени | | | | | | Поскольку решение задач распределения методом МОДИ основано на одной матрице затрат или прибылей, то при использовании этого метода необходимо упростить формулировку задачи, сведя ее на постановку к заданию следующей информации: 1) набору потребностей; 2) набору производственных мощностей; 3) матрице затрат или прибылей. Если такое упрощение нежелательно, то следует использовать симплексный метод. 14 При тех же условиях распределению заказов по станкам с помощью «индикаторного» метода соответствует общая прибыль в 1198 долл. Поэтому распределение, полученное методом МОДИ без учета затрат на наладку, когда возможно разделение заказа между станками, оказывается экономически более выгодным. 3. Распределение заказов по станкам при помощи симплексного метода. Симплексный метод является более точным методом распределения заказов по станкам. Рассмотрим его применение на конкретном примере. Используя данные табл. 6, можно сформулировать задачу следующим образом: Максимизировать Z = 3X1A + 2.5X1B +2,8X1C+4X1D + 2,5X2A +1,0X2B - 0,6X2C +1,2X2D + 3,5X3A +3,25X3B +X3C +3,8X3D +4X4A +4,75X4B +2X4C +4X4D При ограничениях X1A + X1B +X1C+X1D =100 X2A +X2B - X2C + X2D =200 X3A + X3B +X3C + X3D = 50 X4A +X4B +X4C +X4D = 75 X1A + 0,5X2A +0,5 X3A + X4A <= 80 1,5X1B + X2B +0,75X3B +1,25X4B <= 150 1,25X1C + 1,1 X2C + X3C +1,5X3C <=250 0,75X1D +0,6X2D +0,4 X3D +0,8X4D <=100 XIJ >=0 . РЕШЕНИЕМ ЭТОЙ ЗАДАЧИ ЯВЛЯЕТСЯ : X1D =100, X2А = 160, X3DB = 31 2/3 , X2D = 8 1/3 , X3D = 50 , X4B = 75, Z = 1387,92 долл. Это решение имеет следующую содержательную интерпретацию: Обработать 100 изделий заказа 1 па станке D; Обработать 160 изделий заказа 1 на станке A; Обработать 31 2/3 изделий заказа 2 на станке B; Обработать 8 1/3 изделий заказа 2 на станке D; Обработать 50 изделий заказа 3 на станке D; Обработать 75 изделий заказа 4 на станке B', Суммарная прибыль при этом равна 1387,92 долл. Но если это решение округлить до допустимых целых чисел, то получается то же решение, что и при использовании метода МОДИ. Список используемой литературы. - Бигель Дж. Управление производством. Количественный подход.-М.: Мир, 1973. -304 с. - Васильев Г.Н. Автоматизация проектирования металлорежущих станков .-М.: Машиностроение ,1987. -280 с. - Васильев Г.Н. Оптимальное проектирование станочных систем. Известия вузов .-М.: Машиностроение. 1987, №10, с. 142-153. Применение линейного программирования в задачах оптимизации загрузки станочного оборудования . В вышеизложенном докладе рассмотрена задача оптимальной загрузки оборудования станочной системы из условия максимального суммарного времени его работы , путём подбора соответствующей партионности обрабатываемых деталей . Здесь станочная система состоит из металлорежущих станков различного типа (токарных, фрезерных, сверлильных и т.д.). Задача оптимизации загрузки оборудования станочной системы при заданном фонде времени его работы заключается в выборе числа деталей в партии (имеется N различных деталей). Этот вопрос вполне актуален в наши дни . Сейчас всё больше появляется частных предприятий, где очень строго контролируется использование ресурсов, а значит и финансов, которые ограниченны. Всё это конечно относится и государственным предприятиям . В связи с переходом на самофинансирование и хозрасчёт руководители должны всё больше уделять внимание на рациональное использование станочного оборудования. Произошёл переход от экстенсивного использования ресурсов к интенсивному. Рассмотрим решение этой задачи с помощью метода линейного программирования. Эту задачу можно решить графически и аналитически .Из геометрической интерпретации задачи линейного программирования следует, что для ее решения необходимо вычислить значения целевой функции в вершинах многогранника ограничений (предварительно определив координаты его вершин). Сравнивая значения целевой функции (перебором), можно найти величину, где достигается extr F. В этом случае возникает трудности с построением многогранника ограничений, т.е. с определением координат вершин, которые являются внешними к области определения параметров. Кроме того, число вершин многогранника резко возрастает с увеличением коэфициэнтов ,и такой перебор значений целевой функции будет слишком трудоемким. Аналитическое решение задач линейного программирования производится с помощью симплексного метода (метод последовательного улучшения плана). Этот метод обеспечивает большую эффективность, нежели метод перебора. Его суть заключается в том, что начиная с вычисления F в некоторой произвольной вершине многогранника ограничений, переходят к отысканию такой вершины. где значение целевой функции будет больше, чем в предыдущей (если отыскивается вершина с максимальным значением F). В условиях многономенклатурного производства, когда одни и те же изделия можно обрабатывать на различных станках, могут возникать задачи распределения заказов по станкам. Целевой функцией при этом является минимизация общих затрат. Для точного решения подобной задачи требуется большой объем информации, значительные затраты времени и большой объем вычислений, особенно если задача решается вручную. Однако если предположить, что затраты па изделие пропорциональны времени его обработки, то можно применить простой метод решения задачи, получивший название «индикаторного». Применение Линейного Программирования в Задачах Оптимизации Загрузки Станочного Оборудования .