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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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