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

Сызықты программалау есебінің тұжырымына сүйене отырып, (3.4) – (3.6) шектеулі жүйе мен мақсатты функцияны мына түрде жазамыз:

Сонда (3.5) –ке сәйкес b₁ ,b₂ ,…,b_r бос мүшелері теріс емес, Б= базис, ал оған сәйкес f_б =C₀ үшін базистік шешімі (b₁,b₂,…,b_r,0,0,…,0) болады.

(3.13) –тен шығатыны, f-тің мәнін азайту дегеніміз жақшаға алынған өрнектің мәні оң болатындай, бір бос белгісізді көбейту арқылы табу жолын. _Сr+1 , _Cr+2,…, Cn коэффиценттердің таңбасына байланысты екі жағдай қарастыруға болады:

1. Барлық сандар _Сr+1 , _Cr+2,…, Cn теріс, онда f-мәні одан артық кемімейді, себебі бұл тек қана бос белгісіздердің мәндерін кеміту жолымен орындалады, бірақ ол мүмкін емес. Бұдан (3.14)-ң базистік шешімі бұл жағдайда үйдесімді болатыны шығады.

2. _Сr+1 , _Cr+2,…, Cn сандарының арасында оң сандар бар. Айталқ, мысалы с_j>0 (r+1≤j≤n). Ол басқа бос белгісіздердің мәнін нолмен қалдырып, х_j -ді үлкейту жолымен f-мәнін азайтуға мүмкіндлік береді. х_j -ден басқа барлық белгісіздердің мәні Х_r+1 , _Хr+2,…, х_n нолге тең деп, (3.12) және (3.13) негізінде мынаны аламыз:

_(3.15)

_{…………………….}

_(3.16)

_{Алайда,(3.15) теңдіктен -ң} мәнін артыра отырып, теріс емес базистік айнымалылардың теріс емес екендігі жөніндегі шартының сақталуын қадағалап отыру керек екендігі шығады.Бұдан ,бос мүшелер теріс болмағанда соңғысы толығымен коэффициенттің таңбасына байланысты өзгеретінін көреміз.Мұнда тағы екі жағдай қарастырылады:

2а ) Барлық сандар. оң емес.Сонда -ң мәні шексіз көбеюі мүмкін,бұл f-тің мәнін шексіз азаюға алып келед.Демек,осы жағдайда f минимумына жетпейді,яғни

2б) сандарының арасындаоң сандар бар.Айталық, мысалы (1<k<r) осы шартты қанағаттандыратын коэффициенттері бірнешеу болуы мүмкін.Ол үшін дербес түрдің мәнін анықтап, осы дербес түрлердің арасынан ең кішісін алайық, ол болсын.Барлық (бәрінен бұрын )базистік белгісіздердің теріс еметігі сақталуы үшін -ң мәні K-дан үлкен болмауы керектігі түсінікті. Осы шарттардағы коэффициентін шешуші элемент деп атайды.

Сонымен деп алып,базистік белгісіздердің мәнін табамыз.

Енді белгісізі бос белгісіздердің құрамына өтуі керек, ал оның орнына базиске белгісізін енгізуіміз тиіс.Жаңа базис келесі түрде болады. .

Б базисіне сәйкес мақсатты функияның мәні мынаған тең:

Соңғы өрмек процестің біріншіқадамын орындағанан кейін мақсатты функцияның мәні кемитінін білдіреді.

Симплекс әдісінің келесі келесі қадамына көшу үшін (3.12)шектеуліжүйені және (3.13) мақсатты функцияны жаңа базисте қолданатындай өзгерту қажет.Осы мақсатпен (3.12) жүйесінде қарастырылып кеткен базистік белгісізден жаңа базистік белгісіз жүйенің қалған теңдеулерінен алынып тастап өрнектеледі.Бұдан кейін осы қарастырылған әрекет қайтадан орындалады.

Теорема 3.1: (Симплекс әдісінің алгоритмінің нәтижесі туралы)

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