Сызықтық программалаудың негізгі есебі
КІРІСПЕ
Қазіргі заманғы қоғамның дамуынмынадай деңгейлермен сипаттауға болады: техникалық білімдерінің жоғарылауымен, өндіріс орындары талаптарының өсуімен, қоғамдық еңбек дамуымен,жоспарлау әдістеріне, шаруашылық басқаруға деген жоғарғы талап қоюумен. Бұл жағдайларда басшыларға қоғамның экономикалық өміріне ғылыми тәсілдер қолдану халық шаруашылығының қарқынды дамуына ықпал етеді.
Экономиканың әріқарай дамуының қажетті шарттарының бірі және бірегейлері сандық анализдің нақты әдістерінің қолданылуы жәнеде математиканың кеңінен қолданылуы ықпал етеді.
Қазіргі таңда математиканың ең жоғарғы жетістіктерімен, заманауи есептік техниканың жетістіктері, экономикалық зерттеулермен жоспарлауларда кеңінен қолданылуда. Бұл мақсатта қолданылып жұрген математикалық жетістіктер: математикалық программалау, ойын теориясы, жалпыға қызмет ету теориясы секілді көптеген математикалық әдістер. Қазіргі таңда көптеген экономикалық есептер және экономикалық шешімдерді математикалық әдістерді қолдануда. Айтарлықтай табысқа жеткен әдістерінің бірі оптималды жоспарлау. Ал ол өз кезегінде математикалық программалаудың негізі болуда. Болашақ бағдарламашылар үшін қолданылған математиканың ең маңызды саласының бірі – математикалық бағдарламалау; Ол экстремальді есептерді зерттеуге және оларды шешу әдістеріне арналған. Бұл пәнді оқу студентке қарапайым экономикалық есептердің математикалық модельдерін құрастыруда алғашқы қадам жасауға, математикалық қойылыммен шешу әдістерін үйренуге мүмкіншілік береді.
Экстремальды экономикалық есеп шешімдерін үш кезеңге бөлуге болады:
1. Экономикалық математиканың моделін құру.
2. Оптималды шешімдердің біреуін математикалық әдіспен табу.
3. Практикалық көзқарас және халық шаруашылық.
Экономиканың математикалық моделін құру үшін алдымен экономикалық процестің математикалық моделін солай құру керек, онда оның шынайылығы көрініп тұратындай болуы керек.
Математикалық программалаудың құрамдас бөліктері үшке бөлінеді. Олар: Сызықтық, сызықтық емес және динамикалық программалау.
Алғашқы рет сызықтық программалаудың есебін совет экономисті А.Н.Толстой 1930 жылы қойды. Ал 1931 жылы венгерлік математик Б.Эгервари сызықтық программалаудың математикалық түрде қойылуын қарастырып, оған «таңдау кедергісі» деп аталып, венгерлік шешім деген атқа ие болды. Жүйелі түрде зерттеулер нәтижесінде сызықтық программалаудың есебін, жалпы әдісін және шешімін табуды совет ғалымы Л.В.Канторовичтің (1932) жұмыстарында берілген жалпы шешімдерін табу әдісін ұсынды. Ол М.К.Гавуринмен бірлесе отырып потенциал әдісін ойлап табуды және оны транпорттық есептерді шешуде қолданды.
Сызықтық программалаудың әдістерін жақын шет елдегі ғалымдар да зерттеді. Дәлірек айтар болсақ, американдық ғалым 1941 жылы Хичкок транспорттық есепті қойды. Сызықтық программалауды шешудің негізгі әдісі ретінде – симплекс әдісі болып жарияланды. Ол 1949 жылы Данциг жариялады. Одан әрі қарай да көптеген ғалымдар өз еңбектерін сызықтық және сызықтық емес программалау әдістерін дамытты.
Қазіргі заманғы қоғамның дамуынмынадай деңгейлермен сипаттауға болады: техникалық білімдерінің жоғарылауымен, өндіріс орындары талаптарының өсуімен, қоғамдық еңбек дамуымен,жоспарлау әдістеріне, шаруашылық басқаруға деген жоғарғы талап қоюумен. Бұл жағдайларда басшыларға қоғамның экономикалық өміріне ғылыми тәсілдер қолдану халық шаруашылығының қарқынды дамуына ықпал етеді.
Экономиканың әріқарай дамуының қажетті шарттарының бірі және бірегейлері сандық анализдің нақты әдістерінің қолданылуы жәнеде математиканың кеңінен қолданылуы ықпал етеді.
Қазіргі таңда математиканың ең жоғарғы жетістіктерімен, заманауи есептік техниканың жетістіктері, экономикалық зерттеулермен жоспарлауларда кеңінен қолданылуда. Бұл мақсатта қолданылып жұрген математикалық жетістіктер: математикалық программалау, ойын теориясы, жалпыға қызмет ету теориясы секілді көптеген математикалық әдістер. Қазіргі таңда көптеген экономикалық есептер және экономикалық шешімдерді математикалық әдістерді қолдануда. Айтарлықтай табысқа жеткен әдістерінің бірі оптималды жоспарлау. Ал ол өз кезегінде математикалық программалаудың негізі болуда. Болашақ бағдарламашылар үшін қолданылған математиканың ең маңызды саласының бірі – математикалық бағдарламалау; Ол экстремальді есептерді зерттеуге және оларды шешу әдістеріне арналған. Бұл пәнді оқу студентке қарапайым экономикалық есептердің математикалық модельдерін құрастыруда алғашқы қадам жасауға, математикалық қойылыммен шешу әдістерін үйренуге мүмкіншілік береді.
Экстремальды экономикалық есеп шешімдерін үш кезеңге бөлуге болады:
1. Экономикалық математиканың моделін құру.
2. Оптималды шешімдердің біреуін математикалық әдіспен табу.
3. Практикалық көзқарас және халық шаруашылық.
Экономиканың математикалық моделін құру үшін алдымен экономикалық процестің математикалық моделін солай құру керек, онда оның шынайылығы көрініп тұратындай болуы керек.
Математикалық программалаудың құрамдас бөліктері үшке бөлінеді. Олар: Сызықтық, сызықтық емес және динамикалық программалау.
Алғашқы рет сызықтық программалаудың есебін совет экономисті А.Н.Толстой 1930 жылы қойды. Ал 1931 жылы венгерлік математик Б.Эгервари сызықтық программалаудың математикалық түрде қойылуын қарастырып, оған «таңдау кедергісі» деп аталып, венгерлік шешім деген атқа ие болды. Жүйелі түрде зерттеулер нәтижесінде сызықтық программалаудың есебін, жалпы әдісін және шешімін табуды совет ғалымы Л.В.Канторовичтің (1932) жұмыстарында берілген жалпы шешімдерін табу әдісін ұсынды. Ол М.К.Гавуринмен бірлесе отырып потенциал әдісін ойлап табуды және оны транпорттық есептерді шешуде қолданды.
Сызықтық программалаудың әдістерін жақын шет елдегі ғалымдар да зерттеді. Дәлірек айтар болсақ, американдық ғалым 1941 жылы Хичкок транспорттық есепті қойды. Сызықтық программалауды шешудің негізгі әдісі ретінде – симплекс әдісі болып жарияланды. Ол 1949 жылы Данциг жариялады. Одан әрі қарай да көптеген ғалымдар өз еңбектерін сызықтық және сызықтық емес программалау әдістерін дамытты.
Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 57 бет
Таңдаулыға:
Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 57 бет
Таңдаулыға:
КІРІСПЕ
Қазіргі заманғы қоғамның дамуын мынадай деңгейлермен сипаттауға болады: техникалық білімдерінің жоғарылауымен, өндіріс орындары талаптарының өсуімен, қоғамдық еңбек дамуымен, жоспарлау әдістеріне, шаруашылық басқаруға деген жоғарғы талап қоюумен. Бұл жағдайларда басшыларға қоғамның экономикалық өміріне ғылыми тәсілдер қолдану халық шаруашылығының қарқынды дамуына ықпал етеді.
Экономиканың әріқарай дамуының қажетті шарттарының бірі және бірегейлері сандық анализдің нақты әдістерінің қолданылуы және де математиканың кеңінен қолданылуы ықпал етеді.
Қазіргі таңда математиканың ең жоғарғы жетістіктерімен, заманауи есептік техниканың жетістіктері, экономикалық зерттеулермен жоспарлауларда кеңінен қолданылуда. Бұл мақсатта қолданылып жұрген математикалық жетістіктер: математикалық программалау, ойын теориясы, жалпыға қызмет ету теориясы секілді көптеген математикалық әдістер. Қазіргі таңда көптеген экономикалық есептер және экономикалық шешімдерді математикалық әдістерді қолдануда. Айтарлықтай табысқа жеткен әдістерінің бірі оптималды жоспарлау. Ал ол өз кезегінде математикалық программалаудың негізі болуда. Болашақ бағдарламашылар үшін қолданылған математиканың ең маңызды саласының бірі - математикалық бағдарламалау; Ол экстремальді есептерді зерттеуге және оларды шешу әдістеріне арналған. Бұл пәнді оқу студентке қарапайым экономикалық есептердің математикалық модельдерін құрастыруда алғашқы қадам жасауға, математикалық қойылыммен шешу әдістерін үйренуге мүмкіншілік береді.
Экстремальды экономикалық есеп шешімдерін үш кезеңге бөлуге болады:
1. Экономикалық математиканың моделін құру.
2. Оптималды шешімдердің біреуін математикалық әдіспен табу.
3. Практикалық көзқарас және халық шаруашылық.
Экономиканың математикалық моделін құру үшін алдымен экономикалық процестің математикалық моделін солай құру керек, онда оның шынайылығы көрініп тұратындай болуы керек.
Математикалық программалаудың құрамдас бөліктері үшке бөлінеді. Олар: Сызықтық, сызықтық емес және динамикалық программалау.
Алғашқы рет сызықтық программалаудың есебін совет экономисті А.Н.Толстой 1930 жылы қойды. Ал 1931 жылы венгерлік математик Б.Эгервари сызықтық программалаудың математикалық түрде қойылуын қарастырып, оған таңдау кедергісі деп аталып, венгерлік шешім деген атқа ие болды. Жүйелі түрде зерттеулер нәтижесінде сызықтық программалаудың есебін, жалпы әдісін және шешімін табуды совет ғалымы Л.В.Канторовичтің (1932) жұмыстарында берілген жалпы шешімдерін табу әдісін ұсынды. Ол М.К.Гавуринмен бірлесе отырып потенциал әдісін ойлап табуды және оны транпорттық есептерді шешуде қолданды.
Сызықтық программалаудың әдістерін жақын шет елдегі ғалымдар да зерттеді. Дәлірек айтар болсақ, американдық ғалым 1941 жылы Хичкок транспорттық есепті қойды. Сызықтық программалауды шешудің негізгі әдісі ретінде - симплекс әдісі болып жарияланды. Ол 1949 жылы Данциг жариялады. Одан әрі қарай да көптеген ғалымдар өз еңбектерін сызықтық және сызықтық емес программалау әдістерін дамытты.
1 СЫЗЫҚТЫҚ ПРОГРАММАЛАУДЫҢ НЕГІЗГІ ЕСЕБІ
1.1 ЖӘЙ ЭКОНОМИКАЛЫҚ ЕСЕПТЕР
Шикізатты қолдану есебі
Екі түрлі П1 және П2 өнімдерін дайындау үшін төрт түрлі шикізат қажет деп болжайық: S1 , S2, S3, S4. Әр шикізат қоры шектеулі, яғни b1, b2,b3,b4 шартты бірліктері. Шикізат қорлары, өнімнің әр данасы үшін жұмсалатын шикізат көлемі белгілі болсын. (1-кесте)
Кесте 1
Шикізат түрлері
Шикізат қоры
Өнім түрлері
П1
П2
S1
S2
S3
S4
b1
b2
b3
b4
a11
a21
a31
a41
a12
a22
a32
a42
Кіріс
C1
C2
мұнда aij(i=1,..,4;j=1,2) Пjтүріндегі өнімді өндіру үшін Si түріндегі шикізат көлемі кестедегі соңғы қатарда әрбір өнімнен түскен өндірістің пайдасы.
П1 және П2 өнім шығару үшін максимальды пайда түсім беретін өнім өндіру жобасын құру керек болсын. Математикалық түрде берілуін келесі сандық мысалда көреміз (2 - кесте).
Кесте 2
Шикізат түрлері
Шикізат қоры
Өнім түрлері
П1
П2
S1
S2
S3
S4
19
13
15
18
2
2
0
3
3
1
3
0
Кіріс
7
5
Айталық П1 -деп x1 , П2-деп x2 өнімдер дайындалсын. Ол үшін S1-деп 2x1 + 3x2 бірлік шикізат алу талап етілсін (2-кесте).Сонымен S1 - де барлығы 19 бірлік шикізат мөлшері болса, онда ол
2x1 + 3x2 =19
теңсіздігін орындау керек.
Теңсіздік S1 - дегі шикізат қорлары толықтай пайдаланбай өндіріс максимальды табысқа жетуі қарастырылған.
Ал қалған шикізаттың түрлері келесі теңсіздікпен берілген
Осындай шарттармен өндіріске түскен табыс
F=7x1+5x2
құрайды.
Сонымен математикалық есеп былай тұжырымдалады
(1.1.1)
жүйесі берілген, төрт сызықтық теңсіздіктен сызықтық форма
(1.1.2)
түрінде болады.
Теріс емес шешімдерден (1.1.1) теңсіздіктер жүйесінен шешімді F формасы ең үлкен мән қабылдайтындай етіп таңдауға болады.
Құрылғылардың қуаттылығын пайдалану есебі.
Өнеркәсіп өндірісте уақыт және наменклатура бойынша жоспар құрған. П1 -түрдегі N1- өнімді және П2 - дегі N2- өнімді T уақытта шығаруы керек болсын. Әрбір түрлі өнімді әртүрліқуаттылығына қарай А және В екі машинамен өндіруі мүмкін. Бұл қуаттылықтар 3- кестеде көрсетілген. Мұнда a1- А машинамен бірлік уақытта өндірілген П1 түрдегі өнім мөлшері. Ал қалғандарының да берілгендері кестеде көрсетілген.
Кесте 3 Кесте 4 Кесте 5
П1
П2
П1
П2
П1
П2
А
a1
a2
A
α1
α2
A
x1
x2
В
b1
b2
B
β1
β2
B
x3
x4
Берілген машинада өнімдердің түрлеріне қарай шығындарда әр түрлі болып табылады және 4 - кестеде көрсетілген.
Бұл кестеде α1 мен- П1 түрдегі дайындалған өнімнің А машинасындағы жұмыс уақытының бірлік бағасын өрнектейді. Ал қалған α2,β1,β2 шамаларыда өзгелерге ұқсас.
Машинаның жұмыс жасауының оптимальды жоспарын, атап айтсақ әрбір А және В машиналары П1 және П2 түрдегі өнімдерді қанша уақытта дайындағанда, өндірістегі өнімдердің құны минималь болатындай етіп құру керек.
Қойылған есептің математикалық тұжырымдамасын жасайық. Өнімдерді өндіру үшін машинаның жұмыс уақытына (5 кестеде) көрсетілгендей белгілеулер енгіземіз. Мұнда, мысалыға x1- П1 түрдегі өнімді А машинасында дайындау уақытын көрсетеді. Сондай-aқ x2,x3,x4 осындай болады.
Қаншалықты А және В машиналары бір уақытта жұмыс жасаса, уақыт бойынша жоспарды орындау келесі теңсіздіктермен қамтамасыз етеді.
x1+x2=T,
x3+x4=T.
Бұл теңсіздіктің сол жағы А және В машиналарына сәйкес жалпы жұмыс уақытын білдіреді.
x1 уақыт бірлігінде П өнімін А машинасында дайындайды. Сонымен А машинасында П1 өнімді В машинасында b1x3 бірлікте дайындайды. Сондықтан жоспарды нөмір бойынша қамтамасыз ету үшін келесі теңдік орындалуы тиіс.
a1x1+b1x3=N1.
Дәл осылай П2 өнімді шығару жоспарын қамтамасыз ету үшін келесі теңдікті қанағаттандыруы тиіс.
a2x2+b2x4=N2.
Бұдан әрі осы шарттардан барлық өнімдердің жалпы бағасы
F=a1x1+a2x2+β1x3+β2x4.
құрайды.
Қорытындысында келесі математикалық есепке келеміз.
x1+x2=T,x3+x4=T,a1x1+b1x3=N1,a2x 2+b2x4=N2. (1.1.3)
екі сызықтық теңдеумен екі сызықтық теңсіздіктерден сызықтық форма беріледі
F=α1x1+α2x2+β1x3+β2x4. (1.1.4)
(1.1.3) жүйеден барлық теріс емес шешімдердің арасынан F форма қай кезде ең
аз мәнді қабылдайтындығын табу керек.
Қойылған есептен бір ең маңызды нұсқасын белгілейміз.
А және В машиналары барлық T уақытта жоспар бойынша жүргізуін талап етеміз. Сонда
x1+x2=T,
x3+x4=T
Теңсіздігі теңдікке өтеді. Сол кезде соңғы (1.1.3) жүйедегі екі теңдік теңсіздікке өтеді.
a1x1+b1x3=N1,
a2x2+b2x4=N2.
Сонда T уақыттағы машиналар жұмыс тек қана жоспар бойынша асыра орындайды. Сондықтан минимизациялау талабы бойынша нөмір бойынша артық орындауды теріске шығара алмайды.
Транспорт есебі
A1 және A2 екі станциядан a1 және a2 сәйкес біртекті бірлік жүкті жіберу керек. Бұл жүктерді b1,b2, b3 мөлшерінде B1,B2, B3 пунктіне тасымалдау керек. Ai пунктінен Bj пунктіне жүкті тасымалдау құны Cij белгілі. Берілген мәліметтер 6-шы кестеде көрсетілген.
Кесте 6
Қабылдау
пункті
Жіберу
пункті
Тағайындау пункті
Жүк қорлары
B1
B2
B3
A1
A2
C11
C21
C12
C22
C13
C23
a1
a2
Жүкке
қажеттілік
b1
b2
b3
ai=bj
Станциялардағы жүкті тасымалдаудың жалпы қоры осы жүкті жеткізудегі сұраныстың қосындысына тең болады. Шындығында
a1+a3=b1+b2+b3. (1.1.5)
Тасымалдау бағасы ең аз болатын жоспарда құруымыз керек.
Ai пунктінен Bi пунктіне жіберілетін жүктің санын xij деп белгілейміз. Сонда жүктің саны A1 және A2 пункттерінен B1 пунктеріне жеткізу жоспарланған,
x11+x21.
деп қорылады.
Ал бірақ B1 пункттегі жүктің қажеттілігі b1-ге тең болса, онда
x11+x21=b1.
орындалады.
Дәл осындай талқылаулардан келесі теңдік бере келеміз.
x12+x22=b2,
x13+x23=b3.
Басқаша айтқанда А станциясынан жіберілген жүктің жалпы мөлшері
x11+x12+x13,
қосындысымен өрнектеледі, бұдан байқағанымыз A1 пунктінен пайдалану пункттеріне жіберілген жүктердің қосындысы
x11+x12+x13=a1.
сондай-ақ
x21+x22+x23=a2.
Алынған қатынастарды есте сақтап, барлық шамаларды кестеге енгіземіз. Сонда i-нші қатарда орналасқан барлық xij қосындысын оңай тексеруге болады. Ai пунктіндегі тасымалдау ai қорына тең. j-ші қатарларға xij қосындысы bj-ге тасымалдау Bj-тең. Есептің шарттарынан тасымалдаудың барлық F бағасы
F=c11x11+c12x12+c13x13+c21x21+c22x2 2+c23x23==i=12j=13cijxij=i,jcijxij.
тең.
Кесте 7
Белгіленген
орны
Жіберу
Орны
B1
B2
B3
Қосымша
Қорлар
7 кесте жалғасы
A1
A2
x11
x21
x12
x22
x13
x23
a1
a2
Қажеттілер
b1
b2
b3
Сонымен транспорт есебінің математикалық тұжырымдамасы мынадай
x11+x21=b1,x12+x22=b2,x13+x23=b3,x1 1+x12+x13=a1,x21+x22+x23=a2. (1.1.6)
Алты айнымалылар арқылы бес сызықтың алгебралық теңдеулерден сызықтық форма
F=i,jcijxij. (1.1.7)
(1.1.6) теңдеулер жүйесінен xij шешімінің барлық теріс емес шешімдерінін F формасы минимал, яғни ең кіші мәнге ие болатын шешімін таңдап аламыз.
Сонымен, транспорт есебін шешу барысында ең маңызды қатынасты ескерсек, осы шарттардан
iai=jbj (1.1.5')
шығады.
Алайда кей жағдайда (1.1.5') шарты орындалмайтын да есептердің қойылуы мүмкін.
Азықтандыру есебі
Адам өз өмірінде денсаулығын сақтау және жұмысқа деген құлшынысын арттыру үшін бір күнде кейбір құнарлы заттарды пайдалануы тиіс, мысалға белоктар, майлар, көмірқышқылдар, су және дәрумендер. Бұл қоспалардың қорлары әртүрлі түрдегі PIi(i=1,2,...) тағамдарда әртүрлі. Қарапайым түрде екі түрлі тағамның түрін алып 8 кестедегі түрде берейік, мысалыға a11 саны PIi түрдегі тағамдағы майлардың қорын береді, ал қалған aij сандары осы тектес алынады.
Кесте 8
Құнарлы өнімдер
Қалыпты
Тағам түрлері
PI1
PI2
B1-майлар
B2-нәруыздар
B3-көмірлер
B4-сулар
B5-дәрумендер
b1
b2
b3
b4
b5
a11
a21
a31
a41
a51
a12
a22
a32
a42
a52
Құны
с1
с2
Әрі қарай PIi түріндегі тағамдардың жалпы құны ci-ді құрайды. Адам ағзасын күндік нормасы құнарлы заттардың барлық түрін алатындай жалпы ең кіші болатын жоспарды ұһқұруымыз керек. Bi(i=1,2,...5).
x1және x2 - PI1 және PI2-дегі тағам түрлерінің мөлшері болсын. Бұл жағдайда екі түрлі тағамдағы майлардың қоры
a11x1+a12x2
және b1 минималь нормасынан аз болуы тиіс. Бұл талап
a11x1+a12x2=b1.
теңсіздігіне алып келеді.
Теңсіздектегі таңбалар тамақтану жүйесіндегі қолданылатын майлар ең кіші нормасынан көбірек болғандығын көрсетеді. Сонымен осы жағдайлардан
a21x1+a22x2=b2,
a31x1+a32x2=b3,
a41x1+a42x2=b4,
a51x1+a52x2=b5.
төрт теңсіздіктер жүйесіне келеді.
Сонымен F тамақтанудың жалпы құны
F=c1x1+c2x2.
тең. Демек біз келесі математикалық есепке орлайық.
ai1x1+ai2x2=bi (i=1, ...,5) (1.1.8)
x1,x2 айнымалы бес сызықтық теңсіздік және
F=c1x1+c2x2 (1.1.9)
сызықтық форма жүйесімен берілген.
8-жүйеден барлық теріс емес шешімдердің арасынан F- формасы ең кіші мәнге ие болатындығын табу керек.
1.2 НЕГІЗГІ ЕСЕП ЖӘНЕ НЕГІЗГІ ТҮСІНІКТЕР.
Сызықтық программалаудың негізгі есептері келесі түрде болады
a11x1+...+a1nxn=b1,a21x1+...+a2nxn= b2,. . . . . . . . . . . . . . . .am1x1+...+amnxn=bm. (1.2.1)
m- сызықтық алгебралық теңдеулер n белгісіз x1...xn айнымалылардан туратын жүйе берілген және осы белгісіздерге қатысты сызықтыө форма
F=c1x1+...+cnxn+c0 (1.2.2)
түрде жазылады.
(1.2.1) берілген жүйеден барлық теріс емес шешімдердің арасынан F сызықтық форма ең кіші мәнге ие болатын шешімді таңдау керектігін талап етеді.
Анықтама 1.1 (1.2.1)жүйені берілген есептің шектеулер жүйесі деп атаймыз.
Ескерту 1.1 Есепте x1,x2,...,xn белгісіздері тек қана теңдікті емес, сонымен қатар теңсіздікті де қанағаттандыруы тиіс.
Ескерту 1.2 Ең маңызды жайт (1.2.1)теңсіздктегі шектеулер шындыңында негізгі есептегі барлық шектеулерді қамтымайды, себебі x1,x2,...,xn айнымалылар теріс шартты қанағаттандырмауы міндетті
x1=0...xn=0
Анықтама 1.2 (1.2.1) жүйенің барлық теріс емес x1(0),...,xn0 (xi0=0;i=1,...,n) шешімдерін мүмкін шешімдер деп атаймыз.
Анықтама 1.3 (1.2.1) жүйенің F формасын минималдаушы теріс емес шешімдерін минималдаушы оптималды деп атаймыз.
Ескерту 1.3 Ережеде оптимальды шешім жалғыз болуы керек. Кей жағдайда оңтайлы шешімдер сансыз жиын болуы да мүмкін. (1.2.1) шектеулер жүйесін зерттеуге қайта оралайық. Есебімізде мынадай тұжырымдарда болуы мүмкін, егерде (1.2.1) жүйе үйлесімді болады, яғни (Кронекер-Капелла теоремасна сәйкес) негізгі матрицаның рангы сәйкес келсе. Сызықты алгебра курсынан белгілі болғандай жалпы ранг n белгісіздер санынан аспайды. Егер r=n болғанда (1.2.1)жүйенің x1(0),...,xn0 шешімдері жалғыз және ол Крамер теоремесы бойынша табылады. Егерде бұл xi0=0;i=1,...,n шешімдері мүмкін болса, онда оптимальды болатындығы айқын көрініп тұр. Егeрде xi0 сандарының ішінен бір теріс сан болса, онда есебіміздің шешімі жоқ. Шындығында оңтайлы шешім жоқ, өйткені шешімге ие болуы үшін теріс шешім бола алмайды.
Сонымен, rn болған жағдай ғана қызықтырады болса, тек сол жағдайды қарастырамыз. x1,..,xn айнымалыларымен берілген теңдеулер және теңсіздіктермен және осы айнымалыларға қатысты F сызықтық формасы берілген.
Берілген шектеулер жүйесінен барлық теріс емес шешімдері арасынан F сызықтық формасы ең кіші және ең үлкен мәнді беретін шешімдерін табу керек. Сондықтан 1-4 есептердің мәліметінде сызықтық программалаудың негізгі есептеріне келтіру үшін біріншіден формаларды: максималдау және минималдау туралы мәселені енгізу, екіншіден теңсіздік түрде берілген шектеулерден оларда кейбір эквивалентті теңдіктерде көшуді үйрену керек.
Оны қалай жасау керектігін көрсетейік.
1) x1,..,xn белгісіздердің мәндерінде F формасы ең үлкен шамаға тең болуы, сондай-ақ осы белгісіз шамаларда F1=-F ең кіші мәнге де тең болуы айқын. Шындығында да F формасының максималдылығы F1=-F формасының минималдау шартына тепе-тең. Сонымен максималдау есебі минималдау есебіне келтіріледі.
Ескерту 1.4 F формасының ең үлкен мәні F1 формасының қарама-қарсы таңбамен алынған ең кіші мәніне тең екені белгілі.
2) Есептің шектеулері арасынан кейбір теңсіздіктері бар болсын. Оны әр уақытта
α1x1+α2x2+...+αnxn+β=0 (1.2.3)
түрінде жазамыз.
Қосалқы деп аталатын теңдеулерге x1,..,xn белгісіздерімен байланысты жаңа белгісіздер енгіземіз.
xn+1=α1x1+...+αnxn+β (1.2.4)
xn+1 шамасының теріс емес шарты (1.2.3) теңсіздіктің орындалуына эквивалентті. Басқа сөзбен айтқанда егерде x1(0)...xn(0),xn+1(0) жүйесінің теріс емес x1,..,xn,xn+1 белгісіздері (1.2.4) теңдеуді қанағаттандыратын болса, онда x1(0)...xn(0) жүйесі де (1.2.3) теңсіздікті қанағаттандырады. Ал, екрісінше, егерде x1(0)...xn(0) шамалары теріс болып, (1.2.3) теңсіздікті қанағаттандырса, онда
xn+1(0)=α1x1(0)+...+αnxn(0)+β
(1.2.4) теңдеуден табылған шамалары теріс болып табылады.
Демек (1.2.3) теңсіздік (1.2.4) теңсіздікпен эквивалентті. Сонымен қосымша айнымалылар енгізу арқылы теңсіздіктерді теңдеулерге айналдыруға болады. Сондықтан берілген есепте қосымша белгісіздер теңсіздіктегі шектеулер санына тең.
Есеп 1 (1.1.1) жүйедегінің барлық мүшесінің шектеулерін оң жағына көшіретін болсақ, онда ол келесі түрде болады.
0=19-2x1-3x20=13-2x1-x20=15-3x20 =18-3x1 (1.2.5)
2) Ережесі бойынша қосымша x3,x4, x5,x6, белгісіздер енгізіп, келесі жаңа теңдеулер жүйесіне көшеміз.
x3=19-2x1-3x2x4=13-2x1-x2x5=15-3x2x 6=18-3x1 (1.2.6)
1) Ережеге қатысты F=7x1-5x2 максималдау формасының орнына F1=-F=-7x1-5x2 минималдау формасын аламыз.
Есеп 2. Шектеулерменберілген (1.1.3)
0=T-x1-x2,0=T-x3-x4,a1x1+b1x3=N1, a2x2+b2x4=N2, (1.2.7)
қосымша x5,x6 белгісіздерін енгізіп теңсіздіктен теңдеулер жүйесіне көшеміз.
x5=T-x1-x2,x6=T-x3-x4,a1x1+b1x3=N1, a2x2+b2x4=N2, (1.2.8)
(1.1.9) жүйенің теріс емес шешімдерінің арасынан F= α1x1+α2x2+β1x3+β2x4 формасы үшін (оптимальды) оңтайлы шешімді таңдап алуға болатындығы шығады.
Есеп 3. Транспорт есебінің негізгі түрі бар.
Есеп 4. (1.1.8) теңсіздіктер жүйесін
a11x1+a12x2-b1=x3,a21x1+a22x2-b2=x4 ,a31x1+a32x2-b3=x5,a41x1+a42x2-b4=x 6,a51x1+a52x2-b5=x7 (1.2.9)
теңдеулер жүйесімен алмастырамыз. Минимальданатын F=c1x1+c2x2 формасы өзгеріссіз қалады.
5-ші есептегі мәліметтерді негізгі әдістермен көрсетейік. 5-ші есептердегі математикалық шартын еске түсірейік.
Жүйенің теріс емес шешімдерінің арасынан
x11+x21=50,x12+x22=30,x13+x23=45, (1.1.10)
екі сызықтық формасы бірдей максимумдары
t1=4x11+10x12+10x13,t2=6x21+8x22+20 x23, (1.1.11)
минималь болатын Т шамасын табу керек.
Берілген есептердегі мәліметтер үшін (1.1.10) шектеулер қатарынан негізгі есепті және екі теңсіздіктерді қарастырамыз.
y=t1,y=t2 (1.2.10)
және сызықтық форма F=y.
Енді (1.1.10) және (1.2.10) шектеулердің сызықтық форманы минимизациялайтын шешімін іздейік және бұл қандай нәтіжеге келтіндігін көрейік.
Біріншіден xij теріс емес шешімдерден t1 және t2 теріс еместігі туындайды сондықтан y- те теріс емес болады.
Екіншіден F=y формасына тең болса, онда F-ті минимизациялайтын болсақ ол y-ті минимизациялау дегенді білдіреді. Бірақ y-тің ең кіші мәні (1.2.10) теңдікті қанағаттандыратын болса автоматты түрде t1және t2 мәндерінің ең үлкен мәндері теңеседі, басқаша айтқанда ymin=max( t1, t2) (1-сурет).
Cурет 1
Басқа сөзбен айтатын болсақ F формасының ең кіші мәні әрқашанда max( t1, t2) тең. Сонымен (1.1.10) және (1.2.10) шектеулер жүесінің табылған шешімдерінен F=y формасының ең кіші мәнін беретін болса, онда (1.1.10) жүйесінің мұндай шешімдерінен Т=max( t1, t2). Шамасы ең кіші мүмкін мәндері болып табылады.
Демек 5-ші есеп (1.1.10) және (1.2.10) шектеулермен берілген F=y формасының минимизациясына эквивалентті.
(1.2.10) теңсіздіктер жүйесі көрсетілген 2 әдіс бойынша теңдеулер жүйесіне келтіріледі. 5-ші есептің соңғы қадамының нәтіжесінде шектеулер жүйесі негізі түрге келеді.
x11+x21=50,x12+x22=30,x13+x23=45,y- 4x11-10x12-10x13=z1y-6x21-8x22-20x2 3=z2
бұл жерде z1 және z2- қосымша айнымалылар және минимизацияланатын форма.
Бұл есепте y шамасы айқын экономикалық мағынаны береді. (1.2.10) теңсіздікті қанағаттандыратын y-тің кез-келген мәнін xij шамасымен берілген жоспарды уақыт ретінде түсіндіруге болады. Сондықтан ymin үшін берілген жоспарды xij -ң ең аз уақыт ішінде жүзеге асыруға қажетті болады.
Сызықтық бағдарламалау есептерінен 1.1 келтірілгендей бұл есептегі шектеулер әртүрлі беріледі: олардың арасында теңдік ретінде де кездеседі, сондай-ақ теңсіздік түрінде де кездеседі. Бір қарағанда мұндағы негізгі есептегі шектеулер біртексіздікті көрсетеді. Бірақ бұлай болуы мүмкін емес, (1.2.1) шектеулер теңдігіне басқалары x1,...,xn шамасымен байланысқандары шектеулер теңсіздіктерінде орындалады. Бұл эквивалентті есептердегі барлық шектеулер тек қана теңсіздіктен тұрады.
Шектеулері теңсіздіктермен берілген сызықтық программалаудың негізгі есебі
Шектеулер берілген (1.2.1) жүйені қарастырамыз. 2.1 аталғандай rn жағдайын қарастырайық(r-жүйенің рангы, n-белгісіздер саны). Сызықтық алгебрадан белгілі болғандай бұл жағдайда r-белгісіздер n-r=k қалған белгісіздері арқылы сызықты өрнектеледі(бұл соңғы қабылдағандарды бос мүше деп атаймыз). Әрқашанда белгісіздерді нөмірлеуге болады, соңғы xk+1,...,xn белгісіздерін x1,x2,...,xk алғашқы белгісіздері арқылы өрнектеледі(n=k+r болса, онда xk+1,...,xn белгісіздері r қанша болса сонша дәлдікпен алынады).
xk+1=α11x1+α12x2+...+α1kxk+β1,xk+2= α21x1+α22x2+...+α2kxk+β2,. . . . . . . . . . . . . . . . . . . . . . . . . . .xn=αr1x1+αr2x2+...+αrkxk+βr. (1.2.12)
(1.2.12) жүйе (1.2.1) жүйеге эквивалентті.
(1.2.2) өрнектегі xk+1,...,xn шамаларының орнына (1.2.12)-гі мәндері F формасына қойсақ, онда F форма басқа түрге келеді.
F=γ0+γ1x1+...+γkxk (1.2.13)
яғни бұрынғы сызықтық түрде қалады, бірақ тек қана x1,...,xn бос белгісіздері арқылы өрнектеледі.
Негізгі есепті шеше отырып, (1.2.1) жүйенің теріс емес шешімдерін шектейміз. Сондықтан теңсіздік қажеттілікпен орындалуы тиіс.
xi=0 i=1,2,...,n. (1.2.14)
Егер (1.2.12) теңдікті ескерсек, онда i=R+1, R+2,...,n үшін
0=α11x1+...+β1,0=α21x1+...+β2,. . . . . . . . . . . . . .0=αr1x1+...+βr
теңсіздігін аламыз.
xi бос белгісіздер үшін (i=1,...,k) (1.2.14) теңсіздікті қайта жазамыз. Келесі жүйе
x1=0,. . . . .xk=0,α11x1+...+α1kxk+β1=0,. . . . . . . . . . . . . . . . . . .αr1x1+...+αrkxk+βr=0. (1.2.15)
R белгісіздеріне қатысты n сызықтық теңсіздігі бар жүйеге көшеміз. (1.2.12) жүйенің мүмкін шешімдері (1.2.15) теңсіздіктің шешімдері бола алатындығы айқын. Ал керісінше қалауымызша x10,...,xk0 (1.2.15) жүйенің шешімдерін алсақ, және (1.2.12) формула бойынша табатын болсақ,
xk+i0=αi1x1(0)+...+αikxk0+βi i=1,...,n,
шамаларын аламыз, демек (1.2.12) және (1.2.1) жүйенің шешімдері теріс еместігі айқын. Сонымен қатар (12) теңдеулер жүйесінен теріс емес шешімдерді іздеу үшін (1.2.15) теңсіздіктер жүйесінің барлық шешімдерін іздейміз.
Нәтижесінде келесі математикалық есепке келеміз. (1.2.15) x1,...,xk - ке қатысты k белгісізді n сызықтық теңсіздіктер жүйесі және
F=γ0+γ1x1+...+γkxk (1.2.13)
сызықтық формасы берілсін.
(1.2.15) жүйемен F формасы ең кіші мәнге ие блатындай шешімді табу керек.
(1.2.15) жүйенің шешімдерінен F формасының ең кіші мәнеге ие болуын оңтайлы шешім деп атаймыз.
Аталған есептерді шешу барысында сызықтық программалаудың негізгі есептері қойылған есепке эквивалентті. Мұндай есептерді шектеулі теңсіздіктермен берілген сызықтық программалаудың негізгі есебі деп аталады қысқаша түрде (А) түрдегі есеп деп атаймыз.
Есеп 1 2-ші тараудағы мәліметтерге сүйеніп келесі жүйедегі шектеулерге келеміз.
x3=19-2x1-3x2,x4=13-2x1-x2,x5=15-3x 2,x6=18-3x1 (1.2.6)
және F1=-7x1-5x2. (1.2.6) - жүйеден I матрицасын жазамыз.
I=2 3 1 0 0 02 1 0 1 0 00 3 0 0 1 03 0 0 0 0 1.
Бұл есепте ранг тең, сонымен ал
Жалпы схемаға сәйкес төрт белгісізді қалған екеуі арқылы өрнектеледі (1.2.6) жүйеден байқағанымыздай соңғы белгісіздер алғышқы арқылы өрнектелген. Барлық теріс емес белгісіздерді қолданып келесі теңсіздіктер жүйесіне келеміз.
x1=0,x2=0, 19-2x1-3x2=0,13-2x1-x2=0,15-3x2= 0,18-3x1=0. (1.2.16)
Сонымен 1-ші есеп (А) түрдегі математикалық есепке келеді.
Есеп 2 Бұл есепке (A) формасын берейік. Шектеулер жүйесі және сызықтық форма мына түрде беріледі:
x1+x2=T,x3+x4=T,a1x1+b1x3=N1,a2x2 +b2x4=N2, (1.1.3)
F=α1x1+α2x2+β1x3+β2x4. (1.1.4)
(1.1.3) және (1.1.4) шамаларға мәндер беріп есепті нақтылаймыз. a1=6, a2=24, b1=13, b2=13, N1=30, N2=96, T=6, α1=4, α2=47, β1=13, β2=26.
Сонда шектеулер жүйесі мен F формасы
x1+x2=6,x3+x4=6,6x1+13x3=96,24x2+ 13x4=96, (1.2.17)
F=4x1+47x2+13x3+26x4.
түрге келеді.
Алғашқы екі теңсіздіктерді өзінде қалдыра отырып, x3 және x4 теңсіздіктерді x1 және x2 арқылы өрнектейміз.
x3=11330-6x1,x4=11396-24x2. (1.2.18)
Әрі қарай, берілген теңсіздіктің сол жағына және F формасын бос белгісіздермен өрнектеп, нәтижесінде
x3+x4=11330-6x1+11396-24x2=6,
F=4x1+47x2+30-6x1+2(96-24x2)
аламыз немесе қарапайым алгебралық түрлендіруден соң
x1+4x2=8,
F=222-2x1-x2.
аламыз.
x3 және x4 теріс емес шешімдері теңсіздікке эквивалентті
11330-6x1=0,
11396-24x2=0,
соңғы элементар түрлендірулерден соң
x1=5, x2=4.
x1+x2=6 және барлық теріс емес шешімдерін ескере отырып, келесі шектеулерді аламыз:
x1=0,x2=0,x1=5,x2=4,x1+x2=6,x1 +4x2=8. (1.2.19)
Сонымен минималданатын форма келесі түрде болады:
F=222-2x1-x2. (1.2.20)
1.3 ЕСЕПТІҢ ГЕОМЕТРИЯЛЫҚ МАҒЫНАСЫ
Алдыңғы параграфта сызықтық программалау есебі жайлы айтылған. Онда түрлі типте берілген есептерді негізгі есепке келтіру түрлері кқрсетілген. Негізгі есепті шешу үшін әртүрлі әдістер ойлап табылды. Бұл әдістер аналитикалық сипатқа әкеледі. Бұл әдістердің кейбірін кейінрек қарастырамыз.
Бұл параграфта біз негізгі есептердің геометриялық түсіндірмесін қарастырамыз. Бұл түсіндірмелерде аналитикалық әдістің маңыздылығын терең әрі оңай түсінуге көмек беріп, көрінісі анық болады.
Сызықтық программалаудың негізгі есебінің геометриялық берілуі анық болады, егерде бұл түрден шектеулері теңсіздіктермен ьерілген эквивалентті есептерге көшетін болсақ онда мына түрдегі есептің қойылуын еске түсірейік құрамында n=k+r k белгісіздеріне қатысты x1,...,xk сызықтық теңсіздік пен
F=γ0+γ1x1+...+γkxk (1.2.13)
сызық формасы бар мына
x1=0,x2=0,. . . .xk=0,a11x1+...+a1kxk+β1=0,. . . . . . . . . . . . . . . . . . .ar1x1+...+arkxk+βr=0, (1.2.15)
жүйе берілсін.
(1.2.15)жүйенің шешімдерінің арасынан F формасы ең кіші мәнге ие болатын шешімді табу керек.
Есеп 3 F1 формасы мен шектеулер бұл есепте (А) типтегі есептер сияқты қойылған және мына түрде болады.
x1=0,x2=0,19-2x1-3x2=0,13-2x1-x2 =0,15-3x2=0,18-3x1=0, (1.2.16)
F1=-7x1-5x2.
Жазықтықтағы тікбұрышты декарттық жүйесіне x1Ox2 координаталарын енгіземіз. Жазықтықтағы нүктелердің геометриялық орны белгілі болса, сызықтық теңсіздіктер жүйесін қанағаттандыратын координаталар дөңес көпбұрышты құрайды. Бұл көпбұрыштарды берілген теңсіздіктер жүйесінің шешімдерінің көпбұрышы деп атайды. Егерде теңсіздіктер жүйесіндегі теңсіздік таңбасын тура теңдікке ауыстырып, алынған теңдеудегі көпбұрыштың қабырғалары түзуде орналасады. Бұл жүйенің әрбір теңсіздігі жарты жазықтықты, шекаралық түзулерді құрайды. Біздің жағдайымызда мұндай түзулер мына түрде болады.
x1=0, Ix2=0, (II)19-2x1-3x2=0, III13-2x1-x2=0, IV15-3x2=0, V18-3x1=0, (VI)
(2)-суреттегі түзулерді сызайық, мұндағы стрелкалар жарты жазықтықтардың қиылысуы көпбұрыштық шешімдерін береді.
Сурет 2
Сонымен бірге F1=-7x1-5x2 формасын қарасытрайық. Бұл жазықтықтағы (x1,x2) нүктелер сызықтық функцияның (x1,x2) координаталары болатындығын көрсетеді. Бұл мәселеге жазықтықта осы F формасы бір және сол С мәнді қабылдау үшін нүктелер қалай орналасады деген сауал қояйық.
Қойылған сұраққа жеткілікті түрде F1 формасы С мәнді қабылдайды және
-7x1-5x2=C (1.3.1)
теңдеуін алады.
Бұл теңдеулер жазықтықта түзулерді береді. Бұл түзулер F1 формасы берілген С мәнді қабылдағандағы нүктелердің геометриялық орнын береді. C-ң мәнін өзгертсек, әртүрлі түзулерді аламыз, бірақ олар өзара параллель түзулер, яғни параллель түзулердің шоғырын құрайды. Жазықтықтағы әрбір нүкте арқылы бір түзу өтеді. Осы түзулер (1.3.1) шоғырындағы әрбір түзуден F1 формасының сызықтық деңгейі деп аталатын деңгейді қабылдауға болады. Бір түзуден келесі түрге көшкенде F1 формасының мәні өзгереді. 3 - суретте
Cурет 3
C=-17,5;-35;-52,5 мәндерімен берілген түзулер көрсетілген y-векторы форманың үлкен мәнінен кіші мәніне көшкендегі қозғалыс бағытын көрсетеді.
Аналитикалық курсынан белгілі болғандай түзудің теңдеуіндегі айнымалы коэффиценттер n векторының проекциясы түзуге перпендикуляр болады. Біздің жағдайымызда n=-7;-5. Біздің байқағанымыз F1 формасының кему бағыты, n векторының бағытына қарама-қарсы.
2-суретке қайта оралайық. Көпбұрыштар шешімінен P0(x10,x2(0)) кез-келген нүктесін қарастырайық. Бұл нүктелер (1.3.1) түзулер шоғырынан өтеді. Бұл түзулердің бойынан F1 формасы мынадай мәнді P0 нүктесі сияқты,яғни C0(-7x10,-5x2(0)) мәнді қабылдайды.
2-суретте пунтирленген түзулер C=-35 мәнін көрсетеді. P0 нүктесі есептің оңтайлы шешіміне сәйкес келмейді. Сондықтан көпбұрыш шешімдерінің ішінен фoрма мәніне сәйкес келетін C0-ден кіші болатын нүктені табуға болады. Барлық көпбұрыштың шешімдері болатын түзулер қиылысады, ол үшін y векторының бағытымен C0 түзуден басқа түзуге () түзулер шоғырына параллель болатын түзулерге көшу жеткілікті болады.
Енді шешім анық болу үшін оңтайлы шешім Q5;-3 нүктесінде анықталып, ол F1 формасының ең кіші мәні F1min=-7∙5-5∙3=-50 тең емес 1-есептің оңтайлы шешімі x1=5, x2=3 табылды.
Егерде (1) беттегі есептің шартын еске түсіретін болсақ, онда шикізат қолданудың рационды жоспары үшін кепілдік беретін өнеркәсіптердің түсім үлкен, 5 бірлік П1 түрдегі өнімді және түрдегі өнімді және 3 бірлік П2 түрдегі өнім шығару керек және онда түсетін ең үлкен түсім Fmax=50 құрайды.
Сонымен S1 және S2 түрдегі шикізат толықтай пайдаланылады, S2 және S4- жартылай қолданылады(бұдан табылған шешімдер бойынша x1=5, x2=3).
Ескерту 1.4 Бұл 1-есептегі геометриялық түсіндірмесі тек қана есептің қойылуына емес, сонымен қатар есептің есептің шешімін табуға көмектеседі.
Ескерту 1.5 Математикалық талдау курсынан функциялардың экстремаль нүктелерін табу белгілі. Онда бұл есептерді дифференциалдық есептеулермен шығарылады. Неліктен бұл әдістерді сызықтық программалау есептерін шешуде қолдануға болмайды. Демек, дифференциалдық есептеу әдістері шекарадағы емес, қатаң облыстағы эксремаль нүктелерді анықтайды. Сызықтық программалау есептерінде форманың оңтайлы әруақытта көпбұрышты шешімдерінің шекараларында болады. Мысалыға 1-есепте. Сондықтан дифференциалдық есептеу әдістерін мұндай есептерді шешуге қолдануға болмайды.
Есеп 4 Геометриялық түсіндірмесін бере отырып, 2-есептің шешімдерін аламыз. (A) түрдегі есепке келтіре отырып (20 бет) біз келесі шектеулерді аламыз.
x1=0, Ix2=0, IIx1=5, IIIx2=4, IVx1+x2=6, Vx1+4x2=8, (VI) (1.2.19)
F=222-2x1-x2. (1.2.20)
Жазықтықтағы координат жүйесіне x1Ox2 енгізе отырып 1-ші есепке ұқсас (1.2.19) жүйенің көпбұрыштар шешімін сызамыз. Ол үшін (1.2.19) жүйедегі теңсіздіктерді теңдікке алмастырып, сәйкесті түзулерді сызамыз(сурет 4 ). Бұл суретте (1.2.20) форманың F=219 мәніне сәйкес сызықтың деңгейінің біреуі сызылған. g векторы F форманың кему бағытын көрсетеді.
Сурет 4
Сызбадан көрінгендей F формасы ең кіші мәнге көпбұрыштар шешімдерінің М (5,1) нүктесінде (III) және (V) түзулердің қиылысуында болады. x1=5,x2=1 болғанда (1.2.20) теңдеуден сызықтық форманың ең кіші мәні
Fmin=222-2∙5-1=211
тең болады.
Алынған шешімдерден қандай экономикалық тұжырымды байқауға болады. xi(i=1, 2, 3, 4) шамалары А және В машиналарының П1және П2 түріндегі өнімдердің дайындауға кеткен уақыт екендігін еске түсірейік. x1=5, және x2=1 шамалар белгілі, ал енді x3,x4 шамаларын (1.2.18) теңдеулерден табамыз
x3 =11330-6x1=11330-30=0,
x4 =11396-24x2=11396-24=7213.
cонымен есеп толығымен шығарылды.
Есеп 5 Геометриялық түсіндірмелер арқылы 3-ші есепті шешейік. Шектеулермен минимизацияланатын форма (А түрге келтірілгеннен соң ) мына түрде болады.
20-x11-x12=0, I10-x11=0, II30-x12=0, III-10+x11+x12=0, IVx11=0, V x12=0, (VI) (1.3.1)
F=330-2x11-x12. (1.3.2)
Жазықтықтағы координаталар жүйесіне енгізейік. Бұл жолы x11, және x12 деп осьтерді белгілейік. F формасын бір сызықтық деңгеймен көпбұрыш шешімдерін сызайық (5-сурет).
Сурет 5
N(10;10) нүктесінде оптималь шешімді береді, демек x11=10, x12=10, Fmin=300 қалған xij мәндері (1.2.20) теңдеулері табылады.
x13=20-x11-x12=0,
x21=10-x11=0,
x22=30-x12=20,
x23=-10+x11+x12=10.
2 СИМПЛЕКС ӘДІСІ
2.1 ӘДІСТІҢ ИДЕЯСЫ ЖӘНЕ АЛГЕБРАСЫ
1°. Сызықтық программалаудың негізгі есебін қарастырайық.
a11x1+...+a1nxn=b1,a21x1+...+a2nxn= b2,. . . . . . . . . . . . . . ..am1x1+...+amnxn=bm. (2.1.1)
m сызықтық теңдеулері n белгісізді x1,...,xn және осы белгісіздерге қатысты
F=c1x1+...+cnxn (2.1.2)
сызықтық форма берілген.
(2.1.1) теңдеулер жүйесінен теріс емес шешімдерінен F формасы ең кіші мәнге ие болатын шешімді табамыз. 1-тараудың 1.2 көрсетілгендей негізгі есептер (A) шектеулер теңсіздіктер болатын есепке егер бос белгісіздер k=n-r санына тең болып (мұнда n- барлық белгісіздер саны, ал r- (5.12)жүйенің рангі) эквивалентті түрге келеді. 1 тарудағы 1.3 көрсетілгендей k=2 болғанда негізгі есеп геометриялық әдістермен шешіледі. k2 болғанда негізгі есепті геометриялық әдістермен шешу мүмкін емес. Сондықтан мұндай есептерді аналитиалық әдістермен шешу қажет екендігін түсіндірейік. Осындай ұқсас әдістерді қазіргі уақытта симплекс- әдісі деп атаймыз. Бұл әдістің идеясын қарапайым мысалдармен түсіндірейік.
2° (2.1.1) жүйе мынадай шектеулермен және сызықтық формамен берілсін
x2+2x4+3x5-7=0,x3-x4-3x5-2=0,x1+x4+ x5-2=0, (2.1.3)
ал форма
F=3-x4+x3. (2.1.4)
(2.1.3) жүйенің үйлесімді екендігін оңай көз жеткізуге болады. Оның рангі r=3 , ал бос белгісіздер R=5-3=2. Бұл есепті геометриялық түрге шешуге болады. Алайда біз бұл әдіспен емес басқа әдістермен есепті шешіп көрейік. Бос белгісіздер ретінде x4және x5- ті, ал белгісіздер x1,x2,x3 арқылы алып, F формасы сол белгісіздер арқылы өрнектейміз.
x1=2-x4-x5, x2=7-2x4-3x5,x3=2+x4+3x5. (2.1.5)
(2.1.4) теңдеуден көрінгендей F формасы бос белгісіздер арқылы өрнектелген. Сонымен xi барлық шамалары қаншалықты теріс болса, онда бос белгісіздердің мәнім ен бос емес (базисты) белгісіздердің ең кіші мәні нөлге тең: x4=0, x5=0. Осындай бос белгісіздердің мәні тең. x1=2, x2=7, x3=2. Сонымен көріп тұрғанымыздай бұл мәндер оң, мәндер жүйесі
x2=2, x2=7, x3=2, x4=0,x5=0 (2.1.6)
болғанда (2.1.3) жүйеден мумкін шешімдерді құрайды. Сонымен табылған шешімдерден F форма F=3 мәнге тең болады.
Бос белгісіздер x4 және x5-ті нөлге тең деп алсақ бірақ бұл таңдауымыз ешнәрсені нақтылай алмайды. x4 және x5 мәндерін жоғарлату арқылы F формасының кіші мәнге тең болуына болады ма соны көрейік. F формасы үшін (2.1.4) өрнектен x5 белгісізі (2.1.4) -ге оң таңбамен кіретін болса, онда мәндерді үлкейту,форманы да жоғарлатуға әкеледі. Бұл бізге қолайсыз. Бұл уақытта x4 белгісізі (2.1.4) - ге теріс таңбалы кіреді. Сондықтан x4-ң мәні ұлғайған сайын, F формасы аз мән қабылдауда жалғастырады. Тек бір ғана нәрсені түсіну керек, x4 бос белгісіздерді ұлғайту базисті белгісіздерге өзгерістер жасайды. Бұл өзгерістер базисті белгісіздер теріс болуы мүмкін, яғни мүмкін емес шешімдерге келеміз. Ал мүмкін емес шешімдер қарастырылмаған. Шындығында (2.1.5)-ң бірінші тіңдеуінен x42 болса, онда x1 белгісіз теріс болады. Ал осы уақытта 2.1.4 және 2.1.5 теңдеулерден x4 ұлғайтқан сайын x4=2, x3 белгісізі ұлғаяды, ал x3 белгісізі кемиді бірақ оң болып қалады. Сонымен x4=2 мәні қолайлырақ болады. Өйткені
x1=0, x2=3, x3=4, x4=2, x5=0. (2.1.7)
Демек біз жаңа мүмкін шешімдерге оралдық. Алдыңғылардан байқағанамыздай (2.1.7) жаңа шешімдерінен F формасының мәні (2.1.6) шешімдерінен аз. Бұл шешімдерді салыстырайық. Олардың ішінде әрбір екі белгісіздері нөлге тең болады. (2.1.7) - ң шешімдерінен x1 және x5 нөлдік мәнге ие, ал (2.1.6)-ң нөлдік мәндері x4 және x5 бос белгісіздерінен таңдалған. Сондықтан бос белгісіздер ретінде x4 және x5 белгісіздерді емес, x1 және x5- терді алса F формасы шынайырақ көрінер еді, атап айтқанда бұл белгісіздер жаңа шешімдерде нөлдік мәнге ие. Осындай мақсатпен (2.1.5) жүйенің бірінші теңдеуінен x4 - ті x1 және x5 арқылы өрнектейміз
x4=2-x1-x5.
аламыз.
Алынған шешімдерді (2.1.5) жүйенің екінші және үшінші теңдеулеріне қойсақ F формасы үшін.
x2=3+2x1-x5, x3=4-x1+2x5,x4=2-x1-x5, (2.1.8)
F=1+x1+2x5. (2.1.9)
табамыз.
Енді (2.1.9) форма және (2.1.8) жүйелер үшін аналогиялық талқылау жасайық. Барлық x1,x5 белгісіздерін өсірген сайын F формасының ұлғайуына әкеледі. Сондықтан x1 және x5 - тер нөлге тең болғанда F формасы F=1 ең кіші мәнге жетеді. Осы x1=0, x5=0 мәндерін (2.1.8) қойып (2.1.7) шешімдеріне келеміз. Сонымен (2.1.5) мүмкін шешімдері ізделінді оңтайлы шешім болады.
3°. Жалпы жағдайға қайта оралайық (2.1.1) шектеулер жүйесінде қандайда бір k елгісізі бос мүше ретінде алынсын. Оларға кез келген мән беруге болады, ал қалған белгісіздер теңдеулер жүйесінен табылады.
Анықтама.1 (2.1.1) шектеулер жүйесінің шешімі бос белгісіздердің мәндері нөлдік мәнмен сәйкес болса, оларды базисты деп атаймыз.
Әрбір таңдалған еркін айнымалылардың базисті шешімдері бар екендігін байқадық. Бұдан әрі бізді осы мүмкін базисті шешімдерді табуды қарастырамыз.
Алынған мысалды қарастыра отырып, (2.1.6) және (2.1.7) шешімдер (2.1.5)жүйені мүмкін базисті шешімдері болып табылады. Олардың біріншісі x4 және x5 айнымалылары еркін айнымалы ретінде, ал екіншісі x1және x5 еркін айнымалылары ретінде алынады.
4 °. 1 ші есептің шешімдерін аналитикалық әдіспен шешуді қарастырайық.
Шектеулер жүйесін және сызықтық формасын жазайық.
x3=19-2x1-3x2,x4=13-2x1-x2,x5=15-3x 2,x6=18-3x1 (2.1.10)
F1=-7x1-5x2
Егерде x1 және x2 еркін айнымалы ретінде алсақ онда сызықтық форма F1 базисті белгісіздері арқылы өрнектелген. Базисті шешімдерін алайық
x1=0, x2=0, x3=19, x4=13, x5=15, x6=18. (2.1.11)
(2.1.11) өрнектегі екі бос белгісіздердің коэффиценттері теріс таңбалы. Сондықтан олардың кез келгенінің көбеюі. F формасының азаюына әкеледі. Мысал ретінде x2- шектеуден бастайық. Мысалы x2 мәнін көбейтейік. x2 айнымалысы x2=5 болғанға дейін өседі. x5 базисті айнымалы нөлге айналып, қалған базисті айнымалылар оң таңба қалпында қалады. Жаңадан x1 және x5 еркін айнымалылар жұбын енгізейік. x2, x3, x4, x6 жаңа базисты айнымалыларды және F форманы x1, x5-арқылы өрнектеп
x2=5-13x5,x3=4-2x1+x5,x4=8-2x1+13x5 ,x6=18-3x1, (2.1.12)
F=-25-7x1+53x5. (2.1.13)
аламыз.
Еркін айнымалыларды таңдауда үйлесімді базисті шешімдері есептің
x1=0, x2=5, x3=4, x4=8, x5=0, x6=18. (2.1.14)
шешімдер болып табылады.
Сонымен, F1=-25. (2.1.13) өрнекке x1 айнымалысы теріс коэффицентпен кіреді, сондықтан оның өсуі F формасының кемуіне алып келеді. x1 мәнін x1=2 мәніне дейін өсіреміз. Сондықтан x3 нөлге айналады, ал қалған базисті айнымалылар оң мәнді сақтайды. Енді x3 және x5 бос белгісіздерін алайық. Олар арқылы F1 формасын және базисты айнымалыларды өрнектейік.
x1=2-12x3+12x5,x2=5-13x5,x4=4+x3-23 x5,x6=12+32x3-32x5,
F1=-39+72x3-116x5.
табамыз.
Сәйкесті үйлесімді базисті шешімдері мыналар:
x1=2, x2=5, x3=0, x4=4, x5=0, x6=12. (2.1.15)
cонымен F1=-39.
Аналитикалық қорытындылар жасай отырып, x3 және x4 бос белгісіздер ретінде қабылдап,
x1=5+14x3-34x4,x2=3-12x3+12x4,x5=6+ 32x3-32x4,x6=3-34x3+94x4,
F1=-50+34x3+114x4.
аламыз.
Осындай бос белгісіздерді таңдауда мүмкін базистік шешімдері
x1=5, x2=3, x3=0, x4=0, x5=6, x6=3.
болады.
Сонымен базистік шешімдер оптимальды болып, ең кіші ...F1min=-50 бoлады. Есеп шешілді.
5° Жоғарыда баяндалған есептің шешу әдісі бір мүмкін базистік шешімнен басқа шешімге көшу әдісімен шығарылды. Бірақ мұндай әрбір көшуде минимизацияланатын фрманың кемуіне алып келеді.
Енді симплекс әдісінің растаушы теориясын тұжырымдайық.
Теорема 2.1 Қандайда бір сызықтық программалау негізгі есебі берілсін. Осы есептің (оптималь) оңтайлы шешімі бар деп ұйғарайық. Сонда бұл есепте ең болмағанда бір ғана оңтайлы базистік шешімдер бар.
Түсіндірме Біз ереже бойынша оңтайлы шешімнің жалғыздығын айтқан болатынбыз. Бірақта кейде оңтайлы шешім жалғыз емес жағдайларыда болуы мүмкін. 1-ші теореме осындай оңтайлы шешімдердің арасында бір жаңа базисті шешімі бар екендігін айтады. Егерде есепте бір ғана оңтайлы шешім бар болса, онде ол базисті болып табылады. Бұл теремены дәлелдеусіз қабылдаймыз.
6°. Алдыңғы параграфта симплекс әдісінің қарапайым мысалдармен идеясын түсіндіріп, бұл әдістің теоремаларын расталған болатын. Қазір біз сызықтық программалаудың негізгі есептерін қарастырып, оны симплекс әдісімен шешудегі минимизацияланатын форма мен шектеулер жүйесінің алгебралық түсіндіру заңын үйренеміз.
Шектеулер жүйесімен негізгі есептің сызықтық формасы мына түрде болады.
a11x1+...+a1nxn=b1,. . . . . . . . . . . . . . .am1x1+...+amnxn=bm, (2.1.16)
F=c0+c1x1+...+cnxn. (2.1.17)
(2.1.16) жүйесінің рангі n белгісіздер санынан кіші. Әрқашан белгісіздерді нөмерлеуге болады, бос белгңһісіздерді теңесу үшін (k=n-r) алғашқы белгісіздері шығады.
Бұл жағдайда базисты айнымалыларды xk+1,...,xn , деп өрнектеп, F форманы сол бос айнымалылар арқылы өрнектесек
xk+1=α'11x1+...+α'1kxk+β1,. . . . . . . . . . . . . . . . . . . . .xk+l=α'l1x1+...+α'lkxk+βl,. . . . . . . . . . . . . . . . . . . . .xn=α'r1x1+...+α'rkxk+βr, (2.1.18)
F=γ0+γ'1x1+...+γ'kxk. (2.1.19)
қатынастарға келеміз.
Бос белгісіздер арқылы
x1=0,...,xk=0, xk+1=β1,..., xn=βr. (2.1.20)
базисті шешімдер болады.
(2.1.20) шешімі бос белгісіздер арқылы жасанды деп табылсы. Бұл дегеніміз β1,...,βr теріс емес. F формасы сонымен γ0- тең.
Енді (2.1.20) жасанды базистышешімдерден басқа базисты шешімге F формасы γ0- ден кіші болатын мәнге ие болу үшін көшеміз. Ықшамдау үшін (2.1.18) жүйе мен (2.1.19) фoрманы мына түрде қайта жазамыз.
xk+1=β1-(-α'11x1-...-α'1kxk),. . . . . . . . . . . . . . . . . . . . .xk+l=βl-(-α'l1x1-...-α'lkxk),. . . . . . . . . . . . . . . . . . . . .xn=βr-(-α'r1x1-...-α'rkxk),
F=γ0-(-γ'1x1-...-γ'kxk).
қысқаша белгілеулер енгіземіз.
-α'ij=αij;-γ'i=γi(i=1,...,k; j=1,...,r)
келесі жүйе мен формаға келеміз.
xk+1=β1-(α11x1+...+α1kxk),. . . . . . . . . . . . . . . . . . . . .xk+l=βl-(αl1x1+...+αlkxk),. . . . . . . . . . . . . . . . . . . . .xk+i=βi-(αi1x1+...+αikxk),. . . . . . . . . . . . . . . . . . . . .xn=βr-(αr1x1+...+α'rkxk), (2.1.21)
F=γ0-(γ1x1+...γkxk). (2.1.22)
Ескерту 2.1 Барлық жағдайда симплекс әдісі бойынша шектеулер жүйесі мен минималданатын F формасын (2.1.21) және (2.1.22) түрде жазамыз. Мұндай жазба барлық топтағы бас белгісізі бар қосындылар алдында жалпы минус таңбасы қойылады.
7°. (2.1.21) және (2.1.22) -дағы бос мүшелерді және бос белгісіздердің барлық коэффициенттерін жалпы таблицаға енгіземіз, оны симплекс -таблица деп атаймыз, бос белгісіздер жиынына сәйкес келетін.
Кесте 8
Бос
белгісіздер
Базисті
белгісіздер
x1...
xs...
xj
...
xk
xk+1
β1
α11
α1s
α1j
...
α1k
Кесте 8 жалғасы
...
...
...
...
...
...
...
xk+l
βl
αl1
αls
αlj
...
αlk
...
...
...
...
...
...
...
xk+i
βi
αi1
αis
αij
...
αik
...
...
...
...
...
...
...
xn
βr
αr1
αrs
αrj
...
αrk
F
γ0
γ1
γs
γj
...
γk
Бұл кестенің әрбір қатары теңдеудің базистік белгісіздерді бос белгісіздер арқылы көрсетуіне жауап береді. (2.1.22) өрнектің құрамына F формасы γi коэффициенттін кіретін бос белгісіздерді қарастырайық. Осы қарастырылатын бос белгісіздерден кез- келген біреуін таңдаймыз, мысалыға xj (xj үшін алынан) бос белгісіз (2.1.22) өрнектің құрамына γi ең кіші оң коэффициентпен кіретіндей етіп таңдауымыз керек. Бірақ бұл шарт міндетті болып табылмайды.
Егерде барлық бос белгісіздерді xj-деп басқаларын нөлдік мәндерімен сақтасақ, ал xj өсірсек, онда ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
Қазіргі заманғы қоғамның дамуын мынадай деңгейлермен сипаттауға болады: техникалық білімдерінің жоғарылауымен, өндіріс орындары талаптарының өсуімен, қоғамдық еңбек дамуымен, жоспарлау әдістеріне, шаруашылық басқаруға деген жоғарғы талап қоюумен. Бұл жағдайларда басшыларға қоғамның экономикалық өміріне ғылыми тәсілдер қолдану халық шаруашылығының қарқынды дамуына ықпал етеді.
Экономиканың әріқарай дамуының қажетті шарттарының бірі және бірегейлері сандық анализдің нақты әдістерінің қолданылуы және де математиканың кеңінен қолданылуы ықпал етеді.
Қазіргі таңда математиканың ең жоғарғы жетістіктерімен, заманауи есептік техниканың жетістіктері, экономикалық зерттеулермен жоспарлауларда кеңінен қолданылуда. Бұл мақсатта қолданылып жұрген математикалық жетістіктер: математикалық программалау, ойын теориясы, жалпыға қызмет ету теориясы секілді көптеген математикалық әдістер. Қазіргі таңда көптеген экономикалық есептер және экономикалық шешімдерді математикалық әдістерді қолдануда. Айтарлықтай табысқа жеткен әдістерінің бірі оптималды жоспарлау. Ал ол өз кезегінде математикалық программалаудың негізі болуда. Болашақ бағдарламашылар үшін қолданылған математиканың ең маңызды саласының бірі - математикалық бағдарламалау; Ол экстремальді есептерді зерттеуге және оларды шешу әдістеріне арналған. Бұл пәнді оқу студентке қарапайым экономикалық есептердің математикалық модельдерін құрастыруда алғашқы қадам жасауға, математикалық қойылыммен шешу әдістерін үйренуге мүмкіншілік береді.
Экстремальды экономикалық есеп шешімдерін үш кезеңге бөлуге болады:
1. Экономикалық математиканың моделін құру.
2. Оптималды шешімдердің біреуін математикалық әдіспен табу.
3. Практикалық көзқарас және халық шаруашылық.
Экономиканың математикалық моделін құру үшін алдымен экономикалық процестің математикалық моделін солай құру керек, онда оның шынайылығы көрініп тұратындай болуы керек.
Математикалық программалаудың құрамдас бөліктері үшке бөлінеді. Олар: Сызықтық, сызықтық емес және динамикалық программалау.
Алғашқы рет сызықтық программалаудың есебін совет экономисті А.Н.Толстой 1930 жылы қойды. Ал 1931 жылы венгерлік математик Б.Эгервари сызықтық программалаудың математикалық түрде қойылуын қарастырып, оған таңдау кедергісі деп аталып, венгерлік шешім деген атқа ие болды. Жүйелі түрде зерттеулер нәтижесінде сызықтық программалаудың есебін, жалпы әдісін және шешімін табуды совет ғалымы Л.В.Канторовичтің (1932) жұмыстарында берілген жалпы шешімдерін табу әдісін ұсынды. Ол М.К.Гавуринмен бірлесе отырып потенциал әдісін ойлап табуды және оны транпорттық есептерді шешуде қолданды.
Сызықтық программалаудың әдістерін жақын шет елдегі ғалымдар да зерттеді. Дәлірек айтар болсақ, американдық ғалым 1941 жылы Хичкок транспорттық есепті қойды. Сызықтық программалауды шешудің негізгі әдісі ретінде - симплекс әдісі болып жарияланды. Ол 1949 жылы Данциг жариялады. Одан әрі қарай да көптеген ғалымдар өз еңбектерін сызықтық және сызықтық емес программалау әдістерін дамытты.
1 СЫЗЫҚТЫҚ ПРОГРАММАЛАУДЫҢ НЕГІЗГІ ЕСЕБІ
1.1 ЖӘЙ ЭКОНОМИКАЛЫҚ ЕСЕПТЕР
Шикізатты қолдану есебі
Екі түрлі П1 және П2 өнімдерін дайындау үшін төрт түрлі шикізат қажет деп болжайық: S1 , S2, S3, S4. Әр шикізат қоры шектеулі, яғни b1, b2,b3,b4 шартты бірліктері. Шикізат қорлары, өнімнің әр данасы үшін жұмсалатын шикізат көлемі белгілі болсын. (1-кесте)
Кесте 1
Шикізат түрлері
Шикізат қоры
Өнім түрлері
П1
П2
S1
S2
S3
S4
b1
b2
b3
b4
a11
a21
a31
a41
a12
a22
a32
a42
Кіріс
C1
C2
мұнда aij(i=1,..,4;j=1,2) Пjтүріндегі өнімді өндіру үшін Si түріндегі шикізат көлемі кестедегі соңғы қатарда әрбір өнімнен түскен өндірістің пайдасы.
П1 және П2 өнім шығару үшін максимальды пайда түсім беретін өнім өндіру жобасын құру керек болсын. Математикалық түрде берілуін келесі сандық мысалда көреміз (2 - кесте).
Кесте 2
Шикізат түрлері
Шикізат қоры
Өнім түрлері
П1
П2
S1
S2
S3
S4
19
13
15
18
2
2
0
3
3
1
3
0
Кіріс
7
5
Айталық П1 -деп x1 , П2-деп x2 өнімдер дайындалсын. Ол үшін S1-деп 2x1 + 3x2 бірлік шикізат алу талап етілсін (2-кесте).Сонымен S1 - де барлығы 19 бірлік шикізат мөлшері болса, онда ол
2x1 + 3x2 =19
теңсіздігін орындау керек.
Теңсіздік S1 - дегі шикізат қорлары толықтай пайдаланбай өндіріс максимальды табысқа жетуі қарастырылған.
Ал қалған шикізаттың түрлері келесі теңсіздікпен берілген
Осындай шарттармен өндіріске түскен табыс
F=7x1+5x2
құрайды.
Сонымен математикалық есеп былай тұжырымдалады
(1.1.1)
жүйесі берілген, төрт сызықтық теңсіздіктен сызықтық форма
(1.1.2)
түрінде болады.
Теріс емес шешімдерден (1.1.1) теңсіздіктер жүйесінен шешімді F формасы ең үлкен мән қабылдайтындай етіп таңдауға болады.
Құрылғылардың қуаттылығын пайдалану есебі.
Өнеркәсіп өндірісте уақыт және наменклатура бойынша жоспар құрған. П1 -түрдегі N1- өнімді және П2 - дегі N2- өнімді T уақытта шығаруы керек болсын. Әрбір түрлі өнімді әртүрліқуаттылығына қарай А және В екі машинамен өндіруі мүмкін. Бұл қуаттылықтар 3- кестеде көрсетілген. Мұнда a1- А машинамен бірлік уақытта өндірілген П1 түрдегі өнім мөлшері. Ал қалғандарының да берілгендері кестеде көрсетілген.
Кесте 3 Кесте 4 Кесте 5
П1
П2
П1
П2
П1
П2
А
a1
a2
A
α1
α2
A
x1
x2
В
b1
b2
B
β1
β2
B
x3
x4
Берілген машинада өнімдердің түрлеріне қарай шығындарда әр түрлі болып табылады және 4 - кестеде көрсетілген.
Бұл кестеде α1 мен- П1 түрдегі дайындалған өнімнің А машинасындағы жұмыс уақытының бірлік бағасын өрнектейді. Ал қалған α2,β1,β2 шамаларыда өзгелерге ұқсас.
Машинаның жұмыс жасауының оптимальды жоспарын, атап айтсақ әрбір А және В машиналары П1 және П2 түрдегі өнімдерді қанша уақытта дайындағанда, өндірістегі өнімдердің құны минималь болатындай етіп құру керек.
Қойылған есептің математикалық тұжырымдамасын жасайық. Өнімдерді өндіру үшін машинаның жұмыс уақытына (5 кестеде) көрсетілгендей белгілеулер енгіземіз. Мұнда, мысалыға x1- П1 түрдегі өнімді А машинасында дайындау уақытын көрсетеді. Сондай-aқ x2,x3,x4 осындай болады.
Қаншалықты А және В машиналары бір уақытта жұмыс жасаса, уақыт бойынша жоспарды орындау келесі теңсіздіктермен қамтамасыз етеді.
x1+x2=T,
x3+x4=T.
Бұл теңсіздіктің сол жағы А және В машиналарына сәйкес жалпы жұмыс уақытын білдіреді.
x1 уақыт бірлігінде П өнімін А машинасында дайындайды. Сонымен А машинасында П1 өнімді В машинасында b1x3 бірлікте дайындайды. Сондықтан жоспарды нөмір бойынша қамтамасыз ету үшін келесі теңдік орындалуы тиіс.
a1x1+b1x3=N1.
Дәл осылай П2 өнімді шығару жоспарын қамтамасыз ету үшін келесі теңдікті қанағаттандыруы тиіс.
a2x2+b2x4=N2.
Бұдан әрі осы шарттардан барлық өнімдердің жалпы бағасы
F=a1x1+a2x2+β1x3+β2x4.
құрайды.
Қорытындысында келесі математикалық есепке келеміз.
x1+x2=T,x3+x4=T,a1x1+b1x3=N1,a2x 2+b2x4=N2. (1.1.3)
екі сызықтық теңдеумен екі сызықтық теңсіздіктерден сызықтық форма беріледі
F=α1x1+α2x2+β1x3+β2x4. (1.1.4)
(1.1.3) жүйеден барлық теріс емес шешімдердің арасынан F форма қай кезде ең
аз мәнді қабылдайтындығын табу керек.
Қойылған есептен бір ең маңызды нұсқасын белгілейміз.
А және В машиналары барлық T уақытта жоспар бойынша жүргізуін талап етеміз. Сонда
x1+x2=T,
x3+x4=T
Теңсіздігі теңдікке өтеді. Сол кезде соңғы (1.1.3) жүйедегі екі теңдік теңсіздікке өтеді.
a1x1+b1x3=N1,
a2x2+b2x4=N2.
Сонда T уақыттағы машиналар жұмыс тек қана жоспар бойынша асыра орындайды. Сондықтан минимизациялау талабы бойынша нөмір бойынша артық орындауды теріске шығара алмайды.
Транспорт есебі
A1 және A2 екі станциядан a1 және a2 сәйкес біртекті бірлік жүкті жіберу керек. Бұл жүктерді b1,b2, b3 мөлшерінде B1,B2, B3 пунктіне тасымалдау керек. Ai пунктінен Bj пунктіне жүкті тасымалдау құны Cij белгілі. Берілген мәліметтер 6-шы кестеде көрсетілген.
Кесте 6
Қабылдау
пункті
Жіберу
пункті
Тағайындау пункті
Жүк қорлары
B1
B2
B3
A1
A2
C11
C21
C12
C22
C13
C23
a1
a2
Жүкке
қажеттілік
b1
b2
b3
ai=bj
Станциялардағы жүкті тасымалдаудың жалпы қоры осы жүкті жеткізудегі сұраныстың қосындысына тең болады. Шындығында
a1+a3=b1+b2+b3. (1.1.5)
Тасымалдау бағасы ең аз болатын жоспарда құруымыз керек.
Ai пунктінен Bi пунктіне жіберілетін жүктің санын xij деп белгілейміз. Сонда жүктің саны A1 және A2 пункттерінен B1 пунктеріне жеткізу жоспарланған,
x11+x21.
деп қорылады.
Ал бірақ B1 пункттегі жүктің қажеттілігі b1-ге тең болса, онда
x11+x21=b1.
орындалады.
Дәл осындай талқылаулардан келесі теңдік бере келеміз.
x12+x22=b2,
x13+x23=b3.
Басқаша айтқанда А станциясынан жіберілген жүктің жалпы мөлшері
x11+x12+x13,
қосындысымен өрнектеледі, бұдан байқағанымыз A1 пунктінен пайдалану пункттеріне жіберілген жүктердің қосындысы
x11+x12+x13=a1.
сондай-ақ
x21+x22+x23=a2.
Алынған қатынастарды есте сақтап, барлық шамаларды кестеге енгіземіз. Сонда i-нші қатарда орналасқан барлық xij қосындысын оңай тексеруге болады. Ai пунктіндегі тасымалдау ai қорына тең. j-ші қатарларға xij қосындысы bj-ге тасымалдау Bj-тең. Есептің шарттарынан тасымалдаудың барлық F бағасы
F=c11x11+c12x12+c13x13+c21x21+c22x2 2+c23x23==i=12j=13cijxij=i,jcijxij.
тең.
Кесте 7
Белгіленген
орны
Жіберу
Орны
B1
B2
B3
Қосымша
Қорлар
7 кесте жалғасы
A1
A2
x11
x21
x12
x22
x13
x23
a1
a2
Қажеттілер
b1
b2
b3
Сонымен транспорт есебінің математикалық тұжырымдамасы мынадай
x11+x21=b1,x12+x22=b2,x13+x23=b3,x1 1+x12+x13=a1,x21+x22+x23=a2. (1.1.6)
Алты айнымалылар арқылы бес сызықтың алгебралық теңдеулерден сызықтық форма
F=i,jcijxij. (1.1.7)
(1.1.6) теңдеулер жүйесінен xij шешімінің барлық теріс емес шешімдерінін F формасы минимал, яғни ең кіші мәнге ие болатын шешімін таңдап аламыз.
Сонымен, транспорт есебін шешу барысында ең маңызды қатынасты ескерсек, осы шарттардан
iai=jbj (1.1.5')
шығады.
Алайда кей жағдайда (1.1.5') шарты орындалмайтын да есептердің қойылуы мүмкін.
Азықтандыру есебі
Адам өз өмірінде денсаулығын сақтау және жұмысқа деген құлшынысын арттыру үшін бір күнде кейбір құнарлы заттарды пайдалануы тиіс, мысалға белоктар, майлар, көмірқышқылдар, су және дәрумендер. Бұл қоспалардың қорлары әртүрлі түрдегі PIi(i=1,2,...) тағамдарда әртүрлі. Қарапайым түрде екі түрлі тағамның түрін алып 8 кестедегі түрде берейік, мысалыға a11 саны PIi түрдегі тағамдағы майлардың қорын береді, ал қалған aij сандары осы тектес алынады.
Кесте 8
Құнарлы өнімдер
Қалыпты
Тағам түрлері
PI1
PI2
B1-майлар
B2-нәруыздар
B3-көмірлер
B4-сулар
B5-дәрумендер
b1
b2
b3
b4
b5
a11
a21
a31
a41
a51
a12
a22
a32
a42
a52
Құны
с1
с2
Әрі қарай PIi түріндегі тағамдардың жалпы құны ci-ді құрайды. Адам ағзасын күндік нормасы құнарлы заттардың барлық түрін алатындай жалпы ең кіші болатын жоспарды ұһқұруымыз керек. Bi(i=1,2,...5).
x1және x2 - PI1 және PI2-дегі тағам түрлерінің мөлшері болсын. Бұл жағдайда екі түрлі тағамдағы майлардың қоры
a11x1+a12x2
және b1 минималь нормасынан аз болуы тиіс. Бұл талап
a11x1+a12x2=b1.
теңсіздігіне алып келеді.
Теңсіздектегі таңбалар тамақтану жүйесіндегі қолданылатын майлар ең кіші нормасынан көбірек болғандығын көрсетеді. Сонымен осы жағдайлардан
a21x1+a22x2=b2,
a31x1+a32x2=b3,
a41x1+a42x2=b4,
a51x1+a52x2=b5.
төрт теңсіздіктер жүйесіне келеді.
Сонымен F тамақтанудың жалпы құны
F=c1x1+c2x2.
тең. Демек біз келесі математикалық есепке орлайық.
ai1x1+ai2x2=bi (i=1, ...,5) (1.1.8)
x1,x2 айнымалы бес сызықтық теңсіздік және
F=c1x1+c2x2 (1.1.9)
сызықтық форма жүйесімен берілген.
8-жүйеден барлық теріс емес шешімдердің арасынан F- формасы ең кіші мәнге ие болатындығын табу керек.
1.2 НЕГІЗГІ ЕСЕП ЖӘНЕ НЕГІЗГІ ТҮСІНІКТЕР.
Сызықтық программалаудың негізгі есептері келесі түрде болады
a11x1+...+a1nxn=b1,a21x1+...+a2nxn= b2,. . . . . . . . . . . . . . . .am1x1+...+amnxn=bm. (1.2.1)
m- сызықтық алгебралық теңдеулер n белгісіз x1...xn айнымалылардан туратын жүйе берілген және осы белгісіздерге қатысты сызықтыө форма
F=c1x1+...+cnxn+c0 (1.2.2)
түрде жазылады.
(1.2.1) берілген жүйеден барлық теріс емес шешімдердің арасынан F сызықтық форма ең кіші мәнге ие болатын шешімді таңдау керектігін талап етеді.
Анықтама 1.1 (1.2.1)жүйені берілген есептің шектеулер жүйесі деп атаймыз.
Ескерту 1.1 Есепте x1,x2,...,xn белгісіздері тек қана теңдікті емес, сонымен қатар теңсіздікті де қанағаттандыруы тиіс.
Ескерту 1.2 Ең маңызды жайт (1.2.1)теңсіздктегі шектеулер шындыңында негізгі есептегі барлық шектеулерді қамтымайды, себебі x1,x2,...,xn айнымалылар теріс шартты қанағаттандырмауы міндетті
x1=0...xn=0
Анықтама 1.2 (1.2.1) жүйенің барлық теріс емес x1(0),...,xn0 (xi0=0;i=1,...,n) шешімдерін мүмкін шешімдер деп атаймыз.
Анықтама 1.3 (1.2.1) жүйенің F формасын минималдаушы теріс емес шешімдерін минималдаушы оптималды деп атаймыз.
Ескерту 1.3 Ережеде оптимальды шешім жалғыз болуы керек. Кей жағдайда оңтайлы шешімдер сансыз жиын болуы да мүмкін. (1.2.1) шектеулер жүйесін зерттеуге қайта оралайық. Есебімізде мынадай тұжырымдарда болуы мүмкін, егерде (1.2.1) жүйе үйлесімді болады, яғни (Кронекер-Капелла теоремасна сәйкес) негізгі матрицаның рангы сәйкес келсе. Сызықты алгебра курсынан белгілі болғандай жалпы ранг n белгісіздер санынан аспайды. Егер r=n болғанда (1.2.1)жүйенің x1(0),...,xn0 шешімдері жалғыз және ол Крамер теоремесы бойынша табылады. Егерде бұл xi0=0;i=1,...,n шешімдері мүмкін болса, онда оптимальды болатындығы айқын көрініп тұр. Егeрде xi0 сандарының ішінен бір теріс сан болса, онда есебіміздің шешімі жоқ. Шындығында оңтайлы шешім жоқ, өйткені шешімге ие болуы үшін теріс шешім бола алмайды.
Сонымен, rn болған жағдай ғана қызықтырады болса, тек сол жағдайды қарастырамыз. x1,..,xn айнымалыларымен берілген теңдеулер және теңсіздіктермен және осы айнымалыларға қатысты F сызықтық формасы берілген.
Берілген шектеулер жүйесінен барлық теріс емес шешімдері арасынан F сызықтық формасы ең кіші және ең үлкен мәнді беретін шешімдерін табу керек. Сондықтан 1-4 есептердің мәліметінде сызықтық программалаудың негізгі есептеріне келтіру үшін біріншіден формаларды: максималдау және минималдау туралы мәселені енгізу, екіншіден теңсіздік түрде берілген шектеулерден оларда кейбір эквивалентті теңдіктерде көшуді үйрену керек.
Оны қалай жасау керектігін көрсетейік.
1) x1,..,xn белгісіздердің мәндерінде F формасы ең үлкен шамаға тең болуы, сондай-ақ осы белгісіз шамаларда F1=-F ең кіші мәнге де тең болуы айқын. Шындығында да F формасының максималдылығы F1=-F формасының минималдау шартына тепе-тең. Сонымен максималдау есебі минималдау есебіне келтіріледі.
Ескерту 1.4 F формасының ең үлкен мәні F1 формасының қарама-қарсы таңбамен алынған ең кіші мәніне тең екені белгілі.
2) Есептің шектеулері арасынан кейбір теңсіздіктері бар болсын. Оны әр уақытта
α1x1+α2x2+...+αnxn+β=0 (1.2.3)
түрінде жазамыз.
Қосалқы деп аталатын теңдеулерге x1,..,xn белгісіздерімен байланысты жаңа белгісіздер енгіземіз.
xn+1=α1x1+...+αnxn+β (1.2.4)
xn+1 шамасының теріс емес шарты (1.2.3) теңсіздіктің орындалуына эквивалентті. Басқа сөзбен айтқанда егерде x1(0)...xn(0),xn+1(0) жүйесінің теріс емес x1,..,xn,xn+1 белгісіздері (1.2.4) теңдеуді қанағаттандыратын болса, онда x1(0)...xn(0) жүйесі де (1.2.3) теңсіздікті қанағаттандырады. Ал, екрісінше, егерде x1(0)...xn(0) шамалары теріс болып, (1.2.3) теңсіздікті қанағаттандырса, онда
xn+1(0)=α1x1(0)+...+αnxn(0)+β
(1.2.4) теңдеуден табылған шамалары теріс болып табылады.
Демек (1.2.3) теңсіздік (1.2.4) теңсіздікпен эквивалентті. Сонымен қосымша айнымалылар енгізу арқылы теңсіздіктерді теңдеулерге айналдыруға болады. Сондықтан берілген есепте қосымша белгісіздер теңсіздіктегі шектеулер санына тең.
Есеп 1 (1.1.1) жүйедегінің барлық мүшесінің шектеулерін оң жағына көшіретін болсақ, онда ол келесі түрде болады.
0=19-2x1-3x20=13-2x1-x20=15-3x20 =18-3x1 (1.2.5)
2) Ережесі бойынша қосымша x3,x4, x5,x6, белгісіздер енгізіп, келесі жаңа теңдеулер жүйесіне көшеміз.
x3=19-2x1-3x2x4=13-2x1-x2x5=15-3x2x 6=18-3x1 (1.2.6)
1) Ережеге қатысты F=7x1-5x2 максималдау формасының орнына F1=-F=-7x1-5x2 минималдау формасын аламыз.
Есеп 2. Шектеулерменберілген (1.1.3)
0=T-x1-x2,0=T-x3-x4,a1x1+b1x3=N1, a2x2+b2x4=N2, (1.2.7)
қосымша x5,x6 белгісіздерін енгізіп теңсіздіктен теңдеулер жүйесіне көшеміз.
x5=T-x1-x2,x6=T-x3-x4,a1x1+b1x3=N1, a2x2+b2x4=N2, (1.2.8)
(1.1.9) жүйенің теріс емес шешімдерінің арасынан F= α1x1+α2x2+β1x3+β2x4 формасы үшін (оптимальды) оңтайлы шешімді таңдап алуға болатындығы шығады.
Есеп 3. Транспорт есебінің негізгі түрі бар.
Есеп 4. (1.1.8) теңсіздіктер жүйесін
a11x1+a12x2-b1=x3,a21x1+a22x2-b2=x4 ,a31x1+a32x2-b3=x5,a41x1+a42x2-b4=x 6,a51x1+a52x2-b5=x7 (1.2.9)
теңдеулер жүйесімен алмастырамыз. Минимальданатын F=c1x1+c2x2 формасы өзгеріссіз қалады.
5-ші есептегі мәліметтерді негізгі әдістермен көрсетейік. 5-ші есептердегі математикалық шартын еске түсірейік.
Жүйенің теріс емес шешімдерінің арасынан
x11+x21=50,x12+x22=30,x13+x23=45, (1.1.10)
екі сызықтық формасы бірдей максимумдары
t1=4x11+10x12+10x13,t2=6x21+8x22+20 x23, (1.1.11)
минималь болатын Т шамасын табу керек.
Берілген есептердегі мәліметтер үшін (1.1.10) шектеулер қатарынан негізгі есепті және екі теңсіздіктерді қарастырамыз.
y=t1,y=t2 (1.2.10)
және сызықтық форма F=y.
Енді (1.1.10) және (1.2.10) шектеулердің сызықтық форманы минимизациялайтын шешімін іздейік және бұл қандай нәтіжеге келтіндігін көрейік.
Біріншіден xij теріс емес шешімдерден t1 және t2 теріс еместігі туындайды сондықтан y- те теріс емес болады.
Екіншіден F=y формасына тең болса, онда F-ті минимизациялайтын болсақ ол y-ті минимизациялау дегенді білдіреді. Бірақ y-тің ең кіші мәні (1.2.10) теңдікті қанағаттандыратын болса автоматты түрде t1және t2 мәндерінің ең үлкен мәндері теңеседі, басқаша айтқанда ymin=max( t1, t2) (1-сурет).
Cурет 1
Басқа сөзбен айтатын болсақ F формасының ең кіші мәні әрқашанда max( t1, t2) тең. Сонымен (1.1.10) және (1.2.10) шектеулер жүесінің табылған шешімдерінен F=y формасының ең кіші мәнін беретін болса, онда (1.1.10) жүйесінің мұндай шешімдерінен Т=max( t1, t2). Шамасы ең кіші мүмкін мәндері болып табылады.
Демек 5-ші есеп (1.1.10) және (1.2.10) шектеулермен берілген F=y формасының минимизациясына эквивалентті.
(1.2.10) теңсіздіктер жүйесі көрсетілген 2 әдіс бойынша теңдеулер жүйесіне келтіріледі. 5-ші есептің соңғы қадамының нәтіжесінде шектеулер жүйесі негізі түрге келеді.
x11+x21=50,x12+x22=30,x13+x23=45,y- 4x11-10x12-10x13=z1y-6x21-8x22-20x2 3=z2
бұл жерде z1 және z2- қосымша айнымалылар және минимизацияланатын форма.
Бұл есепте y шамасы айқын экономикалық мағынаны береді. (1.2.10) теңсіздікті қанағаттандыратын y-тің кез-келген мәнін xij шамасымен берілген жоспарды уақыт ретінде түсіндіруге болады. Сондықтан ymin үшін берілген жоспарды xij -ң ең аз уақыт ішінде жүзеге асыруға қажетті болады.
Сызықтық бағдарламалау есептерінен 1.1 келтірілгендей бұл есептегі шектеулер әртүрлі беріледі: олардың арасында теңдік ретінде де кездеседі, сондай-ақ теңсіздік түрінде де кездеседі. Бір қарағанда мұндағы негізгі есептегі шектеулер біртексіздікті көрсетеді. Бірақ бұлай болуы мүмкін емес, (1.2.1) шектеулер теңдігіне басқалары x1,...,xn шамасымен байланысқандары шектеулер теңсіздіктерінде орындалады. Бұл эквивалентті есептердегі барлық шектеулер тек қана теңсіздіктен тұрады.
Шектеулері теңсіздіктермен берілген сызықтық программалаудың негізгі есебі
Шектеулер берілген (1.2.1) жүйені қарастырамыз. 2.1 аталғандай rn жағдайын қарастырайық(r-жүйенің рангы, n-белгісіздер саны). Сызықтық алгебрадан белгілі болғандай бұл жағдайда r-белгісіздер n-r=k қалған белгісіздері арқылы сызықты өрнектеледі(бұл соңғы қабылдағандарды бос мүше деп атаймыз). Әрқашанда белгісіздерді нөмірлеуге болады, соңғы xk+1,...,xn белгісіздерін x1,x2,...,xk алғашқы белгісіздері арқылы өрнектеледі(n=k+r болса, онда xk+1,...,xn белгісіздері r қанша болса сонша дәлдікпен алынады).
xk+1=α11x1+α12x2+...+α1kxk+β1,xk+2= α21x1+α22x2+...+α2kxk+β2,. . . . . . . . . . . . . . . . . . . . . . . . . . .xn=αr1x1+αr2x2+...+αrkxk+βr. (1.2.12)
(1.2.12) жүйе (1.2.1) жүйеге эквивалентті.
(1.2.2) өрнектегі xk+1,...,xn шамаларының орнына (1.2.12)-гі мәндері F формасына қойсақ, онда F форма басқа түрге келеді.
F=γ0+γ1x1+...+γkxk (1.2.13)
яғни бұрынғы сызықтық түрде қалады, бірақ тек қана x1,...,xn бос белгісіздері арқылы өрнектеледі.
Негізгі есепті шеше отырып, (1.2.1) жүйенің теріс емес шешімдерін шектейміз. Сондықтан теңсіздік қажеттілікпен орындалуы тиіс.
xi=0 i=1,2,...,n. (1.2.14)
Егер (1.2.12) теңдікті ескерсек, онда i=R+1, R+2,...,n үшін
0=α11x1+...+β1,0=α21x1+...+β2,. . . . . . . . . . . . . .0=αr1x1+...+βr
теңсіздігін аламыз.
xi бос белгісіздер үшін (i=1,...,k) (1.2.14) теңсіздікті қайта жазамыз. Келесі жүйе
x1=0,. . . . .xk=0,α11x1+...+α1kxk+β1=0,. . . . . . . . . . . . . . . . . . .αr1x1+...+αrkxk+βr=0. (1.2.15)
R белгісіздеріне қатысты n сызықтық теңсіздігі бар жүйеге көшеміз. (1.2.12) жүйенің мүмкін шешімдері (1.2.15) теңсіздіктің шешімдері бола алатындығы айқын. Ал керісінше қалауымызша x10,...,xk0 (1.2.15) жүйенің шешімдерін алсақ, және (1.2.12) формула бойынша табатын болсақ,
xk+i0=αi1x1(0)+...+αikxk0+βi i=1,...,n,
шамаларын аламыз, демек (1.2.12) және (1.2.1) жүйенің шешімдері теріс еместігі айқын. Сонымен қатар (12) теңдеулер жүйесінен теріс емес шешімдерді іздеу үшін (1.2.15) теңсіздіктер жүйесінің барлық шешімдерін іздейміз.
Нәтижесінде келесі математикалық есепке келеміз. (1.2.15) x1,...,xk - ке қатысты k белгісізді n сызықтық теңсіздіктер жүйесі және
F=γ0+γ1x1+...+γkxk (1.2.13)
сызықтық формасы берілсін.
(1.2.15) жүйемен F формасы ең кіші мәнге ие блатындай шешімді табу керек.
(1.2.15) жүйенің шешімдерінен F формасының ең кіші мәнеге ие болуын оңтайлы шешім деп атаймыз.
Аталған есептерді шешу барысында сызықтық программалаудың негізгі есептері қойылған есепке эквивалентті. Мұндай есептерді шектеулі теңсіздіктермен берілген сызықтық программалаудың негізгі есебі деп аталады қысқаша түрде (А) түрдегі есеп деп атаймыз.
Есеп 1 2-ші тараудағы мәліметтерге сүйеніп келесі жүйедегі шектеулерге келеміз.
x3=19-2x1-3x2,x4=13-2x1-x2,x5=15-3x 2,x6=18-3x1 (1.2.6)
және F1=-7x1-5x2. (1.2.6) - жүйеден I матрицасын жазамыз.
I=2 3 1 0 0 02 1 0 1 0 00 3 0 0 1 03 0 0 0 0 1.
Бұл есепте ранг тең, сонымен ал
Жалпы схемаға сәйкес төрт белгісізді қалған екеуі арқылы өрнектеледі (1.2.6) жүйеден байқағанымыздай соңғы белгісіздер алғышқы арқылы өрнектелген. Барлық теріс емес белгісіздерді қолданып келесі теңсіздіктер жүйесіне келеміз.
x1=0,x2=0, 19-2x1-3x2=0,13-2x1-x2=0,15-3x2= 0,18-3x1=0. (1.2.16)
Сонымен 1-ші есеп (А) түрдегі математикалық есепке келеді.
Есеп 2 Бұл есепке (A) формасын берейік. Шектеулер жүйесі және сызықтық форма мына түрде беріледі:
x1+x2=T,x3+x4=T,a1x1+b1x3=N1,a2x2 +b2x4=N2, (1.1.3)
F=α1x1+α2x2+β1x3+β2x4. (1.1.4)
(1.1.3) және (1.1.4) шамаларға мәндер беріп есепті нақтылаймыз. a1=6, a2=24, b1=13, b2=13, N1=30, N2=96, T=6, α1=4, α2=47, β1=13, β2=26.
Сонда шектеулер жүйесі мен F формасы
x1+x2=6,x3+x4=6,6x1+13x3=96,24x2+ 13x4=96, (1.2.17)
F=4x1+47x2+13x3+26x4.
түрге келеді.
Алғашқы екі теңсіздіктерді өзінде қалдыра отырып, x3 және x4 теңсіздіктерді x1 және x2 арқылы өрнектейміз.
x3=11330-6x1,x4=11396-24x2. (1.2.18)
Әрі қарай, берілген теңсіздіктің сол жағына және F формасын бос белгісіздермен өрнектеп, нәтижесінде
x3+x4=11330-6x1+11396-24x2=6,
F=4x1+47x2+30-6x1+2(96-24x2)
аламыз немесе қарапайым алгебралық түрлендіруден соң
x1+4x2=8,
F=222-2x1-x2.
аламыз.
x3 және x4 теріс емес шешімдері теңсіздікке эквивалентті
11330-6x1=0,
11396-24x2=0,
соңғы элементар түрлендірулерден соң
x1=5, x2=4.
x1+x2=6 және барлық теріс емес шешімдерін ескере отырып, келесі шектеулерді аламыз:
x1=0,x2=0,x1=5,x2=4,x1+x2=6,x1 +4x2=8. (1.2.19)
Сонымен минималданатын форма келесі түрде болады:
F=222-2x1-x2. (1.2.20)
1.3 ЕСЕПТІҢ ГЕОМЕТРИЯЛЫҚ МАҒЫНАСЫ
Алдыңғы параграфта сызықтық программалау есебі жайлы айтылған. Онда түрлі типте берілген есептерді негізгі есепке келтіру түрлері кқрсетілген. Негізгі есепті шешу үшін әртүрлі әдістер ойлап табылды. Бұл әдістер аналитикалық сипатқа әкеледі. Бұл әдістердің кейбірін кейінрек қарастырамыз.
Бұл параграфта біз негізгі есептердің геометриялық түсіндірмесін қарастырамыз. Бұл түсіндірмелерде аналитикалық әдістің маңыздылығын терең әрі оңай түсінуге көмек беріп, көрінісі анық болады.
Сызықтық программалаудың негізгі есебінің геометриялық берілуі анық болады, егерде бұл түрден шектеулері теңсіздіктермен ьерілген эквивалентті есептерге көшетін болсақ онда мына түрдегі есептің қойылуын еске түсірейік құрамында n=k+r k белгісіздеріне қатысты x1,...,xk сызықтық теңсіздік пен
F=γ0+γ1x1+...+γkxk (1.2.13)
сызық формасы бар мына
x1=0,x2=0,. . . .xk=0,a11x1+...+a1kxk+β1=0,. . . . . . . . . . . . . . . . . . .ar1x1+...+arkxk+βr=0, (1.2.15)
жүйе берілсін.
(1.2.15)жүйенің шешімдерінің арасынан F формасы ең кіші мәнге ие болатын шешімді табу керек.
Есеп 3 F1 формасы мен шектеулер бұл есепте (А) типтегі есептер сияқты қойылған және мына түрде болады.
x1=0,x2=0,19-2x1-3x2=0,13-2x1-x2 =0,15-3x2=0,18-3x1=0, (1.2.16)
F1=-7x1-5x2.
Жазықтықтағы тікбұрышты декарттық жүйесіне x1Ox2 координаталарын енгіземіз. Жазықтықтағы нүктелердің геометриялық орны белгілі болса, сызықтық теңсіздіктер жүйесін қанағаттандыратын координаталар дөңес көпбұрышты құрайды. Бұл көпбұрыштарды берілген теңсіздіктер жүйесінің шешімдерінің көпбұрышы деп атайды. Егерде теңсіздіктер жүйесіндегі теңсіздік таңбасын тура теңдікке ауыстырып, алынған теңдеудегі көпбұрыштың қабырғалары түзуде орналасады. Бұл жүйенің әрбір теңсіздігі жарты жазықтықты, шекаралық түзулерді құрайды. Біздің жағдайымызда мұндай түзулер мына түрде болады.
x1=0, Ix2=0, (II)19-2x1-3x2=0, III13-2x1-x2=0, IV15-3x2=0, V18-3x1=0, (VI)
(2)-суреттегі түзулерді сызайық, мұндағы стрелкалар жарты жазықтықтардың қиылысуы көпбұрыштық шешімдерін береді.
Сурет 2
Сонымен бірге F1=-7x1-5x2 формасын қарасытрайық. Бұл жазықтықтағы (x1,x2) нүктелер сызықтық функцияның (x1,x2) координаталары болатындығын көрсетеді. Бұл мәселеге жазықтықта осы F формасы бір және сол С мәнді қабылдау үшін нүктелер қалай орналасады деген сауал қояйық.
Қойылған сұраққа жеткілікті түрде F1 формасы С мәнді қабылдайды және
-7x1-5x2=C (1.3.1)
теңдеуін алады.
Бұл теңдеулер жазықтықта түзулерді береді. Бұл түзулер F1 формасы берілген С мәнді қабылдағандағы нүктелердің геометриялық орнын береді. C-ң мәнін өзгертсек, әртүрлі түзулерді аламыз, бірақ олар өзара параллель түзулер, яғни параллель түзулердің шоғырын құрайды. Жазықтықтағы әрбір нүкте арқылы бір түзу өтеді. Осы түзулер (1.3.1) шоғырындағы әрбір түзуден F1 формасының сызықтық деңгейі деп аталатын деңгейді қабылдауға болады. Бір түзуден келесі түрге көшкенде F1 формасының мәні өзгереді. 3 - суретте
Cурет 3
C=-17,5;-35;-52,5 мәндерімен берілген түзулер көрсетілген y-векторы форманың үлкен мәнінен кіші мәніне көшкендегі қозғалыс бағытын көрсетеді.
Аналитикалық курсынан белгілі болғандай түзудің теңдеуіндегі айнымалы коэффиценттер n векторының проекциясы түзуге перпендикуляр болады. Біздің жағдайымызда n=-7;-5. Біздің байқағанымыз F1 формасының кему бағыты, n векторының бағытына қарама-қарсы.
2-суретке қайта оралайық. Көпбұрыштар шешімінен P0(x10,x2(0)) кез-келген нүктесін қарастырайық. Бұл нүктелер (1.3.1) түзулер шоғырынан өтеді. Бұл түзулердің бойынан F1 формасы мынадай мәнді P0 нүктесі сияқты,яғни C0(-7x10,-5x2(0)) мәнді қабылдайды.
2-суретте пунтирленген түзулер C=-35 мәнін көрсетеді. P0 нүктесі есептің оңтайлы шешіміне сәйкес келмейді. Сондықтан көпбұрыш шешімдерінің ішінен фoрма мәніне сәйкес келетін C0-ден кіші болатын нүктені табуға болады. Барлық көпбұрыштың шешімдері болатын түзулер қиылысады, ол үшін y векторының бағытымен C0 түзуден басқа түзуге () түзулер шоғырына параллель болатын түзулерге көшу жеткілікті болады.
Енді шешім анық болу үшін оңтайлы шешім Q5;-3 нүктесінде анықталып, ол F1 формасының ең кіші мәні F1min=-7∙5-5∙3=-50 тең емес 1-есептің оңтайлы шешімі x1=5, x2=3 табылды.
Егерде (1) беттегі есептің шартын еске түсіретін болсақ, онда шикізат қолданудың рационды жоспары үшін кепілдік беретін өнеркәсіптердің түсім үлкен, 5 бірлік П1 түрдегі өнімді және түрдегі өнімді және 3 бірлік П2 түрдегі өнім шығару керек және онда түсетін ең үлкен түсім Fmax=50 құрайды.
Сонымен S1 және S2 түрдегі шикізат толықтай пайдаланылады, S2 және S4- жартылай қолданылады(бұдан табылған шешімдер бойынша x1=5, x2=3).
Ескерту 1.4 Бұл 1-есептегі геометриялық түсіндірмесі тек қана есептің қойылуына емес, сонымен қатар есептің есептің шешімін табуға көмектеседі.
Ескерту 1.5 Математикалық талдау курсынан функциялардың экстремаль нүктелерін табу белгілі. Онда бұл есептерді дифференциалдық есептеулермен шығарылады. Неліктен бұл әдістерді сызықтық программалау есептерін шешуде қолдануға болмайды. Демек, дифференциалдық есептеу әдістері шекарадағы емес, қатаң облыстағы эксремаль нүктелерді анықтайды. Сызықтық программалау есептерінде форманың оңтайлы әруақытта көпбұрышты шешімдерінің шекараларында болады. Мысалыға 1-есепте. Сондықтан дифференциалдық есептеу әдістерін мұндай есептерді шешуге қолдануға болмайды.
Есеп 4 Геометриялық түсіндірмесін бере отырып, 2-есептің шешімдерін аламыз. (A) түрдегі есепке келтіре отырып (20 бет) біз келесі шектеулерді аламыз.
x1=0, Ix2=0, IIx1=5, IIIx2=4, IVx1+x2=6, Vx1+4x2=8, (VI) (1.2.19)
F=222-2x1-x2. (1.2.20)
Жазықтықтағы координат жүйесіне x1Ox2 енгізе отырып 1-ші есепке ұқсас (1.2.19) жүйенің көпбұрыштар шешімін сызамыз. Ол үшін (1.2.19) жүйедегі теңсіздіктерді теңдікке алмастырып, сәйкесті түзулерді сызамыз(сурет 4 ). Бұл суретте (1.2.20) форманың F=219 мәніне сәйкес сызықтың деңгейінің біреуі сызылған. g векторы F форманың кему бағытын көрсетеді.
Сурет 4
Сызбадан көрінгендей F формасы ең кіші мәнге көпбұрыштар шешімдерінің М (5,1) нүктесінде (III) және (V) түзулердің қиылысуында болады. x1=5,x2=1 болғанда (1.2.20) теңдеуден сызықтық форманың ең кіші мәні
Fmin=222-2∙5-1=211
тең болады.
Алынған шешімдерден қандай экономикалық тұжырымды байқауға болады. xi(i=1, 2, 3, 4) шамалары А және В машиналарының П1және П2 түріндегі өнімдердің дайындауға кеткен уақыт екендігін еске түсірейік. x1=5, және x2=1 шамалар белгілі, ал енді x3,x4 шамаларын (1.2.18) теңдеулерден табамыз
x3 =11330-6x1=11330-30=0,
x4 =11396-24x2=11396-24=7213.
cонымен есеп толығымен шығарылды.
Есеп 5 Геометриялық түсіндірмелер арқылы 3-ші есепті шешейік. Шектеулермен минимизацияланатын форма (А түрге келтірілгеннен соң ) мына түрде болады.
20-x11-x12=0, I10-x11=0, II30-x12=0, III-10+x11+x12=0, IVx11=0, V x12=0, (VI) (1.3.1)
F=330-2x11-x12. (1.3.2)
Жазықтықтағы координаталар жүйесіне енгізейік. Бұл жолы x11, және x12 деп осьтерді белгілейік. F формасын бір сызықтық деңгеймен көпбұрыш шешімдерін сызайық (5-сурет).
Сурет 5
N(10;10) нүктесінде оптималь шешімді береді, демек x11=10, x12=10, Fmin=300 қалған xij мәндері (1.2.20) теңдеулері табылады.
x13=20-x11-x12=0,
x21=10-x11=0,
x22=30-x12=20,
x23=-10+x11+x12=10.
2 СИМПЛЕКС ӘДІСІ
2.1 ӘДІСТІҢ ИДЕЯСЫ ЖӘНЕ АЛГЕБРАСЫ
1°. Сызықтық программалаудың негізгі есебін қарастырайық.
a11x1+...+a1nxn=b1,a21x1+...+a2nxn= b2,. . . . . . . . . . . . . . ..am1x1+...+amnxn=bm. (2.1.1)
m сызықтық теңдеулері n белгісізді x1,...,xn және осы белгісіздерге қатысты
F=c1x1+...+cnxn (2.1.2)
сызықтық форма берілген.
(2.1.1) теңдеулер жүйесінен теріс емес шешімдерінен F формасы ең кіші мәнге ие болатын шешімді табамыз. 1-тараудың 1.2 көрсетілгендей негізгі есептер (A) шектеулер теңсіздіктер болатын есепке егер бос белгісіздер k=n-r санына тең болып (мұнда n- барлық белгісіздер саны, ал r- (5.12)жүйенің рангі) эквивалентті түрге келеді. 1 тарудағы 1.3 көрсетілгендей k=2 болғанда негізгі есеп геометриялық әдістермен шешіледі. k2 болғанда негізгі есепті геометриялық әдістермен шешу мүмкін емес. Сондықтан мұндай есептерді аналитиалық әдістермен шешу қажет екендігін түсіндірейік. Осындай ұқсас әдістерді қазіргі уақытта симплекс- әдісі деп атаймыз. Бұл әдістің идеясын қарапайым мысалдармен түсіндірейік.
2° (2.1.1) жүйе мынадай шектеулермен және сызықтық формамен берілсін
x2+2x4+3x5-7=0,x3-x4-3x5-2=0,x1+x4+ x5-2=0, (2.1.3)
ал форма
F=3-x4+x3. (2.1.4)
(2.1.3) жүйенің үйлесімді екендігін оңай көз жеткізуге болады. Оның рангі r=3 , ал бос белгісіздер R=5-3=2. Бұл есепті геометриялық түрге шешуге болады. Алайда біз бұл әдіспен емес басқа әдістермен есепті шешіп көрейік. Бос белгісіздер ретінде x4және x5- ті, ал белгісіздер x1,x2,x3 арқылы алып, F формасы сол белгісіздер арқылы өрнектейміз.
x1=2-x4-x5, x2=7-2x4-3x5,x3=2+x4+3x5. (2.1.5)
(2.1.4) теңдеуден көрінгендей F формасы бос белгісіздер арқылы өрнектелген. Сонымен xi барлық шамалары қаншалықты теріс болса, онда бос белгісіздердің мәнім ен бос емес (базисты) белгісіздердің ең кіші мәні нөлге тең: x4=0, x5=0. Осындай бос белгісіздердің мәні тең. x1=2, x2=7, x3=2. Сонымен көріп тұрғанымыздай бұл мәндер оң, мәндер жүйесі
x2=2, x2=7, x3=2, x4=0,x5=0 (2.1.6)
болғанда (2.1.3) жүйеден мумкін шешімдерді құрайды. Сонымен табылған шешімдерден F форма F=3 мәнге тең болады.
Бос белгісіздер x4 және x5-ті нөлге тең деп алсақ бірақ бұл таңдауымыз ешнәрсені нақтылай алмайды. x4 және x5 мәндерін жоғарлату арқылы F формасының кіші мәнге тең болуына болады ма соны көрейік. F формасы үшін (2.1.4) өрнектен x5 белгісізі (2.1.4) -ге оң таңбамен кіретін болса, онда мәндерді үлкейту,форманы да жоғарлатуға әкеледі. Бұл бізге қолайсыз. Бұл уақытта x4 белгісізі (2.1.4) - ге теріс таңбалы кіреді. Сондықтан x4-ң мәні ұлғайған сайын, F формасы аз мән қабылдауда жалғастырады. Тек бір ғана нәрсені түсіну керек, x4 бос белгісіздерді ұлғайту базисті белгісіздерге өзгерістер жасайды. Бұл өзгерістер базисті белгісіздер теріс болуы мүмкін, яғни мүмкін емес шешімдерге келеміз. Ал мүмкін емес шешімдер қарастырылмаған. Шындығында (2.1.5)-ң бірінші тіңдеуінен x42 болса, онда x1 белгісіз теріс болады. Ал осы уақытта 2.1.4 және 2.1.5 теңдеулерден x4 ұлғайтқан сайын x4=2, x3 белгісізі ұлғаяды, ал x3 белгісізі кемиді бірақ оң болып қалады. Сонымен x4=2 мәні қолайлырақ болады. Өйткені
x1=0, x2=3, x3=4, x4=2, x5=0. (2.1.7)
Демек біз жаңа мүмкін шешімдерге оралдық. Алдыңғылардан байқағанамыздай (2.1.7) жаңа шешімдерінен F формасының мәні (2.1.6) шешімдерінен аз. Бұл шешімдерді салыстырайық. Олардың ішінде әрбір екі белгісіздері нөлге тең болады. (2.1.7) - ң шешімдерінен x1 және x5 нөлдік мәнге ие, ал (2.1.6)-ң нөлдік мәндері x4 және x5 бос белгісіздерінен таңдалған. Сондықтан бос белгісіздер ретінде x4 және x5 белгісіздерді емес, x1 және x5- терді алса F формасы шынайырақ көрінер еді, атап айтқанда бұл белгісіздер жаңа шешімдерде нөлдік мәнге ие. Осындай мақсатпен (2.1.5) жүйенің бірінші теңдеуінен x4 - ті x1 және x5 арқылы өрнектейміз
x4=2-x1-x5.
аламыз.
Алынған шешімдерді (2.1.5) жүйенің екінші және үшінші теңдеулеріне қойсақ F формасы үшін.
x2=3+2x1-x5, x3=4-x1+2x5,x4=2-x1-x5, (2.1.8)
F=1+x1+2x5. (2.1.9)
табамыз.
Енді (2.1.9) форма және (2.1.8) жүйелер үшін аналогиялық талқылау жасайық. Барлық x1,x5 белгісіздерін өсірген сайын F формасының ұлғайуына әкеледі. Сондықтан x1 және x5 - тер нөлге тең болғанда F формасы F=1 ең кіші мәнге жетеді. Осы x1=0, x5=0 мәндерін (2.1.8) қойып (2.1.7) шешімдеріне келеміз. Сонымен (2.1.5) мүмкін шешімдері ізделінді оңтайлы шешім болады.
3°. Жалпы жағдайға қайта оралайық (2.1.1) шектеулер жүйесінде қандайда бір k елгісізі бос мүше ретінде алынсын. Оларға кез келген мән беруге болады, ал қалған белгісіздер теңдеулер жүйесінен табылады.
Анықтама.1 (2.1.1) шектеулер жүйесінің шешімі бос белгісіздердің мәндері нөлдік мәнмен сәйкес болса, оларды базисты деп атаймыз.
Әрбір таңдалған еркін айнымалылардың базисті шешімдері бар екендігін байқадық. Бұдан әрі бізді осы мүмкін базисті шешімдерді табуды қарастырамыз.
Алынған мысалды қарастыра отырып, (2.1.6) және (2.1.7) шешімдер (2.1.5)жүйені мүмкін базисті шешімдері болып табылады. Олардың біріншісі x4 және x5 айнымалылары еркін айнымалы ретінде, ал екіншісі x1және x5 еркін айнымалылары ретінде алынады.
4 °. 1 ші есептің шешімдерін аналитикалық әдіспен шешуді қарастырайық.
Шектеулер жүйесін және сызықтық формасын жазайық.
x3=19-2x1-3x2,x4=13-2x1-x2,x5=15-3x 2,x6=18-3x1 (2.1.10)
F1=-7x1-5x2
Егерде x1 және x2 еркін айнымалы ретінде алсақ онда сызықтық форма F1 базисті белгісіздері арқылы өрнектелген. Базисті шешімдерін алайық
x1=0, x2=0, x3=19, x4=13, x5=15, x6=18. (2.1.11)
(2.1.11) өрнектегі екі бос белгісіздердің коэффиценттері теріс таңбалы. Сондықтан олардың кез келгенінің көбеюі. F формасының азаюына әкеледі. Мысал ретінде x2- шектеуден бастайық. Мысалы x2 мәнін көбейтейік. x2 айнымалысы x2=5 болғанға дейін өседі. x5 базисті айнымалы нөлге айналып, қалған базисті айнымалылар оң таңба қалпында қалады. Жаңадан x1 және x5 еркін айнымалылар жұбын енгізейік. x2, x3, x4, x6 жаңа базисты айнымалыларды және F форманы x1, x5-арқылы өрнектеп
x2=5-13x5,x3=4-2x1+x5,x4=8-2x1+13x5 ,x6=18-3x1, (2.1.12)
F=-25-7x1+53x5. (2.1.13)
аламыз.
Еркін айнымалыларды таңдауда үйлесімді базисті шешімдері есептің
x1=0, x2=5, x3=4, x4=8, x5=0, x6=18. (2.1.14)
шешімдер болып табылады.
Сонымен, F1=-25. (2.1.13) өрнекке x1 айнымалысы теріс коэффицентпен кіреді, сондықтан оның өсуі F формасының кемуіне алып келеді. x1 мәнін x1=2 мәніне дейін өсіреміз. Сондықтан x3 нөлге айналады, ал қалған базисті айнымалылар оң мәнді сақтайды. Енді x3 және x5 бос белгісіздерін алайық. Олар арқылы F1 формасын және базисты айнымалыларды өрнектейік.
x1=2-12x3+12x5,x2=5-13x5,x4=4+x3-23 x5,x6=12+32x3-32x5,
F1=-39+72x3-116x5.
табамыз.
Сәйкесті үйлесімді базисті шешімдері мыналар:
x1=2, x2=5, x3=0, x4=4, x5=0, x6=12. (2.1.15)
cонымен F1=-39.
Аналитикалық қорытындылар жасай отырып, x3 және x4 бос белгісіздер ретінде қабылдап,
x1=5+14x3-34x4,x2=3-12x3+12x4,x5=6+ 32x3-32x4,x6=3-34x3+94x4,
F1=-50+34x3+114x4.
аламыз.
Осындай бос белгісіздерді таңдауда мүмкін базистік шешімдері
x1=5, x2=3, x3=0, x4=0, x5=6, x6=3.
болады.
Сонымен базистік шешімдер оптимальды болып, ең кіші ...F1min=-50 бoлады. Есеп шешілді.
5° Жоғарыда баяндалған есептің шешу әдісі бір мүмкін базистік шешімнен басқа шешімге көшу әдісімен шығарылды. Бірақ мұндай әрбір көшуде минимизацияланатын фрманың кемуіне алып келеді.
Енді симплекс әдісінің растаушы теориясын тұжырымдайық.
Теорема 2.1 Қандайда бір сызықтық программалау негізгі есебі берілсін. Осы есептің (оптималь) оңтайлы шешімі бар деп ұйғарайық. Сонда бұл есепте ең болмағанда бір ғана оңтайлы базистік шешімдер бар.
Түсіндірме Біз ереже бойынша оңтайлы шешімнің жалғыздығын айтқан болатынбыз. Бірақта кейде оңтайлы шешім жалғыз емес жағдайларыда болуы мүмкін. 1-ші теореме осындай оңтайлы шешімдердің арасында бір жаңа базисті шешімі бар екендігін айтады. Егерде есепте бір ғана оңтайлы шешім бар болса, онде ол базисті болып табылады. Бұл теремены дәлелдеусіз қабылдаймыз.
6°. Алдыңғы параграфта симплекс әдісінің қарапайым мысалдармен идеясын түсіндіріп, бұл әдістің теоремаларын расталған болатын. Қазір біз сызықтық программалаудың негізгі есептерін қарастырып, оны симплекс әдісімен шешудегі минимизацияланатын форма мен шектеулер жүйесінің алгебралық түсіндіру заңын үйренеміз.
Шектеулер жүйесімен негізгі есептің сызықтық формасы мына түрде болады.
a11x1+...+a1nxn=b1,. . . . . . . . . . . . . . .am1x1+...+amnxn=bm, (2.1.16)
F=c0+c1x1+...+cnxn. (2.1.17)
(2.1.16) жүйесінің рангі n белгісіздер санынан кіші. Әрқашан белгісіздерді нөмерлеуге болады, бос белгңһісіздерді теңесу үшін (k=n-r) алғашқы белгісіздері шығады.
Бұл жағдайда базисты айнымалыларды xk+1,...,xn , деп өрнектеп, F форманы сол бос айнымалылар арқылы өрнектесек
xk+1=α'11x1+...+α'1kxk+β1,. . . . . . . . . . . . . . . . . . . . .xk+l=α'l1x1+...+α'lkxk+βl,. . . . . . . . . . . . . . . . . . . . .xn=α'r1x1+...+α'rkxk+βr, (2.1.18)
F=γ0+γ'1x1+...+γ'kxk. (2.1.19)
қатынастарға келеміз.
Бос белгісіздер арқылы
x1=0,...,xk=0, xk+1=β1,..., xn=βr. (2.1.20)
базисті шешімдер болады.
(2.1.20) шешімі бос белгісіздер арқылы жасанды деп табылсы. Бұл дегеніміз β1,...,βr теріс емес. F формасы сонымен γ0- тең.
Енді (2.1.20) жасанды базистышешімдерден басқа базисты шешімге F формасы γ0- ден кіші болатын мәнге ие болу үшін көшеміз. Ықшамдау үшін (2.1.18) жүйе мен (2.1.19) фoрманы мына түрде қайта жазамыз.
xk+1=β1-(-α'11x1-...-α'1kxk),. . . . . . . . . . . . . . . . . . . . .xk+l=βl-(-α'l1x1-...-α'lkxk),. . . . . . . . . . . . . . . . . . . . .xn=βr-(-α'r1x1-...-α'rkxk),
F=γ0-(-γ'1x1-...-γ'kxk).
қысқаша белгілеулер енгіземіз.
-α'ij=αij;-γ'i=γi(i=1,...,k; j=1,...,r)
келесі жүйе мен формаға келеміз.
xk+1=β1-(α11x1+...+α1kxk),. . . . . . . . . . . . . . . . . . . . .xk+l=βl-(αl1x1+...+αlkxk),. . . . . . . . . . . . . . . . . . . . .xk+i=βi-(αi1x1+...+αikxk),. . . . . . . . . . . . . . . . . . . . .xn=βr-(αr1x1+...+α'rkxk), (2.1.21)
F=γ0-(γ1x1+...γkxk). (2.1.22)
Ескерту 2.1 Барлық жағдайда симплекс әдісі бойынша шектеулер жүйесі мен минималданатын F формасын (2.1.21) және (2.1.22) түрде жазамыз. Мұндай жазба барлық топтағы бас белгісізі бар қосындылар алдында жалпы минус таңбасы қойылады.
7°. (2.1.21) және (2.1.22) -дағы бос мүшелерді және бос белгісіздердің барлық коэффициенттерін жалпы таблицаға енгіземіз, оны симплекс -таблица деп атаймыз, бос белгісіздер жиынына сәйкес келетін.
Кесте 8
Бос
белгісіздер
Базисті
белгісіздер
x1...
xs...
xj
...
xk
xk+1
β1
α11
α1s
α1j
...
α1k
Кесте 8 жалғасы
...
...
...
...
...
...
...
xk+l
βl
αl1
αls
αlj
...
αlk
...
...
...
...
...
...
...
xk+i
βi
αi1
αis
αij
...
αik
...
...
...
...
...
...
...
xn
βr
αr1
αrs
αrj
...
αrk
F
γ0
γ1
γs
γj
...
γk
Бұл кестенің әрбір қатары теңдеудің базистік белгісіздерді бос белгісіздер арқылы көрсетуіне жауап береді. (2.1.22) өрнектің құрамына F формасы γi коэффициенттін кіретін бос белгісіздерді қарастырайық. Осы қарастырылатын бос белгісіздерден кез- келген біреуін таңдаймыз, мысалыға xj (xj үшін алынан) бос белгісіз (2.1.22) өрнектің құрамына γi ең кіші оң коэффициентпен кіретіндей етіп таңдауымыз керек. Бірақ бұл шарт міндетті болып табылмайды.
Егерде барлық бос белгісіздерді xj-деп басқаларын нөлдік мәндерімен сақтасақ, ал xj өсірсек, онда ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
Ұқсас жұмыстар
Пәндер
- Іс жүргізу
- Автоматтандыру, Техника
- Алғашқы әскери дайындық
- Астрономия
- Ауыл шаруашылығы
- Банк ісі
- Бизнесті бағалау
- Биология
- Бухгалтерлік іс
- Валеология
- Ветеринария
- География
- Геология, Геофизика, Геодезия
- Дін
- Ет, сүт, шарап өнімдері
- Жалпы тарих
- Жер кадастрі, Жылжымайтын мүлік
- Журналистика
- Информатика
- Кеден ісі
- Маркетинг
- Математика, Геометрия
- Медицина
- Мемлекеттік басқару
- Менеджмент
- Мұнай, Газ
- Мұрағат ісі
- Мәдениеттану
- ОБЖ (Основы безопасности жизнедеятельности)
- Педагогика
- Полиграфия
- Психология
- Салық
- Саясаттану
- Сақтандыру
- Сертификаттау, стандарттау
- Социология, Демография
- Спорт
- Статистика
- Тілтану, Филология
- Тарихи тұлғалар
- Тау-кен ісі
- Транспорт
- Туризм
- Физика
- Философия
- Халықаралық қатынастар
- Химия
- Экология, Қоршаған ортаны қорғау
- Экономика
- Экономикалық география
- Электротехника
- Қазақстан тарихы
- Қаржы
- Құрылыс
- Құқық, Криминалистика
- Әдебиет
- Өнер, музыка
- Өнеркәсіп, Өндіріс
Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор #1 болып табылады.
Ақпарат
Қосымша
Email: info@stud.kz