Þðèäè÷åñêèé òåõíèêóì Ðàññìîòðåíî è îäîáðåíî ÏÖÊ
ã. Êðîïîòêèí ïðîãðàììèðîâàíèÿ
Ïðåäñåäàòåëü ÏÖÊ
Ïîêàëèöûíà Î.Â.
Ïëàí
÷òåíèÿ ëåêöèè ïî ó÷åáíîé äèñöèïëèíå
«Ìàòåìàòè÷åñêèå ìåòîäû»
Ðàçäåë ¹ 2. Ëèíåéíîå ïðîãðàììèðîâàíèå.
Òåìà ¹ 2.1. Âèäû çàäà÷ ëèíåéíîãî ïðîãðàììèðîâàíèÿ.
Çàíÿòèå ¹
Ó÷åáíûå è âîñïèòàòåëüíûå öåëè: èçó÷èòü îñíîâíûå âèäû çàäà÷ ëèíåéíîãî ïðîãðàììèðîâàíèÿ, èõ ìàòåìàòè÷åñêèå ìîäåëè.
Âðåìÿ
Ìåñòî ïðîâåäåíèÿ: àóäèòîðèÿ.
Ó÷åáíûå âîïðîñû: Çàäà÷à ëèíåéíîãî ïðîãðàììèðîâàíèÿ (ÇËÏ). Òðóäíîñòè ðåøåíèÿ ÇËÏ. Êëàññèôèêàöèÿ çàäà÷ îïòèìèçàöèè: çàäà÷à î ïèùåâîì ðàöèîíå, çàäà÷à î ïëàíèðîâàíèè ïðîèçâîäñòâà, çàäà÷à î çàãðóçêå îáîðóäîâàíèÿ, çàäà÷à î ñíàáæåíèè ñûðüåì.
Ëèòåðàòóðà:
1. Âåíöåëü Å.Ñ. Èññëåäîâàíèå îïåðàöèé. Çàäà÷, ïðèíöèïû, ìåòîäîëîãèÿ. – Ì.: Íàóêà, 1980.
2. Øåëîáàåâ Ñ.È. Ìàòåìàòè÷åñêèå ìåòîäû è ìîäåëè â ýêîíîìèêå, ôèíàíñàõ, áèçíåñå. – Ì.:ÞÍÈÒÈÄÀÍÀ, 2001
Ó÷åáíûå âîïðîñû è ðàñ÷åò âðåìåíè
¹ï/ï | Ó÷åáíûå âîïðîñû | Âðåìÿ, ìèí | Ìåòîäè÷åñêèå óêàçàíèÿ |
1. 2. 3. | Çàäà÷à ëèíåéíîãî ïðîãðàììèðîâàíèÿ (ÇËÏ). Òðóäíîñòè ðåøåíèÿ ÇËÏ. Êëàññèôèêàöèÿ çàäà÷ îïòèìèçàöèè. |
Ââîäíàÿ ÷àñòü. Îðãàíèçàöèîííûé ìîìåíò. Ïëàí çàíÿòèÿ. Îñíîâíûå òðåáîâàíèÿ.
Îñíîâíàÿ ÷àñòü.
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.
Öåëåâàÿ ôóíêöèÿ:
Ñèñòåìà îãðàíè÷åíèé:
a11x1+a21x2+a31x3+a41x4?b1
a12x1+a22x2+a32x3+a42x4?b2
a13x1+a23x2+a32x3+a43x4?b3
Ýòè ëèíåéíûå íåðàâåíñòâà ïðåäñòàâëÿþò ñîáîé îãðàíè÷åíèÿ, íàêëàäûâàåìûå íà ýëåìåíòû ðåøåíèÿ x1, x2, x3, x4.
Òàêèì îáðàçîì, ïîñòàâëåííàÿ çàäà÷à ñâîäèòñÿ ê ñëåäóþùåé: íàéòè òàêèå íåîòðèöàòåëüíûå çíà÷åíèÿ ïåðåìåííûõ x1, x2, x3, x4, ÷òîáû îíè óäîâëåòâîðÿëè îãðàíè÷åíèÿì – íåðàâåíñòâàì è îäíîâðåìåííî îáðàùàëè â ìèíèìóì ëèíåéíóþ ôóíêöèþ ýòèõ ïåðåìåííûõ: