Симплекс әдісімен есеп шығару

Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 13 бет
Таңдаулыға:

ЖОСПАР

І. Кіріспе

ІІ. Негізгі бөлім

2.1.Симплекс әдісі

2.2.Симплекс әдісімен есеп шығару

2.3.Жасанды базисі бар симплекс әдісі

2.4.Экономикалық-математикалық модельдердің жалпы

мәселелері

2.5. Математикалық модельдеу

2.6. Модельдеу әдісі

ІІІ. Қорытынды

ІV. Пайдаланылған әдебиеттер

КІРІСПЕ

К. Маркстің Ғылым математиканы пайдалануға мүмкіндігі болса кемелдікке
Қазақстанда жүргізлеетін макроэкономикалық саясатты, белең алған макро-микроэкономикалық
Президент Н.Ә. Назарбаев Л.Н. Гумилев атындағы Еуразия ұлттық
Қазіргі таңда математикалық әдістер қайсыбір дәрежеде пайдаланылмайтын адамзат
Біздің ойымызша, осы жағдайды төмендегі себептермен түсіндіруге болады:

Экономикалық үдерістер әжептәуір шамада ретсіз, басқарусыз өрбиді.
Экономика саласы мамандарының, әдетте, математикалық

жалпы, атап айтқанда, математикалақ модельдеу мәселелері бойынша
Математикалық модельдеу саласындағы мамандардың қолында экономикалық үдерістің нысандандырылған
Симплекс әдісі

Сызықтық бағдарлама есебінің оңтайлы шешімдері көпбұрыштың бұрыштық нүетелерімен
Алғашқы жоспар құру. Сызықтық бағдарлама есебі қойылған болсын.
F=C1X1+ C2X2+... +CnXn
мына шектеулерде

а11х1+ а21х2+... +а1nхn=В1
а21х1+ а22х2+... +а2nхn=В2
... ... ... ... ... ... ... ... ... ... ...
аm1х1+ аm2х2+... +аmnхn=Вm
мұнда,
хj=0, (i=1,2,...,m).
Шектеу жүйесінің m бірлік векторлары болсын деп ұйғарсақ,
F=C1X1+ C2X2+... +CnXn ,
мына шектеулерде
X1+a11,m+1Xm+1+a11,m+2Xm+2+...+a11. nxn=B11
X2+a2,m+1Xm+1+a2,m+2Xm+2+...+a12.nx n=B12
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
Xm+a1m,m+1Xm+1+a1m,m+2Xm+2+...+a1m. nxn=B1m
хj=0, j=1,2,...,n.
Жүйені (5,5) векторлық формада жазамыз:
x1A1+x2A2+...+xmAm+xm+1Am+1+xnAn=B
А1, А2,...,Аm векторлар - m өлшемді кеңістіктің сызықтық
Хо=(х1=в1; х2=в2; ... хm=вm; хm+1=0;
Жоғарыдағы (5.7)-ден (5.8) жоспарды ескерсек, төмендегі жіктеу шығады:

x1А1+х2А2+... + хm,Аm = В,
мұнда А1, А2, ...А m векторлар сызықтық тәуелсіз,
1-анықтама. Еркін белгісіздердің нөл мағыналарына сәйкес келетін шектеулер
Бастапқы негізге алынатын жоспарға (5.9) сүйене отырып, екінші
Х1,m+1А1+Х2,m+1А2+... + Хm,m+1Аm =Аm+1
Жүйенің оң жағы В бөлікті осы айнымалының оң
Оңтайлылық талаптары. СБ есебінің базистік шешімі бар деп
x1 А1+х2А2+... + хmАm = В,
х1С1+х2С2+... + хmСm = Ғ,
мұнда барлық хj=0, j=1,2,...,n., ал Ғ-осы жоспарға сәйкес
Оңтайлылық өлшемі бағдарламадан шығарылатын қызметтің құнының сомасына тең
cj - мақсат функциясының белгісіздер коэффициенттері. Төмендегі теоремалар
1-теорема. Егер кейбір Аj векторы үшін төмендегі талап
Fj-Cj=0,
онда Хо жоспары функцияның максимумы үшін оңтайлы болып
2-теорема. Егер кейбір Аj векторы үшін төмендегі талап
Сөйтіп, мәселені симплекс әдіспен шешу мына сызба бойынша
1) базистік шешім құрылады;
Осы әдіспен есептеулер қайталана отырып, іріктеу нәтижесінде ең
Симплекс әдісі алгоритмі

Симплекс әдістің кестедегі алгоритмін қарастырайық. Есепті максимумға қарастырамыз.
Симплекс-кесте
№ Базис Оң жағы, вi Айнымалылар
x1 х2... хm
1 xm+1 b1 a11 a12 a1m
2 xm+2 b2 A21 a22 a2m
... ... ... ... ...
m xm+n bm Am1 am2 a1m
m+1 Fj-Cj 0 c1 c2
1. Алғашқы базистік жоспарды құру.
Симплекс әдіспен шешілетін есептің шектеулер жүйесі Мұнда хn+I - базистік айнымалылар, хj- еркін
Енді симплекс әдісінің орындалу ретін(алгоритмін) кестеде қарастырайық.
1)Симплекс кесте құрамыз. Кесте шектеулер жүйесі коэффициенттерінен және
2) Оңтайлылықты тексеру. Индекстік жолда теріс санның бар-жоғын
3)Бағыттаушы баған мен жолды анықтау. Бағыттаушы баған мен
4)Жаңа негізге алынатын жоспар кұру. Бағыт беруші жол
Эн=Эс-

5)Немесе төмендегі формулалар бойынша:
В1= (ві-(вгаrk)аіk болса і r
а'ij= (аij-аrjark)аіk болса і=r ; аrjаrk болса і=r)
Ғ'о=Ғо- (bгrаrk) k; j=А,-
Барлық осы сандар жаңа симплекс кестеде жазылады.
6)Табылған жаңа базистің оңтайлылығын тексеру. Егер жоспар оңтайлы
СИМПЛЕКС ӘДІСІМЕН ЕСЕП ШЫҒАРУ
Симплекстік әдіс сызықтық бағдарламалау есептерін шешудің әмбебап әдісі
Есеп. Еңбек ресурстарының мына мөлшері, яғни 2700 адам
Есептің мақсаты. Дәнді дақылдардың, қант қызылшасының және күнбағыс
Есептің шешуі. Бастапқы деректер 1-кестеде келтірілген.
1-кесте
Ауыл шаруашылығы дақылдары Еңбек шығындары, адам-күн тыңайтқыш ц.
Дәнді дақылдар
Қызылша
Күнбағыс 1
20
0,9 1,7
4
1,6 200
350
300
Есептің шешімі экономикалық - математикалық модельді құрудан басталады.
Х1-дәнді дақылға бөленген егістік көлемі, га
Х2-қызылшаға бөлінген егістік көлемі, га
Х3-күнбағысқа бөлінген егістік көлемі, га
Шектеулер жүйесі шартқа негізделіп жазылады, оған сәйкес ресурстардың
Мақсат функциясы ауыл шаруашылығы дақылдарын сатудан түсетін жалпы
Zmin=200Х1+350Х2+300Х3, (5.16)
сондай-ақ мәселенің экономикалық мағынасынан олардың айнымалылардың теріс емес
Х, 0, Х2 0, Х3
Шектеулер жүйесіне (5.15)-(5.17) теріс
(5.18)
Х4, Х5, Х6 қосымша айнымалылар - егістіктің (Х4),
Толықтай пайдаланылмаған ресурстар ешқандай кіріс әкелмейді және сондықтан
Zmах=200Х1+350Х2+300Хз+0Х4+0Х5+0Х6
Симплекс әдіс бірінші (бастапқы) базистік шешімді тапқанда да,
Оның идеясы мынада. Канондық формадағы шектеулер жүйесінде осы
Қарастырылған есептің бірінші базистік шешімін табамыз.
Осы жоспар өнім шығарылмайтын, ресурстар пайдаланылмайтын және пайданың
Есептеулер жүргізуге қолайлы болу үшін есептің моделі кестеде
2-кесте
№ базис bi X1 X2 X3 X4 X5
1 X4 580 1 1 1 1 0
2 X5 2700 1 20 0.9 0 1
3 X6 1200 1.7 4 1.6 0 0
4 F 0 -200 -350 -300 0 0
Симплекс кестеде базистік айнымалылардың арнайы бағаны енгізіледі және
Бірінші кесте есептің моделі жазылған канондық формадан тікелей
Ғ - 200х1, - 350х2 - З00хз -
Соңғы жол бағалау немесе индекстік болып табылады. Екінші
Есеп максимумге шешкенде индекстік жолда теріс сандардың болмауы
Бірінші симплекс кестенің индекстік жолында теріс коэффициенттер бар.
Жаңа базистік жоспарға көшу симплекстік жаңарту деп аталады.
Есеп максимумге шешілгендіктен, дақылдар егістігінің жоспарына барынша көп
Енді қызылшаның егістігі қандай көлемде қарастырылуы мүмкін екенін
5801=580га; 270020=135 га;
Қатынастар (5.19) симплексті деп аталады. Олардың барынша аз
х2 айнымалыны базистік айнымалының бірі нөлге тең болатындай
Егер 135 га қызылша егілсе, онда еңбек ресурстары
Енді екінші симплекс кестені, яғни екінші базистік жоспар
Теңдеулер жүйесін енгізілетін х2 айнымалының бірлік баған векторы
Қалған жолдарды бағыттаушы бағанның торларында нөлдер пайда болатындай
2700:20=135; 1:20=0,05; 20:20=1;
Кейінгі кестедегі бағыттаушы баған бойынша рұксат беруші элементтің
і-ші жолда және і-ші бағанда орналасқан элементтің жаңа
Мысалы, х4 жол х4-х2н формула бойынша толтырылады, сонда
580-135=445; 1-0,05=0,95; 1-1=0;
0-0,05= -0,05; 0-0=0.
Ал х6 жолды хб-4х2н формуласы бойынша аламыз,
1200-4x135=660; 1,7-4x0,05=1,5; 4-4=0; 1,6-4x0,045=1,42;
0-4х0,05=-0,2; 1-4x0=1.

Мақсат функцияның жолы Ғ+350х2 формула бойынша толтырылады; сонда
жазамыз.
3-кесте
№ базис bi X1 X2 X3 X4 X5
1 X4 135 0,05 1 0,045 0 0,05
2 X5 445 0,95 0 0,.955 1 -0,05
3 X6 660 1,5 0 1,42 0 -0,2
4 F 47250 -182,5 0 -284,25 0 17,5
Оны жасағаннан кейін жоспардың оңтайлылығы тексеріледі. Индекстік жолда
Бағыттаушы баған мен бағыттаушы жол тағы да іздестіріледі,
Мысалы, Хз жол былай есептеледі: х6:1.42, сонда төмендегіні
660: 1,42 =464,788; 1,5:1,42=1,06; 0:1,42=0; 1,42:1,42=1; 0:1,42=0;
Ал х2 жолды х2-0,045х3 формула бойынша аламыз:
135-464,78x0,045=114,08; 0,05-1,06x0,045=0,002;
0,045-1x0,045=0; 0-0x0,045=0; 0,05-0,14x0,045=0,044; 0-0,7х0,045=-0,03. х4 жолды х4-0,955х3 формуласы
445-0,955x464,78=1,12; 0,95-0,955x1,06=-0,06; 0-0,955x0=0; 0,955-0,955x1=0; 1-0x0,955=1; -0,05-0,955х0,14=-0,18; 0-0,955х0,7=-0,67. Мақсат
№ Базис bi X1 X2 X3 X4 X5
1 X3 464,788 1,06 0 1 0 0,14
2 X2 114,08 0,002 1 0 0 0,044
3 X4 1,12 -0,06 0 0 1 -0,18
4 F 179366 118,8 0 0 0 57,3
17,5+284,25x0,14=57,3; . 0+0,7x284,25=199. 4-кесте

Соңғы кесте бойынша оңтайлы шешім оңтайлы жоспарға сәйкес
Х1=0, Х2=114,08, Х3=464,78, Х4=1,12, Х5=0, Х6=0, Ғmах=179366 тг.
Үшінші симплекс кестенің индекстік жолында теріс сандардың болмауы
2.3. ЖАСАНДЫ БАЗИСТІҢ СИМПЛЕКС ӘДІСІ
Шектеулері (=) таңбалы теңсіздіктермен берілген есептерде қосымша белгісіздер
Шешім алгоритмін нақты мәселе мысалында талдауға болады.
Есеп. Фирмада екі түрлі шикізаттан төрт түрлі өнім
5-кесте
Өнім 1-шикізат 2-шикізат Өнім бірлігінің өзіндік құны
№1 1 100 3
№2 0,2 14 0,5
№3 0,12 9 1,4
№4 0,5 79 2,0
х1, х2, х3, х4 деп өнімнің түрлерін белгілейміз.
Х1+0,2х2+0,12х3+ 0,5х4= 9.4
100х1+14х2+ 9х3+ 79х4 = 987
Х1х4 Барлық белгісіздер теріс емес болуға және сызықтық функция
Fmin = Зх1+0,5х2+1,4хз+2х4.
Есепте х5, xб, х7 қосымша айнымалылардың көмегімен канондық
Х1+0,2х2+0,12хз+ 0,5х4 - х5= 9.4 100х1+14х2 + 9х3+
Х1 + х6 = 2,5
х4 + х7 = 5
Есепті шешу үшін аталмыш жүйенің табиғи базисі жоқ,
Бастапқы базистік шешім алу үшін осы теңдеулерге бірлік
x1+0,2х2+0,12х3+ 0,5х4 - х5 + у1=9.4 100х1+14х2+ 9х3+
x1 + х6=2.5
х4 +х7 = 5

Барлық белгісіздер теріс емес болуға тиіс, ал жазбаның
Fmin = 3х1+0,5х2+1,4хз+2х4 +0х5 + 0хб + 0х7
Бірінші симплекс кестені жасаймыз. Бірінші кестеде шек-теулер (=)
Қолайлы болу үшін индекстік жол мына екі қатарға:
6-кесте
№ Базис Ві х1 х2 xз х4 х5
1 У1 9,4 1 0,2 0,12 0,5 -1
2 У2 987 100 14 9 79 0
3 Х6 2,5 1 0 0 0 0
4 х7 5,0 0 0 0 1 0
m+1 F 0 -3 -0.5 -1.4 -2 0
m+2
996.4М 101М 14.2М 9,12М 79,5М -М 0 0
Жасанды базисі бар есепті шешу алгоритмі табиғи базисі
мәндердің ішіндегі ең үлкен теріс мәні бойынша, ал
Оларды есептеудің дұрыстығы Ғj - Сj ретінде жалпы ережеге
Есептеу базистен жасанды белгісіздер толық алып тасталғанға дейін
Базистен шығарылған жасанды белгісіздерді екінші қайтара енгізу қажетсіз,
Барлық жасанды айнымалылар базистен шығарылғанда, сондай-ақ m+2 жолы
Барлық жасанды айнымалылар базистен шығарылған, m+2 жол бойынша
6-кестеде х1 - бағыттаушы баған, ал үшінші жол
7-кесте
№ базис Ві x1 x2 х3 х4 Х5
1 Х1 2,5 1 0 0 0 0
2 х7 5 0 0 0 1 0
3 У1 6,9 0 0,2 0,12 0,5 -1
4 У2 737 0 14 9 79 0
m+1 F 7,5 0 -0,5 -1,4 -2 0
m+2
743,9М 0 14,2М 9,12М 79,5М -м -101M 0
3-кестенің m+2 индекстік жолының мәндері жоспарды одан әрі
8-симплекс кестеде бағыттаушы баған - х2, ал бағыттаушы
8-кесте
№ базис Ві Х1 х2 х3 х4 х?
1 х4 5 0 0 0 1 0
2 Хі 2,5 1 0 0 0 0
3 Уі 4,4 0 0,2 0,12 0 -1
4 У2 342 0 14 9 0 0
m+1 F 17,5 0 -0,5 -1,4 0 0
m+2
346,4М 0 14,2М 9,12М 0 -м -101M -79.5М
9-кестеде де оңтайлы жоспарға қол жеткізілмеген. ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.