Butun sonli chiziqli dasturlash modellari

CHIZIQLI DASTURLASH MASALASINI MATEMATIK MODELI
CHiziqli dasturlash masalasining umumlashgan matematik modeli formasining yozilishi quyidagi ko'rinishga ega.



Modelni vektor ko'rinishida quyidagicha yozish mumkin



Chiziqlidasturlashmasalasinimatematikmodeli
Iqtisodiy matematik modelning birinchi formulasi iqtisodiy ma'noda izlanayotgan miqdorlarga qo'yiladigan cheklanishlarni ifodalaydi, ular resurslar miqdori, ma'lum talablarni qondirish zaruri, 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. Uchinchisi maqsad funksiyasi deyilib, izlanayotgan miqdorning biror bog'lanishini ifodalaydi. Noma'lumlarning son qiymatlari to'plami masalaning yechimi deyiladi.
CHeklanishlar tizimini qanoatlantiruvchi har qanday yechim mumkin bo'lgan yechim deyiladi.
Maqsad funksiyasiga maksimal (yoki minimal) qiymat beruvchi mumkin bo'lgan yechim masalaning optimal yechimideyiladi.
Tengsizliklar tizimi ko'rinishida berilgan cheklanish shartlarini qo'shimcha o'zgaruvchilar, ya'ni xn+i kiritib tenglamalar tizimini quyidagicha yozish mumkin.



U holda bunday masalaga kanonik ko'rinishda berilgan chiziqli dasturlash masalasi deyiladi.
CHIZIQLI DASTURLASH MASALASINI YECHISHNING SIMPLEKS USULI
Simpleks usuli chiziqli dasturlash masalasini yechishning asosiy usullaridan biri bo'lib, ketma-ket yaqinlashish usuli yordamida o'tkazuvchilarning shunday optimal qiymatini topadiki, bu qiymatlar maqsad funksiyasiga maksimal (yoki minimal) qiymat beriladi.
Quyidagi chiziqli dasturlash masalasi berilgan bo'lsin:



Masalani yechish uchun simpleks jadval quramiz va simpleks usulga moslashtirish uchun berilgan masalani quyidagicha kanonik formada yozamiz.

Bu yerda – ozod o'zgaruvchilar deyiladi. Ularni qulaylik, hamda boshqa o'zgaruvchilardan farqlash uchun mos ravishda u1, deb belgilaymiz va yana quyidagi belgilashlarni kiritamiz bi0=bi; bij=aij; b0j=cj. Bu belgilashlar asosida quyidagi simpleks jadval deb ataluvchi jadvalni tuzamiz.

Chiziqli dasturlash masalasini Simpleks usuli yordamida yechishning bosqichlari
Chiziqli dasturlash masalasini simpleks usul yordamida yechish ikki bosqichdan iborat:
1. Boshlang'ich tayanch yechimni topish.
2. Tayanch yechimlar ichidan masalaning optimal yechimini toppish