n айнымалысы бар m сызықтық теңдеу түрінде жазылуы мынадай болады:
 (2.1)
Сызықтық програмалау есебінде әдетінше А=(aij) i=1,2…m
J=1,2…n
Жүйе матрицасының r рангы r
(2.1) жүйесінде m теңдеулер сызықтық тәуелсіз болсын, яғни r = m немесе m < n.
n айнымалысы бар m сызықтық теңдеудің кез- келген m айнымалысы (m < n) негізгі немесе базистік деп аталады, егер олардың коэффиценттерінен құрастырылған матрицаның анықтауышы 0-ге тең емес болса. Онда қалған
n – m айнымалылар негізгі емес немесе еркін деп аталады.
n айнымалылардың әртүрлі топтары негізгі болуы мүмкін. Ондай топтар саны былайша есептеледі:
Дәріс 4
Сызықтық программалаудың канон және жалпы есебі. Дөнес жиындар алгебрасының және геометриясының элементтері
ерілген жүйеден
 (2.1)
Анықтама. (2.1) жүйенің Х=( x1 , x2...хn ) шешімі мүмкін болу шешімі деп аталады, егер кез- келген J=1,2…n
хj 0, яғни шешім тек қана теріс емес компоненттерден тұратын болса.
Анықтама. n айнымалысы бар m сызықтық теңдеулер жүйесінің базистік шешімі деп, барлық n – m негізгі болмайтын айнымалылар тең болмағандағы шешімі аталады.СПЕ –де мүмкін болатын базистік шешімдер қарастырылады. Олар тіреуіш жоспары деп аталады. Базистік шешімдер саны шектеулі, себебі олар бойынша есептелінеді. Егер базистік шешімде ең болмағанда бір айнымалы 0-ге тең болса бұндай базистік шешім асқындалған деп аталады.
Қорытынды: (2.1) үйлесімді жүйенің шексіз көп шешімі бар. Ал, базистік шешімдер саны шектеулі. нан аспайды.
Дәріс 5. Дөнес жиындар алгебрасының және геометриясының элементтері
Сызықтық программалаудың жоғарыда аталған есептерінің үш түрі эквивалентті, яғни, қарапайым түрлендіру көмегімен олардың әрқайсысын басқаша түрде жазуға болады, яғни, көрсетілген есептің біреуінің шығару жолы бар болса, онда үш есептің кез келгенінің оптималды планын табуға болады. Сызықтық программалау есебінің бір формасынан басқа формасына көшу үшін функцияны минимизациялау есебін максимализациялау есебіне айналдыра білу керек. Екіншіден, шектеуші теңсіздіктерден шектеулі теңсіздіктерге өте білу керек. Үшіншіден, терістік емес шартын қанағаттандыратын айнымалыларды алмастыра білу керек.
Егер F= C1 х1+ C2 х2+ ...+ C n х n функциясының минимумын табу керек болса, онда F1= -F =-C1 х1- C2 х2 - ...- C n х n функциясын табуға көшуге болады.
Түрі “” болатын шектеуші теңсіздіктен шектеуші тендікке көшу үшін оның сол жағына қосымша теріс емес айнымалыларды қосамыз.Ал “” шектеуші теңсіздіктен шектеуші теңдікке көшу үшін, оның сол жағынан қосымша айнымалыларды алып тастаймыз.
Шектеуші теңсіздік аi1 x1 +аi2 x2+...+ аi n x n bi болса,онда сәйкес шектеуші теңдікке көшеміз,теріс емес айнымалыларды қосамыз.
аi1 x1 +аi2 x2+...+ аi n x n + x n+1 bi (x n+10)
Ал мынадай шектеуші теңсіздіктен шектеуші теңдікке ауысу үшін
аi1 x1 +аi2 x2+...+ аi n x n bi
аi1 x1 +аi2 x2+...+ аi n x nx n+1 bi (x n+10)
Шектеуші жүйенің әрбір теңдеуін аi1 x1 +аi2 x2+...+ аi n x n bi теңсіздіктер түрінде жазуға болады.
аi1 x1 +аi2 x2+...+ аi n x n bi
-аi1 x1 -аi2 x2-...- аi n x n - bi
Достарыңызбен бөлісу: |
