Мазмұны кіріспе графтардағы тиімділеу есептерін шешу әдістері

1.1. Графтағы тиімділеу есептердің жалпы сипаттамасы..................................7

1.2. Графтағы минималды жабушы ағаш туралы есеп.......................................9

1.3. Графтағы минималды жол туралы есеп.......................................................17

1.4. Бағытталған графтағы максималды жолды табу есебі...............................18

1.5. Желідегі максималды ағын туралы есеп......................................................23

• 
  оптималды жабатын ағашты табу есебі
  
• 
  графтағы ең қысқа жолды табу есебі
  
• 
  желілік графтағы кризистік жолды табу есебі
  
• 
  графтағы максималды ағынды табу есебі
  

• 
  телекоммуникациялық провайдердің кабельдік желісін төсеу;
  
• 
  қаладағы максималды адамдарды таситын транспорттық жүйені құру;
  
• 
  автомобиль магистральдарындағы транспорттық ағымдарды реттеу.
  

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

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

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

Жалпы графтағы оптимизациялық есептің математикалық қойылымы мынадай түрде қалыптасуы мүмкін:

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

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

1. Танымал графтағы оптимизациялық есептердің көбісі бүтінсандық математикалық модель немесе булевті программалау түрінде қалыптасуы мүмкін. Бұл жағдайда оларды шешу тәсілін таңдау толығымен есептің қойылымына сәйкес математикалық қасиеттермен анықталады. Графтағы оптимизациялық практикалық есептерін MS Excel программасының көмегімен шешу мүмкіндігі есептің бүтінсандық немесе булевті программалау түрінде қалыптасу мүмкіндігіне тікелей байланысты.

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

MS Excel программасы бүтінсандық және булевті программалау есебінің нақты шешімін табуға мүмкіндік беретіндіктен, оның көмегімен графтағы оптимизациялық есепті шешуге мүмкіндік туады. Алынатын шешімнің нақты бағасы үшін бөлек практикалық есептердің әртүрлі тәсілдермен алынған оптимальды шешімдерін салыстыру керек. Осы мақсатпен бұл бөлімде графтағы максималды және минималды ағашпен жабу есебінің және ең қысқа жол туралы есептің шешілу тәсілдері сипатталған.

1.2. Графтағы минималды жабылған ағаш туралы есеп.

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

G= (V, E, h) бағдарланбаған тізбекті графты қарастырайық, мұндағы V={v₁,v₂,…,v_n } – төбелердің шекті жиыны, E= {e₁,e₂,…,e_n } – қабырғалардың шекті жиыны, h: E→ Z ₊ – қабырғалардың салмақтық функциясы. Есептің математикалық қойылымы үшін қабырғалардың салмақтық функциясын c_ij=h(e _k) арқылы бөлек мәнін белгілеу ыңғайлы, мұндағы e _k Є E қабырғасы {v_i, v_j } V төбелер жұбына сәйкес келеді. Қарастырылған есептің мазмұндық қойылымымен келісімді c_{i j}= h ({v_i, v_j}) бөлек мәндері шығын ұзындығы немесе негізгі графтың (i, j) учаскісінің құны сияқты түсіндірілуі мүмкін.

G графында E_k C E кез – келген қабырғалар жиынының құны осы жиынға кіретін қабырғалар салмағының қосындысына тең. G графында жабылған ағашты көрсететін және минималды құнды қабырғалар жиынын анықтау қажет етіледі.

Булевті программалау моделі түріндегі графтағы минималды жабылған ағаш туралы есебінің шартының формальды жазылуы үшін графтағы жабылған ағаштың екі шартымен қолдану қажет:

1. 
   Бастапқы графтың әр төбесі минималды жабылған ағашқа кіретін кемінде бір қабырғаға ие болуы қажет. Қарсы жағдайда ізделетін ағашта мұндай төбелер бөлек алынады, демек, ағаш жабылған болмайды.
   
2. 
   Минималды жабылған ағаштың қабырғаларының жалпы саны нақты түрде n – 1-ге тең, мұндағы n – бастапқы граф төбелерінің жалпы саны. Шынында да, егер кейбір ағаш қабырғалары n – 1-ден кем болса, онда ол жабылған болады, егер ағаш қабырғалары n – 1-ден артық болса, онда ол циклды болады.
   

(1.2.3) (1.2.4)

һ қабырғаларының салмақтық функциялары анықталмаған немесе 0-ге тең x_ij айнымалылары (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) минимумды іздеу операциясын максимумды іздеу операциясына ауыстырсақ, онда графтағы максималды жабылған ағаш туралы есебіне сәйкес келетін математикалық қойылымы алынуы мүмкін. Бұл екі оптимизациялау есебінің құрылымы бірдей болғандықтан, оларды шешу әдістері бірге қарастырылады.

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

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

Сараң алгоритмді сипаттау үшін алдын – ала қарастырылуға екі жиын төбесі: V – негізгі граф төбелерінің жабылған ағашпен байланысты жиын және V₀ – негізгі граф төбелерінің жабылған ағашпен байланыспаған жиын. Анықтама бойынша: V U V₀ = V, V ∩ V₀ = Ø

Мұндағы V={v₁, v₂ … v_n } – G = (V, E, h) негізгі граф төбелерінің жиыны.

Максималды жабылған ағашқа кіретін қабырға жиынын E _max арқылы белгілейміз.

Сараң алгоритм итеративті мінезге ие және келесі қадамдардың орындалуын талап етеді:

1. 
   Төбелері байланысқан және байланыспаған жиындардың алдын – ала анықтамасы. Алгоритмнің негізгі итерациясын орындамас бұрын, қарастыруға енгізілген төбелер жиынының келесі жолмен анықтаймыз: V = {v₁} және V₀ = V / {v₁}. Мұндағы V₁ төбесі таңдалады, жалпы жағдайда,
   
2. 
   Алгоритмнің негізгі итерациясы. V және V₀ жиындарының ішінен төбелерді байланыстыратын қабырға жиындарының ішінен c_ij = h (e _k) максималды салмақты қабырғаны таңдау керек, мұндағы е_к Є Е қабырғасы {v_i, v_j} төбелер жұбына сәйкес келеді. Максималды салмақты қабырғаны тапқаннан кейін E _max = E _max U e_k тең болатын E_max жиынына қосылады. Осымен қатар v_j төбесі v₀ жиынынан алынады және V₀ = V₀ / {v_j} және V^' = V U {v_j}тең болатын V жиынына қосылады.
   
3. 
   Алгоритм аяқталу шартын тексеру. V^'₀ = Ø шартының орындалуын тексеру. Егер бұл шарт орындалса, онда негізгі графтың төбелерінің барлығы E _max максмалды жабылған ағашпен байланысты, және алгоритмнің орындалуы осымен аяқталады. Ал егер бұл шарт орындалмаса, онда E _max = E^' _max, V₀ = V^'₀, V = V^' орнату керек және 2 қадам орындалуына көшу керек.
   

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

Қарастырылған сараң алгоритм графтағы минималды жабылған ағашты жабу үшін жеңіл модификацияланған болуы мүмкін. Сонымен қатар, модификация 2 қадам амалының орындалуына ғана қатысты. Яғни, максималды салмақты қабырға таңдаудың орнына минималды салмақты қабырға таңдау керек, ал міндетті шарт өзгеріссіз қалады. Максималды жабылған ағашқа кіретін E _max қабырға жиынына қатысты, онда оның орнына минималды жабылған ағашқа кіретін, барабар қасиетті иеленетін E_min қабырға жиынын қарастыру енгізіледі.

Негізгі графы 1- сур. көрсетілген минималды жабылған ағаш туралы жеке есептің шешімі үшін сараң алгоритмің қолдануын көрсетеміз. Ол үшін сипатталған алгоритмге сәйкес келесі амалдарды орындау қажет:

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

G = (V, E, h) бағытталған графты қарастырайық. Мұндағы V={v₁, v₂, … , v_n} – төбелердің ақырлы жиыны, E = {e₁, e₂, … , e_m} – доғалардың ақырлы жиыны, h: E → Z ₊ – доғалардың салмақты функциясы. Есептің математикалық қойылымы үшін салмақты функциялар доғасының жеке мәндерін c_ij = h (e_k) арқылы белгілеу ыңғайлы, мұндағы e_k Є E доғасы (v_i,v_j) төбелерінің реттелген жұбына сәйкес келеді. Қарастырылатын есептің мазмұндық қойылымымен келісімді c_ij = h ((v_i, v_j)) мәндері участок ұзындығы сияқты түсіндірілуі мүмкін, i – қаласынан j – қаласына көшу құны немесе шығыны.

Графтағы кез – келген маршрут ұзындығы осы маршрутқа кіретін доғалар салмағының қосындысына тең. Қосымша графта екі төбе белгіленеді: бастапқы төбе v_s және соңғы төбе v_t. G негізгі графы байлаулы болсын деп ойлайық, яғни v_t төбесі v_s ішінен потенциалды жеткілікті, v_s бастапқы төбелерінен v_t соңғы төбелеріне минималды ұзындықты маршрутты анықтау қажет.

x_ij келесі булевті айнымалыларын қарастыруға енгіземіз. Бұлар келесі түрде түсіндіріледі. Егер (v_i,v_j) доғасы ізделетін минималды ұзындық маршрутына енсе, онда айнымалы x_ij = 1, әйтпесе x_ij = 0. Яғни, егер (v_i,v_j) доғасы оптимальды маршрутқа енбесе. Онда жалпы жағдайда минималды маршрут туралы немесе графтағы бағытталған жол туралы есептің математикалық қойылымы келесі түрде қалыптасуы мүмкін:

(1.3.1)
Мұндағы ∆_β жіберілетін альтернатива жиыны келесі теңсіздік түріндегі шектеулер жүйесімен қалыптасады:

(1.3.2)

(1.3.3)

(1.3.4)

(1.3.5)

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

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

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

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

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

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

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

және оның орындалуының аяқталу кезін белгілейтін жалғыз соңғы оқиға болуы керек. Бизнес – үрдістің бағытталған графына қолданылатын бұл шарт доғалары шығатын берілген графтың тек бір ғана төбесі және доғалары кіретін жалғыз төбесі болуы қажет екенін білдіреді.

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

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

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

1.4.2. Есептің математикалық қойылымы.

G = (V, E, h) бағытталған графты қарастырайық. Мұндағы V={v₁, v₂, … , v_n} – төбелердің ақырлы жиыны, E = {e₁, e₂, … , e_m} – доғалардың ақырлы жиыны, h: E → Z₊ – доғалардың салмақты функциясы. Есептің математикалық қойылымы үшін салмақты функциялар доғасының жеке мәндерін c_ij = h (e_k) арқылы белгілеу ыңғайлы, мұндағы e_k Є E доғасы (v_i,v_j) төбелерінің реттелген жұбына сәйкес келеді. Қарастырылатын есептің мазмұндық қойылымымен келісімді c_ij = h ((v_i, v_j)) мәндері участок ұзындығы сияқты түсіндірілуі мүмкін, i – қаласынан j – қаласына көшу құны немесе шығыны. Желілік графта кризистік жолды табу есебіне қолданылатын (v_i,v_j) әрбір доғасы бизнес – үрдістің жеке операциясы ретінде, ал c_ij мәні – (v_i,v_j) сәйкес операциясының орындалуының уақытша ұзақтығы ретінде түсіндіріледі.

Қосымша графта екі төбе белгіленеді: бастапқы төбе v_s және соңғы төбе v_t. Графтағы кез – келген маршрут ұзындығы осы маршрутқа кіретін доғалар салмағының қосындысына тең. G негізгі графы байлаулы болсын деп ойлайық, яғни v_t төбесі v_s ішінен потенциалды жеткілікті және цикл болмайды, v_s бастапқы төбелерінен v_t соңғы төбелеріне максималды ұзындықты маршрутты анықтау қажет.

Бағытталған графтағы минималды жол туралы есептегідей x_ij булевті айнымалыларын қарастыруға енгіземіз. Бұлар келесі түрде түсіндіріледі. Егер (v_i,v_j) доғасы ізделетін максималды ұзындық маршрутына енсе, онда айнымалы x_ij = 1, әйтпесе x_ij = 0. Яғни, егер (v_i,v_j) доғасы оптимальды маршрутқа енбесе. Онда жалпы жағдайда максималды маршрут туралы немесе графтағы бағдарланған жол туралы есептің математикалық қойылымы келесі түрде қалыптасуы мүмкін:

Мұндағы ∆_β жіберілетін альтернатива жиыны бағытталған графтағы минималды жол туралы есептің математикалық моделіндегі шектеулер жүйесіндегідей қалыптасады (1.3.2) – (1.3.5). Бұл 1.3.1. бөлімінде көрсетілгендіктен, мұнда көрсетілмейді. Сонымен, бағытталған графта максималды маршрутты табу есебінің математикалық қойылымы туралы сөз болғанда, (1.4.1), (1.3.2) – (1.3.5) модельдерін қарастырамыз.

G = (V, E, h) бағытталған графты қарастырайық. Мұндағы V={v₁, v₂, … , v_n} – төбелердің ақырлы жиыны, E = {e₁, e₂, … , e_m} – доғалардың ақырлы жиыны, h: E → Z₊ – доғаның өткізу қабілеттігі ретінде түсіндірілетін доғалардың салмақты функциясы. Қосымша графта екі төбе белгіленеді: бастапқы төбе v_s және соңғы төбе v_t. G негізгі графы байлаулы болсын деп ойлайық, яғни v_t төбесі v_s ішінен потенциалды жеткілікті және цикл жоқ, v_s бастапқы төбелерінен v_t соңғы төбелеріне баратын максималды ағынды анықтау қажет.

(v_i,v_j) Є E доғасы бойынша өтетін, ағын көлемі ретінде түсіндірілетін – x_ij келесі теріс емес бүтінсанды айнымалыларын қарастыруға енгіземіз. Онда желідегі максималды ағын туралы есептің математикалық қойылымы жалпы жағдайда келесі түрдегідей қалыптасуы мүмкін:

(1.5.1)
Мұндағы ∆_β жіберілетін альтернатива жиыны келесі теңсіздік түріндегі шектеулер жүйесімен қалыптасады:

(1.5.2)

(1.5.3)

(1.5.4)

(1.5.5)

Сонымен қатар бірінші (1.5.2) шектеуі келесі шарт орындалуын талап етеді – v_s төбесінен шығатын ағын көлемі v_t төбесіненен шығатын ағын көлеміне тең болуы қажет. Шектеулердің екінші тобы (1.5.3) келесі шарттың орындалуына кепілдік береді – графтың әрбір аралық төбесіне кіретін кез – келген бөлшектік ағын осы төбеден шығатын ағынға тең болуы қажет. (1.5.2) және (1.5.3) шектеулерінің жалпы саны n – 1-ге тең. Шектеулердің үшінші тобы (1.5.4) келесі шарттың орындалуын талап етеді: (v_i,v_j) Є E доғасы бойынша өтетін ағын көлемі c_ij доғасының өткізу қабілеттілігін жоғарылатпау қажет және теріс емес болуы қажет.

1. 
   Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. – М.: Высшая школа, 1976. -392 с.
   
2. 
   Таха Х. Введение в исследование операции. Том 1, 2..- М.: Мир, 1985.-480 с., - 495 с.
   
3. 
   Форд Л., Фалкерсон Д. Потоки в сетях. - М.: Мир, 1966 - 276 с.
   
4. 
   Ху Т. Целочисленное программирование и потоки в сетях.- М.: Мир, 1974. - 520 с.