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

Презентация қосу

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

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

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

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

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

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

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

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

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

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

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

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

Ата ұрпақ

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

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

Эвристикалық әдіс

Пәндер