Материал: 4708

36

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

Таблица 14

Форма симплексной таблицы

Вычисление величин индексов

Для столбца X1: 1(-1) – (-1) = 0; для столбца X2: 1(-1) – (-1) = 0; для столбца X3: 1(-1) - (-1) = 0; для столбца X4: 0,333(-1) + 0,667(-1) + 0(-1) - (-1) = 0; для столбца X5: 0,667(-1) + 0,333 (-1) + 0(-1) - (-1) = 0; для столбца X6: 0,333(-1) + 0(-1) + 0,75(-1) – (-1) = -0,083; для столбца X7: 0,667(-1) + 0(-1) + 0,25(-1) - (-1) = + 0,083; для столбца X8: 0(-1) + 0,333(-1) + 0,75(-1) – (-1) = - 0,083; для столбца X9: 0(-1) + 0,667(-1) + 0,5(-1) - (-1) = - 0,167; для столбца X10: 0(-1) + 1 (-1) + 0,25(-1) – (-1) = - 0,25; для столбца X11: 0,333(-1) + 0,333(-1) + 0,5(-1) – (-1) = - 0,166.

С некоторой особенностью определяется индекс для столбца свободных членов уравнений. Первоначально соблюдается такая же методика, что и для других столбцов: 25 (– 1) + 26,667 (– 1) + 25 (– 1) = – 76,667. Далее допускаются, что по столбцу свободных членов в целевой строке нуль, тогда – 76,667 – 0 = – 76,667. Так как методика его вычисления отлична, его помещают в отдельной строке. Величина целевой функции с обратным знаком соответствует общему количеству досок; величина свободных членов – это количество досок, раскраиваемых по схемам, указанным в столбце обозначения базисных переменных.

Наличие отрицательных значений индексов в индексной строке указывает на неоптимальность решения, представленного в табл. 15. Переход от неоптимального решения к следующему, более близкого к оптимальному, называет-

37

ся «итерацией». При переходе к следующей симплексной табл. 16 первоначально определяются ключевой столбец, ключевая строка и ключевое число. Ключевым столбцом называется столбец, расположенный в основной части матрицы и содержащий наибольшее по абсолютной величине отрицательное число в индексной строке.

В ключевой строке содержится наименьшее положительное частное от деления элементов столбца свободных членов на соответствующие элементы ключевого столбца (отрицательные, нулевые элементы ключевого столбца при этом не берутся в расчет). Ключевое число лежит на пересечении ключевого столбца и ключевой строки. В индексной строке наибольшее по абсолютной величине число 0,667 находится в столбце Х9, который и будет ключевым в первой симплексной таблице (табл. 15). Частное от деления 26,667 на 0,667 равно 39,98, а частное от деления 25 на 0,5 равно 50, следовательно ключевая строка Х2, а ключевое число 0,667.

Первым шагом в составлении второй симплексной таблице является нахождение главной строки, которая получается путем деления всех элементов ключевой строки на ключевое число. Выделим главную строку второй симплексной таблицы и покажем ее в табл. 16.

В пересечении столбца обозначения базисных переменных с главной строкой вместо старой переменной (в нашем примере Х2) ставят переменную, стоящую в начале ключевого столбца (в нашем примере Х9).

Все элементы табл. 16, кроме тех, которые входят в главную строку, называют производными от чисел табл. 15. Их находят по формуле

где АВ – искомое число, производное числу В; В – число из предыдущей симплексной таблицы, которое заменяется

производным числом в последующей симплексной таблице; С – число, стоящее на пересечении столбца, в котором находится чис-

ло В, и ключевой строки;

D – число, стоящее на пересечении строки, в которой находится число

Ви ключевого столбца;

Е– ключевое число.

38

38

39

По этой формуле находим число, производное 25 из строки Х3

Число производное 0 из пересечения строки Х3 и столбца Х1 равно

A0 0 0 05 0. 0,667

Аналогично находим производные для всех чисел строки Х1 и Х3.

В индексной строке табл. 16 наибольшее по абсолютной величине число 0,083 в столбце Х6, который является ключевым в этой таблице. Ключевая строка Х3, ключевое число 0,75. Вычисляем все элементы главной строки табл. 17, производные числа и индекса. После вычисления производных чисел и индексов оказалось, что в индексной строке два одинаковых по абсолютной величине отрицательных числа в колонке Х10 и Х11. Выбираем в качестве ключевого столбца Х10, в качестве ключевой строки – строку Х9, и ключевое число – 1,499, так как при делении на него свободного члена уравнения получилось минимальное по величине положительное число (табл. 18). Аналогично проводим третью и четвертую (табл. 19) итерацию. Отсутствие отрицательных величин в индексной строке табл. 19 говорит о том, что найдено оптимальное решение. После округления до целых величин результаты этого решения вносим в план раскроя (табл. 20).

40