Задать вопрос:





Статьи

Статьи>> ПТИМИЗАЦИЯ РАСКРОЯ МАТЕРИАЛОВ В МАШИНОСТРОЕНИИ

ПТИМИЗАЦИЯ РАСКРОЯ МАТЕРИАЛОВ В МАШИНОСТРОЕНИИ

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

1. Раскрой одномерных материалов


В качестве одномерных материалов могут выступать листы, рулоны, а также длинномерный прокат. Заготовки из круглого проката, профилей и труб, предназначенные для гибки и других операций, нередко имеют длину l, соизмеримую с длиной исходного материала L. При разрезке последнего на заготовки одного размера возможны значительные отходы из-за некратности L по отношению к . Для сокращения отходов в условиях многономенклатурного производства применяют групповой раскрой, при котором одну трубу или штангу профиля разрезают на заготовки различной длины из заданной номенклатуры. Аналогичным образом разрезают листы на полосы (рис. 1). В данном случае разделение материала происходит в направлении одного размера листа и считается одномерным.


1.1. Применение линейного программирования


Оптимизация раскроя одномерного материала сводится к решению задачи линейного программирования (ЛП).
Исходные данные: значения L и некоторого перечня длин [l], а также требуемое число (партии) [N] заготовок.
Рассмотрим конкретный пример раскроя листов на полосы:
L= 1000 мм, [1]= 380, 290, 180 мм.
Требуемое число заготовок соответственно: [N] = 15, 10, 20 шт.
Оценочная функция — число листов, расходуемое на выполнение всего заказа.


Рис.1. Пример группового раскроя листа 1000х2000мм на продольные полосы

Различные планы разрезки одного листа (табл. 1) составлены в результате полного рассмотрения вариантов по принципу убывания числа заготовок в одном плане, начиная с более длинных. Данный приоритет сохраняется при доукомплектовании плана заготовками меньшей длины, пока отход не оказывается меньше lmin, в данном примере это l3 = 180 мм.


1. Варианты раскроя листа по размеру 1000 мм на полосы шириной l1, l2, l3

№ плана

Число полос шириной, мм

Отход, мм

Обозначение переменной

l1 = 380

l2= 290

l3=180

1

2

0

1

60

x1

2

1

2

0

40

x2

3

1

1

1

150

4

1

0

3

80

x3

5

0

3

0

130

6

0

2

2

60

x4

7

0

1

3

170

8

0

0

5

100

Размер отхода в соответствующей графе табл. 1 рассчитан без учета припуска на разрезку, поскольку операция выполняется на ножницах. Например, согласно плану 6 (см. рис. 1), размер отхода 60 = L- 2/2-2/3. Если применяют оборудование стружкообразующего или термического действия, концевой отход уменьшается на величину, равную произведению ширины реза на число резов.
Планы 5, 8 относятся к примитивным, они содержат заготовки одной длины соответственно l1, l2 и сравнительно просты в реализации, но в данном примере неэкономичны по причине большого отхода. Исключим их при постановке задачи ЛП, равно как и заведомо неприемлемые по тому же показателю отходов комбинированные планы 3, 7. Остальным поставлены в соответствие переменные (см. табл. 1). Каждая переменная х, обозначает число листов, для разрезки которых будет применен соответствующий план. Необходимо найти значения переменных, обеспечивающиеминимумоценочнойфункции

т.е. общего числа израсходованных листов.
Система уравнений ограничений учитывает требуемые числа заготовок [N]:

Коэффициентами при неизвестных являются числа заготовок в соответствующих столбцах табл. 1. Например, первое уравнение (2) ограничивает число заготовок длиной l1= 380 (15 шт.). Коэффициенты содержатся в планах, которым соответствуют переменные х1, х2 , х3. Первый план содержит две таких заготовки, остальные — по одной. Эти числа и являются коэффициентами в выражении 2х1+ х2+ х3 (см. (2)). Значения х1, х2, х3.должны быть такими, чтобы данная сумма равнялась 15. Аналогично составлены и другие ограничения.
Уравнения (1), (2) линейны (отсюда и термин — линейное программирование), в зависимости от общего числа переменных п они описывают прямые (п = 2), плоскости (n = 3) или гиперплоскости (n > 3). Система ограничений (2) определяет границы так называемой области допустимых решений (ОДР): многоугольника, многогранника или гипермногогранника в n-мерном пространстве. Минимум оценочной функции можно найти простым перебором вариантов решения, поочередно подставляя координаты вершин ОДР, т.е. соответствующие значения переменных в уравнение оценочной функции. Существуют методы, ускоряющие решение задачи. Применим один из них — так называемый симплекс-метод Д. Данцига, используя преобразование таблиц с разрешающим элементом.
Преобразование начинают с табл. 2, приведенной ниже, которая содержит уравнения (2), записанные в виде

а также уравнение (1).

Таблица 2

х1

х2

х3

х41

1

0 =

2

1

1

0

-15

0 =

0

2

0

2

-10

0=

1

0

3

2

-20

z=

1

1

1

1

0

Подчеркнутый элемент выбран в качестве разрешающего, его роль сформулирована ниже. Выбор разрешающего элемента на данном этапе преобразований определяется необходимостью избавиться от отрицательных чисел в правом столбце. Для этого находим минимальное отношение элементов, которые принадлежат одной строке и содержат в качестве числителя отрицательное число правого столбца. В данном случае таковым является отношение —20/1, оно меньше других подобных, например —10/2. Знаменатель найденного отношения становится разрешающим элементом (подчеркнут в табл. 2); содержащие его строка и столбец также называются разрешающими. Заметим, что разрешающий элемент должен быть отличным от нуля.
Алгоритм преобразования таблиц представим состоящим из трех этапов. На первом этапе заготавливают форму новой таблицы, у которой, по сравнению с предыдущей, меняют местами символы, находящиеся вверху разрешающего столбца и слева от разрешающей строки. В данном случае это приведет к перемещению символа х1. из столбца в строку, а также к замене 0-строки на 0-столбец. Последний не будет включен в новую таблицу, как не имеющий значения, поскольку все его числа становятся коэффициентами при нуле.
На втором этапе разрешающий столбец остается без изменений, числа разрешающей строки, кроме разрешающего элемента, записывают в новую таблицу с обратными знаками. Остальные элементы таблицы (разумеется, кроме левого столбца и верхней строки, где располагаются переменные) пересчитывают по правилу прямоугольника и затем переносят в новую таблицу. Проиллюстрируем это правило с помощью представления фрагмента преобразуемой таблицы в общем виде (см. табл. 3).


Таблица 3

а

b

с

f

g

h

Формулы новых значений пересчитываемых элементов:

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

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


Таблица 4

х2

х3

х4

1

0 =

1

-5

-4

25

0 =

2

0

2

-10

х1=

0

-3

-2

20

z=

1

-2

-1

20

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

Таблица 5

х2

х3

1

0 =

5

-5

5

х4 =

-1

0

5

х1=

2

-3

10

z=

2

-2

15

Отсутствие отрицательных чисел в правом столбце является признаком выхода на условно допустимое решение задачи. Приравнивают к нулю переменные, расположенные в верхней строке (х2= О, х3 = 0), и получают: х1= 10, х4 = 5, т.е. 10 листов подлежат разрезке по плану 1 и пять листов — по плану 6 (см. табл. 1). Перечисленные листы содержат 20 длинных, 10 средних и 20 коротких заготовок, что превышает заказанную партию (15, 10, 20) на пять длинных заготовок.
Ясно, что полученное условно допустимое решение не может считаться оптимальным. На это указывает и формальный признак — наличие хотя бы одного отрицательного числа в Z-строке. В столбцах, содержащих такие числа, должны быть и другие отрицательные элементы. Каждый из них рассматривают в качестве знаменателя отношения, числитель которого — крайний правый элемент той же строки. В данном примере имеем два подобных отношения: 5/-5, 10/-3. Разрешающим элементом должен быть знаменатель наибольшего из этих отношений (подчернут в табл. 5). Результат очередного преобразования, имеющего целью избавиться от отрицательных чисел в Z-строке, представлен в табл. 6.

Таблица 6

х2

1

х3 =

1

1

х4 =

-1

5

х1=

-1

7

z=

1

13

Полученная таблица содержит искомое решение задачи, на что указывает отсутствие отрицательных чисел в Z-строке и правом столбце. Присваиваем нулевые значения переменным, оставшимся в верхней строке (в данном случае х2), остальные переменные равны соответствующим числам правого столбца: х1 = 7, х3 = 1, х4 = 5. Искомый минимум целевой функции Z= 13 также присутствует в таблице.
Для проверки полученного решения обратимся к табл. 1. По плану 1 будет раскроено семь листов (х1 = 7), это дает 14 полос длиной l1= 380 мм и семь полос длиной l3 = 180 мм. План 2 не нашел применения, хотя и характеризуется наименьшим отходом. По плану 4 (х3= 1) получаем недостающую полосу длиной l1 = 380 мм и 3 полосы длиной l3 = 180 мм; по плану 6 (х4= 5) соответственно по 10 полос длиной l2= 290 мм и l3 = 180 мм.
Рассмотренный пример довольно прост, и найденное решение (х1 = 7, х3 = 1, х4 = 5. ) не является единственным. Такое же значение minZ= 13 можно получить при другом плане раскроя, применив так называемый метод проб и ошибок. Здравый смысл подсказывает, что для получения 10 полос длиной l2 = 290 мм целесообразно раскроить пять листов по плану 2 с минимальным отходом. Тогда для доукомплектования партии полос длиной l1= 380 мм необходимо раскроить пять листов по плану 1, а недостающие 15 полос длиной l3 = 180 мм можно получить по плану 8. Однако в реальных ситуациях, когда номенклатура заготовок исчисляется десятками или сотнями, более эффективно применение математических методов. По сравнению с планами, которые можно назвать рациональными, достигается экономия порядка нескольких процентов расхода металла. В абсолютном выражении она может выразиться в тоннах и более.
Из восьми возможных планов раскроя (см. табл. 1) в уравнениях задачи ЛП фигурировали четыре, выбранных с учетом величины отхода, а также требуемого числа заготовок
([N] = 15, 10, 20). Эти числа согласуются с соотношениями чисел различных заготовок, содержащихся в выбранных планах раскроя. При других исходных данных размерность задачи (число неизвестных) может быть увеличена. Например, при [N] = 15, 10, 100 нельзя обойтись без плана 8, так как любой другой план не обеспечит требуемого отношения числа коротких заготовок к длинным и средним.
На основе рассмотренного симплекс-метода созданы компьютерные программы, однако размерность задач, решаемых в условиях многономенклатурного производства, может быть настолько большой, что строгие подходы к оптимизации раскроя трудно реализовать даже с помощью ЭВМ. В таких случаях применяют эвристические методы и алгоритмы, они обеспечивают проектирование планов, по крайней мере, близких к оптимальным, за приемлемое время. Сказанное относится прежде всего к задачам, постановка которых усложнена дополнительными условиями [1].
Чаще всего это условие Lmax ≥ L Lmin означает возможность выбора размера исходного материала из некоторого множества значений. Например, листы их холоднокатаной стали в зависимости от толщины имеют ширину 500...2300 мм и длину 1000...6000 мм. Всего стандартом предусмотрено более 300 типоразмеров. Для конкретной толщины число типоразмеров намного меньше, тем не менее варьирование хотя бы несколькими значениями L существенно расширяет область поиска оптимального решения.
Также возможны предпосылки для варьирования размерами заготовок . Если имеется в виду ширина полос, отрезаемых от листа
и используемых в дальнейшем для вырубки деталей в штампе, то размер li, во многих случаях зависит от технологического процесса изготовления указанных деталей, параметры которого могут быть изменены с целью экономичного раскроя листов.
В работе [1] дана постановка задачи раскроя плетей, состоящих из труб, сваренных встык. Речь идет о производстве теплообменников большой длины (порядка нескольких десятков метров). Расположение сварных стыков теплообменника регламентируется в довольно широких пределах. Важно только, чтобы они находились на достаточном удалении от изогнутых участков.
Приведен пример решения подобной задачи на одном из котельных заводов. Трубы длиной 9191 мм, поставляемые металлургической промышленностью по специальному заказу, сваривают в непрерывную плеть, а затем отрезают от нее заготовки секций змеевика. Длина комплекта заготовок составляет величину того же порядка, что и длина исходной трубы; расположенные на заготовках сварные швы плети не должны оказаться в зоне последующей гибки. Варьируя очередностью отрезки заготовок различных секций, удается выдержать все ограничения и исключить отходы труб, не считая стружки, образующейся в процессе резки.
Наиболее сложной является оптимизация раскроя рулонного материала на ленты, широко используемые в листоштамповочном производстве. Кроме размеров L и [l] (в данном случае это значения ширины рулона и лент) необходимо учитывать различную длину последних. Она зависит от потребных значений длины различных лент, которые могут составлять от нескольких десятков до нескольких сотен метров в расчете на месячную программу выпуска продукции.
Чтобы свести задачу к одномерной, назначают некоторую единичную длину лент, приемлемую в техническом отношении, например 10 м. Число [N] лент, соответствующее перечню их ширины [1], подсчитывают, разделив требуемые длины на единичную и округлив результаты. Получают исходные данные для решения задачи одномерного раскроя, однако из-за округленных [N] после раскроя образуется избыток одних лент и возможен недостаток других. Поэтому проектирование раскроя рулона для следующей программы выпуска той же продукции выполняют заново, откорректировав значения потребной длины лент.
Листы и длинномерный прокат разрезают последовательно, отделяя с помощью ножниц, пильных и других станков заготовки одну за другой. В отличие от них рулоны разрезают на ленты одновременно по всей ширине, на которой располагают набор дисковых ножей. Расстояния между соседними парами ножей соответствуют значениям ширины лент, отрезаемых в соответствии с реализуемым планом раскроя. Смена плана требует трудоемкой переустановки дисковых ножей.
Вместо постоянной корректировки планов раскроя рулонов на ленты возможно использование избытка одной ленты для покрытия дефицита другой при условии, что ширина первой li ненамного больше, чем ширина второй li. В результате такой замены образуется дополнительный отход материала, площадь которого равна произведению разности li—lj на длину покрываемого дефицита j-й ленты. Минимизация отходов такого рода на заданном множестве лент также сводится к решению задачи ЛП [2].

1.2. Решение систем уравнений

Автоматизированные рабочие места технологов целесообразно оснащать специальными компьютерными программами проектирования оптимального раскроя, в том числе одномерного. Относительно простые задачи можно решать универсальными средствами, включая ручной счет, как это было сделано выше и предстоит сделать в примере со следующими исходными данными:
L= 1000 мм, [l] = 370, 300, 230 мм.

В табл. 7 представлены все возможные планы раскроя листа на полосы, содержащиеся в заданном перечне.


7. Варианты раскроя листа по размеру 1000 мм на полосы шириной l1, l2, l3

№ плана

Число полос шириной, мм

Отход, мм

Обозначение переменной

l1 =370

l2= 300

l3 = 230

1

2

0

1

30

x1

2

1

2

0

30

x2

3

1

1

1

100

4

1

0

2

170

5

0

3

0

100

6

0

2

1

170

7

0

1

3

10

x3

8

0

0

4

80

Ограничим число переменных задачи тремя, получив таким образом замкнутую систему уравнений ограничений, число которых равно числу переменных; необходимые числа заготовок записаны символами N1(l1 = 370мм), N2(l2= 300 мм), N3(l3 = 230 мм):

2x1+x2=N1
2x2+x3=N2
x1+3x3=N3


Сокращая до минимума (в данном случае до трех) число переменных, исходили из того, что три соответствующих плана существенно экономичнее остальных (см. табл. 7). Однако такой подход не всегда является оправданным, как это будет показано в конце данного параграфа. Система (3) при заданных значениях N1, N2, N3 имеет единственное решение. Запишем его в общем виде с учетом того, что значения переменных не могут быть отрицательными:



Область допустимых решений системы вида (4) ограничена в пространстве координат N1, N2, N3. Иначе говоря, соотношения между N1, N2, N3 не могут быть абсолютно произвольными. Например, при N1= N2 из второго и третьего уравнений системы (3) следует: 3,5N1 >N3 > 0,25N1,. Область допустимых значений N1, N2, N3 для данного примера можно представить геометрически (рис. 2). Она ограничена тремя плоскостями, образующими бесконечную трехгранную призму с вершиной в начале координат и ребрами, расположенными в координатных плоскостях.


Рис. 2. Область допустимых решений системы неравенств(4)

Уравнения ребер (рис. 2) получены из соотношений числа различных заготовок в планах раскроя (см. табл. 7). Если принять N1= 0, то окажется, что из трех переменных отлична от нуля только х3, поскольку соответствующий ей план не содержит широких заготовок. Соотношение числа других заготовок в этом плане 3:1, следовательно, в координатной плоскости N1= 0 уравнение ребра ОДР: N3= 3N2. Аналогично получаем уравнения ребер: N1= 2 N2 при N2 = 0 и N2 = 2N1, при N3 = 0.
Если в результате решения системы уравнений, подобной (3), хотя бы одна переменная окажется отрицательной, значит, заданные значения N1, N2, N3.находятся за пределами ОДР системы неравенств (4). В таком случае необходимо увеличить число переменных добавлением других возможных планов раскроя листа к отобранным ранее. Например, в систему уравнений (3) при N1= N2 и N3= 4N1следует добавить переменную х4, поставив ее в соответствие плану 8:

12=N1
23= N2
х1+3х3+4х4= N2


Детерминированное решение становится невозможным, поэтому вводим оценочную функцию (1) и получаем рассмотренную ранее задачу ЛП.

1.3. Получение целочисленных решений

Одна из проблем оптимизации раскроя связана с получением нецелочисленных решений, что противоречит физическому смыслу переменных xi . Если округлять их произвольным образом до целых чисел, можно получить далеко не лучший план раскроя. Строгий метод исключения нецелочисленных значений xi предложенный Р. Гомори, предусматривает ввод дополнительных ограничений в систему уравнений (2) и постепенный выход на лучшее целочисленное решение. Компьютерные программы решения задач ЛП могут автоматически корректировать разрешающую систему уравнений. Соответствующий алгоритм разделяет исходную область допустимых решений на подобласти, исключая определенные части ОДР. Например, при получении значения xi = 5,72 вводятся дополнительные ограничения: xi < 5 и xi > 6, поcле чего задача решается повторно. Последовательное применение подобных итераций позволяет избавиться от всех нецелочисленных значений переменных, однако полученные числа заготовок могут отличаться от заданных в большую сторону.


1.3.1. Графический метод


Задача с двумя переменными имеет наглядную геометрическую интерпретацию, проиллюстрируем ее простым примером:



В табл. 8 представлены возможные варианты раскроя листа на полосы, из которых отбираем наиболее экономичные - планы 1, 2.


8. Варианты раскроя листа по размеру 1000 мм на полосы шириной l1, l2

№ плана

Число полос шириной, мм

Отход,мм

Обозначение переменной

l1= 270

l2= 150

1

3

1

40

x1

2

2

3

10

x2

3

1

4

130

4

0

6

100

Имея два уравнения

с двумя неизвестными, вычисляем: x1 = 1,86; x2= 4,71 (с точностью до сотых). Общее число раскраиваемых листов Z = x1+ x2 = 6,57.
Найденные значения x1 и x2 с практической точки зрения абсурдны. Так, из 1,86 листа, разрезанного по плану 1, получается 5,64 широкой полосы (l= 270 мм) и 1,86 узкой, недостающие 9,36 широкой полосы и 14,14 узкой содержатся в 4,71 листа, разрезанного по плану 2.
В ряде случаев подобные решения можно откорректировать, не меняя их по существу. В данном примере принимают x1= 2; x2 = 4, получая из этих шести листов 14 широких и 14 узких полос. Остальные две узкие и одну широкую полосы отрезают от седьмого листа, ширина остатка (430 мм) вполне допускает его дальнейшее использование.
Для иллюстрации метода Р. Гомори перейдем от ограничений, записанных в виде уравнений (5), к соответствующим неравенствам:


Рис.3. Область допустимых решений:
а-при ограничениях(6); б-с дополнительными ограничениями(7);
в- с дополнительными ограничениями(8)

Им соответствует ОДР, заштрихованная на рис. 3, а.
Приведенному выше нецелочисленному решению задачи соответствуют координаты точки пересечения прямых (5).Исключим из ОДР эту точку и ее окрестности вводом дополнительных ограничений:

На рис. 3, б заштрихована измененная ОДР, оптимальное решение может принадлежать любой из ее вершин. Одна имеет целочисленные координаты x1= 1; x2 = 6), координаты другой: x1 = 2; x2 = 4,66. Исключаем из ОДР нецелочисленную координату x2 с помощью дополнительных ограничений по x2 , аналогичных (7):



Координаты всех вершин полученной ОДР отвечают требованию целочисленности (см. рис. 3, в). В принципе, могло потребоваться более двух корректировок ОДР, однако число их всегда конечно независимо от числа переменных. Двум из трех вершин ОДР на рис. 3, в соответствуют минимальные целочисленные значения Z=x1+x2 = 7, но различные значения переменных соответствуют различным комплектам полос (N1= 15, N2 = 19) и (N1= 16, N2= 17). Сравнивая эти решения с полученным ранее нецелочисленным Z= 6,57 с округлением в меньшую сторону до 6, исходят из чисто практических предпочтений в пользу любого из них.

1.3.2. Применение метода преобразования таблиц


Для решения задачи с тремя переменными используем метод преобразования таблиц с разрешающим элементом, рассмотренный в п. 1.1, и данные табл. 1, подготовленные для проектирования раскроя листов по размеру L= 1000 мм на полосы: [l] = 380, 290, 180 мм. Требуемые числа полос [N] = 10, 12, 20 мм отличаются от приведенных в п. 1.1; соответственно откорректируем систему уравнений ограничений (2):



Оценочная функция — число листов, расходуемое на выполнение всего заказа, описывается управлением (1). Занесем уравнения (9) и (1) в табл. 9, в табл. 10—12 показаны этапы преобразований и конечный результат.

Таблица 9

x1

x2

x3

x4

1

0 =

2

1

1

0

-10

0 =

0

2

0

2

-12

0 =

1

0

3

2

-20

z=

1

1

1

1

0

Таблица 10

x2

x3

x4

1

0 =

1

-5

-4

30

0 =

2

0

2

-12

x1=

0

-3

-2

20

z=

1

-2

-1

20

Таблица 11

x2

x3

1

0 =

5

-5

6

x4=

-1

0

6

x1=

2

-3

8

z=

2

-2

14

Таблица 12

x2

1

x3=

1

1.2

x4=

-1

6

x1=

-1

4.4

z=

0

11.6

Исключим нецелочисленное значение x3= 1,2 с помощью дополнительных ограничений:

Введем вспомогательные переменные y1> О, y2> О, y3> 0, y4>0, связав их с уравнениями (9) и дополнительным ограничением
x3< 1:

Нулевые значения y1, y2, y3 соответствуют заданным числам полос: 10, 12, 20; положительные — завышенным. Возможное завышение числа полос связано с переходом от нецелочисленного решения к целочисленному. Ниже приведены табл. 13, адекватная системе уравнений (11), и ее преобразования; разрешающие элементы подчеркнуты.
Разрешающие элементы таблиц 13, 14 выбраны в соответствии с правилом избавления от отрицательных чисел в правом столбце, что является признаком допустимого решения. Первое допустимое решение содержится в табл. 15: y3= 0, x2= 0, x3 = 0,
y2= 0, y1= 6, x4=6, x1=8, y4=1, Z = 14. Здесь, как и в п. 1.1, переменные верхней строки таблицы приравнены к нулю, при этом переменные левого столбца равны числам правого столбца. Согласно этим значениям переменных восемь листов раскраиваются по плану 1 и шесть — по плану 6. Планы приведены ранее в табл. 1 (им соответствуют переменные x1 и x4). При x4= 6, x1= 8 получается шесть лишних заготовок длиной 380 мм, на что указывает значение y1= 6 (см. табл. 15).


Таблица 13

x1

x2

x3

x4

1

y1 =

2

1

1

0

-10

y2 =

0

2

0

2

-12

y3 =

1

0

3

2

-20

y4 =

0

0

-1

0

1

Z =

1

1

1

1

0

Таблица 14

y3

x2

x3

x4

1

y1 =

2

1

-5

-4

30

y2 =

0

2

0

2

-12

x1=

1

0

3

-2

20

y4 =

0

0

-1

0

1

Z =

1

1

-2

-1

20

Таблица 15

y3

x2

x3

y2

1

y1 =

2

5

-5

-2

6

x4=

0

-1

0

0,5

6

x1=

1

2

3

-1

8

y4 =

0

0

-1

0

1

Z =

1

2

-2

-0,5

14

Таблица 16

y3

x2

y4

y2

1