2015-06-10
294
1 шаг: построить математическую модель(З.Л.П.) экономической задачи:
f (x) = с1x1+с2x2 +с3x3+…+сnxn ® max
xj ³ 0, j = 1,2,...n; xj (j = 1..n) – неизвестные
aij, bi, сj (i = 1..m; j = 1..n) – постоянные величины.
2 шаг: привести систему ограничений З.Л.П. к виду системы линейных уравнений.
| Замечание 12 Любое неравенство можно свести к уравнению путем введения дополнительных переменных. Например: Þ прибавив к левой части неравенства 2х1 +3х2 £ 2 некоторую дополнительную переменную х3 мы получим равенство следующего вида 2х1 +3х2 +х3 = 2 Þ при вычитании из левой части неравенства 5х1 +х2 ³ 2 некоторую дополнительную переменную х3 мы получим равенство следующего вида 2х1 +3х2 –х3 = 2 |
3 шаг: путем элементарных преобразований привестисистему ограничений к виду системы линейных уравнений с выделенными переменными.
4 шаг: найти базисное решение, приравняв для этого небазисные переменные к нулю, а базисные – к свободным членам.
5 шаг: пользуясь Теоремой 1,проверить базисное решение на оптимальность:
Þесли все коэффициенты целевой функции f(x)=с1x1+с2x2 +…+сnxn
|
|
|
при небазисных переменных не положительные,а при базисных равны нулю, то критерий оптимальности выполнен. Далее перейти к 6-му шагу алгоритма.
Þесли в целевой функции найдется хотя бы один положительный коэффициент сj перед небазисной переменной xj, тонайденное базисное решение не является оптимальным. В этом случае, пользуясь теоремой 3,исследуют возможность перехода к новому базисному решению. Если получили, что такой переход возможен, то необходимо осуществить смену одной базисной переменной по схеме 1.
