Шпаргалка по математическим методам в экономике — страница 3

  • Просмотров 2191
  • Скачиваний 268
  • Размер файла 31
    Кб

пока xi>=0, т.е bi-aij0xj0>=0 => {xj0= bi/ aij0, aij0>0. Выберем среди правых частей наим долю. Пусть она достигается в строке i0, тогда эта строка – разрешающая, а элемент aij0 разреш-м элементом. Переведем базисную пременную xi0 в своб переем, а своб переем xj0 в базисную. Получаем новое допустимое базисное решение X1. Для этого выполняется D0-Dj0xi0=F(x0)-Dj0xi0>=F(x0) 3.Теорема о достижении экстремума значения целевой ф-ции в угловой точке. Если задача ЛП имеет

решение, то целевая ф-ция достигает экстемального значения хотя бы в одной из угловых точек многоугольника решений; если же целевая ф-ция достигает оптимального значения более, чем в одной угловой точке, то она достигает того же самого значения в любой точке, являющейся их выпуклой лин комбинацией. 6.Сходимость симплексного метода. Канонич задача ЛП нзв невырожденной, если все ее базисные решения невырождены, т.е ни одно из

базисных переменных не имеет нулевого значения. Если среди базисных решений есть хотя бы одно вырожденное, то задача ЛП нзв вырожденной. Так как при переходе от одной симплекс таблицы к другой используют правило прямоугольника, следоват-но значения целевых функций при нахождении максимума на двух последующих итерациях связаны формулой D0k+1=D0k-bi0Dj0/ai0jo (1) bi0>=0, Dj0<=0, ai0jo>0. Если задача невырождена, то bi0>0, Dj0<=0 => D0k+1>=D0k, Т.е

ф-ция F монотонно возрастает. Теорема: Если все допустимые базисные решения задачи ЛП невырождены, то симплексным методом за конечное число итераций будет найдено либо оптимальное решение, либо будет установлена неограниченность целевой ф-ции. 7.Зацикливание, выход из цикла. Если задача ЛП вырождена, то bi0=0 => D0k+1=D0k, Т.е. ы переходим к нехудшему допустимому базисному решению, но значение целевой ф-ции не изменится. Если такая

ситуация будет систематически повторяться, при переходе к новому базисному решению, то в силу конечности доп-х базисных решений ы придем к решению, которое ранее встречалось, т.е будем иметь повторяющееся симплекс таблицу. Т.о. получили зацикливание. Зацикливание можно избежать изменением правила выбора завершающего столбца и строки. К строке Qi симпл таблицы будем присваивать номер базисной переменной xi, соответствующий этой

таблице. Qm+1=(D0, D1, …, Dn). Допустимое базисное решение xi нзв обобщенно-положительным, если Qiý0 "iÎI={i1, …, im}. Если x0 – допустимое баз решение, то сделать его обобщен-положительным можно перенумеровав столбцы матрицы А. В невырожденной задаче все допустимые базисн решения обобщ-положительны. Пусть имеется задача на минимум, x0 – допуст баз решение. Теорема: Если Dj0 >0, а индекс разрешающей строки i0 выбрать из множ-ва I’={iÎI: