Математические методы в экономике. Копылов Г.Н - 42 стр.

UptoLike

ВУЗ: 

ВолГУ | Волгоград

Составители: 

Рубрика: 

42
§4. ÇÀÄÀ×À Î ÍÀÇÍÀ×ÅÍÈßÕ
Ïðåäïîëîæèì, â îòäåëå åñòü n äîëæíîñòåé è n êàíäèäàòîâ
íà ýòè äîëæíîñòè. Êàê íàçíà÷èòü êàíäèäàòîâ íà äîëæíîñòè îïòè-
ìàëüíûì îáðàçîì?
Êàêóþ èíôîðìàöèþ ìû áóäåì èñïîëüçîâàòü? Åñëè ìû çíà-
åì, íà êàêèõ äîëæíîñòÿõ ìîæåò ðàáîòàòü êàæäûé ÷åëîâåê, òî
íà÷àëüíûå äàííûå ìîæíî çàäàòü â âèäå êâàäðàòíîé ìàòðèöû Ñ,
èìåþùåé ðàçìåðíîñòü (ï½ï). Ýëåìåíòû ýòîé ìàòðèöû — íóëè è
åäèíèöû.
c
ij
=
1
0
,
,
если
i
-й человек мо ж ет р аботать на
j
-й должн ости;
если
i
-й человек не может рабо тать на
j
-й должн ости.
Ñóùåñòâóåò ëè òàêîå ðàñïðåäåëåíèå ðàáîò, ÷òîáû êàæäûé
÷åëîâåê ñïðàâëÿëñÿ ñ ðàáîòîé íà ñâîåé äîëæíîñòè? Êàê ëó÷øå
íàçíà÷èòü ëþäåé íà ðàáîòû?
Íàçíà÷åíèå ÷åëîâåêà íà äîëæíîñòü ìîæíî ðàññìàòðèâàòü,
êàê âûáîð îïðåäåëåííîãî ýëåìåíòà ìàòðèöû Ñ. Êàæäûé ÷åëîâåê
äîëæåí ðàáîòàòü òîëüêî íà îäíîé äîëæíîñòè, è íà êàæäîé äîëæ-
íîñòè äîëæåí ðàáîòàòü òîëüêî îäèí ÷åëîâåê. Ïîýòîìó â êàæäîé
ñòðî÷êå è â êàæäîì ñòîëáöå ìàòðèöû Ñ äîëæíî áûòü âûáðàíî
ðîâíî ïî îäíîé åäèíèöå. Ïîëó÷èëè ñëåäóþùóþ ìàòåìàòè÷åñêóþ
çàäà÷ó:
 ìàòðèöå Ñ(n½n) âûáðàòü n ýëåìåíòîâ, ñòîÿùèõ â ðàçíûõ
ñòðîêàõ è ðàçíûõ ñòîëáöàõ, òàê, ÷òîáû èõ ñóììà áûëà ìàêñè-
ìàëüíîé
3
.
 èäåàëå ýòà ñóììà äîëæíà áûòü ðàâíà n. Ýòî âîçìîæíî â òîì
ñëó÷àå, åñëè äëÿ êàæäîãî ê (1 ≤
ê ≤n) è ëþáûõ ê äîëæíîñòåé,
íàéäåòñÿ íå ìåíåå ê ÷åëîâåê, êàæäûé èç êîòîðûõ ìîæåò ñïðà-
âèòüñÿ õîòÿ áû ñ îäíîé èç ýòèõ ê äîëæíîñòåé (òåîðåìà Õîëëà).
Ðàññìîòðèì äðóãèå ñïîñîáû ðàññìîòðåíèÿ ýòîé çàäà÷è. Çà-
äàäèì ðàñïðåäåëåíèå ïî äîëæíîñòÿì ñ ïîìîùüþ ìàòðèöû Õ(n½n),
ñîñòîÿùåé èç íóëåé è åäèíèö.
x
ij
=
1
0
,
,
если
i
-й человек будет назначен на
j
-ю должность;
если
i
-й человек не будет назначен на
j
-ю должность
__________________
3
Ïðè äðóãîé ïðàêòè÷åñêîé ñèòóàöèè ýòó ñóììó íàäî ìèíèìèçè-
ðîâàòü.
                     §4. ÇÀÄÀ×À Î ÍÀÇÍÀ×ÅÍÈßÕ

     Ïðåäïîëîæèì, â îòäåëå åñòü n äîëæíîñòåé è n êàíäèäàòîâ
íà ýòè äîëæíîñòè. Êàê íàçíà÷èòü êàíäèäàòîâ íà äîëæíîñòè îïòè-
ìàëüíûì îáðàçîì?
     Êàêóþ èíôîðìàöèþ ìû áóäåì èñïîëüçîâàòü? Åñëè ìû çíà-
åì, íà êàêèõ äîëæíîñòÿõ ìîæåò ðàáîòàòü êàæäûé ÷åëîâåê, òî
íà÷àëüíûå äàííûå ìîæíî çàäàòü â âèäå êâàäðàòíîé ìàòðèöû Ñ,
èìåþùåé ðàçìåðíîñòü (ï½ï). Ýëåìåíòû ýòîé ìàòðèöû — íóëè è
åäèíèöû.
        1 , если i-й человек может работать на j-й должности;
c ij = 
        0 , если i-й человек не может работать на j-й должности.
     Ñóùåñòâóåò ëè òàêîå ðàñïðåäåëåíèå ðàáîò, ÷òîáû êàæäûé
÷åëîâåê ñïðàâëÿëñÿ ñ ðàáîòîé íà ñâîåé äîëæíîñòè? Êàê ëó÷øå
íàçíà÷èòü ëþäåé íà ðàáîòû?
     Íàçíà÷åíèå ÷åëîâåêà íà äîëæíîñòü ìîæíî ðàññìàòðèâàòü,
êàê âûáîð îïðåäåëåííîãî ýëåìåíòà ìàòðèöû Ñ. Êàæäûé ÷åëîâåê
äîëæåí ðàáîòàòü òîëüêî íà îäíîé äîëæíîñòè, è íà êàæäîé äîëæ-
íîñòè äîëæåí ðàáîòàòü òîëüêî îäèí ÷åëîâåê. Ïîýòîìó â êàæäîé
ñòðî÷êå è â êàæäîì ñòîëáöå ìàòðèöû Ñ äîëæíî áûòü âûáðàíî
ðîâíî ïî îäíîé åäèíèöå. Ïîëó÷èëè ñëåäóþùóþ ìàòåìàòè÷åñêóþ
çàäà÷ó:
     Â ìàòðèöå Ñ(n½n) âûáðàòü n ýëåìåíòîâ, ñòîÿùèõ â ðàçíûõ
ñòðîêàõ è ðàçíûõ ñòîëáöàõ, òàê, ÷òîáû èõ ñóììà áûëà ìàêñè-
ìàëüíîé 3 .
     Â èäåàëå ýòà ñóììà äîëæíà áûòü ðàâíà n. Ýòî âîçìîæíî â òîì
ñëó÷àå, åñëè äëÿ êàæäîãî ê (1 ≤ ê ≤n) è ëþáûõ ê äîëæíîñòåé,
íàéäåòñÿ íå ìåíåå ê ÷åëîâåê, êàæäûé èç êîòîðûõ ìîæåò ñïðà-
âèòüñÿ õîòÿ áû ñ îäíîé èç ýòèõ ê äîëæíîñòåé (òåîðåìà Õîëëà).
     Ðàññìîòðèì äðóãèå ñïîñîáû ðàññìîòðåíèÿ ýòîé çàäà÷è. Çà-
äàäèì ðàñïðåäåëåíèå ïî äîëæíîñòÿì ñ ïîìîùüþ ìàòðèöû Õ(n½n),
ñîñòîÿùåé èç íóëåé è åäèíèö.
          1 , если i-й человек будет назначен на j-ю должность;
  x ij = 
          0 , если i-й человек не будет назначен на j-ю должность
__________________


       Ïðè äðóãîé ïðàêòè÷åñêîé ñèòóàöèè ýòó ñóììó íàäî ìèíèìèçè-
        3

ðîâàòü.

                                42

Страницы