Теорема. Егер сызықтық программалаудың негізгі есебінің ең тиімді жоспары бар болса онда ол шешімдер көпбұрышының қандай да бір төбесінде орналасқан. Егер мақсаттық функция өзінің максималды мәнін шешімдер көпбұрышының екі төбенің дөңес сызықты комбинациясы болатын кез-келген нүктеде де өзінің максимум мәнін қабылдайды.
Теорема. Егер P1, P2,…, Pk (k n) векторлар жүйесі (9) теңсіздікте сызықты тәуелсіз және
х1Р1+х2Р2+...+хкРк=Р0
болса, мұндағы барлық xj 0, онда X=(X1; X2;…;Xn; 0;...;0) нүктесі шешімдер көпбұрышының төбесі болып табылады.
Теорема. егер X=(X1; X2;…;Xn) шешімдер көпбұрышының төбесі болса, онда (10) теңсіздік дұрыс xj –ге сәйкес Pj векторлары сызықты тәуелсіз.
Құрастырылған теоремалар келесі қорытындыларды жасауға мүмкіндік береді.
Сызықтық программалаудың негізгі есебінің жоспарының жиыны бос жиын болмаса, онда ол дөңес көпжақты құрайды. Осы дөңес көпжақтың әрбір төбесі тірек жоспарына сәйкес келеді. Осы аталған төбелердің бірінде яғни қандай да бір тірек жоспары үшін мақсаттық функцияның мәні оның максимумына тең болады. Демек бұл төбе оң тиімді жоспарды анықтайды.
Мақсаттық функция максимал мәнге ие болатын шешімдер көпбұрышының төбесін салыстрмалы түрде табу оңай, егер стандарттық түрде жазылған септің екеуден көп емес айнымалысы бар болса немесе негізгі түрде жазылған есептің екеуден көп емес бос айнымалысы, яғни шектелген есептің жүйесінің коэфициенттерінен құралған n-r2, мұндағы n- айнымалылар саны, r-матрица рангі, бар болса.
Мынандай есепті қарастырайық:
F=c1x1+c2x2 max (11)
шарттары
ai1x1+ai2x2bi (i= ), (12)
 (13)
(12) және (13) теңсіздіктің әрқайсысы геометрия тілінде жартылай жазықтықты анықтайды. Сондықтан (12), (13) теңсіздіктің жүйесінің шешуі бар болса, онда ол жоғарыда тұрған әрбір жартылай жазықтыққа тиісті болады. Жартылай жазықтықтың қиылысуы дөңес жиын болады. Бұл жиынды шешімдер көпбұрышы деп атайды. Бұл көпбұрыштың қабырғалары жататын түзудің теңдеуі (11)-(12) теңсіздіктерді теңдікке айналдыруда шығатын формуламен анықтайды. Демек, сызықтық программалаудың (12)-(13) есебінің шешуі дегеніміз шешімдер көпбұрышы бос жиын болмауы керек және мақсаттық функция осы шешімдер көпбұрышы жоғарыдан шектелуі керек. Осы шарттар орындалғанда шешімдер көпбұрышының ең болмағанда бір төбесінде мақсаттық функция өзінің максимум мәнін қабылдады. Осы ең тиімді жоспарға сәйкес төбені анықтау үшін мына сызықты c1x1+c2x2=h сызамыз және бұл сызықты  = {c1; c2} векторлары бағытында параллель жылжытамыз. Нәтижесінде ол осы түзумен көпбұрыштың ең соңғы қиылысатын нүктесі ең тиімді жоспарға сәйкес нүкте болады.
(12), (13) есептерінің геометриялық интерпретациясын қарастыруды анықтай отырып, оның шешімін табу кезінде 1.1-1.4 суреттердегі көрсетілген жағдайлар кездесуі мүмкін.
 
B Fmax
Fmax
A
c
x1 x1
1.1 сурет 1.2 сурет
1.1 суретте ең тиімді жоспарға сәйкес бір ғана нүкте төбесі болады. 1.2 суреттен мақсаттық функция максимал мәнді АВ кесіндісінің кез-келген бөлігінде қабылдай алатындығы көрініп тұр. 1.3 суретте есептің шешімі болмайды. Себебі мақсаттық функция шешімдер көпбұрышында жоғарыдан шектелмеген. 1.4 суретте есептің шешімі болмайды. Себебі шешімдер көпбұрышы бос жиын.
 
1.3 сурет 1.4 сурет
Берілген шектелген жүйедегі сызықтық функцияның минималды мәнін табу оның осындай шектеудегі максимал мәнін табудан айырмашылығы c1x1+c2x2=h сызығы = {c1; c2} векторының бойымен емес, оған қарама-қарсы бағытта жылжуында. Осылайша мақсаттық функцияның максималды мәнін табуда кездесетін жоғарыда көрсетілген жағдайлар сол мақсаттық функцияның минимал мәнін тапқанда да орын алады.
Сонымен, сызықтық программалау есептерінің (11), (13) геометриялық мағынасына сүйеніп, графиктік әдіспен шешу мынадай қадамдардан тұрады:
1. Теңдеуі (12), (13) шарттардағы теңсіздік белгісін теңдікпен алмастырғанда шығатын түзулер сызады.
2. Есептің шартындағы әрбір теңсіздіктің шешуі болатын жартылай жазықтықтар табады.
3. Шешімдер көпбұрышын анықтайды.
4. = {c1; c2} сызады.
5. c1x1+c2x2=h түзуін сызады. Бұл түзу с векторына перпендикуляр орналасады.
6. c1x1+c2x2=h түзуін с векторы бағытында параллель жылжыта береді. Нәтижесінде мақсаттық функцияның максимум мәнін қабылдайтын нүктені табады немесе есептің шешімі болмайтындығын анықтайды.
7. Ең тиімді жоспардың координаталарын анықтап, мақсаттық функцияның сол нүктедегі мәнін есептейді.
Өзін-өзі тексеру сұрақтары
Сызықтық программалау дегеніміз не?
Сызықтық программалаудың негізгі ұғымдарын атаңыздар. Әрбір ұғымға анықтама беріңіз.
Сызықтық программалау тапсырмаларын шешудің графиктік әдістері.
Сызықтық программалаудың тапсырмаларын шешу әдістері?
Достарыңызбен бөлісу: |
