Побудова економіко-математичної моделі

1 2 3 4 5 6 7

Ïîçíà÷èìî ÷åðåç хij ïëîùó (ãà) і -î¿ çåìåëüíî¿ ä³ëÿíêè, ùî áóäå çàñ³ÿíà j -ì ñîðòîì îçèìî¿ ïøå-

íèö³ (äîìîâèìîñÿ, ùî ñîðòè «Ìèðîí³âñüêà-808», «Áåçîñòà-1», «Îäåñüêà-51» â³äïîâ³äàòèìóòü íîìå-

ðàì 1, 2, 3), (і = 1, 2, 3), (j = 1, 2, 3).

Òîä³ âèêîðèñòàííÿ çåìåëüíèõ óã³äü îïèñóâàòèìå òàêà ñèñòåìà îáìåæåíü:

x 11 + x 12 + x 13 = 40;

x 21 + x 22 + x 23 = 90;

x 31 + x 32 + x 33 = 55.

Âèêîðèñòàííÿ ïîñ³âíîãî ìàòåð³àëó ôîðìàëüíî ìîæíà îïèñàòè òàê:

x 11 + x 21 + x 31 = 80;

x 12 + x 22 + x 32 = 60;

x 13 + x 23 + x 33 = 45.

Âàëîâèé çá³ð çåðíà ðîçðàõîâóºòüñÿ ÿê ñóìà äîáóòê³â óðîæàéíîñòåé â³äïîâ³äíèõ ñîðò³â

ïøåíèö³ íà ¿õ ïîñ³âí³ ïëîù³, òîáòî:

30 28 40.

38 41 45

41 40 46

13 23 33

12 22 32

11 21 31

x x x

F x x x

+ + +

+ + + +

= + + +

Îòæå, åêîíîì³êî-ìàòåìàòè÷íà ìîäåëü çàäà÷³ çàãàëîì áóäå ìàòè âèãëÿä:

13 23 33

12 22 32

11 21 31

30 28 40

38 41 45

max 41 40 46

x x x

F x x x

+ + +

+ + + +

= + + +

çà óìîâ:

ï ï ï ï

ïï ï ï

+ + =

45.

60;

80;

55;

90;

40;

13 22 33

12 22 32

11 21 31

31 32 33

21 22 23

11 12 13

x x x

xij ³ 0 (i =1, 2,3), (j =1, 2,3).

ËÅÊÖ²ß 3. ÇÀÄÀ×À Ë²Í²ÉÍÎÃÎ ÏÐÎÃÐÀÌÓÂÀÍÍß ÒÀ ÌÅÒÎÄÈ ¯¯ ÐÎÇÂ’ßÇÓÂÀÍÍß

Àíîòàö³ÿ

Загальна економіко-математична модель задачі лінійного програмування. Форми запису задач

лінійного програмування. Геометрична інтерпретація задачі лінійного програмування. Основні влас-

тивості розв’язків задачі лінійного програмування. Графічний метод розв’язування задач лінійного

програмування.

3.1 Çàãàëüíà åêîíîì³êî-ìàòåìàòè÷íà ìîäåëü çàäà÷³ ë³í³éíîãî ïðîãðàìóâàííÿ

Çàãàëüíà ë³í³éíà åêîíîì³êî-ìàòåìàòè÷íà ìîäåëü åêîíîì³÷íèõ ïðîöåñ³â òà ÿâèù – òàê çâàíà çà-

ãàëüíà çàäà÷à ë³í³éíîãî ïðîãðàìóâàííÿ ïîäàºòüñÿ ó âèãëÿä³:

max (min) Z = c 1 x 1 + c 2 x 2 +¼+ cn xn (3.1)

çà óìîâ:

{ }

{ } ï

ï ï

+ +¼+ £ ³ =

,,.

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

,,;

1 1 2 2

21 1 22 2 2 2

11 1 12 2 1 1

m m mn n m

n n

a x a x a x b

(3.2)

x 1 ³ 0, x 2 ³ 0,¼, xn ³ 0. (3.3)

Îòæå, ïîòð³áíî çíàéòè çíà÷åííÿ çì³ííèõ x 1, x 2, …, xn, ÿê³ çàäîâîëüíÿþòü óìîâè (3.2) ³ (3.3), ³

ö³ëüîâà ôóíêö³ÿ (3.1) íàáóâàº åêñòðåìàëüíîãî (ìàêñèìàëüíîãî ÷è ì³í³ìàëüíîãî) çíà÷åííÿ.

Äëÿ äîâ³ëüíî¿ çàäà÷³ ìàòåìàòè÷íîãî ïðîãðàìóâàííÿ ó ï.2.1 áóëè ââåäåí³ ïîíÿòòÿ äîïóñòèìîãî

òà îïòèìàëüíîãî ïëàí³â.

Äëÿ çàãàëüíî¿ çàäà÷³ ë³í³éíîãî ïðîãðàìóâàííÿ âèêîðèñòîâóþòüñÿ òàê³ ïîíÿòòÿ.

Âåêòîð Х = (х 1, х 2, …, хn), êîîðäèíàòè ÿêîãî çàäîâîëüíÿþòü ñèñòåìó îáìåæåíü (3.2) òà óìîâè

íåâ³ä’ºìíîñò³ çì³ííèõ (3.3), íàçèâàºòüñÿ допустимим розв’язком (планом) задачі лінійного програ-

мування.

Äîïóñòèìèé ïëàí Х = (х 1, х 2, …, хn) íàçèâàºòüñÿ опорним планом çàäà÷³ ë³í³éíîãî ïðîãðàìó-

âàííÿ, ÿêùî â³í çàäîâîëüíÿº íå ìåíøå, í³æ m ë³í³éíî íåçàëåæíèõ îáìåæåíü ñèñòåìè (3.2) ó âèãëÿä³

ð³âíîñòåé, à òàêîæ îáìåæåííÿ (3.3) ùîäî íåâ³ä’ºìíîñò³ çì³ííèõ.

Îïîðíèé ïëàí Х = (х 1, х 2, …, хn), íàçèâàºòüñÿ невиродженим ______________, ÿêùî â³í ì³ñòèòü òî÷íî m äîäàò-

íèõ çì³ííèõ, ³íàêøå â³í вироджений.

Îïîðíèé ïëàí (, *,, *)

X = x x ¼ xn, çà ÿêîãî ö³ëüîâà ôóíêö³ÿ (3.1) äîñÿãàº ìàñèìàëüíîãî (÷è ì³í³-

ìàëüíîãî) çíà÷åííÿ, íàçèâàºòüñÿ оптимальним розв’язком (планом) задачі лінійного програмуван-

ня.

Çàäà÷ó (3.1)—(3.3) ìîæíà ëåãêî çâåñòè äî êàíîí³÷íî¿ ôîðìè, òîáòî äî òàêîãî âèãëÿäó, êîëè â

ñèñòåì³ îáìåæåíü (3.2) âñ³ bi (i = 1, 2, …, m) íåâ³ä’ºìí³, à âñ³ îáìåæåííÿ º ð³âíîñòÿìè.

ßêùî ÿêåñü bi â³ä’ºìíå, òî, ïîìíîæèâøè i -òå îáìåæåííÿ íà

(– 1), ä³ñòàíåìî ó ïðàâ³é ÷àñòèí³ â³äïîâ³äíî¿ ð³âíîñò³ äîäàòíå çíà÷åííÿ. Êîëè i -òå îáìåæåííÿ ìàº âè-

ãëÿä íåð³âíîñò³ аi 1 х 1+ аi 2 х 2+…+ аinxn ≤ bi, òî îñòàííþ çàâæäè ìîæíà çâåñòè äî ð³âíîñò³, óâ³âøè додат-

кову змінну xn +1:

ai 1 x 1+ ai 2 x 2+…+ ain xn + xn + 1 = bi.

Àíàëîã³÷íî îáìåæåííÿ âèäó аk 1 x 1 + ak 2 x 2 + … + aknxn ≥ bk çâîäÿòü äî ð³âíîñò³, â³äí³ìàþ÷è â³ä

ë³âî¿ ÷àñòèíè додаткову çì³ííó хn +2, òîáòî:

ak 1 x 1 + ak 2 x 2 + … + aknxn – xn + 2 = bk (хn +1 ≥ 0, хn +2 ≥ 0).

3.2 Ôîðìè çàïèñó çàäà÷ ë³í³éíîãî ïðîãðàìóâàííÿ

Çàäà÷ó ë³í³éíîãî ïðîãðàìóâàííÿ çðó÷íî çàïèñóâàòè çà äîïîìîãîþ çíàêà ñóìè «S». Ñïðàâä³, çà-

äà÷ó (3.1)-(3.3) ìîæíà ïîäàòè òàê:

å=

Z c j x j

max(min)

çà óìîâ:

0 (1, 2,,).

(1, 2,,);

x j n

a x b i m

ij j i

³ = ¼

¼ = = å

(3.4)

Ùå êîìïàêòí³øèì º çàïèñ çàäà÷³ ë³í³éíîãî ïðîãðàìóâàííÿ ó âåêòîðíî-ìàòðè÷íîìó âèãëÿä³:

max(min) Z = CX

çà óìîâ:

АХ = À0; (3.5)

Х ≥ 0,

äå

{ }

÷ ÷ ÷ ÷ ÷

ç ç ç ç ç

= =

m m mn

a a a

A a

,,,

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

,,,

1 2

21 22 2

11 12 1

º ìàòðèöåþ êîåô³ö³ºíò³â ïðè çì³ííèõ;

÷ ÷ ÷ ÷

ç ç ç ç



—âåêòîð çì³ííèõ;

÷ ÷ ÷ ÷ ÷

ç ç ç ç ç



0 —âåêòîð â³ëüíèõ ÷ëåí³â;

С = (с1, с2, …, сп)— âåêòîð êîåô³ö³ºíò³â ïðè çì³ííèõ ó ö³ëüîâ³é ôóíêö³¿.

×àñòî çàäà÷ó ë³í³éíîãî ïðîãðàìóâàííÿ çðó÷íî çàïèñóâàòè ó âåêòîðí³é ôîðì³:

max(min) Z = CX

çà óìîâ:

A 1 x 1 + A 2 x 2 + … + Anxn = A 0; (3.6)

X ≥0,

äå

÷ ÷ ÷ ÷

ç ç ç ç

¼ =

÷ ÷ ÷ ÷

ç ç ç ç

÷ ÷ ÷ ÷

ç ç ç ç

m m a

  

1,,,

º âåêòîðàìè êîåô³ö³ºíò³â ïðè çì³ííèõ.

3.3 Ãåîìåòðè÷íà ³íòåðïðåòàö³ÿ çàäà÷³ ë³í³éíîãî ïðîãðàìóâàííÿ

Ðîçãëÿíåìî íà ïëîùèí³ х1Оx2 ñóì³ñíó ñèñòåìó ë³í³éíèõ íåð³âíîñòåé:

ï ï

+ £

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

;

1 1 2 2

21 1 22 2 2

11 1 12 2 1

am x am x bm

a x a x b

(3.7)

x 1 ³ 0, x 2 ³ 0.

Êîæíà íåð³âí³ñòü ö³º¿ ñèñòåìè ãåîìåòðè÷íî âèçíà÷àº ï³âïëîùèíó ç ãðàíè÷íîþ ïðÿìîþ ai 1 x 1 +

ai 2 x 2 = bi (i =1,2,..., т). Óìîâè íåâ³ä’ºìíîñò³ çì³ííèõ âèçíà÷àþòü ï³âïëîùèíè ç ãðàíè÷íèìè ïðÿìèìè

х 1 = 0 òà х 2 = 0. Ñèñòåìà ñóì³ñíà, òîìó ï³âïëîùèíè ÿê îïóêë³ ìíîæèíè, ïåðåòèíàþ÷èñü, óòâîðþþòü

ñï³ëüíó ÷àñòèíó, ùî º îïóêëîþ ìíîæèíîþ ³ ÿâëÿº ñîáîþ ñóêóïí³ñòü òî÷îê, êîîðäèíàòè êîæíî¿ ç ÿêèõ

º ðîçâ’ÿçêîì äàíî¿ ñèñòåìè (ðèñ.3.1).

0 x 1

x 2

Ðèñóíîê 3.1

Ñóêóïí³ñòü öèõ òî÷îê (ðîçâ’ÿçê³â) íàçèâàþòü багатокутником розв’язків, àáî областю допу-

стимих планів (розв’язків) задачі лінйного програмування. Öå ìîæå áóòè òî÷êà (ºäèíèé ðîçâ’ÿçîê),

â³äð³çîê, ïðîì³íü, áàãàòîêóòíèê, íåîáìåæåíà áàãàòîêóòíà îáëàñòü.

ßêùî â ñèñòåì³ îáìåæåíü (3.7) áóäå òðè çì³ííèõ, òî êîæíà íåð³âí³ñòü ãåîìåòðè÷íî âèçíà÷àòè-

ìå ï³âïðîñò³ð òðèâèì³ðíîãî ïðîñòîðó, ãðàíè÷íèìè ïëîùèíàìè êîòðîãî áóäóòü ai 1 x 1 + ai 2 x 2 + ai 3 x 3 = bi

(i = 1, 2,..., т), à óìîâè íåâ³ä’ºìíîñò³ – ï³âïðîñòîðè ç ãðàíè÷íèìè ïëîùèíàìè хj =0 (j = 1, 2, 3), äå і –

íîìåð îáìåæåííÿ, à j– — íîìåð çì³ííî¿. ßêùî ñèñòåìà îáìåæåíü ñóì³ñíà, òî ö³ ï³âïðîñòîðè ÿê îïóêë³

ìíîæèíè, ïåðåòèíàþ÷èñü, óòâîðÿòü ó òðèâèì³ðíîìó ïðîñòîð³ ñï³ëüíó ÷àñòèíó, ùî íàçèâàºòüñÿ бага-

тогранником розв’язків. Â³í ìîæå áóòè òî÷êîþ, â³äð³çêîì, ïðîìåíåì, áàãàòîêóòíèêîì, áàãàòîãðàí-

íèêîì, áàãàòîãðàííîþ íåîáìåæåíîþ îáëàñòþ.

Íåõàé ó ñèñòåì³ îáìåæåíü (3.7) ê³ëüê³ñòü çì³ííèõ á³ëüøà, í³æ òðè: х 1, х 2,… хn; òîä³ êîæíà íåð³-

âí³ñòü âèçíà÷àº ï³âïðîñò³ð n -âèì³ðíîãî ïðîñòîðó ç ãðàíè÷íîþ ã³ïåðïëîùèíîþ аi 1 x 1 + ai 2 x 2 + ai 3 x 3 + …

+ ainxn = bi (i = 1, 2,..., т). Êîæíîìó îáìåæåííþ âèäó (3.7) â³äïîâ³äàþòü ã³ïåðïëîùèíà òà íàï³âïðîñ-

ò³ð, ÿêèé ëåæèòü ç îäíîãî áîêó ö³º¿ ã³ïåðïëîùèíè, à óìîâè íåâ³ä’ºìíîñò³— ï³âïðîñòîðè ç ãðàíè÷íèìè

ã³ïåðïëîùèíàìè хj = 0 (j =1, 2, 3,..., n).

ßêùî ñèñòåìà îáìåæåíü ñóì³ñíà, òî çà àíàëîã³ºþ ç òðèâèì³ðíèì ïðîñòîðîì âîíà óòâîðþº ñï³-

ëüíó ÷àñòèíó â n -âèì³ðíîìó ïðîñòîð³ — îïóêëèé áàãàòîãðàííèê äîïóñòèìèõ ðîçâ’ÿçê³â.

Îòæå, ãåîìåòðè÷íî çàäà÷à ë³í³éíîãî ïðîãðàìóâàííÿ ÿâëÿº ñîáîþ â³äøóêàííÿ êîîðäèíàò òàêî¿

òî÷êè áàãàòîãðàííèêà ðîçâ’ÿçê³â, ïðè ï³äñòàíîâö³ ÿêèõ ó ö³ëüîâó ë³í³éíó ôóíêö³þ îñòàííÿ íàáèðàº

ìàêñèìàëüíîãî (ì³í³ìàëüíîãî) çíà÷åííÿ, ïðè÷îìó äîïóñòèìèìè ðîçâ’ÿçêàìè º óñ³ òî÷êè áàãàòîãðàí-

íèêà ðîçâ’ÿçê³â.

Ö³ëüîâó ôóíêö³þ

î í ì

- - + =

- + =

1 2 6 0.

5 0,

1 2

x x

â п -âèì³ðíîìó ïðîñòîð³ îñíîâíèõ çì³ííèõ ìîæíà ãåîìåòðè÷íî ³íòåðïðåòóâàòè ÿê ñ³ì’þ ïàðàëåëüíèõ

ã³ïåðïëîùèí, ïîëîæåííÿ êîæíî¿ ç ÿêèõ âèçíà÷àºòüñÿ çíà÷åííÿì ïàðàìåòðà Z.

Ðîçãëÿíåìî ãåîìåòðè÷íó ³íòåðïðåòàö³þ çàäà÷³ ë³í³éíîãî ïðîãðàìóâàííÿ íà ïðèêëàä³. Íåõàé

ôåðìåð ïðèéíÿâ ð³øåííÿ âèðîùóâàòè îçèìó ïøåíèöþ ³ öóêðîâ³ áóðÿêè íà ïëîù³ 20 ãà, â³äâ³âøè ï³ä

öóêðîâ³ áóðÿêè íå ìåíøå ÿê 5 ãà. Òåõí³êî-åêîíîì³÷í³ ïîêàçíèêè âèðîùóâàííÿ öèõ êóëüòóð ìàºìî ó

òàáë.3.1:

Òàáëèöÿ 2.3 – Ïîêàçíèêè âèðîùóâàííÿ ñ³ëüñüêîãîñïîäàðñüêèõ êóëüòóð

Ïîêàçíèê

(³ç ðîçðàõóíêó íà 1 ãà)

Îçèìà ïøåíèöÿ Öóêðîâ³

áóðÿêè

Íàÿâíèé

ðåñóðñ

Çàòðàòè ïðàö³, ëþäèíî-äí³â 5 25 270

Çàòðàòè ïðàö³ ìåõàí³çàòîð³â, ëþ-

äèíî-äí³â 2 8 80

Óðîæàéí³ñòü, òîíí 3,5 40 —

Ïðèáóòîê, òèñ. ãðí 0,7 1 —

Êðèòåð³ºì îïòèìàëüíîñò³ º ìàêñèì³çàö³ÿ ïðèáóòêó.

Çàïèøåìî åêîíîì³êî-ìàòåìàòè÷íó ìîäåëü ñòðóêòóðè âèðîáíèöòâà îçèìî¿ ïøåíèö³ òà öóêðîâèõ

áóðÿê³â, ââ³âøè òàê³ ïîçíà÷åííÿ:

х 1 — øóêàíà ïëîùà ïîñ³âó îçèìî¿ ïøåíèö³, ãà;

х 2— øóêàíà ïëîùà ïîñ³âó öóêðîâèõ áóðÿê³â, ãà.

Çàäà÷à ë³í³éíîãî ïðîãðàìóâàííÿ ìàº òàêèé âèãëÿä:

max Z = 0,7 x1 + x2 (3.8)

çà óìîâ:

x1 + x2 ≤ 20; (3.9)

5 x1 + 25 x2 ≤ 270; (3.10)

2 x1 + 8 x2 ≤ 80; (3.11)

x2 ≥ 5; (3.12)

x1 ≥ 0, x2 ≥ 0. (3.13)

Ãåîìåòðè÷íó ³íòåðïðåòàö³þ çàäà÷³ çîáðàæåíî íà ðèñ.3.2.

0 10

20 30 40 50

x 1

x 2

x 2³5

x x 1 2 + 20 £

5 + 25 270 x x 1 2 £

2 + 8 80 x x 1 2 £

0,7 + = 3,5 x x 1 2

0,7 + = 0 x x 1 2

Ðèñóíîê 3.2 – Îáëàñòü äîïóñòèìèõ ðîçâ’ÿçê³â çàäà÷³

Îáëàñòü äîïóñòèìèõ ðîçâ’ÿçê³â ö³º¿ çàäà÷³ ä³ñòàºìî òàê. Êîæíå îáìåæåííÿ, íàïðèêëàä х 1 + х 2

£ 20, çàäàº ï³âïëîùèíó ç ãðàíè÷íîþ ïðÿìîþ х 1 + х 2 = 20. Áóäóºìî ¿¿ ³ âèçíà÷àºìî ï³âïëîùèíó, ÿêà

îïèñóºòüñÿ íåð³âí³ñòþ х 1 + х 2 £ 20. Ç ö³ºþ ìåòîþ â íåð³âí³ñòü х 1+ х 2 £ 20 ï³äñòàâëÿºìî êîîðäèíàòè õà-

ðàêòåðíî¿ òî÷êè, ñêàæ³ìî, х 1=0 ³ х 2=0. Ïåðåêîíóºìîñÿ, ùî öÿ òî÷êà íàëåæèòü ï³âïëîùèí³ х 1+ х 2 £ 20.

Öåé ôàêò íà ðèñ.3.2 ³ëþñòðóºìî â³äïîâ³äíîþ íàïðÿìëåíîþ ñòð³ëêîþ. Àíàëîã³÷íî áóäóºìî ï³âïëîùè-

íè, ÿê³ â³äïîâ³äàþòü íåð³âíîñòÿì (3.10)—(3.13). Ó ðåçóëüòàò³ ïåðåòèíó öèõ ï³âïëîùèí óòâîðþºòüñÿ

îáëàñòü äîïóñòèìèõ ðîçâ’ÿçê³â çàäà÷³ (íà ðèñ.3.2 – ÷îòèðèêóòíèê ABCD). Ö³ëüîâà ôóíêö³ÿ Z = 0,7 x 1 +

x 2 ÿâëÿº _______ñîáîþ ñ³ì’þ ïàðàëåëüíèõ ïðÿìèõ, êîæíà ç ÿêèõ â³äïîâ³äàº ïåâíîìó çíà÷åííþ Z. Çîêðåìà,

ÿêùî Z =0, òî ìàºìî 0,7 х 1 + х 2 = 0. Öÿ ïðÿìà ïðîõîäèòü ÷åðåç ïî÷àòîê ñèñòåìè êîîðäèíàò. Êîëè Z =3,5,

òî ìàºìî ïðÿìó 0,7 х 1 + х 2 = 3,5.

3.4 Îñíîâí³ âëàñòèâîñò³ ðîçâ’ÿçê³â çàäà÷³ ë³í³éíîãî ïðîãðàìóâàííÿ

Âëàñòèâîñò³ ðîçâ’ÿçê³â çàäà÷³ ë³í³éíîãî ïðîãðàìóâàííÿ ôîðìóëþþòüñÿ ó âèãëÿä³ ÷îòèðüîõ òå-

îðåì.

Властивість 1. (Òåîðåìà 3.1) Ìíîæèíà âñ³õ ïëàí³â çàäà÷³ ë³í³éíîãî ïðîãðàìóâàííÿ îïóêëà.

Властивість 2. (Òåîðåìà 3.2) ßêùî çàäà÷à ë³í³éíîãî ïðîãðàìóâàííÿ ìàº îïòèìàëüíèé ïëàí,

òî åêñòðåìàëüíîãî çíà÷åííÿ ö³ëüîâà ôóíêö³ÿ íàáóâàº â îäí³é ³ç âåðøèí ¿¿ áàãàòîãðàííèêà ðîçâ’ÿçê³â.

ßêùî æ ö³ëüîâà ôóíêö³ÿ íàáóâàº åêñòðåìàëüíîãî çíà÷åííÿ á³ëüø ÿê â îäí³é âåðøèí³ öüîãî áàãàòîã-

ðàííèêà, òî âîíà äîñÿãàº éîãî ³ â áóäü-ÿê³é òî÷ö³, ùî º ë³í³éíîþ êîìá³íàö³ºþ òàêèõ âåðøèí.

Властивість 3. (Òåîðåìà 3.3) ßêùî â³äîìî, ùî ñèñòåìà âåêòîð³â A 1, A 2, …, Ak (k≤n) ó ðîçêëàä³

A 1 x 1 + A 2 x 2 + … + Anxn = A 0, X ≥0 ë³í³éíî íåçàëåæíà ³ òàêà, ùî

A 1 x 1 + A 2 x 2 + … + Akxk = A 0,

äå âñ³ xj ≥ 0, òî òî÷êà X = (x 1, x 2, …, xk, 0, …, 0) º êóòîâîþ òî÷êîþ áàãàòîãðàííèêà ðîçâ’ÿçê³â.

Властивість 4. (Òåîðåìà 3.4) ßêùî X = (x 1, x 2, …, xn) – êóòîâà òî÷êà áàãàòîãðàííèêà

ðîçâ’ÿçê³â, òî âåêòîðè â ðîçêëàä³ A 1 x 1 + + A 2 x 2 + … + Anxn = A 0, X ≥ 0, ùî â³äïîâ³äàþòü äîäàòíèì xj, º

ë³í³éíî íåçàëåæíèìè.

Наслідок 1. Îñê³ëüêè âåêòîðè A 1, A 2,..., An ìàþòü ðîçì³ðí³ñòü m, òî êóòîâà òî÷êà áàãàòîêóò-

íèêà ðîçâ’ÿçê³â ìàº íå á³ëüøå, í³æ m äîäàòíèõ êîìïîíåíò³â xi > 0 (i =1, m).

Наслідок 2. Êîæí³é êóòîâ³é òî÷ö³ áàãàòîêóòíèêà ðîçâ’ÿçê³â â³äïîâ³äàº k £ m ë³í³éíî íåçàëå-

æíèõ âåêòîð³â ñèñòåìè A 1, A 2,..., An.

Ç íàâåäåíèõ âëàñòèâîñòåé ìîæíà çðîáèòè âèñíîâîê, ùî ÿêùî ôóíêö³îíàë çàäà÷³ ë³í³éíîãî

ïðîãðàìóâàííÿ îáìåæåíèé íà áàãàòîãðàííèêó ðîçâ’ÿçê³â, òî:

1) ³ñíóº òàêà êóòîâà òî÷êà áàãàòîãðàííèêà ðîçâ’ÿçê³â, â ÿê³é ë³í³éíèé ôóíêö³îíàë äîñÿãàº ñâî-

ãî îïòèìàëüíîãî çíà÷åííÿ;

2) êîæíèé îïîðíèé ïëàí â³äïîâ³äàº êóòîâ³é òî÷ö³ áàãàòîãðàííèêà ðîçâ’ÿçê³â.

Òîìó äëÿ ðîçâ’ÿçàííÿ çàäà÷³ ë³í³éíîãî ïðîãðàìóâàííÿ íåîáõ³äíî äîñë³äæóâàòè ëèøå êóòîâ³

òî÷êè áàãàòîãðàííèêà (îïîðí³ ïëàíè), íå âêëþ÷àþ÷è äî ðîçãëÿäó âíóòð³øí³ òî÷êè ìíîæèíè äîïóñòè-

ìèõ ïëàí³â.

3.5 Ãðàô³÷íèé ìåòîä ðîçâ’ÿçóâàííÿ çàäà÷ ë³í³éíîãî ïðîãðàìóâàííÿ

Äëÿ ðîçâ’ÿçóâàííÿ äâîâèì³ðíèõ çàäà÷ ë³í³éíîãî ïðîãðàìóâàííÿ, òîáòî çàäà÷ ³ç äâîìà çì³ííèìè,

à òàêîæ äåÿêèõ òðèâèì³ðíèõ çàäà÷ çàñòîñîâóþòü ãðàô³÷íèé ìåòîä, ùî ´ðóíòóºòüñÿ íà ãåîìåòðè÷í³é ³í-

òåðïðåòàö³¿ òà àíàë³òè÷íèõ âëàñòèâîñòÿõ çàäà÷ ë³í³éíîãî ïðîãðàìóâàííÿ. Îáìåæåíå âèêîðèñòàííÿ ãðà-

ô³÷íîãî ìåòîäó çóìîâëåíå ñêëàäí³ñòþ ïîáóäîâè áàãàòîãðàííèêà ðîçâ’ÿçê³â ó òðèâèì³ðíîìó ïðîñòîð³

(äëÿ çàäà÷ ç òðüîìà çì³ííèìè), à ãðàô³÷íå çîáðàæåííÿ çàäà÷³ ç ê³ëüê³ñòþ çì³ííèõ á³ëüøå òðüîõ âçàãàë³

íåìîæëèâå.

Ðîçãëÿíåìî çàäà÷ó.

Çíàéòè

max(min) Z = c 1 x 1 + c 2 x 2 (3.15)

çà óìîâ:

ï ï ï

+ £ = ³

{,, }.

{,, };

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:

1 2 3 4 5 6 7

Радиус и область сходимости степенного ряда

Формы и системы оплаты труда

Методы исследования

Условия интерференционного максимума и минимума

Понятие «неблагополучная семья», ее основные характеристики. Типология неблагополучных семей

Мгновенный центр скоростей (МЦС) и его определение. Определение скоростей точек тела с помощью МЦС

Самый сильный аргумент, почему эволюция человека не могла быть