Произвести распил 5 - метровых бревен на брусья размерами 1,5; 2,4; 3,2 м в отношении 1:2:3 так, чтобы минимизировать общую величину отходов.
Решение
Определим всевозможные способы распила бревен, указав сколько соответствующих брусьев при этом получается.
Способы Распила i | Получаемые брусья | Количество бревен, распиливаемых по i-му способу | отходы | ||
1.5 | 2.4 | 3.2 | |||
1 2 3 4 | 3 1 1 0 | 0 1 0 2 | 0 0 1 0 | x1 x2 x3 x4 | 0.5 1.1 0.3 0.2 |
Количество бревен, распиливаемых по каждому способу, обозначим х1, х2, х3, х4 соответственно. Составим математическую модель задачи. Поскольку общее количество бревен, поступающих на распил, неизвестно, будем искать их количество в процентах. Тогда x1+х2+х3+х4=1 (где 1 означает 100%).
линейный программирование симплекс метод
Учитывая количество брусьев каждого размера, получаемых при распиле одним из четырех способов и условие комплектности (1:2:3), получим следующие уравнения:
x1+х2+х3=х - для брусьев длиной 1.5 м;
х2+2х4=2х- для брусьев длиной 2.4 м;
х3=3х- для брусьев длиной 3.2 м.
Из последнего уравнения , подставив в предыдущие уравнения, получим
илиПри этом
Общая величина отходов составит . Необходимо найти минимум этой функции при заданных условиях.
Итак, имеем задачу линейного программирования:
Из второго уравнения системы ограничений следует, что х1=х2=х3=0, а при четвертом способе распила получаются только бруски в 2.4 м, что не удовлетворяет условию задачи. Таким образом данная задача не имеет допустимых решений.
Введем в рассмотрение способы распила, при которых отход превышает возможную величину бруска. Получим следующую таблицу.
Способы Распила i | Получаемые брусья | Количество бревен, распиливаемых по i-му способу | отходы | ||
1.5 | 2.4 | 3.2 | |||
1 2 3 4 5 6 7 8 | 3 1 1 0 2 1 0 0 | 0 1 0 2 0 0 1 0 | 0 0 1 0 0 0 0 1 | x1 x2 x3 x4 х5 х6 х7 х8 | 0.5 1.1 0.3 0.2 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 |
Элементы таблицы (коэффициенты при х) обозначим
Найдем начальное базисное решение.
) Выбираем четвертый столбец разрешающим.
Вычислим симплекс-отношения для положительных элементов четвертого столбцаи выберем наименьшее полученное число
, поэтому разрешающий