2015-04-30
1294
Симплексный метод является наиболее распространенным универсальным вычислительным методом, который может быть применен для решения любых задач линейного программирования.
Идея метода состоит в последовательном продвижении от одного опорного плана к другому по определенному критерию, при котором значение целевой функции возрастает.
Данный переход возможен, если известен какой-нибудь исходный опорный план.
Рассмотрим задачу, для которой этот план можно непосредственно записать.
Пусть исходная задача приведена к каноническому виду (3.6):
F = c1x1 + c2x2 + ……+ cnxn ® max (3.12)
………………………………………. (3.13)
Здесь aij, bi, ci (
) - заданные постоянные числа (m < n, bi ³ 0). Говорят, что система уравнений, записанная в форме (3.13), имеет предпочтительный вид.
Векторная форма данной задачи имеет следующий вид:
(3.14)
(3.15)
где 
; 
.
Так как 
, то по определению опорного плана 
является опорным планом данной задачи.
Этот план определяется системой единичных векторов Рn+1,Рn+2,….. Рn+m, которые образуют базис m - мерного пространства.
Алгоритм табличного симплексного метода
I. Построение начального опорного плана:
1) Приведение задачи к каноническому виду.
2) Приведение системы ограничений к предпочтительному виду (3.13).
3) Построение первой симплекс- таблицы:
а) в столбце «Базис» записываются базисные переменные Хn+1,…, Хn+m (если некоторые или все переменные Хn+1,…, Хn+m , не входят в целевую функцию, то их коэффициенты равны нулю);
б) в столбце Сб записываются коэффициенты при неизвестных целевой функции, имеющие те же индексы, что и переменные данного базиса;
в) в столбце Ро записываются свободные члены b1, b2,…, bm системы ограничений в предпочтительном виде;
г) на пересечении последних (n+m) столбцов и первых m строк расположена матрица коэффициентов системы ограничений;
д) в индексной строке (m+1 я строка) располагают коэффициенты 
и 
, рассчитанные как скалярные произведения соответствующих векторов: 
.
4) Проверка условия оптимальности:
а) все 
, - данный опорный план является оптимальным;
б) 
для некоторого j, и все соответствующие этому индексу величины аij £0, 
, - функция неограниченная сверху: 
в) 
для некоторого j, и для каждого такого j по крайней мере одно из чисел аij >0, тогда можно перейти от исходного опорного плана к новому опорному плану, при котором значение целевой функции увеличится.
II. Переход к лучшему опорному плану (см. таблицу).
1) Выбор разрешающего столбца:
для всех 
выбирается 
, для выбранного 
в базис вводят соответствующую переменную Xk.
2) Выбор разрешающей строки:
Для разрешающего столбца определяют 
(aik > 0): выбранная строка с индексом r определяет переменную хr, которую необходимо вывести из базиса.
3) Выбор разрешающего элемента: это элемент, стоящий на пересечении строки с индексом r и столбца с индексом k: аrk.
4) Симплексные преобразования и построение второй симплекс-таблицы:
а) столбец «Базис»: переменная Xr заменяется на Xk, остальные переменные не меняются;
б) Сб заполняется соответствующими коэффициентами при базисных переменных в целевой функции;
в) элементы разрешающей строки делятся на разрешающий элемент и записываются в соответствующей по номеру строке новой таблицы;
г) элементы разрешающего столбца равны нулю, за исключением элемента, соответствующего месту разрешающего элемента. Он равен 1.
д) все остальные элементы новой таблицы рассчитываются по формулам:
, при i≠r (3.16)
где 
, bi’ - элементы новой симплекс-таблицы, aij, bi - элементы предыдущей симплекс-таблицы, ark - разрешающий элемент, aik - элемент разрешающего столбца, br, arj - элементы разрешающей строки.
5) Проверка условий оптимальности (I.4) и либо переход к (II), либо конец.
| i | Базис | Сб | Ро | С1 | С2 | … | Сr | … | Сk | … | Сn | Сn+1 | Сn+2 | … | Сn+m |
| X1 | X2 | … | Xr | … | Xk | … | Xn | Xn+1 | Xn+2 | … | Xn+m | ||||
| 1 | Xn+1 | Cn+1 | b1 | a11 | a12 | . | a1r | . | a1k | . | a1n | 1 | 0 | . | 0 |
| 2 | Xn+2 | Cn+2 | b2 | a12 | a22 | . | a2r | . | a2k | . | a2n | 0 | 1 | . | 0 |
| . | …. | …. | … | … | … | . | … | . | … | . | … | … | … | . | … |
| r | Xn+r | Cn+r | br | ar1 | ar2 | . | arr | . | ark | . | arn | … | … | . | …. |
| . | …. | …. | … | … | … | . | … | . | … | . | … | … | … | . | … |
| m | Xn+m | Cn+m | bm | am1 | am2 | . | amr | . | amk | . | amn | 0 | 0 | . | 1 |
| m+1 | Do | D1 | D2 | . | Dr | . | Dk | . | Dn | 0 | 0 | . | 0 |
Примечание. Для каждой симплексной таблицы можно записать текущий опорный план по следующему правилу: значение базисных переменных записаны в соответствующих ячейках столбца Ро, а небазисные переменные равны нулю. Кроме того, в ячейке 
записано текущее значение целевой функции при текущем опорном плане задачи. В последней таблице (для которой 
), в указанных ячейках будет записан оптимальный план 
и максимальное значение целевой функции Fmax(X*).
