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

Айталық, (3.1-3.3) сызықтық программалу есебі өқойылсын. (3.1) жүйенің теріс емес шешімдерінің ішінен минимумделген (3.2) мақсатты функцияның шешімін табу керек.

Берілген шектеулі жүйе қандайда бір r белгісізінің айнымалылары басқалары арқылы өрнектелген түрде түрлендіріледі деп есептейік:

(1)

Мұндағы, (2)

х₁, х_2,...,х_r белгісіздерді базисті белгісіздер, ал қалғандары базисті емес немесе бос белгісіздер деп аталады.

Белгісіздердің жиынын базис Б={х₁, х_2,...,х_r } деп атаймыз.

f мақсатты функциясы болса, осы функцияны бос белгісіздер арқылы (1) түрдегі өрнектерді берілген мақсатты функцияның базисті белгісіздердің орнына қойып былайша көрсетуге болады:

(3.6)

Х_i(і=r+1, r+2,…,n) барлықұ боос белгісізедрі нолге тең деп алайық, онда(3.4) жүйедегі х₁₌ болады. (3.3) теріс еместігі жөніндегі шарттардың орындалуынан (3.5)мағынансын арттыратын (3.4) жүйенің бір шешімін алдық:

( ₁, ₂,…, _r,0,0…,0)

Осы шешім мүмкін болатын шешім деп аталады.

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

болғанда ғана

Нәтижесінде f функциясының минимумын беретін базиске өтуге немесе есептің шешімі жоқ екендігін анықтауға болады. Б базисінен бір белгісізді алып тастап, оның орнына қандай да бір бос белгісізді енгізу арқылы жаңа Б^’ базисіне өту орындалады. Бұл түрлендірулер (1) жүйенің аусуымен байланысты. Жаңа базис оған сәйкес базистік шешім және бұл шешімге сәйкес мақсатты функцияның мәні, осылардың барлығы түрлендірулердің әр кезеңіне сай шешімі болады.

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

Мысал 3.2.1.

F=3+x₄-2x₅ мақсатты фунекция және (3.4) түрінде шектеулі жүйе берілген:

Х₁ =2+x₄-x₅

х₂=-2x₂-x₅, (3.8)

х₃₌1-x₂+2x₅

(3.7) функцияны минмумдайтын жүйенің теріс емес шешімін табу керек. Х₁,Х₂,Х₃белгісіздері (3.8) жүйесінде базис құрайды x₄=x₅=0 дегенді қабылдапмақсатты) функцияның мәнін f=3 болатын сәйкес базистік шешімін аламыз:

(2;7;1;0;0)

f-тің мәні х₄-тің мәнін азайтқанын немесе х₅-тің мәнін көбейткеннен кішірейеді. Х_{4 –}ті азайту мүмкін емес, себебі х₄=0 және бұл (3.3) теріс еместігі жөніндегі шартты бұзар еді. Әйткенмен х₅ –тің мәні бақылаусыз өзгерту Х₁,Х₂,Х₃ базистік білгісіздерінің мәнін көрсетеді. Бұл (3.8)-ге қатер болмайды, бірақ бірінші және екінші теңдіктердің мәнін тек 2-ге дейін үлкейтуге болатынын көрсетеді.

Х₅ =2 деп алайық, (3.8) жүйені пайдаланып және х₄ =0 ескеріп, мақсатты функцияның f=-1 мәні болатын жаңа шешімді аламыз.(0;1;11;0;2).

Енді жаңа базисті Х₂,Х,Х₅ белгісіздері құрайды. (Х₁ белгісі Х₅ –тің орнына бос белгісіздерге өтеді). (3.7) жүйені сәйкесінше өзгерту үшін, бірінші теңдіктен Х₅ =2-х₁+х₄ –рнектеп аламыз7 Соден кейін бұны басқа теңдіктер мен мақсатты функцияныңөрнегіне алып барып қоямыз.

Жаңа мақсатты функция

f=-1-2x₁-x₄ (3.10)

мен x₁=1+3x₁-5x₄

x₂=5-2x₁+x_4, (3.9)

X₃=2-x₁+x₄

Шектеулі жүйені алдық.

Осымен процестің бірінші кезеңі аяқталды. Енді х₄ белгісінің мәнін үлкейту арқылы f- тің мәнін кішірейтуге тырысамыз. Сонымен бірге (3.9) жүйенің бірінші теңдігінен x₄ –тің мәнін көп дегенде 0,2 –ге дейігн үлкейтуге болады. Енді x₁=0 деп, x₄ = 0,2 жаңа шешімін аламыз:

(0;0;2,2;0,2; 2,2) (3.11)

Мүндағы f=-1,2 болады. Жаңа базисті x₄ Х₂,Х₃,Х₅ белгісіздері құрайды.)3.10) мақсатты функцияның өрнегіндегі x₁ –ді алып тастап, оның орнына x₂ енгіземіз. (3.9) теңдеулер жүйесінің бірінші теңдеуінен x₄=0.2+0.6x₁+0.2x₂ аламыз, бұл f функциясы үшін жаңа өрнекті береді:

f=-1,2 +1.4x₁+0.2x₂

Бұл өрнектен f-тің мәні тек қана x₁ және x₂ белгісіздерінің азайту жолымен ғана кішірейте алаиындығын көреміз. (3,11) шешімнен x₁ = x₂ =0 және бұларды кішірейту теріс еместігі жөніндегі шарттфң бұзылуына әкеледі.

Сонымен есеп шеілді, яғни мақсатты функцияныңмәнін минимумдайтын (3.11) шешімі алынды.

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

Осындлай жағдайларға алып келетн шарттарды анықтау үшін симплекс әдісін жалпы түрде қарастырамыз.