Сызықтық емес бағдарламалау есептерін шешу
жүктеу/скачать 21,88 Kb.
|
Сызықты емес программалау есебі
- Бұл бет үшін навигация:
- 1.8.2 Сызықтық емес бағдарламалау есебін шешудің жалпы жүйесі
- 1.8.3 Графикалық әдіс
|
1.8 Сызықтық емес бағдарламалау есептерін шешу 1.8.1 Есептің қойылуы Екінші тарауда келтірілген есептердің математикалық модельдерін құрастырғанда сызықтық емес бағдарламалау есебін кездестірген болатынбыз. Ал енді осындай есептің жалпы түрін қарастырайық: F ( х1 , х2 , . . ., хn ) max (9.1) Және шектеуші шарттар: g1( х1 , х2 , . . ., хn ) ≤ b1 , 1=1,k (9.2) g1( х1 , х2 , . . ., хn ) ≤ b1 , 1=1,k +1,m (9.3) Мұндағы F және g1 берілген функциялар, хj айнымалы белгісіздер.Ал b1 - тұрақты шамалар. Берілген (9.2) және (9.3) шарттарын қанағаттандыратын және F функциясының максимум (немес минимумын) беретін белгісіздердің хj(j= 1,n) мәндерін табу керек. Егер F және g1(1=1,m) функциялары сызықты болса, онда есеп жоғарыда қарастырылған сызықтық бағдарламалау есебі болады. Шектеуші теңдеулер (9.3) мен теңсііздіктер (9.2) сызықтық емес болғандықтан, бұл есептің анықталу облысы дөңес болмауы мүмкін және мақсат функциясының экстремум нүктелері анықталу облысының ішінде де болуы мүмкін. 1.8.2 Сызықтық емес бағдарламалау есебін шешудің жалпы жүйесі Сызықтық емес бағдарламалау есебін шешу алгоритмі мынадай болады: Алдымен есептің үйлесімді шешімдер облысын берілген шектемелер (9.3) және (9.2) арқылы анықтау керек. Содан кейін келген h санына сәйкес гипербет тұрғызылады: F ( х1 , х2 , . . ., хn ) = h 3. Осы гипербеттің ішінен h max немесе h min сәйкес болатын гипербет табылады; немесе F функциясының анықталу облысында шектелмегендегі анықталады. 4. Ең үлкен h max немесе h min сәйкес келетін гипербет өтетін анықталу облысының нүктесі табылып, ондағы мақсат функциясының мәнін табу керек. 1.8.3 Графикалық әдіс Есептің шешу алгоритмі түсінікті болу үшін алдымен графикалық әдісті қарастырайық. Ол үшін мынадай мысал қарастырайық Есеп. Келесі мақсат функциясының экстремумын берілген шектемелер анықтайтын үйлесімді шешімдер облысынан табу керек. 3 х1 + 2х2 ≥ 12 х1 - х2 ≤ 6 х2 ≤ 4 х1 ≥ 0, х2 ≥ 0 Берілген теңсіздіктер бойынша үйлесімді шешімдер облысын табамыз; ол АВСД төртбұрышы болады: ******
Егер F= h деп алсақ, онда х1 2 + х2 2 = ( )2 , h > 0 центрі 0(0;0) нүктесіне орналасқан радиусы ( ) шеңбер алынады. Әрине, үйлесімді шешімдер облысының 0 нүктесіне ең жақын орналасқан нүктесі үшін h (немесе F) ең кіші мән қабылдайды; ал ең алыс орналасқан нүкте үшін ең үлкен мән қабылдайды. 0 нүктесінен ең алыс нүкте бірден анықталады; ол В нүктесінің координаттары - келесі жүйені шешу арқылы табылады: х1 - х2 = 6 х1 = 10 х2 = 4 → х2 = 4 F max = 116 Ең жақын нүктені табу үшін 0 нүктесінен 3х1 + 2 х2 = 12 түзуіне дейінгі қашықтықты тапсақ жеткілікті: h min =12/ , ал ол Е нүктесінің координаттары былайша табылады: 3х1 + 2 х2 = 12 х1 = 36/13 2х1 - 3 х2 = 0 → х2 = 24/13 F min = 144/13 Cонымен, есептің шешуі: F max ( 10; 4 ) = 116; F min ( 36/13; 24/13 ) = 144/13. жүктеу/скачать 21,88 Kb. Достарыңызбен бөлісу:
|