Ñáîðíèê çàäà÷ ëèíåéíîãî ïðîãðàììèðîâàíèÿ îíëàéí

Þðèäè÷åñêèé òåõíèêóì Ðàññìîòðåíî è îäîáðåíî ÏÖÊ

ã. Êðîïîòêèí ïðîãðàììèðîâàíèÿ

Ïðåäñåäàòåëü ÏÖÊ

Ïîêàëèöûíà Î.Â.

Ïëàí

÷òåíèÿ ëåêöèè ïî ó÷åáíîé äèñöèïëèíå

«Ìàòåìàòè÷åñêèå ìåòîäû»

Ðàçäåë ¹ 2. Ëèíåéíîå ïðîãðàììèðîâàíèå.

Òåìà ¹ 2.1. Âèäû çàäà÷ ëèíåéíîãî ïðîãðàììèðîâàíèÿ.

Çàíÿòèå ¹

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

Âðåìÿ

Ìåñòî ïðîâåäåíèÿ: àóäèòîðèÿ.

Ó÷åáíûå âîïðîñû: Çàäà÷à ëèíåéíîãî ïðîãðàììèðîâàíèÿ (ÇËÏ). Òðóäíîñòè ðåøåíèÿ ÇËÏ. Êëàññèôèêàöèÿ çàäà÷ îïòèìèçàöèè: çàäà÷à î ïèùåâîì ðàöèîíå, çàäà÷à î ïëàíèðîâàíèè ïðîèçâîäñòâà, çàäà÷à î çàãðóçêå îáîðóäîâàíèÿ, çàäà÷à î ñíàáæåíèè ñûðüåì.

Ëèòåðàòóðà:

1. Âåíöåëü Å.Ñ. Èññëåäîâàíèå îïåðàöèé. Çàäà÷, ïðèíöèïû, ìåòîäîëîãèÿ. – Ì.: Íàóêà, 1980.

2. Øåëîáàåâ Ñ.È. Ìàòåìàòè÷åñêèå ìåòîäû è ìîäåëè â ýêîíîìèêå, ôèíàíñàõ, áèçíåñå. – Ì.:ÞÍÈÒÈÄÀÍÀ, 2001

Ó÷åáíûå âîïðîñû è ðàñ÷åò âðåìåíè

¹ï/ï

Ó÷åáíûå âîïðîñû

Âðåìÿ, ìèí

Ìåòîäè÷åñêèå óêàçàíèÿ

1.

2.

3.

Çàäà÷à ëèíåéíîãî ïðîãðàììèðîâàíèÿ (ÇËÏ).

Òðóäíîñòè ðåøåíèÿ ÇËÏ.

Êëàññèôèêàöèÿ çàäà÷ îïòèìèçàöèè.

  1. Ââîäíàÿ ÷àñòü. Îðãàíèçàöèîííûé ìîìåíò. Ïëàí çàíÿòèÿ. Îñíîâíûå òðåáîâàíèÿ.

  2. Îñíîâíàÿ ÷àñòü.

1. Çàäà÷à ëèíåéíîãî ïðîãðàììèðîâàíèÿ (ÇËÏ).

Òåðìèí ëèíåéíîå ïðîãðàììèðîâàíèå ïîÿâèëñÿ â Àìåðèêå â ñåðåäèíå 40-õ ãîäîâ (ïåðâàÿ àìåðèêàíñêàÿ ðàáîòà ïî ÷àñòíîé çàäà÷å ëèíåéíîãî ïðîãðàììèðîâàíèÿ îïóáëèêîâàíà â 1941 ã.).  Ñîâåòñêîì Ñîþçå èññëåäîâàíèÿ â ýòîé îáëàñòè íà÷àëèñü ðàíåå.  êîíöå 30-õ ãîäîâ öåëûé ðÿä ñóùåñòâåííûõ ðåçóëüòàòîâ ïî ëèíåéíîìó ïðîãðàììèðîâàíèþ áûë óñòàíîâëåí Ë.Â. Êàíòîðîâè÷åì.

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

Çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ ÿâëÿþòñÿ ñàìûìè ïðîñòûìè è ëó÷øå èçó÷åííûìè çàäà÷àìè. Äëÿ íèõ õàðàêòåðíî: ïîêàçàòåëü ýôôåêòèâíîñòè (öåëåâàÿ ôóíêöèÿ) âûðàæàåòñÿ ëèíåéíîé çàâèñèìîñòüþ; îãðàíè÷åíèÿ íà ðåøåíèÿ – ëèíåéíûå ðàâåíñòâà èëè íåðàâåíñòâà.

2. Òðóäíîñòè ðåøåíèÿ ÇËÏ.

Òðóäíîñòè ðåøåíèÿ çàäà÷ ëèíåéíîãî ïðîãðàììèðîâàíèÿ çàâèñÿò îò: âèäà çàâèñèìîñòè, ñâÿçûâàþùåé öåëåâóþ ôóíêöèþ ñ ýëåìåíòàìè ðåøåíèÿ; ðàçìåðíîñòè çàäà÷è, òî åñòü îò êîëè÷åñòâà ýëåìåíòîâ ðåøåíèÿ õ1, õ2,…, xn; âèäà è êîëè÷åñòâà îãðàíè÷åíèé íà ýëåìåíòû ðåøåíèé.

3. Êëàññèôèêàöèÿ çàäà÷ îïòèìèçàöèè.

Çàäà÷à î ðàöèîíàëüíîì ïèòàíèè (çàäà÷à î ïèùåâîì ðàöèîíå).

ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È. Ôåðìà ïðîèçâîäèò îòêîðì ñêîòà ñ êîììåð÷åñêîé öåëüþ. Äëÿ ïðîñòîòû äîïóñòèì, ÷òî èìååòñÿ âñåãî ÷åòûðå âèäà ïðîäóêòîâ: Ï1, Ï2, Ï3, Ï4; ñòîèìîñòü åäèíèöû êàæäîãî ïðîäóêòà ðàâíà ñîîòâåòñòâåííî Ñ1, Ñ2, Ñ3, Ñ4. Èç ýòèõ ïðîäóêòîâ òðåáóåòñÿ ñîñòàâèòü ïèùåâîé ðàöèîí, êîòîðûé äîëæåí ñîäåðæàòü: áåëêîâ – íå ìåíåå bi åäèíèö; óãëåâîäîâ – íå ìåíåå b2 åäèíèö; æèðîâ – íå ìåíåå b3 åäèíèö. Äëÿ ïðîäóêòîâ Ï1, Ï2, Ï3, Ï4 ñîäåðæàíèå áåëêîâ, óãëåâîäîâ è æèðîâ (â åäèíèöàõ íà åäèíèöó ïðîäóêòà) èçâåñòíî è çàäàíî â òàáëèöå, ãäå aij (i=1,2,3,4; j=1,2,3) – êàêèå – òî îïðåäåë¸ííûå ÷èñëà; ïåðâûé èíäåêñ óêàçûâàåò íîìåð ïðîäóêòà, âòîðîé – íîìåð ýëåìåíòà (áåëêè, óãëåâîäû, æèðû).

ïðîäóêò

ýëåìåíòû

áåëêè

óãëåâîäû

æèðû

Ï1

Ï2

Ï3

Ï4

A11

A21

A31

A41

A12

A22

A32

A42

A13

A23

A33

A43

Òðåáóåòñÿ ñîñòàâèòü òàêîé ïèùåâîé ðàöèîí (ò.å. íàçíà÷èòü êîëè÷åñòâà ïðîäóêòîâ Ï1, Ï2, Ï3, Ï4, âõîäÿùèõ â íåãî), ÷òîáû óñëîâèÿ ïî áåëêàì, óãëåâîäàì è æèðàì áûëè âûïîëíåíû è ïðè ýòîì ñòîèìîñòü ðàöèîíà áûëà ìèíèìàëüíà.

ÌÀÒÅÌÀÒÈ×ÅÑÊÓÞ ÌÎÄÅËÜ. Îáîçíà÷èì x1, x2, x3, x4 êîëè÷åñòâà ïðîäóêòîâ Ï1, Ï2, Ï3, Ï4, âõîäÿùèõ â ðàöèîí. Ïîêàçàòåëü ýôôåêòèâíîñòè, êîòîðûé òðåáóåòñÿ ìèíèìèçèðîâàòü, - ñòîèìîñòü ðàöèîíà (îáîçíà÷èì å¸ L): îíà ëèíåéíî çàâèñèò îò ýëåìåíòîâ ðåøåíèÿ x1, x2, x3, x4.

Öåëåâàÿ ôóíêöèÿ: [image][image]

Ñèñòåìà îãðàíè÷åíèé:

a11x1+a21x2+a31x3+a41x4?b1

a12x1+a22x2+a32x3+a42x4?b2

a13x1+a23x2+a32x3+a43x4?b3

Ýòè ëèíåéíûå íåðàâåíñòâà ïðåäñòàâëÿþò ñîáîé îãðàíè÷åíèÿ, íàêëàäûâàåìûå íà ýëåìåíòû ðåøåíèÿ x1, x2, x3, x4.

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

[image]

Çàäà÷à î ïëàíèðîâàíèè ïðîèçâîäñòâà.

ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È. Ïðåäïðèÿòèå ïðîèçâîäèò èçäåëèÿ òð¸õ âèäîâ: U1, U2, U3. Ïî êàæäîìó âèäó èçäåëèÿ ïðåäïðèÿòèþ ñïóùåí ïëàí, ïî êîòîðîìó îíî îáÿçàíî âûïóñòèòü íå ìåíå b1 åäèíèö èçäåëèÿ U1, íå ìåíå b2 åäèíèö èçäåëèÿ U2 è íå ìåíå b3 åäèíèö èçäåëèÿ U3. Ïëàí ìîæåò áûòü ïåðåâûïîëíåí, íî â îïðåäåë¸ííûõ ãðàíèöàõ; óñëîâèÿ ñïðîñà îãðàíè÷èâàþò êîëè÷åñòâà ïðîèçâåä¸ííûõ åäèíèö êàæäîãî òèïà: íå áîëåå ñîîòâåòñòâåííî b1, b2, b3 åäèíèö. Íà èçãîòîâëåíèå èçäåëèé èä¸ò êàêîå-òî ñûðü¸; âñåãî èìååòñÿ ÷åòûðå âèäà ñûðüÿ: s1, s2, s3, s4, ïðè÷¸ì çàïàñû îãðàíè÷åíû ÷èñëàìè g1, g2, g3, g4 åäèíèö êàæäîãî âèäà ñûðüÿ. Òåïåðü íàäî óçíàòü êàêîå êîëè÷åñòâî ñûðüÿ êàæäîãî âèäà èä¸ò íà èçãîòîâëåíèå êàæäîãî âèäà èçäåëèé. Îáîçíà÷èì aij êîëè÷åñòâî åäèíèö ñûðüÿ âèäà si (I= 1, 2, 3, 4), ïîòðåáíîå íà èçãîòîâëåíèå îäíîé åäèíèöû èçäåëèÿ Uj (j= 1, 2, 3). Ïåðâûé èíäåêñ ó ÷èñëà aij – âèä èçäåëèÿ, âòîðîé – âèä ñûðüÿ. Çíà÷åíèÿ aij ñâåäåíû â òàáëèöó (ìàòðèöó).

Ñûðü¸

Èçäåëèÿ

U1

U2

U3

S1

S2

S3

S4

a11

a12

a13

a14

a21

a22

a23

a24

a31

a32

a33

a34

Ïðè ðåàëèçàöèè îäíî èçäåëèå U1 ïðèíîñèò ïðåäïðèÿòèþ ïðèáûëü c1, U2 – ïðèáûëü c2, U3 – ïðèáûëü c3. Òðåáóåòñÿ òàê ñïëàíèðîâàòü ïðîèçâîäñòâî (ñêîëüêî êàêèõ èçäåëèé ïðîèçâîäèòü), ÷òîáû ïëàí áûë âûïîëíåí èëè ïåðåâûïîëíåí (íî ïðè îòñóòñòâèè «çàòîâàðèâàíèÿ»), à ñóììàðíàÿ ïðèáûëü îáðàùàëàñü â ìàêñèìóì.

ÌÀÒÅÌÀÒÈ×ÅÑÊÀß ÌÎÄÅËÜ. Ýëåìåíòàìè ðåøåíèÿ áóäóò x1, x2, x3 – êîëè÷åñòâà åäèíèö èçäåëèé U1, U2, U3, êîòîðûå ìû ïðîèçâåä¸ì. Îáÿçàòåëüíîñòü âûïîëíåíèÿ ïëàíîâîãî çàäàíèÿ çàïèøåòñÿ â âèäå òð¸õ îãðàíè÷åíèé – íåðàâåíñòâ: x1?b1, x2?b2, x3?b3.

Îòñóòñòâèå èçäåëèé ïðîäóêöèè (çàòîâàðèâàíèÿ) äà¸ò íàì åù¸ òðè îãðàíè÷åíèÿ – íåðàâåíñòâà: x1?b1, x2?b2, x3?b3.

Öåëåâàÿ ôóíêöèÿ: L=c1x1+c2x2+c3x3> max.

Ñèñòåìà îãðàíè÷åíèé:

a11x1+a21x2+a31x3??1.

a12x1+a22x2+a32x3??2.

a13x1+a23x2+a33x3??3.

a14x1+a24x2+a34x3??4.

Çàäà÷à î çàãðóçêè îáîðóäîâàíèÿ.

ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È. Òêàöêàÿ ôàáðèêà ðàñïîëàãàåò äâóìÿ âèäàìè ñòàíêîâ, èç íèõ N1 ñòàíêîâ òèïà 1 è N2 ñòàíêîâ òèïà 2. Ñòàíêè ìîãóò ïðîèçâîäèòü òðè âèäà òêàíåé: T1, T2, T3, íî ñ ðàçíîé ïðîèçâîäèòåëüíîñòüþ. Äàííûå aij ïðîèçâîäèòåëüíîñòè ñòàíêîâ â òàáëèöå (ïåðâûé èíäåêñ – òèï ñòàíêà, âòîðîé – âèä òêàíè).

Êàæäûé ìåòð òêàíè âèäà T1 ïðèíîñèò ôàáðèêå äîõîä c1, âèäà Ò2 – äîõîä ñ2, Ò3 – äîõîä ñ3.

Òèï ñòàíêà

Âèä òêàíè

Ò1

Ò2

Ò3

1

2

à11

à21

à12

à22

à13

à23

Ôàáðèêå ïðåäïèñàí ïëàí ñîãëàñíî êîòîðîìó îíà äîëæíà ïðîèçâîäèòü â ìåñÿö íå ìåíåå b1 ìåòðîâ òêàíè Ò1, b2 ìåòðîâ òêàíè Ò2, b3 ìåòðîâ òêàíè Ò3; êîëè÷åñòâî ìåòðîâ êàæäîãî âèäà òêàíè íå äîëæíî ïðåâûøàòü ñîîòâåòñòâåííî b1, b2, b3 ìåòðîâ. Êðîìå òîãî, âñå áåç èñêëþ÷åíèÿ ñòàíêè äîëæíû áûòü çàãðóæåíû. Òðåáóåòñÿ òàê ðàñïðåäåëèòü çàãðóçêó ñòàíêîâ ïðîèçâîäñòâîì òêàíåé Ò1, Ò2, Ò3, ÷òîáû ñóììàðíûé ìåñÿ÷íûé äîõîä áûë ìàêñèìàëåí.

ÌÀÒÅÌÀÒÈ×ÅÑÊÀß ÌÎÄÅËÜ. Ââåä¸ì áóêâó x ñ äâóìÿ èíäåêñàìè (ïåðâûé – òèï ñòàíêà, âòîðîé – âèä òêàíè). Âñåãî áóäåò øåñòü ýëåìåíòîâ ðåøåíèÿ: x11 x12 x13 x21 x22 x23 .

Çäåñü x11 – êîëè÷åñòâî ñòàíêîâ òèïà 1, çàíÿòûõ èçãîòîâëåíèåì òêàíè Ò1, x12 – êîëè÷åñòâî ñòàíêîâ òèïà 1, çàíÿòûõ èçãîòîâëåíèåì òêàíè Ò2 è ò.ä.

Çàïèøåì ñóììàðíûé äîõîä îò ïðîèçâîäñòâà âñåõ âèäîâ òêàíåé. Ñóììàðíîå êîëè÷åñòâî ìåòðîâ òêàíè Ò1, ïðîèçâåä¸ííîå âñåìè ñòàíêàìè, áóäåò ðàâíî a11x11+a21x21 è ïðèíåñ¸ò äîõîä c1(a11x11+a21x21).

Öåëåâàÿ ôóíêöèÿ: L=c1 (a11x11+a21x21)+c2 (a12x12+a22x22)+c3 (a13x13+a23x23) [image] > max.

Ñèñòåìà îãðàíè÷åíèé:

Îáåñïå÷èì âûïîëíåíèÿ ïëàíà îãðàíè÷åíèÿìè ïî ìèíèìàëüíûì ïàðàìåòðàì:

a11x11+a21x21?b1,

a12x12+a22x22?b2,

a13x13+a23x23?b3,

Ïîñëå ýòîãî îãðàíè÷èì âûïîëíåíèå ïëàíà ïî ìàêñèìàëüíûì ïàðàìåòðàì:

a11x11+a21x21?b1,

a12x12+a22x22?b2,

a13x13+a23x23?b3,

Òåïåðü çàïèøåì îãðàíè÷åíèÿ, ñâÿçàííûå ñ íàëè÷èåì îáîðóäîâàíèÿ è åãî ïîëíîé çàãðóçêîé. Ñóììàðíîå êîëè÷åñòâî ñòàíêîâ òèïà 1, çàíÿòûõ èçãîòîâëåíèåì âñåõ òêàíåé, äîëæíî áûòü ðàâíî N1; òèïà 2 – N2.

x11+x12+x13=N1,

x21+x22+x23=N2,

Çàäà÷à î ñíàáæåíèè ñûðü¸ì.

ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È. Èìååòñÿ òðè ïðîìûøëåííûõ ïðåäïðèÿòèÿ: Ï1, Ï2, Ï3, òðåáóþùèõ ñíàáæåíèÿ îïðåäåë¸ííûì âèäîì ñûðüÿ. Ïîòðåáíîñòè â ñûðüå êàæäîãî ïðåäïðèÿòèÿ ðàâíû ñîîòâåòñòâåííî a1, a2, a3 åäèíèö. Èìåþòñÿ ïÿòü ñûðüåâûõ áàç, ðàñïîëîæåííûõ îò ïðåäïðèÿòèé íà êàêèõ – òî ðàññòîÿíèÿõ è ñâÿçàííûõ ñ íèìè ïóòÿìè ñîîáùåíèÿ ñ ðàçíûìè òàðèôàìè. Åäèíèöà ñûðüÿ, ïîëó÷àåìàÿ ïðåäïðèÿòèåì Ïi c áàçû Áj , îáõîäèòñÿ ïðåäïðèÿòèþ â ñij ðóáëåé (ïåðâûé èíäåêñ – íîìåð ïðåäïðèÿòèÿ, âòîðîé – íîìåð áàçû).

Ïðåäïðèÿòèÿ

Áàçû

Á1

Á2

Á3

Á4

Á5

Ï1

Ï2

Ï3

Ñ11

Ñ21

Ñ31

Ñ12

Ñ22

Ñ32

Ñ13

Ñ23

Ñ33

Ñ14

Ñ24

Ñ34

Ñ15

Ñ25

Ñ35

Âîçìîæíîñòè ñíàáæåíèÿ ñûðü¸ì ñ êàæäîé áàçû îãðàíè÷åíû å¸ ïðîèçâîäñòâåííîé ìîùíîñòüþ: áàçû Á1, Á2, Á3, Á4, Á5 ìîãóò äàòü íå áîëåå b1, b2, b3, b4, b5 åäèíèö ñûðüÿ. Òðåáóåòñÿ ñîñòàâèòü òàêîé ïëàí ñíàáæåíèÿ ïðåäïðèÿòèé ñûðü¸ì (ñ êàêîé áàçû, êóäà è êàêîå êîëè÷åñòâî ñûðüÿ âåçòè), ÷òîáû ïîòðåáíîñòè ïðåäïðèÿòèé áûëè îáåñïå÷åíû ïðè ìèíèìàëüíûõ ðàñõîäàõ íà ñûðü¸.

ÌÀÒÅÌÀÒÈ×ÅÑÊÀß ÌÎÄÅËÜ. Îáîçíà÷èì xij êîëè÷åñòâà ñûðüÿ ñ j – îé áàçû. Âñåãî ïëàí áóäåò ñîñòîÿòü èç 15 ýëåìåíòîâ ðåøåíèÿ: x11 x12 x13 x14 x15 x21 x22 x23 x24 x25 x31 x32 x33 x34 x35.

Öåëåâàÿ ôóíêöèÿ: [image]

Ñèñòåìà îãðàíè÷åíèé:

x11+x12+x13+x14+x15=a1,

x21+x22+x23+x24+x25=a2,

x31+x32+x33+x34+x35=a3,

x11+x21+x31?b1,

x12+x22+x32?b2,

x13+x23+x33?b3, (4.3.)

x14+x24+x34?b4,

x15+x25+x35?b5,





Ïîõîæèå êóðñîâûå ðàáîòû

1. Ðåøåíèå çàäà÷ ëèíåéíîãî ïðîãðàììèðîâàíèÿ îíëàéí

2. Å îíëàéí ðåøåíèå çàäà÷ ñèìïëåêñíûì ìåòîäîì

3. Ðåøåíèå çàäà÷ ïî ïðîãðàììèðîâàíèþ ëï îíëàéí

4. Ðåøåíèå çàäà÷ ïî ãðàæäàíñêîìó ïðàâó îíëàéí

5. Íåòòî ñòàâêà â ñòðàõîâàíèè ðåøåíèå çàäà÷

6. Êðèâàÿ ïðîèçâîäíûõ âîçìîæíîñòåé ðåøåíèå çàäà÷

7. Ìèíèìóì ñðåäíèõ èçäåðæåê ðåøåíèå çàäà÷

8. Îðòîíîðìèðîâàííûé áàçèñ ðåøåíèå îíëàéí

9. Ãðàæäàíñêîå ïðàâî ðåøåíèå çàäà÷

10. Îíëàéí ðåøåíèå äâîéñòâåííîé çàäà÷è

11. Ðåøåíèå äâîéñòâåííîé çàäà÷è îíëàéí

12. Îíëàéí ðåøåíèå çëï ãðàôè÷åñêèì ìåòîäîì

13. Ãðàæäàíñêîå ïðàâî ïðàêòèêóì ðåøåíèå çàäà÷ ÷

14. Ðåøåíèå áîëüøîé äâîéñòâåííîé çàäà÷è îíëàéí

15. Òðóäîâîå ïðàâî ðåøåíèå çàäà÷ ñ îòâåòàìè

Êóðñîâûå ðàáîòû, ðåôåðàòû è äîêëàäû