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

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

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

Из существующих способов восстановления общей прочности корпуса судна с износами наиболее эффективным является подкрепление накладываемыми полосами []. В этой же работе рекомендованы размеры накладных полос. В частности, рекомендовано принимать размеры поперечного сечения накладных полос, определенного из условия сохранения устойчивости полос, в том числе — при сжимающих напряжениях, по следующим правилам: ширина полосы в_п=250ч300 мм; толщина полосы t_п=10ч12 мм. Длина каждой полосы должна определяться по формуле:

l_п= l_л+2а₁+2l',

где l_л — длина листа (длина сечения), м; а₁ — рамная шпация (расстояние между поперечными балками палубы или днища), м; l' = 0.5 м — часть полосы за первой и последней поперечными балками по длине полосы.

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

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

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

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

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

Всего имеется n партий материала, причем i-я партия содержит q_i единиц. Комплект состоит из m разных деталей. В комплект входит p_k деталей k-го типа. Единица каждой партии может раскраиваться s различными способами.

Пусть при j-ом способе раскроя i-ой партии полуфабрикатов получается a_ikj деталей k-го типа.

Обозначим через x_ij количество единиц i-ой партии материалов, которые следует раскроить по j-му способу. Количество деталей k-го типа, которое будет при этом получено, равно a_ikjx_ij. Количество деталей k-го типа, которое можно получить из i-ой партии полуфабрикатов, используя все способы раскроя, равно

a_ik1x_i1+ a_ik2x_i2+ a_ik3x_i3+ … + a_ikSx_Is=_irjx_ij.

Общее число деталей k-го типа можно получить, если суммировать количество деталей этого типа, выкраивая из каждой партии материалов:

раскрой технологический материал судостроение

_1kjx_1j + _2kjx_2j + … +_nkjx_nj =_ikjx_ij.

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

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

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

Для демонстрации эффективности использования ЛП в решении задач раскроя материалов в судоремонте, рассмотрим следующий пример.

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

— в первой партии — накладные полосы длиною 1 м. — в количестве 200 шт.,

— во второй партии-накладные полосы длиной 0.6 м. — в количества 250 шт.

Изготовить эти две партии можно из трех видов накладных полос (заготовок), хранящихся на складе судоремонтного предприятия:

— Первый вид заготовок — накладные полосы длиною 2 м. Стоимость одной такой полосы -100 р. Количество имеющихся в наличии таких полос (заготовок) -100 шт.

— Второй вид заготовки — накладные полосы длиною 1.4 м. Стоимость одной полосы — 60 р. Количество накладных полос этой заготовки — 200 шт.

— Третий вид заготовки — накладные полосы длиною 0.8 м. Стоимость одной полосы — 40 р. Количество накладных полос этой заготовки, имеющихся в наличии, — 50 шт.

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

с=20 p/срез.

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

Для получения элементов (накладных полос) той или иной партии используют следующие варианты раскроя заготовок:

1. Заготовки первого вида длиной 2 м можно «раскроить» тремя способами:

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

1.2. Из одной заготовки путем двух срезов получают одну накладную полосу (элемент) первой партии (1 м.) и одну накладную полосу (элемент) второй партии (0.6 м.). После двух срезов остается остаток полосы 0.4 м., который может быть реализован как металлолом по цене b2=10p. за единицу.

1.3. Из одной заготовки путем трех срезов, производимых от конца через каждые 0.6 м., получают три накладные полосы (элемента) второй партии. Остаток после раскроя 0.2 м. Этот остаток, с целью уменьшения расходов на выполнение работ, может быть реализован как металлолом по цене b1=5p. за каждую единицу.

2. Заготовки второго вида длиной 1.4 м. можно «раскроить» двумя способами:

2.1. С помощью одного среза на расстоянии 1 м. от конца можно получить из накладной полосы (заготовки) один элемент полосы первой партии (1 м.) и остаток прутка, непригодный к использованию, длиной 0.4 м. Его можно сдать в металлолом по цене b3=15 p.

2.2. Второй способ раскроя производится двумя поперечными срезами, производимыми от конца заготовки через каждые 0.6 м. В результате получаются две накладные полосы (элемента) второй партии и остаток полосы длиною 0.2 м., который может быть сдан в металлолом по цене b1=5 p.

3. Из заготовки третьего вида длиной 0.8 м. можно получить лишь одну накладную полосу (элемент) второй партии, длина которого 0.6 м. Остаток размером 0.2 м. можно сдать в металлолом по цене b1=5 p. Таким образом, раскрой заготовки третьего вида состоит в выполнении одного поперечного среза.

Используя шесть вариантов раскроя, мы можем найти расходы на реализацию каждого варианта. Введем вектор x размерностью (6 1), элементы которого соответствуют числу используемых вариантов раскроя. Расходы на выполнение одного раскроя по первому варианту составят (a1+c) рублей, а при выполнении x (1) таких раскроев они составят, очевидно, (a1+c)x (1) рублей. Аналогично для других вариантов раскроя получим:

(a1+2*c-b2)x (2),

(a1+3*c-b1)x (3),

(a2+c-b3)x (4),

(a2+2*c-b4)x (5),

(a3+c-b1)x (6).

Нетрудно видеть, что критерием качества, который следует минимизировать, является произведение вектора — строки f на вектор — столбец x и представляет собой скалярную величину — расходы на выполнение работ по подготовке двух партий накладных полос:

J=fx,

где

f=[(a1+c) (a1+2*c-b2) (a1+3*c-b1) (a2+c-b3) (a2+2*c-b4) (a3+c-b1)].

Теперь рассмотрим процедуру введения ограничений.

Число элементов первой партии прутков можно получить с помощью вектора x, если на него умножить вектор — строку:

[2 1 0 1 0 0],

а число элементов второй партии можно получить аналогично, если вектор — строку

[0 1 3 0 2 1]

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

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

A=[1 1 1 0 0 0; 0 0 0 1 1 0; 0 0 0 0 0 1];

b=[100 200 50]';

Далее могут быть заданы дополнительные ограничения на вектор переменных состояния (вектор x, элементы которого соответствуют числу выбираемых видов раскроя при минимизации критерия качества J). Минимум критерия определяется с помощью стандартной функции linprog среды MatLAB.

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

% Файл sah462. m

% Задача о раскрое материала II.

% Стоимость заготовки ai, стоимость оставшейся части

% заготовки bi, стоимость одного среза ci:

a1=100; a2=60; a3=40;

b1=5; b2=10; b3=15; b4=8;

c=20;

f=[(a1+c) (a1+2*c-b2) (a1+3*c-b1) (a2+c-b3) (a2+2*c-b4)…

(a3+c-b1)];

A=[1 1 1 0 0 0; 0 0 0 1 1 0; 0 0 0 0 0 1];

%b=[50 100 50]';

b=[100 200 50]';

Aeq=[2 1 0 1 0 0; 0 1 3 0 2 1]; beq=[200 250]';

lvb=[0 0 2 0 0 0]'; ulb=[20 56 inf 110 95 inf]';

[x, J]=linprog (f, A, b, Aeq, beq, lvb, ulb);

x1=round (x);

J1=f*x1;

[x x1]

[J J1]

beq_corr=Aeq*x1

%ПРИМЕЧАНИЕ. Для решения задачи целочисленного програм;

% мирования рекомендуется применять операцию x=round (linprog (…)),

% после чего корректировать вектор beq: beq_corr=Aeq*round (x).

% Затем внести откорректированное значение в соответствующую строку программы.

% Решение

% >> sah462

% Optimization terminated.

% ans =

% 20.0000 20.0000

% 50.0000 50.0000

% 6.6667 7.0000

% 110.0000 110.0000

% 90.0000 90.0000

% 0.0000 0

% [J J1]=

% 1.0e+004 *

% 2.5363 2.5415

%beq_corr =

% 200 251

% >>

Для получения J=25 415 р. необходимо использовать варианты раскроя в следующих количествах: x1'=[20 50 7 110 90 0].

Из содержания файла следует, что на переменные состояния введены ограничения. Так, согласно нижней границе, следует использовать не менее 2 раскроев по третьему варианту, а вектором верхней границы установлены максимально допустимые значения вариантов раскроя: для первого — 20, второго — 56, четвертого — 110 и пятого — 95. На третий и шестой варианты верхние ограничения не наложены.

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

Введение

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

Введение

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