Сызықтық программалау есептерін шешудің симплексті əдісі



жүктеу 71.3 Kb.
Дата25.10.2018
өлшемі71.3 Kb.
Сызықтық программалау есептерін шешудің

симплексті əдісі

Жоғарыда қарастырылған сызба тəсіл өзінің көрнекілігіне байланысты бірқатар құндылыққа ие, бірақ n ≥ 3 болған жағдайда оны қолдану мүмкін емес. Мұндай есептерді шешу үшін басқа тəсілдер əзірленген. Осындай тəсілдердің бірі симплексті тəсіл болып табылады. Отандық əдебиеттерде ол жоспарды біртіндеп жақсарту тəсілі атауымен жиі кездеседі. Тəсілдің идеясы – онда есепті шешімі көпқырлылығының сүйір ұшын реттемелі іріктеу жүзеге асады. Қандай да бір бұрыштың сүйір ұшы алынады да, онда желілік форманың мəні есептеледі. Содан соң желілік форманың мəні көрші көпқырлылықтың сүйір ұштарында есептеледі. Желілік форманың мəні барынша жоғары болған бұрыштың сүйір ұшы бастапқы ретіндеқабылданады да, процедура қайталанады. Бұрыштың сүйір ұшын іріктеу есептің шешімі табылғанға дейін немесе есептің шешілмейтіндігі белгіленгенге дейін жүре береді. Сонымен қатар қадам саны түпкілікті, себебі жоспарлар жиынтығы немесе дөңес көпқырлылық, немесе дөңес көпқырлы аумақ, бірақ екі жағдайда да шеткі нүктелер (бұрыштардың сүйір ұштары) саны түпкілікті.


Симплекс әдісі

СБ есебінің оңтайлы шешімдері көпбұрыштың бұрыштық нүктелерімен байланысты. Егер айнымалылар саны n=50, теңсіздіктер саны m=25 болса, онда базистік жоспарлар саны болады. Сонда m және n үлкен сан болса, онда барлық негізгі алынатын жоспарларды іріктей отырып, оңтайлыны табу өте көп есептеуді қажет етеді. Сондықтан бір негізге алынатын жоспардан екіншіге ауысуға мүмкіндік беретін әдіс болуға тиіс. Осындай әдіс симплекс әдісі деп аталады. Есептеулердің әрқайсысында осы функцияның өткен жоспардағы мәнімен салыстырғанда осы функцияның өткен жоспардағы мәнімен салыстырғанда мақсатты функциядан кем немесе артық мәніне сәйкес келетін жаңа жоспар табылады. Есептеулерді оңтайлы жоспар алынғанға дейін жалғастырады. Егер мәселенің оңтайлы шешімі болмаса, онда симплексті әдіс оны есептеу кезеңінде анықтауға мүмкіндік береді.

Алғашқы жоспар құру. СБ есебі қойылған болсын.

Төмендегі функцияның барынша аз мәнін табу қажет.



(1.1)

мына шектеулерде



(1.2)

мұнда,



(1.3)

Шектеу жүйесінің m бірлік векторлары болсын деп ұйғарсақ, онда ол алғашқы m векторлар болады. Осыдан (1.1)-(1.3) есепті алғашқы m векторларға сәйкес түрлендіріп жазамыз:



(1.4)

мына шектеулерде



(1.5)

(1.6)

Жүйені (1.5) векторлық формада жазамыз:



(1.7)





векторлар – m өлшемді кеңістіктің сызықтық тәуелсіз бірлік векторлары. Сондықтан (1.7) өрнекте базистік айнымалылар ретінде . Ал еркін айнымалылар ретінде таңдаймыз, оларды нөлге теңестіріп, базистік айнымалыларды анықтаймыз. Мұнда >=0 (і= 1,2,…,m), ал бірлік векторлар екенін ескерсек, онда алғашқы жоспарды аламыз:

(1.8)

Жоғарыдағы (1.7)-ден (1.8) жоспарды ескерсек, төмендегі жіктеу шығады:



(1.9)

мұнда векторлар сызықтық тәуелсіз, демек, құрылған жоспар базис болып табылады.

1 – анықтама. Еркін белгісіздердің нөл мағыналарына сәйкес келетін шектеулер жүйесінің (1.2) шешімі базистік деп аталады.

Бастапқы негізге алынатын жоспарға (1.9) сүйене отырып, екінші негізге алынатын жоспарды қалай құруға болатынын қарастырамыз. Базиске кірмейтін кейбір вектор үшін, мысалы , жіктеудегі коэффициенттердің ең болмағанда біреуі оң болады деп ұйғарамыз.



Жүйенің оң жағы В бөлікті осы айнымалының оң коэффициенттеріне, яғни бөлеміз. Сөйтіп, векторы жоспар немесе жаңа базис болып табылады. Есептің m-нен асатын базисі болмайды, сондықтан қазіргі бар базистің біреуін алып тастаймыз. Ол үшін Q=min( таңдаймыз. Осы ең кіші мәні бірінші жолда тұрсын, яғни =min(. Сонда жаңа базистік шешім аламыз . Бұл базистен алып тастау, ал базиске енгізу қажет екенін білдіреді. Демек, негізге алынатын жаңа оның орнына базиске енгізілетін айнымалының векторын таңдау қажет.

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

(1.10)

(1.11)

Мұнда барлық >=0, j= 1,2,…,n, ал F – осы жоспарға сәйкес келетін функцияның мәні. Егер сызықтық функциядағы коэффициенті векторға сәйкес келсе, онда оңтайлылық өлшемі немесе сызықтық функцияның бағасы деп аталады.

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



- мақсат функциясының белгісіздер коэффициенттері.

Төмендегі теоремалар орын алады.

1 – теорема. Егер кейбір векторы үшін төмендегі талап орындалса,

,

онда жоспары функцияның максимумы үшін оңтайлы юолып табылады.

2 – теорема. Егер кейбір векторы үшін төмендегі талап орындалса,

онда жоспары функцияның минимумы үшін оңтайлы болып табылады.

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

Сөйтіп, мәселені симплекс әдіспен шешу мына сызба бойынша жүргізіледі:



  1. базистік шешім құрылады;

  2. осы шарт шешім оңтайлылық шартына тексеріледі;

  3. егер шарт орындалмаса, онда келесі базистік шешім құрылады да екінші тармаққа көшеді;

  4. оңтайлылық талабы орындалғанға дейін есептеулер қайталанады.

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

Симплекс әдісі алгоритмі

Симплекс әдістің кестедегі алгоритмін қарастырайық. Есепті максимумға қарастырамыз.

Симплекс – кесте





Базис

Оң жағы,



Айнымалылар

Q



1










2










...





… … … … … … …




m










m+1



0








  1. Алғашқы базистік жоспарды құру.

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

мұнда базистік айнымалылар, - еркін айнымалылар.

Енді симплекс әдісінің орындалу ретін (алгоритмін) кестеде қарайық.

1) Симплекс кесте құрамыз. Кесте шектеулер жүйесі коэффициенттерінен және оң жағынан тұрады. Кестенің соңғы жолы индекстік деп аталады және мақсат функциясының қарама-қарсы таңбаларымен алынған коэффициенттерімен толтырылған.

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

3) Бағыттаушы баған мен жолды анықтау. Бағыттаушы баған мен жолды табамыз. Бағыттаушы баған индекстік жолдың теріс санының барынша көп абсолюттік мөлшері бойынша, ал бағыттаушы жол – бос мүшелер векторы бағанының элементтерін бағыттаушы бағанның аз абсолюттік мөлшерімен анықталады. Бағыттаушы баған мен жол түйіскен жерде бас элемент орналасқан.

4) Жаңа негізге алынатын жоспар құру. Бағыт беруші жол мен бағанға сәйкес келетін белгісіз айнымалылардың орны ауыстырылады. Мұнда базистік айнымалы еркін айнымалы болады және керісінше. і жолда және j бағанда орналасқан элементтің () жаңа мәні элементтің () ескі мәнімен j баған мен бағыттаушы жол () түйіскен жерде орналасқан Элементті і жол мен бағыттаушы баған түйіскен жерде орналасқан элементке () көбейтіп, бас элементке () бөліп алып тастағанға тең болады. Бұл тікбұрыш ережесі деп аталады:



  1. Немесе төмендегі формулалар бойынша:

болса i≠r; болса i=r) (1.12)

болса i=r; болса i=r) (1.13)

(1.14)

Барлық осы сандар жаңа симплекс кестеде жазылады.



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



©stom.tilimen.org 2017
әкімшілігінің қараңыз

    Басты бет