Методическое пособие для выполнения контрольной работы по дисциплине
жүктеу/скачать 0.49 Mb.
|
| Симплекс–метод
Задача линейного программирования записывается в основной форме: максимум целевой функции Q при выполнении условий, заданных в форме равенств. Пусть x1, x2, … , xm – m базисных переменных; хm+1, xm+2, …, xn – (n-m) свободных переменных. Базисные переменные выражают через свободные в результате операции исключения, целевую функцию также выражают через свободные переменные. Тогда ЗЛП будет записана в канонической форме (отличными от нуля будут коэффициенты целевой функции только для свободных переменных):Q= →max (i= ) Векторная форма ЗЛП представляет простой способ ее записи и решения. Введем следующие обозначения: X= - вектор-столбец переменных; θ= - нудь-вектор размерности m; С= - вектор-строка коэффициентов целевой функции; В= - вектор-столбец свободных членов; Р= - симплекс-матрица. m n-m Таким образом, в векторной форме задача линейного программирования записывается в виде: . Для каждой из свободных переменных определяют вспомогательное число ( ), которое для всех базисных переменных равно нулю ( ). Теорема о признаках оптимальности опорного плана: Опорный план является оптимальным, если . Если для некоторого значенияj (допустим числа k) и все , то ЗЛП неразрешима. Если для опорного плана X , то существует другой знак X`, такой, что Q(x’)>Q(x). Для перехода к новой симплекс-таблице необходимо вычислить - скалярное произведениевектор-строки базисных элементов целевой функции и вектор-столбца свободных членов, вспомогательные величины , где - j-ый столбец симплекс-таблицы, - базис. Если существуют отрицательные значения , то в базис вводят новый вектор .Находят min для всех положительных . Пусть это будет i=r. Тогда из базиса исключают вектор .Элемент называется разрешающим элементом. Новый опорный план находят по формулам Жордана-Гаусса: если i≠r если i=r
; если i≠r если i=r
жүктеу/скачать 0.49 Mb. Достарыңызбен бөлісу:
|