Симплекс-метод

Размещено на http://www.allbest.ru/

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

Решение

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

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

x₁+х₂+х₃+х₄=1 (где 1 означает 100%).

линейный программирование симплекс метод

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

3x₁+х₂+х₃=х - для брусьев длиной 1.5 м;

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

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

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

 или

При этом

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

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

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

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

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

При этом

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

.

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

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

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

1)

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

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

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

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

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

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

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

На месте а₃₄ ставим 1.

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

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

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

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

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

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

Получили первоначальное базисное решение х₄=0.2, х₆=0.2, х₈=0.6, х₁=х₂=х₃=х₅=х₇=0, F(х)=1.82. Это решение не является оптимальным, поскольку в F - строке есть отрицательные элементы.

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

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

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

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

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

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

х₃=0.25, х₄=0.25, х₈=0.5, х₁=х₂=х₅=х₆=х₇=0, .

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

Размещено на Allbest.ru