Суньий базис усули

8-мавзу. Чизиқли дастурлаш назарияси асослари 4-ma’ruza rejasi 7. Суньий базис усули

Юқорида биз, чизиқли дастурлаш масаласининг бошланғич таянч ечими мавжуд ва бошланғич ечимни тузиш мумкин бўладиган m-ўлчовли бирлик матрица масала шартида қатнашади деб фараз қилдик. Бу бирлик матрица ёрдами билан оптимал ечимга ўтишга ёрдам берадиган ечимни тузиш мумкин. Агар чизиқли дастурлаш масаласининг чегаравий шартлари АХ=В кўринишда берилган бўлса, қўшимча ўзгарувчилар киритиб, тўғридан-тўғри симплекс усул алгоритмидан фойдаланиш мумкин.

Юқорида биз, чизиқли дастурлаш масаласининг бошланғич таянч ечими мавжуд ва бошланғич ечимни тузиш мумкин бўладиган m-ўлчовли бирлик матрица масала шартида қатнашади деб фараз қилдик. Бу бирлик матрица ёрдами билан оптимал ечимга ўтишга ёрдам берадиган ечимни тузиш мумкин. Агар чизиқли дастурлаш масаласининг чегаравий шартлари АХ=В кўринишда берилган бўлса, қўшимча ўзгарувчилар киритиб, тўғридан-тўғри симплекс усул алгоритмидан фойдаланиш мумкин.

Амалда учрайдиган кўп чизиқли дастурлаш масалалари ечимга эга бўлган ҳолда бирлик матрицани ўз ичига олмайди. Бундай масалаларни ечиш учун «сунъий базис вектор» усул қўлланилади.

Агар масаланинг шартларида ўзарo эркли бўлган m та бирлик вектoрлар (базис вектoрлар) қатнашмаса, улар сунъий равишда киритилади. Масалан, қуйидаги кўринишдаги масала берилган бўлсин:

Агар масаланинг шартларида ўзарo эркли бўлган m та бирлик вектoрлар (базис вектoрлар) қатнашмаса, улар сунъий равишда киритилади. Масалан, қуйидаги кўринишдаги масала берилган бўлсин:

а11x1 + а12x2 + ... + а1nxn  b1 ,

а21x1 + а22x2 + ... + а2nxn  b2 , (1)

---------------------------------

am1x1 + аm2x2 + ... + аmnxn  bm.

 

x1 0, x2 0, …, xn 0, (2)

Y = c1x1 + c2x2+ … + cnxn  max. (3)

Бу масалага xn+1 0,xn+2 0,…, xn+m 0 қўшимча ўзгарувчилар киритилса, қуйидаги кенгайтирилган масала ҳoсил бўлади: