Тағайындау туралы есептер

Тә жірибеде дискретті программалау ә дістерімен шығ арыла-тын есептердің бірі тағ айындау есебі. Халық шаруашылығ ында, оның ішінде агроө неркә сіп кешенінде тағ айындау есебіне ұ қ сас есептер кө птеп кездеседі. Мысалғ а, ауыл шаруашылығ ында бір тү рлі техникалармен бірнеше тү рлі жұ мыстар орындалады, бір жұ мысшы бірнеше тү рлі жұ мыс орындай алады, бірақ бір жұ мыс-шының немесе бір техника тү рінің кез келген жұ мыста ең бек ө німділігі (жұ мыс ө німділігі) немесе берілген уақ ыт аралығ ында жұ мыс кө лемін орындау қ абілеті, ақ ырында ә рбір жұ мыста олардың тиімділігі ә ртү рлі болуы мү мкін. Сондық тан техника тү рлерін немесе жұ мысшыларды тиімді бө ліп, ә рбір жұ мысқ а бекітіп, тағ айындау маң ызды экономикалық есептердің бірі. Мұ ндай мағ ынадағ ы есептер жалпы " Тағ айындау есебі" делінеді.

Айталық n тұ рлі жұ мысты n жұ мысшылар орындай алады делік. Сонымен қ атар ә рбір жұ мысшының кез-келген жұ мыстағ ы ең бек ө німділігі (шығ аратын шығ ыны немесе ә келетін пайдасы немесе т.б.с.с. кө рсеткіштерінің бірі) белгілі босын. Оны C_іj деп белгілейік, жә не .

Есептің экономикалық мә нісі – ә рбір жұ мысқ а тиісті жұ мыс-шыны тағ айындау нә тижесінде ө ндіріс орны ең жоғ ары тиімділікке (максималды ең бек ө німділігіне немесе пайдағ а немесе минималды жұ мыстың орындалу уақ ытына) жету керек. Сонымен қ атар, бір жұ мысшы тек бір жұ мысты ғ ана атқ аруғ а тағ айындалуғ а тиіс.

Есептің математикалық моделін қ ұ ру ү шін X _іj-мен і-жұ мыс-кердің j-жұ мысын атқ аруғ а тағ айындалғ анын белгілейік. Егер X _іj = 1болса, онда і -жұ мыскер j-жұ мысқ а тағ айындалғ ан, керісінше жағ дайда, яғ ни X _іj = 0 ол тағ айындалмағ ан. Сонымен, мә ндері тек 0 немесе 1 болатын, біз бірінші рет екілік айнымалылармен кездестік. Ә дебиеттерде екілік айнымалылар бинарлық, бульдік немесе логикалық деп аталады. Келесі кезекте осындай айнымалылармен қ алай жұ мыс істейтін жағ дайларғ а тоқ талайық. Екілік айнымалы-лар арқ ылы есептің жалпы математикалық моделін былай жазуғ а болады:

Мақ сат функция

(3.10)

Мына жағ дайда

(3.11)

Тағ айындау есептеріне айнымалылардың теріс болмау шарты жазылмайды.

Келтірілген модельден «Тағ айындау» есебі «Тасымалдау» ес-ебімен ө те жақ ын «Туысқ ан» екенін байқ ауғ а болады. «Туысқ ан»-дық есептің математикалық қ ұ рамында, жұ мысшылар жә не жұ мыс тү рлері, жү кті жіберу жә не қ абылдау пунктеріне сә йкес келетіні арқ ылы байқ алса, ал айырмашылығ ы жұ мысшылар саны жұ мыс тү рлерінің санына тең болуы (бірақ, мұ ндай жағ дай тағ айындау есебі ү шін міндетті шарт емес), сонымен қ атар айнымалылардың екілік типте болуы жә не олардың жолдар жә не бағ аналар бойынша сомасы бірдей бірге тең болуында.

Егер жұ мыскерлер санымен жұ мыс тү рлерінің саны бірдей болса, онда мұ ндай есептерді баланысталғ ан дейді де, ал керісінше жағ дайда баланысталмағ ан делінді.

Егер кейбір жұ мыстар бірнеше жұ мыскерлер арқ ылы орын-далса, бірақ жалпы керекті жұ мыскерлер санымен бар жұ мысшылар саны тең болса, онда мұ ндай тағ айындау есептері де баланысталғ ан делінеді. Мұ ндай есептерді «ұ жымы» мен жұ мыстарды орындау деп те атауғ а болады. Осындай жағ дайларда «тасымалдау» кестесі мына тү рде жазылады:

3.3-кесте. «Ұ жымы» мен жұ мыс орындау жағ дайдағ ы тағ айындау

есебінің кестесі

Есеп балансталғ ан болу ү шін мына шарт орындалуғ а тиіс:

K ₁ + K ₂ + …+K _m = n.

Жұ мысшылар жә не жұ мыс тү рлер саны бірдей болғ андағ ы есептің математикалық моделі (3.10) жә не (3.11) формулалар арқ ы-лы ө рнектелінеді. Ал «ұ жымы» мен жұ мыстарды орындайтын бол-са, 3.3-кестедегі кө рсетілген тә ртіп бойынша есептің математи-калық моделіне біраз ө згерістер енгізіледі, яғ ни:

Мақ сат функция

(3.12)

Мына жағ дайда

(3.13)

K ₁ + K ₂ + …+K _m = n. (3.14)

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

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

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

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

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

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

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