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

www.arxiv.uz

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

Режа:

1. 
   Чизиқли дастурлаш масаласининг умумий қўйилиши.
   
2. 
   Чизиқли дастурлаш масаласининг турли формада ифодаланиши.
   
3. 
   Чизиқли дастурлаш масаласининг мумкин бўлган ечимлари. Таянч ечим.
   
4. 
   Тенг кучли алмаштиришлар.
   
5. 
   Мумкин бўлган ечимлар тўпламининг қавариқлиги.
   

Чизиқли дастурлаш масаласи умумий ҳолда қуйидагича ифодаланади:

x₁ ³ 0, x₂ ³ 0, …, x_n ³ 0, (2)
Y_min(max) = c₀ + c₁x₁ + c₂x₂+ … + c_nx_n (3)

(1) ва (2) шартларни қаноатлантирувчи номаълумларнинг шундай қийматларини топиш керакки, улар (3) чизиқли функцияга минимал (максимал) қиймат берсин. Масаланинг (1) ва (2) шартлари унинг чегаравий шартлари деб, (3) чизиқли функция эса масаланинг мақсади ёки мақсад функцияси деб аталади.

Масаладаги барча чегараловчи шартлар ва мақсад функция чизиқли эканлиги кўриниб турибди. Шунинг учун ҳам (1)–(3) масала чизиқли дастурлаш масаласи деб аталади.
Конкрет масалаларда (1) шарт тенгламалар системасидан, «³» ёки «£» кўринишдаги тенгсизликлар системасидан ёки аралаш системадан иборат бўлиши мумкин. Лекин кўрсатиш мумкинки, (1)–(3) кўринишдаги масалани осонлик билан қуйидаги кўринишга келтириш мумкин.



x₁ ³ 0, x₂ ³ 0, …, x_n ³ 0, (5)
Y_min = c₀ + c₁x₁ + c₂x₂+ … + c_nx_n (6)
(4)-(6) кўриниш чизиқли дастурлаш масаласининг каноник кўриниши деб аталади.
(4)–(6) масалани векторлар ёрдамида қуйидагича ифодалаш мумкин: