Сызықтық программалаудың есептері

Кіріспе...
1 Сызықтық программалаудың жалпы және негізгі есептері
2 Сызықтық программалаудың негізгі есебінің қасиеттері
3 Сызықтық программалау есептерінің шешімін табу
Қорытынды
Пайдаланылған әдебиеттер тізімі

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

1. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. Пособие для студентов эконом. спец. вузов. – М.: Высш. шк., 1986. – 319 б.
2. Ашманов С.А. Линейное программирование. – М.: Наука, 1981. – 317 б.
3. Данко П.Е., Попов А.Г., Кожевникова Т.Я. – 7-е изд., испр. – М.: ООО «Издательство Оникс»: ООО «Издательство «Мир и Образование», 209. – 368 б.
4. Гасс С. Линейное программирование (методы и приложения). – М.: Физматгиз, 1961.
5. Гуревич Т.Ф., Лущук В.О. Сборник задач по математическому программированию. – М.: Колос, 1977.
6. Карманов В.Г. Математическое программирование. – М.: Наука, 1975.
7. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. – М.: Высшая школа, 1980.
8. Юдин Д.Б., Гольштейн Е.К. Линейное программирование. Теория и конечные методы. – М.: Физматгиз, 1963.
9. Балашевич В.А. Математические методы в управлении производством. – Минск: Вышэйшая школа, 1976.
10. Виславский М.Н. Линейная алгебра и линейное программирование. – Минск: Вышейшая школа, 1966.
11. Гольштейн Е.Г., Юдин Ю.Б. Новые направления в линейном программировании. – М.: Советское радио, 1966.
12. Вильямс Н.Н. Параметрическое программирование в экономике. – М.: Статистика, 1976.
13. Данциг Дж. Линейное программирование, его обобщения и приложения. – М.: Прогресс, 1966.
14. Зуховицкий С.И., Авдеева Л.И. Линейное и выпуклое программирование. – М.: Наука, 1967.
15. Калихман И.Л. Линейная алгебра и программирование. – М.: Высшая школа, 1967.
16. Нит И.В. Линейное программирование. – М.: Изд-во МГУ, 1978.
17. Полунин И.Ф. Курс математического программирования. – Минск: Вышэйшая школа, 1975.

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

Жанай Гаухар 04401а
Сызықтық программалаудың есептері
Мазмұны

Кіріспе ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
5
1
Сызықтық программалаудың жалпы және негізгі есептері
7
2
Сызықтық программалаудың негізгі есебінің қасиеттері
18
3
Сызықтық программалау есептерінің шешімін табу
32

Қорытынды
58

Пайдаланылған әдебиеттер тізімі
59

Кіріспе

Математикалық программалау өз алдына экстремальдық есептерді оқыту мен оларды шешу әдістерін қарастыру математиканың бір бөлімі болып табылады.
Экстемальдық есептердің жалпы түрдегі математикалық қойылымы анықтамадағы шартының бүтін функциясынан тұрады, мұндағы және - берілген функция, ал - кейбір нақты сан. және функцияларының қасиеттеріне байланысты математикалық программалауды белгілі бір есептердің классын оқыту мен оларды шешу әдістерімен шұғылданатын дербес пән ретінде қарастыруға болады.
Ең алдымен математикалық программалаудың есептері сызықтық және сызықтық емес программалау есептері болып бөлінеді. Бұл жағдайда барлық және функциялары сызықтық болса, онда тиісті есеп те сызықтық программалудың есептері болып табылады.
Математикалық программалаудың көбіне оқылатын бөлімі сызықтық программалау болып табылады. Сызықтық программалаудың есептерін шешу үшін көптеген тиімді әдістер, алгоритмдер және программалар жасалған.
Ең алғаш сызықтық программалаудың есептерінәйгілі Кеңес одағының математигі Контеровичпен тұжырымдалған, және бұл жұмысы үшін экономика бойынша Нобельдік сыйлығы тағайындалды.
Дипломдық жұмыс кіріспеден, үш параграфтан, қорытындыдан және пайдаланылған әдебиеттер тізімінен тұрады.
Бірінші параграфта сызықтық программалаудың жалпы және негізгі есептеріне бірнеше мысалдар келтіру арқылы қарастырылған.
Екінші параграфта сызықтық программалаудың негізгі есебінің қасиеттеріне тоқталып өтілген.
Үшінші параграфта сызықтық программалаудың есептерін симплексті әдіспен шешуге байланысты мысалдар келтіріліп және олардың шешу жолдары көрсетілген.
Осы сызықтық программалаудың есептеріне қатысты көптеген мысалдар қарастырылып, олардың шығарылу әдістері зерттелген.
Дипломдық жұмыстың барлық теориялық материалдары мысалдар келтіру арқылы бекітіліп және әр түрлі әдістер қолдана отырып шешуге бағытталған.
Өзектілігі:
* Қазіргі заманғы ғылымның Сызықтық программалау-ға деген үлкен қызығушылықтың болуы;
* Сызықтық программалаудың есептеріне байланысты мәселелерді теориялық және практикалық маңыздылығы жағынан қарау.
Дипломдық жұмыстың мақсаты. Сызықтық программалаудың есептерін шешу әдістерін зерттеу.
Зерттеу объектісі. Сызықтық программалаудың есептері.
Зерттеу пәні. Сызықтық программалаудың есептерін шешу.
Зерттеу жұмысының міндеттері:
* ғылыми және әдістемелік материалдарды жинақтап талдау;
* сызықтық программалаудың есептерінің шешімдерін зерттеу;
* сызықтық программалаудың есептерін симплексті әдісті қолдану арқылы шешуді зерттеу.

1 Сызықтық программалаудың жалпы және негізгі есептері

Ең алдымен сызықтық программалау есептеріне бірнеше мысалдар қарастырайық.
Мысал 1.

теңсіздігімен анықталатын жарты жазықтықты табыңыз.
Шешімі. теңсіздікті тура теңдікке алмастыру арқылы немесе түзуінің теңдеуін аламыз (1 сурет). Берілген теңсіздікті түріне келтіріп аламыз. Сәйкесінше, ізделініп отқан жарты жазықтық түзуінен төмен орналасқан.

О

1 сурет

Мысал 2. Қандай жазықтықты

теңсіздігі анықтайды?
Шешімі. теңсіздікті тура теңдікке алмастыру арқылы, координта басынан өтетін немесе түзуінің теңдеуін аламыз. Ізделініп отырған жарты жазықтық теңсіздігінен шығады және ол түзуінен төмен орналасқан (2 сурет).

О

2 сурет

Мысал 3. , және бұйымдарының үш түрін дайындау үшін токарлық, фрезерлік, дәнекерлейтін және тегістейтін (өңдейтін) құралдар пайдаланылады. Құрал-жабдықтың әрбір типінің бір бұйымды өңдеуге шығындайтын уақыты 1 кестеде көрсетілген. Онда пайдаланылатын құрал-жабдықтың әрбір типінің жұмыс уақытының жалпы қоры, сондай-ақ, әрбір түрдің бір бұйымын жасаудан шығатын пайда көрсетілген. Олардың іске асырылуынан максимальді пайда болуы үшін кәсіпорынға қанша бұйым және қай түрінен дайындау (жасап шығару) қажеттігін анықтау талап етіледі. Тапсырманың математикалық моделін құрастыру керек.
1кесте

Құрал-жабдық
типі - металл
Түрдің бір бұйымын
өңдеуге шығындайтын уақыты (станок)
Құрал-жабдықтың жұмыс уақытының жалпы қоры (с)

А
В
С

Фрезерлік - темір
Токарлық - аллюминий
Дәнекерлейтін - мыс
Тегістейтін - алтын
2
1
7
4
4
8
4
6
5
6
5
7
120
280
240
360
Пайда (теңге)
10
14
12

Шешімі. Бұйымның түрінен бірлік, түрінен бірлік және түрінен бірлік дайындалады делік. Онда сондай бұйым санының өндірісі үшін фрезерлік құрал-жабдықтың станок-сағат уақыты қажет болады.
Аталмыш типтегі станоктардың жұмыс уақытының жалпы қоры 120-дан артық болғандықтан, теңсіздік орындалуы тиіс

.

Токарлық, дәнекерлейтін және тегістейтін құрал-жабдықтардың қатысты мүмкін қолданылуын осылай пайымдау келесі теңсіздіктерге алып келеді:

Мұнымен қоса дайындалатын бұйымдардың саны теріс бола алмайтындықтан

. (1)

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

(2)

және осы айнымалы шамаға қатысты сызықтық функция берілген

, (3)

теңсіздік жүйесінің (2) барлық теріс емес шешімдері арасынан функция (3) максимальді мәнге ие болатындайды табу талап етіледі. Мұны қалай жасау керектігі алдағы уақытта көрсетіледі.
Теңсіздік жүйесімен (2) және айнымалылардың (1) теріс еместік шартымен бірге максимум анықтау керек болатын сызықтық функция (3) бастапқы есептің математикалық моделін қалыптастырады.
Функция (3) сызықтық, ал жүйе тек сызықтық теңсіздіктен тұратын болғандықтан, (1)-(3) есебі сызықтық программалау есбеі болып табылады.
Мысал 4. Қалалық сүт зауытының өнімдері - бөтелкелерге бөлшектелген сүт, айран және қаймақ. 1 т сүт, айран және қаймақ өндірісіне сәйкесінше 1010, 1010 және 9460 кг сүт талап етіледі. Мұнымен қоса, 1 т сүт пен айранды бөліп құю кезіндегі жұмыс уақытының шығыны 0,18 және 0,19 машина уақытын құрайды. 1 т қаймақты бөлшектеп құюға 3,25 сағ бойы арнайы автоматтар жұмыс жасайды. Қаймағы алынбаған сүт өнімдерінің өндірісі үшін зауыт барлығы 136000 кг сүт пайдалана алады. Негізгі құрал-жабдықтар 21,4 машина с бойы, ал қаймақты бөлшектейтін автоматтар 16,25 сағ. бойы жұмыс істейді. 1 т сүт, айран және қаймақ өндірісіен келетін пайда сәйкесінше 30, 22 және 136 теңгеге тең. Зауыт күн сайын бөтелкелерге бөлшектеліп құйылған 100 т сүттен кем шығармауы тиіс. Басқа өнім өндірісіне ешқандай шектеу жоқ.
Өнімді шығарғаннан түсетін пайда максимальды болуы үшін зауыт күн сайын қандай өнімді және қандай мөлшерде дайындауы қажеттігін анықтау талап етіледі. Есептің математикалық моделін құрамыз.
Шешімі. Сүт зауыты күн сайын тонна сүт, тонна айран және тонна өндіріп шығарады делік. Онда оғаны осы өнімді дайындауы үшін тонна сүт қажет.
Зауыт күн сайын 136 000 т артық емес сүт пайдалана алатындықтан, келесі теңсіздік орындалуы тиіс

Қаймағы алынбаған сүт өнімдерінің бөліп құю және қаймақты бөлшектеп құятын автоматтар линиясын пайдалану ықтималдығына қатысты жүргізілген осыған ұқсас пайымдаулар келесі теңсіздікті жазуға мүмкіндік береді:

Күн сайын 100 т кем емес сүт өндірілуі керек болғандықтан, . Одан әрі және айнымалылыары өзінің экономикалық мәніне қарай тек теріс: , мәнді мәнді ғана қабылдай алады. тонна сүт, тонна айран және тонна қаймақты өндіргеннен түсетін жалпы пайда теңгеге тең. Осылайша, келесі математикалық есепке келеміз:

(4)

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

, (5)

теңсіздік жүйесінің барлық теріс шешімдерінің арасынан (4) функция (5) максималды мәнге ие болатындайды табу талап етіледі. Жүйе (4) сызықтық теңсіздіктердің жиынтығынан тұрып, функция (5) сызықтық болғандықтан бастапқы есеп сызықтық программалаудың есебі болып табылады.
Мысал 5. Тігін фабрикасындағы тігін бұйымдарының қажетті детальдерін дайындау үшін мата бірнеше тәсілмен пішілуі мүмкін. нұсқасында матаның 100 м2 пішуінен түрінің деталі әзірленеді, ал пішудің аталмыш нұсқасындағы қалдықтардың мөлшері м2 - қа тең болсын. түрінің детальдарынан дана әзірлеу керектігін біліп, минимальді жалпы қалдық қалған кезде әрбір түрінен қажетті детал саны алынатындай матаны пішу қажет етіледі. Есептің математикалық моделін құрастырайық.
Шешімі. нұсқасы бойынша м2 матаның жүзіншісі қиылады деп болжалық. 100 м2 матаны пішу кезінде нұсқасы бойынша түрінің деталдары алынатындықтан, пайдаланылған мата пішінінің барлық нұсқалары бойынша түрінің

деталы алынады. Аталмыш түрдің деталы әзірленуі тиіс болғандықтан

Мата пішіндерінің барлық нұсқасы бойынша қалдықтардың жалпы мөлшері

құрайды.
Осылайша, келесі математикалық есепке келеміз

(6)

функциясының оның айнымалылары

(7)

теңсіздігі жүйесін қанағаттандыратын шартында және терістік шартында минимумын табу.
Тұжырымдалған есеп функция (6) сызықтық, ал жүйе (7) тек сызықтық теңдікті ұстағандықтан сызықтық программалаудың есебі болып табылады.
Жоғарыда сызықтық программалау мысалдары қарастырылды. Осы есептердің барлығында айнымалылары теріс мәнге ие болып, сызықтық теңеулердің немесе сызықтық теңсіздіктердің кейбір жүйесін немесе сызықтық теңсіздіктер секілді сызықтық теңеулерден де тұратын жүйені қанағаттандырады. Осы есептердің әрқайсысы сызықтық программалау жалпы есебінің жеке жағдайы болып табылады.
Анықтама 1. Сызықтық программалаудың жалпы есебі деп

(8)

(9)

(10)

шартындағы

(11)

функциясының максимальді мәнінің анықтамасынан тұратын есепті айтады. Мұндағы , , - берілген тұрақты шамалар және .
Анықтама 2. Функция (11) есептің (8)-(11) мақсатты функциясы деп (немесе сызықтық формасы), ал шарт (8)-(10) - берілген есептің шектеулері деп аталады.
Анықтама 3. Сызықтық программалаудың стандартты (немесе симметриялық) есебі деп және болатын (8) және (10) шарттарын орындау кезіндегі (11) функцияның максимальді мәнінің анықтамасында тұратын есепті айтады.
Анықтама 4. Сызықтық программалаудың каноникалық (немесе негізгі) есебі деп және болатын (9) және (10) шарттарын орындау кезіндегі (11) функцияның максимальді мәнінің анықтамасынан тұратын есепті айтады.
Анықтама 5. (8) - (10) есептерінің шектеулерін қанағаттандыратын сандарының жиынтығы шектеулі шешім (немесе жоспар) деп аталады.
Анықтама 6. (11) есептің мақсатты функциясы өзінің максимальді (минимальді) мәніне ие болатын жоспары оңтайлы деп аталады.
Мақсатты функцияның (11) мәнін жоспарында арқылы белгілейміз.Ендеше егер кез келген үшін [сәйкесінше теңсіздігі орындалса - есептің оңтайлы жоспары.
Сызықтық программалау есебінің жоғарыда көрсетілген үш формасы олардың әрқайсысы күрделі емес өзгерістердің көмегімен басқа есептің формасына көшіріп жазылатын жағдайда эквиваленттер болып табылады. Бұл егер көрсетілген есептердің біреуінің шешімін табу тәсілі бар болса, онда сол арқылы үш есептің кез келгенінің оңтайлы жоспары анықталуы мүмкін.
Сызықтық программалау есебі жазбасының бір формасынан басқасына өту үшін жалпы жағдайда біріншіден функция минимизациясының есебін максимизация есебіне қысқарта білу керек, екіншіден теңсіздік шектеуінен теңдік шектеуіне және керісінше өтіп, үшіншіден терістік шартына бағынбайтын айнымалыларды алмастыра білу керек.
функциясының минимумын табу талап етілген жағдайда болғандықтан функциясының максимумын табуға көшуге болады.
Сызықтық программалаудың бастапқы есебінің түріндегі шектеу-теңсіздігі оның сол бөлігіне қосымша теріс айнымалыны қосып шектеу-теңсіздігіне өзгертуге болады, түріндегі шектеу-теңсіздігін оның сол бөлігінен қосымша теріс айнымалыны азайту арқылы шектеу-теңдікке айналдыруға болады. Осылайша

шектеу-теңсіздігі

(12)

шектеу-теңдігіне (теңдеуіне) өзгереді, ал

шектеу-теңсіздігі

(13)

шектеу-теңдігіне айналады.
Сонымен қатар шектеу жүйесінің әрбір теңдеуін

теңсіздік түрінде жазуға болады:

(14)

Енгізілетін қосымша теріс айнымалылардың саны шектеу-теңсіздігінен шектеу-теңдігіне өзгеру кезінде өзгерілетін теңсіздіктер санына тең.
Енгізілетін қосымша айнымалылар толықтай анықталған экономикалық мағынаға ие. Мысалы, егер сызықтық программалаудың шектеулерінде өндірістік ресурстардың шығыны мен қолда бары көрінсе, онда негізгі формада жазылған есеп жоспарындағы қосымша айнымалының сандық мәні пайдаланылмаған тиісті ресурстың көлеміне тең.
Егер айнымалы терістік шартына бағынбаған болса, онда оны қабылдап және екі теріс емес айнымалыларға ауыстырған жөн.
Мысал 6.

шектелген сызықтық формасын кеңейту.
Шешімі. Теңсіздіктің таңбасын қатаң теңдікке алмастырып, түзулерінің теңдеуі арқылы мәндер облысын құрамыз.(сурет 3).
Теңсіздіктің мәндер облысы үшбұрышы болады. векторын құрайық.

M
P
N

3 сурет

Мысал 7. Сызықтық программалау есебінің негізгі формасында келесі есепті жазу:

.

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

Ендеше, аталмыш есеп негізгі есеп формасында былайша жазылуы мүмкін:

шартындағы функциясын максимализациялау.
Мысал 8.

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

.

шартындағы функциясының максимумын табу.
Мысал 9. Сызықтық программалаудың стандартты формасында келесі есепті жазу:

.

шартындағы функциясының максимумын табу.
Шешімі. Белгісіздерді жүйелі шығару әдісі арқылы аталмыш есепті келесіге келтіреміз:

.

шартындағы функциясының максимумын табу.
Соңғы есеп

.

шартындағы функциясының максимальді мәнін табудан тұратын есепке арналған негізгі формасында жазылған.
Есептің мақсатты функциясы және орнына есептің шектеу жүйесінің теңдеулеріне сәйкес олардың мәндерін қою арқылы түрлендірілген.

2 Сызықтық программалаудың негізгі есебінің қасиеттері

Сызықтық программалаудың негізгі есебін қарастырамыз. § 1-де атап өткендей ол шартындағы функциясының максимальді анықтамасынан тұрады.
Бұл есепті векторлық формада қайта көшіреміз:

(15)

(16)

шартындағы

(17)

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

.

Анықтама 7. Егер жіктеуге кіретін векторларының жүйесі (16) оң коэффициенттерімен сызықтық тәуелсіз болса жоспары сызықтық программалаудың негізгі есебінің тірек жоспары деп аталады.
Сөйтіп, векторлары -өлшеуіш болғандықтан, тірек жоспары анықтамасынан оның оң компоненттерінің саны -дан көп бола алмайтыны шығады.
Анықтама 8. Тірек жоспары бірдеу оң компоненттерінен тұрса ол өзгешеленбеген деп, ал керісінше жағдайда өзгешеленген деп аталады.
Сызықтық программалаудың негізгі есебінің (15) - (17) қасиеті дөңес жиындар қасиеттерімен тығыз байланысты.
Анықтама 9. - евклид кеңістігінің кез келген нүктелері болсын. Осы нүктелердің дөңес сызықтық комбинациясы деп жиынтығы тең, - кез келген теріс саны болатын, жиынтығы аталады.
Анықтама 10. Егер жиынтық өзінің кез келген екі нүктесімен бірге олардың кез келген дөңес сызықтық комбинациясынан тұрса онда ол жиынтық дөңес деп аталады.
Анықтама 11. Дөңес жиынтықтың нүктесі егер аталмыш жиынтықтың қандай да бір екі әр алуан нүктесінің дөңес сызықтық комбинациясы түрінде көрсетілмесе онда ол нүтке бұрыштық деп аталады.
Теорема 1. Сызықтық программалаудың негізгі есебі жоспарларының жиынтығы (егер ол бос болмаса) дөңес болып табылады.
Анықтама 12. Сызықтық программалаудың негізгі есебі жоспарының бос емес жиынтығы шешімнің көпжағы (көп қырлы дене) деп, ал шешім көп жағының кез келген бұрыштық нүктесі - ұшы деп аталады.
Теорема 2. Егер сызықтық программалаудың негізгі есебінің тиімді жоспары болса, онда есептің мақсатты функциясының максимальді мәні ұштардың бірінде шешім көп қырын қабылдайды. Егер есептің мақсатты функциясының максимальді мәні бір ұштан да көп қабылдаса, онда ол оны осы ұштардың дөңес сызықтық комбинациясы болып табылатын кез келген нүктеде қабылдайды.
Теорема 3. Егер жіктеудегі (16) векторлар жүйесі сызықтық тәуелсіз болса және

, (18)

мұндағы болса, онда нүктесі шешім көп жақтың (көп қырлы дененің) ұшы болып табылады.
Теорема 4. Егер - шешім көпжақтың (көп қырлы дененің) ұшы болса, онда оң - пен сәйкес келетін векторлары жіктеуде (16) сызықты тәуелсіз.
Тұжырымдалған теоремалар келесі қорытындылар жасауға мүмкіндік береді.
Сызықтық программалаудың негізгі есебінің бос емес жиынтығы дөңес көпжақ (көп қырлы дене) түзеді. Осы көпжақтың әрбір ұшы тірек жоспарын анықтайды. Шешім көпжағының бір ұшындағы (яғни тірек жоспарларының бірі үшін) мақсатты функцияның (функция жоғары жағынан жоспарлар жиынтығына шектелген болған жағдайда) мәні максимальді болып табылады. Егер функция максимальді мәнді бір ұштағыдан да көп қабылдаса, онда ол осы мәнді аталмыш ұштардың сызықтық комбинациясының дөңесі болып табылатын кез келген нүктеде қабылдайды.
Мақсатты функция максимальді мәні қабылдайтын шешім көпжағының ұшын салыстырмалы түрде табу оңай, егер стандартты формада жазылған есеп құрамы екі айнымалыдан көп болмаса немесе негізгі формада жазылған есеп құрамы екі еркін айнымалыдан көп болмаса, яғни , мұндағы - айнымалылар саны, - есептерді шектеу жүйесіндегі коэффициенттерден құралған матрицалар рангі.

(19)

. (20)

болса

(21)

функциясының максимальді мәнінің анықтамасынан тұратын есеп шешімін табамыз.
Есепті шектеу жүйесі теңсіздігінің әрқайсысы геометриялық түрде шектес түзулерге сәйкесті жарты жазықтықты анықтайды. Егер (19), (20) теңсіздік жүйесі бірлескен болса оның шешілу алаңында көрсетілген барлық жарты жазықтықтарға жататын нүктелер жиыны бар. Аталмыш жарты жазықтықтардың қиылысу нүктелерінің жиыны дөңес болғандықтан, есептің шектеулі шешімінің аясы (19) - (21) шешімнің көпбұрышы (бұрын енгізілген шешімнің көпжағы деген термині әдетте n3 болса қолданылады) деп аталатын дөңес жиын болып табылады. Осы көпбұрыштың қабырғалары теңдеуі теңсіздік белгілерінің дәл теңдік белгілеріне алмасуды шектеудің бастапқы жүйесінен алынатын түзулерде жатады.
Осылайша, сызықтық программалаудың бастапқы есебі мақсатты функциясы максимальді мәнді қабылдайтын көпбұрыш шешімінің нүктесін табудан тұрады. Бұл нүкте көпбұрыш шешімі болмағанда және ондағы мақсатты функция жоғарыдан шектеулі болғанда бар болады. Көпбұрыш шешімі ұштарының біріндегі көрсетілген шарттарда мақсатты функция максимальді мәнге ие болады. Аталған ұшты анықтау үшін шешім көпбұрышы арқылы өтетін (мұндағы - аз ғана тұрақты шама) деңгейінің сызығын құрамыз және оны векторының бағытында ол вектордың шешім көпбұрышымен ортақ соңғы нүктесінен өткенге дейін жылжытамыз. Көрсетілген нүктенің координаттары берілген есептің тиімді жоспарын анықтайды.

0
А

4 сурет

0
А

В
5 сурет

(8) - (21) есептерінің геометриялық түсіндірілуін қарастыруды аяқтай келе, оның шешімін табу барысында 4-7-суреттерінде суреттелген жағдайлар кездесуі мүміндігін атап өтеміз. 4-суреті мақсатты функция жалғыз нүктесіндегі максимальді мәнді қабылдағандағы жағдайды сипаттайды. 5-суретінен мақсатты функция максимальді мәнді кесігінің кез келген нүктесінен қабылдайтыны көрініп тұр. 6-суретінде мақсатты функция жоғарыдан шектеулі шешімдер жиынына шектелмеген жағдайы, ал 7-суретте - есептің шектеу жүйесі бірлеспеген жағдайы көрсетілген.
Көрсетілген шектеу жүйесі кезіндегі сызықтық функцияның максимальді мәнін табу сол шектеулердегі оның максимальді мәнін табудан айырмашылығы - деңгейінің сызығы векторы бағытында емес қарама-қарсы бағытында жылжитынында ғана.

0

6 сурет

0

6 сурет

Осылайша, мақсатты функцияның максимальді мәнін табуда ұшырасқан жоғарыда айтылған жағдайлар оның минимальді (ең аз) мәнін анықтауда да орын алады.
Сөйтіп, геометриялық түсіндіру негізінде сызықтық программалау есептерінің (19)-(21) шешімін табу келесі кезеңдерден тұрады:
1. Шектеулердегі (19) және (20) теңсіздік белгілерінің дәл теңдік белгілеріне алмасуы нәтижесінде алынатын түзу теңдеулер құрады.
2. Есеп шектеуінің әрқайсысымен анықталатын жарты жазықтықтарды табады.
3. Шешім көп бұрышын табады.
4. векторын құрады.
5. Шешім көпбұрышы арқылы өтетін түзуін құрады.
6. түзуін векторының бағытында жылжытады, нәтижесінде мақсатты функция максимальді мән қабылдайтын нүктені табады немесе жоспарлар жиынына функцияның жоғарынан шексіздік орнатады.
7. Функция максимумы нүктесінің координаттарын анықтайды және осы нүктедегі мақсатты функцияның мәнін есептеп шығарады.
Мысал 7. және бұйымдарының екі түрлі өндірісі үшін кәсіпорын шикізаттың үш түрін қолданады. Өнімнің аталмыш түрінің бірліктерін дайындауға кететін әрбір шикізат түрінің шығын нормасы 1.2-кестеде көрсетілген. Онда әрбір түрдің бір бұйымын жасаудан түсетін пайда және кәсіпорын пайдаланатын аталмыш шикізат түрінің жалпы саны көрсетілген.

2 кесте

Шикізат түрі
Бір бұйымға кететін шикізат шығынының нормасы (кг)
Шикізаттың жалпы саны (кг)

I
II
III
A
B

300
120
252

12
4
3
4
4
12

Бір бұйымды жасаудан (шығарудан) түсетін пайда (теңге)

30

40

және бұйымдарының кез келген арақатынаста өндірілетінін (өткізу қамтамасыз етілген) ескере отырып, барлық бұйымдарды шығарудан кәсіпорын түсіретін пайда максимальді болатындай оларды шығару жоспарын құру талап етіледі.
Шешімі. Кәсіпорын түрінің бұйымын және түрінің бұйымын дайындайды делік. Өнім өндірісіне беретін кәсіпорын қарауында бар әрбір түрдің шикізаты шектеулі болғандықтан және дайындалатын бұйым саны теріс болмайтындықтан келесі теңсіздік орындалуы тиіс

.

түрінен бұйымын және түрінен бұйымын шығарудан түсетін жалпы пайда құрайды.
Осылайша, біз келесі математикалық есепке келеміз: сызықтық теңсіздіктердің аталмыш жүйесінің барлық теріс шешімі арасынан функциясы максимальді мән қабылдайтынды табу талап етіледі.
Тұжырымдалған есептің геометриялық түсіндірілуін пайдалана отырып оның шешімін табамыз. Алдымен шешім көпбұрышын анықтаймыз. Бұл үшін шектеу жүйесі теңсіздіктерінде және айнымалылардың теріс емес жағдайындағы теңсіздік белгілерін дәл теңдік нүктесінің белгілеріне алмастырамыз және сәйкес түзулерді табамыз:

Бұл түзулер 5-суретте көрсетілген. Құрылған түзулердің әрқайсысы жазықтықты 2 жарты жазықтыққа бөледі. Бір жарты жазықтық нүктелерінің координаттары бастапқы теңсіздікті қанағаттандырады, ал басқасы қанағаттандырмайды. Ізделіп отырған жарты жазықтықты анықтау үшін жарты жазықтықтың біріне тиесілі қандай да бір нүктені алып, оның координаттары аталмыш теңсіздікті қанағаттандыра ма жоқ па соны тексеру керек. Егер алынған нүктенің координаттары берілген теңсіздікті қанағаттандырса, онда ізделіп отырған жарты жазықтық осы нүкте тиесілі жарты жазықтық болады, ал керісінше жағдайда - басқа жарты жазықтық болады.
Мысалы, теңсіздігімен анықталатын жарты жазықтықты табайық. Бұл үшін түзуін құрып (5-суретте осы түзу), алынған екі жарты жазықтықтың біріне жататын (тиесілі) қандай да бір нүктені аламыз, мысалы нүктесін. Бұл нүктенің координаттары теңсіздігін қанағаттандырады; яғни нүктесі жататын жарты жазықтық теңсіздігімен анықталады. Бұл 5-суретте стрелкалармен көрсетілген.

7 cурет

Алынған жарты жазықтықтардың қиылысы берілген есептің шешімінің көп бұрышын анықтайды.
7-суретте көрініп тұрғандай бес бұрышы шешім көп бұрышы болып табылады. Осы бес бұрышқа тиесілі кез келген нүкте координаттары теңсіздіктің аталмыш жүйесі мен айнымалылардың теріс емес шартын қанағаттандырады. Сондықтан тұжырымдалған есеп - егер біз функциясы максимальді мән қабылдайтын бес бұрышына тиесілі нүктені таба алсақ шешілетін болады. Көрсетілген нүктені табу үшін векторын және түзуін құрамыз, мұндағы - түзуі шешім көп бұрышымен бірге ортақ нүктеге ие болатын аз ғана тұрақты шама. Мысалы, делік те (7 сурет) түзуін құрамыз.
Енді құрылған түзу мен шешім көп бұрышына тиесілі қандай да бір нүктені алсақ, онда оның координаттары бұйымды шығарудан түскен пайда 480 теңге тең болатын және бұйымы өндірісі жоспарын анықтайды (белгілейді). Әрі қарай, 480-нен көп кейбір санға тең деп болжап түрлі паралеллді түзулер аламыз. Егер олардың шешім көпбұрышымен ортақ нүктелері болса, онда бұл нүктелер бұйым шығарудан түсетін пайда 480 теңгеден асып түсетін және бұйымы өндірісінің жоспарын анықтайды.
Құрастырылған түзуін векторы бағытына орналастыра отырып, оның есеп шешімі көбұрышымен ортақ соңғы нүктесі қызметін нүктесі атқаратынын көреміз. Осы нүктенің координаттары және бұйымын шығару жоспарын анықтайды, ал оларды шығарғаннан түсетін пайда максимальді болып келеді.
ІІ және ІІІ түзу қиылыстарының нүткесі секілді нүктесінің координаттарын табамыз. Ендеше, оның координаттары осы

түзулердің теңдеулерін қанағаттандырады.
Осы теңеу жүйесін шешіп аламыз. Сәйкесінше, егер кәсіпорын түрінің 12 бұйымын және түрінің 18 бұйымын дайындаса, онда ол теңгеге тең максимальді пайда табады.
Мысал 8.

.

болғандағы функциясының максимумы мен минимумын табу.
Шешімі. Шешім көпбұрышын құрамыз. Бұл үшін шектеу жүйесінің теңсіздігінде және айнымалылар теріс емес болғандағы теңсіздік белгілерін дәл теңдік белгілеріне алмастырамыз:

Алынған түзулерді құрып сәйкесті жарты жазықтықтар мен олардың қиылыстарын табамыз (8 сурет).
8 суреттен көрініп тұрғандай есеп шешімінің көпбұрышы үшбұрышы болып табылады. Осы үш бұрыш нүктелерінің координаттары есеп шектеу жүйесінің теріс еместігі мен теңсіздік шартын қанағаттандырады. Ендеше, егер бұрышының нүктелері арасынан функциясы максимальді және минимальді мән қабылдайтынды тапса есеп шешілетін болады. Бұл нүктелерді табу үшін түзуін және векторын құрамыз.
Берілген түзуді векторының бағытында өз-өзіне паралель жылжыта отырып есеп шешімінің көпбұрышымен оның соңғы ортақ нүктесі нүктесі екенін көреміз. Ендеше осы нүктеде функция максимальді мән қабылдайды. - І және ІІ түзулер қиылысының нүктесі болғандықтан оның координаттары осы түзулердің теңеулерін қанағаттандырады:

8 сурет

Теңеудің осы жүйесін шеше отырып аламыз. Осылайша, функцияның максимальді мәні.
Есептің мақсатты функциясының максимальді мәнін табу үшін түзуді векторы бағытына қарама-қарсы бағытқа жылжытамыз. Бұл жағдайда 6 суретінен көрініп тұрғандай түзудің шешім көпбұрышымен ортақ соңғы нүктесі нүктесі болып табылады. Сәйкесінше, бұл нүктеде функциясы минимальді (ең аз) мәнді қабылдайды. нүктесінің координаттарын анықтау үшін теңдеу жүйесін шешеміз

мұндағы .Айнымалылардың табылған мәнін мақсатты функцияға ауыстып қоя отырып аламыз.
Мысал 9. функцияның

.

болғандағы максимальді мәнін табамыз.
Шешімі. Жоғарыда қарастырылған есептерге қарағанда бастапқы есепте шектеулер теңдеу түрінде берілген.Сондықтан белгісіздер саны беске тең. Сондықтан берілген есепті белгісіздердің саны екеуіне тең болатындай есепке келтірген жөн. Қарастырылған жағдайда мұны негізгі формада жазылған бастапқы есептен стандартты формада жазылған есепке өту арқылы жасауға болады.
Жоғарыда (1 параграфты қарау) функцияның

.

болғандағы максимальді мәнін табудан тұратын есепке арналған, негізгі формада жазылған бастапқы есеп көрсетілді.
Бастапқы есептің мақсатты функциясынан айнымалылары олардың мәндерін шектеу жүйесінің сәйкесті теңдеуіне қою арқылы алынып тасталды.
Алынған есеп шешімінің көпбұрышын құрамыз (9 сурет). 9 суреттен көрініп тұрғандай есептің мақсатты функциясы максимальді мәнді І және ІІ түзулер қиылысындағы нүктесінде қабылдайды. Шектес түзулердің әрқайсысы бойында сәйкесті теңсіздікке өту кезінде алынып тасталған айнымалылардың бірінің мәні нольге тең. Сондықтан соңғы есеп шешімінің көпбұрышынан алынған ұштың әрқайсысындағы кем дегенде бастапқы есептің екі айнымалысы нольдік мәнді қабылдайды.

9 сурет

Сөйтіп, нүктесінде және болады. Бұл мәндерді бастапқы есептің шектеу жүйесінің бірінші және екінші теңдеулеріне ауыстырып қоя отырып екі теңдеу

жүйесін аламыз, оларды шеше отырып табамыз.
Табылған және мәндерін бастапқы есептің шектеу жүйесінің үшінші теңдеуіне ауыстырып қоя отырып, 14-ке тең айнымалының мәнін анықтаймыз.
Сәйкесінше, қарастырылатын есептің тиімді жоспары болып табылады. Мұнымен қоса мақсатты функция мәнінің жоспарында бар.
Мысал 10. функцияның

болғандағы максимальді мәнін анықтаудан тұратын есеп шешімін табамыз.
Шешімі. Мысал 6-есебін шешу барысында көрсетілгендей бастапқы есеп стандартты формада келесідей жазылуы мүмкін: функциясының

болғандағы максимумын табамыз.
Алынған есеп екі белгісіден тұрады. Сәйкесінше, оның шешімін сызықтық программалау есебінің геометриялық түсіндірілуін пайдалана отырып табуға болады. 10 суретінен мақсатты функциясы максимальді мәнді І және ІІ түзулері қиылысатын В нүктесінде қабылдайтыны көрінеді. Сәйкесінше, осы нүктелердің координаттарын сызықтың теңдеу

жүйесінен табуға болады.
Бұл жүйені шеше отырып, және аламыз. Алынған және мәндерін бастапқы есептің шектеу жүйесі теңдеуіне ауыстырып қоя отырып аламыз.
Осылайша, бастапқы есептің тиімді жоспары болып табылады. Мұнымен қоса жоспарда .

10 сурет

3 Сызықтық программалау есептерінің шешімін табу

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

функцияның максималды мәнін табу қажет,

болса.
Мұндағы және - берілген тұрақты сандар және ).
Берілген есептің векторлық формасы мынадай түрде болады:

(22)

максимум функциясын табу қажет, егер

(23)

, (24)

болса.
Мұндағы,

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

.

болсын делік.
. - векторлары бірдей болғандықтан, және ,ал болады.
Теорема 5. (тірек жоспардың тиімділік белгісі). Егер кез келген үшін болса, (22) - (24) есебінің тірек жоспары болып табылады.
Теорема 6. Егер қандай да бір үшін болса және сандарының ішінде оң сандар болмаса, (22) - (24) есебінің (22) мақсатты функциясы оның жоспарларының көбінде шектелмеген.
Теорема 7. Егер (22) - (24) есебінің тірек жоспары өзгешеленбеген және болса, алайда сандарының ішінде оң сандар (барлығы емес) болса, онда болатындай тірек жоспар болады.
Жүйеленген теоремалар табылған тірек жоспардың тиімді - тиімсіздігін тексеруге және жаңа тірек жоспарға көшудің мақсаттылығын анықтауға мүмкіндік береді.
Есептің шарттары мен бастапқы тірек жоспарды анықтағаннан кейін алынған алғашқы мәндерді 3-кестедегідей етіп жазсақ, тірек жоспардың тиімділігін зерттеу, сондай-ақ, мұнан кейінгі есептеу үрдісін жүргізу ыңғайлы болады.
Осы кестенің бағанына индекстері осы базис векторларының мәндерімен бірдей болатын белгісіз мақсатты функциядағы коэффициенттер жазылады.
бағанына бастапқы тірек жоспардың оң компоненттері жазылады да, есептеулер нәтижесінде тиімді жоспардың оң компоненттері алынады. векторларының бағандары осы векторлардың берілген базистің векторлары бойымен жіктелу коэффициенттерінен көрініс береді.
3-кестедегі алғашқы жолдар есептің бастапқы мәндерімен анықталады, ал -ші жолдың көрсеткіштерін есептеп шығарады. векторы бағанының осы жолына мақсатты функцияның берілген тірек жоспар кезінде қабылдайтын мәні, ал векторының бағанына мәні жазылады.
мәні векторының векторына скалярлық көбейтіндісі ретінде табылады:

.

мәні векторының векторына скалярлық көбейтіндісіне тең:

.

3-кестені толтырғаннан кейін бастапқы тірек жоспардың тиімділігін тексереді. Ол үшін -ші элементтерін қарастырады. Нәтижесінде төменде берілген үш жағдайдың бірі орын алуы мүмкін:
1) үшін ( болғанда) . Сондықтан да бұл жағдайда 1-ден -ге дейінгі барлық үшін болады;
2) кейбір үшін және осы индекске сәйкес келетін барлық шамалар болады.
3) -дің кейбір индекстері үшін және осындай -дің әрқайсысы үшін сандарының бірі оң болады.
Бірінші жағдайда тиімділік белгісі негізінде бастапқы тірек жоспар тиімді болып табылады. Екінші жағдайда мақсатты функция жоспарлардың көбінде жоғарыдан шектелмеген, ал үшінші жағдайда мақсатты функцияның мәні ұлғаятын бастапқы жоспардан жаңа тірек жоспарға көшуге болады. Тірек жоспардың бірінен екіншісінен көшу бастапқы базистен векторларының бірін алып тастап, оған басқа жаңа вектор енгізу арқылы жүзеге асырылады. Базиске енгізілетін вектор ретінде болатын индексі бар векторының кез келгенін алуға болады. Мысалға, және базиске векторын енгізу қажет болсын.
Базистен алып тастауға жататын векторды анықтау үшін, барлық үшін табады. Бұл минимумға болғанда қол жеткіземіз. Сонда векторы базистен алынып тасталады, ал саны шешуші элемент деп аталады. Қиылысында шешуші элемент орналасқан баған мен жол бағыттаушы деп аталады.
Бағыттаушы жол мен бағыттаушы бағанды белгілен соң, жаңа тірек жоспар мен жаңа тірек жоспарға сәйкес келетін жаңа базис векторы арқылы векторларының орналасу коэффициенттерін табады. Жордан-Гаусс әдісін пайдалансақ, мұны іске асыру оңай. Сонымен қатар, жаңа тірек жоспардың оң компоненттері

(25)

формулалары бойынша,

3 кесте

Ба-зис

1
2

r

m

1
0

0

0
0
1

0

0

0
0

1

0

0
0

0

1

0
0

0

0

4 кесте

Ба-зис

1
2

r

m

1
0

0

0
0
1

0

0

0
0

0

1

0
0

0

ал жаңа тірек жоспарға сәйкес келетін жаңа базис векторы арқылы векторларының орналасу коэффициенттері

(26)

формулалары бойынша есептелетінін көрсетуге болады.
(25) және (26) формулаларға сәйкес және есептегеннен кейін олардың мәндерін 4-кестеге енгізеді. Осы кестенің -ші жолының элементтері я

(27)

(28)

формулалары бойынша, я оларды анықтау негізінде есептелінеді.
-ші жолының элементтері табудың екі тәсілінің де болуы жүргізілген есептеулердің дұрыстығын бақылауды жүзеге асыруға мүмкіндік береді.
(27) формуласынан тірек жоспардың бірінен екіншісіне көшкенде абсолютті шамасы бойынша саны максималды болатын индексі бар векторын базиске енгізу анағұрлым мақсатты екендігін көруге болады. Алайда есептеу үрдісін қысқарту мақсатында алдағы уақытта базиске енгізілетін векторды теріс сандарының максималды абсолютті шамасына сүйене отырып анықтайтын боламыз. Егер мұндай сандар бірнеше болса, онда базиске берілген сандарымен анықталатын сандарының максималды мәніндегідей индексі бар векторды енгіземіз.
Сонымен, тірек жоспардың бірінен екіншісіне көшу симплексті -кестенің бірінен екіншісіне көшуге сай келеді. Жаңа симплексті кестенің элементтерін (25) - (28) рекурентті формулалар көмегімен де, осы формулалардан шығатын ережелер бойынша да есептеуге болады. Мұндай ережелер мыналардан тұрады.
Базиске ... жалғасы

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