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

СП жалпы есебін келесі түрде құруға болады. х₁ х₂,..., х_n – нің

шектеулер жүйесін

теріс еместік шартын қанағаттандыратын және

сызықтық функциясы (мақсат функция) экстремумге (максимум немесе минимум) жететін мәнін табу.

Координаттары шектеулер жүйесін қанағаттандыратын X = (х_г х₂,..., х_n) векторын сызықтық программалау есебінің жоспары немесе мүмкін шешімі деп аталады.

Барлық мүмкін шешімдердің (жоспарлардың) жиынтығын есептің мүмкін шешімдер аймағы деп атайды.

X — (хj, x₂,..., х_п) жоспары таяныш деп аталады, егер оң х белгісізі кезінде коэффициенттерден құралған Aj (J = 1,m) векторлары сызықты тәуелсіз болып табылады. Таяныш шешім құлдырамайтын болады, егер ол m оң компоненттен тұрса, кері жағдайда таяныш шешім құлдыраушы деп аталады.

Тиімді жоспар немесе сызықтық программалау есебінің тиімді жоспары деп сызықтық функцияға ең үлкен (ең кіші) мән беретін жоспар аталады.

Сызықтық программалаудың с тандартты (немесе симметриялы) есебі деп айнымалылардың теріс еместік шартында <= bи түріндегі теңсіздік шектеулерінде мақсат функциясының мәнін анықтаудан тұрады.

Сызықтық программалаудың к анондық (негізгі) есебі деп айнымалылардың теріс еместік шартындамаксималды (минималды) мәнін анықтаудан тұрады.

Сызықтық программалау есебін жазудың әртүрлі формалары бар: матрицалық, векторлық және қосынды белгісінің көмегімен.

Сызықтық программалау есебінің көрсетілген үш формасы эквивалентті, өйткені олардың әрбірі күрделі емес түрлендірулер нәтижесінде басқа есеп түрінде жазылуы мүмкін. Бұл егер бір есептің шығарылу әдісі табылса, онда үш есептің кез-келген біреуінің оңтайлы жоспарын анықтауға болатынын білдіреді. Сызықтық программалау есебін жазудың бір түрінен екіншісіне өту үшін жалпы жағдайда, біріншіден функцияны минимизациялау есебін максимизациялау есебіне келтіру, екіншіден теңсіздік – шектеулерден теңдік шектеулерге өту және керісінше, үшіншіден теріс еместік шартына бағынбайтын айнымалыларды ауыстыру керек. Теңсіздік – шектеулерден теңдік шектеулерге түрлендіру кезінде енізілетін қосымша теріс емес айнымалылардың саны түрлендіретін теңсіздіктердің санына тең. Егер айнымалы теріс еместік шартына тең болса, онда оны екі теріс емес айнымалылармен алмастыруға болады.