Чизиқли дастурлаш усули асосий масаласининг қўйилиши

Чизиқли дастурлаш усули асосий масаласининг қўйилиши.
Ҳар битта ишлаб чиқариш жараёнини математик формулалар билан ифодалаш, ёзиб чиқиш мумкин. Масалан, бир нечта j=1,2,…,n тармоқларда (фолият соҳасида, бозор сегментларида), i=1,2,....,m корхоналар бор. Уларнинг ҳар бири турли хилдаги маҳсулотлар ишлаб чиқарадилар, масалан, x_ij. Маҳсулотлардан олинадиган ўртача даромат С_ij билан белгилаймиз. Унда ялпи даромад с_ijх_ij га тенг бўлади. У даромадни албатта иложи борича кўпроқ олиш керак, яъни с_ij х_ij max га интилиш лозим.
Бунга мос мақсад функцияси:
(1)
Бу мақсадга етиш учун бир неча шартлар бажарилиши керак:

1. 
   ишлатиладиган ресурслар корхонадаги ресурслар бор заҳирасидан ошмаслиги к керак:
   

2)
бу ерда a_ij - ҳар битта маҳсулотга i-корхонада j-тармоқда кетадиган сарфлар меъёрларидир.

2. 
   ўзгарувчиларнинг номанфийлик шартлари:
   

x_ij 0.
Буларни ҳисобга олиб, ушбу чизиқли дастурлаш усулининг масаласини ёзиб чиқамиз:
, (1)
_, (2)
x_{i j} 0. (3)
Умуман, чизиқли дастурлашнинг умумий масаласи иккита усул ёрдамида ечилиши мумкин. Булардан биринчиси – симплекс усул ёки вариантларни (режани) кетма-кет яхшилаш усулидир. Иккинчиси усул – бу тақсимлаш усулидир, бошқача айтганда, нобаланслари кетма-кет қисқартириб бориш усулидир. Чизиқли дастурлашнинг бу усули, асосан, транспорт масаласини ечишда ишлатилади. Тақсимлаш усули юк ташишни самарали ташкил этишда тарихан биринчилардан қўлланилган.
Агар ноьмалум ўзгарувчилар m, шартлар – тенгсизликлар n га тенг бўлса, унда масаланинг битта оптимал ечими бор.
Кўпинча m<n бўлган тенгламалар тизими кўрилади. Унда масаланинг бир нечта ечими бўлади. Бизнинг асосий вазифамиз – бир нечта ечимлар орасидан оптимал ечимини топишдир.