pronikov_a_s_2000_t_3 (830968), страница 107
Текст из файла (страница 107)
Требуется определить число Я; станков ~-го типа, составляющих СтС. Математическая модель оптимизации представлена в табл. 16.2, п.1. Модель синтеза компоновки второго типа с частичной взаимозаменяемостью станков для СтС, на которой должна производиться обработка деталей ~ групп при годовой программе ~~ выпуска деталей каждой группы. Детали Ьй группы ф = 1, 2, ... г) проходят некоторое число операций из набора,4. На каждой~~-й операции из этого набора (~р = 1, 2, ....4) возможно применение Я„- взаимозаменяемых станков Х типов (~; = 1, 2, ...
1,), отличающихся друг от друга производительностью и уровнем автоматизации, стоимостью и затратами на эксплуатацию. Станкоемкость обработки детали Ж-й группы на у~-й операции, осуществляемой на станке ~;го типа, равна «„~, реальный годовой фонд времени станка ~;го типа составляет Т„-К„„; а приведенные затраты на его приобретение и эксплуатацию равны С„. Необходимо определить оптимальное число станков каждого типа Я; соответствующего уровня автоматизации для каждой операции (п.2, табл.
16.2). Модель синтеза компоновок станочных систем с взаимозаменяемостью технологических маршрутов обработки (внутри каждой А-й группы деталей) строится также для г групп деталей с годовой программой г~ выпуска деталей каждой группы. Для деталей каждой Ьй группы возможна реализация М~ технологических маршрутов. Станкоемкость обработки деталей Ьй группы на станке ~-го типа 552 16.3. Иходные данные задачи максимальной загрузки оборудования СтС Оборудование Но мав еменинаоб а деталей, ч Месячный фонд времени работы группы оборудования, ч Све лильное Тока ное 0,1 0,3 200 0,5 09 700 0,3 0,2 330 Сформулируем задачу линейного программирования. Запишем уравнения ограничений по фонду времени оборудования: 0,1х1 + 0,3хр < 200 0,5х~ + 0,9х2 < 700 0,3х1 + 0,2х2 < 330 (16.1) (16.2) (16.3) 554 Во всех трех типах моделей могут быль учтены дополнительные ограничения по дефицитности станков и по надежности станочной системы.
Анализ моделей синтеза станочных систем показывает, что первая модель (см. 1, табл. 16.2) является частным случаем второй модели (см. 2, табл. 16.2) при у~ = 1, а вторая является частным случаем третьей (см. 3, табл. 16.2) при М~ = 1. Приведенные модели относятся к прямой задаче объемного планирования СтС, т.е. к задаче определения оптимального качественного и количественного состава оборудования. Под обратной задачей объемного планирования, решаемой на этапах проектирования СтС, понимается задача оптимального распределения обрабатываемых деталей по оборудованию СтС. Это — в основном задачи распределения ресурсов, которые в ряде случаев решаются комбинатор- ными методами, методом «ветвей и границ», методами динамического программирования и методами целочисленного линейного программирования.
Рассмотрим пример решения обратной задачи объемного планирования с помощью метода линейного программирования. Задача линейного программирования имеет следующий вид: найти х; > 0 (г = 1, 2, ... А), удовлетворяющие линейным ограничениям д,. = ~ Ь„х,.
(<, =, >~ Р, при (г = 1, 2, ..., и) )=1 и обеспечивающие экстремум целевой функции Г(х) =~~~ а„,х,, ехй'. г=1 В качестве примера формулировки и решения задачи линейного программирования рассмотрим выбор оптимального размера партий деталей .О~ и ХЬ~ из условия максимальной- загрузки оборудования станочной системы. Пусть станочная система состоит из трех групп станков: сверлильных, токарных и фрезерных. Известны фонды времени работы оборудования в месяц а также нормы времени на обработку деталей на станках каждой группы. Эти данные сведены в табл.
16.3. Необходимо определить х~ и хъ т.е. число деталей Х)~ и ХЬ, которое обеспечивает максимальную загрузку оборудования станочной системы. Целевая функция равна суммарному времени работы всех групп оборудования Р(х, х,) = 0,1х, + 0,3х, + 0,5х, + 0,9х + 0,3х, + 0,2х, = (16.4) = 0,9х, + 1,4х2 — ~ тах Требуется найти х~ и х2, удовлетворяющие заданным ограничениям и обеспечивающие максимум целевой функции Г(хь х2).
Двухпараметрическую задачу линейного программирования можно решить графически. На рис. 16.6 показано графическое решение задачи о максимальной загрузке системы станочного оборудования. Сначала по уравнениям ограничений строят область допустимых значений параметров х1х2, которая получается в виде многоугольника.
Его у р~ сторонами являются прямые, построенные по уравнениям ограничений. Так, отрезок АВ соответствует юоо ограничению (16.1), отрезок ВС вЂ” (16.2), а отрезок СΠ— щщ (16.3). Целевая функция, согласно уравнению, имеет ~~Ф также вид прямой. На г4 а рис. 16.6 построено уравне- н г~ ние целевой функции при ~ ф,» Гу = 1800 ч, однако эта прямая не проходит через область допустимых значений С Х1 и Х2 и следовательно, не может являться решением задачи линейного програм- ~ ~~~~ ~® миро вания.
Прямые, по- Ф строенные по уравнению целевой функции при раз Рис. 1б.б. Графическое решение задачи максимальной загрузки оборудования ных ее значениях будут параллельны друг другу, поэтому прямая, соответствующая оптимальному значению целевой функции, будет параллельна прямой Г1 и должна касаться области допустимых значений х1 и х2. Оптимальное решение Г*= 1201,47 ч; х~ = 924 шт.; х2 = 265 шт. Все другие прямые, построенные по уравнению целевой функции и лежащие ниже линии Г*, соответствуют меньшим значениям целевой функции.
Так, линия, проходящая через начало координат, соответствует минимальному значению целевой функции Г = О. Данная задача относится к задаче целочисленного программирования при непрерывном изменении параметров, так как погрешность округления в этом случае незначительна. В случае большей размерности задачи ее геометрическое решение невозможно, так как необходимо найти точку касания в А-мерном простран- 18* 555 Г = СХ где С = (а», а2, ..., а„) при ВХ = О, В = ~ЬД, О = (Р», 32,, Р ), х; ~ О.
Задача определения пип Г может быть сведена к задаче нахождения шах Р~ -при Г» = — Г. Если ограничения имеют вид д;=~Ь,,х >Р;, у'=» то каждому такому неравенству соответствует уравнение с двумя дополнительными переменными Жс+» Жс+2 " у=» При Р; < О и неравенстве типа «больше или равно» уравнение с дополнительной переменной имеет вид — ~Ь,,х,. +х„„= — ~3,.
/'=» 16.4. Общий вид исходной задачи линейного программирования при решении ее симплексным методом П р и м е ч а н и е. В последней строке в правой крайней клетке вносится значение функции на каждой итерации с обратным знаком»- Е). Если ограничение задано в виде равенства й К, =~Ь,,х, =~3,, у=» необходимо ввести два уравнения с дополнительными переменными: Ь, х +х~,» =~3,с у'=» При ограничениях, определяющих значения независимых переменных в интервале, например, Р; < х, < Р;.», вводится дополнительная переменная х»,.» = х, — В;, и ограничение принимает вид ~~+» < Р~+1 — Р~. Алгоритм симплексного метода показан на рис.
16.7. Решение задачи получается в виде итерационной последовательности таблиц Исходная симплекс-таблица имеет вид табл. 16.4 (блок 2 на рис. 16.7). На каждой последующей итерации (номер итерации п) определяется максимальное 557 Рис. 16.7, Алгоритм симплексного метода решения задачи линейного программирования значение коэффициента а~ в уравнении целевой функции .Е Таким обра- зом, определяют переменную х„" ~независимую или дополнительную), которую будем вводить в список основных (базисных) переменных. Если все коэффициенты столбца, соответствующего переменной х„нулевые или отрицательные, задача решения не имеет. В противном случае определяют строку О и базисную переменную, которую заменит переменная х,.
Номер строки определяют в блоке 5 по минимальному отношению постоянной р," к соответствующему коэффициенту ч-го столбца. После того, как о-я строка найдена, все ее элементы делят на коэффициент Ь"„находящийся на пересечении О-й строки и ч-го столбца (блок 6). Далее вычисляют коэффициенты, с помощью которых все элементы ч-го столбца, кроме Р„"," (который равен 1), приводят к нулю (блок 7). Соответственно в блоках 11, 12 и 13 осуществляют преобразование строк сим- 558 плексной таблицы путем прибавления к каждой строке д-й строки, умноженной на коэффициент 4 (или коэффициент ~ для преобразования строки целевой функции).
Преобразование таблицы заканчивается введением переменной х„" в список базисных переменных (блок 10). Если после преобразования симплексной таблицы все коэффициенты уравнения целевой функции становятся нулевыми или отрицательными (блок 9), процесс решения заканчивается. На печать выводятся значения основных переменных, равные соответствующим значениям постоянных Р,"." (блок 8).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
