ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ПЛАНИРОВАНИЯ РАСКРОЯ ПИЛОВОЧНОГО СЫРЬЯ

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

В лесопильный цех ЛДП поступают бревна, рассортированные на п размерных групп. Известна спецификация пиломатериалов, которые требуется получить в результате раскроя данного объема пиловочного сырья. Задан также набор поставов для раскроя бревен каждой размерной группы. Требуется определить, какой объем бревен следует распилить по каждому из рассматриваемых поставов, чтобы выполнить спецификацию пиломатериалов при минимальном расходе пиловочного сырья.

Введем обозначения:

Ук имеющийся объем бревен к-й размерной группы, к = 1,

  • 2, ..., п
  • ?), — минимально допустимый объем выработки пиломатериалов /-го сечения, /'=1,2, ..., т (т — общее число сечений вырабатываемых пиломатериалов);

хк] искомый объем бревен к-й размерной группы, распиливаемых по у-му поставу, у =1,2, ..., Nkк количество предназначенных к использованию поставов для раскроя бревен к-й размерной группы);

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

С учетом введенных обозначений объем пиломатериалов /-го сечения, полученных в результате распиливания хк] кубометров бревен к-й размерной группы по у-му поставу, составляет ак]1 хк]. Общий объем таких пиломатериалов получают в результате суммирования этого выражения по всем поставам и размерным группам, п нк

т.е. ХХ^уЛу- Поэтому требование выработки пиломатериалов

к=1у=1

/-го сечения в объеме, не меньшем (У,., м3, реализуется в виде следующего ограничения:

п N.

Qi^> I ~ 1? 2, (3.52)

к= у=1

Если, кроме того, задан максимально допустимый объем О, выработки этих пиломатериалов, то необходимо дополнительно учесть соответствующее ограничение:

п Мк

XXаклхк] ^ (?*> I = 12,..., т. (3.53)

к= У=1

Общий объем бревен к-й размерной группы, распиливаемых

Nk

по всем рассчитанным для них поставам, равен, очевидно, X^/ty-

7=1

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

Xxkj ^vk’ к = 1,2,п. (3.54)

7=1

Переменные xkjдолжны быть неотрицательны:

xkj >0, к = 1,2,...,п; у = 1,2, ...,Nk. (3.55)

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

п Nk

XXх# min- (3-56)

fc=l7=1

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

т;

ckj — X akji»

/=1

где rrij — число сечений пиломатериалов, вырабатываемых с использованием у'-го постава.

Тогда коэффициент объемного выхода отходов для этого же постава равен

^ — Ckj — ^ ~ X akji •

/=1

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

nNk

ХХ(! - ckj)xkjmin- (3.57)

к= у=1

Совокупность соотношений (3.52)—(3.56) или (3.52)—(3.55), (3.57) — это задача линейного программирования, являющаяся математической моделью задачи планирования раскроя пиловочного сырья.

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

Пример. Решим на компьютере задачу планирования раскроя бревен с учетом качества сырья и пиломатериалов в соответствии с моделью (3.52), (3.54), (3.55), (3.57) [9]. Раскрою подлежат сосновые бревна длиной 5,5 м, диаметром 18...28 см, рассортированные на шесть размерных групп. В каждой размерной группе содержится 30% бревен 2-го и 70% 3-го сорта. Всего, таким образом, имеется 12 размерно-качественных групп сырья. В табл. 3.12 и 3.13 приведены спецификации сырья и вырабатываемых пиломатериалов соответственно.

Таблица 3.12

Диаметр, см

Объем, м3

2-го сорта

3-го сорта

Всего

18

30

70

100

20

45

105

150

22

45

105

150

24

60

140

200

26

60

140

200

28

60

140

200

Таблица 3.13

Номинальные размеры пиломатериалов, мм

Объем, м3

Сорт

толщина

ширина

60

150

56,50

0...2

60

150

52,25

3,4

50

125

57,00

0...2

50

125

42,75

3,4

32

125

83,60

0...2

32

125

71,25

3,4

25

Разная

50,00

0...2

25

»

40,00

3,4

19

»

25,00

0...2

19

»

40,00

3,4

16

»

60,00

0...4

Итого

578,35

Примечание. Длина пиломатериалов — 5,5 м.

Для всех основных сечений пиломатериалов, указанных в спецификации, составлено и рассчитано на компьютере 18 поставов с высотой бруса, равной 0,44...0,75 диаметра вершинного торца бревна. Их краткая характеристика приведена в табл. 3.14. Для бревен различных сортов одного диаметра использован постав одной структуры. Влияние сорта бревен сказывается на посортном выходе пиломатериалов. Объемный же выход пиломатериалов по поставу из бревен различных сортов считается одинаковым. Это допущение принято из-за отсутствия достоверных данных.

Таблица 3.14

Номер постава

Диаметр, см

Сорт

Постав

1

28

2

150 25 19 60 19

2

28

3

1 ’ 2 ’ 4 ’ 3 ’ 4

3

26

2

150 19 60 19

4

26

3

1 ’ 4 ’ 3 ’ 4

5

24

2

150 19 60 25 19

6

24

3

1 ’ 4 ’ 2 ’ 2 ’ 2

7

22

2

150 16 60 16

8

22

3

1 ’ 2 ’ 2 ’ 4

9

20

2

150 16 60 25 16

10

20

3

1 ’ 2 ’ Г 2 ’ 2

11

18

2

150 60 25 16

12

18

3

1 ’ Г 2 ’ 2

13

28

2

125. 25. 19. 50. 19

14

28

3

1 ’ 2 ’ 4 ’ 4 ’ 4

15

26

2

125 25 19 50 19

16

26

3

1 ’ 2 ’ 4 ’ 4 ’ 2

17

24

2

125. 25. 19. 50. 19

18

24

3

1 ’ 2 ’ 2 ’ 3 ’ 4

19

22

2

125 16 50 16

20

22

3

1 ’ 4 ’ 3 ’ 2

21

20

2

125 16 50 25

22

20

3

1 ’ 2 ’ 2 ’ 2

23

18

2

125 16 50 16

24

18

3

1 ’ 2 ’ 2 ’ 2

25

28

2

125 25 19 32 19

26

28

3

1 ’ 2 ’ 4 ’ 6 ’ 4

27

26

2

125 25 19 32 19

28

26

3

1 ’ 2 ’ 4 ’ 6 ’ 2

Номер постава

Диаметр, см

Сорт

Постав

29

24

3

126 25 19. 32. 19

30

24

3

1 ’ 2 ’ 2 ’ 5 ’ 2

31

22

2

125. 16. 32. 16

32

22

3

1 ’ 4 ’ 4 ’ 4

33

20

2

125. 16. 32. 16

34

20

3

1 ’ 2 ’ 4 ’ 4

35

18

2

125. 16. 32. 16

36

18

3

1 ’ 2 ’ 3 ’ 2

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

В табл. 3.15 приведены результаты расчета постава № 1 для раскроя бревен 2-го сорта диаметром 28 см, длиной 5,5 м, объемом 0,41 м При расчете посортного выхода пиломатериалов (графы 9 и 10 табл. 3.15) использованы соответствующие нормативы.

Таблица 3.15

Постав (запись от центра)

Расход ширины полупостава, мм

Расстояние от центра

постава

до наружной

пласти доски в мм/ долях вершинного

радиуса

Номи

нальные

размеры

доски

Полезный выход

общий

в том числе сорта, %

Число досок

Номинальная

толщина

доски, мм

Ширина, мм

Длина, м

м3

%

0...2-Й

3, 4-й

1

2

3

4

5

6

7

8

9

10

1

150

77,00

77/0,55

233,87

5,5

1

25

29,40

106/0,76

150

0,0412

10,06

6,340

3,720

2

19

23,25

129,65 /0,92

125

4,75

0,0225

5,51

3,030

2,480

23,25

152,9/1,09

75

2,0

0,0056

1,39

0,695

0,695

1

60

30,91

30,91/0,22

150

5,5

0,0495

12,07

7,600

4,470

2

60

65,42

96,33 /0,69

150

5,5

0,0990

24,14

15,210

8,930

2

19

23,25

119,58/0,85

125

5,5

0,0261

6,37

3,820

2,550

2

19

23,25

142,83 / 1,02

100

3,25

0,0123

3,01

1,505

1,505

Постав (запись от центра)

Расход ширины полупостава, мм

Расстояние

от центра

постава

до наружной

пласта доски в мм/ долях вершинного

радиуса

Номи

нальные

размеры

доски

Полезный выход

общий

в том числе сорта, %

Число досок

Номинальная

толщина

доски, мм

Ширина, мм

Длина, м

м3

%

0...2-Й

3, 4-й

1

2

3

4

5

6

7

8

9

10

Итого выход пиломатери-

алов

0,2564

62,55

38,200

24,350

60

0,1485

36,21

22,810

13,400

25

0,0412

10,06

6,340

3,720

19

0,0665

16,28

9,050

7,230

Объем отходов древесины

0,1536

37,46

Непосредственно для решения поставленной задачи из этой таблицы берут следующие данные:

  • 1) посортный выход пиломатериалов каждого сечения, % (графы 9 и 10 для строк 10... 12). Поделив эти числа на 100, получим коэффициенты аклв ограничениях (3.52);
  • 2) объем отходов древесины, равный 37,46% для данного постава, поделенный на 100, он представляет собой соответствующий коэффициент (1 — 0^) в целевой функции (3.57) (строка 13).

Величины Ук в правых частях ограничений (3.54) по ресурсам сырья приведены в графах 2 и 3 табл. 3.12. Значения ?) из ограничений (3.52) на выработку пиломатериалов содержатся в графе 4 табл. 3.13. Таким образом, исходные данные для поставленной задачи полностью определены.

Рассматриваемая задача была решена на компьютере с использованием пакета прикладных программ. Предварительно ее модель (3.52), (3.54), (3.55) и (3.57), содержащая двухиндексные переменные хк], была приведена к стандартному виду задачи линейного программирования (3.20)—(3.22) с одноиндексными переменными ху. Для этого введена сплошная нумерация поставов: у = 1, 2, ..., N,

П

где N = Переменная х. означает объем сырья, распиливае-

к=1

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

сырья, которые распиливаются по данномуу-му поставу, и равна нулю для всех остальных групп сырья. Поэтому теперь для записи ограничения по ресурсам сырья, аналогичного неравенству (3.54), приходится ввести новый параметр Ьк]. Это число равно 1, если по у-му поставу распиливают бревна к-й размерно-качественной группы, и равно нулю в противном случае. Тогда рассматриваемое ограничение можно записать в виде

N

Х^/*у -ук> к = I 2, ...,я. (3.58)

У=1

Пример. Согласно табл. 3.12 имеются бревна 2-го сорта диаметром 28 см в объеме 60 м3. Их распиливают, как видно из табл. 3.14, только по поставам № 1, 13 и 25. Поэтому соответствующее ограничение (3.58) запишется в явном виде:

*1 + *13 + *25 ^ 60. (3.59)

Вместо ограничений (3.52) и (3.55) и целевой функции (3.57) записывают соотношения аналогичного им следующего вида:

N

- 0/. = 1, 2, ..., т (3.60)

У=|

Ху >0, у = 1, 2, ..., И; (3.61)

N

^(1 - Су)Ху -> гшп. (3.62)

У=1

Запишем, например, ограничение (3.60) для пиломатериалов сорта 0—2 сечения 60x150 мм. Присвоим этой размерно-качественной группе пиломатериалов номер / = 1. Для их выработки используются поставь! № 1 — 12 (см. табл. 3.14). Поэтому имеем

аХ + <*12*2 +-- + «1 12*12 ^ 01- (3.63)

Величина 0, равна 56,5 м3 (см. табл. 3.13), а коэффициенты посорт-ного выхода пиломатериалов аи берутся из таблиц расчета поставов. Так, ап = 0,228 (см. табл. 3.15).

Для ввода в компьютерную программу исходные данные задачи (3.58), (3.60)—(3.62) сведены в матрицу, фрагмент которой представлен в табл. 3.16. В ее верхней строке, начиная с четвертой графы, приведен список переменных задачи. Индекс каждой переменной совпадает с номером постава из табл. 3.14. В первой графе таблицы пронумерованы ограничения. Номер 0 соответствует целевой функции. Номера с 1-го по 11-й присвоены ограничениям (3.60). Во второй графе в этих строках приведены сечения пиломатериалов. Строки с 12-й по 23-ю соответствуют ограничениям (3.58). Во второй графе в них вписаны значения диаметра бревен. В третьей графе указан сорт пиломатериалов и бревен. В клетке на пересечении каждой строки и графы записывается коэффициент при соответствующей переменной в рассматриваемом ограничении или в целевой функции для нулевой строки. Пустые клетки соответствуют нулевым коэффициентам. Например, ограничение (3.63) записано в первой, а ограничение (3.59) — в двенадцатой строке табл. 3.16.

Номер

Наименование

Переменные

строки

ограничений

*1

*2

*3

*4

*5

• • •

*36

Тип огра-

значение ограничении

0

Целевая функция

0,375

0,375

0,392

0,392

0,387

• • •

0,429

ничений

Нижняя

граница

Верхняя

граница

1

2

3

4

5

6

7

8

9

10

и

12

13

1

60 х 150

0...2

0,228

0,163

0,269

0,186

0,233

>

56,50

2

60 х 150

3,4

0,134

0,199

0,144

0,228

0,100

>

52,25

3

50 х 125

0...2

>

57,00

4

50 х 125

3,4

>

42,75

5

32 х 125

0...2

0,160

>

83,60

6

32 х 125

3,4

0,240

>

71,25

7

25 х разная

0...2

0,063

0,050

0,070

>

50,00

8

25 х разная

3,4

0,037

0,050

0,043

>

40,00

9

19 х разная

0...2

0,090

0,051

0,111

0,078

0,100

>

25,00

10

19 х разная

3,4

0,072

0,112

0,083

0,117

0,067

>

40,00

11

16 х разная

0...4

0,171

>

60,00

12

28

2

1

<

60

13

28

3

1

<

140

14

26

2

1

<

60

15

26

3

1

<

140

16

24

2

1

<

60

17

24

3

<

140

18

22

2

<

45

19

22

3

<

105

20

20

2

<

45

21

20

3

<

105

22

18

2

<

30

23

18

3

1

<

70

х

н

о

с

С

о

X

о

ГУ

СЗ

X

X

о,

о

н

а

о

с

аЗ

X

Т

О

X

О

^ ?

Спецификация пиломатериалов, подлежащих выработке

Толщина, мм

60

60

50

50

32

32

25

25

19

19

16

Ширина, мм

150

150

125

125

125

125

Разная

Длина, м

5,5

5,5

5,5

5,5

5,5

5,5

Разная

А

сх

и

н

<ь>

С

Сорт

0...2

3,4

0...2

3,4

0...2

3,4

0...2

3,4

0...2

3,4

0...4

С

X

%

х

X

ГА

к

Плановый объем, м3

56,50

52,25

57,00

42,75

83,60

71,25

50,00

40,00

25,00

40,00

60,00

«=г

ю

о

Объем по поставу, м3

Получено пиломатериалов по расчету,

м3

2

28

98,11

61,37

16,03

19,49

4,94

4,94

4,97

11,00

6

24

3

78,62

48,21

14,15

12,05

4,72

4,19

5,24

7,86

8

22

105,00

64,05

22,89

18,06

23,10

11

18

2

9,80

5,10

1,79

1,01

1,01

0,56

0,73

12

18

11,45

5,96

1,64

1,64

0,98

0,85

0,85

16

26

3

57,40

35,69

11,79

10,52

3,50

2,87

2,39

4,62

21

20

2

42,62

25,36

9,74

5,48

3,65

2,43

4,06

22

20

3

105,00

62,49

21,37

16,12

7,50

7,50

10,00

24

18

57,74

34,63

14,10

10,63

9,90

25

28

2

60,00

35,40

12,58

6,73

3,80

2,05

5,56

4,68

26

28

3

41,89

24,72

6,02

7,46

2,25

1,84

2,35

4,80

27

26

2

60,00

35,98

14,33

7,66

4,33

2,33

3,83

3,50

28

26

3

82,60

49,53

13,53

16,74

5,04

4,13

3,44

6,65

29

24

2

60,00

36,39

13,20

8,80

4,19

3,80

3,40

3,00

30

24

3

61,39

37,23

8,18

14,32

4,09

4,10

2,04

4,50

31

22

45,00

27,00

10,26

5,94

10,80

33

20

2

2,38

1,38

0,65

0,37

0,36

35

18

20,20

11,54

4,85

3,23

3,46

Итого

999,20

602,03

56,50

52,25

57,00

42,75

83,60

71,25

50,00

41,59

33,22

50,61

63,26

Недовыпол-

нение, %

Перевыпол-

3,98

32,88

26,53

5,43

нение, %

Результаты решения задачи сведены в табл. 3.17. Из таблицы видно, что объем выработки пиломатериалов толщиной 32...60 мм равен плановому заданию, а для остальных толщин превышает его. В целом перевыполнение плана выработки пиломатериалов не превышает 5%. Из анализа данных в графах 2—4 табл. 3.17 видно также, что ресурсы сырья по всем его размерно-качественным группам израсходованы полностью, за исключением бревен 3-го сорта диаметром 18 см. По ним предусматривается недорасход в объеме 0,8 м3. Найденному оптимальному решению соответствует значение целевой функции, равное 396,166 м3.

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

 
< Пред   СОДЕРЖАНИЕ     След >