Симплекс метод

  • 26 сент. 2011 г.
  • 551 Слова
Симплекс метод
Необходимо найти максимальное значение функции:
;
при условиях
.
В векторной форме уравнение будет выглядеть следующим образом:
;
при условиях:

где
; ; ; .
Вслучае, если одно из ограничений представлено не равенством а неравенством, то нужно добавить в это ограничение искусственную переменную с коэффициентом +1 если стоит , или -1 если стоит .
Так каксреди векторов нет достаточного количества единичных векторов, чтобы построить базис, то уравнения добавляются новые переменные. И теперь задача состоит в определении максимального значения функции:при условии:
.
где М – некоторое достаточно большое положительное число, конкретное значение которого обычно не задается, и это называется расширенной задачей. Такой метод называют методомискусственного базиса.
Расширенная задача имеет опорный план:

определяется системой единичных векторов Рn+1,Pn+2,…,Pn+m, образующих базис m-го векторного пространства, который называется искусственным. Сами векторыи переменные, которым они соответствуют, так же называются искусственными. Так как задача имеет опорный план, то она может быть решена симплекс методом.
При опорном плане расширенной задачи,значение линейной формы есть , а значения равны . Таким образом, F0 и разности состоят из двух независимых частей, одна из которых зависит от М, другая нет.
После вычисления F0 и их значения, а так жеисходные расширенной задачи заносятся в таблицу, которая содержит на одну строку больше чем обычная симплексная таблица. При этом в последнюю строку помещают коэффициенты при М, а в предпоследнюю – слагаемые, несодержащие М. При переходе от одного опорного плана к другому в базис вводят вектор, соответствующий наибольшему по абсолютной величине отрицательному числу последней строки, это значение помещаем во вторуюсимплексную таблицу, в колонку базисных переменных. Искусственный вектор, исключенный из базиса в результате некоторой итерации, в дальнейшем не имеет смысла...
tracking img