Способы распила бревен,

Произвести распил 5 – метровых бревен на брусья размерами 1,5; 2,4; 3,2 м в отношении 1:2:3 так, чтобы минимизировать общую величину отходов.

Решение

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

Способы

Распила

Получаемые брусья

Количество бревен,

распиливаемых по

i-му способу

отходы

1.5

2.4

3.2

0.5

1.1

0.3

0.2

Количество бревен, распиливаемых по каждому способу, обозначим х1, х2, х3, х4 соответственно.

Составим математическую модель задачи. Поскольку общее количество бревен, поступающих на распил, неизвестно, будем искать их количество в процентах. Тогда

x1+х2+х3+х4=1 (где 1 означает 100%).

Учитывая количество брусьев каждого размера, получаемых при распиле одним из четырех способов и условие комплектности (1:2:3), получим следующие уравнения:

3x1+х2+х3=х – для брусьев длиной 1.5 м;

х2+2х4=2х– для брусьев длиной 2.4 м;

х3=3х– для брусьев длиной 3.2 м.

Из последнего уравнения , подставив в предыдущие уравнения, получим

или

При этом

Общая величина отходов составит

. Необходимо найти минимум этой функции при заданных условиях.

Итак, имеем задачу линейного программирования:

Из второго уравнения системы ограничений следует, что х1=х2=х3=0, а при четвертом способе распила получаются только бруски в 2.4 м, что не удовлетворяет условию задачи. Таким образом данная задача не имеет допустимых решений.

Введем в рассмотрение способы распила, при которых отход превышает возможную величину бруска. Получим следующую таблицу.

Способы

Распила

Получаемые брусья

Количество бревен,

распиливаемых по

i-му способу

отходы

1.5

2.4

3.2

х5

х6

х7

х8

0.5

1.1

0.3

0.2

3.5

2.6

1.8

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

При этом

Функция отходов примет вид

Получаем следующую задачу линейного программирования:

Решим ее симплекс методом.

Будем искать . Запишем данные задачи в таблицу.

Базисные переменные	х1	х2	х3	х4	х5	х6	х7	х8	bi
	1	1	1	1	1	1	1	1	1
	3	1		0	2	1	0		0
	0	1		2	0	0	1		0
-F	0.5	1.1	0.3	0.2	2	3.5	2.6	1.8	0

Элементы таблицы (коэффициенты при х) обозначим

Найдем начальное базисное решение.

2) Выбираем четвертый столбец разрешающим.

Вычислим симплекс-отношения для положительных элементов четвертого столбца и выберем наименьшее полученное число

, поэтому разрешающий элемент а34=2.

Элементы второй строки делим на а34=2.

Элементы четвертого столбца заменяем 0.

На месте а34 ставим 1.

х4 переходит в столбец базисных переменных.

Остальные элементы таблицы пересчитываем по формуле ,

где - разрешающий элемент.

Базисные переменные	х1	х2	х3	х4	х5	х6	х7	х8	bi
	1	0.5		0	1	1	0.5		1
	3	1		0	2	1	0		0
х4	0	0.5		1	0	0	0.5		0
-F	0.5	1	0.367	0	2	3.5	2.5	1.867	0

3) Выберем шестой столбец. Находим , тогда разрешающий элемент а26=1.

Пользуясь вышеизложенными правилами, заполняем следующую таблицу.

Базисные переменные	х1	х2	х3	х4	х5	х6	х7	х8	bi
	-2	-0.5		0	-1	0	0.5		1
х6	3	1		0	2	1	0		0
х4	0	0.5		1	0	0	0.5		0
-F	-10	-2.5	-1.97	0	-5	0	2.5	3.034	0

4) Теперь нужно записать базисную переменную в первую строку. В восьмом столбце единственный положительный элемент , поэтому а18= - разрешающий.

Базисные переменные	х1	х2	х3	х4	х5	х6	х7	х8	bi
х8	-1.2	-0.3	0.4	0	-0.6	0	0.3	1	0.6
х6	2.6	0.9	0.8	0	1.8	1	0.1	0	0.2
х4	-0.4	0.4	-0.2	1	-0.2	0	0.6	0	0.2
-F	-6.36	-1.59	-3.18	0	-3.18	0	1.59	0	-1.82

Получили первоначальное базисное решение х4=0.2, х6=0.2, х8=0.6, х1=х2=х3=х5=х7=0, F(х)=1.82. Это решение не является оптимальным, поскольку в F – строке есть отрицательные элементы.

5) Перейдем к новому решению.

Наибольший по модулю отрицательный элемент в F – строке – это -6.36. Поэтому разрешающий столбец – первый.

Единственный положительный элемент в первом столбце а21=2.6, он и будет разрешающим.

х1 занимает место х6 среди базисных переменных. Далее выполняем еще один шаг симплекс-метода и получаем новую таблицу.

Базисные переменные	х1	х2	х3	х4	х5	х6	х7	х8	bi
х8	0	0.115	0.769	0	0.231	0.461	0.346	1	0.692
х1	1	0.346	0.308	0	0.692	0.385	0.038	0	0.077
х4	0	0.538	-0.077	1	0.077	0.154	0.615	0	0.231
-F	0	0.612	-1.223	0	1.223	2.446	4.77	0	-1.33

6) Полученное решение не является оптимальным, поскольку в последней строке есть отрицательный элемент. Третий столбец разрешающий. Находим симплексное отношение : . Разрешающий элемент а23=0.308.

Базисные переменные	х1	х2	х3	х4	х5	х6	х7	х8	bi
х8	-2.5	-0.23	0	0	-1.5	-0.5	0.25	1	0.5
х3	3.25	1.12	1	0	1.27	1.25	0.12	0	0.25
х4	0.25	0.63	0	1	0.25	0.25	0.63	0	0.25
-F	4	2	0	0	4	4	5	0	-1.025

Так как в последней строке целевой функции нет отрицательных оценок, то найденное решение оптимально:

х3=0.25, х4=0.25, х8=0.5, х1=х2=х5=х6=х7=0, .

Ответ: чтобы выполнить условие задачи, необходимо 25% бревен распиливать третьим способом, 25%- четвертым способом и 50% восьмым способом. При этом минимальная средняя величина отходов составит 1.025 м с каждого бревна.

Способы распила бревен,