Сызықтық жоспарлаудағы екіұшты есеп

 

 

Сызықтық жоспарлаудағы  екіұшты есеп

 

 

Осыған  дейін айналысып келген сызықтық жоспарлау есебін тура сызықтық жоспарлау есебі деп аталық. Әрбір тура сызықтық жоспарлау есебіне оған екіұшты сызықтық жоспарлау есебін сәйкестікке қоюға болады (двойственная задача). Ол сәйкестік төмендегі таблицадағыдай болады:

 

 

 

Модельдердің жалпы түрі
Тура есеп	Екіұшты есеп
	кез келген
кез келген

 

 

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

 

Тура есеп		Екіұшты есеп
L=c1x1+c2x2+c3x3+c4x4      →max   a11x1+a12x2+a13x3+a14x4≤b1 a21x1+a22x2+a23x3+a14x4≤b2		T=b1y1+b2y2          →min   a11y1+a21y2≥c1 a12y1+a22y2≥c2 a13y1+a23y2≥c3 a14y1+a24y2≥c4

 

 

 

 

Төмендегі таблицада тура есептің әртүрлі  берілген жағдайында екіұшты есептің  қалай анықталатыны көрсетілген:

 

 

Өзара екіұшты симметриялық есептер
Тура есеп стандартты формада	Екіұшты есеп

 

 

Тура есеп канондық түрде берілген кез
Тура есеп	Екіұшты есеп
	оң да теріс те болады

 

 

Екіұштылық теоремалары

 

 

 

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

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

 

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

 

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

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

 

 

Екіұшты есептің экономикалық интерпретациясы

 

 

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

 

L(x) = ∑с_jx_j → mах 
∑a_ijxj ≤ b_i, 
x_j ≥0, i = 1,m,    j = 1,n.

 

Бұған екіұшты есептің математикалық  моделі төмендегідей болады:

 

Т(y) = ∑b_iy_i → min 
∑a_ijу_j ≥ c_j,

у_i ≥ 0, i = 1,m.

 

Егер  тура есептегі  бос мүшелерді  өзгертсек, онда ол өзгеріс тура есептің шешіміне әсер етеді, ол барып мақсаттық функцияның тиімді мәнінің де өзгеруіне әкеледі. Егер  у_i екіұшты есептегі тиімді шешімнің бір айнымалысының мәні болса, онда ол тура есептегі b_i бос мүшесінің (i- ші ресурсқа қойылған шектеу) мақсаттық функцияға әсерін сипаттайды екен, яғни у_i = ðL_i / ðb_i. Егер  ðL_i  ≈ ∆L_i, ðb_i  ≈ ∆b_i, десек, онда

 

∆L_i ≈ у_i*∆b_i.

 

Яғни  бұдан біз i –ші ресурстың құндылығы у_i - ге байланысты екенін көреміз. Егер   үлкен болса,  i - ші ресурстың көбейгені   табыстың көбеюіне әкеледі (тура пропорционал). Сондықтан у_i  айнымалысы  i - ші ресурстың құндылығын сипаттайды деп айтады.

 

 

Тура және екіұшты есептердің шешімдерінің арасындағы байланыс

 

 

Өзара түйіндес есептерді қарастыралық:

 

 

Бұларды канондық түрге келтірелік

 

 

Екі есептің екеуінде белгісіздердің сандары  бірдей    m+n. Тура есепте базистік айнымалылар ретінде қосымша енгізілген  х_n+1, х_n+2,…, х_n+m айнымалыларды алалық, екіұшты есепте  у_m+1, у_m+2,…, у_m+n  айнымалыларын алалық.

 

Екі есептің біреуіндегі базистік айнымалыларға  екіншісіндегі бос айнымалылар  сәйкес келеді жіне керісінше.и Айталық  тура есептегі х₁, х₂,…, х_n  бос айнымалыларға екіұшты есептегі у_m+1, у_m+2,…, у_m+n  базистік айнымалылар сәйкестікке қойылады, ал тура есептегі  х_n+1, х_n+2,…, х_n+m  базистік айнымалыларға екіұшты есептегі бос айнымалылар у₁, у₂,…, у_m сәйкестікке қойылады. Яғни:

 

x1	x2	…	xn		xn+1	xn+2	…	xn+m
­ ¯	­ ¯	­ ¯	­ ¯		­ ¯	­ ¯	­ ¯	­ ¯
ym+1	ym+2	…	ym+n		y1	y2	…	ym

 

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

 

Мысал қарастыралық:

 

L=4x1+6x2   ® max	T=y1+2y2+3y3      ®min
2x1+5x2£1 3x1+x2£2 -x1+2x2£3 x1,x2³0	2y1+3y2-y3³4 5y1+3y2+2y3³6 y1,y2,y3³0
Бұл есептерді канондық түрге келтірелік
L=4x1+6x2   ® max	T=y1+2y2+3y3      ®min
2x1+5x2+x3            =1 3x1+x2        +x4      =2 -x1+2x2             +x5=3 x1,x2,x3,x4,x5³0	2y1+3y2   -y3 -y4      =4 5y1+3y2+2y3       -y5 =6 y1,y2,y3y4,y5³0

 

Айнымалылар арсындағы сәйкестікті  жазалық

 

х3	х4	х5		х1	х2
­ ¯	­ ¯	­ ¯		­ ¯	­ ¯
у1	у2	у3		у4	у5

 

 

Осы сәйкестікті ескере отырып бір  есепті симплекс әдісімен шығарып екінші есептің шешімін табамыз.

Тура есепті шешкен кездегі ең соңғы  симплекс таблицаны келтірелік:

 

 

d	х1	х2	х3	х4	х5	Св	Ескерту
х1	1	5/2	1/2	0	0	1/2	® х1
х4	0	-13/2	-3/2	1	0	1/2	® х4
х5	0	9/2	1/2	0	1	7/2	® х5
L	0	4	2	0	0	2	®L=T
	­ ¯	­ ¯	­ ¯	­ ¯	­ ¯		х2=0, х3 =0
	y4	y5	y1	y2	y3

 

Бұдан Lmax=Tmin=2, Xmax={1/2; 0; 0;1/2;7/2}, Ymin={2;0;0;0;4}

 

 

 

Тасымалдау есебі

 

Тасымалдау есебінің шарты

 

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

1957 жылы Кеңес Одағында көмір  тасу үкіметтік аса маңызы  бар жұмыс болды, ол барлық  тасымал жұмысының 25 пайызын құраған  болатын: 384 млн. тонна көмірді  көмір өндіру бассейндерінде  орналасқан 30 ірі базадан 98 негізгі  ірі көмір тұтынушыларға тасылатын.  Осы тасымал есебін шешу арқылы  көмір тасу схемасы жасалды.  Сол кездегі Госпланның мамандары құрған схемаға қарағанда тасымал есебі арқылы анықталған схема 10.2 пайызға (110 млн. доллар, сол кездегі бағамен) үнемді болып шықты. Қазір, әрине мұндай үлкен тасымал жоспарланбайды, дегенмен көптеген транспорт ұжымдарында бұл есеп шешімі үлкен маңыз атқарады. Есеп әуел баста тасымал жұмыстарына арналғанмен, тасымал жұмыстарына қатысы жоқ есептер де осы модельге келтіреді, дегенмен тасымал есебіндегі терминологияны қолдану қалыптасып қалған.

Тасымал есебінің моделіне келтіретін басқа  есептердің мысалын кейінірек келтіреміз.

Есеп. Айталық материалдар (мысалы тауарлар) сақталатын жалпы саны m болатын    A₁,A₂,…,A_m пунктері (мысалы қоймалар) бар делік. Олардың әрқайсысында сәйкес қарастырылып отырған материалдардың  a₁,a₂,…,a_m  бірліктері (кг, литр, дана, шаршы метр т.с.с.) бар болсын. Сонымен қатар жалпы саны n  болатын B₁,B₂,…,B_n  тұтыну пунктері (мысалы дүкен, зауыт т.с.с.) бар болсын, алардың әрқайсысына сәйкес қарастырылып отырған материалдардың b₁,b₂,…,b_n  бірліктері қажет болсын. Қоймалардағы бар материалдардың мөлшерлерінің қосындысы мен тұтынушыларға қажетті материалдар мөлшерлерінің қосындысы тең болсын дейік (тең емес жағдай кейінірек қаралады). Яғни:

 

   (1)

Материалдарды қоймадан тұтыну пунктіне тасу бағалары белгілі болсын. Мысалы A_i пунктінен B_j (i=1,2,…,m;       j=1,2,…,n)  пунктіне бір бірлік материал тасу бағасы  c_ij болсын. Сол c_ij  сандары тікбұрышты матрица құрайды:

 

      (2)

(2) матрицаны тарифтік матрица деп атайды.  Тасу бағасы материал өлшеміне тура пропорционал деп есептейміз.

Тиімді  тасу жоспарын құру керек. Яғни барлық тасымал жұмыстары жүргізіліп, тасымал  жұмыстарының жалпы құны ең аз (ең тиімді) болуы керек.