Симплекс әдісі

⇐ ПредыдущаяСтр 2 из 5Следующая ⇒

Сызықтық бағдарлама есебінің оңтайлы шешімдері көпбұрыштың бұрыштық нүетелерімен байланысты. Егер айнымалалар саны n=50,теңсіздіктер саны m=25 болса, онда базистік жоспарлар саны 10¹⁴ болады. Сонда м және н үлкен сан болса, онда барлық негізге алынатын жоспарларды іріктей отырып, оңтайлыны табу өте көп есептеуді қажет етеді. Сондықтан бір негізге алынатын жоспардан екіншіге ауысуға мүмкіндік беретін әдіс болуға тиіс. Осындай әдіс симплекс әдісі деп аталады. Есептеулердің әрқайсысында осы функцияның өткен жоспардағы мәнімен салыстырғанда мақсатты функциядан кем немесе артық мәніне сәйкес келетін жаңа жоспар табылды. Есептеулерді оңтайлы жоспар алынғанға дейін жалғасады. Егер мәселенің оңтайлы шешімі болмаса, онда симплексті әдіс оны есептеу кезеңінде анықтауға мүмкіндік береді.

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

F=C₁X₁+ C₂X₂+… +C_nX_n(5.1)

мына шектеулерде

а₁₁х₁+ а₂₁х₂+... +а_1nхn=В₁

а₂₁х₁+ а₂₂х₂+... +а_2nхn=В₂

.......................................... (5.2)

а_m1х₁+ а_m2х₂+... +а_mnх_n=В_m

мұнда, х_j>=0, (i=1,2,…,m). (5.3)

Шектеу жүйесінің m бірлік векторлары болсын деп ұйғарсақ, онда ол алғашқы m векторлар болады. Осыдан (5.1) – (5.3) есепті алғашқы m векторларға сәйкес түрлендіріп жазамыз:

F=C₁X₁+ C₂X₂+… +C_nX_n_, (5.4)

мына шектеулерде

X₁+a¹₁,_m+1X_m+1+a¹₁,_m+2X_m+2+…+a¹_1.nx_n=B¹₁

X₂+a₂,_m+1X_m+1+a₂,_m+2X_m+2+…+a¹_2.nx_n=B¹₂ (5.5)

_{……………………………………………………………………}

X_m+a¹_m,_m+1X_m+1+a¹_m,_m+2X_m+2+…+a¹_m.nx_n=B¹_m

х_j>=0, j=1,2,…,n. (5.6)

Жүйені (5,5) векторлық формада жазамыз:

x₁A₁+x₂A₂+…+x_mA_m+x_m+1A_m+1+x_nA_n=B (5.7)

А₁, А₂,...,А_m векторлар – m өлшемді кеңістіктің сызықтық тәуелсіз бірлік векторлары. Сондықтан (5.7) өрнекте базистік айнымалылар ретінде x_1,x_2,…,x_m. Ал еркін айнымалылар ретінде x_m+1,x_m+2,…,x_n таңдаймыз, оларды нөлге теңестіріп, базистік айнымалыларды анықтаймыз. Мұнда в_і>=0 (і=1,2,... m), ал А₁, А₂,..., А_mбірлік векторлар екенін ескерсек, онда алғашқы жоспарды аламыз:

Х_о=(х₁=в₁; х₂=в₂;... х_m=в_m; х_m₊₁=0;... х_n=0) (5.8)

Жоғарыдағы (5.7)-ден (5.8) жоспарды ескерсек, төмендегі жіктеу шығады:

x₁А₁+х₂А₂+... + х_m,А_m = В, (5.9)

мұнда А₁, А₂,...А _m векторлар сызықтық тәуелсіз, демек, құрылған жоспар базис болып табылады.

1-анықтама. Еркін белгісіздердің нөл мағыналарына сәйкес келетін шектеулер жүйесінің (5.2) шешімі базистік деп аталады.

Бастапқы негізге алынатын жоспарға (5.9) сүйене отырып, екінші негізге алынатын жоспарды қалай құруға болатынын қарастырамыз. Базиске кірмейтін кейбір вектор үшін, мысалы А_m₊₁, жіктеудегі х_і,_m₊₁ коэффициенттердің ең болмағанда біреуі оң болады деп ұйғарамыз.

Х_1,_m₊₁А₁+Х₂,_m₊₁А₂+... + Х_m_,_m₊₁А_m =А_m₊₁

Жүйенің оң жағы В бөлікті осы айнымалының оң коэффициенттеріне, яғни В_і/а_іm+1 бөлеміз. Сөйтіп, х_m+1 векторы жоспар немесе жаңа базис болып табылады. Есептің m -нен асатын базисі болмайды, сондықтан қазіргі бар базистің біреуін алып тастаймыз. Ол үшін Q=min(в_і/а_i,m+1). таңдаймыз. Осы ең кіші мәні бірінші жолда тұрсын, яғни Q₁=min (в_і/а_1,m+1). Сонда жаңа базистік шешім аламыз Х=(x₂, х_з,...х_m,х_m+1). Бұл базистен Х₁ алып тастау, ал базиске х_m+1енгізу қажет екенін білдіреді. Демек, негізге алынатын жаңа жоспарларды таңдау үшін, базистен шығарылатын және оның орнына базиске енгізілетін айнымалының векторын таңдау кажет.

Оңтайлылық талаптары. СБ есебінің базистік шешімі бар деп ұйғарамыз. Бұл жағдайда есептің математикалық формасы төмендегідей болады:

x₁ А_1+х2А₂+... + х_mА_m = В, (5.10)

х₁С₁+х₂С₂+... + х_mС_m = Ғ, (5.11)

мұнда барлық х_j>=0, j=1,2,...,n., ал Ғ -осы жоспарға сәйкес келетін функцияның мәні. Егер сызықтык функциядағы С_j коэффициенті А_j векторға сәйкес келсе, онда Ғ_j –С_j- оңтайлылық өлшемі немесе сызықтық функцияның бағасы деп аталады.

Оңтайлылық өлшемі бағдарламадан шығарылатын қызметтің құнының сомасына тең болады, одан жоспарға енгізілетін өнімнің бірлігінен түсетін кіріс алынып тасталады. Ғ_j – мақсат функциясының коэффициенттерін шектеулердегі айнымалылардың коэффициенттеріне көбейтіндісінің қосындысына, яғни,

c_j – мақсат функциясының белгісіздер коэффициенттері. Төмендегі теоремалар орын алады.

1-теорема. Егер кейбір А_j векторы үшін төмендегі талап орындалса,

F_j-C_j>=0,

онда Х_о жоспары функцияның максимумы үшін оңтайлы болып табылады.

2-теорема. Егер кейбір А_j векторы үшін төмендегі талап орындалса, онда Х_о жоспары функцияның минимумы үшін оңтайлы болып табылады. Демек, сызықтық функцияның максимумына сәйкес есептің жоспары оңтайлы болу үшін оның бағалары оң болуы қажетті әрі жеткілікті болады. Ал функцияның минимумы үшін оның бағалары теріс болуы қажетті әрі жеткілікті болады.

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

1) базистік шешім құрылады; 2) осы базистік шешім оңтайлылық шартына тексеріледі; 3) егер шарт орындалмаса, онда келесі базистік шешім құрылады да екінші тармаққа көшеді;

4) оңтайлылық талабы орындалғанға дейін есептеулер кайталанады.

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

Дата добавления: 2015-12-18; просмотров: 1; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 123 4 5 Следующая ⇒

Мы поможем в написании ваших работ!