Балансталмаған тағайындау есептері

Балансталмаған тағайындау есептерінде көбінесе жұмыскерлер саны жұмыс түрлері санынан көп болады. Бірақ, мұндай жағдай міндетті шарт емес. Себебі тәжірибеде керісінше жағдайлар да кездесуі мүмкін. Ондай есептер кездескен жағдайда «Артық мөлшерлі есептер үшін шек-теулер» тәсілін оқып-зерделеген оқырман ешқандай қиындықсыз мұндай есептерді өзбетінше талқылай алуға тиіс. Біз тек жұмыс-керлер жұмыс түрлерінен көп болған жағдайды қарастырамыз. Мы-салға, m жұмыс түрлері және n жұмыскерлер, сонымен қатар m < n болсын. Сөзсіз, барлық вакансиялар қолданылып, бірнеше жұмыс-керлер жұмыссыз қалады да мынадай шектеулер құрылады:

– жұмыскерлердің жұмысқа тағайындалу жағдайы (жолдар бойынша сома)

– әрбір жұмыс түрлері толығымен жұмыскерлермен қамта-масыздандырылады (бағаналар бойынша сома)

«Ұжымы» мен жұмыстарды орындауға баланысталмаған тағайындау есептерінде шектеулер қалай жазылатын тәсілдерін қарастырайық. Мұндай есептерде мынадай шарт орындалынады: K₁+ K₂ + …+K_m < n. Келтірілген шартты ескере отырып, есептің шектеулерін былай өрнектейміз:

– жұмыскерлердің жұмысқа тағайындалу жағдайы (жолдар бойынша сома)

– әрбір жұмыс түрлері толығымен жұмыскерлермен қамта-масыздандырылады (бағаналар бойынша сома)

Мұндай есептер комбинаторлық класс есептеріне жатады. Қазіргі кезде осындай есептерді шешуге арналған бірнеше әдістер бар. Солардың ішіндегі ең көп таралғаны Венгер әдісі. «Тағайын-дау» есептерінің барлық варианттарын, n-үлкен сан болған жағдайда, қарастыру мұмкін емес. Себебі бір жұмысшыны барлық жұмысқа тағайындаумен қатар барлық жұмысшы бойынша n!-нұсқаларды қарастыру керек. Сондықтан мұндай есептер қазіргі кезде MS Excel көмегімен шығарылады.