|
Пример 1. Рассмотрим задачу 4 из п. 6 § 2. Имеем общую задачу:
Путем введения новых неотрицательных переменных приведем ее
к каноническому виду:
Определим ранг матрицы коэффициентов системы уравнений.
В нашем случае ясно, что он равен 4, так как коэффициенты при новых переменных образуют единичную подматрицу. Еще более очевидно, что переменные x3, x4, x5, x6 могут одновременно быть выражены через x1 и x2. Таким образом, x3, x4, x5, x6 являются базисными переменными, а x1 и x2 — свободными. В этом случае система (4) имеет вид:
Составим для полученной системы и целевой функции симплекс-таблицу (таблица 9). X = (0; 0; 322; 70; 180; 100) — опорный план, с которого мы начинаем движение в сторону уменьшения значения . Для него = 0. Значения x3, x4, x5, x6 считываются из столбца свободных членов bi0, так как именно эти значения получаются, если свободные переменные равны нулю.
В идим, что в последней строке есть положительные элементы в столбцах при x1 и x2. Значит, любой из этих столбцов в дальнейшем может стать разрешающим.
Рассмотрим столбец x2. В нем есть положительные коэффициенты
в строках при x3, x4 и x6.
Находим, в какой из этих строк достигается Видим, что и достигается в строке при x6. Значит, эта строка будет разрешающей.
О тметим в таблице разрешающую строку, разрешающий столбец, разрешающий элемент и выполним один шаг жордановых исключений, то есть переведем переменную x2 в базисные, а x6 — в свободные. Преобразования исходной таблицы отражены в таблице 10, а новая симплекс-таблица представлена в верхних треугольниках таблицы 11. В дальнейшем для экономии места в случае, если новая таблица снова подвергается преобразованиям, будем в ней заполнять нижние треугольники, что соответствует следующим жордановым исключениям. Так сделано в таблице 11, судя по которой значение от 0 в начале процесса вычислений уменьшилось до –5 000. Это значение целевой функции на опорном плане X = (0; 50; 122; 20; 180; 0). Значения x3, x4, x5, x2 считываются из столбца свободных членов bi0. Вернемся к пункту 3 алгоритма симплекс-метода.
Видим, что в последней строке таблицы 11 (рассматриваем только верхние треугольники) положительный элемент только один — в столбце x1.
Этот столбец — разрешающий, так как в нем в строках при x3, x5
и x2 находятся положительные коэффициенты.
Н аходим, в какой из этих строк достигается Видим, что , и достигается в строке при x3. Значит, эта строка будет разрешающей.
Отметим в таблице 11 разрешающую строку, разрешающий столбец, разрешающий элемент и выполним один шаг жордановых исключений, то есть переведем переменную x1 в базисные, а x3 — в свободные. Преобразования исходной таблицы отражены в нижних треугольниках таблицы 11, а новая симплекс-таблица представлена в верхних треугольниках таблицы 12. По таблице 12 находим, что значение от –5 000 на предыдущем шаге симплекс-метода уменьшилось до
–7 135. Это — значение целевой функции на опорном плане X = (61; 34,75; 0; 35,25; 58; 0). Значения x1, x4, x5, x2 считываются из столбца свободных членов bi0. Вернемся к пункту 3 алгоритма симплекс-метода.
Видим, что в последней строке таблицы 12 положительных элементов нет. Это означает, что найденное опорное решение является оптимальным: X*= (61; 34,75; 0; 35,25; 58; 0). Наименьшее значение равно –7 135. Интерпретируем полученные результаты:
— оптимальный выпуск задвижек в день составляет 61 штуку;
— оптимальный выпуск тисков в день составляет 34,75 штук;
— сталь-45 при таком выпуске расходуется полностью;
— остаток чугуна (кг) на складе за 1 день;
— остаток бронзы (кг) на складе за 1 день;
— сталь-3 при таком выпуске расходуется полностью;
— наибольшая выручка (руб.) за день за выпущенную продукцию.
Получили то же решение, что и в § 1.1.
Если выпускать 34,75 тисков в день нельзя, то этот результат можно интерпретировать так: оптимальным является выпуск 34,75 · 4 = 139 штук тисков за 4 дня. Остальные цифры также должны быть соответственно пересчитаны. Можно поступить и по-другому: оптимальным считать выпуск 34 тисков в день. Но в этом случае необходимо пересчитать выручку, остаток стали-45, чугуна и стали-3.
Заметим, что выбирая разрешающий столбец в таблице 1 (пункт 4), можно было бы остановиться и на столбце переменной x1: в последней строке этого столбца и в других строках есть положительные элементы.
В этом случае решение пошло бы по другому пути. Убедитесь в этом самостоятельно. Порядок жордановых исключений в этом случае таков: x1 меняем с x5, x2 меняем с x3, x5 меняем с x6. Значения целевой функции при этом будут уменьшаться так: 0, –5 400, –6 700, –7 135.
Do'stlaringiz bilan baham: |
