Метод симплекс-таблиц. Исполнитель
- Скачано: 31
- Размер: 159.5 Kb
Метод симплекс-таблиц.
Как известно общая задача линейного программирования имеет следующей вид:
{spoiler=Подробнее}
(1)
при условиях
(2)
(3)
(4)
где А i j , Вi , С j -- заданные постоянные величины и к
F=CX (5)
при условияx
х 1 P1 + X2 P2 + ...+ Хп Рп = Ро (6)
x С (7)
где С = (С1 , С 2 , ..... , С n) Х= ( Х : , Х 2 , .... , Х n ): CX - скалярное произведения: Р1 , Р2 , .... Рn -n -мерный вектор столбце, составление из коэффициентов при неизвестных и свободных членах системы уравнений задачи:
P0 =
Пусть требуется найти максимальное значение функции
при условиях
Здесь ai ,bi и ci (i=1,m; j=1,n) - заданные постоянные числи (m=n и bi>0).
(8)
при условиях
X1P1 + X2P2 + . . . + XmPm + . . . + XnPn = P0 (9)
Xj>0 (j=1,n) (10)
где
Так, как
b1p1 + b2p1 + . . . + bmpm = p0
то на определению опорного плана Х=( b1, b2,...bm ;0,0,....0) является опорном планом данной задачи. Этот план определяется системой единичных векторов Р1, Р2, ... Рn которые образуют базис m-мерного пространства
Пусть
Положим так как векторы р1,р2,......,рm- единичные, то xij=aij и zi=, a Aj=.
ТЕОРЕМА: (признак оптимальности опорного плана)
Опорный план х*=(х1*,x2*,….xn*,0,0,0…..0) задачи (8)-(10)-является оптимальный если Аj=0 для любого j(j=1,n) Исследование опорного плана на оптимальность ,а также дальнейший вычислительный процесс удобного вести, записать так как показано в следующее таблице:
I |
Базис | Сб | Р0 | С1 | С2 | …. | С2 | … | Сm | Cm+1 | … | Ck | … | Cn | |||
P1 | P2 | … | P2 | … | Pm | Pm+1 | … | Pk | … | Pn | |||||||
12 . . .r . . m |
P1 P2 . . PR . . Pm |
C1 C2 . . Cr . . Cm |
B1 B2 . . br . . bm |
1 0 . . 0 . . 0 |
0 1 . . 0 . . 0 |
… … … … .. … … … |
0 0 . . 1 . . 0 |
… … … … … … … … |
0 0 . . 0 . . .1 |
A1m+1 A2m+1 ….. ….. arm+1 …. …. Amm+1 |
…………………… |
A1k A2k … … ark … … amk |
…………………… | ||||
M+1 | F0 | 0 | 0 | … | 0 | … | 0 | :m+1 | … | :k | … | :k | |||||
В столбце Сб этой таблицы записывают коэффициенты при неизвестных целевой функции , имеющие те же индексы, что и векторы данного базиса.
В столбце р0 записывают положительные компоненты исходного опорного плана, в нем же в результате вычисления получают положительные компоненты оптимального плана.
Столбце векторов рi представляет собой коэффициенты разложенный этик векторов данного базиса. В строке определяются исходными данными задачи, а показатели (m+1)-й строке вычисляют. В этой строке в столбце вектора р0 записывают значение целевой функции ,которое она принимает при данном опорном плане, а в столбце вектора рi -значение Di=zi-ci ;,m) на вектор Сб=(С1;C2;….,Cm)
Zi=
Значение F0 равно скалярному произведению вектора р0 на вектор Сi:
Fn значение zi находится как скалярное произведение вектора
Fi(i=1 =
После заполнения таблицы опорного плана проверяют на оптимальность. Для этого просматривают элементы (m+1)-й строки таблицы. В результате может иметь место один из следующих трех случаев:
- для j=m+1 , m+r,....... ,n(при j=1,mZj=Cj)
По этому, в данном случая числа :j0 всех j от 1до n:
2) для некоторых индексов j и для каждого такого j по крайней мере одно из чисел аji положительно.
3) для некоторого j и все соответствующие этому индексу величины аij (i=1,m)
В первом случае на основании признака оптимальности исходный опорный план является оптимальным. Во втором случай целевая функция не ограничена сверху на множестве планов. А в третьем случае можно перейти от исходного плана к новому опорному плану ,при котором значение целевой функции увеличиться .
Этот переход от одного опорного плана к другому осуществляются исключением из исходного базис какого-нибудь из векторов и введением в него нового вектора.
Пусть, например, Dk0 и решено вести в базис вектор рк.
Для определения вектора, подлежащего исключению из базиса ,находят min(в аik) для всех аik. Пусть этот минимум достигает при i=2. Тогда из базиса исключают вектор рr а число аrk называют разрешающим элементом.
Столбец и строку ,на пересечением которых находится разрешающей элемент называют направляющими.
После выделения направляющей строки направляющего столбца находят новый опорный план и коэффициенты разложении векторов Рj через векторы нового базиса ,соответствующего новому опорному плану , это легко реализовать если воспользоваться методом Жордана-Гаусс. При этом можно показать ,что положительных компоненты нового опорного плана вычисляются по формулам:
bi1= при
a-коэффициенты разложения векторов Рj через векторы нового базиса, соответствующего новому опорному плану -по формулам:
ai1j= при
После вычисления br1j и ai1j согласно но формулой 11 и 12 их значения заносят в след. табл.
Элементы (m+1) й строки этой таблицы могут быть вычислены либо по формулам:
p01=p0-(br/ark) Dk (13)
Dj1=Dj-(arj/ark) Dk (14)
либо основании их определения .
После заполнения новой симплекс таблицы просматривают элементы(m+1)-й строки. Если все zj-cj, то новый опорный план является оптимальным.
Таким образом, решение симплексным методом осуществляется в определенной последовательности .
1)Находится базисное допустимое решение .
2)Вычисляется симплекс - разность для каждой переменной не входящей в базис;
3)Вводится в базис переменная, удовлетворяющая условию max(xr)=min(xi1/xir)
4)Исключается из решения переменная, соответствующая max(xr),ни вектор Рi;
5)n 1-4 повторяется до тех пор, пока симплекс разность для всех переменных не входящих в базис, не станет равной нулю или отрицательной . это свидетельствует о том , что оптимальное решение получено.
{/spoilers}