Читать контрольная по математике: "Симплекс-метод" Страница 1

назад (Назад)скачать (Cкачать работу)

Функция "чтения" служит для ознакомления с работой. Разметка, таблицы и картинки документа могут отображаться неверно или не в полном объёме!

Произвести распил 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

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

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

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

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

, поэтому разрешающий