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

                                             n   n
÷åíèÿìè, òî èùåì ìàêñèìóì ôóíêöèè L =       ∑∑ xij cij , åñëè æå
                                            i =1 j =1
èçäåðæêè — ìèíèìóì.
      Äðóãîé ïðèìåð. Íàì íåîáõîäèìî ðàñïðåäåëèòü çàêàçû ìåæ-
äó ôèðìàìè. Åñëè cij ïëàòà, êîòîðóþ ìû ïëàòèì ôèðìå i çà âû-
ïîëíåíèå çàêàçà j, òîãäà ôóíêöèþ çàòðàò L íàäî ñâîäèòü ê ìèíè-
ìóìó. Çäåñü ïðåäïîëàãàåòñÿ, ÷òî êàæäàÿ ôèðìà âûïîëíÿåò çàêàç
êà÷åñòâåííî. Åñëè æå cij — öåíà, êîòîðóþ ïëàòèò íàì ôèðìà i çà
ïîëó÷åíèå çàêàçà j, òî ôóíêöèþ L íåîáõîäèìî ìàêñèìèçèðîâàòü.
      Ïîëó÷åííàÿ çàäà÷à ÿâëÿåòñÿ òàêæå çàäà÷åé ëèíåéíîãî ïðî-
ãðàììèðîâàíèÿ. Êàê è âñÿêóþ çàäà÷ó ëèíåéíîãî ïðîãðàììèðîâà-
íèÿ, åå ìîæíî ðåøèòü ñèìïëåêñ-ìåòîäîì.
      Òàêèì îáðàçîì, ó íàñ åñòü äâå ýêâèâàëåíòíûå ôîðìóëèðîâ-
êè çàäà÷è î íàçíà÷åíèÿõ.
      1) Â ìàòðèöå Ñ(n½n) âûáðàòü n ýëåìåíòîâ, ñòîÿùèõ â ðàçíûõ
ñòðîêàõ è ðàçíûõ ñòîëáöàõ, òàê, ÷òîáû èõ ñóììà áûëà ìàêñèìàëü-
íîé (ìèíèìàëüíîé).
      2) Ñðåäè âñåõ ìàòðèö X, óäîâëåòâîðÿþùèõ óñëîâèÿì (1), (2),
(3), íàéòè òàêóþ, äëÿ êîòîðîé ñóììà (4) èìååò íàèáîëüøåå (íàè-
ìåíüøåå) çíà÷åíèå.
      Ìû ðàññìîòðèì àëãîðèòì, íàçâàííûé âåíãåðñêèì.
      Â îñíîâå âåíãåðñêîãî àëãîðèòìà ëåæèò ëåììà îá îïòèìàëü-
íîñòè, ïîçâîëÿþùàÿ â ðÿäå ñëó÷àåâ ãàðàíòèðîâàòü îïòèìàëüíîñòü
íàéäåííîãî ðåøåíèÿ, è ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ ìàòðèöû
ñòîèìîñòåé, ïîçâîëÿþùèå âîñïîëüçîâàòüñÿ ëåììîé.
      Ëåììà îá îïòèìàëüíîñòè. Åñëè â ìàòðèöå Ñ(n½n) íåò îòðè-
öàòåëüíûõ ýëåìåíòîâ è óäàëîñü âûáðàòü n íóëåé, ñòîÿùèõ â ðàçíûõ
ñòðîêàõ è ðàçíûõ ñòîëáöàõ, òî ýòîò âûáîð îïòèìàëåí â çàäà÷å íà
ìèíèìóì.
      Äîêàçàòåëüñòâî ëåììû î÷åâèäíî.  ñàìîì äåëå, ñóììà ëþ-
áûõ ýëåìåíòîâ ìàòðèöû íåîòðèöàòåëüíà. Ñóììà âûáðàííûõ íàìè
÷èñåë ðàâíà 0, òàê êàê âñå âûáðàííûå ÷èñëà ðàâíû 0. Ïîýòîìó
íåëüçÿ âûáðàòü ýëåìåíòû ñ ìåíüøåé ñóììîé. Íàø âûáîð îïòè-
ìàëåí.
      Ëåììà ïðàâèëüíà, íî íà ïåðâûé âçãëÿä áåñïîëåçíà, òàê êàê â
ìàòðèöå ìîæåò áûòü ìàëî èëè ñîâñåì íå áûòü íóëåâûõ ýëåìåíòîâ.
      Ïðèìåíåíèå ëåììû îáåñïå÷èâàåòñÿ âîçìîæíîñòüþ ïðåîáðà-
çîâûâàòü ìàòðèöó, ñîçäàâàÿ â íóæíûõ ìåñòàõ íóëåâûå ýëåìåíòû.


                              44