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

Сызықтық бағдаpламалау есептерін шешудің негізгі тәсілі симплекс тәсілі болып табылады. Ол тәсілдің авторы АҚШ ғалымы Дж.Данциг және оның оқушылары. Қазіргі кезде ол тәсіілдің әртүрлі алгоритмдері мен түрлері (модификаторы) компьютерді пайдалануға арналып құрастырылған.

Симплекс тәртiбін пайдалану үшін алдымен есеп сызықтық бағдарламалаудың негізгі есебі түрінде жазылуы тиіс. Ол былайша жазылады:
F(Х) =0₁ х₁ + 0₂ х₂ +...+ 0_nх_n  max (4.1)

а₁₁х₁ + а₁₂ х₂ +...+ 0_1nх_n = b₁ (4.2)

x_j0, j= 1,n (4.3)
Сонымен, теңдеулер жүйесін (4.2) қанағаттандыратын, теріс емес мәндер қабылдайтын (4.3) және мақсат функциясының (4.1) максимумына сәйкес келетін х j белгісіздерінің мәндерін табу керек.

Ескерту: егер, мақсат функциясының F(Х) максимумы ізделінсе, онда оның таңбасын айыстыру арқылы максимумды қарастыруға болады.

Егер берілген сызықтық бағдарламалау есебінде теңсіздіктер болса, онда қосымша белгісіздерді енгізу арқылы олар теңдеулерге айналдырылуы тиіс. Мысалы, есепте мынадай теңсііздік болсын делік:
а₁₁х₁ + а₁₂ х₂ +...+ а _1nх_n  b₁ (4.4)
Онда жаңа x_{n +1} айнымалысы енгізіліп, бұл теңсіздік былайша теңдік күйінде жазылады:
а₁₁х₁ + а₁₂ х₂ +...+ а _1nх_n + x_{n +1} = b₁ (4.5)
Ескерту: Енгізілетін жаңа айнымалылар саны теңсііздіктердің санына тең болады.

1. 
   
   
   
   жүктеу/скачать 1,47 Mb.
   
   Достарыңызбен бөлісу: