Симплекстік әдіс

Уикипедия — ашық энциклопедиясынан алынған мәлімет
Мұнда ауысу: шарлау, іздеу

Математикалық ықшамдауда, Данцигтің симлекс алгоритмі (немесе симлекстік әдіс) сызықтық программалауда кеңінен таралған алгоритм. Информатика төңiрегiндегi техникалық есептеуiш журналы (The journal Computing in Science and Engineering) бұл алгоритмді 20 ғасырдың он мықты алгоритмдерінің біреуіне жатқызды.Алгоритм аты Т.С.Мотцин айтып кеткендей жеңіл (simplex ) деген сөзден шыққан.Симплекс әдістерде қолданыс таппайды, бірақ ол симплексациялық конустарға ісерін тигізеді, қосымша шектеулермен симплекстерге тиісті болады. Конусты симплексті қарау бұрыш яғни бұрыштарының жаны геометриялық дене, көпжақ.

Стандартты түрі[өңдеу]

Сызықтық программалауды стандартты түрдің ьіреуіне келтіру келесі түрде іске асуы мүмкін. Біріншіден, барлық нөлден басқа мәні кіші мүшеге жаңа мүше енгізілуі мүмкін. Шын мүше жаңа мүше арқылы шеттелуге болады.

x_1 \ge 5

жаға мүше, y1, былайша жазылады

\begin{align}
  y_1 = x_1 - 5\\
  x_1 = y_1 + 5
\end{align}

Екінші теңдеу x 1 мүшесін сызықтық программадан шығарылуы үшін қолданыс табады.Осылайша кіші мәнді шектеулер оң мәнді шектеулерге айналады. Екіншіден, әр бір қалып отырған шектеулер үшін "жалған айнымалы" еніп отыр,олар шектеулерді теңдікке ауыстыру үшін кіргізіледі.Бұл айнымалы теңсіздіктің екі жағындағы айырмашылықты көрсетеді және бұл айнымалы оң болады деп санаймыз.

\begin{align}
  x_2 + 2x_3 &\le 3\\
 -x_4 + 3x_5 &\ge 2
\end{align}

төмендегіге ауысады.

\begin{align}
  x_2 + 2x_3 + s_1 &= 3\\
 -x_4 + 3x_5 - s_2 &= 2\\
  s_1,\, s_2 &\ge 0
\end{align}

Бұл түрде алгебралық тұрғыда амалдар қолдану жеңіл болады. " ≥ " пайда болатын теңсіздіктерде көптеген авторлар "мол айнымалысына" жүгінеді. Үшіншіден,шектеусіз мүше сызықтық программалауда теңсіздіктен шығады. Екі әдіспен іске асыруға болады.Бір жолы мүше кездескен теңсіздікте айнымалы енгізу арқылы, екінші жолы мүшені екі шегі бар мүшемен алмастыру болып табылады. Мысалы, егер z1 шектеусіз болса,онда

\begin{align}
  &z_1 = z_1^+ - z_1^-\\
  &z_1^+,\, z_1^- \ge 0
\end{align}

Теңдіктен z1 сызықты программалауда алып тастау мүмкін болды.

Процесс толық мүмкін ауданға келгенде мынадай түрде жазылады

\mathbf{A}\mathbf{x} = \mathbf{b},\, x_i \ge 0

Бұл жердегі A қатардағы сан деп ойлаймыз. Бұл ешқандай кемшіліктергі әкелмейді немесе Ax >= b керек емес теңдеулерге,сызықтық программаның шешімі жоқ деген шешімге әкелуі мүмкін.

Pivot operations[өңдеу]

The geometrical operation of moving from a basic feasible solution to an adjacent basic feasible solution is implemented as a pivot operation. First, a nonzero pivot element is selected in a nonbasic column. The row containing this element is multiplied by its reciprocal to change this element to 1, and then multiples of the row are added to the other rows to change the other entries in the column to 0. The result is that, if the pivot element is in row r, then the column becomes the r-th column of the identity matrix. The variable for this column is now a basic variable, replacing the variable which corresponded to the r-th column of the identity matrix before the operation. In effect, the variable corresponding to the pivot column enters the set of basic variables and is called the entering variable, and the variable being replaced leaves the set of basic variables and is called the leaving variable. The tableau is still in canonical form but with the set of basic variables changed by one element.