Автор: Пользователь скрыл имя, 23 Апреля 2012 в 13:38, лекция
На практике часто встречаются ситуации, когда достичь какого-либо результата можно не одним, а несколькими различными способами. Очевидно, что встает задача – из некоторого множества решений выбрать наилучшее. Математически эта задача обычно сводится к нахождению наибольшего или наименьшего значения некоторой функции при наличии некоторых ограничений (условий), т.е. к задачам на условный экстремум.
2. Имеется свободная переменная, коэффициент при которой в выражении (4) положителен (например, для определённости, gn > 0), а все коэффициенты при этой переменной в уравнениях системы (3) неотрицательны (то есть -a1n ³ 0, -a2n ³ 0,…, -amn ³0). Тогда будем наращивать значение xn, не меняя при этом значение остальных свободных переменных xm+1 = … = xn-1 = 0.
Значение базисных переменных при этом будут меняться. Используя выражения (3) получим следующую систему уравнений для базисных переменных:
x1 = b1 – a1nxn ³ b1,
x2 = b2 – a2nxn ³ b2,
…………………...,
xm = bm – amnxn ³ b, то есть решение X = (x1, x2, …, xm, 0, …, 0, xn) будет оставаться неотрицательным, то есть допустимым. При этом целевая функция F примет значение F = g0 + gnxn ³ g0 и, так как gn > 0, то значение F с ростом xn будет неограниченно увеличиваться. Т. о. целевая функция неограниченна в направлении оптимизации и задача решения не имеет: Fmax ® ¥.
3. Имеется свободная переменная, коэффициент при которой в целевой функции (4) положителен. Например, (gn>0), а среди коэффициентов при этой неизвестной в уравнениях (3) есть отрицательные. Например, первые два - a1n<0, - a2n<0. В этом случае производится шаг, а именно от базиса Б: {x1, x2, …, xm} мы переходим к новому базису Б’? таким образом, чтобы значение целевой функции FБ’ увеличилось, или по крайней мере не уменьшилось.
Очевидно, что изменение базиса влечёт за собой перестройку системы (3) и выражения для целевой функции (4).
Опишем содержание шага. Если мы снова, как в случае 2., будем наращивать значение переменной xn, (значение остальных свободных переменных оставим равными нулю), то будем иметь:
x1 = b1 – a1nxn,
x2 = b2 – a2nxn,
……………...,
xm = bm – amnxn,
при этом значения х1 и х2 будут уменьшаться, а значения остальных переменных будут увеличиваться, при этом оставаясь неотрицательными. При наращивании xn наступит момент, когда одно из неизвестных х1 или х2 обратятся в ноль: для х1 таким моментом будет xn = b1/a1n, а для x2 будет xn = b2/a2n. Выберем из этих отношений b1/a1n и b2/a2n, выберем из них наименьшее. Пусть, например, это будет первый b1/a1n = r. Тогда наращивание переменной xn возможно только от нуля до r. При xn = r переменная х1 = 0, а при дальнейшем росте xn переменная х1 станет отрицательной, что недопустимо.
Полагая, в системе (3) xn = r , а значение остальных свободных переменных равное нулю, получим следующее неотрицательное решение:
х1 = 0
х2 = b2 – a2nr = b2
…………………..
xm = bm – amnb = bm
xm+1 = 0
…………………...
xn-1 = 0
xn = r, т.е. X1 = (0, b2, …, bm, 0, …, 0, r).
Значение целевой функции для этого решения F = g0 + gnr ³ g0 (поскольку gn >0 и r ³0).
В нашем случае с ростом значения xn первой из базисных переменных обращается в ноль переменная х1 (для определённости), это служит сигналом к замене базиса Б= {x1, x2, …, xm} на базис Б’= {xn, x2, …, xm}, а именно: из старого базиса Б удаляется неизвестная x1 и вместо неё вводится неизвестная xn (из числа прежних свободных переменных). Смена базиса, как уже говорилось, влечёт за собой перестройку системы (3). Из первого уравнения для x1 выражаем xn.
и подставляем это выражение в остальные уравнения. В итоге получаем систему вида:
xn = bn – (an1*x1 + anm+1*xm+1 + … + ann-1*xn-1).
x2 = b2 – (a21*x1 + a2m+1*xm+1 + … + a2n-1*xn-1).
………………………………………………
xm = bm – (am1*x1 + amm+1*xm+1 + … + amn-1*xn-1)
с базисным решением (0, b2, …, bm, 0, …, 0, bn), которое должно совпадать с решением X1, поскольку, как видно из системы (6), двух разных решений с нулевыми значениями свободных переменных: x1 = xm+1 = … = xn-1 = 0 быть не может.
Таким образом, базисное решение X1 является неотрицательным, то есть допустимым.
Определим новое значение целевой функции в базисе Б’: F Б’ = g0 + gnr ³ g0 и т.о. FБ1 ³ FБ ,так как gn > 0 и r ³ 0. Итак, с переходом от базиса Б к базису Б’, значение целевой функции увеличилось (по крайней мере не уменьшилось).
Переход от базиса Б к новому базису Б’ означает шаг. Разумеется, старое выражение для целевой функции F (4) должно быть заменено новым, которое получается из выражения (4) для целевой функции заменой переменной xn по формуле (5). После преобразований целевая функция имеет вид:
(7) F = g0’ + gm+1' * xm+1 + … + gn-1’* xn-1 + g1’x1 ® max.
Если
для полученной задачи, записанной
формулами (6) и (7) снова имеет место
случай 3, то делаем следующий шаг,
то есть переходим к новому базису Б”,
для которого значение целевой функции
будет FБ”³
FБ’. И так до тех пор,
пока не прийдём к одному из случаев 1 или
2. Тогда процесс вычисления заканчивается.