Chiziqli programmalash masalasinining geomatematik interpritatsiyasi

Chiziqli programmalash masalasinining geomatematik interpritatsiyasi

Bizga maqsad funksiyaning cheklanish tengsizliklar sistemasini qanoatlantiradigan minimumini topishning chiziqli programmalash masalasi berilgan boʻlsin:

Tengsizliklar sistemasini qanoatlantiradigan ixtiyoriy x₁, x₂…,x_n sonlar toʻplami uning echimlari deyiladi.
Sistema hech boʻlmasa bitta echimga ega boʻlsa sistema birgalikda deyiladi. Aks holda esa, sistema birgalikda emas deyiladi. Bundan keyin biz tengsizliklar sistemasini birgalikda deb faraz qilamiz.
n=2 boʻlganda tengsizliklar sistemasidan quyidagi sistemani hosil qilamiz:

Bu tengsizliklarning har biri a_i1x₁+a_i2x₂₌b_i toʻgri 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. Tengsizliklar sistemasi birgalikda boʻlganligi uchun hech boʻlmaganda bitta echimga ega boʻladi, ya’ni chegaraviy toʻgʻri chiziqlar bir-biri bilan kesishib, mumkin boʻlgan (oʻrinli) echimlar toʻplamini hosil qiladi. Demak, n=2 boʻlganda mumkin boʻlgan echimlar toʻplami koʻpburchakning nuqtalaridan iborat boʻladi. Masalan, m=4 boʻlganda mumkin boʻlgan echimlar toʻplami 1.5.1-rasmda koʻrsatilgan koʻpburchakdan iborat boʻladi. Agar 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=1,2,…m) tekisliklar bilan, echimlarning manfiy boʻlmaslik shartlari x_j0 lar esa, x_j=0 tekisliklar bilan chegaralangan uch oʻlchovli yarim fazolardan iborat boʻladi.
Ikkinchi tomondan, sistema birgalikda boʻlganligi uchun bu yarim fazolar kesishib, biror bir koʻpyoqli hosil qiladi. Koʻp yoqli esa mumkin boʻlgan echilar toʻplamini beradi, ya’ni uning ixtiyoriy nuqtasining koordinatalari sistemada n>3 boʻlsa, bu tengsizliklarning har biri
A_i1x₁+ a_i2x₂+ …+a_inx_n =b_i, (i=1,2,…m)
gipertekisliklar bilan echimlarning manfiy boʻlmaslik shartlari esa x_j=0 gipertekisliklar bilan chegaralangan yarim fazolardan iborat boʻladi. Bu yarim fazolar kesishib, mumkin boʻlgan echimlar toʻplami boʻlgan birorta koʻp yoqlini hosil qiladi.
Yuqoridagi mulohazalar chiziqli programmalash masalalarini geometrik nuqtai nazaridan quyidagicha talqin qilishga imkon beradi: mumkin boʻlgan echimlar toʻplami boʻlgan koʻpyoqlining shunday nuqtasining koordinatalarini topish kerakki, bu nuqtada maqsad funksiya oʻzining eng kichik qiymatiga erishsin.

1.5.1-rasm. Qavariq koʻpburchak 1.5.2-rasm.Koʻpburchakli qavariq soha

1.5.3- rasm. Yagona nuqtali 1.5.4- rasm. Boʻsh toʻplam
Mumkin boʻlgan echimlar sohasi (toʻplami) qavariq koʻpburchak (1.5.1-rasm), koʻpburchakli qavariq soha (1.5.2-rasm), yagona nuqta (1.5.3-rasm) va boʻsh toʻplam (1.5.4-rasm) boʻlishi mumkin.