Решение задач симплексным методом

Ðåøåíèå çàäà÷ ñèìïëåêñíûì ìåòîäîì

Îãëàâëåíèå

ÂÂÅÄÅÍÈÅ 3

1. ÊÐÀÒÊÈÉ ÎÁÇÎÐ ÀËÃÎÐÈÒÌÎÂ ÐÅØÅÍÈß ÇÀÄÀ× ÄÀÍÍÎÃÎ ÒÈÏÀ 5

1.1 Ìàòåìàòè÷åñêîå ïðîãðàììèðîâàíèå 5

1.2 Òàáëè÷íûé ñèìïëåêñ - ìåòîä 6

1.3 Ìåòîä èñêóññòâåííîãî áàçèñà 7

1.4 Ìîäèôèöèðîâàííûé ñèìïëåêñ - ìåòîä 7

2.ÑÎÄÅÐÆÀÒÅËÜÍÀß ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È 9

3.ÐÀÇÐÀÁÎÒÊÀ È ÎÏÈÑÀÍÈÅ ÀËÃÎÐÈÒÌÀ ÐÅØÅÍÈß ÇÀÄÀ×È 10

3.1 Ïîñòðîåíèå ìàòåìàòè÷åñêîé ìîäåëè çàäà÷è 10

3.2 Ðåøåíèå çàäà÷è âðó÷íóþ 11

4.ÍÀÇÍÀ×ÅÍÈÅ ÏÐÎÃÐÀÌÌÛ 14

5.ÈÍÑÒÐÓÊÖÈß ÏÎËÜÇÎÂÀÒÅËÞ 15

6. ÒÅÊÑÒ ÈÑÕÎÄÍÎÃÎ ÌÎÄÓËß 17

Çàêëþ÷åíèå 29

Ñïèñîê èñïîëüçîâàííûõ èñòî÷íèêîâ 30


ÂÂÅÄÅÍÈÅ 

Ïðîíèêíîâåíèå ìàòåìàòèêè â ýêîíîìè÷åñêóþ íàóêó ñâÿçàíî ñ ïðåîäîëåíèåì çíà÷èòåëüíûõ òðóäíîñòåé. Â ýòîì îò÷àñòè áûëà "ïîâèííà" ìàòåìàòèêà, ðàçâèâàþùàÿñÿ íà ïðîòÿæåíèè íåñêîëüêèõ âåêîâ â îñíîâíîì â ñâÿçè ñ ïîòðåáíîñòÿìè ôèçèêè è òåõíèêè. Íî ãëàâíûå ïðè÷èíû ëåæàò âñå æå â ïðèðîäå ýêîíîìè÷åñêèõ ïðîöåññîâ, â ñïåöèôèêå ýêîíîìè÷åñêîé íàóêè.

Áîëüøèíñòâî îáúåêòîâ, èçó÷àåìûõ ýêîíîìè÷åñêîé íàóêîé, ìîæåò áûòü îõàðàêòåðèçîâàíî êèáåðíåòè÷åñêèì ïîíÿòèåì ñëîæíàÿ ñèñòåìà.

Íàèáîëåå ðàñïðîñòðàíåíî ïîíèìàíèå ñèñòåìû êàê ñîâîêóïíîñòè ýëåìåíòîâ, íàõîäÿùèõñÿ âî âçàèìîäåéñòâèè è îáðàçóþùèõ íåêîòîðóþ öåëîñòíîñòü, åäèíñòâî. Âàæíûì êà÷åñòâîì ëþáîé ñèñòåìû ÿâëÿåòñÿ ýìåðäæåíòíîñòü - íàëè÷èå òàêèõ ñâîéñòâ, êîòîðûå íå ïðèñóùè íè îäíîìó èç ýëåìåíòîâ, âõîäÿùèõ â ñèñòåìó. Ïîýòîìó ïðè èçó÷åíèè ñèñòåì íåäîñòàòî÷íî ïîëüçîâàòüñÿ ìåòîäîì èõ ðàñ÷ëåíåíèÿ íà ýëåìåíòû ñ ïîñëåäóþùèì èçó÷åíèåì ýòèõ ýëåìåíòîâ â îòäåëüíîñòè. Îäíà èç òðóäíîñòåé ýêîíîìè÷åñêèõ èññëåäîâàíèé - â òîì, ÷òî ïî÷òè íå ñóùåñòâóåò ýêîíîìè÷åñêèõ îáúåêòîâ, êîòîðûå ìîæíî áûëî áû ðàññìàòðèâàòü êàê îòäåëüíûå (âíåñèñòåìíûå) ýëåìåíòû.

Ñëîæíîñòü ñèñòåìû îïðåäåëÿåòñÿ êîëè÷åñòâîì âõîäÿùèõ â íåå ýëåìåíòîâ, ñâÿçÿìè ìåæäó ýòèìè ýëåìåíòàìè, à òàêæå âçàèìîîòíîøåíèÿìè ìåæäó ñèñòåìîé è ñðåäîé. Ýêîíîìèêà ñòðàíû îáëàäàåò âñåìè ïðèçíàêàìè î÷åíü ñëîæíîé ñèñòåìû. Îíà îáúåäèíÿåò îãðîìíîå ÷èñëî ýëåìåíòîâ, îòëè÷àåòñÿ ìíîãîîáðàçèåì âíóòðåííèõ ñâÿçåé è ñâÿçåé ñ äðóãèìè ñèñòåìàìè (ïðèðîäíàÿ ñðåäà, ýêîíîìèêà äðóãèõ ñòðàí è ò.ä.). Â íàðîäíîì õîçÿéñòâå âçàèìîäåéñòâóþò ïðèðîäíûå, òåõíîëîãè÷åñêèå, ñîöèàëüíûå ïðîöåññû, îáúåêòèâíûå è ñóáúåêòèâíûå ôàêòîðû.

Ñëîæíîñòü ýêîíîìèêè èíîãäà ðàññìàòðèâàëàñü êàê îáîñíîâàíèå íåâîçìîæíîñòè åå ìîäåëèðîâàíèÿ, èçó÷åíèÿ ñðåäñòâàìè ìàòåìàòèêè. Íî òàêàÿ òî÷êà çðåíèÿ â ïðèíöèïå íåâåðíà. Ìîäåëèðîâàòü ìîæíî îáúåêò ëþáîé ïðèðîäû è ëþáîé ñëîæíîñòè. È êàê ðàç ñëîæíûå îáúåêòû ïðåäñòàâëÿþò íàèáîëüøèé èíòåðåñ äëÿ ìîäåëèðîâàíèÿ; èìåííî çäåñü ìîäåëèðîâàíèå ìîæåò äàòü ðåçóëüòàòû, êîòîðûå íåëüçÿ ïîëó÷èòü äðóãèìè ñïîñîáàìè èññëåäîâàíèÿ.

Ïîòåíöèàëüíàÿ âîçìîæíîñòü ìàòåìàòè÷åñêîãî ìîäåëèðîâàíèÿ ëþáûõ ýêîíîìè÷åñêèõ îáúåêòîâ è ïðîöåññîâ íå îçíà÷àåò, ðàçóìååòñÿ, åå óñïåøíîé îñóùåñòâèìîñòè ïðè äàííîì óðîâíå ýêîíîìè÷åñêèõ è ìàòåìàòè÷åñêèõ çíàíèé, èìåþùåéñÿ êîíêðåòíîé èíôîðìàöèè è âû÷èñëèòåëüíîé òåõíèêå. È õîòÿ íåëüçÿ óêàçàòü àáñîëþòíûå ãðàíèöû ìàòåìàòè÷åñêîé ôîðìàëèçóåìîñòè ýêîíîìè÷åñêèõ ïðîáëåì, âñåãäà áóäóò ñóùåñòâîâàòü åùå íåôîðìàëèçîâàííûå ïðîáëåìû, à òàêæå ñèòóàöèè, ãäå ìàòåìàòè÷åñêîå ìîäåëèðîâàíèå íåäîñòàòî÷íî ýôôåêòèâíî.

1. ÊÐÀÒÊÈÉ ÎÁÇÎÐ ÀËÃÎÐÈÒÌÎÂ ÐÅØÅÍÈß ÇÀÄÀ× ÄÀÍÍÎÃÎ ÒÈÏÀ 1.1 Ìàòåìàòè÷åñêîå ïðîãðàììèðîâàíèå 

Ìàòåìàòè÷åñêîå ïðîãðàììèðîâàíèå çàíèìàåòñÿ èçó÷åíèå ýêñòðåìàëüíûõ çàäà÷ è ïîèñêîì ìåòîäîâ èõ ðåøåíèÿ. Çàäà÷è ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ ôîðìóëèðóþòñÿ ñëåäóþùèì îáðàçîì : íàéòè ýêñòðåìóì íåêîòîðîé ôóíêöèè ìíîãèõ ïåðåìåííûõ f ( x1, x2, ... , xn ) ïðè îãðàíè÷åíèÿõ gi ( x1, x2, ... , xn )  bi , ãäå gi - ôóíêöèÿ, îïèñûâàþùàÿ îãðàíè÷åíèÿ,  - îäèí èç ñëåäóþùèõ çíàêîâ  ,  ,  , à bi - äåéñòâèòåëüíîå ÷èñëî, i = 1, ... , m. f íàçûâàåòñÿ ôóíêöèåé öåëè ( öåëåâàÿ ôóíêöèÿ ).

Ëèíåéíîå ïðîãðàììèðîâàíèå - ýòî ðàçäåë ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ, â êîòîðîì ðàññìàòðèâàþòñÿ ìåòîäû ðåøåíèÿ ýêñòðåìàëüíûõ çàäà÷ ñ ëèíåéíûì ôóíêöèîíàëîì è ëèíåéíûìè îãðàíè÷åíèÿìè, êîòîðûì äîëæíû óäîâëåòâîðÿòü èñêîìûå ïåðåìåííûå.

Çàäà÷ó ëèíåéíîãî ïðîãðàììèðîâàíèÿ ìîæíî ñôîðìóëèðîâàòü òàê . Íàéòè max



ïðè óñëîâèè : a11 x1 + a12 x2 + . . . + a1n xn  b1 ; 

a21 x1 + a22 x2 + . . . + a2n xn  b2 ; 

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

am1 x1 + am2 x2 + . . . + amn xn  bm ; 

x1  0, x2  0, . . . , xn  0 . 

Ýòè îãðàíè÷åíèÿ íàçûâàþòñÿ óñëîâèÿìè íåîòðèöàòåëüíîñòè. Åñëè âñå îãðàíè÷åíèÿ çàäàíû â âèäå ñòðîãèõ ðàâåíñòâ, òî äàííàÿ ôîðìà íàçûâàåòñÿ êàíîíè÷åñêîé. 

Â ìàòðè÷íîé ôîðìå çàäà÷ó ëèíåéíîãî ïðîãðàììèðîâàíèÿ çàïèñûâàþò ñëåäóþùèì îáðàçîì. Íàéòè max cT x

ïðè óñëîâèè

A x  b ;

x  0 ,

ãäå À - ìàòðèöà îãðàíè÷åíèé ðàçìåðîì ( mn), b(m1) - âåêòîð-ñòîëáåö ñâîáîäíûõ ÷ëåíîâ, x(n  1) - âåêòîð ïåðåìåííûõ, ñÒ = [c1, c2, ... , cn ] - âåêòîð-ñòðîêà êîýôôèöèåíòîâ öåëåâîé ôóíêöèè.

Ðåøåíèå õ0 íàçûâàåòñÿ îïòèìàëüíûì, åñëè äëÿ íåãî âûïîëíÿåòñÿ óñëîâèå ñÒ õ0  ñÒ õ , äëÿ âñåõ õ  R(x).

Ïîñêîëüêó min f(x) ýêâèâàëåíòåí max [ - f(x) ] , òî çàäà÷ó ëèíåéíîãî ïðîãðàììèðîâàíèÿ âñåãäà ìîæíî ñâåñòè ê ýêâèâàëåíòíîé çàäà÷å ìàêñèìèçàöèè. 

Äëÿ ðåøåíèÿ çàäà÷ äàííîãî òèïà ïðèìåíÿþòñÿ ìåòîäû:

1) ãðàôè÷åñêèé;

2) òàáëè÷íûé ( ïðÿìîé, ïðîñòîé ) ñèìïëåêñ - ìåòîä;

3) ìåòîä èñêóññòâåííîãî áàçèñà;

4) ìîäèôèöèðîâàííûé ñèìïëåêñ - ìåòîä;

5) äâîéñòâåííûé ñèìïëåêñ - ìåòîä. 

1.2 Òàáëè÷íûé ñèìïëåêñ - ìåòîä 

Äëÿ åãî ïðèìåíåíèÿ íåîáõîäèìî, ÷òîáû çíàêè â îãðàíè÷åíèÿõ áûëè âèäà “ ìåíüøå ëèáî ðàâíî ”, à êîìïîíåíòû âåêòîðà b - ïîëîæèòåëüíû. 

Àëãîðèòì ðåøåíèÿ ñâîäèòñÿ ê ñëåäóþùåìó :

Ïðèâåäåíèå ñèñòåìû îãðàíè÷åíèé ê êàíîíè÷åñêîìó âèäó ïóò¸ì ââåäåíèÿ äîïîëíèòåëüíûõ ïåðåìåííûõ äëÿ ïðèâåäåíèÿ íåðàâåíñòâ ê ðàâåíñòâàì.

Åñëè â èñõîäíîé ñèñòåìå îãðàíè÷åíèé ïðèñóòñòâîâàëè çíàêè “ ðàâíî ” èëè “ áîëüøå ëèáî ðàâíî ”, òî â óêàçàííûå îãðàíè÷åíèÿ äîáàâëÿþòñÿ 

èñêóññòâåííûå ïåðåìåííûå, êîòîðûå òàê æå ââîäÿòñÿ è â öåëåâóþ ôóíêöèþ ñî çíàêàìè, îïðåäåëÿåìûìè òèïîì îïòèìóìà.

Ôîðìèðóåòñÿ ñèìïëåêñ-òàáëèöà.

Ðàññ÷èòûâàþòñÿ ñèìïëåêñ-ðàçíîñòè.

Ïðèíèìàåòñÿ ðåøåíèå îá îêîí÷àíèè ëèáî ïðîäîëæåíèè ñ÷¸òà.

Ïðè íåîáõîäèìîñòè âûïîëíÿþòñÿ èòåðàöèè.

Íà êàæäîé èòåðàöèè îïðåäåëÿåòñÿ âåêòîð, ââîäèìûé â áàçèñ, è âåêòîð, âûâîäèìûé èç áàçèñà. Òàáëèöà ïåðåñ÷èòûâàåòñÿ ïî ìåòîäó Æîðäàíà-Ãàóññà èëè êàêèì-íèáóäü äðóãèì ñïîñîáîì.

1.3 Ìåòîä èñêóññòâåííîãî áàçèñà 

Äàííûé ìåòîä ðåøåíèÿ ïðèìåíÿåòñÿ ïðè íàëè÷èè â îãðàíè÷åíèè çíàêîâ “ ðàâíî ”, “ áîëüøå ëèáî ðàâíî ”, “ ìåíüøå ëèáî ðàâíî ” è ÿâëÿåòñÿ ìîäèôèêàöèåé òàáëè÷íîãî ìåòîäà. Ðåøåíèå ñèñòåìû ïðîèçâîäèòñÿ ïóò¸ì ââîäà èñêóññòâåííûõ ïåðåìåííûõ ñî çíàêîì, çàâèñÿùèì îò òèïà îïòèìóìà, ò.å. äëÿ èñêëþ÷åíèÿ èç áàçèñà ýòèõ ïåðåìåííûõ ïîñëåäíèå ââîäÿòñÿ â öåëåâóþ ôóíêöèþ ñ áîëüøèìè îòðèöàòåëüíûìè êîýôôèöèåíòàìè  , à â çàäà÷è ìèíèìèçàöèè - ñ ïîëîæèòåëüíûìè  . Òàêèì îáðàçîì èç èñõîäíîé ïîëó÷àåòñÿ íîâàÿ  - çàäà÷à.

Åñëè â îïòèìàëüíîì ðåøåíèè  - çàäà÷è íåò èñêóññòâåííûõ ïåðåìåííûõ, ýòî ðåøåíèå åñòü îïòèìàëüíîå ðåøåíèå èñõîäíîé çàäà÷è. Åñëè æå â îïòèìàëüíîì ðåøåíèè  - çàäà÷è õîòü îäíà èç èñêóññòâåííûõ ïåðåìåííûõ áóäåò îòëè÷íà îò íóëÿ, òî ñèñòåìà îãðàíè÷åíèé èñõîäíîé çàäà÷è íåñîâìåñòíà è èñõîäíàÿ çàäà÷à íåðàçðåøèìà.

1.4 Ìîäèôèöèðîâàííûé ñèìïëåêñ - ìåòîä 

Â îñíîâó äàííîé ðàçíîâèäíîñòè ñèìïëåêñ-ìåòîäà ïîëîæåíû òàêèå îñîáåííîñòè ëèíåéíîé àëãåáðû , êîòîðûå ïîçâîëÿþò â õîäå ðåøåíèÿ çàäà÷è ðàáîòàòü ñ ÷àñòüþ ìàòðèöû îãðàíè÷åíèé. Èíîãäà ìåòîä íàçûâàþò ìåòîäîì îáðàòíîé ìàòðèöû.

Â ïðîöåññå ðàáîòû àëãîðèòìà ïðîèñõîäèò ñïîíòàííîå îáðàùåíèå ìàòðèöû îãðàíè÷åíèé ïî ÷àñòÿì, ñîîòâåòñòâóþùèì òåêóùèì áàçèñíûì âåêòîðàì. Óêàçàííàÿ ñïîñîáíîñòü äåëàåò âåñüìà ïðèâëåêàòåëüíîé ìàøèííóþ ðåàëèçàöèþ âû÷èñëåíèé âñëåäñòâèå ýêîíîìèè ïàìÿòè ïîä ïðîìåæóòî÷íûå ïåðåìåííûå è çíà÷èòåëüíîãî ñîêðàùåíèÿ âðåìåíè ñ÷¸òà. Õîðîø äëÿ ñèòóàöèé, êîãäà ÷èñëî ïåðåìåííûõ n çíà÷èòåëüíî ïðåâûøàåò ÷èñëî îãðàíè÷åíèé m.

Â öåëîì, ìåòîä îòðàæàåò òðàäèöèîííûå ÷åðòû îáùåãî ïîäõîäà ê ðåøåíèþ çàäà÷ ëèíåéíîãî ïðîãðàììèðîâàíèÿ, âêëþ÷àþùåãî â ñåáÿ êàíîíèçàöèþ óñëîâèé çàäà÷è, ðàñ÷¸ò ñèìïëåêñ-ðàçíîñòåé, ïðîâåðêó óñëîâèé îïòèìàëüíîñòè, ïðèíÿòèå ðåøåíèé î êîððåêöèè áàçèñà è èñêëþ÷åíèå Æîðäàíà-Ãàóññà.

Îñîáåííîñòè çàêëþ÷àþòñÿ â íàëè÷èè äâóõ òàáëèö - îñíîâíîé è âñïîìàãàòåëüíîé, ïîðÿäêå èõ çàïîëíåíèÿ è íåêîòîðîé ñïåöèôè÷íîñòè ðàñ÷¸òíûõ ôîðìóë.

2.ÑÎÄÅÐÆÀÒÅËÜÍÀß ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È 

Äëÿ ïðîèçâîäñòâà äâóõ âèäîâ èçäåëèé À è Â èñïîëüçóåòñÿ òðè òèïà òåõíîëîãè÷åñêîãî îáîðóäîâàíèÿ. Íà ïðîèçâîäñòâî åäèíèöû èçäåëèÿ À èä¸ò âðåìåíè, ÷àñîâ : îáîðóäîâàíèåì 1-ãî òèïà - à1 , îáîðóäîâàíèåì 2-ãî òèïà - à2 , îáîðóäîâàíèåì 3-ãî òèïà - à3 . Íà ïðîèçâîäñòâî åäèíèöû èçäåëèÿ Â èä¸ò âðåìåíè, ÷àñîâ : îáîðóäîâàíèåì 1-ãî òèïà - b1 , îáîðóäîâàíèåì 2-ãî òèïà - b2 ,, îáîðóäîâàíèåì 3-ãî òèïà - b3 . 

Íà èçãîòîâëåíèå âñåõ èçäåëèé àäìèíèñòðàöèÿ ïðåäïðèÿòèÿ ìîæåò ïðåäîñòàâèòü îáîðóäîâàíèå 1-ãî òèïà íå áîëåå, ÷åì íà t1 , îáîðóäîâàíèå 2-ãî òèïà íå áîëåå, ÷åì íà t2 , îáîðóäîâàíèå 3-ãî òèïà íå áîëåå, ÷åì íà t3 ÷àñîâ.

Ïðèáûëü îò ðåàëèçàöèè åäèíèöû ãîòîâîãî èçäåëèÿ À ñîñòàâëÿåò  ðóáëåé, à èçäåëèÿ Â -  ðóáëåé.

Ñîñòàâèòü ïëàí ïðîèçâîäñòâà èçäåëèé À è Â, îáåñïå÷èâàþùèé ìàêñèìàëüíóþ ïðèáûëü îò èõ ðåàëèçàöèè. Ðåøèòü çàäà÷ó ïðîñòûì ñèìïëåêñ-ìåòîäîì. Äàòü ãåîìåòðè÷åñêîå èñòîëêîâàíèå çàäà÷è, èñïîëüçóÿ äëÿ ýòîãî å¸ ôîðìóëèðîâêó ñ îãðàíè÷åíèÿìè-íåðàâåíñòâàìè.

à1 = 1 b1 = 5 t1 = 10  = 2 

à2 = 3 b2 = 2 t2 = 12  = 3

à3 = 2 b3 = 4 t3 = 10 

3.ÐÀÇÐÀÁÎÒÊÀ È ÎÏÈÑÀÍÈÅ ÀËÃÎÐÈÒÌÀ ÐÅØÅÍÈß ÇÀÄÀ×È 3.1 Ïîñòðîåíèå ìàòåìàòè÷åñêîé ìîäåëè çàäà÷è 



Íà ïðîèçâ-âî èçäåëèÿ À, ÷àñîâ

Íà ïðîèçâ-âî èçäåëèÿ B, ÷àñîâ

Ïðåäïð-å ïðåäîñòàâèò, ÷àñîâ

Îáîðóä-å 1ãî òèïà

1

5

10

Îáîðóä-å 2ãî òèïà

3

2

12

Îáîðóä-å 3ãî òèïà

2

4

10

Ïðèáûëü îò ðåàëèçàöèè, çà åä. èçä-ÿ

2

3



Ïîñòðîåíèå ìàòåìàòè÷åñêîé ìîäåëè îñóùåñòâëÿåòñÿ â òðè ýòàïà :

1. Îïðåäåëåíèå ïåðåìåííûõ, äëÿ êîòîðûõ áóäåò ñîñòàâëÿòüñÿ ìàòåìàòè÷åñêàÿ ìîäåëü.

Òàê êàê òðåáóåòñÿ îïðåäåëèòü ïëàí ïðîèçâîäñòâà èçäåëèé À è Â, òî ïåðåìåííûìè ìîäåëè áóäóò:

x1 - îáú¸ì ïðîèçâîäñòâà èçäåëèÿ À, â åäèíèöàõ;

x2 - îáú¸ì ïðîèçâîäñòâà èçäåëèÿ Â, â åäèíèöàõ.

2. Ôîðìèðîâàíèå öåëåâîé ôóíêöèè.

Òàê êàê ïðèáûëü îò ðåàëèçàöèè åäèíèöû ãîòîâûõ èçäåëèé À è Â èçâåñòíà, òî îáùèé äîõîä îò èõ ðåàëèçàöèè ñîñòàâëÿåò 2x1 + 3x2 ( ðóáëåé ). Îáîçíà÷èâ îáùèé äîõîä ÷åðåç F, ìîæíî äàòü ñëåäóþùóþ ìàòåìàòè÷åñêóþ ôîðìóëèðîâêó öåëåâîé ôóíêöèè : îïðåäåëèòü äîïóñòèìûå çíà÷åíèÿ ïåðåìåííûõ x1 è x2 , ìàêñèìèçèðóþùèõ öåëåâóþ ôóíêöèþ F = 2x1 + 3x2 .

3. Ôîðìèðîâàíèå ñèñòåìû îãðàíè÷åíèé.

Ïðè îïðåäåëåíèè ïëàíà ïðîèçâîäñòâà ïðîäóêöèè äîëæíû áûòü ó÷òåíû îãðàíè÷åíèÿ íà âðåìÿ, êîòîðîå àäìèíèñòðàöèÿ ïðåäïðèÿòèÿ ñìîæåò ïðåäîñòàâèòü íà èçãîòîâëåíèÿ âñåõ èçäåëèé. Ýòî ïðèâîäèò ê ñëåäóþùèì òð¸ì îãðàíè÷åíèÿì :

x1 + 5x2  10 ; 3x1 + 2x2  12 ; 2x1 + 4x2  10 .

Òàê êàê îáú¸ìû ïðîèçâîäñòâà ïðîäóêöèè íå ìîãóò ïðèíèìàòü îòðèöàòåëüíûå çíà÷åíèÿ, òî ïîÿâëÿþòñÿ îãðàíè÷åíèÿ íåîòðèöàòåëüíîñòè :

x1  0 ; x2  0 .

Òàêèì îáðàçîì, ìàòåìàòè÷åñêàÿ ìîäåëü çàäà÷è ïðåäñòàâëåíà â âèäå : îïðåäåëèòü ïëàí x1 , x2 , îáåñïå÷èâàþùèé ìàêñèìàëüíîå çíà÷åíèå ôóíêöèè :

max F = max ( 2x1 + 3x2 ) 

ïðè íàëè÷èè îãðàíè÷åíèé :

x1 + 5x2  10 ;

3x1 + 2x2  12 ; 

2x1 + 4x2  10 .

x1  0 ; x2  0 .

3.2 Ðåøåíèå çàäà÷è âðó÷íóþ 

Òàáëè÷íûé ìåòîä åù¸ íàçûâàåòñÿ ìåòîä ïîñëåäîâàòåëüíîãî óëó÷øåíèÿ îöåíêè. Ðåøåíèå çàäà÷è îñóùåñòâëÿåòñÿ ïîýòàïíî.

1. Ïðèâåäåíèå çàäà÷è ê ôîðìå :

x1 + 5x2  10 ;

3x1 + 2x2  12 ; 

2x1 + 4x2  10 .

x1  0 ; x2  0 .

2. Êàíîíèçèðóåì ñèñòåìó îãðàíè÷åíèé :

x1 + 5x2 + x3 = 10 ;

3x1 + 2x2 + x4 = 12 ; 

2x1 + 4x2 + x5 = 10 .

x1  0 ; x2  0 .

A1 A2 A3 A4 A5 A0

3. Çàïîëíÿåòñÿ èñõîäíàÿ ñèìïëåêñ-òàáëèöà è ðàññ÷èòûâàþòñÿ ñèìïëåêñ-ðàçíîñòè ïî ôîðìóëàì :

0 = - òåêóùåå çíà÷åíèå öåëåâîé ôóíêöèè





C

2

3

0

0

0

Á

Cá

A0

A1

A2

A3

A4

A5

A3

0

10

1

5

1

0

0

A4

0

12

3

2

0

1

0

A5

0

10

2

4

0

0

1





0

-2

-3

0

0

0

i = - ðàñ÷¸ò ñèìïëåêñ-ðàçíîñòåé, ãäå j = 1..6 .

Òàê êàê ïðè ðåøåíèè çàäà÷è íà max íå âñå ñèìïëåêñ-ðàçíîñòè ïîëîæèòåëüíûå, òî îïòèìàëüíîå ðåøåíèå ìîæíî óëó÷øèòü.

4. Îïðåäåëÿåì íàïðàâëÿþùèé ñòîëáåö j*. Äëÿ çàäà÷è íà max îí îïðåäåëÿåòñÿ ìèíèìàëüíîé îòðèöàòåëüíîé ñèìïëåêñ-ðàçíîñòüþ. Â äàííîì ñëó÷àå ýòî âåêòîð À2 

5. Âåêòîð i*, êîòîðûé íóæíî âûâåñòè èç áàçèñà, îïðåäåëÿåòñÿ ïî îòíîøåíèþ :

min ïðè ài j > 0

Â äàííîì ñëó÷àå ñíà÷àëà ýòî À3 .

5. Çàïîëíÿåòñÿ íîâàÿ ñèìïëåêñ-òàáëèöà ïî èñêëþ÷åíþ Æîðäàíà - Ãàóññà :

à). íàïðàâëÿþùóþ ñòðîêó i* äåëèì íà íàïðàâëÿþùèé ýëåìåíò : 

a i j = a i j / a i j , ãäå j = 1..6

á). ïðåîáðàçîâàíèå âñåé îñòàâøåéñÿ ÷àñòè ìàòðèöû :

a ij = aij - a i j  aij , ãäå i  i* , j  j* 





C

2

3

0

0

0

Á

Cá

A0

A1

A2

A3

A4

A5

A2

3

2

1/5

1

1/5

0

0

A4

0

8

13/5

0

-2/5

1

0

A5

0

2

6/5

0

-4/5

0

1





6

-7/5

0

3/5

0

0

Â ðåçóëüòàòå ïðåîáðàçîâàíèé ïîëó÷àåì íîâóþ ñèìïëåêñ-òàáëèöó : 

Ïîâòîðÿÿ ïóíêòû 3 - 5, ïîëó÷èì ñëåäóþùèå òàáëèöû :





C

2

3

0

0

0

Á

Cá

A0

A1

A2

A3

A4

A5

A2

3

5/3

0

1

1/3

0

-1/6

A4

0

11/3

0

0

4/3

1

-13/6

A1

2

5/3

1

0

-2/3

0

5/6





8 1/3

0

0

-1/3

0

7/6









































































































C

2

3

0

0

0

Á

Cá

A0

A1

A2

A3

A4

A5

A2

3

3/4

0

1

0

-1/4

3/8

A3

0

11/4

0

0

1

3/4

-13/8

A1

2

7/2

1

0

0

1/2

-1/4





9 1/4

0

0

0

1/4

5/8

Òàê êàê âñå ñèìïëåêñ-ðàçíîñòè ïîëîæèòåëüíû, òî îïòèìàëüíîå ðåøåíèå íàéäåíî : 

X = ( 7/2 , 3/4 , 11/4 , 0 , 0 ) ( åäèíèö )

max F = 9 1/4 ( ðóáëåé ) 

4.ÍÀÇÍÀ×ÅÍÈÅ ÏÐÎÃÐÀÌÌÛ 

Ïðîãðàììà ïðåäóñìîòðåíà äëÿ ðåøåíèÿ ñèñòåì ëèíåéíûõ íåðàâåíñòâ òàáëè÷íûì ìåòîäîì, à òàê æå äëÿ ïîïûòêè îïòèìèçàöèè ðàçëè÷íûõ ýêîíîìè÷åñêèõ, ñîöèàëüíûõ è ò. ä. ïðîáëåì.

Ìåòîä, îïèñàííûé â ïðîãðàììå, ìîæåò ïðèìåíÿòüñÿ íà ãîñóäàðñòâåííûõ è ÷àñòíûõ ïðåäïðèÿòèÿõ äëÿ óëó÷øåíèÿ ýôôåêòèâíîñòè ïðîèçâîäñòâà.


5.ÈÍÑÒÐÓÊÖÈß ÏÎËÜÇÎÂÀÒÅËÞ 

Çàäàíèå óñëîâèé

Âñå óñëîâèÿ çàäàþòñÿ â êîëîíêå “A” ïåðâîãî ëèñòà(ïðîãðàììà ðåçóëüòàò ïîìåùàåò â ëèñò 2)

Â òðåòüåé ñòðîêå(”A3″) íåîáõîäèìî çàïèñàòü öåëåûóþ ôóíêöèþ íà ìèíèìóì èëè ìàêñèìóì(min èëè max ïîñëå =) íàïðèìåð:

3×1+2×2+4×3+2×4=min

Â 5 ñòðîêå íåîáõîäèìî çàïèñàòü êîëè÷åñòâî çíàêîâ â äðîáíîé ÷àñòè ÷èñåë(èëè íè÷åãî òî åñòü ïóñòî èëè ïðîáåë(û) ) 

íà÷èíàÿ ñ 9 ñòðîêè çàïèñûâàþòñÿ îãðàíè÷åíèÿ ïî îäíîé ñòðîêå íà êàæäîå îãðàíè÷åíèe. Hàïðèìåð:

6×2+6×3+4×4=60
2×1+4×2+8×3+8×4<=80
4×1+4×2+12×4>=20
2×1+6×2+2×3+8×4=30
(ìîæíî âûäåëèòü è çàíåñòè âñå îãðàíè÷åíèÿ íàøåãî ïðèìåðà â áóôåð è âñòàâèòü â ÿ÷åéêó “9À”, ïðîãðàììà àâòîìàòè÷åñêè ðàçìåñòèò èõ â ñòðî÷êè, ÷òî ðàñïîëàãàþòñÿ íèæå.)Ñîäåðæèìîå ïîñëåäíåé ñòðîêè îãðàíè÷åíèé(Â íàøåì ïðèìåðå A13) äîëæíî áûòü ïóñòî èëè ïðîáåë(û) Ïåðåìåííûå Xi ïî óìîë÷àíèþ ñ÷èòàåòñÿ íå îòðèöàòåëüíûìè.

Âî âñåõ, íå çàíÿòûõ óñëîâèåì çàäà÷è ÿ÷åéêàõ, ìîæíî ïèñàòü ÷òî óãîäíî. Ïîñëå ââîäà óñëîâèé çàäà÷è êëàöíèòå ïî êíîïêå, êîòîðóþ âû ïåðâóþ çàíåñëè íà ëèñò Excel.

Ïîëó÷åíèå ðåçóëüòàòà

Ðåçóëüòàò ðàáîòû ðàñïîëàãàåòñÿ íà âòîðîì ëèñòå êíèãè.

Âíà÷àëå òàì ïîìåùàåòñÿ òàáëèöà èçîáðàæàþùàÿ óñëîâèå çàäà÷è â êàíîíè÷åñêîì âèäå, à çàòåì î÷åðåäíàÿ èòåðàöèÿ. Ëþáóþ òàáëèöó(íà÷àëüíóþ èëè ïîñëå î÷åðåäíîé èòåðàöèè) ìîæíî êàê óãîäíî îôîðìèòü äëÿ ïå÷àòè è ðàñïå÷àòàòü. âñå èçìåíåíèÿ ñäåëàííûå â ýòî âðåìÿ íà ýòîì ëèñòå íèêàê íå âëèÿþò íà ñëåäóþùóþ èòåðàöèþ. Ïðè ñëåäóþùåé èòåðàöèè âòîðîé ëèñò ïîëíîñòüþ î÷èùàåòñÿ è ôîðìèðóþòñÿ ðåçóëüòàòû íîâîé èòåðàöèè.

Äëÿ ïîëó÷åíèÿ íîâîé èòåðàöèè ñëåäóåò ïåðåéòè íà ïåðâûé ëèñò(îí íàçûâàåòñÿ “Initial data” è íàæàòü êíîïêó äëÿ ïîëó÷åíèÿ ñëåäóþùåé èòåðàöèè. Åñëè ïðîìåæóòî÷íûå ðåçóëüòàòû íå íóæíû, òî ñëåäóåò ïîñëåäîâàòåëüíî íàæèìàòü íà êíîïêó ïîëó÷åíèÿ íîâîé èòåðàöèè, íå ïåðåõîäÿ íà âòîðîé ëèñò è ïåðåéòè íà íåãî òîëüêî äëÿ ïðîñìîòðà îêîí÷àòåëüíîãî ðåçóëüòàòà.

6. ÒÅÊÑÒ ÈÑÕÎÄÍÎÃÎ ÌÎÄÓËß 

Dim Ftarget As String  ’öåëåâàÿ ôóíêöèÿ target function

Dim MaxX As Integer ‘ìàêñèìàëüíûé èíäåõ Õ â öåëåâîé ôóíêöèè

Dim MaxLi As Boolean ‘true-max; False-min

Dim AmRest As Integer ‘ Êîëè÷åñòâî ñòðîê îãðàíè÷åíèé (Amount of the restrictions)

Private Type Tmy

IndX As Integer

KoefX As Double

End Type

‘Íîìåð î÷åðåäíîãî îáðàáàòûâàåìîãî ñèìâîëà â ñòðîêå

Dim Icurrent As Integer

Dim BgRight As Integer  ’Íîìåð áàéòà íà÷àëà ïðàâîé ÷àñòè îãðàíè÷åíèÿ, èíà÷å 0;

‘The Number of the byte begin right part of restriction, otherwise 0;

Dim Isx As String

Dim Rez() As Tmy

Dim NumIter As Integer ‘Íîìåð èòåðàöèè. Åñëè ðàâåí íóëþ, êàíîíè÷åñêèé âèä ñèìïëåêñ òàáëèöû

‘Number to iterations. If is a zero, canonical type simplex tables

Dim MiCiXiAi() As Double ‘Äâà ïåðâûõ ñòîëáöà ýòîãî ìàññèâà çàìåíÿþò ïåðâûé ñòîëáåö ñèìïëåêñíîé òàáëèöû.

‘Ïåðâûé ñòîëáåö, ýòî ìíîæèòåëü “Ì”, ââîäèìûé äëÿ èñêóñòâåííûõ ïåðåìåííûõ äëÿ îãðàíè÷åíèé “>” èëè “=”

‘Âòîðîé ñòîëáåö, ýòî êîýôèöèåíòû ïåðåìåííûõ â öåëåâîé ôóíêöèè

‘(íîìåðà ýòèõ ïåðåìåííûõ óêàçàíû â òðåòüåì ñòîëáöå ìàññèâà MiCiXiAi)

‘×åòâåðòûé ñòîëáåö ìàññèâà MiCiXiAi(”Alfa”), ýòî ïîñëåäíèé ñòîëáåö ñèìïëåêñíîé òàáëèöû ðàâíûé X0/Õi

‘Two first columns of this array change the first column of the simplex table.

‘First column, this multiplier “M”, introduced for illusory variables for restrictions “>” or “=”

‘Second column, this values from target function

‘Second column is values variables in target function

‘(number these variables is specified in one third column array MiCiXiAi)

‘Fourth column of the array MiCiXiAi(”Alfa”), this last column of the simplex table equal X0/Hi

Dim Tsimp() As Double   ‘ the simplex table

Dim CleaDoub() As Double

Dim CleaTMY() As Tmy

Dim Icol As Integer  ’ Êëþ÷åâîé ñòîëáåö.The Key column.

Dim Irow As Integer  ’ Êëþ÷åâàÿ ñòðîêà. The Key line.

Dim AllPlans As String    ’Âñå ïëàíû â òåêóùåé çàäà÷å. All plans in the current task.

Dim DirectCycle As Boolean ‘True-Ïðÿìîé öèêë; True-Direct cycle;

Private Sub ProcString(Strin As String, Ans() As Tmy, CalcMaxX As Boolean)

‘Âûäåëåíèå èç “Strin” ÷èñëîâûõ äàííûõ. Îäíîâðåìåííî âû÷èñëÿåì ìàõèìàëüíûé èíäåõ ïåðåìåííî Õ

‘Separation from “Strin” numeric data. Simultaneously we calculate the Largest number variable X.

Dim Awork() As Tmy

Dim VaLi As Double

Dim i As Integer  ’ index in awork

Strin = Replace(Strin, ” “, “”) ‘ Óáðàëè ëèøüíèå ïðîáåëû â öåëåâîé ôóíêöèè

Strin = Trim(Strin)

Strin = Replace(Strin, “X”, “x”) ‘Çàìåíèì âñå õ íà ìàëåíüêîå àíãëèéñêîå

Strin = Replace(Strin, “Õ”, “x”) ‘Ðóññêîå áîëüøîå íà ìàëåíüêîå àíãëèéñêîå x

Strin = Replace(Strin, “õ”, “x”) ‘Ðóññêîå ìàëåíüêîå íà ìàëåíüêîå àíãëèéñêîå x

Strin = Replace(Strin, “>=”, “>”) ‘

Strin = Replace(Strin, “<=”, “<”) ‘

BgRight = 0

i = 0

Icurrent = 1

Do While BgRight = 0

i = i + 1

ReDim Preserve Awork(i)

VaLi = ExtractDbl(Strin, Icurrent)

Awork(i).KoefX = VaLi

VaLi = ExtractDbl(Strin, Icurrent)

Awork(i).IndX = CInt(VaLi)

If CalcMaxX Then If MaxX < CInt(VaLi) Then MaxX = CInt(VaLi)

Loop

Ans = Awork

End Sub

Private Sub CommandButton1_Click()

Dim i As Integer

Dim j As Integer

Dim K As Integer

Dim Acell As String

Dim St1 As String * 1

Dim Vdbl As Double

NumIter = 0

MaxX = 0

AllPlans = “”

DirectCycle = True

CommandButton1.ForeColor = &H40C0&  ’Îðàíæåâûé

CommandButton1.Caption = “Ïðèâåñòè ê êàíîíè÷åñêîìó âèäó”

CommandButton1.Font = Bold

CommandButton1.Font.Size = 12

CommandButton1.Top = 1.5

CommandButton1.Left = 0.75

CommandButton1.Height = 24

CommandButton1.Width = 204

CommandButton2.ForeColor = &H8000&  ’Çåëåíûé

CommandButton2.Font = Bold

CommandButton2.Font.Size = 12

CommandButton2.Top = 1.5

CommandButton2.Left = 204

CommandButton2.Height = 24

CommandButton2.Width = 186

MiCiXiAi = CleaDoub

Rez = CleaTMY

Tsimp = CleaDoub

CommandButton2.Visible = False

Sheets(2).Name = “Ïóñòî”

Sheets(2).Tab.ColorIndex = 6

‘Ñêðîåì âñå ëèñòû êðîìå ïåðâîãî. Ïåðâûé ëèñò ïåðåèìåíóåì â èñõîäíûå äàííûå.

‘We shall Hide all sheets except the first. The First sheet shall name “Initial data”.

‘For i = 3 To Sheets.Count

‘    Sheets(i).Visible = False

‘   Sheets(i).Visible = True

‘Next i

Sheets(1).Name = “Initial data”

‘îïðåäåëåíèå êîëè÷åñòâî ñòðîê ñ îãðàíè÷åíèÿìè

‘âû÷èñëåíèå ìàêñèìàëüíîãî èíäåõà ïåðåìåííîé Õ (çàïèñ³âàåì â MaxX).

‘Determination amount lines with restrictions

‘calculation the largest number variable X (record in MaxX).

Ftarget = Range(”A3″).Value

ProcString Ftarget, Rez, True

i = i

Isx = Trim(Range(”A9″).Value)

Do While Isx <> “”

ProcString Isx, Rez, True    ’if True, then calculate MaxX

i = i + 1

Acell = “A” & CStr(i + 

Isx = Trim(Range(Acell).Value)

Loop

AmRest = i - 1

‘Ïîëó÷åíèå çíà÷åíèé öåëåâîé ôóíêöèè â ìàññèâå Rez

‘Reception of importances of the target function in array Rez

Ftarget = Range(”A3″).Value

ProcString Ftarget, Rez, False

i = InStr(Ftarget, “=”)

If i = 0 Then

MsgBox (”Â öåëåâîé ôóíêöèè íåò çíàêà = “)

End

End If

If Mid(Ftarget, i + 1, 3) = “min” Then

MaxLi = False

ElseIf Mid(Ftarget, i + 1, 3) = “max” Then

MaxLi = True

Else

MsgBox (”Â öåëåâîé ôóíêöèè íåò íè ‘max’ íè ‘min’ “)

End

End If

‘ Çàïèñü çíà÷åíèé öåëåâîé ôóíêöèè â ñèìïëåêñ òàáëèöó

‘We write values of the target function in simplex table

ReDim Preserve Tsimp(AmRest + 3, MaxX)

ReDim Preserve MiCiXiAi(AmRest, 4)

For i = 1 To UBound(Rez)

j = Rez(i).IndX

Tsimp(0, j) = Rez(i).KoefX

Next

‘Ïîëó÷åíèå çíà÷åíèé óñëîâèé â ìàññèâå Rez è çàïèñü èõ çíà÷åíèÿ  â ñèìïëåêñ òàáëèöó

‘Reception of importances of the conditions in array Rez and record of their values in simplex table

For K = 1 To AmRest

Acell = “A” & CStr(K + 

Isx = Range(Acell).Value

ProcString Isx, Rez, False

For i = 1 To UBound(Rez)

j = Rez(i).IndX

Tsimp(K, j) = Rez(i).KoefX

Next i

Tsimp(K, 0) = Mid(Isx, BgRight)  ’Ïðàâàÿ ÷àñòü îãðàíè÷åíèÿ. Right part of restriction.

St1 = Mid(Isx, BgRight - 1, 1)

‘ Åñëè ñâîáîäíûé ÷ëåí îòðèöàòåëåí, òî ñëåäóåò  èçìåíèòü âñå çíà÷åíèÿ íà ëèíèè “K” â ïðîòèâîïîëîæíîì çíà÷åíèè.

‘  If free member negative, that follows to change all importances on lines “K” in opposite importance

If Tsimp(K, 0) < 0 Then

For i = 0 To AmRest

Tsimp(K, i) = -Tsimp(K, i)

Next i

If St1 = “>” Then

St1 = “<”

ElseIf St1 = “<” Then

St1 = “>”

End If

End If

If St1 = “>” Then ‘ Åñëè áîëüøå äîáàâèì 2 èñêóñòâåííûõ íåèçâåñòíûõ

MaxX = MaxX + 2

ReDim Preserve Tsimp(AmRest + 3, MaxX)

Tsimp(K, MaxX - 1) = -1

Else          ’Îãðàíè÷åíèå íà ðàâíî èëè ìåíüøå

MaxX = MaxX + 1

ReDim Preserve Tsimp(AmRest + 3, MaxX)

End If

Tsimp(K, MaxX) = 1

If MaxLi And (St1 = “>” Or St1 = “=”) Then    ’ Åñëè ìàõèìóì, â öåëåâóþ ôóíêöèþ äîáàâëÿåì -Mxi, èíà÷å +Mxi

Tsimp(AmRest + 3, MaxX) = -1               ‘ äëÿ > èëè =

ElseIf (Not MaxLi) And (St1 = “>” Or St1 = “=”) Then

Tsimp(AmRest + 3, MaxX) = 1

End If

MiCiXiAi(K, 1) = Tsimp(AmRest + 3, MaxX)

MiCiXiAi(K, 3) = MaxX

Next K

‘ Âû÷èñëåíèå îöåíêè

For j = 0 To MaxX

Vdbl = 0

For i = 1 To AmRest

Vdbl = Vdbl + MiCiXiAi(i, 1) * Tsimp(i, j)

Next i

Tsimp(AmRest + 1, j) = Vdbl - Tsimp(AmRest + 3, j)

Tsimp(AmRest + 2, j) = -Tsimp(0, j)

Next j

FRowCol

If Cycle() Then

MsgBox (”Íåèçâåñòíàÿ îøèáêà”)

End If

If Icol > 0 And Irow > 0 Then

LookResult “Êàíîíè÷åñêàÿ òàáëèöà”, 31

ElseIf Icol > 0 And Irow <= 0 Then

LookResult “Ôóíêöèÿ íå îãðàíè÷åíà”, 28

Else

LookResult “Èòåðàöèÿ íåâîçìîæíà”, 3

End If

End Sub

Private Sub LookResult(Sname As String, Fcolor As Integer)

‘Sheets(2).Tab.ColorIndex = 4

‘ Fcolor=  4-çåëåíûé, 3-Êðàñíûé, 37-Ñåðîñèíèé, 6-Æåëòûé

‘ Íà âòîðîì ëèñòå íà÷èíàÿ ñ ÿ÷åéêè A11 ïîñòðîèì ñèìïëåêñ òàáëèöó

‘ Âíà÷àëå ñäåëàåì ðàìêó

‘CreFrame(Vtop As Integer, Vleft As Integer, Vbottom As Integer, Vright As Integer)

Dim i As Integer, j As Integer

Dim Stk As String

Dim Sround As String

Sheets(2).Name = Sname

Sheets(2).Tab.ColorIndex = Fcolor

Sheets(2).Range(”a:iv”).Clear

CreFrame 11, 4, 11, MaxX + 3

CreFrame 12, 1, 12, MaxX + 4

CreFrame 12, 1, 12, 2

CreFrame 12, 4, 12, MaxX + 3

CreFrame 13, 1, 12 + AmRest, MaxX + 4

CreFrame 13, 4, 12 + AmRest, MaxX + 3

CreFrame 13, 3, 12 + AmRest, 3

CreFrame 13 + AmRest, 3, 13 + AmRest, MaxX + 4

CreFrame 13 + AmRest, 4, 13 + AmRest, MaxX + 3

CreFrame 14 + AmRest, 3, 14 + AmRest, MaxX + 4

CreFrame 14 + AmRest, 4, 14 + AmRest, MaxX + 3

‘Çàïîëíåíèå øàïêè ñèìïëåêñíîé òàáëèöû

‘Filling the hat of the simplex table

For i = 0 To MaxX

Sheets(2).Cells(12, i + 3).Value = “X” + CStr(i)

Next i

If MaxLi Then Sheets(2).Cells(11, 3).Value = “F(Max)” Else Sheets(2).Cells(11, 3).Value = “F(Min)”

Sheets(2).Cells(12, 1).Value = “Ñi”

Sheets(2).Cells(12, 2).Value = “P” + CStr(NumIter - 1)

Sheets(2).Cells(12, MaxX + 4).Value = “Alfa”

Sheets(2).Cells(13 + AmRest, 2).Value = “M–>”

‘Çàïîëíåíèå ñèìïëåêñíîé òàáëèöû êîýôôèöèåíòàìè öåëåâîé ôóíêöèè

‘Filling the simplex table factor to target function

For j = 1 To MaxX

If Tsimp(AmRest + 3, j) = 0 Then

Sheets(2).Cells(11, j + 3).Value = Tsimp(0, j)

Else

If Tsimp(AmRest + 3, j) > 0 Then Sheets(2).Cells(11, j + 3).Value = ”  M” Else Sheets(2).Cells(11, j + 3).Value = ” -M”

End If

Next j

‘Ôîðìèðîâàíèå ïåðâîé, âòîðîé è ïîñëåäíåé êîëîíîê ñèìïëåêñíîé òàáëèöû

‘Shaping first, second and last columnû of the simplex table

For i = 1 To AmRest

If MiCiXiAi(i, 1) = 0 Then

Sheets(2).Cells(12 + i, 1).Value = MiCiXiAi(i, 2)

ElseIf MiCiXiAi(i, 1) > 0 Then

Sheets(2).Cells(12 + i, 1).Value = ”  M”

Else

Sheets(2).Cells(12 + i, 1).Value = ” -M”

End If

Sheets(2).Cells(12 + i, 2).Value = MiCiXiAi(i, 3)

Sheets(2).Cells(12 + i, MaxX + 4).Value = MiCiXiAi(i, 4)

Next i

‘Çàïîëíåíèå ñèìïëåêñíîé òàáëèöû êîýôèöèåíòàìè îãðàíè÷åíèé

‘Filling the simplex table koefficient restrictions

For i = 1 To AmRest + 2

For j = 0 To MaxX

Sheets(2).Cells(12 + i, j + 3).Value = Tsimp(i, j)

Next j

Next i

If Icol > 0 Then

‘ColourFrame(Vtop, Vleft, Vbottom, Vright, Vcolour=34)

ColourFrame 11, Icol + 3, AmRest + 14, Icol + 3, 34

End If

If Irow > 0 Then

ColourFrame Irow + 12, 2, Irow + 12, MaxX + 4, 34

End If

‘Èíôîðìàöèÿ îá èòåðàöèè èëè êàíîíè÷åñêîé òàáëèöå

‘Information on iterations or canonical table

If Fcolor = 31 Or Fcolor = 3 Then

Stk = “Íà÷àëüíàÿ ñèìïëåêñ òàáëèöà çàäà÷è íà ”

Stk = Stk & IIf(MaxLi, “ìàêñèìóì”, “ìèíèìóì”) & “, ïðèâåäåííîé ê êàíîíè÷åñêîìó âèäó.”

With Sheets(2).Range(”A1″)

.Font.FontStyle = “Bold”

.Value = Stk

End With

Stk = IIf(Fcolor = 31, “Âîçìîæíî óëó÷øåíèå ïëàíà.”, “Èòåðàöèÿ íåâîçìîæíà(Âèäèìî ïðîòåðîðå÷èâûå óñëîâèÿ).”)

Sheets(2).Range(”A2″).Value = Stk

Stk = “Ðàçðåøàþùèé ñòîëáåö îïðåäåëÿåòñÿ ïî äâóì ïîñëåäíèì ñòðîêàì òàáëèöû.”

Sheets(2).Range(”A3″).Value = Stk

Stk = “Â ïåðåñå÷åíèè êîëîíîê Õ0-Õ” & CStr(MaxX)

Stk = Stk & IIf(MaxLi, “(âûáèðàåòñÿ ìàêñèìàëüíîå ïî ìîäóëþ îòðèöàòåëüíîå ÷èñëî).”, “(âûáèðàåòñÿ ìàêñèìàëüíîå ïîëîæèòåëüíîå ÷èñëî).”)

Sheets(2).Range(”A4″).Value = Stk

Stk = “Ñíà÷àëà ïðîñìàòðèâàåòñÿ ñòðîêà ïîìå÷åííàÿ çíàêîì “”M–>”" ”

Sheets(2).Range(”A5″).Value = Stk

Stk = ” è åñëè â íåé íåò ” & IIf(MaxLi, “îòðèöàòåëüíûõ”, “ïîëîæèòåëüíûõ”) & “÷èñåë, ïðîñìàòðèâàåòñÿ ïîñëåäíÿÿ ñòðîêà.”

Sheets(2).Range(”A6″).Value = Stk

Stk = “Åñëè ðàçðåøàþùèé ñòîëáåö íå íàøëè, òî â òàáëèöå ïðåäñòàâëåí îïòèìàëüíûé ïëàí.”

Sheets(2).Range(”A7″).Value = Stk

Stk = “Ðàçðåøàþùàÿ ñòðîêà îïðåäåëÿåòñÿ ïî ìèíèìàëüíîìó íå îòðèöàòåëüíîìó îòíîøåíèþ ”

Sheets(2).Range(”A8″).Value = Stk

Stk = “êîýôôèöèåíòîâ ñòîëáöà Õ0 è ðàçðåøàþùåãî ñòîëáöà(÷òî ïðåäñòàâëåíî â ñòîëáöå Alfa).”

Sheets(2).Range(”A9″).Value = Stk

ElseIf Fcolor = 50 Then

Sheets(2).Range(”A1:A10″).ClearContents

Stk = “Ïîñëå èòåðàöèè  ¹” & CStr(NumIter - 1) & “(âîçìîæíî óëó÷øåíèå ïëàíà) ”

With Sheets(2).Range(”A6″)

.Font.FontStyle = “Bold”

.Value = Stk

End With

i = IIf(Tsimp(AmRest + 1, Icol) = 0, 1, 2)

Stk = “Òàê êàê â ” & IIf(i = 1, “ïîñëåäíåé”, “ïðåäïîñëåäíåé”) & “ñòðîêå(íà÷èíàÿ ñ êîëîíêè Õ1)”

Sheets(2).Range(”A7″) = Stk

Stk = IIf(MaxLi, “(èìååòñÿ ìàêñèìàëüíîå ïî ìîäóëþ îòðèöàòåëüíîå ÷èñëî).”, “(èìååòñÿ ìàêñèìàëüíîå ïîëîæèòåëüíîå ÷èñëî).”)

Sheets(2).Range(”A8″) = Stk

Stk = “À â ñòîëáöå “”Alfa”" èìååòñÿ íå îòðèöàòåëüíîå ÷èñëî(âûáðàíî ìèíèìàëüíîå)”

Sheets(2).Range(”A9″) = Stk

ElseIf Fcolor = 37 Then

Stk = “Ïîñëå èòåðàöèè  ¹” & CStr(NumIter - 1) & ” ïîëó÷èëè îïòèìàëüíûé ïëàí. ”

j = IIf(Trim(CStr(Sheets(1).Range(”A5″).Value)) <> “”, CInt(Sheets(1).Range(”A5″).Value), -1) ‘j=-1 Without truncation

With Sheets(2).Range(”A5″)

.Font.FontStyle = “Bold”

.Value = Stk

End With

Sround = IIf(j = -1, CStr(Tsimp(AmRest + 2, 0)), CStr(Round(Tsimp(AmRest + 2, 0), j)))

Stk = “Äëÿ ôóíêöèè ” & Ftarget & ” ðåçóëüòàò ðàâíûé ” & Sround

Sheets(2).Range(”A6″).Value = Stk

Stk = “Äîñòèãàåòñÿ ïðè ”

For i = 1 To AmRest

If MiCiXiAi(i, 2) <> 0 Then

Sround = IIf(j = -1, CStr(Tsimp(i, 0)), CStr(Round(Tsimp(i, 0), j)))

Stk = Stk & “X” & CStr(MiCiXiAi(i, 3)) & “=” & Sround & “;”

End If

Next i

Sheets(2).Range(”A7″).Value = Stk

Stk = “Íîìåðà ïåðåìåííûõ Õ è èõ çíà÷åíèÿ íàõîäÿòñÿ, ñîîòâåòñòâåííî, âî âòîðîé è òðåòüåé êîëîíêàõ ñèìïëåêñ òàáëèöû”

Sheets(2).Range(”A8″).Value = Stk

Stk = “Îïòèìàëüíûé ïëàí íàõîäèòñÿ â ïåðâîé ÿ÷åéêå ïîñëåäíåé ñòðîêè ñèìïëåêñ òàáëèöû”

Sheets(2).Range(”A9″).Value = Stk

End If

‘Îêðóãëåíèå Truncation

‘Êîëè÷åñòâî çíàêîâ â äðîáíîé ÷àñòè â ñèìâîëüíîì âèäå

‘Amount sign in fractional part in symbol type

If Trim(CStr(Sheets(1).Range(”A5″).Value)) <> “” Then

j = CInt(Sheets(1).Range(”A5″).Value)

Sround = “0.”

For i = 1 To j

Sround = Sround & “0″

Next i

Stk = “C13:” & R1C1_to_A1(AmRest + 12, MaxX + 3)

Sheets(2).Range(Stk).NumberFormat = Sround

Stk = R1C1_to_A1(AmRest + 14, 3)

Sheets(2).Range(Stk).NumberFormat = Sround

End If

‘Viewing Canonical type

End Sub

Function ExtractDbl(Stk As String, ByVal iBg As Integer) As Double

‘ïîèñê íîìåðà íåèçâåñòíîãî xi(òî åñòü âû÷èñëåíèå i)

‘ íîìåð i íà÷èíàåòñÿ îò ñèìâîëà ñ íîìåðîì iBg(âêëþ÷èòåëüíî) è ïðîäîëæàåòñÿ äî îäíîãî èç ñèìâîëîâ: +, -, =, >, <

‘Searching for of the number unknown xi(that is to say calculation i).

‘Number i begins from symbol with number iBg(inclusive) and lasts before one of the symbol: +, -, =, >, <

Dim SimIbg As String * 1

Dim i As Integer

Dim St1 As String * 1

For i = iBg To Len(Stk)

St1 = Mid(Stk, i, 1)

If i = iBg Then SimIbg = St1

If St1 = “x” Then

Icurrent = i + 1

Exit For

ElseIf (St1 = “+” Or St1 = “-”) And i <> iBg Then

Icurrent = i

Exit For

ElseIf St1 = “=” Or St1 = “>” Or St1 = “<” Then

Icurrent = i + 1

BgRight = i + 1

Exit For

End If

Next i

If i > Len(Stk) Then

MsgBox (”osibka in “”" & Stk & “”"”)

End

End If

If iBg = i Then

ExtractDbl = 1

ElseIf (i - iBg) = 1 And (SimIbg = “+” Or SimIbg = “-”) Then

If SimIbg = “+” Then ExtractDbl = 1 Else ExtractDbl = -1

Else

ExtractDbl = CDbl(Mid(Stk, iBg, i - iBg))

End If

End Function

‘Ïðîöåäóðà CreFrame îáðàìëÿåò îáëàñòü ëèñòà çàäàííóþ êîðäèíàòàìè

‘âåðõíåãî ëåâîãî óãëà è êîîðäèíàòàìè íèæíåãî ïðàâîãî óãëà

‘ Procedure CreFrame does frame of the area of the sheet

‘given by coordinates of the upper left corner and coordinates of the right lower corner

Sub CreFrame(Vtop As Integer, Vleft As Integer, Vbottom As Integer, Vright As Integer)

Dim Stk As String

Stk = R1C1_to_A1(Vtop, Vleft) & “:” & R1C1_to_A1(Vbottom, Vright)

With Sheets(2).Range(Stk)

.Borders(xlEdgeLeft).Weight = xlThick

.Borders(xlEdgeRight).Weight = xlThick

.Borders(xlEdgeTop).Weight = xlThick

.Borders(xlEdgeBottom).Weight = xlThick

.Borders(xlInsideVertical).Weight = xlThin

.Borders(xlInsideHorizontal).Weight = xlThin

End With

End Sub

‘Ïðîöåäóðà ColourFrame çàïîëíÿåò öâåòîì îáëàñòü ëèñòà çàäàííîãî êîîðäèíàòàìè

‘âåðõíåãî ëåâîãî óãëà è êîîðäèíàòàìè ïðàâîãî íèæíåãî óãëà

‘ The Procedure ColourFrame fills the colour an area sheet given by coordinates

‘ of the upper left corner and coordinates of the right lower corner.

Sub ColourFrame(Vtop As Integer, Vleft As Integer, Vbottom As Integer, Vright As Integer, Vcolour As Integer)

Dim Stk As String

Stk = R1C1_to_A1(Vtop, Vleft) & “:” & R1C1_to_A1(Vbottom, Vright)

Sheets(2).Range(Stk).Interior.ColorIndex = Vcolour  ’Vcolour åñòü íîìåð öâåòà â öâåòîâîé ñõåìå.

‘       .ColorIndex = 34       ‘Vcolour there is number of the colour in color scheme.

End Sub

Function R1C1_to_A1(Vrow As Integer, Vcol As Integer) As String

V26 = “ABCDEFGHIJKLMNOPQRSTUVWXVZ”

Dim Stk As String

If Vcol > 26 Then

Stk = Mid(V26, Int(Vcol / 26), 1) + Mid(V26, (Vcol Mod 26), 1) + CStr(Vrow)

Else

Stk = Mid(V26, Vcol, 1) + CStr(Vrow)

End If

R1C1_to_A1 = Stk

End Function

Private Sub CalcColB()

‘Âû÷èñëåíèå êëþ÷åâîãî ñòîëáöà ïî íàéáîëüøåé îöåíêå(êîãäà min)

‘Calculation key column on the largest estimation(when min)

Dim i As Integer

Dim WrcM As Double, IrcM As Integer

Dim WrcC As Double, IrcC As Integer

WrcM = 0

WrcC = 0

For i = 1 To MaxX

If Tsimp(AmRest + 1, i) > WrcM Then

WrcM = Tsimp(AmRest + 1, i)

IrcM = i

ElseIf Tsimp(AmRest + 2, i) > WrcC And Tsimp(AmRest + 1, i) = 0 Then

WrcC = Tsimp(AmRest + 2, i)

IrcC = i

End If

Next i

If WrcM > 0 Then

Icol = IrcM

ElseIf WrcC > 0 Then

Icol = IrcC

Else

Icol = 0

End If

End Sub

Private Sub CalcColL()

‘Âû÷èñëåíèå êëþ÷åâîãî ñòîëáöà ïî îòðèöàòåëüíîé(ìàêñèìàëüíîé ïî ìîäóëþ) îöåíêå(êîãäà max)

‘Calculation key column on negative(maximum modulo) to estimation(when max)

Dim i As Integer

Dim WrcM As Double, IrcM As Integer

Dim WrcC As Double, IrcC As Integer

WrcM = 0

WrcC = 0

For i = 1 To MaxX

If Tsimp(AmRest + 1, i) < 0 And Abs(Tsimp(AmRest + 1, i)) > WrcM Then

WrcM = Abs(Tsimp(AmRest + 1, i))

IrcM = i

ElseIf (Tsimp(AmRest + 2, i) < 0) And (Abs(Tsimp(AmRest + 2, i)) > WrcC) And (Tsimp(AmRest + 1, i) = 0) Then

WrcC = Abs(Tsimp(AmRest + 2, i))

IrcC = i

End If

Next i

If WrcM > 0 Then

Icol = IrcM

ElseIf WrcC > 0 Then

Icol = IrcC

Else

Icol = 0

End If

End Sub

Private Sub CalcRow()

‘Âû÷èñëåíèå êëþ÷åâîé ñòðîêè ïî ïîëîæèòåëüíîìó ìèíèìóì îòíîøåíèÿ X0/Xi

‘Calculation of the key line on positive minimum relations X0/Xi

Dim Cslave As Double, Islave As Integer

Dim Wrk As Double

If Icol = 0 Then

For i = 1 To AmRest

MiCiXiAi(i, 4) = -1

‘MiCiXiAi(i, 4) = Nothing

Next i

Irow = 0

Else

Cslave = -1

Islave = 0

For i = 1 To AmRest

If Tsimp(i, Icol) <> 0 Then

If Tsimp(i, 0) = 0 Then

Wrk = IIf(Sgn(Tsimp(i, Icol)) = 1, 0, -1)

Else

Wrk = Tsimp(i, 0) / Tsimp(i, Icol)

End If

MiCiXiAi(i, 4) = Wrk

If Wrk >= 0 And Islave = 0 Then

Cslave = Wrk

Islave = i

ElseIf Wrk >= 0 Then

If DirectCycle Then

If Wrk < Cslave Then    ’îñòàâëÿòü èç ðàâíûõ ïåðâûé

Cslave = Wrk

Islave = i

End If

Else

If Wrk <= Cslave Then   ‘îñòàâëÿòü èç ðàâíûõ ïîñëåäíèé

Cslave = Wrk

Islave = i

End If

End If

End If

Else

MiCiXiAi(i, 4) = -1

End If

Next i

Irow = Islave

End If

End Sub

Private Sub CommandButton2_Click()

‘Ñîâåðøèòü èòåðàöèþ

Dim Welm As Double

MiCiXiAi(Irow, 1) = Tsimp(AmRest + 3, Icol)

MiCiXiAi(Irow, 2) = Tsimp(0, Icol)

MiCiXiAi(Irow, 3) = Icol

Welm = Tsimp(Irow, Icol)

For i = 1 To AmRest + 2

If i <> Irow Then

For j = 0 To MaxX

If j <> Icol Then

Tsimp(i, j) = Tsimp(i, j) - (Tsimp(i, Icol) / Welm) * Tsimp(Irow, j)

End If

Next j

End If

Next i

For j = 0 To MaxX

Tsimp(Irow, j) = Tsimp(Irow, j) / Welm

Next j

For i = 1 To AmRest + 2

Tsimp(i, Icol) = 0

Next i

Tsimp(Irow, Icol) = 1

FRowCol

If Cycle() Then

LookResult “Èòåðàöèè çàöèêëèëèñü íà èòåðàöèè ¹” & CStr(NumIter - 1), 11

ElseIf Icol > 0 And Irow > 0 Then

LookResult “Ñìîòðè èòåðàöèþ ¹” & CStr(NumIter - 1), 50

ElseIf Icol > 0 And Irow <= 0 Then

LookResult “Ôóíêöèÿ íå îãðàíè÷åíà”, 28

Else

LookResult “Îïòèìàëüíûé ïëàí”, 37

End If

End Sub

Private Sub FRowCol()

‘Ïîèñê ðàçðåøàþùèõ ñòðîêè è ñòîëáöà

If MaxLi Then

CalcColL    ’max

Else

CalcColB    ’ min

End If

CalcRow  ’X0/Xi

If Icol > 0 And Irow > 0 Then

CommandButton2.Visible = True

NumIter = NumIter + 1

CommandButton2.Caption = “Ïðîèçâåñòè èòåðàöèþ ¹” & CStr(NumIter)

Else

NumIter = NumIter + 1

CommandButton2.Visible = False

End If

End Sub

Private Function Cycle() As Boolean ‘Åñëè “Âåðíî” çàöèêëèëèñü. If “True” were looped.

Dim CurrentPlan As String

Dim i As Integer

Cycle = False

CurrentPlan = “”

For i = 1 To AmRest

CurrentPlan = CurrentPlan & CStr(MiCiXiAi(i, 3))

Next i

If InStr(AllPlans, CurrentPlan) > 0 Then

If DirectCycle = True Then

DirectCycle = False

Else

Cycle = True

End If

AllPlans = “”

Else

AllPlans = AllPlans & ” ” & CurrentPlan

End If

End Function

Çàêëþ÷åíèå 

Â äàííîé ðàáîòå ðàññìàòðèâàþòñÿ äâà ñïîñîáà ðåøåíèÿ èñõîäíîé çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ. 

Ïåðâûé çàêëþ÷àåòñÿ â òîì, ÷òî ñíà÷àëà ðåøàåòñÿ âñïîìîãàòåëüíàÿ çàäà÷à (L-çàäà÷à), ïîçâîëÿþùàÿ ïîñòðîèòü íà÷àëüíûé îïîðíûé ïëàí, çàòåì íà îñíîâå ýòîãî íàéäåííîãî ïëàíà ðåøàåòñÿ èñõîäíàÿ çàäà÷à (îïðåäåëÿåòñÿ åå îïòèìàëüíûé ïëàí). Âòîðîé ñïîñîá ÿâëÿåòñÿ îáúåäèíåíèåì äâóõ ýòàïîâ è ñîñòîèò â ðåøåíèè ðàñøèðåííîé çàäà÷è (M-çàäà÷è), òàêæå ïðèâîäÿùåé ê íàõîæäåíèþ îïòèìàëüíîãî ïëàíà èñõîäíîé çàäà÷è.

Âû÷èñëèòåëüíóþ îñíîâó ýòèõ äâóõ ñïîñîáîâ ðåøåíèÿ ñîñòàâëÿþò ñîîòâåòñòâåííî ïåðâûé è âòîðîé àëãîðèòìû ñèìïëåêñ-ìåòîäà. Îäèí èç ïàðàìåòðîâ, ïî êîòîðîìó ìîæåò áûòü îöåíåí ëþáîé èòåðàöèîííûé àëãîðèòì – êîëè÷åñòâî øàãîâ, ïðèâîäÿùèõ ê ðåøåíèþ çàäà÷è èëè óñòàíîâëåíèþ åå íåðàçðåøèìîñòè. Äëÿ äàííîé çàäà÷è íàèáîëåå ýôôåêòèâíûì ìåòîäîì îêàçàëñÿ ïåðâûé ìåòîä(L-çàäà÷à + èñõîäíàÿ çàäà÷à), ò.ê. îí ïðèâåë ê ðåøåíèþ çà 4 øàãà, à âòîðîé ìåòîä (M-çàäà÷à) çà 5 øàãîâ. Ðàçíèöà â ÷èñëå øàãîâ, âåðîÿòíî, îáóñëîâëåíà íåîäíîçíà÷íîñòü âûáîðà ðàçðåøàþùåãî ýëåìåíòà â èñõîäíîé òàáëèöå L-çàäà÷è. 

Ñðàâíåíèå êîëè÷åñòâà âû÷èñëåíèé íà êàæäîé èòåðàöèè ïðèâîäèò ê ñëåäóþùèì îöåíî÷íûì ðåçóëüòàòàì ðàññìàòðèâàåìûõ àëãîðèòìîâ. Ïðåèìóùåñòâåííàÿ ÷àñòü âû÷èñëåíèé íà êàæäîì øàãå àëãîðèòìîâ îïðåäåëÿåòñÿ ðàçìåðíîñòüþ ãëàâíîé ÷àñòè òàáëèöû (â ïåðâîì àëãîðèòìå) èëè îñíîâíîé òàáëèöû (âî âòîðîì àëãîðèòìå). Â ïåðâîì ñëó÷àå îíà èìååò ðàçìåðíîñòü (m+1)x(n+1), âî âòîðîì - (m+1)x(m+1). Äàæå ó÷èòûâàÿ, ÷òî âòîðîé àëãîðèòì òðåáóåò ïîñòðîåíèÿ âñïîìîãàòåëüíîé òàáëèöû, îí îêàçûâàåòñÿ áîëåå êîìïàêòíûì.

Åùå îäíî íåñîìíåííîå äîñòîèíñòâî âòîðîãî àëãîðèòìà çàêëþ÷àåòñÿ â âîçìîæíîñòè îïðåäåëåíèÿ îïòèìàëüíîãî ïëàíà äâîéñòâåííîé çàäà÷è èç (m+1)-é ñòðîêè îñíîâíîé òàáëèöû, ñîîòâåòñòâóþùåé ïîñëåäíåé èòåðàöèè, áåç âñÿêèõ äîïîëíèòåëüíûõ âû÷èñëåíèé.

Ñïèñîê èñïîëüçîâàííûõ èñòî÷íèêîâ 

Âåíòöåëü Å.Ñ. Èññëåäîâàíèå îïåðàöèé: çàäà÷è, ïðèíöèïû, ìåòîäîëîãèÿ. – Ì.: Âûñøàÿ øêîëà, 2001.

Àðîíîâè÷ À.Á., Àôàíàñüåâ Ì.Þ., Ñóâîðîâ Á.Ï. Ñáîðíèê çàäà÷ ïî èññëåäîâàíèþ îïåðàöèé. – Ì.: Èçäàòåëüñòâî Ìîñêîâñêîãî óíèâåðñèòåòà, 1997.

Èññëåäîâàíèå îïåðàöèé â ýêîíîìèêå /Ïîä ðåä. Êðåìåð. – Ì.: ÞÍÈÒÈ, 1997. 

Ìîðîçîâ Â.Â., Ñóõàðåâ À.Ã., Ôåäîðîâ Â.Â. Èññëåäîâàíèå îïåðàöèé â çàäà÷àõ è óïðàæíåíèÿõ. – Ì.: Âûñøàÿ øêîëà, 1986.

Øèêèí Å.Â., ×õàðòèøâèëè À.Ã. Ìàòåìàòè÷åñêèå ìåòîäû è ìîäåëè óïðàâëåíèÿ. – Ì.: Äåëî, 2000.

Àêóëè÷ È.Ë. Ìàòåìàòè÷åñêîå ïðîãðàììèðîâàíèå â ïðèìåðàõ è çàäà÷àõ. – Ì.: Âûñøàÿ øêîëà, 1986.

Ôèëëèïñ Ä., Ãàðñèà-Äèàñ À. Ìåòîäû àíàëèçà ñåòåé. – Ì.: Ìèð, 1984.

Ëèïñêè Â. Êîìáèíàòîðèêà äëÿ ïðîãðàììèñòîâ. – Ì.: Ìèð, 1988.



30