Образовательная программа: Вычислительная техника и программное обеспечение 8D06104
жүктеу/скачать 221,11 Kb.
|
Лекция 6. Математическая модель ЛП. Часть 1
| Идея симплексного заключается в том, что, начиная с некоторого исходного опорного решения, осуществляется последовательно направленное перемещение по опорным решениям задачи к оптимальному.
Значение целевой функции при этом перемещении для задач на максимум не убывает. Так как число опорных решений конечно, то через конечное число шагов получим оптимальное опорное решение. Опорным решением называется базисное неотрицательное решение. Алгоритм симплексного метода: I. Построим первый опорный план, базис в котором полностью заполнен и свободные члены неотрицательны. Для базисных переменных заполним единичные столбцы: на пересечении одинаковых переменных по столбцу и строке ставится 1, остальные элементы столбца заполняются нулями; II. Проверим план на оптимальность. План будет оптимальным, если в строке целевой функции Z не будет отрицательных коэффициентов (в задачах на max, в задачах на min – положительных). Если в строке Z есть отрицательные коэффициенты, то план можно улучшить, построив новый план; III. Построим новый план. 1. Выберем разрешающий столбец. Им будет столбец с максимальным по модулю отрицательным коэффициентом в строке целевой функции Z; 2. Выберем разрешающую строку. Ей будет строка с минимальным симплексным отношением. Симплексные отношения рассчитываются делением свободных членов (bi) на положительные коэффициенты разрешающего столбца (aij*); 3. На пересечении разрешающего столбца и разрешающей строки выделим разрешающий элемент; 4. В базис новой таблицы вместо X разрешающей строки старой таблицы вводим X разрешающего столбца. Остальные переменные базиса переписываем из старой таблицы без изменений; 5. Строка с новым X в новой таблице называется начальной и рассчитывается делением коэффициентов разрешающей строки старой таблицы на разрешающий элемент; 6. Для базисных переменных заполним единичные столбцы; 7. Остальные элементы новой таблицы рассчитываются по правилу «прямоугольного треугольника»: элемент в новой таблице равен разности между соответствующим элементом в старой таблице и произведением соответствующего элемента разрешающего столбца на соответствующий элемент начальной строки. жүктеу/скачать 221,11 Kb. Достарыңызбен бөлісу:
|