2-машғулот. Чизикли программалаштириш масаласини ечишининг симплекс–усули

Аосий формулалар

Қаралаётган масаланинг бирор базис плани берилган деб фараз қиламиз. Бундан ташқари, барча базис планлар бузилмаган бўлсин. Аниқлик учун нинг дастлабки та координатаси базис координатаси бўлсин, яъни , ; , ; – базис матрица ва эса мақсад функциянинг базис планга мос келувчи қийматидир. Базис план таърифига биноан матрица мавжуд.

векторнинг базисидаги i-координатасини билан белгилаймиз, яъни . Бунда вектор масаланинг плани бўлгани учун . Мақсад функциясига га қараганда каттароқ қиймат берувчи ва дан битта базис вектори билан фарқ қилувчи бошқа базис план излаймиз. Фараз қилайлик, базисдаги векторни (базисга кирмайдиган) га алмаштириш керак бўлсин. Бунинг учун
; ( ), ,
формулалардан фойдаланамиз. Бу формулалар симплекс-усул учун асосий формулалар деб аталади. элементни ( ) ҳал қилувчи элемент деб аташади. Асосий формулаларни тўғри тўртбурчак (баъзи адабиётларда, учбурчак) қоидаси деб ҳам аташади.
А
сосий формулаларга асосан
, , , бунда ( ) – b векторнинг олдинги базисдаги координаталари, яъни , . вектор базис план бўлиши учун , , , , бўлиши керак. Шундай қилиб, 1) ва 2) шартлар бажарилса векторни га алмаштириш йўли билан янги базис ҳосил қилиш мумкин.
Энди янги план учун мақсад функциясининг қийматини ҳисоблаймиз:

,
бунда ; . бўлгани учун бўлади, агарда бўлса. га векторнинг баҳоси, векторга эса баҳолар вектори деб аталади.
Таъкидлаш керакки, барча базис векторлар учун баҳолар нолга тенг.

3.