ИННОВАЦИИ БИЗНЕСУ

Результат выполнения технологической разработки.

Симплексный метод является основным численным методом решения задач линейного программирования. Применительно к канонической задаче линейного программирования симплексный метод описывается:

<с,х> min

Ах=в, х>0, где А Э А~(m,n), в Эr ^m, с Эr ^m (1)

Это не ограничивает общность метода, т.к., любая задача линейного программирования может быть представлена в форме (1) Предположим, чтоrang А=m,т.е., все строки матрицы А линейно независимы. К этому можно прийти, исключив из системы (1) линейно зависимые уравнения, что обычно и делается в рамках специальной процедуры, предшествующей симплексному методу.

Обозначим через х допустимое множество задачи (1), т.е.,

Х={xЭ.r ⁿ | ax=в, х>0}

Точка х множества Х является вершиной только в том случае, если векторы

а^j(jЭj(x)), т.е., столбцы матрицы А, соответствующие положительным координатам точки х, линейно независимы. При этом вершина х невырожденна, если

| j(x) |=m,и вырожденна, если| j(x) |<>

Базисом вершины х множества Х называется произвольная система из mлинейно независимых столбцов матрицы А, включающая в себя все точки х. Невырожденная вершина х имеет единственный базис{a ^j | jЭj(х)|}. У вырожденной вершины базисов может быть несколько, причем условиеrang a=mобеспечивает существование по крайней мере одного базиса.

Симплекс-метод представляет собой вычислительную процедуру, которая генерирует последовательность вершин х1,х2..., хnвместе с некоторыми их базисами. На очереднойn-ой итерации в зависимости от текущего значения параметров либо делается один из двух выводов:

1.хt- решение задачи (1);

2.задача (1) не имеет решения.

либо строится следующая вершина х^t+1.Если при этом вершинаxtневырожденна, то в новой вершине целевая функция принимает заведомо большее значение:

^t+1>> (2)

Под правильным симплексом понимается совокупность равноудаленных друг от друга точек вn-мерном пространстве. В одномерном пространстве симплексом является отрезок прямой, в дву - равносторонний треугольник, в трехмерном - правильная треугольная пирамида.

К1К2...Кn-1Кn

-r1 r2... Кn-1Кn

aij = 0 -r2 ... kn-1 kn (3)

0 0 ... kn-1 kn

0 0 ... -rn-1 kn

0 0 ... 0 kn

Каждая строка матрицы (3) представляет вершину правильного симплекса с ребром, равным еденице, и с центром тяжести в начале координат. На основе матрицы (3) можно получить матрицу произвольного симплекса с произвольными длинами сторон и с центром в наперед выбранной точке по следующей формуле:

cij = aij gi + coi,

Гдеgi- длина сторон симплекса по каждой координате,coi- точка, в которую перемещается центр тяжести симплекса.

Пусть набор коэффициентовci(i = 0,n)образует точку вn=1-мерном пространстве коэффициентов отображающей функции. Тогда, задаваяgi, coi, можно построить матрицу исходного симплекса, каждая строка которой представляет набор коэффициентов отображающей функции. Любому такому набору можно поставить в соответствие величину подсчитанного среднего отклоненияs.

Тогда из совокупностиs, подсчитанных для каждой вершины исходного симплекса, выбирается точка К, которой соответствует s=smax, и заменяется новой полученной зеркальным отражением точки К относительно противоположной грани симплекса по формуле:

n+1

e cji - cki

cki = j=1

n+1

Этот процесс шагового восхождения продолжается до тех пор, пока уменьшаетсяs. Для достижения необходимой точности производится дробление симплекса, то есть уменьшаются длины ребер симплекса, а процесс шагового восхождения продолжается с точки, соответствующейs=sminна предыдущем этапе.