 |
|
Алгоритм симплексного метода
Рассмотрим алгоритм симплексного метода в таблицах. Задачу рассмотрим на максимум.
Симпекс-таблица
| № | Базис | Свободные члены, вi | Переменные | Q |
| х1 х2 … хm хm+1 хm+2 ….. xn | ||||
| хm+1 | в1 | a11 a12 a1m 1 0 …. 0 | ||
| хm+2 | в2 | a21 a22 a2m 0 1 …. 0 | ||
| … | … | … | … … … … … … … | |
| m | xm+n | вm | am1 am2 amn 0 …. …. 1 | |
| m+1 | Fj-Cj | с1 c2 cm 0 0 …. 0 |
1) Составление первого опорного плана.
Система ограничений задачи, решаемой симплексным методом, задана в виде системы неравенств смысла <=, правые части которых bi>=0. Перейдем от системы неравенств к системе уравнений путем введения неотрицательных дополнительных переменных. Векторы-столбцы при этих переменных представляют собой единичные векторы и образуют базис, а соответствующие им переменные называются базисными:
е aij xj +xn+i =bi
jÎ J
гдеxn+i -базисные переменные, xj -свободные переменные.
1) Составляем симплекс таблицу.Таблица состоит из коэффициентов системы ограничений и свободных членов. Последняя строка таблицы называется индексной и заполняется коэффициентами функции цели, взятыми с противоположным знаком.
2) Проверка плана на оптимальность.Выясняем, имеется ли хотя бы одно отрицательное число в индексной строке. Если нет, то найденный опорный план оптимален при решении задачи на максимум. Если же среди чисел индексной строки имеются отрицательные, то либо устанавливают неразрешимость задачи, либо переходят к следующему этапу алгоритма.
3) Определение ведущих столбца и строки.Находим направляющие столбец и строку. Направляющий столбец определяется наибольшим по абсолютной величине отрицательного числа индексной строки, а направляющая строка - минимальным из отношений компонентов столбца вектора свободных членов к положительным компонентам направляющего столбца min(bi/air). На пересечении направляющего столбца и строки находится главный элемент.
4) Построение нового опорного плана.Неизвестные переменные, соответствующие разрешающей строке и столбцу, меняют местами. При этом базисная переменная становится свободной переменной и наоборот. Новое значение элемента (Эн ) находящегося в i-й строке и в j-м столбце равно Старое значение элемента (Эс ) минус Элемент находящийся на пересечении j-го столбца и направляющей строки (Э1) * Элемент находящийся на пересечении i-й строки и направляющего столбца (Э2)/главный элемент (Эг). Это называется правилом прямоугольника.
Или по формулам
bi1= (bi-(br/ark)aikпри i=/r ; br/arkпри i=r) (5.12)
a’ij=(aij-(arj/ark)aikпри i=r ; arj/ark при i=r) (5.13)
F’0=F0 - (br/ark) Δk ; Δ’j =Δj - (arj/ark) Δk (5.14)
определяют положительные компоненты нового опорного плана, коэффициенты разложения векторов Аj по векторам нового базиса и числа F’0 , Δ’j . Все эти числа записываются в новой симплекс таблице.
6) Проверяют найденный опорный план на оптимальность. Если план не оптимален и необходимо перейти к новому опорному плану, то возвращаются к этапу 4), а в случае получения оптимального плана процесс решения задачи заканчивается.