Maruza mashg’ulotlari

Chiziqli dasturlash masalasini simpleks usulda yechish

Aytaylik, bizga (1.1) maksad funksiyasining (13.2) cheklanish tengsizliklar sistemasini kanoatlantiradigan minimumini topish masalasi berilgan bo‘lsin. Tengsizliklar sistemasi (13.2)ni qanoatlantiradigan ixtiyoriy x₁,x₂,..,x_n sonlar to‘plami uning echimlari deyiladi.

(13.2) sistema xech bo‘lmasa bitta echimga ega bo‘lsa sistema birgalikda deyiladi. Aks xolda sistema birgalikda emas deyiladi. Bundan keyin biz tengsizliklar sistemasi (13.2)ni birgalikda deb faraz qilamiz.

n=2 bo‘lganda (13.2)dan quyidagi sistemani hosil qilamiz.

; i= ; x₁ ; x₂ (14.1)

Bu tengsizliklarning har biri a_i1x₁+a_i2x₂=b_i to‘g‘ri chiziq bilan, echimlarning manfiy bo‘lmaslik shartlari x_j≥0 j=1;2 esa, x_j=0 to‘g‘ri chiziq bilan chegaralangan yarim tekisliklar bo‘ladi. (14.1) tengsizliklar sistemasi birgalikda bo‘lgani uchun xech bo‘lmaganda bitta echimga ega bo‘ladi, ya’ni chegaraviy to‘g‘ri chiziqlar bir-biri bilan kesishib, o‘rinli echimlar to‘plamini hosil qiladi. Demak, n=2 bo‘lganda o‘rinli echimlar to‘plami ko‘pburchakning nuqtalarilan iborat bo‘ladi. (13.2)da n=3 bo‘lsa va bu tengsizliklarning har biriga geometrik nuqtai nazardan qaraganda ularning har biri a_i1x₁+a_i2x₂+a_i3x₃=b_i, i= tekisliklari bilan, echimlarning manfiy bo‘lmaslik shartlari x_j=0 lar esa, x_j0 tengsizliklar bilan chegaralangan uch o‘lchovli yarim fazolardan iborat bo‘ladi.

Ikkinchi tomondan (13.2) sistema birgalikda bo‘lganligi uchun bu yarim fazolar kesishib, biror bir ko‘pyoqli hosil qiladi. KO‘pyoqli esa, o‘rinli echimlar to‘plamini beradi, ya’ni uning ixtiyoriy nuqtasining koordinatalari (13.2) ni qanoatlantiradi va nihoyat (13.2) da n>3 bo‘lsa bu tengsizlikning har biri a_i1x₁+a_i2x₂+ ..+a_inx_n=b_i; i= gipertekisliklar bilan, manfiy bo‘lmaslik shartlari esa, x_j=0 gipertekisliklar bilan chegaralgan yarim fazolardan iborat bo‘ladi. Bu yarim fazolar kesishib, o‘rinli echimlar to‘plami bo‘lgan birorta ko‘pyoqlini hosil qiladi.

Yuqoridagi mulohazalar chiziqli dasturlash masalalarini geometrik nuqtai nazardan talqin qilishga imkon beradi: o‘rinli echimlar bo‘lgan ko‘pyoklining shunday nuqtasining koordinatalarini topish kerakki, bu nuqtada maqsad funksiya (13.1) o‘zining eng kichik qiymatiga erishsin.

Grafik usul. Bizga ikki o‘lchovli fazoda chiziqli dasturlash masalasi berilgan bo‘lsin, ya’ni ushbu

Z = C₁X₁ + C₂ X₂ (14.2)

funksiyaning cheklanish tengsizliklari sistemasi

(14.3)

ni qanoatlantiradigan eng kichik qiymatini topish talab qilingan bo‘lsin.

Tengsizliklar sistemasi (14.3) ni birgalikda deb faraz qilsak, bu tengsizlikning har biri a_i1x₁+ a_i2x₂ = b_i, i = 1,2 to‘g‘ri chiziqlar bilan, echimlarning manfiy emaslik shartlari esa Xj=0, j=1,2 to‘g‘ri chiziqlar bilan yarim tekisliklarni tashkil etadi va bu yarim tekisliklar bir – biri bilan kesishib, o‘rinli echimlar to‘plami bo‘lgan birorta ko‘pburchakni tashkil etadi.

Maqsad funksiya (14.2) Z ning har bir qiymatida birorta to‘g‘ri chiziqning tenglamasini bildiradi, ya’ni

C₁X₁ + C₂ X₂= const (14.4)

hususiy holda Z=0 , bo‘lsa to‘g‘ri chiziq

C₁X₁ + C₂ X₂=0 (14.5)

ko‘rinishda bo‘lib , koordinata boshidan o‘tadi. Maqsad funksiyasi orqali aniqlanuvchi bunday to‘g‘ri chiziq satx chiziІi deyiladi. Endi qo‘yilgan masalani quyidagicha bayon qilish mumkin: o‘rinli echimlar to‘plami bo‘lgan ko‘pburchakning shunday tayanch to‘g‘ri chiziІini topish kerakki, ko‘pburchak bilan tayanch to‘g‘ri chiziqqa umumiy bo‘lgan nuqtada maqsad funksiya (14.2) o‘zining eng kichik qiymatiga erishsin. Maqsad funksiya =(C₁,C₂) vektor yo‘nalishi bo‘yicha xamma vaqt o‘suvchi bo‘lib, vektor (14.4) to‘g‘ri chiziqlarga perpendikulyar bo‘ladi Shuning uchun (14.5) to‘g‘ri chiziqni N vektor yo‘nalishi bo‘yicha o‘ziga parallel ravishda ko‘chira boshlasak, u AVSDEF ko‘pburchakka A va D nuqtalarda tayanch to‘g‘ri chiziq bo‘ladi va maqsad funksiya (14.2) shu A nuqtada eng kichik qiymatiga erishadi.

S

X₂
V D




A E

F

X₁

A nuqtaning koordinatalari X⁰₁ va X⁰₂ lar AV va AF to‘g‘ri chiziqlarning tenglamalaridan tuzilgan sistemani, ya’ni

ni birgalikda echish natijasida topiladi.

Grafik usuli bilan echiladigan chiziqli dasturlashtirish masalalariga doir misollar.

1) Xom ashyodan foydalanish masalasini echish.

Xom ashyodan foydalanish masalasi ushbu Z = 50X₁ + 40 X₂

chiziqli funksiyaning quyidagi

cheklanish tengsizliklar sistemasini qanoatlantiradigan maksimumini topishdan iboratdir.

Echish: Avval, o‘rinli echimlar to‘plami bo‘lgan ko‘p burchakni hosil qilamiz. Buning uchun X₁OX₂ tekislikda cheklanish tengsizliklarining har biriga to‘g‘ri keladigan chegaraviy to‘g‘ri chiziklarning , ya’ni

larning o‘rnini topamiz. Natijada o‘rinli echimlar to‘plami bo‘lgan, OAVSD ko‘pburchakni hosil qilamiz, Z=0 bo‘lganda

50X₁ +40X₂=0

to‘g‘ri chiziq N=(50,40) vektorga perpendikulyar bo‘lib koordinata boshidan o‘tadi va OAVSD ko‘pburchakka O va S nuqtalarda tayanch to‘g‘ri chiziq bo‘ladi. Maqsad funksiyamiz N vektor yo‘nalishi bo‘yicha o‘suvchi bo‘lganligi uchun, O nuqtada minimumga,S nuqtada esa maksimumga erishadi. C nuqtaning koordinatalari X₁⁽⁰⁾ va X₂⁽⁰⁾ lar esa l₂ va l₃ to‘g‘ri chiziqlarning tenglamalaridan tuzilgan quyidagi sistemani, ya’ni

8X₁⁽⁰⁾ + 5X⁽⁰⁾₂=40

5X₁⁽⁰⁾ + 6X⁽⁰⁾₂=30

ni birgalikda echish natijasida topiladi. Shunday qilib berilgan maqsad funksiyaga optimal , ya’ni eng katta qiymat beruvchi echim X₁⁽⁰⁾=3,9; X⁽⁰⁾₂=1,7 bo‘lib,

Z=50X₁ +40X⁽⁰⁾₂=50*3,9+40*1,7=263

bo‘ladi.

Demak, 263 so‘mdan iborat bo‘lgan eng katta foydani olish uchun birinchi xil maxsulot M₁ dan 3.9 birlik va ikkinchi xil maxsulot M₂ dan 1.7 birlik maxsulot ishlab chiqarishni rejalashtirish zarur ekan.