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

     Êàæäûé ÷åëîâåê äîëæåí ðàáîòàòü òîëüêî íà îäíîé äîëæíî-
ñòè, è íà êàæäîé äîëæíîñòè äîëæåí ðàáîòàòü òîëüêî îäèí ÷åëî-
âåê. Ïîýòîìó â êàæäîé ñòðî÷êå è â êàæäîì ñòîëáöå ìàòðèöû X
äîëæíî áûòü ðîâíî ïî îäíîé åäèíèöå, à îñòàëüíûå ýëåìåíòû
ðàâíû íóëþ. Ñëåäîâàòåëüíî, ìàòðèöà Õ äîëæíà óäîâëåòâîðÿòü
ñëåäóþùèì óñëîâèÿì:
                           n
                          ∑ xij =1           (j =1, 2,..., n).
                                                             .   (1)
                          i =1

                           n
                          ∑ xij = 1 (i = 1,2 ,..., n).           (2)
                          j =1
                          xij ∈ {0,1}.                           (3)
     Ðàññìîòðèì ñóììó
                                  n    n
                                 ∑ ∑ xij cij .                   (4)
                                 i =1 j =1
      Åñëè ýëåìåíòû ìàòðèöû Ñ íóëè è åäèíèöû, òî ýòà ñóììà
ðàâíà êîëè÷åñòâó ëþäåé, íàçíà÷åííûõ íà òå äîëæíîñòè, ñ êîòî-
ðûìè îíè ñïðàâÿòñÿ. Ýòó ñóììó ìû õîòèì ìàêñèìèçèðîâàòü. Âîç-
íèêëà çàäà÷à: ñðåäè âñåõ ìàòðèö X, óäîâëåòâîðÿþùèõ óñëîâèÿì
(1), (2), (3), íàéòè òàêóþ, äëÿ êîòîðîé ñóììà (4) èìååò íàè-
áîëüøåå çíà÷åíèå. Åñëè óñëîâèå (3) çàìåíèòü óñëîâèåì
                              0 ≤ xij ≤ 1,                (5)
òî âîçíèêàåò çàäà÷à ëèíåéíîãî ïðîãðàììèðîâàíèÿ, ãäå
     n   n
L = ∑∑ xij cij   — öåëåâàÿ ôóíêöèÿ, êîòîðóþ íåîáõîäèìî ìàê-
    i =1 j =1
ñèìèçèðîâàòü, óñëîâèÿ (1), (2), (5) çàäàþò ñèñòåìó ëèíåéíûõ
îãðàíè÷åíèé. Ìîæíî äîêàçàòü, ÷òî ñðåäè îïòèìàëüíûõ ðåøåíèé
ýòîé çàäà÷è îáÿçàòåëüíî åñòü öåëî÷èñëåííûå ðåøåíèÿ. Äëÿ òàêèõ
ðåøåíèé óñëîâèå (3) áóäåò âûïîëíåíî.
      Âîçìîæíû è äðóãèå ïîñòàíîâêè äàííîé çàäà÷è. Åñëè ìîæíî
îöåíèòü ýôôåêòèâíîñòü ëþáîãî íàçíà÷åíèÿ è äàòü êîëè÷åñòâåí-
íóþ îöåíêó ðàáîòû, òî ìàòðèöà Ñ ìîæåò ñîäåðæàòü ëþáûå ÷èñ-
ëà, à íå òîëüêî 0 è 1.  ýòîì ñëó÷àå cij — ðåçóëüòàò ðàáîòû i—ãî
÷åëîâåêà íà j-é äîëæíîñòè. Åñëè ýëåìåíòû ìàòðèöû Ñ ïðîèçâîëü-
íûå ÷èñëà, òî ñóììà (4) — íåêèé êðèòåðèé ýôôåêòèâíîñòè íà-
çíà÷åíèé. Åñëè ìàòðèöà Ñ çàäàåò íàøè ïðèáûëè â ñâÿçè ñ íàçíà-



                                      43