Графтардағы тиімділеу есептерін шешу әдістері
Кіріспе 4
1 Графтардағы тиімділеу есептерін шешу әдістері 5
1.1 Графтағы тиімділеу есептердің жалпы сипаттамасы 5
1.1.1. Графтағы оптимизациялық есептердің математикалық қойылымы 5
1.1.2. Графтағы оптимизациялық есептерді шешудің негізгі әдістері 6
1.2 Графтағы минималды жабушы ағаш туралы есеп 7
1.2.1. Есептің математикалық қойылымы. 7
1.2.4. Сараң алгоритм көмегімен максималды және минималды жабылған ағаш туралы есепті шешу 10
1.3 Графтағы минималды жол туралы есеп 15
1.3.1. Есептің математикалық қойылымы 15
1.4 Бағытталған графтағы максималды жолды табу есебі 16
1.4.1. Бизнес . үрдістің орындалуының кризистік жолын табу есебінің мазмұндық қойылымы. 17
1.4.2. Есептің математикалық қойылымы 19
1.5 Желідегі максималды ағын туралы есеп 20
1.5.1. Есептің математикалық қойылымы. 20
Қорытынды
Қолданылған әдебиеттер тізімі 23
1 Графтардағы тиімділеу есептерін шешу әдістері 5
1.1 Графтағы тиімділеу есептердің жалпы сипаттамасы 5
1.1.1. Графтағы оптимизациялық есептердің математикалық қойылымы 5
1.1.2. Графтағы оптимизациялық есептерді шешудің негізгі әдістері 6
1.2 Графтағы минималды жабушы ағаш туралы есеп 7
1.2.1. Есептің математикалық қойылымы. 7
1.2.4. Сараң алгоритм көмегімен максималды және минималды жабылған ағаш туралы есепті шешу 10
1.3 Графтағы минималды жол туралы есеп 15
1.3.1. Есептің математикалық қойылымы 15
1.4 Бағытталған графтағы максималды жолды табу есебі 16
1.4.1. Бизнес . үрдістің орындалуының кризистік жолын табу есебінің мазмұндық қойылымы. 17
1.4.2. Есептің математикалық қойылымы 19
1.5 Желідегі максималды ағын туралы есеп 20
1.5.1. Есептің математикалық қойылымы. 20
Қорытынды
Қолданылған әдебиеттер тізімі 23
Оптимизацияның көптеген қолданбалы есептері графтағы тиімділеу есептері арқылы сипатталады. Бұнымен қатар, графтар теориясындағы есептер оптимизациялау есептерімен шешіледі. Осыған байланысты графтағы оптимизациялау есептерін зерттеу және оны шешу әдістерін білу қажеттілігі туады. Бұл есептерді шешкенде алгоритмдік ойлау қабілетті қажет етеді, ал бұл дегеніміз, қазіргі білім элементіне жатады. Жұмыста графтағы оптимизациялау есептерінің ішінде классикалыққа айналғандағы қарастырылған. Бұлар:
- оптималды жабатын ағашты табу есебі
- графтағы ең қысқа жолды табу есебі
- желілік графтағы кризистік жолды табу есебі
- графтағы максималды ағынды табу есебі
Графтағы оптимизациялау есептерінің бизнес – қосымшаларына:
- телекоммуникациялық провайдердің кабельдік желісін төсеу;
- қаладағы максималды адамдарды таситын транспорттық жүйені құру;
- автомобиль магистральдарындағы транспорттық ағымдарды реттеу.
- оптималды жабатын ағашты табу есебі
- графтағы ең қысқа жолды табу есебі
- желілік графтағы кризистік жолды табу есебі
- графтағы максималды ағынды табу есебі
Графтағы оптимизациялау есептерінің бизнес – қосымшаларына:
- телекоммуникациялық провайдердің кабельдік желісін төсеу;
- қаладағы максималды адамдарды таситын транспорттық жүйені құру;
- автомобиль магистральдарындағы транспорттық ағымдарды реттеу.
1. Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. – М.: Высшая школа, 1976. -392 с.
2. Таха Х. Введение в исследование операции. Том 1, 2..- М.: Мир, 1985.-480 с., - 495 с.
3. Форд Л., Фалкерсон Д. Потоки в сетях. - М.: Мир, 1966 - 276 с.
4. Ху Т. Целочисленное программирование и потоки в сетях.- М.: Мир, 1974. - 520 с.
2. Таха Х. Введение в исследование операции. Том 1, 2..- М.: Мир, 1985.-480 с., - 495 с.
3. Форд Л., Фалкерсон Д. Потоки в сетях. - М.: Мир, 1966 - 276 с.
4. Ху Т. Целочисленное программирование и потоки в сетях.- М.: Мир, 1974. - 520 с.
МАЗМҰНЫ
Кіріспе 4
1 Графтардағы тиімділеу есептерін шешу әдістері 5
1.1Графтағы тиімділеу есептердің жалпы сипаттамасы 5
1.1.1. Графтағы оптимизациялық есептердің математикалық қойылымы 5
1.1.2. Графтағы оптимизациялық есептерді шешудің негізгі әдістері6
1.2Графтағы минималды жабушы ағаш туралы есеп 7
1.2.1. Есептің математикалық қойылымы. 7
1.2.4. Сараң алгоритм көмегімен максималды және минималды 10
жабылған ағаш туралы есепті шешу
1.3Графтағы минималды жол туралы есеп 15
1.3.1. Есептің математикалық қойылымы 15
1.4Бағытталған графтағы максималды жолды табу есебі 16
1.4.1. Бизнес – үрдістің орындалуының кризистік жолын табу 17
есебінің мазмұндық қойылымы.
1.4.2. Есептің математикалық қойылымы 19
1.5Желідегі максималды ағын туралы есеп 20
1.5.1. Есептің математикалық қойылымы. 20
Қорытынды
Қолданылған әдебиеттер тізімі 23
Кіріспе
Оптимизацияның көптеген қолданбалы есептері графтағы тиімділеу
есептері арқылы сипатталады. Бұнымен қатар, графтар теориясындағы есептер
оптимизациялау есептерімен шешіледі. Осыған байланысты графтағы
оптимизациялау есептерін зерттеу және оны шешу әдістерін білу қажеттілігі
туады. Бұл есептерді шешкенде алгоритмдік ойлау қабілетті қажет етеді, ал
бұл дегеніміз, қазіргі білім элементіне жатады. Жұмыста графтағы
оптимизациялау есептерінің ішінде классикалыққа айналғандағы қарастырылған.
Бұлар:
- оптималды жабатын ағашты табу есебі
- графтағы ең қысқа жолды табу есебі
- желілік графтағы кризистік жолды табу есебі
- графтағы максималды ағынды табу есебі
Графтағы оптимизациялау есептерінің бизнес – қосымшаларына:
- телекоммуникациялық провайдердің кабельдік желісін төсеу;
- қаладағы максималды адамдарды таситын транспорттық жүйені құру;
- автомобиль магистральдарындағы транспорттық ағымдарды реттеу.
1 Графтардағы есептерді тиімділеу әдістері
1. Графтағы оптимизациялық есептердің жалпы сипаттамасы.
Графтағы оптимизациялық есептер класына кейбір мақсаттық функциялардың
оптимальдық мәнімен қамтамасыздайтын, графта арнайы обьектілерді табу
түрінде қалыптасқан оптимизациялау есебі жатады. Сонымен қатар, мақсаттық
функция түрі және шектеулер алдын-ала көрсетілмейді және оптимизация
есебінің нақты спецификасымен анықталады. Жалпы жағдайда графтағы
оптимизациялық есеп математикалық программалау есебі түрінде бастапқы есеп
түрін ескермейді, бірақ сәйкес есептің шешілуі оның математикалық қойылымы
үшін сәтті модель таңдауымен тығыз байланысты.
1.1.1. Графтағы оптимизациялық есептердің математикалық қойылымы.
Графтағы оптимизациялық есептер өзінің алғашқы қойылымында
бағдарланған немесе бағдарланбаған графтардың жалпы ұғымын қолданады.
Графтардың жалпы қасиетіне қосымша графтағы оптимизациялық есептер түрінде
қолданылатын арнайы обьектілер жолдар, ағаштар және ағымдар сияқтылар
қарастырылуға енгізіледі. Сонымен қатар, әрбір осындай обьектіге сәйкесінше
нақтылы граф негізінде есептелетін, оптимизациялау есебінің алғашқы
берілгендері ретінде қарастырылатын мақсаттық функцияның кейбір сандық
мәндері қойылады. Осы обьектілер үшін міндетті шарт кейбір конструкциялы
әдістердің тізімделуі бар болуы болып табылады, әйтпесе, сәйкес
оптимизациялау есебі есептік көзқараспен шешілмеуі мүмкін.
Сонымен, бөлек графтағы оптимизациялық есеп мақсаттық функцияның
максималды немесе минималды мәні сәйкес келетін арнайы обьектіні табу
сияқты болып қалыптасады.
Жалпы графтағы оптимизациялық есептің математикалық қойылымы мынадай
түрде қалыптасуы мүмкін:
немесе ƒ (x) → , (1.1.1)
мұнда х айнымалысы шартты түрде графтың кейбір арнайы обьектілерін
білдіреді, ал көптеген жіберілетін ∆β альтернативасында қарастырылатын
түрдің барлық мүмкін арнайы обьектілері бар. Сонымен қатар, мақсаттық
функция немесе шектеулер сипаттамаларына ешқандай қосымша болжамдар
берілмейді. Практикалық оптимизациялау есебінде негізгі графтар ақырлы
болып табылады, осы сияқты графтағы оптимизациялық типтік есептерінде
көптеген жіберілетін альтернативалар ақырлы болып табылады.
Графтағы оптимизациялық есептердің математикалық қойылымын
қарастыруда мүмкін альтернативалар жиынының нақты түріндегі жеке граф үшін
сәйкес оптимизация есебі осы не басқа арнайы обьектілер үшін бос болуы
мүмкін екенін ескеру қажет. Мысалы, оптимальды жабылған ағашты іздеу немесе
байланбаған граф жолы үшін өз мәнін жоғалтады. Осы себептен, графтағы
оптимизация есебінің бастапқы қойылымында сәйкес оптимизация есебінің
шешімі бар болатынын қанағаттандыратын графтың қосымша қасиетін көрсету
қажет.
1.1.2. Графтағы оптимизациялық есептерді шешудің негізгі әдістері.
Графтағы оптимизациялық есептердің жалпы математикалық қойылымы оның
шешімінің мүмкін әдістері туралы ешқандай ақпарат бермесе де, мұндай
есептердің шешілуінің барлық әдістерін шартты түрде екі классқа бөлуге
болады.
1. Танымал графтағы оптимизациялық есептердің көбісі бүтінсандық
математикалық модель немесе булевті программалау түрінде қалыптасуы мүмкін.
Бұл жағдайда оларды шешу тәсілін таңдау толығымен есептің қойылымына сәйкес
математикалық қасиеттермен анықталады. Графтағы оптимизациялық практикалық
есептерін MS Excel программасының көмегімен шешу мүмкіндігі есептің
бүтінсандық немесе булевті программалау түрінде қалыптасу мүмкіндігіне
тікелей байланысты.
2. Графтағы оптимизациялық есептер графтың қандай да бір
обьектілерінің спецификалық ерекшеліктерін және жиынның жіберілетін
альтернативалардың ақырлы қуатын ескеретін арнайы алгоритмдерді қолданып
шешілуі мүмкін. Бұл байланыста графтағы оптимизациялық есептер комбинаторлы
оптимизациялау есептерімен тығыз байланысты. Графтағы оптимизациялық
есептердің дәл шешімін табу үшін шекара және бұтақ әдісі және динамикалық
программалау әдісі түріндегі жалпы алгоритмдерді қолдануға болады,
есептеуіш көзқараспен арнайы алгоритмдер эффектілі болып табылады. Графтағы
оптимизациялық типтік есептердің дәл осындай, шешілу алгоритмдері осы
бөлімде қарастырылады және II бөлімде VBA программасына салынған.
MS Excel программасы бүтінсандық және булевті программалау есебінің
нақты шешімін табуға мүмкіндік беретіндіктен, оның көмегімен графтағы
оптимизациялық есепті шешуге мүмкіндік туады. Алынатын шешімнің нақты
бағасы үшін бөлек практикалық есептердің әртүрлі тәсілдермен алынған
оптимальды шешімдерін салыстыру керек. Осы мақсатпен бұл бөлімде графтағы
максималды және минималды ағашпен жабу есебінің және ең қысқа жол туралы
есептің шешілу тәсілдері сипатталған.
1.2. Графтағы минималды жабылған ағаш туралы есеп.
Бұл бөлімде булевті прогаммалау түріндегі оптимизациялау есебінің
шешімі және шарттарының формальды жазылуы үшін қолданылатын графтағы
минималды жабылған ағаш туралы есепің модификациясы қарастырылады.
1.2.1. Есептің математикалық қойылымы.
G= (V, E, h) бағдарланбаған тізбекті графты қарастырайық, мұндағы
V={v1,v2,...,vn } – төбелердің шекті жиыны, E= {e1,e2,...,en } – қабырғалардың
шекті жиыны, h: E→ Z + – қабырғалардың салмақтық функциясы. Есептің
математикалық қойылымы үшін қабырғалардың салмақтық функциясын cij=h(e k)
арқылы бөлек мәнін белгілеу ыңғайлы, мұндағы e k Є E қабырғасы {vi, vj } V
төбелер жұбына сәйкес келеді. Қарастырылған есептің мазмұндық қойылымымен
келісімді ci j= h ({vi, vj}) бөлек мәндері шығын ұзындығы немесе негізгі
графтың (i, j) учаскісінің құны сияқты түсіндірілуі мүмкін.
G графында Ek C E кез – келген қабырғалар жиынының құны осы жиынға кіретін
қабырғалар салмағының қосындысына тең. G графында жабылған ағашты
көрсететін және минималды құнды қабырғалар жиынын анықтау қажет етіледі.
Булевті программалау моделі түріндегі графтағы минималды жабылған ағаш
туралы есебінің шартының формальды жазылуы үшін графтағы жабылған ағаштың
екі шартымен қолдану қажет:
1. Бастапқы графтың әр төбесі минималды жабылған ағашқа кіретін кемінде
бір қабырғаға ие болуы қажет. Қарсы жағдайда ізделетін ағашта мұндай
төбелер бөлек алынады, демек, ағаш жабылған болмайды.
2. Минималды жабылған ағаштың қабырғаларының жалпы саны нақты түрде n – 1-
ге тең, мұндағы n – бастапқы граф төбелерінің жалпы саны. Шынында да,
егер кейбір ағаш қабырғалары n – 1-ден кем болса, онда ол жабылған
болады, егер ағаш қабырғалары n – 1-ден артық болса, онда ол циклды
болады.
Қарастыруға m булевті айнымалыларын енгіземіз. Ыңғайлы болу үшін xij
арқылы белгіленеді және келесі түрдегідей түсіндіріледі. Егер {vi,vj}
төбелер жұбына сәйкес келетін ekЄ E қабырғасы ізделетін минималды
құндыжабылған ағашқа енсе, онда айнымалы xij = 1, әйтпесе xij = 0. Яғни,
егер {vi,vj} қабырғасы оптимальды жабылған ағашқа енбесе. Онда жалпы
жағдайда графтағы минималды жабылған ағаш туралы есептің математикалық
қойылымы келесі түрде қалыптасуы мүмкін:
(1.2.1)
Мұндағы ∆β жіберілетін альтернатива жиыны келесі теңсіздік және теңдік
түріндегі шектеулер жүйесімен қалыптасады:
(1.2.2)
(1.2.3)
(1.2.4)
(1.2.5)
(1.2.6)
һ қабырғаларының салмақтық функциялары анықталмаған немесе 0-ге тең xij
айнымалылары (1.2.1) – (1.2.6) қарастырылатын есептің математикалық
қойылымына кірмейтінін ескерейік. (1.2.2) – (1.2.4) алғашқы үш шектеуі
алдын – ала белгіленген қасиеттерінің біріншісінің орындалуын талап етеді,
яғни ізделетін жабылған ағашта бөлек алынып тасталатын төбелері болмауы
қажет. (1.2.4) төртінші шектеуі алдын – ала белгіленген қасиеттерінің
екіншісінің орындалуын талап етеді, яғни ізделетін жабылған ағаштың n – 1
қабырғасы болуы қажет. (1.2.2) – (1.2.5) шектеулерінің жалпы саны n-ге тең.
(1.2.6) соңғы шектеуі айнымалылардың тек булевті мәндерін қабылдауын талап
етеді.
Егер графтағы минималды жабылған ағаш туралы есептің математикалық
қойылымындағы (1.2.1) – (1.2.6) мақсаттық функция мәнін (1.2.1) минимумды
іздеу операциясын максимумды іздеу операциясына ауыстырсақ, онда графтағы
максималды жабылған ағаш туралы есебіне сәйкес келетін математикалық
қойылымы алынуы мүмкін. Максималды және минималды жабылған ағаш туралы
есептің оптимальды шешімін табу үшін сараң алгоритм деген экзотикалық атау
алған арнайы әдіс ұсынылады.
1.2.4. Сараң алгоритм көмегімен максималды және минималды жабылған
ағаш туралы есепті шешу.
Программалық жабдықтар көмегімен алынған графтағы максималды жабылған
ағаш туралы есептің шешімінің дұрыс нәтижесі және бағаның дәлдігі үшін,
берілген класс есептерін шешу үшін өңделген сараң алгоритмін қолдануға
болады.
Сараң алгоритмді сипаттау үшін алдын – ала қарастырылуға екі жиын
төбесі: V – негізгі граф төбелерінің жабылған ағашпен байланысты жиын және
V0 – негізгі граф төбелерінің жабылған ағашпен байланыспаған жиын. Анықтама
бойынша: V U V0 = V, V ∩ V0 = Ø
Мұндағы V={v1, v2 ... vn } – G = (V, E, h) негізгі граф төбелерінің жиыны.
Максималды жабылған ағашқа кіретін қабырға жиынын E max арқылы белгілейміз.
Сараң алгоритм итеративті мінезге ие және келесі қадамдардың
орындалуын талап етеді:
1. Төбелері байланысқан және байланыспаған жиындардың алдын – ала
анықтамасы. Алгоритмнің негізгі итерациясын орындамас бұрын,
қарастыруға енгізілген төбелер жиынының келесі жолмен анықтаймыз: V =
{v1} және V0 = V {v1}. Мұндағы V1 төбесі таңдалады, жалпы жағдайда,
2. Алгоритмнің негізгі итерациясы. V және V0 жиындарының ішінен
төбелерді байланыстыратын қабырға жиындарының ішінен cij = h (e k)
максималды салмақты қабырғаны таңдау керек, мұндағы ек Є Е қабырғасы
{vi, vj} төбелер жұбына сәйкес келеді. Максималды салмақты қабырғаны
тапқаннан кейін E max = E max U ek тең болатын Emax жиынына қосылады.
Осымен қатар vj төбесі v0 жиынынан алынады және V0 = V0 {vj} және
V' = V U {vj}тең болатын V жиынына қосылады.
3. Алгоритм аяқталу шартын тексеру. V'0 = Ø шартының орындалуын тексеру.
Егер бұл шарт орындалса, онда негізгі графтың төбелерінің барлығы E
max максмалды жабылған ағашпен байланысты, және алгоритмнің орындалуы
осымен аяқталады. Ал егер бұл шарт орындалмаса, онда E max = E' max,
V0 = V'0, V = V' орнату керек және 2 қадам орындалуына көшу керек.
Қарастырылған сараң алгоритм схемасы UML тілінің қызметіндегі диаграмма
түрінде графикалы сипатталуы мүмкін. (1-сур.)
[V0= Ø] V0 Ø
1-сур. Максималды жабылған ағашты табу үшін сараң алгоритм диаграммасы
Қарастырылатын сараң алгоритм қолдануын 1 – сур. негізгі графы
көрсетілген максималды жабылған ағаш туралы жеке есепті шешу үшін
қарастырып көрейік. Бұл үшін сипатталған алгоритмге сәйкес келесі амалдарды
орындау қажет:
1 қадам. V = {v1}, V0 = {v2, v3, v4, v5, v6, v7} және Emax = Ø
орнату.
2 қадам (бірінші итерация). 2 қадам шартын қанағаттандыратын қабырға
ретінде {v1, v3} қабырғаны таңдау.Орнату: V' = {v1, v3}, V'0 = {v2, v4, v5,
v6, v7} және E' max = {{v1, v3}}.
3 қадам. V'0 = Ø алгоритм аяқталу шарты орындалмайтындықтан, 2 қадам
орындалуына көшу.
2 қадам (екінші итерация). 2 қадам шартын қанағаттандыратын қабырға
ретінде {v3, v5} қабырғасын таңдау. Орнату: V' = {v1, v3, v5}, V'0 = {v2,
v4, v6, v7} және E' max = {{v1, v3}, {v3, v5}}.
3 қадам. V'0 = Ø алгоритмнің аяқталу шарты орындалмайтындықтан, 2
қадам орындалуына көшу.
2 қадам (үшінші итерация). 2 қадам шартын қанағаттандыратын қабырға
ретінде {v5, v2} қабырғасын таңдау. Орнату: V' = {v1, v2, v3, v5}, V'0 =
{v4, v6, v7} және E' max = {{v1, v3}, {v3, v5}, {v5, v2}}.
3 қадам. V'0 = Ø алгоритмнің аяқталу шарты орындалмайтындықтан, 2
қадам орындалуына көшу.
2 қадам (төртінші итерация). 2 қадам шартын қанағаттандыратын қабырға
ретінде {v5, v7} қабырғасын таңдау. Орнату: V' = {v1, v2, v3, v5, v7}, V'0
= {v4, v6} және E' max = {{v1, v3}, {v3, v5}, {v5, v2}, {v5, v7}}.
3 қадам. V'0 = Ø алгоритмнің аяқталу шарты орындалмайтындықтан, 2
қадам орындалуына көшу.
2 қадам (бесінші итерация). 2 қадам шартын қанағаттандыратын қабырға
ретінде {v7, v6} қабырғасын таңдау. Орнату: V' = {v1, v2, v3, v5, v6, v7},
V'0 = {v4} және E' max = {{v1, v3}, {v3, v5}, {v5, v2}, {v5, v7}, {v7,
v6}}.
3 қадам. V'0 = Ø алгоритмнің аяқталу шарты орындалмайтындықтан, 2
қадам орындалуына көшу.
2 қадам (алтыншы итерация). Берілген итерацияда 2 қадам шартын
қанағаттандыратын екі қабырға бар: {v1, v4} және {v6, v4}. Ізделінген
қабырға ретінде олардың ішінен біріншісін таңдаймыз: {v1, v4}. Орнату
керек: V' = {v1, v2, v3, v4, v5, v6, v7}, V'0 = Ø және E' max = {{v1, v3},
{v3, v5}, {v2, v5}, {v5, v7}, {v6, v7}, {v1, v4}}.
3 қадам. V'0 = Ø алгоритмнің аяқталу шарты орындалатындықтан, онда
алгортимнің толық орындалуы осымен аяқталады. Нәтиже ретінде максималды
жабылған ағаш қабылданады: E' max = {{v1, v3}, {v3, v5}, {v2, v5}, {v5,
v7}, {v6, v7}, {v1, v4}}.
Алынған нәтижені берілген жеке есептің MS Excel программасының
көмегімен шешілу қорытындысымен салыстырсақ, олардың дәл келуін аламыз. Бұл
сәйкес келетін нәтижелердің дұрыстығына куә болады.
Қарастырылған сараң алгоритм графтағы минималды жабылған ағашты жабу
үшін жеңіл модификацияланған болуы мүмкін. Сонымен қатар, модификация 2
қадам амалының орындалуына ғана қатысты. Яғни, максималды салмақты қабырға
таңдаудың орнына минималды салмақты қабырға таңдау керек, ал міндетті шарт
өзгеріссіз қалады. Максималды жабылған ағашқа кіретін E max қабырға
жиынына қатысты, онда оның орнына минималды жабылған ағашқа кіретін,
барабар қасиетті иеленетін Emin қабырға жиынын қарастыру енгізіледі.
Негізгі графы 1- сур. көрсетілген минималды жабылған ағаш туралы жеке
есептің шешімі үшін сараң алгоритмің қолдануын көрсетеміз. Ол үшін
сипатталған алгоритмге сәйкес келесі амалдарды орындау қажет:
1 қадам. V = {v1}, V0 = {v2, v3, v4, v5, v6, v7} және Emin = Ø орнату.
2 қадам (бірінші итерация). 2 қадам шартын қанағаттандыратын қабырға
ретінде {v1, ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
Кіріспе 4
1 Графтардағы тиімділеу есептерін шешу әдістері 5
1.1Графтағы тиімділеу есептердің жалпы сипаттамасы 5
1.1.1. Графтағы оптимизациялық есептердің математикалық қойылымы 5
1.1.2. Графтағы оптимизациялық есептерді шешудің негізгі әдістері6
1.2Графтағы минималды жабушы ағаш туралы есеп 7
1.2.1. Есептің математикалық қойылымы. 7
1.2.4. Сараң алгоритм көмегімен максималды және минималды 10
жабылған ағаш туралы есепті шешу
1.3Графтағы минималды жол туралы есеп 15
1.3.1. Есептің математикалық қойылымы 15
1.4Бағытталған графтағы максималды жолды табу есебі 16
1.4.1. Бизнес – үрдістің орындалуының кризистік жолын табу 17
есебінің мазмұндық қойылымы.
1.4.2. Есептің математикалық қойылымы 19
1.5Желідегі максималды ағын туралы есеп 20
1.5.1. Есептің математикалық қойылымы. 20
Қорытынды
Қолданылған әдебиеттер тізімі 23
Кіріспе
Оптимизацияның көптеген қолданбалы есептері графтағы тиімділеу
есептері арқылы сипатталады. Бұнымен қатар, графтар теориясындағы есептер
оптимизациялау есептерімен шешіледі. Осыған байланысты графтағы
оптимизациялау есептерін зерттеу және оны шешу әдістерін білу қажеттілігі
туады. Бұл есептерді шешкенде алгоритмдік ойлау қабілетті қажет етеді, ал
бұл дегеніміз, қазіргі білім элементіне жатады. Жұмыста графтағы
оптимизациялау есептерінің ішінде классикалыққа айналғандағы қарастырылған.
Бұлар:
- оптималды жабатын ағашты табу есебі
- графтағы ең қысқа жолды табу есебі
- желілік графтағы кризистік жолды табу есебі
- графтағы максималды ағынды табу есебі
Графтағы оптимизациялау есептерінің бизнес – қосымшаларына:
- телекоммуникациялық провайдердің кабельдік желісін төсеу;
- қаладағы максималды адамдарды таситын транспорттық жүйені құру;
- автомобиль магистральдарындағы транспорттық ағымдарды реттеу.
1 Графтардағы есептерді тиімділеу әдістері
1. Графтағы оптимизациялық есептердің жалпы сипаттамасы.
Графтағы оптимизациялық есептер класына кейбір мақсаттық функциялардың
оптимальдық мәнімен қамтамасыздайтын, графта арнайы обьектілерді табу
түрінде қалыптасқан оптимизациялау есебі жатады. Сонымен қатар, мақсаттық
функция түрі және шектеулер алдын-ала көрсетілмейді және оптимизация
есебінің нақты спецификасымен анықталады. Жалпы жағдайда графтағы
оптимизациялық есеп математикалық программалау есебі түрінде бастапқы есеп
түрін ескермейді, бірақ сәйкес есептің шешілуі оның математикалық қойылымы
үшін сәтті модель таңдауымен тығыз байланысты.
1.1.1. Графтағы оптимизациялық есептердің математикалық қойылымы.
Графтағы оптимизациялық есептер өзінің алғашқы қойылымында
бағдарланған немесе бағдарланбаған графтардың жалпы ұғымын қолданады.
Графтардың жалпы қасиетіне қосымша графтағы оптимизациялық есептер түрінде
қолданылатын арнайы обьектілер жолдар, ағаштар және ағымдар сияқтылар
қарастырылуға енгізіледі. Сонымен қатар, әрбір осындай обьектіге сәйкесінше
нақтылы граф негізінде есептелетін, оптимизациялау есебінің алғашқы
берілгендері ретінде қарастырылатын мақсаттық функцияның кейбір сандық
мәндері қойылады. Осы обьектілер үшін міндетті шарт кейбір конструкциялы
әдістердің тізімделуі бар болуы болып табылады, әйтпесе, сәйкес
оптимизациялау есебі есептік көзқараспен шешілмеуі мүмкін.
Сонымен, бөлек графтағы оптимизациялық есеп мақсаттық функцияның
максималды немесе минималды мәні сәйкес келетін арнайы обьектіні табу
сияқты болып қалыптасады.
Жалпы графтағы оптимизациялық есептің математикалық қойылымы мынадай
түрде қалыптасуы мүмкін:
немесе ƒ (x) → , (1.1.1)
мұнда х айнымалысы шартты түрде графтың кейбір арнайы обьектілерін
білдіреді, ал көптеген жіберілетін ∆β альтернативасында қарастырылатын
түрдің барлық мүмкін арнайы обьектілері бар. Сонымен қатар, мақсаттық
функция немесе шектеулер сипаттамаларына ешқандай қосымша болжамдар
берілмейді. Практикалық оптимизациялау есебінде негізгі графтар ақырлы
болып табылады, осы сияқты графтағы оптимизациялық типтік есептерінде
көптеген жіберілетін альтернативалар ақырлы болып табылады.
Графтағы оптимизациялық есептердің математикалық қойылымын
қарастыруда мүмкін альтернативалар жиынының нақты түріндегі жеке граф үшін
сәйкес оптимизация есебі осы не басқа арнайы обьектілер үшін бос болуы
мүмкін екенін ескеру қажет. Мысалы, оптимальды жабылған ағашты іздеу немесе
байланбаған граф жолы үшін өз мәнін жоғалтады. Осы себептен, графтағы
оптимизация есебінің бастапқы қойылымында сәйкес оптимизация есебінің
шешімі бар болатынын қанағаттандыратын графтың қосымша қасиетін көрсету
қажет.
1.1.2. Графтағы оптимизациялық есептерді шешудің негізгі әдістері.
Графтағы оптимизациялық есептердің жалпы математикалық қойылымы оның
шешімінің мүмкін әдістері туралы ешқандай ақпарат бермесе де, мұндай
есептердің шешілуінің барлық әдістерін шартты түрде екі классқа бөлуге
болады.
1. Танымал графтағы оптимизациялық есептердің көбісі бүтінсандық
математикалық модель немесе булевті программалау түрінде қалыптасуы мүмкін.
Бұл жағдайда оларды шешу тәсілін таңдау толығымен есептің қойылымына сәйкес
математикалық қасиеттермен анықталады. Графтағы оптимизациялық практикалық
есептерін MS Excel программасының көмегімен шешу мүмкіндігі есептің
бүтінсандық немесе булевті программалау түрінде қалыптасу мүмкіндігіне
тікелей байланысты.
2. Графтағы оптимизациялық есептер графтың қандай да бір
обьектілерінің спецификалық ерекшеліктерін және жиынның жіберілетін
альтернативалардың ақырлы қуатын ескеретін арнайы алгоритмдерді қолданып
шешілуі мүмкін. Бұл байланыста графтағы оптимизациялық есептер комбинаторлы
оптимизациялау есептерімен тығыз байланысты. Графтағы оптимизациялық
есептердің дәл шешімін табу үшін шекара және бұтақ әдісі және динамикалық
программалау әдісі түріндегі жалпы алгоритмдерді қолдануға болады,
есептеуіш көзқараспен арнайы алгоритмдер эффектілі болып табылады. Графтағы
оптимизациялық типтік есептердің дәл осындай, шешілу алгоритмдері осы
бөлімде қарастырылады және II бөлімде VBA программасына салынған.
MS Excel программасы бүтінсандық және булевті программалау есебінің
нақты шешімін табуға мүмкіндік беретіндіктен, оның көмегімен графтағы
оптимизациялық есепті шешуге мүмкіндік туады. Алынатын шешімнің нақты
бағасы үшін бөлек практикалық есептердің әртүрлі тәсілдермен алынған
оптимальды шешімдерін салыстыру керек. Осы мақсатпен бұл бөлімде графтағы
максималды және минималды ағашпен жабу есебінің және ең қысқа жол туралы
есептің шешілу тәсілдері сипатталған.
1.2. Графтағы минималды жабылған ағаш туралы есеп.
Бұл бөлімде булевті прогаммалау түріндегі оптимизациялау есебінің
шешімі және шарттарының формальды жазылуы үшін қолданылатын графтағы
минималды жабылған ағаш туралы есепің модификациясы қарастырылады.
1.2.1. Есептің математикалық қойылымы.
G= (V, E, h) бағдарланбаған тізбекті графты қарастырайық, мұндағы
V={v1,v2,...,vn } – төбелердің шекті жиыны, E= {e1,e2,...,en } – қабырғалардың
шекті жиыны, h: E→ Z + – қабырғалардың салмақтық функциясы. Есептің
математикалық қойылымы үшін қабырғалардың салмақтық функциясын cij=h(e k)
арқылы бөлек мәнін белгілеу ыңғайлы, мұндағы e k Є E қабырғасы {vi, vj } V
төбелер жұбына сәйкес келеді. Қарастырылған есептің мазмұндық қойылымымен
келісімді ci j= h ({vi, vj}) бөлек мәндері шығын ұзындығы немесе негізгі
графтың (i, j) учаскісінің құны сияқты түсіндірілуі мүмкін.
G графында Ek C E кез – келген қабырғалар жиынының құны осы жиынға кіретін
қабырғалар салмағының қосындысына тең. G графында жабылған ағашты
көрсететін және минималды құнды қабырғалар жиынын анықтау қажет етіледі.
Булевті программалау моделі түріндегі графтағы минималды жабылған ағаш
туралы есебінің шартының формальды жазылуы үшін графтағы жабылған ағаштың
екі шартымен қолдану қажет:
1. Бастапқы графтың әр төбесі минималды жабылған ағашқа кіретін кемінде
бір қабырғаға ие болуы қажет. Қарсы жағдайда ізделетін ағашта мұндай
төбелер бөлек алынады, демек, ағаш жабылған болмайды.
2. Минималды жабылған ағаштың қабырғаларының жалпы саны нақты түрде n – 1-
ге тең, мұндағы n – бастапқы граф төбелерінің жалпы саны. Шынында да,
егер кейбір ағаш қабырғалары n – 1-ден кем болса, онда ол жабылған
болады, егер ағаш қабырғалары n – 1-ден артық болса, онда ол циклды
болады.
Қарастыруға m булевті айнымалыларын енгіземіз. Ыңғайлы болу үшін xij
арқылы белгіленеді және келесі түрдегідей түсіндіріледі. Егер {vi,vj}
төбелер жұбына сәйкес келетін ekЄ E қабырғасы ізделетін минималды
құндыжабылған ағашқа енсе, онда айнымалы xij = 1, әйтпесе xij = 0. Яғни,
егер {vi,vj} қабырғасы оптимальды жабылған ағашқа енбесе. Онда жалпы
жағдайда графтағы минималды жабылған ағаш туралы есептің математикалық
қойылымы келесі түрде қалыптасуы мүмкін:
(1.2.1)
Мұндағы ∆β жіберілетін альтернатива жиыны келесі теңсіздік және теңдік
түріндегі шектеулер жүйесімен қалыптасады:
(1.2.2)
(1.2.3)
(1.2.4)
(1.2.5)
(1.2.6)
һ қабырғаларының салмақтық функциялары анықталмаған немесе 0-ге тең xij
айнымалылары (1.2.1) – (1.2.6) қарастырылатын есептің математикалық
қойылымына кірмейтінін ескерейік. (1.2.2) – (1.2.4) алғашқы үш шектеуі
алдын – ала белгіленген қасиеттерінің біріншісінің орындалуын талап етеді,
яғни ізделетін жабылған ағашта бөлек алынып тасталатын төбелері болмауы
қажет. (1.2.4) төртінші шектеуі алдын – ала белгіленген қасиеттерінің
екіншісінің орындалуын талап етеді, яғни ізделетін жабылған ағаштың n – 1
қабырғасы болуы қажет. (1.2.2) – (1.2.5) шектеулерінің жалпы саны n-ге тең.
(1.2.6) соңғы шектеуі айнымалылардың тек булевті мәндерін қабылдауын талап
етеді.
Егер графтағы минималды жабылған ағаш туралы есептің математикалық
қойылымындағы (1.2.1) – (1.2.6) мақсаттық функция мәнін (1.2.1) минимумды
іздеу операциясын максимумды іздеу операциясына ауыстырсақ, онда графтағы
максималды жабылған ағаш туралы есебіне сәйкес келетін математикалық
қойылымы алынуы мүмкін. Максималды және минималды жабылған ағаш туралы
есептің оптимальды шешімін табу үшін сараң алгоритм деген экзотикалық атау
алған арнайы әдіс ұсынылады.
1.2.4. Сараң алгоритм көмегімен максималды және минималды жабылған
ағаш туралы есепті шешу.
Программалық жабдықтар көмегімен алынған графтағы максималды жабылған
ағаш туралы есептің шешімінің дұрыс нәтижесі және бағаның дәлдігі үшін,
берілген класс есептерін шешу үшін өңделген сараң алгоритмін қолдануға
болады.
Сараң алгоритмді сипаттау үшін алдын – ала қарастырылуға екі жиын
төбесі: V – негізгі граф төбелерінің жабылған ағашпен байланысты жиын және
V0 – негізгі граф төбелерінің жабылған ағашпен байланыспаған жиын. Анықтама
бойынша: V U V0 = V, V ∩ V0 = Ø
Мұндағы V={v1, v2 ... vn } – G = (V, E, h) негізгі граф төбелерінің жиыны.
Максималды жабылған ағашқа кіретін қабырға жиынын E max арқылы белгілейміз.
Сараң алгоритм итеративті мінезге ие және келесі қадамдардың
орындалуын талап етеді:
1. Төбелері байланысқан және байланыспаған жиындардың алдын – ала
анықтамасы. Алгоритмнің негізгі итерациясын орындамас бұрын,
қарастыруға енгізілген төбелер жиынының келесі жолмен анықтаймыз: V =
{v1} және V0 = V {v1}. Мұндағы V1 төбесі таңдалады, жалпы жағдайда,
2. Алгоритмнің негізгі итерациясы. V және V0 жиындарының ішінен
төбелерді байланыстыратын қабырға жиындарының ішінен cij = h (e k)
максималды салмақты қабырғаны таңдау керек, мұндағы ек Є Е қабырғасы
{vi, vj} төбелер жұбына сәйкес келеді. Максималды салмақты қабырғаны
тапқаннан кейін E max = E max U ek тең болатын Emax жиынына қосылады.
Осымен қатар vj төбесі v0 жиынынан алынады және V0 = V0 {vj} және
V' = V U {vj}тең болатын V жиынына қосылады.
3. Алгоритм аяқталу шартын тексеру. V'0 = Ø шартының орындалуын тексеру.
Егер бұл шарт орындалса, онда негізгі графтың төбелерінің барлығы E
max максмалды жабылған ағашпен байланысты, және алгоритмнің орындалуы
осымен аяқталады. Ал егер бұл шарт орындалмаса, онда E max = E' max,
V0 = V'0, V = V' орнату керек және 2 қадам орындалуына көшу керек.
Қарастырылған сараң алгоритм схемасы UML тілінің қызметіндегі диаграмма
түрінде графикалы сипатталуы мүмкін. (1-сур.)
[V0= Ø] V0 Ø
1-сур. Максималды жабылған ағашты табу үшін сараң алгоритм диаграммасы
Қарастырылатын сараң алгоритм қолдануын 1 – сур. негізгі графы
көрсетілген максималды жабылған ағаш туралы жеке есепті шешу үшін
қарастырып көрейік. Бұл үшін сипатталған алгоритмге сәйкес келесі амалдарды
орындау қажет:
1 қадам. V = {v1}, V0 = {v2, v3, v4, v5, v6, v7} және Emax = Ø
орнату.
2 қадам (бірінші итерация). 2 қадам шартын қанағаттандыратын қабырға
ретінде {v1, v3} қабырғаны таңдау.Орнату: V' = {v1, v3}, V'0 = {v2, v4, v5,
v6, v7} және E' max = {{v1, v3}}.
3 қадам. V'0 = Ø алгоритм аяқталу шарты орындалмайтындықтан, 2 қадам
орындалуына көшу.
2 қадам (екінші итерация). 2 қадам шартын қанағаттандыратын қабырға
ретінде {v3, v5} қабырғасын таңдау. Орнату: V' = {v1, v3, v5}, V'0 = {v2,
v4, v6, v7} және E' max = {{v1, v3}, {v3, v5}}.
3 қадам. V'0 = Ø алгоритмнің аяқталу шарты орындалмайтындықтан, 2
қадам орындалуына көшу.
2 қадам (үшінші итерация). 2 қадам шартын қанағаттандыратын қабырға
ретінде {v5, v2} қабырғасын таңдау. Орнату: V' = {v1, v2, v3, v5}, V'0 =
{v4, v6, v7} және E' max = {{v1, v3}, {v3, v5}, {v5, v2}}.
3 қадам. V'0 = Ø алгоритмнің аяқталу шарты орындалмайтындықтан, 2
қадам орындалуына көшу.
2 қадам (төртінші итерация). 2 қадам шартын қанағаттандыратын қабырға
ретінде {v5, v7} қабырғасын таңдау. Орнату: V' = {v1, v2, v3, v5, v7}, V'0
= {v4, v6} және E' max = {{v1, v3}, {v3, v5}, {v5, v2}, {v5, v7}}.
3 қадам. V'0 = Ø алгоритмнің аяқталу шарты орындалмайтындықтан, 2
қадам орындалуына көшу.
2 қадам (бесінші итерация). 2 қадам шартын қанағаттандыратын қабырға
ретінде {v7, v6} қабырғасын таңдау. Орнату: V' = {v1, v2, v3, v5, v6, v7},
V'0 = {v4} және E' max = {{v1, v3}, {v3, v5}, {v5, v2}, {v5, v7}, {v7,
v6}}.
3 қадам. V'0 = Ø алгоритмнің аяқталу шарты орындалмайтындықтан, 2
қадам орындалуына көшу.
2 қадам (алтыншы итерация). Берілген итерацияда 2 қадам шартын
қанағаттандыратын екі қабырға бар: {v1, v4} және {v6, v4}. Ізделінген
қабырға ретінде олардың ішінен біріншісін таңдаймыз: {v1, v4}. Орнату
керек: V' = {v1, v2, v3, v4, v5, v6, v7}, V'0 = Ø және E' max = {{v1, v3},
{v3, v5}, {v2, v5}, {v5, v7}, {v6, v7}, {v1, v4}}.
3 қадам. V'0 = Ø алгоритмнің аяқталу шарты орындалатындықтан, онда
алгортимнің толық орындалуы осымен аяқталады. Нәтиже ретінде максималды
жабылған ағаш қабылданады: E' max = {{v1, v3}, {v3, v5}, {v2, v5}, {v5,
v7}, {v6, v7}, {v1, v4}}.
Алынған нәтижені берілген жеке есептің MS Excel программасының
көмегімен шешілу қорытындысымен салыстырсақ, олардың дәл келуін аламыз. Бұл
сәйкес келетін нәтижелердің дұрыстығына куә болады.
Қарастырылған сараң алгоритм графтағы минималды жабылған ағашты жабу
үшін жеңіл модификацияланған болуы мүмкін. Сонымен қатар, модификация 2
қадам амалының орындалуына ғана қатысты. Яғни, максималды салмақты қабырға
таңдаудың орнына минималды салмақты қабырға таңдау керек, ал міндетті шарт
өзгеріссіз қалады. Максималды жабылған ағашқа кіретін E max қабырға
жиынына қатысты, онда оның орнына минималды жабылған ағашқа кіретін,
барабар қасиетті иеленетін Emin қабырға жиынын қарастыру енгізіледі.
Негізгі графы 1- сур. көрсетілген минималды жабылған ағаш туралы жеке
есептің шешімі үшін сараң алгоритмің қолдануын көрсетеміз. Ол үшін
сипатталған алгоритмге сәйкес келесі амалдарды орындау қажет:
1 қадам. V = {v1}, V0 = {v2, v3, v4, v5, v6, v7} және Emin = Ø орнату.
2 қадам (бірінші итерация). 2 қадам шартын қанағаттандыратын қабырға
ретінде {v1, ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
Ұқсас жұмыстар
Пәндер
- Іс жүргізу
- Автоматтандыру, Техника
- Алғашқы әскери дайындық
- Астрономия
- Ауыл шаруашылығы
- Банк ісі
- Бизнесті бағалау
- Биология
- Бухгалтерлік іс
- Валеология
- Ветеринария
- География
- Геология, Геофизика, Геодезия
- Дін
- Ет, сүт, шарап өнімдері
- Жалпы тарих
- Жер кадастрі, Жылжымайтын мүлік
- Журналистика
- Информатика
- Кеден ісі
- Маркетинг
- Математика, Геометрия
- Медицина
- Мемлекеттік басқару
- Менеджмент
- Мұнай, Газ
- Мұрағат ісі
- Мәдениеттану
- ОБЖ (Основы безопасности жизнедеятельности)
- Педагогика
- Полиграфия
- Психология
- Салық
- Саясаттану
- Сақтандыру
- Сертификаттау, стандарттау
- Социология, Демография
- Спорт
- Статистика
- Тілтану, Филология
- Тарихи тұлғалар
- Тау-кен ісі
- Транспорт
- Туризм
- Физика
- Философия
- Халықаралық қатынастар
- Химия
- Экология, Қоршаған ортаны қорғау
- Экономика
- Экономикалық география
- Электротехника
- Қазақстан тарихы
- Қаржы
- Құрылыс
- Құқық, Криминалистика
- Әдебиет
- Өнер, музыка
- Өнеркәсіп, Өндіріс
Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор #1 болып табылады.
Ақпарат
Қосымша
Email: info@stud.kz