វិធីសាស្រ្ត Gomory ។ ដំណោះស្រាយនៃបញ្ហាការសរសេរកម្មវិធីចំនួនគត់

បញ្ហាទម្ងន់នៃការធ្វើផែនការសេដ្ឋកិច្ចនិងសូម្បីតែបញ្ហាពីវិស័យដទៃទៀតនៃបញ្ហាជីវិតរបស់មនុស្សដែលមានទំនាក់ទំនងជាមួយអថេរទាក់ទងទៅនឹងចំនួនគត់។ ជាលទ្ធផលនៃការវិភាគរបស់ខ្លួននិងការស្វែងរកវិធីល្អបំផុតដើម្បីដោះស្រាយបញ្ហាប្រឈមខ្លាំងសញ្ញាណនេះ។ លក្ខណៈពិសេសរបស់វាគឺជាលក្ខណៈពិសេសខាងលើនេះត្រូវចំណាយពេលជាតម្លៃចំនួនគត់និងភារកិច្ចខ្លួនវាត្រូវបានគេចាត់ទុកថាជាអ្នកសរសេរកម្មវិធីចំនួនគត់គណិតវិទ្យា។

ការប្រើប្រាស់សំខាន់នៃបញ្ហាជាមួយនឹងអថេរចំនួនគត់គឺការបង្កើនប្រសិទ្ធិភាព។ វិធីសាស្រ្តដែលប្រើជាចំនួនគត់មួយ សរសេរកម្មវិធីលីនេអ៊ែរ, ហៅផងដែរថាវិធីសាស្រ្តកាត់ផ្តាច់បាន។

វិធីសាស្រ្ត Gomory ត្រូវបានដាក់ឈ្មោះតាមគណិតវិទូដែលបានអភិវឌ្ឍដំបូងនៅក្នុង 1957-1958 ក្បួនដោះស្រាយនៅតែប្រើយ៉ាងទូលំទូលាយដើម្បីដោះស្រាយបញ្ហាការសរសេរកម្មវិធីលីនេអ៊ែរចំនួនគត់។ សំណុំបែបបទដែល Canonical នៃបញ្ហាការសរសេរកម្មវិធីចំនួនគត់អនុញ្ញាតឱ្យចូលដំណើរការបាននិងបង្ហាញយ៉ាងពេញលេញនូវឧត្តមភាពនៃវិធីសាស្រ្តនេះ។

វិធីសាស្រ្ត Gomori អនុវត្តទៅការសរសេរកម្មវិធីលីនេអ៊ែរយ៉ាងខ្លាំងក្នុងការស្វែងរកភារកិច្ចស្មុគស្មាញតម្លៃល្អបំផុតនោះ។ បន្ទាប់ពីសមាហរណកម្មគឺជាការតម្រូវជាមូលដ្ឋានបន្ថែមទៀតប៉ារ៉ាម៉ែត្រទាំងអស់នៃបញ្ហានេះ។ មានករណីគឺនៅពេលដែលមានបញ្ហាដោយមាន (គត់) ផែនការត្រឹមត្រូវដែលបានមានវត្តមាននៅក្នុង មុខងារគោលដៅ នៃការរឹតបន្តឹងលើសំណុំទទួលយកការសម្រេចចិត្តនេះបានមកដើម្បីសម្រេចបានអតិបរមា។ នេះគឺដោយសារតែការខ្វះខាតរបស់វាគឺដំណោះស្រាយអាំងតេក្រាល។ ដោយគ្មានលក្ខខណ្ឌដូចគ្នា, ជាក្បួនមួយនៅក្នុងសំណុំបែបបទនៃការសម្រេចចិត្តមួយគឺវ៉ិចទ័រសមរម្យ។

ដើម្បីបង្ហាញអំពីភាពត្រឹមត្រូវក្បួនដោះស្រាយការដោះស្រាយបញ្ហាជាលេខសម្រាប់ការមានតម្រូវការអនុវត្ត superimposition បន្ថែមទៀតនៃស្ថានភាពផ្សេងគ្នា។

ដោយប្រើវិធីសាស្រ្តនៃ Gomory ជាធម្មតាពិចារណាផែនការជាច្រើនសម្រាប់បញ្ហាដែលគេហៅថាដំណោះស្រាយ polyhedron កំណត់។ នៅលើមូលដ្ឋាននេះសំណុំនៃផែនការសំខាន់ទាំងអស់មានតម្លៃកំណត់សម្រាប់ភារកិច្ច។

ដូចគ្នានេះផងដែរសម្រាប់ធានាមុខងារសំខាន់សន្មត់ថាតម្លៃនៃមេគុណនេះគឺគត់ផងដែរ។ ទោះបីជាមានភាពធ្ងន់ធ្ងរនៃស្ថានភាពទាំងនេះខ្សោយដែលពួកគេបានគ្រប់គ្រងមួយចំនួន។

វិធីសាស្រ្តពាក់ព័ន្ធនឹងការរឹតបន្តឹងជាសំខាន់ Gomory អគារដែលបានកាត់បន្ថយដំណោះស្រាយដែលមិន nonintegral ។ ក្នុងករណីនេះមិនមានការកាត់ផ្តាច់មិនមានដំណោះស្រាយចំនួនគត់ផែនការ។

ក្បួនដោះស្រាយសម្រាប់ការដោះស្រាយបញ្ហាទាក់ទងនឹងការស្វែងរកជម្រើសសមរម្យ វិធីសាស្រ្តធម្មតា, ដោយមិនយកទៅក្នុងគណនីលក្ខខណ្ឌនៃការរួមបញ្ចូលគ្នានេះ។ ប្រសិនបើមានសមាសភាគទាំងអស់នៃផែនការល្អប្រសើរបំផុតនេះមានការសម្រេចចិត្តទាក់ទងទៅនឹងចំនួនគត់, វាអាចត្រូវបានសន្មត់ថាគោលដៅសរសេរកម្មវិធីចំនួនគត់ត្រូវបានសម្រេច។ ប្រហែលជាដែលត្រូវបានរកឃើញនៃ insolubility បញ្ហានេះដូច្នេះយើងមានភស្តុតាងដែលថាបញ្ហាការសរសេរកម្មវិធីចំនួនគត់មានដំណោះស្រាយទេ។

វ៉ារ្យ៉ង់, នៅពេលដែលសមាសភាគនៃដំណោះស្រាយល្អប្រសើរបំផុតដែលមានលេខដែលមិនមែនជាចំនួនគត់។ ក្នុងករណីនេះការដាក់កម្រិតថ្មីត្រូវបានបន្ថែមទៅឧបសគ្គទាំងអស់នៃបញ្ហានេះ។ នេះជាការរឹតបន្តឹងថ្មីត្រូវបានកំណត់លក្ខណៈដោយចំនួននៃលក្ខណៈសម្បត្តិមួយ។ ជាដំបូងនៃការទាំងអស់វាគួរតែមានលីនេអ៊ែរ, គួរតែត្រូវបានកាត់ផ្តាច់ពីសំណុំរកឃើញនៃផែនការដែលមិនមែនជាចំនួនគត់ល្អបំផុត។ ជាដំណោះស្រាយចំនួនគត់ទាំងមិនគួរត្រូវបានបាត់បង់, បានកាត់ផ្តាច់។

នៅពេលដែលការកសាងការរឹតបន្តឹងគួរត្រូវបានជ្រើសសមាសភាគមួយនៃផែនការល្អប្រសើរបំផុតជាមួយប្រភាគខ្ពស់បំផុត។ វាគឺជាការកំណត់នេះនឹងត្រូវបានបន្ថែមទៅក្នុងតារាងធម្មតាដែលមានស្រាប់។

យើងបានរកឃើញដំណោះស្រាយនៃបញ្ហាលទ្ធផលដោយប្រើការបម្លែងសាមញ្ញធម្មតា។ យើងបានពិនិត្យមើលដំណោះស្រាយនៃបញ្ហានេះនៅលើអត្ថិភាពនៃផែនការល្អប្រសើរបំផុតចំនួនគត់ដែលបានប្រសិនបើលក្ខខណ្ឌត្រូវបានពេញចិត្តបន្ទាប់មកបញ្ហានេះត្រូវបានដោះស្រាយ។ ប្រសិនបើលទ្ធផលនេះត្រូវបានទទួលបានជាថ្មីម្តងទៀតជាមួយនឹងវត្តមាននៃដំណោះស្រាយមិនមែនជាចំនួនគត់, បន្ទាប់មកយើងណែនាំកម្រិតបន្ថែមនិងការធ្វើឡើងវិញដំណើរការគណនា។

ដោយអនុវត្តចំនួនកំណត់នៃការនិយាយឡើងវិញនោះយើងសម្រេចបាននូវកម្មវិធីល្អប្រសើរបំផុតនៃបញ្ហាដែលបានចោទនៅចំពោះមុខនៃកម្មវិធីចំនួនគត់ឬបញ្ជាក់ថា insolubility នៃបញ្ហានេះ។