Chiziqli programmalashtirish masalasini kanonik shakllari

Chiziqli tenglamalar sistemasini bazis va nobazis echimlarini topish

Chiziqli programmalshtirish masalasini echishda shartdan kelib chiqqan holda, tenglamalar sistemasining nomanfiy bazis echimlarini aniqlash talab qilinadi. Chegaraviy shartni ifodalovchi tenglamalar sistemasida oʻzgaruvchilar soni , tenglamalar soni dan koʻp boʻlganligi sababli tenglama bazis echimlar ham koʻp boʻladi. U holda bazis echimlar soni bazis oʻzgaruvchilar hamda umumiy oʻzgaruvchilar sonidan kelib chiqib quyidagi formula orqali aniqlanadi.

,
bu erda – bazis oʻzgaruvchilar soni, n – umumiy oʻzgaruvchilar soni.
Bazis oʻzgaruvchilar soni 2 va umumiy oʻzgaruvchilar soni 4 boʻlgani uchun bazislar sonini aniqlash uchun quyidagi hisoblashni amalga oshiramiz.
.
Matematik programmalash matematikaning asosan koʻp variantli echimga ega boʻlgan masalalarinining eng yaxshi, maqsadga muvofiq, ya’ni optimal echimini topishga yordam beruvchi bir yoʻnalishidir. Matematik programmalash chiziqli programmalash, chiziqli boʻlmagan programmalash va dinamik programmalash deb ataluvchi qismlarni oʻz ichiga oladi. “Programmalash” deganda echimlarni ketma - ket hosil qilish jarayoni tushuniladi. Bu echim jarayonki, unda eng avval boshlangʻich echim topiladi va keyin bu echim qadamba-qadam yaxshilanib boriladi. Bu jarayon eng yaxshi dastur topulguncha davom ettiriladi va har bir qadamda maxsus koʻrsatgichlar yordamida qanday ish tutish, hamda optimal echimga qanday yaqinlashish kerakligi koʻrsatilib boriladi.
Chiziqli programmalash masalasini toʻliq tushunish uchun oldin chiziqli funksiya, Chiziqli tenglamalar va tengcizliklar, ularning echimlari haqida toʻliq tassavurlarga ega boʻlish lozim. Shu sabab biz matematikada bu tushunchalar berilgan boʻlsada ularga qicqacha tushuntirish berib oʻtamiz.
Chiziqli programmalash matematik programmalashning asosiy qismlaridan biri boʻlib, koʻp oʻzgaruvchi funksiyalarning ekstremumlarini topishni oʻrganadi va iqtisodiy-matematik modellarni tekshirishda matematik apparat boʻlib hisoblanadi.
Koʻp oʻzgaruvchi funksiyaning minimum yoki maksimumi izlanayotganda oʻzgaruvchilarga koʻp cheklanishlar qoʻyiladi. Bu cheklanishlarning har xil turlariga qarab chiziqli programalash masalasi uch xil koʻrinishda yoziladi: simmetrik, kanonik va standart. Chiziqli programmalash masalasining qoʻyidagi istalgan formada yozilgan matematik modelini qaraymiz.
Matematik model qoʻyidagicha talqin qilanadi: Tenglamalar yoki tengsizliklar sistemasini qanoatlantiruvchi oʻzgaruvchilarining shunday manfiy boʻlmagan qiymatlarini topish talab qilinadiki, bunda oʻzgaruvchilarning chiziqli funksiyasi boʻlgan miqdor (maqsad funksiyasi) eng katta (eng kichik) qiymatga ega boʻlsin (erishsin).

Ushbu matematik modelni vektor koʻrinishida quyidagicha yozish mumkin
(1.2.3)
(1.2.3) formulaning birinchi shart - iqtisodiy ma’noda izlananayotgan miqdorlarga qoʻyiladigan cheklanishlarni ifodalaydi, ular resurslar miqdori, ma’lum talablarni qondirish zarurati, texnologiya sharoiti va boshqa iqtisodiy hamda texnikaviy faktorlardan kelib chiqadi. Ikkinchi shart - oʻzgaruvchilarning, ya’ni izlanayotgan miqdorlarning manfiy boʻlmaslik sharti boʻlib hisoblanadi. Uchinchi shart - maqsad funksiyasi deyilib, izlanayotgan miqdorning biror bogʻlanishini ifodalaydi (ishlab chiqarish maxsulotlarini sotishdan keladigan foyda, ma’lum miqdordagi ishni bajarishga sarf boʻlgan xarajat va h.k.).
Agar maqsad funksiyasi iqtisodiy faktorlarni ifodalasa, u holda funksiyaning maksimum qiymati izlanadi, aks holda minimumni izlash kerak boʻladi.