Литтл алгоритмі негізіндегі коммивояжер мәселесін шешу

 ҚАЗАҚСТАН РЕСПУБЛИКАСЫНЫҢ ҒЫЛЫМ ЖӘНЕ БІЛІМ МИНИСТРЛІГІ Қ.И. Сәтбаев атындағы Қазақ ұлттық техникалық университеті Техникалық кибернетика кафедрасы КУРСТЫҚ ЖҰМЫСҚА түсіндірме жазба Тақырыбы Литтл есебі Жетекші _________________________ Доцент Л.Ш. Балғабаева «__» _________________2005ж. Студент Қуспанғалиева А.Н. Мамандығы 370140 (АӨБКЖ) Тобы КСУ-02-02 Алматы 2005 ЕСЕПТІҢ ҚОЙЫЛЫМЫ Операцияны зерттеу негіздері пәнінен курстық жұмысқа арналған тапсырма “ Литтл есебі ” негізгі әдістері (шекара және Жұмыс жетекшісі _________ Л.Ш. Балғабаева Жұмысты орындауға қабылдаған студент _______ Куспангалиева Тапсырманы орындауға қабылдап алған күні "___" ___________ 2005 Аяқталған жұмысты қорғау күні "____"___________2005ж. Курстық жұмысқа берілген тапсырма 32-вариант Мұнай көздерінен мұнай өңдейтін зауытқа қарай бір мұнай Төменде келтірілген сандық мәліметтер шартты бірліктермен берілген: m-4 Cij-2 i 1 2 3 4 1 x 2 6 x 4 3 3 2 2 x 1 4 4 6 5 x Мазмұны КІРІСПЕ ......................................................................................................... 1 Операцияны зерттеудің негізгі кезеңдері.................................................. 1.1 Операцияны жүйелеп талдау............................................................... 1.2 Операцияны басқару есептерін мазмұндау........................................ 1.3 Болжамдар жасау.................................................................................. 1.4 Математикалық модельді құру............................................................ 1.5 Басқару есептерін шешетін әдісті таңдау........................................... 1.6 Алгоритмдерді жүзеге асыратын программа құру және оны келтіру.................................................................................................... 1.7 Есепті шешу және шешімдерді талдау............................................... 2 Операцияларды зерттеудің негізгі принциптері....................................... 3 Қарапайым актілерді шығару мысалдары................................................. 3.1 Қоспаның ең жақсы құрамын анықтау (Диета тұтынушы 3.2 Металл өнімдерін тасымалдауды ұйымдастыру (транспорт)......... 4 Коммивояжер әдісі...................................................................................... 4.1 Литтл алгоритмі.................................................................................. 5 Сандық түрдегі шешім................................................................................ 6 Программаның баяндалуы ......................................................................... 6.1 Жалпы мағлұматтар .............................................................................. 6.2 Функционалдық тағайындалуы............................................................ 6.4 Шақыру және жүктеу ........................................................................... 6.5 Қажетті техникалық жабдықтар .......................................................... ҚОРЫТЫНДЫ.............................................................................................. ҚОЛДЫНЫЛҒАН ӘДЕБИЕТТЕР .......................................................... Қосымша А...................................................................................................... Қосымша Ә..................................................................................................... Қосымша Б..................................................................................................... КІРІСПЕ Қазіргі кезеңде операцияны зерттеу әдістері адамзат өмірінің әртүрлі Бұл ғылымның математикалық әдістері күрделі авиациялық, ракеталықжәне ғарыштық Негізінде ЭЕМ-ң өмірге келуі көптеген ғылымдардың пайда болуына Операцияны зерттеу әдістемесі соңғы бес онжылдықта экономика, ұйымдастырушылық, Іскерлік қабілеттілігін арттыруға ұмтылу қоғамға тән нәрсе және Негізінде АБЖ-ны – нақтылы және толық ақпаратты жаңа ЭЕМ-ы жаңарған сайын қабылданатын басқарушы шешімдердің толық және Бастапқы мәліметтер Өңделген ақпарат қосымша ақпарат Басқару сигналы Қабылданған шешімдер туралы ақпарат Қалыптаспаған ақпарат 1-сурет Мұндай жүйелердің негізгі ерекшеліктері интерпретациялық түсініктердің сәйкестілігінде , Операцияны зерттеудің даму тарихы – оның жұмыстарының масштабының Операцияның зерттеу әдісістерінің көмегімен әртүрлі есептер қарастырылады, бұл Операцияны зерттеу – білім саласы ретінде кеңейе түсуде, 1 Операцияны зерттеудің негізгі кезеңдері Кезең № Операцияны зерттеу кезеңдерінің аты-жөні Қажетті мамандар Операцияны (басқарылатын жүйелерді) жүйелеп талдау Операцияны басқару есептерін мазмұндау және операцияның қарапайым бөлшектерін Болжамдар жасау (жорамал құрастыру) Математикалық модельді жасау Басқару есептерін шешетін әдісті таңдау Алгоритмді жүзеге асыратын программа құратын және оны жөнге Есепті шешу және шешімдерді талдау Есептің шешімдерін іс жүзінде қолдану Жоспарлаушы (технолог) операцияны зерттеуші Жоспарлаушы (технолог) операцияны зерттеуші Жоспарлаушы (технолог), операцияны зерттеуші Операцияны зерттеуші, математика маманы Операцияны зерттеуші, математика маманы Жүйелеуші программа маманы, операцияны зерттеуші Жоспарлаушы және операцияны зерттеуші Алдыңғы кезеңдердегі барлық мамандар Басқарылатын дүниені жобалауға дейінгі Басқарылатын дүниені жобалауға дейінгі зерттеулер Басқарылатын дүниені жобалауға дейінгі зерттеулер Техникалық жобалау Техникалық жобалау Жұмыс жобалау кезеңіне сәйкес Өндірістік-тәжірибелік жағдайда іске асыру Өндіріске енгізу 1.1 Операцияны жүйелеп талдау Бұл кезеңдегі жұмыстарды технолог пен операцияны зерттеуші бірігіп 1.2 Операцияны басқару есептерін мазмұндау және Бұл кезеңдегі жұмыстарды технолог пен операцияны зерттеуші бірігіп Операцияның қозғаушы еүшінің тізбегі бөлу керек олар математикалық Осы қозғаушы күштерінің өзара әрекеттесуінің шамасы (сипаты) болу Осы операцияның бөлшектерінің бүтін операцияға орны көрсетілуі керек. Операцияның қарапайым бөлщектерін немесе актілерін бөліп шығару аралық 1.3 Болжамдар жасау Бұл кезеңдегі жұмыстарды технолог пен операцияны зерттеуші бірігіп Жиі кездесетін болжамдар: Суықтық. Дөңес. Адективтік. 1.4 Математикалық модельді құру Операцияны зерттеу үшін іс жүзінде қолданбалы математика маманы Модель – ақиқатты нақты белгілеу. Модель көмегімен есептеуге Тәуелсіз айнымалылар – есептің негізгі шешімдерін табуға қолданылады. Мақсатты функция – деп max немесе mіn мәнін Шектеулер – ол тәуелсіз айнымалылар жиынтығының дәлдік шегін 1.5 Басқару есептерін шешетін әдісті таңдау Бұл кезеңдегі жұмыстарды операцияны зерттеуші мен математика маманы Айнымалының саны бойынша бір өлшемді және көп өлшемді Шектеулерге байланысты шартты және шартсыз есептерге бөлінеді. Тәуелсіз айнымалының уақыттан функция болу болмауына байланысты статикалық, Ескерілетін информармацияның дәрежелері бойынша детерминдік және стохастикалық оптималдандыру Математикалық модельді жасаған соң мақсатты функциялар мен шектеулердің Сызықтық бағдарламалау – Егер мақсатты функция мен шектеулер Бейсызықты бағдарламалау – Егер математикалық функция немесе шектеулер Дискретті бағдарламалау – Егер математикалық функция мен шектеулер Динамикалық бағдарламалау – Егер тәуелсіз айнымалылар кейбір параметрден Ойындар теориясына – Егер шешім активті немесе Стохастикалық бағдарламалау – Егер тәуелсіз айнымалының бастапқы мәндері Сондықтан, қарастырып отырған есеп қандай математикалық бағдарламалау есептеріне Алгоритм дегеніміз – есептің шешімін табу үшін оның Алгоритмнің сипаттамалары 1. Детерминдік – ол есептеу кезендерінде де берілген 2. Есептеу процессінің дискреттілігі орындалуы күдік туғызбайтын бөліктелген 3. Жалпылық – ол әр – түрлі берілген 1.6 Алгоритмдерді жүзеге асыратын программа құру және оны Бұл кезеңдегі жұмыстарды операцияны зерттеуші мен программа Есептеу алгоритмінің блок – схемасы бойынша программаның детальдік Программа тілін таңдау. Программа құру. Шешүі белгілі (тесттік) есептер қолдана отырып, программаны тексеру Берәлген шарттардың өлшем функциясы ретінде есептеу алгоритмінің бір Кіріс және шығыс мәліметтерін белгілі бір формада дайындау. 1.7 Есепті шешу және шешімдерді талдау Бұл кезеңдегі жұмыстарды операцияны зерттеуші мен жоспарлаушы бірігіп Бұл кезеңде бастапқы мәліметтер жөнге келтіріледі. Есеп ЭЕМ 2 Операцияларды зерттеудің негізгі принциптері Операцияларды зерттеудің негізгі принциптері келесілер 1. Операцияны зерттейтін топ құрамына әртүрлі мамандар Себебі: Көптеген басқарлатын дүниелерді әртүрлі көзқараспен зерттеу керек. Бір адам әртүрлі салада білімді маман болуы қиын. Терең білімді. Ой - өрісі кең. Зерделі. Жұмысқа жеке мамандарды жұмылдыра алатын қабілеті болуы керек. Топтың жұмысын ойдағыдай атқару керек. 2. Математикалық модельдеу принципі Операцияны басқаруда шешім қабылдау үшін мтематикалық модельді қолдану. 3. Оптималдық принцип Шешім қабылдауда бізге кез - келген шешім керек 4. Іс жүзінде қолдану принципі Кез – келген операцияны зерттеудің негізгі бағыты өндіріске 5. Үйлестік (ұқсастық) принципі Жаңа есепті ұқсасты есепке келтіру. 6. Декомпозиция (бөлшектеу) принципі Күрделі операцияларды зерттеуде қолданылады. Мысалы, басқару теория негіздерінде жүйені бақылану мен 7. Жүйелер тәсілдерінің принциптерінің негізгі операцияларға әсер ететін 8. Агрегаттау (іріктеу) принципі Күрделі есеп шығару мен күрделі операцияларды зерттеуге қолданады. 3 Қарапайым актілерді шығару мысалдары 3.1 Қоспаның ең жақсы құрамын анықтау (Диета тұтынушы Мал шаруашылығында малға беретін жем құрамы жоспары. Жем - жем түрлері - Қоректі заттар саны - j жемнің бірлігіндегі I- заттың бірлігі - тәулігіндегі қоректі заттардың қажеттілігі - жем бірлігінің бағасы енгізу - Жемтүрінің мөлшері Қарапайым актілер: 1. Жем түрінің жалпы бағасын минималдау 2. Тәулікте қоректі заттар мөлшерін қанағаттандыру 3.2 Металл өнімдерін тасымалдауды ұйымдастыру (транспорт) Өндірістік қуаттары аі-ге тең бірінғай метал өнім шығынын К-дегенміз жүк бірлігінің арақашықтық бірлігіне тасымалдау құны. Материалдық техникалық жабдықтау басқармасына транспорт шығындары. Минималдау болатындай шығын -Тұтынушыларға жіберілетін металл мөлшерінің көлемі Қарапайым аспектілер: Транспорт шығынын минималдау (мақсатты функция) Тұтынушы сұрансын қанағттандыру Өндіріс қуаттарының шетілігін ескеру 4 Коммивояжер әдісі Коммивояжер n пунктке (қалаға) минималды жолмен бір-бір ретпен Коммивояжер туралы есептің математикалық моделі: 1- Егер Коммивояжер і-ші қаладан кейін 0- қарсы жағдайда. Цикл деп – реттелген қалалар жиынтығын айтады. Егер Сонда Коммивояжердың жалпы жол шығыны t циклына мынадай Циклда С матицасының әрбір жолының және әрбір бағанының h- келтіру рәсімінің немесе итерация нөмері k- келтірілген константа 4.1 Литтл алгоритмі к=1 Келтірілген матрицаны табу Ол үшін әрбір жолдың оң жағына ең кіші Келтірілген константаны табу Тарауға үміткерлер жұбын таңдау Тарауға тек -шісі 0-ге тең Үміткерлер үшін бағаларын анықтау Барлық бағалардың (Q (i, j)) ішінде ең үлкенін Q ( k, l ) =max Q(i, j) Максималды бағасы бар жұпты матрицадан сызып тастаймыз (к Алынған матрицаның шамасы 2х2 болса, екі жұп тарауға Келтіру рәсімі жасалады, есептелінеді k= k+1. Мысал 1: 1 2 1 2 3 4 5 х 4 2 х 8 5 5 8 1 5 4 2 5 5 1 1 2 1 2 3 4 5 х 0 0 х 3 0 0 3 0 4 0 0 1 2 1 2 3 4 5 х 0 0 х 3 0 0 3 0 4 1 2 1 2 4 5 х 0 0 х 0 3 0 4 2 3 1 4 5 0 3 3 х 4 0 0 2 0 2 3 1 4 5 х 3 1 х 4 0 1 0 2 3 1 4 5 х 3 0 х 3 0 2 5 1 4 х 0 0 0 0 0 0 0 5 Сандық түрдегі шешім Cij – тасымалдау құны. Хij – тасымалдаудың өнім көлемі. Қарапайым актілер: Мұнай шығындарын минималдандыру. Операцияның орындалуындағы ең жақсы жүйелігін қанағаттандыру. Жалпы түрдегі мақсатты функция: Мақсатты функция: Z = 3X12 + 2X13 + 5X14+6X21 +4X25+3X24+2X31+2X32+ X34+4X41+6X42+5X43 X12+ X13+ X14=1 X21+ X23 + X24=1 X31+ X32+ X34=1 X41+ X42+ X43=1 X21+ X 31+ X41=1 X12+ X32+ X42=1 X13+ X23+ X43=1 X14+ X24+ X34=1 1 2 3 4 1 x 3 2 5 2 2 6 x 4 3 3 3 2 2 x 1 1 4 4 6 5 x 4 1 2 3 4 1 x 1 0 3 2 3 x 1 0 3 1 1 x 0 4 0 2 1 x 0 1 0 0 1 2 3 4 1 x 0 0 3 2 3 x 1 0 3 1 0 x 0 4 0 1 1 x H(1) =11 C12=0 Q(1.2)=0 C13=0 Q(1.3)=1 C24=0 Q(2.4)=1 C32=0 Q(3.2)=0 C34=0 Q(3.4)=0 C41=0 Q(4.1)=2 2 3 4 1 0 0 x 0 2 x 1 0 0 3 0 x 0 0 0 0 0 H(2) =0 C12=0 Q(1.2)=0 C13=0 Q(1.3)=1 C24=0 Q(2.4)=1 C32=0 Q(3.2)=0 C34=0 Q(3.4)=0 2 4 2 x 0 3 0 0 H(3) =0 C24=0 Q(2.4)=x C32=0 Q(3.2)=x C34=0 Q(3.4)=0 11 13 4 1 6 Программаның баяндалуы 6.1 Жалпы мағлұматтар Қарастырылып отырған программа Borland Delphi 7.0 ортасында құрылды. 6.2 Функционалдық тағайындалуы Бұл программа жоғарыда берілген коммивояжер есебінің шығарылу жолын 6.4 Шақыру және жүктеу Біз бұл программаны орындау үшін Borland Delphi папкасын 6.5 Қажетті техникалық жабдықтар Бұл программаны жасауда Celeron 1800| 256 Mb| ҚОРЫТЫНДЫ Коммивояжер есебі жолдың бағытын таңдап оның ұзақтығын минималдауға Borland Delphi тілі арқылы коммивояжер есептің минималдау әдісі Бұл программа арқылы механикалық шеберханада бұйымдар жасаудың ең ҚОЛДАНЫЛҒАН ӘДЕБИЕТТЕР 1 Зуховицкий С.Н., Авдеева Л.И. Линейное и 2 Исследование операций (в 2 – х 3 Калихман И.Л. Сборник задач по математическому программированию 4 Таха Х. Введение в исследование операций (в М: Мир 1985. 5 Балғабаева Л.Ш. Сызықтық және бейсызықтық бағдарламалау. А: ҚазҰТУ 1997. Қосымша А Dim pro(), pro_u, a(), n, m, u, h(), Sub getmin() m_min = 0 pro_u = pro_u + 1 For i = 1 To m For j = 1 To m If a(u, i, j) "x" Then mini(u, i) = a(u, i, j) Else pro(pro_u, i, j) = a(u, i, j) End If Next For j = 1 To m If a(u, i, j) "x" Then If a(u, i, j) < mini(u, i) Then End If Next m_min = m_min + mini(u, i) Next For i = 1 To m For j = 1 To m If a(u, i, j) "x" Then a(u, i, j) = a(u, i, j) - pro(pro_u, i, j) = a(u, i, j) End If Next Next 'min from j pro_u = pro_u + 1 For i = 1 To m For j = 1 To m If a(u, j, i) "x" Then minj(u, i) = a(u, j, i) Else pro(pro_u, i, j) = a(u, i, j) End If Next For j = 1 To m If a(u, j, i) "x" Then If a(u, j, i) < minj(u, i) Then End If Next m_min = m_min + minj(u, i) Next For i = 1 To m For j = 1 To m If a(u, i, j) "x" Then a(u, i, j) = a(u, i, j) - pro(pro_u, i, j) = a(u, i, j) Қосымша А (жалғасы) End If Next Next h(u) = m_min End Sub Sub zero() For i = 1 To m For j = 1 To m If a(u, i, j) = 0 Then r_i = a(u, i, 0) r_j = a(u, 0, j) c(u, r_i, r_j) = 1 'first min min_i = 0 min_j = 0 For k = 1 To m If a(u, i, k) "x" And k min_i = a(u, i, k) End If If a(u, k, j) "x" And k min_j = a(u, k, j) End If Next 'real min For k = 1 To m If a(u, i, k) "x" And k If a(u, i, k) < min_i Then min_i End If If a(u, k, j) "x" And k If a(u, k, j) < min_j Then min_j End If Next q(u, r_i, r_j) = min_i + min_j End If Next Next End Sub Sub getmax() Max = 0 p_i = 0 p_j = 0 For i = 1 To n For j = 1 To n If c(u, i, j) = 1 Then If q(u, i, j) > Max Then Max = q(u, i, j) Қосымша А (жалғасы) p_i = i p_j = j End If If q(u, i, j) = Max And a(1, Max = q(u, i, j) p_i = i p_j = j End If End If Next Next path(u, 1, 1) = p_i path(u, 1, 2) = p_j If u > 1 Then path(u, 1, 3) = path(u - 1, 1, Else path(u, 1, 3) = h(u) End If path(u, 2, 1) = p_j path(u, 2, 2) = p_i path(u, 2, 3) = path(u, 1, 3) + End Sub Sub otrez() u = u + 1 m = m - 1 k_i = 0 k_j = 0 x_i = 0 x_j = 0 pro_u = pro_u + 1 For i = 0 To m + 1 For j = 0 To m + 1 If a(u - 1, i, 0) p_i a(u, k_i, k_j) = a(u - 1, i, pro(pro_u, k_i, k_j) = a(u, k_i, k_j) k_j = k_j + 1 If k_j > m Then k_j = 0 k_i = k_i + 1 End If End If Next If a(u, i, 0) = path(u - 1, If a(u, 0, i) = path(u - 1, Next Қосымша А (жалғасы) If x_i 0 And x_j 0 a(u, x_i, x_j) = "x" pro(pro_u, x_i, x_j) = a(u, x_i, x_j) End If End Sub Private Sub find_Click() ReDim h(n + 2) ReDim mini(n, n), minj(n, n), c(n, n, n), Dim fs_j(2) As Integer m = n While m 2 Call getmin Call zero Call getmax Call otrez Wend If a(u - 1, 1, 1) = "x" fs_j(1) = 2 fs_j(2) = 1 End If If a(u - 1, 1, 2) = "x" fs_j(1) = 1 fs_j(2) = 2 End If k = a(u, 2, 0) For i = 1 To 2 h(u) = 0 path(u, 1, 1) = a(u - i + path(u, 1, 2) = a(u - i + path(u, 1, 3) = path(u - 1, 1, path(u, 2, 1) = a(u - i + path(u, 2, 2) = a(u - i + path(u, 2, 3) = "-100" u = u + 1 Next u = u - 1 Call uploadtofile End Sub Sub uploadtofile() file = "out.txt" Open file For Output As #1 For l = 1 To n - 2 For k = 1 To 3 For i = 0 To n - l Қосымша А (жалғасы) s = "" For j = 0 To n - l If i = 0 Or j = 0 s = s + Trim(a(l, i, j)) Else s = s + Trim(pro(l + k - End If If i = 0 And j = 0 s = s + " " End If If i = 0 Or j = 0 s = s + " |" ElseIf Len(Trim(pro(l + k - 1, i, j))) s = s + " " Else s = s + " " End If Next Write #1, s Next Write #1, If k = 1 Then Write #1, "min i=" For i = 1 To n - l Write #1, mini(l, i) Next Write #1, End If If k = 2 Then s = "min j=" For i = 1 To n - l s = s + Trim(minj(l, i)) + " Next Write #1, s Write #1, End If Next s = "" For i = 1 To n For j = 1 To n If c(l, i, j) = 1 Then s = "C(" + Trim(i) + "," + Write #1, s End If Next Қосымша А (жалғасы) Next s = "max=Q(" + Trim(path(l, 1, 1)) + Write #1, s Write #1, Next For i = 0 To 2 s = "" For j = 0 To 2 s = s + Trim(a(n - 1, i, If i = 0 And j = 0 s = s + " " End If If i = 0 Or j = 0 s = s + " |" ElseIf Len(Trim(a(n - 1, i, j))) = 2 s = s + " " Else s = s + " " End If Next Write #1, s Next Write #1, '65 65 ' *->4,3 ' \ ' 80 ' 3,4 s = "" s = Trim(path(1, 1, 3)) + " s1 = " *" s2 = " " s3 = "" s4 = "" For i = 1 To u s = s + Trim(path(i, 1, 3)) + s1 = s1 + "->" + Trim(path(i, 1, s2 = s2 + "\ If path(i, 2, 3) = -100 Then s3 = s3 + " бес" Else s3 = s3 + " " End If s4 = s4 + " " Next s1 = s1 + "->" + Trim(path(u, 1, Write #1, s Қосымша А (жалғасы) Write #1, s1 Write #1, s2 Write #1, s3 Write #1, s4 Close #1 ztext.Text = Trim(path(u, 1, 3)) s = Trim(path(1, 1, 1)) k = path(1, 1, 2) For i = 1 To 3 For j = 1 To n If path(j, 1, 1) = k Then k = path(j, 1, 2) s = s + "->" + Trim(path(j, 1, Exit For End If Next Next pathtext.Text = s End Sub Private Sub loadfromfile_Click() List1.Clear pro_u = 1 file = "in.txt" n = Int(ntext.Text) ReDim a(n, n, n) ReDim pro((n - 1) * 3, n, n) u = 1 Open file For Input As #1 For i = 1 To n s = "" For j = 1 To n Input #1, a(u, i, j) If a(u, i, j) = -1 Then a(u, pro(pro_u, i, j) = a(u, i, j) s = s + Trim(a(u, i, j)) + Next List1.AddItem (s) a(u, i, 0) = i a(u, 0, i) = i pro(pro_u, i, 0) = a(u, i, 0) pro(pro_u, 0, i) = a(u, 0, i) Next Close #1 End Sub Қосымша Ә Сурет 1 - Кіріс мәліметтер Қосымша Б Кіріс мәліметтер -1 3 2 6 -1 4 2 2 -1 4 6 5 Шығыс мәліметтер " |1 |2 |3 |4 |" "1 |x 3 2 5 "2 |6 x 4 3 "3 |2 2 x 1 "4 |4 6 5 x "min i=" 2 3 1 4 " |1 |2 |3 |4 |" "1 |x 1 0 3 "2 |3 x 1 0 "3 |1 1 x 0 "4 |0 2 1 x "min j=0 1 0 0 " " |1 |2 |3 |4 |" "1 |x 0 0 3 "2 |3 x 1 0 "3 |1 0 x 0 "4 |0 1 1 x "C(1,2)=0 Q=(1,2)=0" "C(1,3)=0 Q=(1,3)=1" "C(2,4)=0 Q=(2,4)=1" "C(3,2)=0 Q=(3,2)=0" "C(3,4)=0 Q=(3,4)=0" "C(4,1)=0 Q=(4,1)=2" "max=Q(4,1)" " |2 |3 |4 |" "1 |x 1 0 " "2 |3 x 1 " "3 |1 1 x " "min i=" 0 Қосымша Б (жалғасы) 0 0 " |2 |3 |4 |" "1 |x 0 0 " "2 |3 x 1 " "3 |1 0 x " "min j=0 0 0 " " |2 |3 |4 |" "1 |0 0 x " "2 |x 1 0 " "3 |0 x 0 " "C(1,2)=0 Q=(1,2)=0" "C(1,3)=0 Q=(1,3)=1" "C(2,4)=0 Q=(2,4)=1" "C(3,2)=0 Q=(3,2)=0" "C(3,4)=0 Q=(3,4)=0" "max=Q(1,3)" " |2 |4 |" "2 |x 0 " "3 |0 0 " "11 11 11 " *->4,1->1,3->2,2->3,4->11" " \ \ " 13 12 " 1,4 3,1 2 Басқарушы орталық Басқарылатын объект Мәліметтерді өңдеу жүиесі 2.3 4.2 3.1 1.4 3.2 2.4 1.3 4.1 ..1