Екі жақтылық есебі
Екіжақтылық ұғымы және оның мәні
Математиканың көптеген салаларында екіжақтылық теоремалары деп аталатын нәтижелер кездеседі. Мұндай теоремалар берілген теориядағы кез келген тұжырымнан белгілі бір ережелер бойынша екінші бір тұжырымды құруға мүмкіндік береді және алғашқы тұжырым дұрыс болса, екіншісінің дұрыстығы да автоматты түрде шығады.
Екіжақтылық идеясы сызықтық (мәтінде «стохастикалық» деп аталып кеткен) бағдарламалау есептерінде де маңызды орын алады. Төменде негізгі есеп пен оған екіжақты есептің құрылуын, олардың өзара байланысын және практикалық түсіндірілуін жүйелі түрде қарастырамыз.
Негізгі есеп (I) және екіжақты есеп (II)
Негізгі (I) есеп ретінде шектеулері теңсіздік түрінде берілген сызықтық бағдарламалау есебін алайық. Айнымалылар x₁, x₂, …, xₙ теріс емес және шектеулер жүйесі арқылы анықталады. Мақсат — сызықтық функцияны минимумдеу:
Мұндағы A — коэффициенттер матрицасы, b — бос мүшелер векторы, c — мақсатты функция коэффициенттері.
Осы есепке екіжақтылық байланыста болатын екінші есеп құрылады. Онда айнымалылар y₁, y₂, …, yₘ болады, мақсат — жаңа сызықтық функцияны максимумдеу:
Мұнда негізгі есептің матрицасы транспонирленіп (Aᵀ) қолданылады.
Екі есептің өзара сәйкестігі
Негізгі және екіжақты есепті салыстырғанда келесі негізгі заңдылықтар байқалады:
-
Негізгі есептегі коэффициенттерден құралған матрица мен екіжақты есептегі матрица бір-бірінен транспонирлеу арқылы алынады (жолдар бағандарға ауысады).
-
Әр есептің шектеулер жүйесінің оң жағындағы бос мүшелер екінші есептің мақсатты функциясының коэффициенттерімен орын ауыстырады (b ↔ c).
-
Негізгі есеп минимум табуға бағытталса, екіжақты есеп максимум табуға бағытталады.
-
Теңсіздік бағыттары қарама-қарсы болады: бір есепте ≥ болса, екіншісінде ≤ болады.
-
Бір есептегі айнымалылар саны екінші есептегі шектеулер санына тең болады.
Осы шарттарды қанағаттандыратын жұп есептер симметриялы екіжақты жұп деп аталады: біреуі — негізгі есеп, екіншісі — оның екіжақты есебі.
Кейде симметриялы емес жұптар да кездеседі: мұнда шектеулердің бір бөлігі теңдік түрінде беріледі және екіжақты есепте айнымалыларға теріс еместік талабы қойылмауы мүмкін.
Екіжақтылық теоремасы
Негізгі тұжырым
Егер негізгі есептің тиімді (оптимал) шешімі бар болса, онда екіжақты есептің де тиімді шешімі бар болады. Сонымен қатар, негізгі есептің мақсатты функциясының минимумы екіжақты есептің мақсатты функциясының максимумына тең:
Егер негізгі есептің мақсатты функциясы төменнен шектелмеген (яғни шексіз кішірейе беретін) болса, онда екіжақты есептің шектеулер жүйесінде теріс емес шешім болмайды.
Екінші теорема (қарама-қайшылық белгісі)
Егер тура (негізгі) есептегі мақсатты функция шектеусіз болса, онда оның екіжақты есебінің шешімі болмайды. Бұл жағдай есептің қойылымында қарама-қайшылық барын көрсетеді.
Екіжақтылық әдісі және екіжақты симплекс
Екіжақтылық теоремасына сүйенетін практикалық тәсілдердің бірі — екіжақтылық әдісі. Оның идеясы: бастапқы есеп берілсе, оған екіжақты есеп құрылады да, оны симплекс-әдіс арқылы шешу арқылы бастапқы есептің оптимумы туралы қорытынды жасалады.
Базистердің сәйкестігі туралы қағида
Өзара екіжақты (I) және (II) есептерінде бір есепте бастапқы базистен тиімді базиске көшуге болатын болса, онда екінші есепте де сәйкес базисті ауыстырғанда алынатын жаңа базис тиімді болады.
Бұл сәйкестік екі есептегі базистік және базистік емес айнымалылар коэффициенттері арқылы құрылады; практикада ол екіжақты симплекс әдісін қолдануға мүмкіндік береді.
Екіжақты симплекс әдісі әсіресе бастапқы есепте шектеулер саны айнымалылар санынан көп болғанда ыңғайлы.
Мысал: екіжақты есеп құру идеясы
Төменде есепті (II) деп алып, оған екіжақты (I) есепті қалай құруға болатыны көрсетіледі. Мәтіндегі жазылымдағы олқылықтарды түзеп, үлгі ретінде ықшам түрде берейік.
2y₁ − y₂ − y₃ ≤ −2
y ≥ 0
2x₁ − x₂ ≥ −2
−3x₁ − x₂ ≥ −3
x ≥ 0
Мұнда коэффициенттер матрицасы транспонирленеді, теңсіздік бағыттары ауысады, ал мақсаттың бағыты (max ↔ min) өзгертіледі. Қажет болғанда шектеулерді теңдікке айналдыру үшін қосымша айнымалылар (қалдық/артық) енгізіліп, есеп симплекс әдіске келтіріледі.
Экономикалық түсіндірме: ресурс бағасын анықтау
Екіжақтылықтың классикалық экономикалық мағынасы — ресурстардың «көлеңкелі бағасын» табу. Негізгі есепте кәсіпорын шектеулі ресурстарды пайдаланып өнім көлемін таңдайды және табысты максимумдеуге ұмтылады.
Тура модель (өндіріс жоспары)
f = ⟨c, x⟩ → max
Мұнда xⱼ — j-өнім мөлшері, cⱼ — оның бірлік пайдасы, ал aᵢⱼ — бірлік өнімге жұмсалатын i-ресурс шығыны.
Екіжақты модель (ресурс бағалары)
Егер кәсіпорын ресурстарды өнім өндірмей-ақ тікелей сатқысы келсе, онда әр ресурс бірлігіне баға yᵢ тағайындау керек. Сатып алушы бағаны азайтқысы келеді, ал сатушының табысы өнім өндірудегі ықтимал пайдадан кем болмауы тиіс.
Aᵀy ≥ c, y ≥ 0
Бұл шектеулер әр өнім үшін ресурстар құны оның өнім бағасынан (пайдасынан) аспау/кем болмау талаптарын білдіреді.
Екіжақты есеп құрудың қысқа алгоритмі
Екіжақты есепті құруды жүйелеу үшін мына қадамдар жиі қолданылады:
-
1) Теңсіздіктерді бір қалыпқа келтіру
Барлық шектеулерді бір типке келтіріңіз (≤ немесе ≥), қажет болса теңсіздікті −1-ге көбейтіңіз.
-
2) Коэффициенттер матрицасын белгілеу
A, b, c элементтерін айқын жазыңыз.
-
3) Транспонирлеу
Екіжақты есепте Aᵀ қолданылады: жолдар — баған, бағандар — жол болады.
-
4) «min ↔ max» және «≤ ↔ ≥» ауыстыру
Мақсат бағытын және теңсіздіктер бағытын екіжақтылық ережесіне сай ауыстырыңыз.
-
5) Айнымалыларға шектеулерді анықтау
Айнымалылардың теріс еместігі (x ≥ 0, y ≥ 0) немесе еркіндігі шектеулер түріне байланысты қойылады.
Мысалдар (құрылымдық түрде)
Мысал A: тура және екіжақты жұп
2x₁ + 4x₂ ≤ 8
2x₁ + x₂ ≤ 6
x ≥ 0
2y₁ + 2y₂ ≥ 6
4y₁ + y₂ ≥ 4
y ≥ 0
Мысал B: екіжақты есеп құруға арналған жаттығу
Төмендегі тура есеп үшін екіжақты есепті құрыңыз (айнымалылар теріс емес):
4x₁ + 2x₂ + 2x₃ + 3x₄ ≤ 35
x₁ + x₂ + 2x₃ + 3x₄ ≤ 30
3x₁ + x₂ + 2x₃ + x₄ ≥ 40
x ≥ 0
Алдымен үшінші теңсіздікті ≤ түріне келтіріп, содан кейін матрицаны транспонирлеу және ережелерді қолдану арқылы екіжақты модельді жазыңыз.
Мысал C: қысқа тапсырма
Келесі есеп үшін екіжақты есепті құрыңыз (теңсіздіктерді бір типке келтіріп барып):
2x₁ + 5x₂ − x₃ + 7x₄ ≤ 2
5x₃ − x₄ ≥ 3
3x₃ + 7x₄ ≤ 5
x ≥ 0
Қорытынды
Екіжақтылық — сызықтық бағдарламалаудағы ең қуатты ұғымдардың бірі. Ол есептің құрылымын терең түсіндіреді, оптимал мәндердің теңдігін береді және практикалық шешу әдістерін (соның ішінде екіжақты симплекс) негіздейді.