Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Осжақтылықтың негізгі теоремалары.
Ө зара қ осжақ ты есептер берілсін. Теорема 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.4. Ө зара қ осжақ ты есептердің біреуінің тиімді шешімінің оң (нө лдік емес) компоненттері екінші есептің тиімді шешімінің нө лдік компоненттеріне сә йкес келеді, яғ ни кез келген , ү шін: егер болса, онда ; егер болса, онда ; егер болса, онда ; егер болса, онда . Осы теоремадан келесі маң ызды қ орытынды алынады: ө зара қ осжақ тылық есептерінің айнымалыларының арасындағ ы енгізілген (3.12) сә йкестік оптимумғ а жеткен кезде (яғ ни ә рбір есепті симплекс ә діспен шешкен кезде соң ғ ы қ адамда) қ осжақ тылық есептерінің біреуінің негізгі айнымалылары (нө лге тең емес) мен екіншісінің негізгі емес айнымалылары (нө лге тең) жарамды базистік шешімді берген кезде олардың арасындағ ы сә йкестікті береді. 3.4-теорема келесі теореманың салдары болып табылады. Теорема 3.5 (қ осжақ тылық тың екінші теоремасы). Қ осжақ ты есептің тиімді шешімінің компоненттері бастапқ ы есептің тиімді шешімінің негізгі емес айнымалылары арқ ылы ө рнектелген сызық тық функциясының сә йкес айнымалыларының коэффициенттерінің абсолют мә ніне тең. 3.4-теореманы қ осжақ тылық теориясының екінші теоремасы ретінде қ арастыруғ а болады. Ескерту. Егер ө зара қ осжақ ты есептің біреуінің тиімді шешімінің жалғ ыздығ ы жойылса, онда екіншісінің тиімді шешімі ө згеше болады. Қ осжақ тылық теориясының теоремаларының кө мегімен бастапқ ы есепті симплекс ә діспен шығ арып, бастапқ ы есепке қ осжақ ты есептің оптимумын жә не тиімді шешімін табуғ а (қ осжақ ты есепті шығ армай) болады. Алдымен қ осжақ ты есеп симплекс ә діспен шығ арылып, одан кейін бастапқ ы есептің оптимумы жә не тиімді шешімі қ осжақ тылық теориясының теоремаларының кө мегімен анық талатын ә діс қ осжақ ты симплекс ә дісі деп аталады. Бастапқ ы есептің алғ ашқ ы базистік шешімі жарамды емес болса, немесе, мысалы, оның шектеулер саны айнымалылар санынан артық болғ ан жағ дайда осы ә дісті қ олданғ ан ың ғ айлы.
|