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

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

aij0>0} Так, чтобы 1/ai0j0Qi0í1/aij0Qi, i¹i0, то новое допустимое базисное решение будет обобщ-положит, при этом Q’m+1íQm+1 Вывод из теоремы: если перед решением задачи произвести нумерацию базисных переменных xi так, что исходное допуст баз решение будет обобщ-положит, а разрешающую строку при каждой последующей итерации выбирать по правилу (1), то зацикливания не произойдет. Это следует из того, что если сущ Dj0 >0, aij0>0 для некотор i, то

при переходе к нов допустим базису строка Qm+1 будет лексикографически уменьшаться. Поэтому ни одно из допуст баз решений не повторится с исх допус баз решениями. А в силу конечности допуст баз решений получим, что найдется либо оптим решение, либо ф-ция F неограниченна снизу. 8. 1 метод искусственного базиса. Пусть имеется канонич задача ЛП Допустим, что все bi≥0. Ограничение в (1) имеет предпочтительный вид, если левая часть

ограничения содержит переменную, входящую с коэф-ом =1, а в ост огранич-ях с коэф 0. Если каждое ограничение в (1) имеет предпочтит вид, то допуст базисное решение находится путем приравнивания к 0 всех непредпочтит-х переменных. Если при этом получили не более m 0-ых координат, то согласно теореме об угловых точках многоуг-ка решений получим доп базисное решение. В этом случае предпочтит эл-ты есть базисные, а не предпочтит-ые –

свободные. А если не все ограничения имеют предпочтит вид, то в левую часть вводятся искусственные переменные Wi. В ф-цю F переменные Wi вводятся с коэф М в случае нахождения минимума, и с коэф-ом –М в случае нахождения максимума, где М – большое положит число. Полученная задача нза М-задачей соответ-ей исходной. М-задача всегда имеет предпочтит вид. (2*) Теорема: Если в оптимальном решении М-задачи X*(x1, …, xn, W1, …, Wn) все искуственнве

преенные Wi =0, то решение X=(x1, …, xn) явл оптимальным и для исходной задачи. 9. 2 метод искусственного базиса. Необх найти решение канонич задачи ЛП: bi>=0, i=1,m; xj>=0, j=1, n (1) (2) Пусть (1) не имеет предпочтит вид. Вводим дп переменные Wn+1, …, Wn+m так, чтобы (1) приобрела предпочтит вид. bi>=0, i=1,m; xj>=0, j=1, n (4) Теорема: Пусть задача (1) (2) имеет доп решение X=(x1, …, xnn, Wn+1, …, Wn+m) явл оптимальным для задачи (3) (4), ТТогда все искусств переем =0. Алгоритм: 1. Задача

(1) (2) преобразуется в (3) (4) 2. задача (3) (4) решается симплексным методом. Находят x. 3. если x невырожден, то в посл симплекс таблице вычеркиваются столбцы, соответствующие искусственным переменным и пересчитывается Dj. Это будет исходна симплекс таблица для задачи (1) (2) 10. Метод обратной матрицы Идея: пусть исходный базис состоит из векторов A1, …, Am. Xi и ci соответствуют базисным векторам. В симплексном методе использовалась формула (1) А