Стохастикалық программалаудың өзара екі жақтылық есебі

Математиканың көптеген салаларында екі жақтылық теоремалары деп аталатын теоремалар кездеседі. Олардың әрқайсысы берілген теорияның кез-келген тұжырымы белгілі-бір ережелер стандарты бойынша екінші бір тұжырым алуға мүмкіндік береді және біріншісінің дұрыстығынан автоматты түрде екіншісінің де дұрыстығы алынады. Екі жақтылық есебінің мысалдары стохастикалық бағдарлау есебінде де кездеседі.

Өзара екі жақтылық есебін сипаттайық. Бастапқы немесе І-ші есепдеген атпен  стохастикалық бағдарлаудың қандай да бір болмасын есебі берілсін де шектеулер теңсіздіктер түрінде болсын. Сонымен

a₁₁х₁+а₁₂х₂+…

а₂₁-х₁+а₂₂-х₂+… 

п белгісізді т теңсіздікте жүйесі мен сызықты форма

f= с₁х₁+с₂х₂+… + с„х„(2)

берілсін.

(1)-ші жүйенің барлық теріс емес шешімдерінің ішінен (2)-ші форманы минимумдейтінін табу керек. Қойылған есеппен екінші бір есепті, яғни бастапқы есептен екі жақтылық байланыста болатын есепті қарастырайық. Оның қойылуы мынадай: т — белгісізі бар п теңдеулер жүйесі берілген:

а х  + а х  + … + а  х  ≤ b

…   …   …   …   …   …   … …

a x  + a x  + … + a x  ≤ b

a x  + a x  + … + a x = b

…   …   …   …   …   …   …  …

a x + a x  + … + a x  = b

және стохастикалық форма

 

cр = Ь₁у₁+Ь₂у₂+… + Ь_ту_т

түрінде жазылады.

(Г) жүйесінің барлық теріс емес шешімдерінің ішінен    (2′) формасын

максимумдейтінін таңдап алу керек. Бұл есепті (П) — есеп деп алайық.

Екі есепті салыстыру арқылы мынаны байқауға болады.

1. Бастапқы  есептегі  белгісіздер жанындағы  коэффициенттерден құрылған  матрицасы мен екі жақтылық есебіндегі матрицалары бір — бірін «транспонирлеуден», яғни жатық жолды бағаналармен ауыстырудан алынады. Олардың реттері сақталады.

1. Әр есептің шектеулер жүйесінің оң жағында екінші есептің сызықты формасының коэффициенттері орналасқан.
2. Бастапқы есептегі теңсіздіктер > — типті, і- формасының минимумы
   табылу керек те, ал екі жақтылық есебіндегі шектеулерде < — типті теңсіздіктер,
   яғни қарама-қарсы мағыналы, ал  ср     формасы максимум мэн, яғни қарсы
   мағыналы мэн қабылдайды.
3. Біреуінің белгісіздерінің саны, екіншісінің шектеулер санына тең.
4. Осы бес шартты қанағаттандыратын стохастикалық бағдарлау есебі симметриялы деп аталады. Оның біреуі негізгі, ал екіншісі — екі жақтылы есептер деп аталады.
5. Стохастикалық  бағдарлау есептерінде симметриялы екі жақты парлармен қатар, симметриялы емес те екі жақты парлар кездеседі. Онда:
6. а) Негізгі есеп: Теңдік сақталады:

а х + а х + … + а  х  ≤ b

…   …   …   …   …   …   … …

a x + a x + … + a x  ≤ b

a x  + a x  + … + a x = b

…   …   …   …   …   …   …  …

a x + a x  + … + a x = b

б) Екі жақтылық есебі:

а у  + а у  + … + а  у  ≤с

…   …   …   …   …   …   … …

a у  + a у  + … + a у  ≤ с

a у  + a у  + … + a у = с

…   …   …   …   …   …   …  …

a у + a у  + … + a у  = с

Бұл   есептер   симметриялы   пар   жағдайынан   мынадай   екі   жолмен ерекшеленеді:

1. (3) — (4)-ші есептердегі шектеулер теңдікпен берілген.
2. (3′)-(4′)-есептерінде  у_{   айнымалыларының  і = 1,т) теріс еместік

белгілері жоқ.

2. Сонымен қатар, екі жақтылық есебіндегі стохастикалық форма үшін

mах ср = —mіп(- ср)

— болатынын көрсетуге болады. Олай болса, екіншісі үшін екі жақтылық есебі, 1-ші есеппен бірдей болады, яғни симметриялы пардағы екі есеп, өзара екі жақты деп аталады.

Екі жақтылық теоремасы.Егер бастапқы есептің тиімді шешімі бар болса, онда екінші екі жақтылық есебінің де тиімді шешімі бар болады. Әрі / -формасының минимумы, ср -формасының максимумына тең болады.

тіп / = тах ф.

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

 Екі жақтылық әдісі

Екі жақтылық теоремасымен бағдарлау есебін шығарудың әдістерінің бірі «екі жақтылық әдісі»деп аталатын әдіспен байланысты. Оның мағынасы мынадай:

Стохастикалық бағдарлау есебі теңсіздік түріндегі шектеулермен берілсін. Оны біз Г-есебі ретінде қабылдайық та, ол үшін екі жақтылық есебі болып табылатын І-ші есепті құрып, оның шешімін симплекс-әдісті пайдаланып табайық. Бұл жағдайда екі жақтылық теоремасына мынадай қосымша енгізуге болады. Өзара екі жақты (I) жэне (II) есептері (1)-(2) жэне (1’)-(2′) түрлерінде берілсін. Егер І-ші есепте біз бастапқы базистен тиімді базиске көшетін болсақ, ал одан кейін (II) есебіндегі сәйкес базистерді ауыстырсақ, онда (II) есебіндегі жаңа базис те тиімді болады. Әрі біреуінің базисті шешімі екі жақтылық есебіндегі стохастикалық формасының сәйкес базисті емес айнымалыларының жанындағы коэффициенттерінің теріс таңбамен алынған жаңа базистік айнымалыларына теңестіру арқылы алынады.

Сәйкестік былай орнатылады:

^{Х        Х}„       ^Х  …    ^Хп+т

.    .    .    .    .   .    .   .   .

Ут+1′»  Ут+п   У  . . .      Ут

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

Мысал 1. ф = -у_х — 2у₂ — Зу₃ — формасын максимумдеу қажет болсын жэне ол келесі шектеулермен берілген

— у, + 2у₇ -Зу. 1

2у -у₂-у_ъ<-1

Бұл қойылған есепті ІІ деп алдық. Оған екі жақтылық есебі болатын І-ші есепті құрайық. Ол былай қойылады:

f = x₁ — x₂ — формасын минимумдеу керек жэне ол төменгі шектеулермен жүйесімен берілген.

-х_х + 2x₂ >-1

2x₁ — x₂ > -2

— 3×1 — x₂ > -3

Енді бұл форма мен шектеулердің қалай алынғанын түсіндірейік. Алдындағы келтірілген теория бойынша (1)-(2) жүйесі мен І»-формасы, (1′)-(2′) жүйесі және ср — формасымен мынадай байланыста болады.

ІІ есепте айнымалылар саны үшеу және де: с_х = 1-ге, с₂ = —1 —ге, т = 3 —тең. Теңдеудің саны екеу, ал жалпы түрде

ср = Ь_х -у_х +Ь₂ -у₂+… + Ъ_т -у_т.

Салыстыру арқылы b_х =, b₂ =-2, b_ъ=-3- терге тең және (Г)-тің бастапқы екі теңдеуінен

а_п =-1,    а_2Х =2, а_ъх =-3, а_п =2,      а₂₂ =-1, а_Ъ2 =-.ә

-екендіктеріне көз жеткіземіз.

Осы айтылғандарды пайдаланып І-есепті құрамыз.

/ = с_х-х_х+с₂-х₂+… + с_п -х„(2)

және (1)-ді табамыз. т = 3 — болғандықтан шектеулер жүйесі 3 теңдеуден тұруы керек.

с_х = 1, с₂ = -2 — болып табылды, сондықтан

/ = -х_х+(-)-х₂=х_х-х₂.

Енді (1)-ші шектеулерді жазайық

х₂>-1 (=b_Х) (2)-х₁₊(-)-х₂>-2 (=b₂) (-3)-х₁₊(-1)-х₂>-3 (=b₃) 

—    x₁ + 2x₂ >-1
2x₁ — x₂ > -2

—    3x₁ — x₂ > -3

F = x₁ -х₂.

—    Шектеулер жүйесі және мақсатты функция алынды. Екі жақтылы есебі шықты. Жаңадан    x₃,x₄,x₅  айнымалыларын қосу арқылы І-ші есепті мына

—    түрде жазуға болады.

—    1-ші есеп.

—    — x₁ + 2x₂ — x₃ = -1

—    -х₅=-3

—    Минимумдеу

—    / = x₁ — x₂ + 0 • x₃ + 0 • x₄ + 0 • x₅ 

— және барлық

—    айнымалылары теріс болмауы тиіс.

—    Есепті  симплекс-әдіспен  шығаруға  болады.   Тек,   есепті  келесі  түрге келтірген ыңғайлы

x₂ =2 + 2x₄ — x₅,

x₂ = 2 + 2x₁ — x₄,

f= x ₄    — x₁ 

    (II) — екінші  қарастырылған  есептің  экономикалық  мағынасына тоқталайық.

Ресурстары b_г і = ,т) өндіріс орны, бұл ресурстарды өнім шығару үшін

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

Ах<b,         х>0,     /_тах=тах<с,х>,    х_у>0      (у=м)                               (3) берілсін.

мұндағы   x_} — } -ші түрлі  өнім  шамасы,   С_} — } -ші түрлі  өнімнің  бір

бірлігінің шамасы, а_ц — } -ші өнім бірлігіне жұмсалатын / -ші ресурс шығыны.

Енді қандай бір болмасын өндіріс орны ресурстарын өнім дайындауға шығындамай-ақ, тікелей сатуға жіберуге үйғарды дейік.

Ресурсты қандай бағамен сату керек деген сұрақ туады?

Баға сатушыны да, сатып алушыны да қанағаттандыруы керек.

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

Есептің математикалыц моделі

1. Мақсатты функция

     —             (р = b_г у₁+b₂у₂ +. . . + b_ту_п—>mіп  (4)

сатып алатын жақтың мақсатын сипаттайды. у_т — /-ші ресурс бірлігінің бағасы.

2.   Шектеулер жүйесі сатып алушылардың қызығушылығын сипаттайды.

Әр өнім бірлігін дайындауға кеткен ресурстарды бағалау қажет. Сонымен қатар ол ресурстар бағасын өткізілетін өнім бірліктері бағасымен шектеу керек

3. Баға теріс бола алмайды.

_Уі>0   (і = ^п)                                                                                                      

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

	Негізгі есептің үлгісі	Жаңадан қойылған есептің үлгісі
1.	f =>mах	cр=>mіп
2.	Шектеулер жүйесі < — типті	Шектеулер жүйесі > — типті
3.	С} -лер    мақсатты    функцияның коэффициенттері	С} — бос мүшелер
4.	bг — бос мүшелер	bг-лер      мақсатты      функцияның коэффициенттері
5.	Шектеулер                         жүйесінің коэффициенттері => бағаналар	Шектеулер                            жүйесінің коэффициенттері => жатық жол

Осы екі жақты есеп болудың бес белгісі бізде бұрын айтылған.

І — тура есеп, ІІ — оған екі жақтылық есебі.

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

Екі жақтылықтың екінші теоремасы:

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

Мысал 1.

Тура есеп. f = 6x1 + 4x2-» mах 2x1 + 4x2 < 8  2x1 + x2 < 6	Екі жақтылық есебі. ср = 8x + 6x2 —> mіп 2y + 2y2 > 6 4у, +2у2 >4
х2>0.»

 Екіжақтылықесебінқұрудыңмысалдары. 

Мысал 1. Стохастикалықпрограммалау есебі қойылған: cызықты функция

Ғ = 14x₁ +10х₂ +14х₃ +11х₄ 

  келесі шектеулермен берілген.

4x₁ + 2x₂ + 2x₄ + 3x₄ < 35 x₁ +х₂ +2х₃ +3х₄ <30 3x₁ + x₂ + 2x₃ + x₄ > 40 x₁ >0,х₂ >0,х₃ >0,х₄ >0.

Қойылған есепке екі жақтылық есебін құрыңдар.

Шешуі:Есептің шешу жолын келесі кесте түрінде береміз.

Кесте 1

	Алгоритм	Қойылған алгоритмге сэйкестік
					Орнату
1	2				3
1	Шектеулер жүйесіндегі барлық	Үшінші		теңсіздікті  аталған түрге
	теңсіздіктерді < түріне келтіру	келтіреміз: —			3x1 — x2 — 2x3 — x4 < -40
2	Берілген жүйенің коффициенттері-
	нен құрылған Аі матрицасын		4	2     2	3     35
	құрамыз. Оның құрамына:	Л	1	1     2	3    30
	а) айнымалылар жанындағы коэф-	А —	-3	-1-2	-1-40
	фициенттер енеді;		^14	10 14	11     Ғ
	б) шектеулер жүйесінің оң жағын-	ч
	дағы бос мүшелер бағанасы енеді;
	в) стохастикалық функцияның қүрамын-
	дағы айнымалылары жанындағы
	коэффициенттер енеді.
3	Аі матрицаның транспонирленген		4	і -:	3        14 л
	А| матрицасын табу.		2	1   —	1        10
		4 =	2	2 —	2     -14
			3	3    —	1        11
			V35	30 —	40       Ғу
4	Алынған А| матрицасының негізінде	2 = 35у,		+ 30_у2	+ ? 40^3 -^ шіп
	екі жақтылық есебін құру.	4Уг+У2—		~з.у3 ^	14,
		2Уі+У°2		«3^3   *	ю,
		2ух+2у2		-2Уъ	>14,
				-Уз^	11
		У^0,у2		^0,у3	>0.

Мысал 2. Стохастикалық программалау есебі қойылған:

Ғ = 5x₁ — x₂ + 8x₃ — x₄ -^ тах

2x₁ + 5x₂ — x₃ + 7x₄ < 2,

■5x₃ — x₄ > 3,

■3x₃ + 7x₄ < 5

— X

^x2

x₁ >0,х₂ >0,х₃ >0,х₄ >0.

Қойылған есепке екі жақтылық есебін құрыңдар Екі жақтылық есебіне тағы бір мысал қарастырайық. Мысал -3. Берілген стохастикалық бағдарлау есебіне

+10х₂ —» шіп

+3х₂ > 6  + x₂ > 9

I x — 8_x < 8

x₁ > 0, x₂ > 0

екі жақтылық есебін құрыңдар.

  Шешуі: Келесі кестені құрайық.

Кесте 2

№	Алгоритм	Қойылған алгоритмге сәйкестік орнату
1	2	3
1	Шектеулер жүйесіндегі барлық теңсіздіктерді > түріне келтіру	Үшінші теңсіздікті  -хг+8x2 > -8 түріне келтіріп жазамыз
2	Кеңейтілген Аі матрицасын құрамыз.	А =	13       6 3      1      9 -1   8   -8 ч80 10     2у
3	Аі матрицаның транспонирленген 1′ матрицасын табу.	4 =	3    -1    80 3      1      8     10 6     9    -8     Ғ V                                   )
4	Табылған       А|        матрицасының негізінде    екі    жақтылық    есебін құрыңдар.	Ғ = вух + 9у2 — 8у3 —» тах ^+3^2-^3>80 Ъух +у2 +8у3 >10 Уі >0,у2 >0,у3 >0.