Бірінші симплекс кестесі

Құрылған кестенің (І) (m+1)- жолын қараймыз. Егер барлық болса, онда тірек шешімі оптималды, сызықтық функцияның min мәні .

Әйтеуір бір баға делік; онда шешім оптималді емес, бұл бағаға тиісті векторды базиске енгізіп, сызықтық функция мәні алғашқыдан кем болатындай, басқа тірек шешімін құруға болады.

Оң таңбалы бағалар бірнешеу болса, барлық -лерден мәні сәйкес вектор енгізіледі.,

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

 

і Базис С Базис А0 С1 С2 ... Сl … Сm Сm+1 … Сj … Сk … Сn
A1 A2 … Al … Am Am+1 … Aj … Ak … An
. . . l . . . m A1 A2 . . . Al . . . Am C1 C2 . . . Cl . . . Cm x1 x2 . . . xl . . . xm . . . . . . . . . . . . … … . . . … . . . … . . . . . . … … . . . … . . . … . . . . . . X1,m+1 X2,m+1 . . . Xl,m+1 . . . Xm,m+1 … … . . . … . . . … X1j X2j . . . Xlj . . . Xmj … … . . . … . . . … X1k X2k . . . Xlk . . . Xmk … … . . . … . . . … X1n X2n . . . Xln . . . Xmn
m+1 Zj-Cj Z0 … … Zm+1-Cm+1 … Zj-Cj … Zk-Ck … Zn-Cn


делік, яғни max мәні к-ші векторға қатысты, . Онда базиске Ак векторы енгізіледі, ал базистен мәніне тиісті вектор шығарылады.

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

 

9, 10 – ші дәрістер. Жасанды базис әдісі. Кейбір экономикалық есептерге жасанды базис әдісін қолдану.

 

Жасанды базис әдісі

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

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

қарастырайық. Шектеулер жүйесінде бірлік матрица айқын берілмесін. Әрбір теңдеуге - жасанды айнымалысын қосып, жүйеге бірлік матрицаны енгізу арқылы

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

Бастапқы есептің оптималдық шешімін табу үшін келесі теореманы қолданады.

Теорема. Егер кеңейтілген есептің оптималдық шешімдегі жасанды айнымалылары болса, онда бастпқы есептің оптималдық шешімі болады.

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

Х бастапқы есептің оптималдық шешімі болатындығын керісінен дәлелдейміз, яғни х оптималдық шемшім емес делік. Онда оптималдық шешімі табылып, теңсіздігі орындалады, ал үшін яғни болып шығады.

Демек, кеңейтілген есептің шешімі оптималды емес, теореманың шартына қарама-қайшы. Теорема дәлелденді.

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

Алдынала берілген М санына байланысты, кеңейтілген есептің симплекс кестесінің бір жолы, яғни (m+2)- жолы артық. Осы жолға жазылған М-нің коэффициенттері арқылы базиске енгізілетін векторлар жасанды векторларды базистен түгел шығарғанша анықталып отырады. Оптималды шешімді іздестіру әрі қарай (m+1)- жолымен жалғастырылады.

Мысал.

Шешуі: Шектеулер жүйесіне жасанды айнымалылар -ды енгізу арқылы бірлік матрицасы бар кеңейтілген есепке көшеміз

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

Симплекс кестесін құрып, (m+1)- жолдың бағалары арқылы шешімнің оптималдығын тексереміз

формаулалармен -жолдарының элементтерін есептейміз:

Бағалар мәндері М шамасы бойынша сызытық функция, есептеуге анғайлы болу үшін (m+1)-жолына М-нен тәуелсіз бөлігін, (m+2)-жолына М-нің коэффициенттерін жазамыз

 

(m+2)- жолында теріс таңбалы элементтердің болуы кеңейтілген есептің тірек шешімінің оптималды еместігін білдіреді. Онда мәні шешуші элементті, базиске енгізілетін және базистен шығарылатын векторларды анықтайды. Бірінші шешімде мәні А1 векторына тән: Демек, шешуші элемент 2, А, базиске енгізіледі, А6 базистен шығарылады. Симплекс түрлентіруімен екінші шешімді аламыз. Екінші шешім де оптималды емес, (m+2)-жолында теріс таңбалы элементтері бар. Тағы да мәні арқылы шешуші элементі, базиске енгізілетін және базистен шығарылатын векторларды анықтаймыз, симплекс түрлендіруін атқарамыз. Осылайша симплекс түрлендірулерін алдымен (m+2)-ші, сонан соң (m+1)-жолдың элементтерінің белгілерімен оптималдық шешімді тапқанша, немесе есептің шешімі жоқ екендігін анықтағанша жалғастырамыз.

Үшінші шешім оптималды, себебі (m+2) және (m+1) жолдарында max үшін оптималдық шарты орындалған. Жасанды айнымалылар болғандықтан, алынған шешім бастапқы есептің де оптималдық шешімі береді және

Соңғы сатыдағы А1 және А3 жолдармен А5, А6 болғандарының қиылысында кері матрицаны аламыз.

Есептің шектеулер жүйесінде бірлік матрица берілсе, оны шешу үшін шамамен m жуықтау керек, бастапқы тірек шешім үшін толық жасанды базис енгізілсе, онда жуықтау саны шамамен 2m-ге дейін жетеді.

 

11, 12 – ші дәрістер.Түйіндестік қағидасы. Түйіндестік теоремасы. Негізгі есеп. Симметрия емес және симметриялық түйіндес есептер.

Сызықтық программалаудағы түйіндестік және

түйіндестік түсінігі

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

Мысал ретінде шикізаттарды пайдалану есебін қарастырамыз.

Кәсіпорынның n түрлі өнім шығару үшін m түрлі, көлемдері шикізаттары бар. j- зат бірлігін дайындау үшін і – шикізаттың aij көлемі жұмсалады, өнімнің бағасы Cj. Бағаға шаққанда max – ды болатын өнім дайындау жоспарын құру керек.

Өндірілетін j- затты xj десек, сызықтық программалаудың бастапқы есебі былай қойылады:

Сызықтық фунцияға

мәнін беретін, шектеулер жүйесінің

шешімі - векторын табу керек.

Шикізаттарды бағалайық. і – шикізат бағасын десекб j-өнімді дайындауға жұмсалған барлық шикізаттар бағасы болады. Жұмсалған шикізаттар бағасы алынған өнімнің бағасынан кем болуы мүмкін емес, демек теңсіздігі орындалады. Бар шикізаттардың бағасы . Сонымен, түйіндесесеп былай қойылады:

Сызықтық функцияға

мәнін беретін, шектеулер жүйесінің

шешімі - векторын табу керек.

Қарастырылған бастапқы және түйіндес есептердің экономикалық мағыналары мынада.

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

Түйіндес есеп. Шикізаттар көлемдері және өндірілетін заттар бағалары белгілі болғанда, өндірудің жалпы шығыны min–ды болуы үшін шикі заттардың бағалары қандай болуы керек?

Айнымалылар уi бағалар, немесе есептелінетін, айқын емес бағалар деп аталады. Түйіндестік есептердің математикалық моделдері тығыз байланысты. Бастапқы есеп шектеулерінің матрицасы А қосалқы есепте транспонирленген, сызықтық функция коэффициенттері С қосалқы есепте шектеулерінің бос мүшелері, шектеулердің бос мүшелері В қосалқы есепте сызықтық функцияның коэффициенттері болып келеді.

 

Симметриясыз түйіндес есептер.

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

Бастапқы есеп. Шектеулердің

сызықтық функцияны Z=CX минимизациялайтын шешімі баған – матрицаны табу керек.

Түйіндес есеп.

(2)

шектеулерінің сызықтық функцияны

максимизациялайтын шешімі жол-матрицаны табу керек.

Екі есепте де - жол – матрица, - баған матрица, шектеулер жүйесі коэффициенттерінің матрицасы. Түйіндес есептердің оптималдық шешімдерінің байланысы келесі теоремамен беріледі.

Теорема. (түйіндестік теоремасы).

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

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

 

 

 

 

 

Соңғы базистің компоненттерінің матрицасы D десек, онда кестенің элементтері векторларының осы базистегі жіктелу коэффициенттері болады, яғни (3) орындалады. Оптималдық шешім үшін векторларының жіктелу коэффициенттерінен құрылған матрица десек, (3) - (4) қатынастардан аламыз.

мұнда ал - векторының компоненттері оң таңбалы емес, себебі олар оптималды шешім бағаларымен бірдей.

Бастапқы есептің оптималдық шешімі болғандықтан, түйіндес есеп шешімін

түрінде іздестіреміз. түйіндес есептің шешімі болатындығын көрсетелік. (2) теңсіздікті түрінде жазып, сол жағына қойсақ , теңсіздігін аламыз, ал бұдан екендігі, яғни түйіндес есептің шешімі екендігіне көз жеткіземіз.

Бұл шешім үшін , ал (9), (6), (7) қатынастардан

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

Енді оптималдық шешім болатындығын көрсетейік. Ол үшін (1) – ні қосалқы есептің кезкелген Y шешіміне, (2) – ні бастапқы есептің кезкелген х шешіміне көбейтеміз:

бұдан

орындалады. Бұл қатынас арқылы экстрамалды мәндері де байланысты.

max f (Y) £ min Z (x)

Соңғы теңсіздіктен

max f (Y) = min Z (x)

 

екендігі шығады, ал бұл шешімінде ғана орындалады, демек түйіндес есептің оптималды шешімі.

Дәл осылайша, түйіндес есептің шешімі болса, бастапқы есептің де шешімі болатындығын және

 

max f (Y) £ min z () екендігін көрсетеміз.

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

Дәлелденген теорема түйіндес есептердің біреуінің шешімі арқылы екіншісінің оптималдық шешімін табуға көмектеседі.

Бастапқы есеп.

 

Жол – матрица С = (1; 0; -1; 0; 0 – 2; 0),

Баған – матрица

 

Түйіндес есеп. f=y1 + y2 + 3 y3 ® max

Бастапқы есептің шешімін симплекс әдісімен табамыз.

 

 

і Б Сб А0 С1=10 С2=6 С3=8 С4=-2 С5=-М С6=-М
А1 А2 А3 А4 А5 А6
А5 А6 -M -M
m+1 m+2 Zj-Cj   -10 -6 -8
-9 -5 -7 -4 -4
А5 А1 -M 3/2 3/2 3/2 ½ 3/2 ½ -3/2 ½
m+1 m+2 Zj-Cj   -3
-3/2 -2 -3/2 -3/2 5/2
А3 А1 4/3 1/3 2/3 -1/3 -1
m+1 m+2 Zj-Cj  

 

(m+2)- жолында теріс таңбалы элементтердің болуы кеңейтілген есептің тірек шешімінің оптималды еместігін білдіреді. Онда мәні

 

Оптималдық шешім. Түйіндестік теоремасына сәйкес түйіндес есептің оптималдық шешімі соңғы базиске енген А5, А4, А3 векторларының компоненттерінен құрылған D матрицасына кері матрица,

кері матрица D1, А2, А4, А6 бағандарының соңғы итерациядағы коэффициентерінен құралады

 

да соңғы итерациядан алынады.

Сонымен

яғни - алғашқы бірлік матрицаның тиісті бағандарында соңғы итерацияда алынған коэффициенттерден тұрады. Немесе, і- қосалқы айнымалыны алғашқы бірлік матрица бағандарының (m+1) жолындағы бағаларына сызықтық функцияның тиісті коэфициенттерін қосу арқылы алуға болады:

Осы шешімдегі

Симметриялы түйіндес есептер.

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

 

Бастапқы есеп . Шектеулер жүйесін

Қанағаттандырып, сызықтық функцияны

минимизациялайтын баған – матрицаны табу керек.

Түйіндес есеп. Шектеулер жүйесін

қанағаттандырып, сызықтық функцияны

максимизациялайтын жол-матрицаны табу керек.

Қосымша айнымалылар енгізу арқылы теңсіздіктерді теңдеулерге айналдыруға болатындықтан, симметриялы қосалқы есептерді симметриясыз, қосалқылық теоремасы дәлелденген есептерге келтіруге болады. Симметриялықты пайдалану арқылы қосақталған есептерден шешуге ыңғайлысын таңдауға болады.

13, 14 – ші дәрістер.Түйіндес есеп пен шешімдерінің арасындағы байланыс. Тиімділік шарты. Түйіндестік есептердің математикалық моделдерінің түрлері

Негізгі есеп. Түйіндес есеп пен шешімдерінің арасындағы байланыс. Тиімділік шарты

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

(1)

шарттары

, . (2)

, . (3)

Қосалқы есеп: функцияның минимумын табу керек. Функция

, (4)

шарттары

. (5)

Теорема. Егер (1)-(3) немесе (4)-(5) қосалқы есептер жұптарының бірінде тиімді жоспар бар болса, онда басқаларында да тиімді жоспарлар бар болады және есептің мақсатты функциясының тиімді жоспарындағы мәндері өзара тең болады.

Теорема. (1)-(3) есебінің жоспары және (4)-(5) есебінің жоспары, берілген есептер жұбы үшін тиімді жоспарлар болып табылады, егер кез келген j ( ) үшін

теңдігі орындалса.

Қосалқы есептердің математикалық моделдерінің түрлері.

Қосақталған есептердің математикалық модельдері келесі түрлердің біреуіне жатады:

 

Бастапқы есеп. Қосалқы есеп

Симметриясыз есептер

Симметриялы есептер

Сонымен, берілген бастапқы есепке қосалқы есепті жазу үшін, бастапқы есептің шектеулер жүйесін белгілі түрдің біреуіне келтіру керек.

15, 16 – ші дәрістер. Сызықты бағдарламалауда транспорттық есеп. Есепті құру және оның математикалық модельі. Алғашқы тіреу планын құру. Солтүстік-батыс бұрышы әдісі. Кіші құн әдісі. Қос мүмкіндік әдісі. Транспорттық есептін ашық модель. Потенциал әдісі

.