Кіріспе
Комбинаторлық оңтайландыру мәселесі
Тапсыру мәселесі – комбинаторлық оңтайландырудың негізгі мәселесі. Ең жалпы түрінде мәселе мынадай: Мәселе мысалында бірнеше агенттер мен бірнеше тапсырмалар болады. Кез келген агентке кез келген тапсырманы орындауға тағайындауға болады, бұл агент-тапсырма тағайындамасына байланысты өзгеріп отыруы мүмкін белгілі бір құн тудырады. Әр тапсырмаға ең көп дегенде бір агентті және әр агентке ең көп дегенде бір тапсырманы тағайындау арқылы, мүмкіндігінше көп тапсырманы орындау қажет, сонда тағайындаманың жалпы құны ең төмен болады. Басқаша айтқанда, мәселені графтар теориясын қолдану арқылы сипаттауға болады: Тапсыру мәселесі – салмақты екі бөлікті графта берілген өлшемдегі сәйкестікті табудан тұрады, онда қабырғалардың салмақтарының қосындысы ең аз. Агенттер мен тапсырмалардың саны тең болса, онда мәселе теңгерімді тағайындама деп аталады. Әйтпесе, теңгерімсіз тағайындама деп аталады. Егер барлық тапсырмалар үшін тағайындаманың жалпы құны әрбір агенттің құнының қосындысына тең болса (немесе әрбір тапсырманың құнының қосындысы, бұл жағдайда бірдей), онда мәселе сызықтық тағайындама деп аталады. Көбінесе, ешқандай қосымша нақтыламасыз тапсыру мәселесі туралы айтқанда, сызықтық теңгерімді тағайындама мәселесі түсініледі.
The problem instance has a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent task assignment. It is required to perform as many tasks as possible by assigning at most one agent to each task and at most one task to each agent, in such a way that the total cost of the assignment is minimized. Alternatively, describing the problem using graph theory:
The assignment problem consists of finding, in a weighted bipartite graph, a matching of a given size, in which the sum of weights of the edges is minimum. If the numbers of agents and tasks are equal, then the problem is called balanced assignment. Otherwise, it is called unbalanced assignment. If the total cost of the assignment for all tasks is equal to the sum of the costs for each agent (or the sum of the costs for each task, which is the same thing in this case), then the problem is called linear assignment. Commonly, when speaking of the assignment problem without any additional qualification, then the linear balanced assignment problem is meant.
Мысалдар
Мысалы, такси компаниясында үш такси (агент) және үш клиент (тапсырма) бар, оларды мүмкіндігінше жылдам алып кетуді қалайды. Компания жылдам қызмет көрсетумен мақтанады, сондықтан әрбір такси үшін нақты клиентті алып кетудің "бағасы" таксинің клиентке жетуіне кеткен уақытқа байланысты болады. Бұл – теңгерілген тағайындау мәселесі. Оның шешімі – таксилер мен клиенттердің қандай комбинациясы ең төменгі жалпы бағаға ие болса, соның нәтижесінде шығады. Енді, төрт такси бар делік, бірақ клиенттер саны үш қана. Бұл – теңгерілмеген тағайындау мәселесі. Оны шешудің бір жолы – төртінші жасанды тапсырманы ойлап табу, мысалы, "бос отыру" деп атауға болады, мұндай тапсырмаға тағайындалған такси үшін баға 0-ге тең болады. Бұл мәселені теңгерілген тағайындау мәселесіне дейін тоғыстырады, одан кейін оны әдеттегідей шешуге болады және бұл мәселенің ең жақсы шешімін береді. Агенттерден көп тапсырмалар болғанда, бірнеше агенттерді бір тапсырмаға тағайындау қажет болғанда (мысалы, бір таксиге сыймайтын клиенттер тобы) немесе бағаны азайтудың орнына пайданы арттыру үшін де осындай түзетулер жасауға болады.
Алгоритмдер
Тапсырмалар мәселесін шешудің қарапайым тәсілі – барлық мүмкін тапсырмаларды тексеріп, әрқайсысының құнын есептеу. Бұл өте тиімсіз болуы мүмкін, себебі n агент және n тапсырма болғанда, n! (n факториалы) түрлі тапсырмалар болады. Тағы бір қарапайым тәсіл – ең төменгі құнмен жұпты алдымен тағайындап, осы агенттер мен тапсырмаларды алып тастау; содан кейін, қалған агенттер мен тапсырмалар арасынан ең төменгі құнмен жұпты тағайындау; және т.с.с. Бұл алгоритм оңтайлы емес шешім беруі мүмкін. Мысалы, екі тапсырма және екі агент бар делік, олардың құны былай: Алиса: 1-ші тапсырма = 1, 2-ші тапсырма = 2. Жорж: 1-ші тапсырма = 5, 2-ші тапсырма = 8. Алдымен тағайындау алгоритмі 1-ші тапсырманы Алисаға, 2-ші тапсырманы Жоржқа тағайындайды, бұл жағдайда жалпы құн 9-ға тең. Бірақ кері тағайындаудың жалпы құны 7-ге тең. Әйбағымызға орай, n-ге қатысты полиномдық уақытта оңтайлы тағайындауды табуға арналған көптеген алгоритмдер бар. Тапсырмалар мәселесі – тасымалдау мәселесінің ерекше жағдайы, ал тасымалдау мәселесі – ең төменгі құнмен ағын мәселесінің ерекше жағдайы, ал ол өз кезегінде сызықтық бағдарламаның ерекше жағдайы. Бұл мәселелердің кез келгенін симплекс алгоритмін қолдану арқылы шешуге болады, бірақ әр мамандық үшін шешім кеңістігі кішірек және осының арқасында оның ерекше құрылымын пайдалануға арналған тиімді алгоритмдер жасалған.
Alice: Task 1 = 1, Task 2 = 2. George: Task 1 = 5, Task 2 = 8. The greedy algorithm would assign Task 1 to Alice and Task 2 to George, for a total cost of 9; but the reverse assignment has a total cost of 7. Fortunately, there are many algorithms for finding the optimal assignment in time polynomial in n. The assignment problem is a special case of the transportation problem, which is a special case of the minimum cost flow problem, which in turn is a special case of a linear program. While it is possible to solve any of these problems using the simplex algorithm, each specialization has a smaller solution space and thus more efficient algorithms designed to take advantage of its special structure.
Теңгерімді тапсырма
Теңгерілген тапсырма мәселесінде екі жақты графтың екі бөлігінде де n арқылы белгіленетін төбелер саны бірдей болады.
Теңгерілген тапсырма үшін алғашқы полиномиалдық уақыт алгоритмдерінің бірі – венгр алгоритмі. Бұл жаһандық алгоритм – ол кеңейтілген жолдар (сәйкес келмейтін төбелер арасындағы кезектесетін жолдар) бойынша сәйкестікті жақсартуға негізделген. Фибоначчи үйінділерін пайдаланғанда оның орындалу уақытының күрделілігі , мұндағы m – қабырғалар саны. Бұл қазіргі уақытта осы мәселенің күшті полиномиалдық алгоритмінің ең жылдам орындалу уақыты. Егер барлық салмақтар бүтін сандар болса, онда орындалу уақытын дейін қысқартуға болады, бірақ нәтижесіндегі алгоритм әлсіз полиномиалды болады. Егер салмақтар бүтін сандар болса және барлық салмақтар C-ден аспаса (мұнда C>1 – қандай да бір бүтін сан), онда мәселені салмақтарды масштабтау әдісімен әлсіз полиномиалдық уақытта шешуге болады. Жалпы әдістерден басқа, жергілікті жаңартуларды табуға негізделген жергілікті әдістер де бар (толық кеңейтілген жолдар емес). Бұл әдістердің асимптотикалық орындалу уақытының кепілдіктері нашар, бірақ олар көбінесе тәжірибеде жақсы жұмыс істейді. Бұл алгоритмдер аукциондық алгоритмдер, итеру-белгілеу алгоритмдері немесе алдын ала ағын итеру алгоритмдері деп аталады. Олардың кейбіреулері эквивалентті екені дәлелденді. Жергілікті әдістердің кейбіреулері графтың толық сәйкестікке ие екенін болжайды; егер бұл жағдай болмаса, онда осы әдістердің кейбіреулері шексіз циклға түсуі мүмкін. Ең төменгі салмақты толық сәйкестік мәселесі графтың жанындағы матрицасында минорларды табуға келтіріледі. Изоляция леммасын пайдаланып, графтағы ең аз салмақты толық сәйкестікті кем дегенде 1/2 ықтималдығымен табуға болады. N төбесі бар граф үшін уақыт қажет.
Теңгерімсіз тапсырма
Теңгерімсіз тағайындау мәселесінде екі жақты графиктің үлкен бөлігінде n төбе, ал кіші бөлігінде r<n төбе болады. Сондай-ақ, графиктегі максималды сәйкестіктің кардиналдығынан аспайтын s тұрақтысы бар. Мақсат – дәл s өлшемді ең төмен құнмен сәйкестікті табу. Ең көп кездесетін жағдай – график бір жақты толық сәйкестікті (яғни r өлшемді сәйкестікті) қабылдайтын және s=r тең болатын жағдай. Теңгерімсіз тағайындауды теңгерімді тағайындауға келтіруге болады. Наive келтіру – кіші бөлікке жаңа төбелер қосу және оларды 0 құнмен үлкен бөлікке жалғау. Дегенмен, бұл жаңа қабырғаларды қажет етеді. Көбірек тиімді келтіру – екі еселеу әдісі. Бұл жерде G' жаңа графигі бастапқы G графигінің екі көшірмесінен құрылады: Gf – алға қарай көшірмесі және Gb – артқа қарай көшірмесі. Артқа қарай көшірме «кері тігіледі», сондықтан G''' графигінің әр жағында енді n+r төбе бар. Көшірмелер арасында екі түрлі байланыс қабырғасын қосу қажет: (II кестеге қараңыз). Олардың жұмысы тағайындау мәселесі (және жалпы ең үлкен салмақты сәйкестендіру мәселесі) үшін жуықтау алгоритмін ұсынады, ол кез келген белгіленген қателік шегі үшін сызықтық уақытта жұмыс істейді.
Жалпылау
Графтар теориясының мәселесі ретінде қарастырылғанда, тапсырма мәселесі екі бөлікті графтардан кез келген графтарға дейін кеңейтілуі мүмкін. Салмақтардың қосындысы максималды болатын салмақты графта сәйкестік табуға қатысты мәселе ең үлкен салмақты сәйкестік табу мәселесі деп аталады. Тапсырма мәселесінің тағы бір жалпылауы – сәйкестендірілетін жиынтар санын екіден көпке дейін ұлғайту. Агенттерді міндеттермен сәйкестендірудің орнына, мәселе агенттерді міндеттермен, уақыт кезеңдерімен және орындармен сәйкестендіруге дейін кеңейтіледі. Бұл көп өлшемді тапсырма мәселесіне (MAP) алып келеді.