Симплекс. моделирование

Мазмұны:

 

Кіріспе……………………………………………………………………………..3

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

1.1 Сызықтық бағдарламалау есебін шешудің симплекс әдісі……………………….…4-5

1.2 Симплекс әдісінің есептеу схемасының негіздері…………………………….6-8

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

2. Сызықтық бағдарламалау есебін математикалық әдісмен шешу                 

2.1 Есептің қойылымы…………………………………………………………....9

2.2  Математикалық моделін құру…………………………………………………..10

2.3  Есепті симплекс әдісімен шығару…………………………………………..11-13

2.4  Программа листингісі………………………………………………………..14-20

 

Қорытынды …………………………………………………………………….….21

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Кiрiспе.

 

Бiздiң ғасырымызға дейiн ғарыштық кемелердi пайдаланған кезде компьютерлер де көптеген салаларда керек бола бастады. Компьютер технологиясы мен методтары, информацияны қолдану адам өмiрiнiң кез келген саласында, тeмip жол тасымалдаушының графигынан жұлдыз жорамал жасауға дейiн қолданылған. Әрине, компьютер кез келген проблемаға дұрыc жауап бере алмайды, бiрақ олар оны аз да болса жеңiлдетедi.

Компьютердiң көмегімен есеп шығару методын eкi негiзгi топқа бөлуге болады.

Бiрiншiден, бұл аналитикалық жолы. Ол зерттелген системены xq ш сандар негiзiнде, оптималды жауабын сипаттайды.

Екiншiден, бұл модельдеу жолы. Бұл жағдайда басындағы қалпы және негiзгi заңдардың қарым-қатынасы берiледi. Осыдан кейiн жүйе «өмірге» енедi, бақылаушы оны бақылайды, кіру арқылы бұл процестен керекті аспекттерін алады.

Математикалық әдiстердi пайдалану үшiн, ең алдымен, тиiмдi шешiмiн таппақшы болған есептің өзінің қойылымын жазуымыз қажет. Математикалық қойылымда берiлген ресурстар, өндiрiстiк технология, қорытынды шешiмдер және олардың арасындағы байланыстар математикалық өрнектер, теңсiздiктер арқылы керсетiледi. Математикалық модель құру үшiн ең алдымен зерттейтiн объектiнiң ең басты қасиеттерiн немесе заңдылықтарын бөлiп алып оларды математикалық өрнектер арқылы  өзара байланыстырып сипаттайды. Математикалық модельдердi құрғаннан кейiн ғaнa есептi шешiп зерттеу үшiн математикалық әдiстерді қолдануға болады.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

1.1 Сызықтық бағдарламалау есебін шешудің симплекс әдісі

Сызықтық  бағдарламалау есебін шешу симплекс әдісінің негізі бар тірек жоспардан басқа тірек жоспарға

ауысқандағы мақсат функцияның мәні өспелі кезінде  орындалады (егер, берілген есептің  оптималды жоспары болса

және оның әрбір тірек жоспары айқындалмаған  болса).

Есепті қарастырайық функцияның максимум мәнін табу керек.

Егер келесі шарт орындалса

мұндағы a_{j bj және^ (і=1,т;]=1,п)-берілген тұрақты сандар(т<п және bj>0). Берілген есептің векторлық нысаны келесідей:

  (1) функцияның максимум табу керек, егер

болса мұндағы

 

 

 

 

 

 

 

 

 

 

 

         

                            болғандықтан, тірек жоспардың анықтамасы бойынша

                    і берілген   есептің ,   тірек    жоспары   болады  (X                 

                          векторының соңғы n-m компоненті нолге тең). Бұл жоспар Рі Рг... Р_п  векторлары -

ның әрбірі және Ро векторы берілген базистік векторларының сызықты комбинациясы түрінде көрсетілуі мүмкін.

1 теорема: (оптималды жоспар болуының белгісі). (1)-(3) есебінің тірек жоспары 
тірек жоспары оптималды болады, егер кез- келген

                       үшін болса.

2. теорема: Егер кейбір j=k үшін болып және сандар арасында оң сандар болмаса  (ajk<0), онда (2)-(3) есебінің (1) мақсат функциясы оның жоспар жиынында шектелмеген болады.
3. теорема: Егер (1)-(3) есебінің тірек жоспары X айқындалмаған және А_к<0 болса, бірақ ajk сандар арасында оң сандар болатын болса онда болатындай  X' тірек жоспары бар болады.

  Жоғарыда аталған теоремалардың көмегімен табылған тірек жоспар оптималды  бола ма және жаңа тірек жоспарға өтудің керектігін айқындайды. 

1.2 Симплекс әдісінің есептеу схемасының негіздері

Тірек жоспарының оптималдығына зерттеу және кейінгі есептеу процессті ыңғайлы жүргізу үшін 1-ші кестеде көрсетілген есептің берілгенін және бастапқы тірек жоспарды анықтағаннан кейінгі бастапқы деректерді жазу керек.

Кестенің Cq бағанында мақсат функцияның белгісіндегі коэффиценттері жазылады. Коэффициенттердің индекстері бірдей болады.

Р₀ бағанында бастапқы тірек жоспардың оң компоненттері жазылады, осында есептелгеннен кейінгі тірек жоспардың оң компоненттерін алады. Pj векторлардың бағандарында берілген базис векторларына жіктелген коэффиценттер жазылады.

1.кестеде алғашқы m жолдар есептің бастапқы деректермен анықталады, ал (т+1) ші  жолды есептейді. Осы жолда  векторының бағанында мақсат функцияның берілген тірек жоспарында қабылдайтын мәні жазылады, ал бағанында -

1. кестені толтырғаннан кейін бастапқы тірек жоспарды оптималдыққа тексереді. Ол үшін (т+1) жолдағы элементтерді қарастырады. Нәтижесінде келесі үш жағдайдың біреуі орындалуы мүмкін:

1)  ∆ _j   >0,  J=m+1 ,  m+2 ,….,n (J = 1,m , z_j= c_j) Үшін

                             2) ∆ _j < 0 Кейбір J үшін және барлық  осы индекс сәйкес  a _ij < 0 (J=1,m)

 3)  ∆ _j < 0 Кейбір J индекс үшін, және  әрбір осындай J үшін  a _ij  сандар ішінен  кем                           дегенде   біреуі  он

 

   

 

V және ау'(4) (5) формулаларға сәйкес есептелгеннен кейін олардың мәні 2-ші кестеге жазылады. (т+1)- ші жолының ,элементтері оларды анықтамасына сәйкес, немесе

формулалармен есептелінеді.

   (т+1)- ші жолының элементтерін есептеудің екі әдісінің болуы есептеудің дұрыстығын тексеруге мүмкіндік береді.

   (7) формуладан бір тірек жоспардан екінші тірек жоспарға өту кезінде базиске енетін j индексі бар Pj векторын абсалютты шамасы бойынша максимум

  саны барын алу керек. Бірақ есептеу үрдісін жеңілдету үшін болашақта базиске енетін векторды теріс Aj сандар ішінен абсолютті шамасы бойынша максимум саны арқылы табамыз. Егерде ондай сандар бірнеше болса онда кез-келген аламыз.

Бір тірек жоспардан екінші тірек жоспарға өту ол бір симплекс кестеден екінші симплекс кестеге өту деген сөз. Жаңа симплекс кестесінің элементтерін (4)-(7) формулалар арқылы немесе осы формулалардан шығатын ережелер арқылы есептеуге болады. Осы ережелер келесіден тұрады.

Базиске кіретін векторлардың бағаналарында а және жолдың қиылысуындағы элемент 1-ге тең болды, ал қалған элементтері 0-ге тең деп жазылады.

Жаңа симплекс кестенің Ро және Pj векторлардың элементтері базиске енген жол бастапқы кестенің осы жолының элементтерін шешуші элементке бөлгеннен шығады. Сб бағанасында енетін вектор жолында С_К әдісімен қояды, мұндағы к-енетін вектордың индексі.

Жаңа симплекс кестенің  Ро және Pj векторлар бағаналардың қалған элементтері үшбұрыш ережесі арқылы есептелінеді. Кез-келген элементін үшін үш санды табады:

1. осы элемент тұрған жаңа симплекс кестенің орнына сәйкес бастапқы симплекс кестенің саны алынады;
2. бастапқы симплекс кестенің базиске кіретін бағана және ізделінетін элемент тұрған жолын қиылысуындағы сан алынады;
3. бастапқы симплекс кестенің базиске кіретін жолдың және ізделінеді элемент тұрған бағананың қиылысуындағы сан алынады.

Осы үш сан үшбұрышты құрастырады. Осы үшбұрыштың екі төбесі бастапқы симплекс кестенің элементтері, ал үшінші төбесі жаңа симплекс кестенің элементі. Ізделінетін элементі табу үшін бірінші саннан екінші және үшінші сандардың көбейтіндісін аламыз.

Жаңа симплекс кестені толтырғаннан кейін (т+1)-ші жолының элементтерін қарастырамыз. Егер барлық Zj'-Cj £0, онда жаңа тірек жоспар оптималды болып есептеледі. Егер де көрсетілген сандардың ішінде теріс сан табылса, онда жоғарыда айтылған алгоритм қайтадан орындалып, жаңа тірек жоспар құрастырылады. Бр[ алгоритм есептің оптималды жоспары қойылғанша немесе есептің шешімін анықтағанша қайталанады.

Сызықтық  бағдарламалау есебінің шешуін тапқан кезде біз осы есептің тірек жоспары бар және ол айқындалмаған деп есептейміз. Егер есеп айқындалған тірек жоспарға ие болса, онда кез-келген итеграцияда тірек жоспардың бір немесе бірнеше элементтері нөлге тең болып шығады. Осылайша бір тірек жоспардан екінші тірек жоспарға өткен кезде функция мәні өзгермей қалуы мүмкін. Осындай жағдай бірнеше итеграцияда қайталануы және де бастапқы базиске қайта оралуы мүмкін, осыны циклдану деп атаймыз. Практикада мұндай жағдай өте сирек кездеседі, сондықтан оны қарастырмаймыз.

Оптималды жоспарды симплекс әдіспен табу келесі этаптардан тұрады:

1. тіректен жоспарды табу;
2. симплекс кестені құрастыру;
3. ең болмағанда бір теріс Aj саны анықталады. Егер жоқ болса, онда Aj табылған тірек жоспар оптималды болып есептеледі. Егер сандардың ішінен теріс сан бар болса, онда есептің шешуі жоқ немесе жаңа тірек жоспарға көшеді;
4. бағыттауыш жол мен бағананы табады. Бағыттауыш бағана теріс Aj ішінен абсолютті шамасы бойынша максимум саны арқылы анықталады. Ал бағыттауыш жол Р₀ және бағыттауыш бағананын сәйкес оң элементтердің қатынасының минимум саны арқылы анықталады;
5. 1(4)- (7) формулалары арқылы жаңа тірек жоспардың оң компоненттері, Pj   векторлардың жаңа базис векторлар бойынша жіктелу коэффиценттері және Fo- Ау сандары есептелінеді. Бұл сандардың барлығы жаңа симплекс кестеге жазылады;
6. табылған жаңа тірек жоспарды оптималдыққа тексеріледі. Егер жоспар оптималды болмаса, онда 4 этапқа қайта оралып жаңа тірек жоспарға көшеміз. Егер жоспар оптималды болмаса немесе шешу мүмкіндгі болмаса, онда есептеу тоқтатылады.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.Сызықтық бағдарламалау есебін математикалық әдіспен шешу

2.1    Есептің қойылымы

Есеп. Фирма ішкі (I) және сыртқы (С) жұмыстар үшін екі түрлі бояу дайындайды. Осы өнімдерді шығару үшін түс және әліп май өнімдері пайдаланылады. Өнімнің шығыны, максималды тәуліктік қоры және 1т. бояудың сату бағасы кестеде көрсетілген.

 

Өлшемдер	1т.Кететін бояуға шығын		Тәулік қоры,т
	Бояу С	БояуI
Түс (пигмент)	0,8	1,6	4,8
Әліп май (Ольфа)	1,6	0,8	6,8
IТ.Бояудың сату бағасы	2,4	1,6

 

Сауда өтімі  көрсеткендей, ішкі (I) жұмыстарға кететін бояудың тәуліктік сұранысы 1,6 т-ден аспайды. Өнімді өткізгенде максималды пайда табу үшін фирма бояудың қай түрін, қандай мөлшерде өндіру керектігін анықтаңыз.

 

2.2   Математикалық моделін құру

 1)Белгілеулер енгізем

                           Х_г Сыртқы жұмыстарға қолданылатын бояу мөлшері.

  Х₂- Ішкі жұмыстарға қолданылатын бояу мөлшері.

  X (Х_ь Х₂)- Сыртқы және ішкі жұмыстар үшін бояудың жоспарланған                       шығарлымы.

                        2) Ресурстар бойынша шектеулер 

                              Бастапқы өнімнің шығыны тәуліктік қор .

  0,8 Х_г - cыртқы жұмыстарға арналған.

                              Хі - бояудың дайындауға кететін түстің мөлшері.

 1,6 Х₂- Ішкі жұмыстарға арналған.

                              0,8 Хі+1,6 Х₂- iшкі және сыртқы жұмыстарға арналған.

  Х_ьХ₂ -  бояудың дайындауға кететін түстің жалпы мөлшері.

                            0,8 Хі+1,6 Х₂£ 4,8 - түсті пайдаланудағы шектеулер.

Тура осы жолмен әліп майды пайдаланудағы  шектеулерді  құрамыз.

                         0,8 Хі+1,6 Х₂   ≤ 6,4 - әліп майды пайдаланудағы шектеулер.

                             0,8 Х₂- ішкі жұмыстарға арналған бояудың тәуліктік сұранысы.

                             0,8 Х₂  ≤1,6- Ішкі жұмыстарға арналған бояудың тәуліктік сұранысы.

  0,8 Хі+1,6 Х₂   ≤ 4.8