Осжақтылықтың негізгі теоремалары.

Ө зара қ осжақ ты есептер берілсін.

Теорема 3.1 (қ осжақ тылық теориясының негізгі тең сіздігі). Кез келген бастапқ ы есептің жарамды шешімдері жә не қ осжақ ты есептің жарамды шешімдері ү шін келесі тең сіздік ақ иқ ат:

немесе . (3.7)

Теорема 3.2 (тиімділіктің жеткілікті белгісі немесе Канторовичтің тиімділік критерийі).

Егер жә не ү шін

(3.8)

тең дігі орындалатындай ө зара қ осжақ ты есептердің жарамды шешімдері болса, онда - бастапқ ы есептің тиімді шешімі, ал - қ осжақ ты есептің тиімді шешімі болады.

Қ осжақ тылық тың бірінші (негізгі) теоремасы.

Теорема 3.3 (бірінші теорема - жарамды шешімнің тиімділігінің қ ажетті белгісі). Егер ө зара қ осжақ ты есептердін біреуінің тиімді шешімі бар болса, онда екіншісінің де тиімді шешімі бар болады, жә не олардың сызық тық функциясының тиімді мә ндері ө зара тең болады:

немесе . (3.9)

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

3.3-теорема (3.8) тең діктің тек қ ана шешімнің тиімділігінің жеткілікті белгісін кө рсетіп қ оймай, сонымен қ атар ө зара қ осжақ ты есептердің шешімінің тиімділігінің қ ажетті белгісі болып табылатынын да кө рсетеді.

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

Ө зара қ осжақ ты есептер берілсін: (3.1)-(3.3) – бастапқ ы есеп, (3.4)-(3.6) – қ осжақ ты есеп. Осы есептерді симплекс ә діспен шығ ару ү шін осы есептің ә рқ айсысын канондық тү рге келтіру керек. Ол ү шін бастапқ ы есептің (3.1) шектеулер жү йесіне теріс емес - айнымалыларын қ осамыз, ал қ осжақ ты есептің (3.4) шектеулер жү йесіне теріс емес айнымалыларын қ осамыз, мұ ндағ ы () - () қ осымша айнымалысы енгізілген тең сіздік нө мірі. Сонда ө зара қ осжақ ты есептің ә рқ айсысының шектеулер жү йесі мына тү рде жазылады:

, , (3.10)

, . (3.11)

Қ осжақ ты есептердің біреуінің бастапқ ыда берілген айнымалылары мен екіншісінің қ осымша айнымалыларының арасындағ ы сә йкестікті орнатайық:

Бастапқ ы есептің айнымалылары	(3.12)
Бастапқ ы айнымалылар	Қ осымша айнымалылар
... ... ... ...	... ... ... ...
Қ осымша айнымалылар	Бастапқ ы айнымалылар
Қ осжақ ты есептің айнымалылары

Теорема 3.4. Ө зара қ осжақ ты есептердің біреуінің тиімді шешімінің оң (нө лдік емес) компоненттері екінші есептің тиімді шешімінің нө лдік компоненттеріне сә йкес келеді, яғ ни кез келген , ү шін:

егер болса, онда ; егер болса, онда ;

егер болса, онда ; егер болса, онда .

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

3.4-теорема келесі теореманың салдары болып табылады.

Теорема 3.5 (қ осжақ тылық тың екінші теоремасы). Қ осжақ ты есептің тиімді шешімінің компоненттері бастапқ ы есептің тиімді шешімінің негізгі емес айнымалылары арқ ылы ө рнектелген сызық тық функциясының сә йкес айнымалыларының коэффициенттерінің абсолют мә ніне тең.

3.4-теореманы қ осжақ тылық теориясының екінші теоремасы ретінде қ арастыруғ а болады.

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

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

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