Графтардағы тиімділеу есептерін шешу әдістері

Кіріспе 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. Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. – М.: Высшая школа, 1976. -392 с.
2. Таха Х. Введение в исследование операции. Том 1, 2..- М.: Мир, 1985.-480 с., - 495 с.
3. Форд Л., Фалкерсон Д. Потоки в сетях. - М.: Мир, 1966 - 276 с.
4. Ху Т. Целочисленное программирование и потоки в сетях.- М.: Мир, 1974. - 520 с.
        
        МАЗМҰНЫ
| |Кіріспе |4 |
|1 ... ... ... шешу әдістері |5 ... ... ... ... ... |5 |
| |1.1.1. ... ... ... ... қойылымы |5 |
| |1.1.2. Графтағы оптимизациялық есептерді шешудің негізгі әдістері|6 |
|1.2|Графтағы минималды жабушы ағаш ... есеп |7 |
| |1.2.1. ... ... ... |7 |
| |1.2.4. ... ... ... максималды және минималды |10 |
| ... ағаш ... ... шешу | ... минималды жол туралы есеп |15 |
| |1.3.1. ... ... ... |15 ... ... максималды жолды табу есебі |16 |
| |1.4.1. ...... ... ... ... табу |17 |
| ... ... қойылымы. | |
| |1.4.2. ... ... ... |19 ... ... ағын туралы есеп |20 |
| |1.5.1. ... ... ... |20 |
| ... | |
| ... ... тізімі |23 ... ... ... ... ... тиімділеу
есептері арқылы сипатталады. Бұнымен қатар, графтар теориясындағы есептер
оптимизациялау есептерімен ... ... ... ... ... ... және оны шешу ... білу қажеттілігі
туады. Бұл есептерді шешкенде алгоритмдік ойлау ... ... ... ... дегеніміз, қазіргі білім ... ... ... ... ... ... ... айналғандағы қарастырылған.
Бұлар:
- оптималды жабатын ағашты табу есебі
- графтағы ең қысқа жолды табу есебі
- желілік графтағы кризистік жолды табу ... ... ... ... табу ... оптимизациялау есептерінің бизнес – қосымшаларына:
- телекоммуникациялық провайдердің кабельдік желісін төсеу;
- қаладағы максималды адамдарды таситын транспорттық жүйені құру;
- автомобиль магистральдарындағы ... ... ... ... ... тиімділеу әдістері
1. Графтағы оптимизациялық есептердің жалпы сипаттамасы.
Графтағы оптимизациялық есептер класына кейбір мақсаттық функциялардың
оптимальдық мәнімен қамтамасыздайтын, ... ... ... ... ... ... ... жатады. Сонымен қатар, мақсаттық
функция түрі және шектеулер ... ... және ... ... ... ... ... жағдайда графтағы
оптимизациялық есеп математикалық программалау есебі түрінде бастапқы ... ... ... ... ... шешілуі оның математикалық қойылымы
үшін сәтті модель таңдауымен ... ... ... ... ... ... ... оптимизациялық есептер өзінің алғашқы қойылымында
бағдарланған ... ... ... жалпы ұғымын қолданады.
Графтардың ... ... ... графтағы оптимизациялық есептер түрінде
қолданылатын арнайы обьектілер жолдар, ... және ... ... ... ... ... ... осындай обьектіге сәйкесінше
нақтылы граф негізінде есептелетін, оптимизациялау ... ... ... ... ... функцияның кейбір сандық
мәндері қойылады. Осы обьектілер үшін міндетті шарт кейбір конструкциялы
әдістердің ... бар ... ... ... ... сәйкес
оптимизациялау есебі есептік көзқараспен шешілмеуі мүмкін.
Сонымен, ... ... ... есеп ... ... ... минималды мәні сәйкес ... ... ... ... ... қалыптасады.
Жалпы графтағы оптимизациялық есептің математикалық қойылымы мынадай
түрде қалыптасуы мүмкін:
немесе ƒ (x) → , ... х ... ... ... ... кейбір арнайы обьектілерін
білдіреді, ал ... ... ∆β ... ... ... ... арнайы обьектілері бар. Сонымен қатар, мақсаттық
функция немесе шектеулер ... ... ... ... ... ... ... негізгі графтар ақырлы
болып табылады, осы сияқты графтағы ... ... ... ... ... ... болып табылады.
Графтағы оптимизациялық есептердің математикалық ... ... ... ... ... ... жеке граф үшін
сәйкес оптимизация есебі осы не ... ... ... үшін бос болуы
мүмкін екенін ескеру қажет. Мысалы, оптимальды жабылған ағашты іздеу немесе
байланбаған граф жолы үшін өз ... ... Осы ... ... ... ... ... сәйкес оптимизация есебінің
шешімі бар болатынын қанағаттандыратын графтың қосымша қасиетін көрсету
қажет.
1.1.2. ... ... ... ... ... ... оптимизациялық есептердің жалпы математикалық қойылымы оның
шешімінің мүмкін әдістері туралы ешқандай ... ... де, ... шешілуінің барлық әдістерін шартты түрде екі ... ... ... ... ... ... ... бүтінсандық
математикалық модель немесе булевті программалау түрінде ... ... ... оларды шешу тәсілін таңдау толығымен есептің қойылымына сәйкес
математикалық қасиеттермен анықталады. Графтағы оптимизациялық практикалық
есептерін MS Excel ... ... шешу ... ... ... булевті программалау түрінде қалыптасу ... ... ... ... ... ... қандай да бір
обьектілерінің спецификалық ... және ... ... ... ... ... арнайы алгоритмдерді қолданып
шешілуі мүмкін. Бұл байланыста графтағы оптимизациялық есептер комбинаторлы
оптимизациялау есептерімен ... ... ... ... дәл шешімін табу үшін шекара және бұтақ әдісі және динамикалық
программалау әдісі түріндегі ... ... ... ... көзқараспен арнайы алгоритмдер эффектілі болып табылады. Графтағы
оптимизациялық типтік есептердің дәл осындай, шешілу алгоритмдері ... ... және II ... VBA программасына салынған.
MS Excel программасы бүтінсандық және булевті программалау есебінің
нақты шешімін ... ... ... оның ... ... ... ... мүмкіндік туады. Алынатын шешімнің нақты
бағасы үшін бөлек практикалық есептердің әртүрлі ... ... ... ... ... Осы ... бұл бөлімде графтағы
максималды және минималды ағашпен жабу ... және ең ... жол ... ... ... ... Графтағы минималды жабылған ағаш туралы есеп.
Бұл бөлімде булевті ... ... ... ... және ... формальды жазылуы үшін қолданылатын ... ... ағаш ... ... модификациясы қарастырылады.
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) ... құны ... ... ... ... Ek C E кез – ... ... жиынының құны осы жиынға кіретін
қабырғалар салмағының қосындысына тең. G графында ... ... және ... ... ... ... ... қажет етіледі.
Булевті программалау моделі түріндегі графтағы минималды жабылған ағаш
туралы есебінің ... ... ... үшін ... ... ... ... қолдану қажет:
1. Бастапқы графтың әр төбесі минималды жабылған ағашқа кіретін кемінде
бір қабырғаға ие ... ... ... ... ізделетін ағашта мұндай
төбелер бөлек алынады, демек, ағаш жабылған болмайды.
2. Минималды жабылған ағаштың ... ... саны ... түрде n – 1-
ге тең, мұндағы n – ... граф ... ... ... Шынында да,
егер кейбір ағаш қабырғалары n – 1-ден кем болса, онда ол ... егер ағаш ... n – 1-ден ... ... онда ол ... m ... ... енгіземіз. Ыңғайлы болу үшін xij
арқылы белгіленеді және келесі ... ... Егер ... жұбына сәйкес келетін ekЄ E ... ... ... ... ... онда ... xij = 1, әйтпесе xij = 0. ... {vi,vj} ... ... ... ағашқа енбесе. Онда жалпы
жағдайда графтағы минималды жабылған ағаш туралы есептің ... ... ... қалыптасуы мүмкін:
(1.2.1)
Мұндағы ∆β жіберілетін альтернатива жиыны келесі теңсіздік және теңдік
түріндегі шектеулер жүйесімен қалыптасады:
(1.2.2)
(1.2.3) ... ... ... ... анықталмаған немесе 0-ге тең xij
айнымалылары (1.2.1) – (1.2.6) ... ... ... ... ескерейік. (1.2.2) – (1.2.4) алғашқы үш шектеуі
алдын – ала белгіленген ... ... ... талап етеді,
яғни ізделетін жабылған ағашта бөлек алынып тасталатын төбелері ... (1.2.4) ... ... ... – ала ... ... орындалуын талап етеді, яғни ізделетін жабылған ағаштың n – ... ... ... (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 арқылы белгілейміз.
Сараң алгоритм итеративті мінезге ие және ... ... ... ... ... ... және байланыспаған жиындардың алдын – ала
анықтамасы. ... ... ... орындамас бұрын,
қарастыруға енгізілген төбелер жиынының келесі жолмен анықтаймыз: V =
{v1} және V0 = V / {v1}. ... V1 ... ... ... ... Алгоритмнің негізгі итерациясы. V және V0 ... ... ... ... жиындарының ішінен cij = h (e ... ... ... ... ... ... ек Є Е қабырғасы
{vi, vj} төбелер жұбына сәйкес келеді. Максималды салмақты қабырғаны
тапқаннан кейін E max = E max U ek тең ... Emax ... ... ... vj ... v0 жиынынан алынады және V0 = V0 / {vj} және
V' = V U {vj}тең болатын V ... ... ... ... ... тексеру. V'0 = Ø шартының орындалуын тексеру.
Егер бұл шарт орындалса, онда негізгі графтың төбелерінің ... ... ... ... ағашпен байланысты, және алгоритмнің орындалуы
осымен аяқталады. Ал егер бұл шарт орындалмаса, онда E max = E' ... = V'0, V = V' ... ... және 2 қадам орындалуына көшу керек.
Қарастырылған сараң алгоритм схемасы UML тілінің ... ... ... ... мүмкін. (1-сур.)
[V0= Ø] V0 Ø
1-сур. Максималды жабылған ағашты табу үшін сараң алгоритм ... ... ... ... 1 – сур. ... графы
көрсетілген максималды жабылған ағаш туралы жеке ... шешу ... ... Бұл үшін ... ... сәйкес келесі амалдарды
орындау қажет:
1 қадам. V = {v1}, V0 = {v2, v3, v4, v5, v6, v7} және Emax = ... ... ... итерация). 2 қадам шартын қанағаттандыратын қабырға
ретінде {v1, v3} қабырғаны таңдау.Орнату: V' = {v1, v3}, V'0 = {v2, v4, ... v7} және E' max = {{v1, ... ... V'0 = Ø ... ... ... орындалмайтындықтан, 2 қадам
орындалуына көшу.
2 қадам (екінші ... 2 ... ... ... қабырға
ретінде {v3, v5} қабырғасын таңдау. Орнату: V' = {v1, v3, v5}, V'0 = ... v6, v7} және E' max = {{v1, v3}, {v3, ... ... V'0 = Ø алгоритмнің аяқталу шарты орындалмайтындықтан, 2
қадам орындалуына көшу.
2 қадам (үшінші итерация). 2 қадам ... ... ... {v5, v2} қабырғасын таңдау. Орнату: V' = {v1, v2, v3, v5}, V'0 =
{v4, v6, v7} және E' max = {{v1, v3}, {v3, v5}, {v5, ... ... 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, ... ... 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}, ... ... V'0 = Ø ... ... ... ... 2
қадам орындалуына көшу.
2 қадам (алтыншы итерация). Берілген итерацияда 2 қадам шартын
қанағаттандыратын екі ... бар: {v1, v4} және {v6, v4}. ... ... ... ... ... таңдаймыз: {v1, v4}. Орнату
керек: V' = {v1, v2, v3, v4, v5, v6, v7}, V'0 = Ø және E' max = {{v1, ... v5}, {v2, v5}, {v5, v7}, {v6, v7}, {v1, ... ... V'0 = Ø ... ... шарты орындалатындықтан, онда
алгортимнің толық орындалуы осымен аяқталады. Нәтиже ретінде ... ағаш ... E' max = {{v1, v3}, {v3, v5}, {v2, v5}, ... {v6, v7}, {v1, ... ... ... жеке ... MS Excel программасының
көмегімен шешілу қорытындысымен салыстырсақ, олардың дәл ... ... ... ... нәтижелердің дұрыстығына куә болады.
Қарастырылған сараң алгоритм графтағы минималды жабылған ... ... ... модификацияланған болуы мүмкін. Сонымен қатар, модификация 2
қадам амалының орындалуына ғана қатысты. Яғни, максималды ... ... ... ... ... ... таңдау керек, ал міндетті шарт
өзгеріссіз қалады. Максималды жабылған ағашқа кіретін E max ... ... онда оның ... ... ... ағашқа кіретін,
барабар қасиетті иеленетін Emin қабырға ... ... ... графы 1- сур. көрсетілген минималды жабылған ағаш туралы жеке
есептің шешімі үшін сараң алгоритмің ... ... Ол ... ... сәйкес келесі амалдарды орындау қажет:
1 қадам. V = {v1}, V0 = {v2, v3, v4, v5, v6, v7} және Emin = Ø ... ... ... ... 2 ... ... қанағаттандыратын қабырға
ретінде {v1, v2} қабырғаны таңдау.Орнату: V' = {v1, v2}, V'0 = {v3, v4, ... v7} және E' min = {{v1, ... ... V'0 = Ø ... ... ... орындалмайтындықтан, 2 қадам
орындалуына көшу.
2 қадам (екінші итерация). 2 қадам шартын қанағаттандыратын қабырға
ретінде {v2, v3} ... ... ... V' = {v1, v2, v3}, V'0 = ... v6, v7} және E' min = {{v1, v2}, {v2, ... ... V'0 = Ø алгоритмнің аяқталу шарты ... ... ... ... ... ... ... 2 қадам шартын қанағаттандыратын қабырға
ретінде {v3, v4} қабырғасын таңдау. Орнату: V' = {v1, v2, v3, v4}, V'0 ... v6, v7} және E' min = {{v1, v2}, {v2, v3}, {v3, ... ... V'0 = Ø ... ... шарты орындалмайтындықтан, 2
қадам орындалуына көшу.
2 ... ... ... 2 қадам шартын қанағаттандыратын қабырға
ретінде {v3, v6} қабырғасын таңдау. Орнату: V' = {v1, v2, v3, v4, v6}, ... {v5, v7} және E' min = {{v1, v2}, {v2, v3}, {v3, v4}, {v3, ... ... V'0 = Ø ... ... ... орындалмайтындықтан, 2
қадам орындалуына көшу.
2 қадам (бесінші итерация). 2 ... ... ... ... {v6, v5} қабырғасын таңдау. Орнату: V' = {v1, v2, v3, v4, v5, v6},
V'0 = {v7} және E' min = {{v1, v2}, {v2, v3}, {v3, v4}, {v3, v6}, ... ... V'0 = Ø ... ... ... орындалмайтындықтан, 2
қадам орындалуына көшу.
2 қадам (алтыншы итерация). 2 қадам шартын қанағаттандыратын қабырға
ретінде {v5, v7} ... ... ... керек: V' = {v1, v2, v3, ... v6, v7}, V'0 = Ø және E' min = {{v1, v2}, {v2, v3}, {v3, v4}, {v3, ... v5}, {v5, ... қадам. V'0 = Ø алгоритмнің аяқталу шарты орындалатындықтан, онда
алгортимнің толық ... ... ... ... ... ... ағаш қабылданады: E' min = {{v1, v2}, {v2, v3}, {v3, v4}, ... {v6, v5}, {v5, ... ... берілген жеке есептің MS Excel программасының
көмегімен шешілу қорытындысымен салыстырсақ, олардың дәл ... ... ... ... ... дұрыстығына куә болады.
1.3. Графтағы минималды жол туралы есеп.
1.3.1. Есептің математикалық қойылымы.
G = (V, E, h) ... ... ... ... V={v1, v2, ... vn} – ... ақырлы жиыны, E = {e1, e2, … , em} – доғалардың ... h: E → Z + – ... ... ... ... математикалық
қойылымы үшін салмақты функциялар доғасының жеке мәндерін cij = h (ek)
арқылы ... ... ... ek Є E ... (vi,vj) ... ... ... келеді. Қарастырылатын есептің ... ... cij = h ((vi, vj)) ... ... ұзындығы сияқты
түсіндірілуі мүмкін, i – қаласынан j – қаласына көшу құны немесе шығыны.
Графтағы кез – ... ... ... осы маршрутқа кіретін доғалар
салмағының қосындысына тең. Қосымша графта екі төбе белгіленеді: бастапқы
төбе vs және соңғы төбе vt. G ... ... ... болсын деп ойлайық,
яғни vt төбесі vs ішінен потенциалды жеткілікті, vs бастапқы ... ... ... ... ... ... ... қажет.
xij келесі булевті айнымалыларын қарастыруға енгіземіз. Бұлар келесі
түрде түсіндіріледі. Егер (vi,vj) доғасы ізделетін ... ... ... онда ... xij = 1, ... xij = 0. Яғни, егер
(vi,vj) ... ... ... ... Онда ... ... ... туралы немесе графтағы бағытталған жол туралы есептің математикалық
қойылымы ... ... ... ... ∆β ... альтернатива жиыны келесі теңсіздік түріндегі
шектеулер жүйесімен қалыптасады:
(1.3.2)
(1.3.3)
(1.3.4)
(1.3.5)
Сонымен қатар бірінші (1.3.2) шектеуі келесі шарт ... ...... жол vs ... ... ... (1.3.3) шектеуі келесі
шарттың орындалуын талап етеді – ізделетін жол vt ... ... ... ... ... ... жолдың байламдылығына кепілдік береді,
яғни ізделетін жол графтың аралық төбелері арқылы өтуі қажет. (1.3.2) ... ... ... саны n – ге тең. (1.3.5) ... шектуі
айнымалылардың тек булевті мәндерді қабылдауын талап етеді.
1.4. Бағытталған графта максималды ... табу ... ... максималды жолды табу есебі ... ... ... жол ... ... ... ... да, бизнес – үрдістің
орындалуының ... ... табу ... ... ... контексінде өзіндік
мәні бар. Осы ... оның ... ... ... түріндегі
оптимизация есебіне сәйкес келетін шарттардың формальды жазылуы үшін қажет
мазмұндық қойылымы қарастырылады.
1.4.1. Бизнес – үрдістің орындалуының ... ... табу ... ... есеп әр ... бизнес – үрдістердің модельдеу кезінде ең
негізгілерінің бірі болып табылады, тағы ... ... ... ... ... ... және жоспарлауда. Бизнес –
үрдістің ... ... ... табу ... мәні ... ... ... мысалы, қаланың транспорттық желісі және үй
құрылысы, механизм және машинаның жасалуы және ... ... ету және ... ... өңдеу, логистикада және саудада
тапсырыстарды өңдеу, және де институтта ... және кофе ... ... ... әр түрлі операциялар және жұмыстардың ... ... ... Бұл ... ... бір ... ... орындалуы мүмкін, басқалары – тек тізбектеліп, егер басқа операция
орындалғаннан кейін ғана бұл операцияның басталуы мүмкін ... ... үй ... ... ... ... қатар үйдің
жанындағы алаңды көгалдандыру жұмыстарын ... ... ... ... өңдеуде бір модульге және басқа модульдерді тестілеу үшін
программа жазылуын бір ... ... ... ... ...... операцияларының тізбектеліп орындалуы
жеке жұмыстардың басталу және аяқталу уақыттарының келісілуін талап етеді.
Мысалы, үй құрылысында үй ішіндегі ... ... тек үй ... ... тұрғызылу бойынша жұмыстары аяқталғаннан кейін ғана
басталуы мүмкін. Программалық қамтамасыз етуді өңдеуде жеке ... ... ... тек оған ... ... спецификациядан кейін ғана басталу
мүмкін, мысалы, қолдану нұсқалары түрінде. Кофеқайнатқыш көмегімен ... ... ... кофеқайнатқышты тоққа қоспай тұрып, оның ішіне
су ... ал ... ... кофе салу ... жағдайда, жеке операциялар немесе жұмыстардың орындалуының логикалық
өзара байланысын және тізбектелуді ... ...... ... кейбір
соңғы бағытталған граф түрінде көрсетілуі мүмкін. Сонымен қатар, жеке
операциялар осы ... ... ... де және ... ... ... ... Жұмыс интерпретациясының екінші жағдайы бағытталған граф
доғалары түріндегі бизнес – үрдісінің орындалуының жалпы уақытын есептеуде
ыңғайлы ... ол ...... ... жолды табудың
мазмұндық қойылымын қарастыруда дәстүрлі түрде ... ...... модельдеу үшін алынатын ақпарат операциялар
орындалуының бағытталған графы болып табылады, әр доғасы осы ... ... ... ... жеке операциясы түрінде болады, ал төбесі – осы не
басқа операциялардың ... ... ... ... ... ... ... жеке операциялардың орындалуының уақыт ұзақтығы
сәйкес ... доға ... ... ... ... – үрдістің
орындалуының жалпы логикасынан ... ... шарт ...... ... ... оның орындалуының басталуын көрсететін
жалғыз бастапқы оқиғасы болуы керек,
және оның орындалуының аяқталу кезін белгілейтін жалғыз ... ... ... Бизнес – үрдістің бағытталған графына қолданылатын бұл шарт доғалары
шығатын берілген графтың тек бір ғана төбесі және доғалары ... ... ... ... екенін білдіреді.
Егер кейбір бизнес – ... ... ... ... онда оның ... ... жеке ... орындалу уақытының
интервалдарының алгебралық қосындысына тең. Ал егер ...... ... ... онда ...... жалпы ұзақтығы қатар
орындалатын операциялардың максималды уақыт интервалына тең. ... ... ... ... желілік граф моделінде көрсетілген бизнес ... ... ... осы ... ... төбесі мен соңғы төбесін
байланыстыратын ... жол ... тең. ... жол арнайы атау алды
– желілік ... ... ... ... ... ... табу өзінің орындалу уақытында
кризисті болатын бизнес – ... ... ... ... ... да, ... жолдағы операциялардың орындалу уақытының
өсуі бизнес – үрдістің орындалуының жалпы уақытының ... ... ...... ... ең ... сәйкес келетін желілік графтың
кризистік жолына кіретін операцияларды ... ... ... бағытталған. Басқа жағынан, бизнес – жүйенің ішкі
резервтері арқылы ... ... ... ... ... ... бірі болып табылатын, барлық операциялар
жиынтығының орындалуының жалпы уақытын қысқартуы мүмкін.
Сонымен, кризистік жол ... ...... ... ... ... бағаланады, ал бизнес – үрдістің
желілік графының құрылу есебі және осы желілік графта кризистік ... ...... модельдеуінің маңызды элементі болып табылады.
1.4.2. Есептің математикалық қойылымы.
G = (V, E, h) ... ... ... ... V={v1, v2, … ...... ақырлы жиыны, E = {e1, e2, … , em} – доғалардың ... h: E → Z+ – ... ... ... ... математикалық
қойылымы үшін салмақты функциялар доғасының жеке ... cij = h ... ... ... ... ek Є E ... (vi,vj) төбелерінің
реттелген жұбына сәйкес келеді. ... ... ... ... cij = h ((vi, vj)) ... ... ... сияқты
түсіндірілуі мүмкін, i – қаласынан j – қаласына көшу құны немесе шығыны.
Желілік графта кризистік ... табу ... ... (vi,vj) ... бизнес – үрдістің жеке операциясы ретінде, ал cij мәні – ... ... ... ... ... ретінде түсіндіріледі.
Қосымша графта екі төбе белгіленеді: бастапқы төбе vs және ... ... ... кез – келген маршрут ұзындығы осы маршрутқа кіретін доғалар
салмағының қосындысына тең. G ... ... ... болсын деп ойлайық,
яғни vt төбесі vs ... ... ... және цикл ... ... ... vt ... төбелеріне максималды ұзындықты маршрутты
анықтау қажет.
Бағытталған графтағы минималды жол ... ... xij ... қарастыруға енгіземіз. Бұлар келесі түрде түсіндіріледі. Егер
(vi,vj) доғасы ... ... ... маршрутына енсе, онда айнымалы
xij = 1, әйтпесе xij = 0. ... егер (vi,vj) ... ... ... Онда ... жағдайда максималды маршрут туралы немесе графтағы
бағдарланған жол ... ... ... ... ... ... мүмкін:
(1.4.1)
Мұндағы ∆β жіберілетін альтернатива жиыны ... ... жол ... ... математикалық моделіндегі шектеулер
жүйесіндегідей қалыптасады (1.3.2) – (1.3.5). Бұл 1.3.1. ... ... ... ... ... графта
максималды маршрутты табу есебінің математикалық қойылымы туралы сөз
болғанда, (1.4.1), (1.3.2) – (1.3.5) ... ... ... максималды ағын туралы есеп.
1.5.1. Есептің математикалық қойылымы.
G = (V, E, h) ... ... ... ... V={v1, v2, … ...... ақырлы жиыны, E = {e1, e2, … , em} – ... ... h: E → Z+ – ... ... қабілеттігі ретінде түсіндірілетін
доғалардың салмақты функциясы. Қосымша графта екі төбе ... төбе vs және ... төбе vt. G ... ... ... ... ... яғни vt төбесі vs ішінен потенциалды жеткілікті және цикл жоқ, vs
бастапқы төбелерінен vt соңғы төбелеріне баратын ... ... ... Є E ... бойынша өтетін, ағын көлемі ретінде түсіндірілетін
– xij келесі теріс емес бүтінсанды ... ... ... ... ... ағын ... ... математикалық қойылымы жалпы
жағдайда келесі түрдегідей қалыптасуы мүмкін:
(1.5.1)
Мұндағы ∆β жіберілетін альтернатива ... ... ... ... жүйесімен қалыптасады:
(1.5.2)
(1.5.3)
(1.5.4)
(1.5.5)
Сонымен қатар бірінші (1.5.2) шектеуі келесі шарт орындалуын талап
етеді – vs төбесінен ... ағын ... vt ... ... ағын
көлеміне тең болуы қажет. Шектеулердің екінші тобы (1.5.3) ... ... ... ...... ... ... төбесіне кіретін кез –
келген бөлшектік ағын осы төбеден шығатын ағынға тең болуы ... ... (1.5.3) ... ... саны n – 1-ге тең. ... үшінші
тобы (1.5.4) келесі шарттың орындалуын талап ... (vi,vj) Є E ... ... ағын көлемі cij доғасының өткізу қабілеттілігін жоғарылатпау
қажет және теріс емес болуы қажет.
(1.5.5) соңғы ... тек ... емес ... мәндерін
Қорытынды
Графтар теориясына негіз болған есептердің бірі Кенигсберг көпірлері
туралы есебі болған. Бұл есепті алғаш рет Л.Эйлер графтар ... ... ... ... 100 жыл ... соң ... Англияда жаратылыстану
ғылымының барынша әр түрлі формадағы саласында графтар теориясы пайдаланыла
бастады. Электр тізбегі мен ... ... ... структурасын
зерттеуге, сондай-ақ ойындар теориясы мен ... ... ... ... ... математикадағы логикалық есептерді шешуде
кеңінен қолданылады. Логикалық есептер деп ... ... ... ... ... талдау жасауды қажет ететін есептерді айтамыз.
Математикалық логиканы жетік түсінбейінше, оны меңгеру өте ... ... ... ... мен ... қарыштап дамыған сайын ол ... ... ең ірі ... ... ... ... ... математикадағы логикалық есептерді шешуге
болады, сондықтан әсіресе граф көптеген  логикалық есептерді оңай жолдармен
шығаруға, ... ... ... олардың шығару жолдарын  адам есіне лезде
сақтап қалу үшін де ... ... ... ... ... ... әсер етеді және  арттырады. Граф ... ... ... ... ... ... ... ортаның әртүрлі
объектілері  арасындағы байланыстар жүйесі зерттеледі. Объектілер ... ... ... ... ... ал төбелер арасындағы байланыстар
доғалар деп аталып, сәйкес ... ... ... түзулермен 
белгіленеді.
Қолданылған әдебиеттер тізімі
1. Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. – М.: Высшая
школа, 1976. -392 с.
2. Таха Х. ... в ... ... Том 1, 2..- М.: Мир, ... с., - 495 с.
3. Форд Л., Фалкерсон Д. Потоки в сетях. - М.: Мир, 1966 - 276 ... Ху Т. ... ... и ... в ... М.: Мир, ... 520 с.
-----------------------
V: = {v1}
V0: = V\ {v1}
Emax: = Ø
Cij максималды салмақты қабырға табу
V: = V U ... = V0\ ... = EmaxU {vi, vj}

Пән: Математика, Геометрия
Жұмыс түрі: Курстық жұмыс
Көлемі: 15 бет
Бұл жұмыстың бағасы: 700 теңге









Ұқсас жұмыстар
Тақырыб Бет саны
Граф тиімділік есептерін шешу әдістерінің алгоритмдері мен программалары42 бет
"Кәсіпорынның өндірістік қорлары."5 бет
«Қоқыс жағатын және жылу беретін зауыт»13 бет
Жаңажол мұнай газ өңдеу кешенінің №4 зауытының басты компрессорлық станциясының автоматтандырылуын жобалау21 бет
Капитал құрылымның теориясы7 бет
Компанияны басқарудағы қаржылық есептілік9 бет
Салық органдарының қызметін ұйымдастырудың құқықтық негіздері63 бет
Сегменттеу – банктік маркетинг тиімділігін арттыру ретінде59 бет
Сығымдағы машинамен сығу процесін жобалау41 бет
Қазақстан Республикасының Азия аймағындағы сыртқы саясаты6 бет


+ тегін презентациялар
Пәндер
Көмек / Помощь
Арайлым
Біз міндетті түрде жауап береміз!
Мы обязательно ответим!
Жіберу / Отправить


Зарабатывайте вместе с нами

Рахмет!
Хабарлама жіберілді. / Сообщение отправлено.

Сіз үшін аптасына 5 күн жұмыс істейміз.
Жұмыс уақыты 09:00 - 18:00

Мы работаем для Вас 5 дней в неделю.
Время работы 09:00 - 18:00

Email: info@stud.kz

Phone: 777 614 50 20
Жабу / Закрыть

Көмек / Помощь