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

2-машғулот. ЧИЗИКЛИ ПРОГРАММАЛАШТИРИШ МАСАЛАСИНИ ЕЧИШИНИНГ СИМПЛЕКС–УСУЛИ

Режа:

1. 
   Базис план тушунчаси.
   
2. 
   Асосий формулалар
   
3. 
   Теоремалар Симплекс-усул алгоритми
   
4. 
   Симплекс-усулни жадваллар ёрдамида қўллаш.
   

1. 
   Базис план тушунчаси
   

Чизиқли программалаштириш масаласи каноник шаклда берилган бўлсин ( , ,..., ):

,

.
Уни ушбу кўринишда ёзамиз , , . Фараз қилайлик, матрицанинг ранги m га (яъни тенгламалар сонига) тенг бўлсин.
Чизиқли программалаштириш масаласининг x плани унинг базис плани деб аталади, агар унинг (n-m)та координаталари нолга тенг бўлиб, қолган m та координаталарига мос келувчи векторлар чизиқли боғланмаган системани ташкил қилса.
Мисол.

Бу мисолда m=2, n=4, , , , , .
, ва векторлар бу масаланинг планлари эканлигини осонликча пайқаш мумкин. планда , бўлиб, ва ларга мос келувчи ва векторлар чизиқли боғланмаган. Шунинг учун базис пландир. ҳам базис пландир. Лекин – базис план эмас.
Чизиқли программалаштириш масаласининг базис плани бузилмаган дейилади, агар унинг мусбат координаталари m та бўлса, бузилган дейилади, агар унинг мусбат координаталари сони m дан кичик бўлса.
Юқоридаги мисол учун – бузилмаган базис план, эса бузилган базис пландир.
Исботлаш мумкинки, x вектор чизиқли программалаштириш масаласининг планлари тўпламининг фақат ва фақат кўпёқлининг учи бўлсагина унинг базис плани бўлади. Демак, планлар тўпламининг (кўпёқлининг) бир учидан бошқа учига ўтиш бир базис пландан бошқа базис планга ўтишни билдиради.

2.