Симплекстік әдіс және сызықтық программалауды стандартты түрге келтіру әдістері

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

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

13-09 ИСК

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

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

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

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

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

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

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

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

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

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

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

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

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

Көпмүше: анықтамасы, стандартты түрге келтіру, ұқсас мүшелерді біріктіру және дәрежесін анықтау

Ортогональды матрицаларды құру және квадраттық формаларды ортогональды түрлендіру арқылы канондық түрге келтіру

Балықтарды зерттеудің стандартты бағдарламасы мен ихтиологиялық әдістері

Этнопедагогикалық зерттеу әдістері және археологиялық әдіс

Стандартты микробиологиялық зертхана: құрылымы, негізгі жұмыс әдістері және тағам өнімдерін бақылау

Экономикалық есептерді симплекс-әдіспен шешу: сызықтық бағдарламалау теориясы мен алгоритмі

Бірнеше сызықтық регрессия: классикалық және жалпыланған модельдер мен бағалау әдістері

Экономикалық құбылыстарды зерттеуде корреляция коэффициенттері мен сызықтық регрессия әдістері

Қолмен программалауды автоматтандыру және программаны жасақтаудың кезеңдері: тестілеу мен жөндеу

11-сыныпқа арналған көрсеткіштік теңдеулерді шешудің стандартты емес және жасанды әдістері

Пәндер