Кириш. Чизиқли программалаштириш (1-маъруза машғулоти)

тўғри чизиқлар билан чегараланган кўпбурчакни ясалади. Чизиқли функцияни ихтиёрий ўзгармас с0 сонга тенг деб олиб

• тўғри чизиқ ясалади. Бу тўғри чизиқни N(c1 ,c2) вектор йўналишда ёки унга тескари йўналишда ўзига параллел суриб бориб, қавариқ кўпбурчакнинг чизиқли функцияга энг кичик қиймат берувчи четки нуқтаси аниқланади.

Берилган

• Берилган
• (1 )
• x10, x20,..., xm0, xm+10,...., xn0 ( 2)
• ymin=c1x1+ c2x2+.... +cnxn

• 1.Симплекс усулнинг асосий ғояси.

• чизиқли программалаштириш масаласининг режалари мавжуд ва улар хосмас деб фараз қиламиз, яъни барча bi>0, i=1,m. Масаланинг X=(x1, x2,...,xm) таянч режаси ва унга мос келувчи ўзаро чизиқли боғлиқ бўлмаган P1, P2,..., Pm векторлар системаси маълум бўлсин. У ҳолда
• x1P1+x2P2+...+xmPm=P0 ( 3)
• ва y0=c1x1+ c2x2+.... +cnxn (4)
• Умумий ҳолда таянч режани топиш учун масаланинг чегаравий шартларидан ташкил топган чизиқли системани Жордан-Гаусс усулини қўллаб, таянч режа ва унга мос мақсад функция аниқланади.

Симплекс усул алгоритми  

• Берилган бошланғич режадан бошлаб таянч режалар кетма-кетлигини ҳосил қилиб бориб, жараённи оптимал ечим топилгунча давом эттириш мумкин. Фараз қилайлик, X= (x1,x2,...,xm)
• Масаланинг бошланғич таянч режаси, P1, P2,...,Pm шу режага мос келувчи ўзаро чизиқли боғлиқ бўлмаган векторлар системаси бўлсин. Бу векторлардан ташкил топган (P1, P2,...,Pm) матрицани B билан белгилаймиз. У ҳолда BX=P0 . Бундан
• X=B-1P0 ва Xj=B-1Pj
• келиб чиқади. Бу ерда Х=(х1, х2,...,хm) (хi0), xj=(х1j, х2j,...,хmj)-вектор устунлар.

• Симплекс жараённи бошлашдан аввал масаланинг векторларини қуйидагидек гуруҳлаймиз:
• (Р0| P1, P2,...,Pm | Pm+1,...,Pn)
• ёки
• (Р0|В| Pm+1,...,Pn) ( 7)
• Элементлари айрим қисмлардан иборат бўлган ( 7) матрицани В-1 га кўпайтирамиз ва қуйидагига эга бўламиз:
• (В-1 Р0| В-1 В| В-1 Pm+1,..., В-1 Pn) ёки (X|Jm|Xm+1,...,Xn)
• Сўнгра ҳар бир j=1,n учун yj-cj ни ҳисоблаймиз.

• Агар барча j лар учун yj-cj0 бўлса, топилган таянч режа оптимал режа бўлади. Агар yj-cj айирма баъзи j лар учун мусбат бўлса, топилган таянч режа оптимал режа бўлмайди, бу режани оптимал режага яқин бўлган бошқа режа билан алмаштириш керак бўлади. Берилган масалада дастлабки P1, P2,...,Pm векторлар m ўлчовли вектор фазодаги базисни ташкил қилсин, яъни В=( P1, P2,...,Pm)= I m
• бўлсин, бу ерда I m- m ўлчовли бирлик матрица. Бу ҳолда В-1В=I m бўлганлиги сабабли Х=Р0 ва Хj=Рj бўлади.

• Чизиқли системаси АХ=В кўринишда берилган масала учун хi=вi, xij=aij деб қабул қиламиз. Уj -j вектор- устунни С вектор -устунга скаляр кўпайтмасидан иборат, яъни
• у0=

• Yi=

• у0 ва yj-cj ларни жадвалнинг m+1 қаторидаги тегишли устунларга жойлаштирамиз. Базис векторлар учун ҳар доим yj=cj=0 бўлади. Агар yj-cj0 (j=1,n) бўлса, Х=(х1, х2,...,хm)=(b1, b2,...,bm) оптимал режа бўлади. Бу режадаги чизиқли функциянинг қиймати у0 га тенг.

• , j=1,n.