ӘЛ-ФАРАБИ АТЫНДАҒЫ ҚАЗАҚ ҰЛТТЫҚ УНИВЕРСИТЕТІ
Экономика және бизнес факультеті
Экономикалық процестерді модельдеу кафедрасы
КУРСТЫҚ ЖҰМЫС
ЭКОНОМИКАЛЫҚ ПРОЦЕСТЕРДІ ЗЕРТТЕУДЕГІ СЫЗЫҚТЫҚ БАҒДАРЛАМАЛАУ МОДЕЛЬДЕРІ
Орындаған
4 курс студенті:
Ғылыми жетекші:
Алматы 2003
МАЗМҰНЫ
КІРІСПЕ.………………………………………………………………………………………...3
І БӨЛІМ. ТЕОРИЯЛЫҚ БӨЛІМ……………………………………………………………...............................................4
Жоспарлау мен басқарудағы оптималдылық қағидасы және оптималды бағдарламалаудың
Сызықтық бағдарламалау есебі және оның шешімдерінің қасиеттері……….............8
Сызықтық бағдарламалау есебін графиктік әдіспен шешу...........................................9
Сызықтық бағдарламалау есебін шешудің симплекстік әдісі.....................................10
Қарапайым базисті симплекс әдісі…………………………….........................10
Жасанды базисті симплекс әдісі (М-есебі)……………………........................14
Сызықтық бағдарламалаудың екі жақты есептері……………………........................16
ІІ БӨЛІМ. ПРАКТИКАЛЫҚ БӨЛІМ…………………………………...............................19
ҚОРЫТЫНДЫ…………………………………………………...............................................25
ПАЙДАЛАНЫЛҒАН ӘДЕБИЕТТЕР…………………………………………....................26
КІРІСПЕ
Өзінің мүмкіндіктерін тиімді пайдалану арқылы жоғары нәтижеге жету
Оптимизациялық есептерде математикалық әдістерді пайдалану үшін, ең алдымен,
Математикалық модель құру үшін, ең алдымен, зерттейтін объектінің
Экономикалық процестердің математикалық модельдерін құрастыру өте күрделі мәселе,
Оптимизациялау теориясында мүмкін болатын шешімдердің ішінен мақсат функциясы
Осындай есептердің қойылымы мен шығару әдістері мақсат функциясының
Мақсат функциясы мен мүмкін шешімдер жиынын сипаттайтын функциялар
Бұл курстық жұмыста сызықтық бағдарламалау есептерінің қойылымдарының математикалық
І БӨЛІМ. ТЕОРИЯЛЫҚ БӨЛІМ
Жоспарлау мен басқарудағы оптималдылық қағидасы және оптималды бағдарламалаудың
Сызықтық бағдарламалау оптималды бағдарламалаудың бір бөлімі болып табылады.
Жоспарлау мен басқаруда оптималдылық қағидасын қолданудың маңызды шарты
Оптималдылық қағидасының мәні – шаруашылық жүргізуші субъектінің өндірістік
Мұндағы «ең жақсы жолмен» сөздері оптималдылықтың қандай да
«Өндірістік қызметтің ішкі мүмкіндіктері мен сыртқы жағдайларын айқындайтын»
Сонымен, жоспарлау мен басқаруда оптималдылық қағидасының тәжірибеде қолданылуы
X ∊ D, (1.2)
f (X) → max (min), (1.1)
мұнда f (X) – оптималды критерийдің математималық түрде
Мына шектемелерді (шарттарды) қанағаттандыратын:
φ1 (x1, x2, …, xn) {≤ ,=, ≥}
φ1 (x1, x2, …, xn) {≤ ,=, ≥}
………………………………… (1.4)
φm (x1, x2, …, xn) {≤ ,=, ≥}
xj ≥ 0, j = ,
және
f (X) = f (x1, x2, …, xn)
функциясының максимум немесе минимум мәнін табу.
(1.5) шарты міндетті емес, бірақ оған қажетті жағдайда
φi (x1, x2, …, xn) {≤ ,=, ≥}
xj ≥ 0, j = ,
f (x1, x2, …, xn) → max (min)
(1.6) – (1.8) есеп – оптималды (математикалық) бағдарламалаудың
X векторы (басқарушы айнымалылар жиынтығы xj , j
Сонымен, белгілі бір өндірістік жағдайдағы оптималды жоспар таңдау
Оптималды бағдарламалау есебін жалпы түрде мынадай белгілері бойынша
Айнымалылардың өзара байланысу мінездемесі бойынша:
а) сызықтық;
ә) сызықтық емес.
а) жағдайында шектемелер жүйесіндегі барлық функционалдық байланыстар мен
Айнымалылардың өзгеру мінездемесібойынша:
а) үздіксіз;
ә) дискретті.
а) жағдайында басқарушы айнымалылар мәндері қандай да бір
Уақыт факторын ескеру арқылы:
а) статикалық;
ә) динамикалық.
а) есептерінде модельдеу мен шешім қабылдау модель элементтерінің
Айнымалылар туралы ақпараттар бойынша:
а) толық анықталғандық (детерминделгендік) жағдайындағы есептер;
ә) ақпараттың жеткіліксіз жағдайындағы есептер;
б) анықталмағандық жағдайындағы есептер.
ә) есептерінде жеке элементтері ықтималды мүмкін шамалар болып
Баламаларды бағалау критерийлерінің саны бойынша:
а) жай, бір критерийлі есептер;
ә) күрделі, бірнеше критерийлі есептер.
а) есептерін экономикалық тұрғыдан қарастырсақ, бір критерийлі
1 – 5 белгілерінің жиынтығы оптималды бағдарламалау есептері
Сызықтық бағдарламалау есебі және оның шешімдерінің қасиеттері
Берілген ресурстарды (қорларды) тиімді пайдалану арқылы қосымша пайданы
Мына шектемелерді қанағаттандыратын:
a11x1 + a12x2 + … + a1nxn {≤
a21x1 + a22x2 + … + a2nxn {≤
………………………………………… (2.2)
am1x1 + am2x2 + … + amnxn {≤
xj ≥ 0, j =
және
f (x) = c1x1 + c1x1 + …
мақсат функциясына максимум (немесе минимум) мәнін беретін n
Мұндағы aij, bi, cj - берілген тұрақты сандар,
Экономикалық есептердің қойылу ерекшеліктеріне және математикалық зерттеулердің ыңғайына
Мынадай түрде жазылған қойылымдар практикада жиірек кездеседі:
Матрицалық қойылым:
Мына шектемелерді қанағаттандыратын:
AX = B,
x ≥ 0
және
f (x) → max (min)
мәнін беретін x = (x1, x2, …, xn)
Мұндағы A = (aij)mxn – m жатық (көлбеу)
B = (b1, b2, …, bm) – m
C = (c1, c2, …, cn) – n
Векторлық қойылым:
Мына шектемелерді қанағаттандыратын:
= b
xj ≥ 0, j = 1, 2, …,
және
f (x) = → max (min)
мәнін беретін x = (x1, x2, …, xn)
Мұндағы Pj = – A
Енді сызықтық бағдарламалау есебінің қасиеттерін тұжырымдауға қажетті бірнеше
Бірінші анықтама. (2.2) және (2.3) шектемелерді қанағаттандыратын n
Екінші анықтама. Егер мына жіктемедегі
P1, P2, …, Pk – векторлары сызықты тәуелсіз
m компонентті векторлардан құралған сызықты тәуелсіз векторлардың саны
Үшінші анықтама. Оң компоненттерінің саны m-ге тең болатын
Төртінші анықтама. (2.1) – (2.3) сызықтық бағдарламалау есебінің
Енді осы анықтамалар негізінде сызықтық бағдарламалау есебінің шешімдер
Сызықтық бағдарламалау есебінің жоспарлар жиыны әруақытта да дөңес
Сызықтық бағдарламалау есебінің оптималдық жоспары мүмкіндік шешімдер жиынының
Егер P1, P2, …, Pk векторлар жүйесі сызықты
P1x1 + P2x2 + …+ Pk xk =
xj ≥ 0, i =1, 2, …, k,
онда x = (x1, x2, …, xk, 0,
Керісінше, егер x = (x1, x2, …, xn)
Осыдан x = (x1, x2, …, xn) нүктесінің
m компонентті P1, P2, …, Pn векторларынан құралған
Сонымен, кез келген x = (x1, x2, …,
= b
xj ≥ 0, i =1, 2, …, m.
Сызықтық бағдарламалау есебін графиктік әдіспен шешу
Егер сызықтық бағдарламалау есебі екі айнымалылы шектемелермен берілетін
Мына шектемелерді қанағаттандыратын:
(3.2)
(3.3)
және
(3.1)
мақсат функциясына максимум (немесе минимум) мәнін беретін
Сызықтық бағдарламалау есебін графиктік әдіспен шешу келесі қадамдардан
Бірінші қадам. Ең алдымен координаттар
.
Екінші қадам. максимумға ұмтылған жағдайда
Үшінші қадам. Максимум нүктесінің координаттарын табу үшін өзара
функциясын минимумдау жағдайында түзуін вектор-градиентке
Сызықтық бағдарламалау есебін шешудің симплекс әдісі
Есеп векторлық түрде қойылған болсын:
Мына шектемелерді қанағаттандыратын:
(4.2)
(4.3)
және
(4.1)
мақсат функциясына максимум (минимум) мәнін беретін
(4.1) – (4.3) түрінде қойылған сызықтық бағдарламалау есебінің
Осылайша көшу барысында мақсат функциясының мәні біртіндеп өсіп
Осы есептеу процесін іске асыру барысында кезекті қадамда
Бірінші, мақсат функциясының жаңадан табылған шеткі нүктедегі мәні
Екіншіден, жаңадан табылған шеткі нүктенің оптималдық шешім еместігін
Қарапайым базисті симплекс әдісі
Есеп векторлық түрде қойылған болсын:
Мына шектемелерді қанағаттандыратын:
(4.2.2)
(4.2.3)
және
(4.2.1)
мақсат функциясына максимум (минимум) мәнін беретін
Мұндағы - компонентті тік жолдық
- векторларынан құралған кез келген
Бірлік матрицаға сәйкес келетін кері
(4.2.4)
(4.2.5)
мұрдағы
базисі бірлік матрицасы болғандықтан, (4.2.5)
.
Сонда
(4.2.6)
(4.2.7)
Енді тіректі шешімінің оптималдығын тексеруге
Симплекс кестесі
1-кесте. Есептеу процесінің алғашқы қадамы (итерациясы).
i базис c b c1 c2 … cl
P1 P2 … Pl … Pm Pm+1 …
1 P1 c1 x1 1 0 … 0
2 P2 c2 x2 0 1 … 0
… … … … … … … …
l Pl cl xl 0 0 … 1
… … … … … … … …
m Pm cm xm 0 0 … 0
m+1 Δ j
z0 0 0 … 0 … 0 Δ
Тіректі шешімнің базистік (оң) компоненттері ,
Ал кестенің соңғы -ші жолының торларына
Осы бағаларының ішінде ең болмағанда
,
яғни векторын базиске енгізу арқылы
Ескі базистен шығарылатын вектордың нөмірі мына өрнек бойынша
яғни базистік векторларының ішінен
Симплекс кестесінің келесі итерациядағы элементтері есептеу геометриялық тұрғыдан
1.
- жіктелу коэффициенттерін
есептеу үшін.
2.
- жаңа базистік компоненттерін
есептеу үшін.
3.
- Мақсат функциясының жаңа тіректі
жоспардағы мәнін есептеу үшін.
- тік жолдарының жаңа базиске
сәйкес келетін бағаларын есептеу
үшін.
(4.2.12) – (4.2.14) формулаларының есептеу схемалары матрицаның
Сонымен, белгілі бір итерацияға сәйкес симплекс кестесінің барлық
Симплекс кестесінің -ші жолында жазылған
Егер -дің белгілі мәндерінде
өрнегі бойынша анықталған векторы ескі
Базиске енгізілетін тік жолы мен
Соның нәтижесінде жаңа тіректі жоспар және оған сәйкес
1 – 4 кезеңдерде көрсетілген түрлендірулер арқылы тіректі
2-кесте. Есептеу процесінің екінші итерациясы.
i Базис c b c1 c2 … cn
P1 P2 … Pl … Pm Pm+1 …
1 P1 c1 x11 1 0 … x11l
2 P2 c2 x12 0 1 … x12l
… … … … … … … …
Pk ck x1k 0 0 …
… … … … … … … …
Pm cm x1m 0 0 … x1ml …
m+1 Δ j
z10 0 0 … 0 … 0 Δ1m+1
Жасанды базисті симплекс әдісі (M-есебі)
Сызықтық бағдарламалау есебінің қойылымында бірлік базис болмаған жағдайда
Сызықтық бағдарламалау есебі мына түрде қойылған болсын:
a11x1 + a12x1 + … + a1nx1 =
a21x1 + a22x1 + … + a2nx1 =
…………………………………… (4.3.2)
am1x1 + am2x1 + … + amnx1 =
(4.3.3)
шарттарын қанағаттандыратын және
(4.3.1)
мақсат функциясына максимум (минимум) мәнін беретін
Жалпы жағдайда матрицасының тік жолдарының
(4.3.5)
(4.3.6)
шарттарын қанағаттандыратын және
(4.3.4)
мақсат функциясына максимум (минимум) мәнін беретін
Мұндағы айнымалысының шамасы өте үлкен
Егер тік жолдық векторларын енгізсек,
Сонда векторлары жасанды базис деп
Егер (4.3.1) – (4.3.3) түрде қойылған есептің ең
Кеңейтілген есептің құрамында жасанды бірлік базистың болуы ол
Егер алғашқы қойылымдағы (4.3.1) – (4.3.3) есептің бірде-бір
векторы кеңейтілген есептің алғашқы тіректі шешімі болады.
- (4.3.4) мақсат функциясының коэффициент-терінен құралған вектор,
Алғашқы базис бірлік матрица болғандықтан,
Сондықтан жолының бағасы былайша өрнектеледі:
(4.3.7)
(4.3.7) баға өрнегі өзара тәуелсіз екі бөліктен тұрады.
Сондықтан симплекс кестесінің көршілес және
Ол үшін жолының
Ал айнымалыларының ешқайсысы базистік компонент
Бұл жағдайда жатық жол элементтері
3-кесте. Жасанды базис әдісін есептеу процесінің нөлінші итерациясы.
базис
… …
1
2
… … … … … … … …
… …
… … … … … … … …
… …
1 0
…
0 0 … 0 … 0
Сызықтық бағдарламалаудың екі жақты есептері
Сызықтық бағдарламалаудың әр бастапқы есебіне сәйкес басқа екінші
Мынадай мысал қарастырайық: қандай да бір ұйым бір
Әрине, сатып алушы ұйым барлық ресурсқа
(5.1)
Екінші жағынан, ресурстарын сатушы кәсіпорын да өз кезегінде
Бірінші (бастапқы) есеп Екінші (жақты) есеп
a11 x1 + a12 x2 + a13 x3
a21 x1 + a22 x2 + a23 x3
a31 x1 + a32 x2 + a33 x3
…………………………………………………
am1 x1 + am2 x2 + am3 x3
шектемелерін қанағаттандыратын және
теріс еместік шарты орындалатын
мақсат функциясының ресурстарды тұтыну олардың әрқайсысы бойынша бар
a12 y1 + a22 y2 + a32 y3
a13 y1 + a23 y2 + a33 y3
………………………………………………
a1n y1 + a2n y2 + a3n y3
шектемелерін қанағаттандыратын және
теріс еместік шарты орындалатын
мақсат функциясының әр өнімді өндіруге қажетті ресурстардың шығындары
Өндірісте өнімнің белгілі бір түрін шығаруға кететін шекті
a11 y1 + a21 y2 + a31 y3
Осылайша әр өнім түріне сәйкес шектемелерді жазуға болады.
Енді формалды түрде кестеде көрсетілген сызықтық бағдарламалаудың екі
Бір есепте сызықтық функцияның максимумы ізделсе, келесісінде минимумы
Бірінші есептегі сызықтық функция айнымалыларының коэффициенттері екінші есепте
Максимумдау есептерінде шектеме-теңсіздіктердің таңбалары « » болса,
Екі есептің де шектемелер жүйесіндегі айнымалылар коэффициенттерінің матрицалары
I есеп үшін II есеп
Бірінші есептегі шектмелер жүйесіндегі теңсіздіктер саны екінші есептегі
Екі есепте де теріс еместік шарты орындалады.
Осындай қасиетттерге ие сызықтық бағдарламалаудың екі есебін (I
ІІ БӨЛІМ. ПРАКТИКАЛЫҚ БӨЛІМ
1-МЫСАЛ.
А және Б түрлі карамельдер шығару үшін кондитер
Технологиялық нормалар бойынша А түрлі карамельдің бір қорабын
Фабрикадағы сәйкес шикізат қорлары (запастары) – 28 кг,
Фабрика А түрлі карамельдің әрбір қорабын сатқаннан 400
Осы есептің шешімін табуүшін алдымен оның математикалық моделін
Қойылған шарттарға сәйкес мынадай математикалық есеп шығады:
Мына шектемелерді қанағаттандыратын:
3,5x1 + 8x2 ≤ 28
7x1 + 3x2 ≤ 21
8x1 + 7x2 ≤ 28
x1 ≥ 0, x2 ≥ 0
және
f(x1, x2) = 400x1 + 300x2 → max
мақсат функциясының максимум мәнін беретін x = (x1,
Осылайша қойылған (1.2) және (1.3) шарттарды қанағаттандыратын шешімдердің
Енді осы есепті графиктік әдіс арқылы шешейік. Ең
3,5x1 + 8x2 – 28 = 0
7x1 + 3x2 – 21 = 0
8x1 + 7x2 – 28 = 0
Енді түзулер бөлетін қажетті шешімдер жарты жазықтығын анықтау
Барлық теңсіздіктер үшін жалпы облысты штрихтаймыз да, дөңес
, x1 = 0,71, x2 = 3,19
Мысалы, C нүктесі (II және III түзулердің қиылысу
, x1 = 2,52, x2 = 1,12
Сонымен, OABCD дөңес көпбұрышының төбелерінің координаттары мынадай: O(0;0),
1-сурет.
Енді қозғалыс бағытын анықтау үшін
Ендігі кезекте OABCD дөңес көпбұрышының төбелерінің координаттарының мәндерін
f(O) = 400 ∙ 0 + 300 ∙
f(A) = 400 ∙ 0 + 300 ∙
f(B) = 400 ∙ 0,71 + 300 ∙
f(C) = 400 ∙ 2,52 + 300 ∙
f(D) = 400 ∙ 3 + 300 ∙
Осыдан шығатыны f(x) мақсат функциясы өз максимумына C
2-МЫСАЛ.
Кәсіпорын А1 және А2 өнімдерін өндіру үшін екі
4-кесте.
Шикізат Өнім данасын өндіруге кеткен шығын, кг/дана
Шикізат саны, кг
А1 А2
Б1
Б2 2
3 5
4 250
240
Өнім данасын сатудан түскен пайда, мың тг./дана
5
6
–
«Максимум пайда» критерийі бойынша өндіріс жоспарын құру керек.
Шешуі. А1 өнімінің өндіріс көлемін x1 деп, ал
2x1 + 5x2 ≤ 250,
3x1 + 4x2 ≤ 240, (2.2)
x1 ≥ 0, x2 ≥ 0
шектемелерін қанағаттандыратын
f(x) = 5x1 + 6x2 → max (2.1)
Қосымша x3 және x4
немесе
2x1 + 5x2 + x3 = 250,
3x1 + 4x2 + x4 = 240,
xj ≥ 0, j = 1, 2, 3,
f(x) = 5x1 + 6x2 + 0x3
Есептің тіректі шешімі – (0,0,250,240) және оны симплекс
5-кесте.
i базис c b 5 6 0 0
P1 P2 P3 P4
1 ←P3 0 250 2 5 1
0
2 P4 0 240 3 4 0 1
3 Δ j = zj - cj
1 →P2 6 50 2/5 1 1/5 0
1
2 ←P4 0 40 7/5 0 -4/5
3 Δ j – 300 -13/5 0 6/5
1 P2 6 270/7 0 1 3/7 -2/7
2
2 →P1 5 200/7 1 0 -4/7 5/7
3 Δ j – 1580/7 0 0 -2/7
Келесі тіректі жоспарға P2 базисін енгізу арқылы көшеміз,
3-МЫСАЛ.
Фирма төрт (I, II, III және IV) сортты
6-кесте.
Тыңайтқыштар Тыңайтқыш данасын өндіруге кеткен шығын, фунт/дана Шикізат
I сорт II сорт III сорт IV сорт
Азот
Фосфор
Калий 3
2
1 2
1
3 1
4
3 4
3
2 20
16
15
Тыңайтқыш данасын сатудан түскен пайда, мың тг./дана
10
14
15
8
–
«Максимум пайда» критерийі бойынша өндіріс жоспарын құру керек.
Осы есептің математикалық моделін құрайық.
Мына шектемелерді қанағаттандыратын:
3x1 + 2x2 + x3 + 4x4 =
2x1 + x2 + 4x3 + 3x4 =
x1 + 3x2 + 3x3 + 2x4 =
xj ≥ 0, j = 1, 2, 3,
және
f(x) = 10x1 + 14x2 + 15x3
Берілген есептің (3.2) теңдеулер жүйесінде бірлік базис болмағандықтан,
Мына шектемелерді қанағаттандыратын:
3x1 + 2x2 + x3 + 4x4 +
2x1 + x2 + 4x3 + 3x4 +
x1 + 3x2 + 3x3 + 2x4 +
xj ≥ 0, j = 1, 2, …,
және
F(x) = f(x) – M(x5 + x6 +
= 10x1 + 14x2 + 15x3 + 8x4
Енді осы есепті жасанды базисті симплекс әдісімен шешейік
7-кесте.
i базис c b 10 14 15 8
P1 P2 P3 P4 P5 P6 P7
1 ←P5 -M 20 3 2 1
0
2 P6 -M 16 2 1 4 3
3 P7 -M 15 1 3 3 2
4 Δ j 1 0 -10 -14 -15
5
M -51 -6 -6 -8 -9 0 0
1 →P4 8 5 3/4 1/2 1/4 1
1
2 ←P6 -M 1 -1/4 -1/2 13/4
3 P7 -M 5 -1/2 2 5/2 0
4 Δ j 1 40 -4 10 -13
5
M -6 3/4 -3/2 -23/4 0 9/4 0
1 P4 8 4/13 10/13 7/13 0 1
2
2 →P3 15 4/13 -1/13 -2/13 1 0
3 ←P7 -M 5/13 -4/13 31/13 0
4 Δ j 1 44 -5 -12 0
5
55/13 4/13 31/13 0 0 0 23/13 0
1 ←P4 8 123/31 26/31 0 0
3
2 P3 15 234/403 -3/31 0 1 0
3 P2 14 55/31 -4/31 1 0 0
4 Δ j 1 234/403 -203/31 0 0
5
M 0 0 0 0 0 1 1
1 ←P4 8 123/31 26/31 0 0
31
2 P3 15 234/403 -3/31 0 1 0
3 P2 14 55/31 -4/31 1 0 0
4 Δ j 1 234/403 -203/31 0 0
1 →P1 10 123/36 1 0 0 31/26
4
2 P3 15 27/26 0 0 1 3/26
3 P2 14 31/13 0 1 0 2/13
4 1 2503/26 0 0
Жоғарыдағы кесте бойынша төрт жолдан тұратын симплекс кестесі
ҚОРЫТЫНДЫ
Сонымен, қорыта келгенде, мынадай тұжырым жасауға болады: «Оптимизациялау
Практикалық бөлімде қарастырылған есептерден мынадай нәтижелер алынды:
1-мысал бойынша:
мақсат функциясы өз максимумына нүктесінде
2-мысал бойынша:
Кәсіпорын үшін ең оптималды жоспар – (200/7,270/7,0,0), яғни
3-мысал бойынша:
Фирма үшін ең оптималды жоспар –
ПАЙДАЛАНЫЛҒАН ӘДЕБИЕТТЕР
Федосеев В. В. и др. Экономико-математические методы и
Оспанов С.С. Экономикадағы сызықтық оптимизациялық модельдер. – Алматы:
Кантарович Л.В., Горстко А.Б. Оптимальные решения в экономике.
Гасс С.Н. Линейное программирование. – М., 1961.
11