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

Мадияр Болатов

13-09 ИСК

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

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

Стандартты түрі

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

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

Стандартты түрі

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

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

Стандартты түрі

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

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

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

Ұқсас жұмыстар

Еттің химиялық құрамы

БАСҚАРУ ЖҮЙЕСІНДЕГІ БАҚЫЛАУДЫҢ ТАПСЫРМАЛАРЫ МЕН ҚҰРЫЛЫМЫ

Ақпаратпен алмасу принциптері мен режимдері

ЭКОНОМИКАЛЫҚ ЕСЕПТЕРДІ СИМПЛЕКС ӘДІСПЕН ШЕШУ

ЖТБ жүйесінің цифралық аппаратуралары

Адам генетикасы

БИОЛОГИЯЛЫҚ ӘДІС

Ата ұрпақ

ЗЕРТТЕУ ӘДІСТЕРІНІҢ ЕРЕКШЕЛІКТЕРІ

Санитарлық –гигиеналық нормативтертердің ғылыми негіздеу

Пәндер