Strreplkirish I bob. Chiziqli programmalashtirish masalalari 1-§. Chiziqli programmalashtirish masalalaining amaliy masalalari

1-teorema. Chiziqli programmalashtirish masalasining mumkin bo`lgan yechimlar to`plami (agar bo`sh to`plam bo`lmasa) qavariq to`plam bo`ladi.
Isbot. va nuqtalar



chiziqli programmalashtirish masalasining mumkin bo`lgan yechimlari bo`lsin.
nuqta ham berilgan masalaning mumkin bo`lgan yechimi bo`lishini isbot qilish kerak, ya’ni X nuqta AX B , X 0 shartlarni qanoatlantirishi kerak. va – mumkin bo`lgan yechimlar bo`lgani uchun
va
shartlar bajariladi.
X nuqtani ham AX B tenglikka qo`yamiz:

0, 0 va 0, 0 bo`lgani uchun X 0 bo`ladi.
Demak, X nuqta ham chiziqli programmalashtirish masalasining mumkin bo`lgan yechimi bo`ladi.
2-teorema. Chegaralangan, yopiq, qavariq ko`pburchak o`zining uchlarini qavariq kombinatsiyasidan iborat.
Teoremaning isbotini keltirmaymiz.
4-ta’rif. Agar chiziqli programmalashtirish masalasining mumkin bo`lgan yechimlari, yechim ko`pburchagining chetki nuqtalariga mos kelsa, ular bazis yechimlar deyiladi.
Bu ta’rifdan, musbat komponentli bazis yechimlar tayanch yechimlar
bo`lishi kelib chiqadi.


Chiziqli programmalashtirish masalasining geometrik talqini.
Masalani grafik usulda yechish
Chiziqli programmalashtirish masalasini grafik usulda yechish, uni geometrik tasvirlashga asoslangan. Ikki o`lchovli fazo (tekislik)da berilgan chiziqli programmalashtirish masalalarini yechish uchun grafik usulni qo`llash maqsadga muvofiq. n 3 o`lchovli fazoda berilgan masalalarni grafik usul bilan yechish noqulay, chunki bu holda, yechimlardan tashkil topgan qavariq ko`pburchakni yasash qiyinlashadi.
Ikki o`lchovli fazoda berilgan quyidagi chiziqli programmalashtirish masalasini ko`ramiz:
(1.2.1)
(1.2.2)
(1.2.3)
Faraz qilaylik, (1.2.1) sistema (1.2.2) shartni qanoatlantiruvchi yechimlarga ega hamda ulardan tashkil topgan to`plam chekli bo`lsin.
Tekislikda to`g`ri burchakli Dekart koordinatalar sistemasini kiritamiz va sonlarning har bir juftligiga tekislikda koordinatalari bo`lgan nuqtani mos qo`yamiz. Avval berilgan masalaning mumkin bo`lgan yechimlari qanday nuqtalar to`plamini tashkil qilishini ko`raylik. Ma’lumki, ikki o`zgaruvchili tengsizlik tekislikda to`g`ri chiziq bilan chegaralangan yarim tekislikni aniqlaydi. Bu yarim tekislik to`g`ri chiziqga nisbatan qaysi nuqtalar to`plami ekanini
aniqlashtirish uchun tengsizlikka tekislikdagi ( to`g`ri chiziqda yotmagan) ixtiyoriy nuqtani qo`yib ko`rish mumkin. Olingan nuqta tengsizlikni qanoatlantirsa, shu nuqta yotgan yarim tekislik, aks holda ikkinchi yarimtekislik, qidirilayotgan yarimtekislik bo`ladi. Buni quyidagi misolda ko`raylik.