Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Дәріс конспекті. Дәріс тақырыбы: Энергетикадағы оптималдандыру есептері




Дәріс тақырыбы: Энергетикадағы оптималдандыру есептері. Сызықты оптималдандыру есептері.

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

Электрлік жүйе басқару айнымалыларымен, күйінің айнымалыларымен, сонымен қатар оптималдандыру мәселелерінің көптеген критерийлерімен сипатталады.

Оптималдандыру мәселесін шешу үшін электрлік схеманы математикалық модель түрінде келтіру қажет.

Математикалық модельде келесідей құраушыларын атап өтуге болады:

1) жүйенің параметрлері (торап конфигурациясы, электр берілісі желісінің және трансформаторлардың активті және реактивті кедергілері және т.б.);

2) кернеудің сыртқы және ішкі әсері, тізбектің әр түрлі нүктелерінде электрлік жүктемелердің мәндері;

3) басқару айнымалылары немесе басқарушы әсерлер, мысалы ажырау нүктелерінің орналасуы;

4) режим күйінің айнымалылары – ағын таралу режимінің айнымалылары және т.б.;

5) оптималдандыру критерийі немесе мақсаттылық функция, мысалы, қуат шығынының шамасы немесе келтірілген шығындардың минимумы;

6) режим күйінің айнымалыларына және басқару айнымалыларына қолданылатын шектеулер – кернеудің деңгейі және жүктеменің рұқсат етілген токтары.

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

Z(х1, х2,... хn)→ extr, (4.1)

мұнда х1, х2,... хn – анықталатын айнымалылар, мәндері есепті шешу барысында есептеледі; айнымалылардың жалпы саны n.

Анықталатын айнымалылар өз сипаты бойынша үзіліссіз, дискретті және бүтін санды деп бөлінеді.

Егер айнымалы кез-келген мәнді қабылдаса, онда мұндай айнымалы үзіліссіз деп аталады. Үзіліссіз айнымалының мысалы ретінде электр берілісі желісі бойымен берілетін токты жатқызуға болады.

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

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

Егер айнымалы белгілі бір мәндерді ғана қабылдаса, онда мұндай айнымалыны дискретті деп атайды.

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

(4.1) мақсаттылық функцияда айнымалылар арасындағы тәуелділік сызықты немесе бейсызықты бола алады.

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

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

 

f11, х2,... хn) < b1;

f21, х2,... хn) = b2;)

…………………….. (4.2)

fm1, х2,... хn) > bm.

 

Шектеулердің жалпы саны m.

bj (j=1, 2, … m) тұрақты коэффициенттері ретінде берілген шектеулердің оң жағы бос мүшелер деп аталады.

Шектеулер жүйесіндегі айнымалылардың арасындағы тәуелділіктер сызықты немесе бейсызықты бола алады.

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

di < хi < Di, i=1, 2, … n, (4.3)

мұнда di және Di – сәйкесінше xi айнымалының өзгеру диапазонының төменгі және жоғарғы шегі.

Техникалық есептерде анықталатын айнымалылар, әдетте, теріс болмайды. Бұл кезде шектік шарттар келесі түрде болады:

хi > 0, i = 1, 2,... n. (4.4)

Оптималдандыру есептерінің көбісін шешу үшін математикалық программалау әдістерін қолданады. Бұл әдістер (4.1) мақсаттылық функцияның экстремальды мәндерін анықтауға мүмкіндік береді, бұл кезде айнымалылар арасындағы қатынастар (4.2) шектеулермен орнатылады және осы шектеулер (4.3) шектік шарттармен анықталатын айнымалының өзгеру диапазонында болады.

Математикалық программалау анықталатын оптималды шешімге әкелетін қайталанатын есептеу процедурасы болып табылады.

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

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

Егер математикалық модельде айнымалылар арасында бейсызықты тәуелділік болса, онда оптималдандыру есептері бейсызықты программалау әдістерін қолданады.

Сызықты программалау әдістері

Сызықты программалау есебі келесі түрде орындалады: сызықты теңдеулер және (немесе) теңсіздіктермен берілген шектеулермен және айнымалылардың өзгеру диапазонын көрсететін шектік шарттармен Z сызықты мақсаттылық функцияның экстремальды мәнін анықтау.

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

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

Симплекс – көп өлшемді дене төбелерінің жиынтығын білдіретін геометриялық ұғым.

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

Әдіс екі этаптан тұрады: бірінші этапта мүмкін шешім ізделеді; екінші этапта бұл мүмкін шешім оптималды мәніне дейін жақсартылады.

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

Жүйе канондық түрдің жүйесі деп аталады, егер әр теңдеуде базистік айнымалы болатын болса.

Базистік айнымалы деп (4.5) жүйенің бір теңдеуінде бірге тең коэффициенті болатын және жүйенің қалған теңдеулерінде және (4.6) мақсаттылық функцияның теңдеуінде кездеспейтін белгісіздер аталады.

Базистік емес айнымалылар деп барлық қалған айнымалыларды айтады.

Минимизацияланатын функция n белгісіздерге x1, x2, … xn тәуелді болсын: болғанда, мұнда i=1, 2, … n.

Шектеу теңдеулерінің канондық түрі:

(4.5)

(4.6)

мұнда x1, x2,…, xm – базистік айнымалылар, базистік айнымалылар саны m, белгісіздер саны n, бұл кезде n > m, ал xi ³ 0.

Егер жүйе (4.5) канондық түрде болса, әр шектеу теңдеуінде базистік айнымалы бар болса – бірінші мүмкін шешімді жазуға болады: барлық базистік емес айнымалылар (xm+1, xm+2,…,xn) нөлге тең, барлық базистік айнымалылар (x1, x2,…,xm) бос мүшелерге тең b1, b2,…,bm және Z минимизацияланатын функция Z0 -ге тең болады.

Z мақсаттылық функцияның оптималдық критерийі Z мақсаттылық функцияның минималды мәндерін (Cj ³ 0) табу кезінде (4.6) жүйедегі барлық Cj коэффициенттерінің теріс болмауында және Z функцияның максималды мәндерін (Cj £ 0) табу кезінде (4.6) жүйедегі барлық Cj коэффициенттерінің оң таңбалы болмауында.

Егер барлығы Cj ³ 0 болса, онда мәндердің теріс болмағандықтан базистік емес айнымалылардың кез-келген өзгерісі Z мәнін көбейтеді немесе оны сақтап қалады, ал бұл берілген шешімнің оптималдығын дәлелдейді.

Егер (4.6) жүйедегі коэффициенттердің бірі Cj < 0 болса, онда xj көбейту арқылы Z мәнін азайтуға болады. Бұл кезде xj белгісізі базистік емес санынан алынып тасталады (яғни базистікке кіреді).

Егер бірнеше Cj коэффициент (4.6) мақсаттылық функцияның теңдеуінде теріс болса, онда оптималдандыру процесін жылдамдату үшін ең кіші мәнімен коэффициентті таңдаған дұрыс, яғни ең үлкен абсолютті шамамен.

Мұндай ең кіші коэффициент келесідей белгіленеді Cs=min(Cj),
мұнда Cs < 0.

Базиске xs белгісізі енгізіледі. Базиске xs енгізген кезде Z шамасы азаяды, себебі көбейтінді болады.

Егер кейбір ai,s > 0 болса, онда xs шамасының көбеюіне шектеулер болады. Бұл кезде сәйкес базистік xі айнымалылар азаяды және осы мәндердің біреуі нөлге жеткен кезде, әрі қарай xs көбеюіне рұқсат етілмейді.

bi/ai,s қатынасы минималды болатын xі базистік айнымалысы бәрінен ерте нөлдік мәнге жетеді. xs шектік мәні келесі шарттан анықталады: xs=min(bi/ai,s), мұнда ai,s > 0.

xs -тің мұндай мәнінде базистік xi айнымалылардың бірі нөлдік мәнді қабылдайды, яғни xi базистік шамасы базистен шығарылып, базистік емес айнымалылар санына қосылады. r индексінің таңдалуы келесі шартпен анықталады: br/ar,s = min(bi/ai,s), мұнда ai,s > 0.

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

Ол үшін xs жаңа базистік айнымалыны (4.5) r жолы теңдеуінен басқа барлық теңдеулерінен алып тастау қажет. r жолы теңдеуінде xs болған кезде коэффициент бірге тең болуы қажет.

r жолынан xs айнымалысы анықталады және xs мәні қалған барлық теңдеулерге қойылады.

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

Мысалы: шектейтін теңдеулердің және мақсаттылық функцияның бастапқы жүйесі келесі түрде берілген:

Бірінші мүмкін шешім: x2 = x3 = 0 => x1 және x4 анықталады.

x1=2; x4=8; Z=0.

Мақсаттылық функция шешімі. Бұл шешім оптималды болып табылмайды, себебі х2 көбейген кезде Z артады.

Коэффициенті ең кіші мақсаттылық функцияда айнымалы таңдалады, яғни -6 x2. Енді теңдеуден нөлге тең емес барлық қосылғыштар шығарылады:

=>

Min (-1; )= .

Мақсат Z шамасын төмендету болғандықтан, минималды нүкте таңдалады , себебі (2) теңдеуде х2 мәні әрі қарай қаншалықты көбейсе де, х1 артады. Нәтижесінде x4 базистен шығарылады, ал x1 базиске кіреді.

Бастапқы жүйе канондық түрге келтіріледі. Ол үшін х2 келесі түрде өрнектеледі: =>

Өрнектелген х2 қалған теңдеуге және мақсаттылық функцияға қойылады

немесе

.

Жаңа теңдеулер жүйесі жазылады.

Мүмкін шешім қарастырылады

x3 = x4 = 0; x1 = ; x2 = ; Z= .

Нөлге тең емес қосылғыштар теңдеулерден алынады

Min (, ) = .

х1 базистен шығарылады, ал x2 базиске кіреді. х1 базистен шығарылатын теңдеуден х3 өрнектеледі

Қалған теңдеуге және мақсаттылық функцияға қойылады

немесе

Мүмкін шешім анықталады

x1 = x4 = 0; x2 = 4; Z=-28

Симплекс – алгоритмнің құрылымдық схемасы.

 

Негізгі әдебиет 1[1-100],

Қосымша әдебиет 1 [430-440]

Бақылау сұрақтары:

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

2. Энергетикадағы оптималдандыру есептерінің жалпы қойылымы.

3. Тасымалдау есебінің математикалық моделін жаз.

4. Тіректі жоспар – құру әдістері.

№14 дәріс конспекті:

Дәріс тақырыбы: Транспорттық есеп.

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

Транспорттық есептің математикалық аппаратын электрэнергетика есептеріне де қолдануға болады.

Мұнда өнім ретінде қорек көзінен электр берілісі желісі бойымен тұтынушыларға берілетін электрлік қуат қабылданады.

Қорек көздеріэлектр станциялары немесе қосалқы станциялар болып табылады, ал тұтынушыларэлектрэнергияның өнеркәсіптік, қалалық, ауылшаруашылықтұтынушылары.

Оптималдандыруға қорек көзі түйіндерін тұтынушылар түйіндерімен байланыстыратын электр берілісі желісінен тұратын электрлік торап схемасына кететін шығындар жатқызылады.

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

Тасымалдау есебін нақтырақ қарастыру үшін төмендегідей белгілеулер енгізейік.

А1, А2,…, Аn тарататын пункттер (электр станциялар) саны – n.

Әр станцияның өндіретін қуат көлемі – а1, а2,…, аn.

Таратылатын пункттер (электрэнергия тұтынушылары) саны – m.

Электрэнергиясын тұтынушылардың тұтыну көлемі b1, b2,…., bm.

Электр станциялардың қосынды қуаты электрэнергиясын тұтынушылардың қосынды қуатына тең.

Мұндай транспорттық есептер жабық деп аталады.

Әр Аі электр станциясынан әр электрэнергия тұтынушысына дейінгі электрэнергия құны Сi,j белгілі.

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

Электр торабына шығындар і қорек көздерінен j тұтынушыларына берілетін қуаттың меншікті құндарына көбейтінділерінің қосындысына тең. Сондықтан минималдандырылатын мақсаттылық функция келесі түрде жазылады:

(4.7)

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

Әр і -ші қорек көзі үшін желілердің бойымен барлық j=1,2,..., m тұтынушылар түйіндеріне берілетін қуаттардың қосындысы осы қорек көзінің Аі қуатына тең:

(4.8)

Әр j -ші қабылдағыш үшін барлық і=1,2,..., n қорек көздерінен желілердің бойымен берілетін қуаттардың қосындысы осы тұтынушының Вj қуатына тең:

(4.9)

Әр түйінде қуат балансын көрсететін (4.8) және (4.9) қатынастары транспорттық есепті шешу барысында шектеулер болып табылады.

Шектеулердің жалпы саны қорек көздері түйіндерінің санына және n+m тұтынушылар санына тең.

Теориялық электртехника курсынан белгілі, кез-келген электр торабы үшін 1-ші Кирхгоф заңы бойынша құрылған тәуелсіз теңдеулер саны түйіндер санынан бірге кем болады және (n + m - 1) құрайды.

Демек, тәуелсіз шектеулер саны (n + m - 1). Базистік айнымалылардың саны (нөлге тең емес) тәуелсіз шектеулер санына тең және (n + m - 1) құрайды.

Қалған айнымалылар бос мүшелер (нөлге тең) болып табылады. Бос айнымалылар саны (nm - (n + m - 1)) құрайды.

Әр xij базистік айнымалысы схемада і және j түйіндерінің арасында желінің барына сәйкес келеді, себебі і және j түйіндері арасында өтетін қуат нөлге тең емес.

Әр xij бос айнымалы схемада і және j түйіндері арасында желінің жоқтығына сәйкес келеді, себебі і және j түйіндері арасындағы өтетін қуат нөлге тең.

Қарастырылып отырған транспорттық есептің қойылымында қорек көздерінен тұтынушыларға таратылатын ізделетін xij қуаттары теріс емес. Демек, шектік шарттар келесі түрде жазылады:

xij > 0, i=1, 2,... n; j=1, 2,... m. (4.10)

(4.7)-(4.9) және (4.10) өрнектері транспорттық есептің математикалық моделі болып табылады. (4.7) мақсаттылық функцияның (4.8) және (4.9) шектеулердің өрнектері сызықты екені байқалады. Демек, транспорттық есепті сипмлекс-әдіспен шығаруға болады.

Бірақ транспорттық есепті бұл әдісті тікелей қолдану мақсаттылы болмайды.

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

Транспорттық есептің ерекшеліктері:

1. барлық шектеулер түрі теңдік түрінде болады;

2. айнымалылар кезінде барлық коэффициенттер шектеулер жүйесінде плюс бірге тең;

3. әр айнымалы шектеулер жүйесіне екі рет кіреді – бірінші рет (4.8) қорек көзі түйіндері балансына, екінші рет (4.9) тұтынушылар түйіндері балансына кіреді.

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

Транспорттық есепті шешу барысында жазудың кестелік формасын қолданған ыңғайлы. Бұл кезде (4.8), (4.9) шектеулері n ´ m өлшемділігімен транспорттық матрица түрінде жазылады.

Сол жағынан қорек көздерінің тапсырылған қуаттары A1, A2, …, An, жоғарғы жағынан – тұтынушылардың тапсырылған қуаттары B1, B2, …, Bm жазылады.

Транспорттық матрицаның торларында ізделетін xij айнымалылары және қуатты тасымалдаудың меншікті құнының Cij тапсырылған мәндері жазылады.

Матрицаның әр і -ші жолы і -ші қорек көзінің қуат балансы теңдеуіне, әр j- ші баған j -ші тұтынушының қуат балансы теңдеуіне сәйкес келеді.

 

j i В1 В2 Вm
b1 b2 bm
А1 a1 C11 x11 C12 x12   C1m x1m
А2 a2 C21 x21 C22 x22   C2m x2m
       
Аn an Cn1 xn1 Cn2 xn2   Cnm xnm

Оптималдандыру процедурасын орындамас бұрын, тіректік жоспарды (бастапқы ұйғарымдық шешім) құру қажет.

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

Мысал. Бастапқы берілгендер

j i В1 В2 В3 В4
       
А1          
А2          
А3          

«Солтүстік-батыс бұрышы әдісі». Транспорттық кестенің толтырылуын («солтүстік-батыс») бұрыштан бастаймыз.

В1 пунктіне 11 МВт қуат қажет: В1 пунктін А1 электр станциясынан электрэнергиясымен қамтамасыз етеміз.

Осыдан кейін А1 электр станциясында келесі қуат шамасы қалады: 22-11=11МВт. Бұл 11МВт қуатты көлденең В2 пункті бойынша көршілес торға береміз, бірақ В2 пунктіне 17МВт қажет, А1 электр станциясынан В2 пункті 11МВт алды, қалған жетпеген 11МВт қуатты А2 электр станциясынан аламыз 17-11=6 МВт.

А2 электр станциясында келесі қуаттың шамасы қалады 23-6=17 МВт. А2 электр станциясында қалған 17МВт қуатты көлденең бойынша В3 тұтынушыға көршілес торға береміз. Әрі қарай есептеулер осы түрде жалғаса береді.

Демек транспорттық матрица соңына дейін толтырылады.

Бұл жоспар орындалатынын тексереміз: орындалады, себебі жол бойынша тасымалдау соммасы сәйкес электр станциясының орныққан қуатына тең, ал баған бойынша тасымалдау соммасы – тұтынушының орныққан қуатына тең.

Тасымал бар торлар базистік деп аталады, тасымал жоқ торлар бос деп аталады.

 

j i В1 В2 В3 В4
       
а1   15 20    
а2     4 12  
а3       12 13

Барлық электр станциядан барлық тұтынушыға электрэнергиясын тасымалдаудың жалпы құны (Z мақсаттылық функция):

Z1 = 15×11 + 20×11 + 4×6 + 12×7 + 12×16 + 13×32 = 1101 мың теңге.

 

«Жолдағы минималды құны әдісі». Бірінші жол алынады (А1 электр станциясын таратамыз), ең төменгі құнын таңдаймыз, мүмкіншілік болғанша толық тасымал жасаймыз (егер минималды құнымен жолдар саны бірнеше болса, онда кез-келгенін таңдаймыз).

Минимум құнын таңдаймыз (15, 20, 7, 5). Минималды құн 5 мың теңге/МВт (мысалы, бес мың теңге тасымалданған бір мегаватт қуат үшін). А1 электр станциясы В4 тұтынушыға 22МВт қуатты бере алады.

j i В1 В2 В3 В4
       
а1         5
а2   10 4    
а3   3   12 13

А1 электр станциясының барлық қуаты тараттық және келесі А2 электр станциясын қарастырамыз, ең аз құны В2 тұтынушы үшін 4 мың теңге/МВт, бұл тұтынушы үшін 17МВт қажет, барлық 17 МВт А2 электр станциясынан, бірақ электр станциясынан тағы да қалғаны 23-17=6 МВт.

Берілген жолда қалған торлардан ең аз құнды таңдаймыз (В1 тұтынушы) және осы тұтынушыға 6МВт береміз. Есептеулер осы түрде жалғасады.

Жалпы құны келесі түрде анықталады:

Z2 = 5×22 + 10×6 + 4×17 + 3×5 + 12×33 + 13×10 = 779 мың теңге.

 

«Бағандағы ең аз құны әдісі». Жолдағы минималды құны әдісіне ұқсас орындалады.

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

Жалпы құны келесі түрде анықталады:

Z3 = 7×22 + 12×11 + 18×12 + 3×11 + 2×17 + 13×20 = 829 мың теңге.

j I В1 В2 В3 В4
       
а1       7  
а2       12 18
а3   3 2   13

 

Қарастырылған үш әдісті салыстырайық. Ең аз құны Z2 = 779 мың теңге.

Жолдағы минималды құны әдісі бойынша тіректік жоспарды қарастырайық.

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

Тасымалдау жоспарын оптималдандырудың барлық сыры теріс құнды циклдер бойымен тасымалдауды орындау болып табылады.

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

Цикл сызықтары тік бұрышпен түйіндік ұяшықтарда қиылысады және цикл ұяшықтарының саны жұп болады.

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

Бұл кезде берілген бос тор базистік болады, ал алдында болған базистік тор – бос тор болады.

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

Мұндай жоспар үшін циклдың теріс құнымен бос торлардың бірі де қалмайды. Бұл оптималды шешімнің табылғандығын көрсетеді.

Сызықты программалау теориясында циклдың теріс құнымен бос тораптарды автоматты түрде таңдауға мүмкіндік беретін әдістер бар. Бұл «Потенциалдар әдісі» болып табылады.

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

Оптималдандыру Ui, Vj симплекс-коэффициенттермен орындалады.

Егер барлық көлденең шектеу теңдеулерін сәйкесінше U1, U2, , Un шамаларына, ал вертикальды шектеу теңдеулерін V1, V2, , Vm шамаларына көбейтіп, сосын осы барлық теңдеулерді қоссақ және олардың қосындысын минималдандырылатын функцияның теңдеуінен алып тастасақ, онда Cij коэффициенттерінің жаңа мәндері барлық базистік белгісіздер үшін нөлге тең болады, яғни минималдандырылатын функцияның теңдеуінен базистік белгісіздер алынып тасталынады. Cij коэффициенттері базистік емес айнымалылар үшін жаңа мәндерге ие болады. Бұл симплекс-коэффициенттердің сипаттамасы болып табылады.

Егер Cij коэффициенттерінің жаңа мәндерін көрсетілген түрлендірулерден кейін Еij арқылы белгілесек, онда Еij, Cij және сипмплекс-коэффициенттері арасындағы байланысты табуға болады.

Түрлендірулерден кейін:

мұнда Eij = Сij - (Uij + Vij).

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

Барлық базистік белгісіздердің симплекс-коэффициенттерін анықтау үшін келесі теңдеулер қолданылады:

Cij = Ui + Vj. (4.11)

Мұндай теңдеулер саны (m + n - 1) (егер жабық транспорттық есеп болатын болса), ал коэффициенттер саны (m + n). Сондықтан коэффициенттердің бірі еркін түрде нөлге тең етіп қабылдауға болады.

Барлық симплекс-коэффициенттерін анықтаған соң, барлық базистік емес белгісіздер үшін коэффициенттердің Eij жаңа мәндерін анықтауға болады:

Eij = Cij – (Ui + Vj). (4.12)

- егер барлығы Eij > 0 болса, онда бастапқы базистік шешім оптималды болып табылады, себебі базистік емес айнымалылардан базистікке енгізілуі минималдандырылатын функцияны төмендетпейді.

- егер коэффициенттердің біреуі болса да Eij < 0 болса, онда базистік белгісіздер санына енгізілуі Z функциясын азайтады.

Егер Eij < 0 болатын торлардың саны бірнеше болса, онда осы торлар үшін қайта есептеу циклдері құрылады және ең үлкен шешімді, яғни maxêDZê беретін тор таңдалады.

Базистік айнымалыларға түзетулерді енгізген соң, өзгерген симплекс-коэффициенттер Uij, Vij, сосын жаңа Eij анықталады. Егер ең болмағанда біреуі теріс болса, онда базиске енгізілетін белгісізді анықтайды және т.с.с.

Оптималдандыру аяқталады, егер барлық Eij теріс болатын болса.

Мысал. Потенциалдар әдісімен оптималды жоспарды табу.

Үш электр станциясы, олардың орныққан қуаттары, электрэнергиясын таратудың меншікті құны (Cij) берілген.

 

 

Бастапқы берілгендер

j i В1 В2 В3 В4   Ui
       
A1               U1=0
A2           4* U2=-3
A3     2*       U3=-2
VJ V1=6 V2=7 V4=5 V4=8  

Тіректік жоспар жолдағы минималды құны бойынша құрылған. Транспорттық есеп жабылады, яғни ; .

Жолдар мен бағандардың балансы сақталған.

Базистік торлар саны m + n - 1= 3 + 4 - 1=6.

Z1 .

Симплекс-коэффициенттер (потенциалдар) базистік торлардан анықталады:

C12 = 7 = U1 + V2; C21 = 3 = U2 + V1; C13 = 5 = U1 + V3;

C31 = 4 = U3 + V1; C14 = 8 = U1 + V4; C34 = 6 = U3 + V4.

Потенциалдардың бірі нөлге теңестіріледі, әдетте базистік торлар саны көп болатын потенциал нөлге теңестіріледі (U1 = 0), ал қалған потенциалдар алынып тасталады.

V2 = 7; V3 = 5; V4 = 8; U3 = -2; V1 = 6; U2 = -3.

Базистік емес торлар үшін Eij анықталады:

E11 = 10 - (0 + 6) > 0; E22 = 6 - (-3 + 7) > 0;

E23 = 8 - (-3 + 5) > 0; E24* = 4 - (-3 + 8) = -1 < 0

E32* = 2 - (-2 + 7) = -3 < 0; E33 = 9 - (-2 + 5) > 0.

24 және 32 торлары үшін қайта есептеу циклдері құрылады.

 

 
21 24

- +

25

 

31 34

+ -

35 15

Бірінші вариант 24. Теріс таңбалы ұяшықтардан тасымалдаудың ең кіші көлемі таңдалады X34=15

DZ=15*(+4-6+4-3)=-15 мың теңге, яғни мақсаттылық функция 15 бірлікке төмендейді.

Z1=940-15=925 мың теңге.

Екінші вариант, тор 32

 

12 14

- +

45 15

 

 

 
32 34

+ -

Ең аз тасымал X34=15, Z мақсаттылық функция келесідей төмендейді

DZ=15*(+2-7+8-6)=-45 мың теңге. Z=940-45=895 мың теңге.

Егер екінші цикл (вариант) бойынша тасымалды қайта таратса, онда бұл үлкен пайданы әкеледі, яғни мақсаттылық функцияны 45 мың теңгеге төмендетеді.

Жаңа жоспар

j i B1 B2 B3 B4   Ui
       
A1                 U1=0
A2             U2=-6
A3                 U3=-5
Vj V1=9 V2=7 V3=5 V4=8  

 

Жолдар мен бағандар бойынша баланс сақталған. Базистік торлар саны

m + n - 1=3 + 4 – 1 = 6

Z2=7×30+5×40+8×30+3×25+4×35+2×15 = 895 мың теңге.

Базистік емес торлар үшін

E11 = 10 - (0 + 9) > 0; E24 = 4 - (-6 + 8) > 0; Е22 = 6 - (-6 + 7) > 0;

E33 = 9 - (-5 + 5) > 0; E23 = (8 - (-6 + 7) > 0; E34=6 - (-5 + 8) > 0






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных