Сызықытық программалау Модель ұғымы. Модельдеудің түрлері
Сызықтық программалау есебін жазу формалары
жүктеу/скачать 349.97 Kb.
|
- Бұл бет үшін навигация:
- 7. Сызықтық программалау есебін графикалық әдіспен
| 6. Сызықтық программалау есебін жазу формалары
Егер сызықтық программалау есебінің барлық айнымалылары теріс еместік шартты қанағаттандырса және (7) шектеулер жүйесі тек қана теңсіздіктерден тұрса, онда сызықтық программалау есебі стандартты немесе симметриялы деп аталады. Егер сызықтық программалау есебінің барлық айнымалылары теріс еместік шартты қанағаттандырса және (7) шектеулер жүйесі тек қана теңдіктерден тұрса, онда сызықтық программалау есебі канондық немесе негізгі деп аталады. Егер сызықтық программалау есебінің барлық айнымалылары теріс еместік шартты қанағаттандырса және (7) шектеулер жүйесі теңдеулерден және теңсіздіктерден тұрса, онда сызықтық программалау есебі жалпы түрде берілген деп аталады. Сызықтық программалау есебінде кез келген сызықтық программалау есебін канондық түрге келтіруге болады. Айталық, сызықтық программалау есебі стандартты түрде берілсін: Стандартты программалау есебін канондық түрге келтіру үшін шектеулер жүйесіне теріс емес , , …, (теңсіздік берілген қанша шектеу болса, сонша қосымша айнымалылар) қосымша айнымалыларын енгіземіз. Қарастырылып отырған есепте барлық теңсіздіктердің таңбасы « » болғандықтан, қосымша айнымалылар «+» таңбасымен енгізіледі, ал егер теңсіздіктердің таңбасы « » болса, онда қосымша айнымалылар «-» таңбасымен енгізіледі. 7. Сызықтық программалау есебін графикалық әдіспен шығару Екі айнымалымен берілген сызықтық программалау есебін графикалық әдіспен шығаруға болады. , шектеулер жүйесін, теріс еместік шартты қанағаттандыратындай мақсат функциясының экстремумын табу керек. Теорема 1. Екі айнымалымен берілген теңсіздіктер шешімінің жиыны жазықтықты түзуі екі жартыжазықтыққа бөлетін осы түзумен бірге жартыжазықтықтың бірі болады, ал осы түзумен бірге екінші жартыжазықтық теңсіздіктер шешімінің жиыны болады. Сызықтық программалау есебін графикалық әдіспен шығару алгоритмі 1. Жарамды шешімдер облысын құру. жазықтығында жарамды шешімдер облысын құру керек. Ол үшін сызықтық программалау есебіндегі шектеулер жүйесіндегі барлық теңсіздіктерді теңдеу түрінде ( , ) жазамыз да, осы теңдеулердің сәйкес түзулерін тұрғызамыз. Осы түзудің әрқайсысы жазықтығын екі жартыжазықтыққа бөледі. Берілген шектеуді қанағаттандыратын жартыжазықтықты анықтау үшін кез келген нүктені, мысалы, көбінесе координатасы нүктені қарастырған жеткілікті. Егер осы нүкте теңсіздікті қанағаттандырса, онда осы нүкте ізделінді жартыжазықтықта жататынын білдіреді және өзімізге ыңғайлы болу үшін осы жартыжазықтықты белгілейміз. Егер теңсіздік орындалмаса, онда ізделінді жартыжазықтық берілген нүктеге қарама-қарсы орналасқан жартыжазықтық болып табылады да, оны белгілейміз.c 2. Деңгей сызығын тұрғызу. 2.1. Мақсат функциясының градиент-векторын (компоненттері мақсат функциясының айнымалыларының коэффициенттері) тұрғызамыз. 2.2. Жарамды шешімдер облысы арқылы өтетін векторына перпендикуляр деңгей сызығының үйірін тұрғызамыз. 3. Шешімді табу. 3.1. векторының бағытында (минимум есебінде не векторының бағытына қарама-қарсы орналасқан, не ең жақын қашықтықта орналасқан), жарамды шешімдер облысы арқылы өтетін ең алыс қашықта орналасқан деңгей сызығын таңдау керек. Осы деңгей сызығы өтетін облыстың бұрыштық нүктелерін таңдау керек. 3.2. Экстремум нүктелерінің координаталарын және осы нүктелердегі мақсат функциясының мәнін табу керек. Ескерту: Бұл жерде алгоритмнің бірінші қадамына қатысты келесі жағдайлар болуы мүмкін: а) Жарамды шешімдер облысы – құр жиын. Бұл жағдайда шектеулер жүйесінің үйлесімсіздігінен сызықтық программалау есебінің тиімді шешімі болмайды. жүктеу/скачать 349.97 Kb. Достарыңызбен бөлісу:
|