Суньий базис усули

7-мавзу. Чизиқли дастурлаш назарияси асослари

1. Чизиқли прoграммалаштиришда иккиланма масалалар
2. Иккиланмаликнинг асосий теоремаси 3. Иккиланма масалаларни тузиш усуллари

1. Чизиқли прoграммалаштиришда иккиланма масалалар

Ҳар қандай чизиқли программалаш масаласига бошқа масала, дастлабки масалага иккиланма масала мос келади. Иккиланмалик назарияси чизиқли программалаш масаласини таҳлил қилиш ва сифатли тадқиқ қилишда катта аҳамиятга эга.

Фараз қилайлик, қандайдир корхона ишлаб чиқарувчи корхонанинг хом-ашёсини сотиб олиш ва уларга оптимал

Фараз қилайлик, қандайдир корхона ишлаб чиқарувчи корхонанинг хом-ашёсини сотиб олиш ва уларга оптимал

нарх белгилашни лозим топган бўлсин. Равшанки, сотиб олувчи корхона бу ресурсларга иложи борича кам харажат қилишни, яъни ресурсларга мос равишда қўйилган нархлар минимал бўлишини истайдилар.

Иккинчи томондан ресурсларни сотувчи корхона шу ресурсларни қайта ишлаб уларни сотишдан кўрадиган фойдаси ресурсларни сотишдаги суммадан кам бўлмасликларини ҳоҳлайдилар.

Иккинчи томондан ресурсларни сотувчи корхона шу ресурсларни қайта ишлаб уларни сотишдан кўрадиган фойдаси ресурсларни сотишдаги суммадан кам бўлмасликларини ҳоҳлайдилар.

Маҳсулотни бир бирлигини тайёрлашда S1 ресурсдан a11 бирлик, S2 дан a21 бирлик, Sm дан am1 бирлик сарфланади. Уларнинг нархлари мос равишда u1, u2,…,um. Шунинг учун сотувчи корхонанинг талаби қондирилиши учун ушбу шарт бажарилиши зарур

Маҳсулотни бир бирлигини тайёрлашда S1 ресурсдан a11 бирлик, S2 дан a21 бирлик, Sm дан am1 бирлик сарфланади. Уларнинг нархлари мос равишда u1, u2,…,um. Шунинг учун сотувчи корхонанинг талаби қондирилиши учун ушбу шарт бажарилиши зарур

a11u1+a21u2+…+ am1um ≥ c1 .

Ҳар бир маҳсулот тури учун шунга ўхшаш тенгсизликларни ёзишимиз мумкин.

Дастлабки масала ва унга иккиланма масала орасидаги мосликни ушбу жадвал ёрдамида келтирамиз.

I масала (дастлабки)	II масала (иккиланма)
Ишлаб чиқаришни шундай режасини тузиш керакки, бунда ишлаб чиқарилган маҳсулотни сотишдан кўрадиган фойда энг катта бўлсин.	Шундай нархлар тўпламини топиш керакки, бунда ресурсларга сарфланадиган умумий харажат энг кичик бўлсин.

3-қадам

3-қадам

Биринчи қадамдаги тенгсизликлар ишораси ≤ кўринишда бўлиб мақсад функциянинг максимуми топилади. Бу иккиланма масаланинг кўринишидир. В матрицанинг дастлабки икки сатри иккиланма тенгсизликлардан, учинчи сатри эса иккиланма мақсад функциядан иборат.

Транспонирланган матрица

Иккиланма масала.

Иккиланма масала.

Иккиланма мақсад функция

Чизиқли программалашнинг ўзаро иккиланма масалаларининг хоссалари

1-хосса. Битта масалада чизиқли функциянинг минимуми изланса, бошқасида максимум изланади.

2-хосса. Битта масалада чизиқли функциянинг коэффициентлари иккинчи масаладаги чеклов шартларининг (тенгсизликлар системасининг) озид ҳадларидан иборат бўлади.

3-хосса. Ҳар иккала масала стандарт кўринишда берилган бўлиб, максималлаштириш масаласида барча тенгсизликлар ≤ кўринишда, минималлаштириш масаласида барча тенгсизликлар ≥ кўринишда бўлади.

4-хосса. Тенгсизликлар системасидаги ўзгарувчилар олдидаги коэффициентлардан тузилган матрицалар ҳар иккала масалада ўзаро транспонирланган бўлади.

4-хосса. Тенгсизликлар системасидаги ўзгарувчилар олдидаги коэффициентлардан тузилган матрицалар ҳар иккала масалада ўзаро транспонирланган бўлади.

5-хосса. Битта масаладаги тенгсизликлар сони иккинчи масаладаги ўзгарувчилар сонига мос тушади.
6-хосса. Ҳар иккала масалада ҳам ўзгарувчиларга номанфийлик шарти қўйилади.

2. Иккиланмаликнинг асосий теоремаси

Агар ўзаро иккиланма масаланинг бири оптимал ечимга эга бўлса, унга иккиланма масала ҳам оптимал ечимга эга бўлади ва уларнинг чизиқли функцияларининг оптимал қийматлари тенг бўлади:

ёки

Агар уларнинг чизиқли функцияларидан бири чегараланмаган бўлса, у ҳолда иккинчи масаланинг жоиз ечими мавжуд бўлмайди.

Агар уларнинг чизиқли функцияларидан бири чегараланмаган бўлса, у ҳолда иккинчи масаланинг жоиз ечими мавжуд бўлмайди.

Ўзаро иккиланма масалаларининг ҳар иккаласини симплекс усулда ечганда бир масаланинг бошланғич ўзгарувчилари иккинчи масаланинг қўшимча ўзгарувчилари билан мос тушади

Дастлабки масаланинг ўзгарувчилари
дастлабки	қўшимча
қўшимча	дастлабки
Иккиланма масаланинг ўзгарувчилари

Ўзаро иккиланма масалалардан дастлабкисининг оптимал ечимидаги дастлабки ўзгарувчилари, унга иккиланма масаланинг оптимал ечимидаги қўшимча ўзгарувчиларга мос тушади. Дастлабки масаланинг дастлабки ўзгарувчилари ва унга иккиланма масаланинг қўшимча ўзгарувчилари орасидаги мосликни ушбу жадвалда келтирамиз.

3. Иккиланма масалаларни тузиш усуллари

3. Иккиланма масалаларни тузиш усуллари

Бу қуйидаги тўрт усулда тузилади:

Бу ерда