5 басылым 18. 09. 2013 ж беттің -сі

жүктеу 7,13 Mb.

бет	43/89
Дата	05.02.2018
өлшемі	7,13 Mb.
	#8525

1 ... 39 40 41 42 43 44 45 46 ... 89

Ескерту

Теорема. Егер кеңейтілген есептің (1.4)-(1.6) тиімді шешіміндегі жасанды айнымалылар нөлге тең болса, онда алғаш берілген есептің (1.1)-(1.3) тиімді шешімі де сол болады.

Осы теореманың тұжырымы бойынша алдымен кеңейтілген есеп (1.4)-(1.6) есебі симплекс тәсілімен шешілуге тиіс және алған шешімдегі жасанды айнымалылар нөлге тең болуы керек. Егер жасанды айнымалының ең болмағанда біреуі нөлге тең болмаса, онда ол есептің тиімді шешімі болмайды.

Егер кеңейтілген есептің алғашқы тірек шешімін (1.7) қарастырсақ, онда оның мақсат функциясының мәні былайша табылады:

ал

мәндері:

(1.8)

Осы формула бойынша

екі бөлімнен тұрады: біріне М кірсе, екіншісі бос болады. Сондықтан кеңейтілген есепті шешу кезінде симплекс кестесінде екі индексті жол болады: m+1-ге

-дың бос мүшесі, ал М-нің коэффициенті m+2-ге жазылады.

Кеңейтілген есепті шешу кезінде итерация m+2-ші жол бойынша анықталады. Ол итерация екі түрлі жағдайға дейін қайталанады:

а) барлық жасанды айнымалылар базистен түгел шығарылғанша;

б) жасанды айнымалылар түгел шығарылмай, бірақ m+2-ші жолда теріс элементтер болмағанға дейін;

Егер а) жағдайы орындалса, онда итерация m+1-ші жол бойынша жалғастырылады.

Егер б) жағдайы орындалса, онда да екі түрле вариантболуы мүмкін:

І. егер m+2-ші жолдың В₁ орналасқан тік жолының элементі теріс болса, онда берілген есептің шешуі болмайды;

ІІ. егер ол нөлге тең болса, онда берілген есептің табылған тірек шешімі аайныған болады және базисте ең болмағанда бір жасанды айнымалы болады.

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

1. кеңейтілген есепті құрастыру (1.4)-(1.6)

2. кеңейтілген есептің тірек шешімін табу

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

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

Ескерту: Егер берілген есепте бірлік векторлар бар болса, олар базиске енгізілуге тиіс.

Мысалдар қарастырайық.

Бақылау сұрақтары:

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

жүктеу 7,13 Mb.

Достарыңызбен бөлісу:

1 ... 39 40 41 42 43 44 45 46 ... 89