Информатика -продвинутый курс
Попробуем увеличить x3. Первое из
Попробуем увеличить x3. Первое из уравнений имеет ограничение x3
= 1 (из условия x1 ? 0), второе - не дает ограничений. Далее, берем x3 = 1, х2
не меняем и получаем новое допустимое решение (0, 0, 1, 3), для которого f = -1 - уменьшилось. Найдем базис, которому соответствует это решение (он состоит, очевидно, из переменных x3, x4). От предыдущей системы ограничений переходим к новой:
а форма в новых свободных переменных имеет вид
Теперь попробуем повторить предыдущую процедуру. Для уменьшения f надо уменьшить либо x1,
либо x2, но это невозможно, так как в этом базисе x1 = 0, x2 = 0.
Таким образом, данное базисное решение является оптимальным, и minf= -1 при x1
= 0, x2 = 0, x3 = 1, x4 = 3.
Приведем алгоритм симплекс-метода в общем виде. Обычно все вычисления по симплекс-методу сводят в стандартные таблицы.
Запишем систему ограничений в виде
а функцию f
Тогда очередной шаг симплекс-процесса будет состоять в переходе от старого базиса к новому таким образом, чтобы значение линейной функции, по крайней мере, не увеличивалось.
Данные о коэффициентах уравнений и линейной функции занесем в табл. 7.12.
Таблица 7.12
Симплекс-таблица
Сформулируем алгоритм симплекс-метода применительно к данным, внесенным в табл. 7.12.
1. Выяснить, имеются ли в последней строке таблицы положительные числа (?0 не принимается во внимание). Если все числа отрицательны, то процесс закончен; базисное решение (b1, b2, .... br, 0, ..., 0) является оптимальным; соответствующее значение целевой функции f = ?0. Если в последней строке имеются положительные числа, перейти к п.2.
2. Просмотреть столбец, соответствующий положительному числу из последней строки, и выяснить, имеются ли в нем положительные числа. Если ни в одном из таких столбцов положительных чисел нет, то оптимального решения не существует. Если найден столбец, содержащий хотя бы один положительный элемент (если таких столбцов несколько, взять любой из них), пометить этот столбец и перейти к п. 3.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий