Chiziqli dasturlashning transport masalasi

Chiziqli dasturlashning transport masalasi Reja: Transport masalasining qo'yilishi va uning matematik modeli. Yopiq transport masalasi Boshlang'ich rejalar tuzish usullari. Shimoliy -G'arbiy usul. Minimal qiymat usuli Transport masalasi - chiziqli dasturlashning alohida xususiyatli masalasi bo'lib bir jinsli yuk tashishning eng tejamli rejasini tuzish masalasidir. Bu masala xususiyligiga qaramay qo'llanish sohasi juda kengdir. Masalaning qo'yilishi va uning matematik modeli m-ta Ai (i = 1,2,…, m) ta'minotchilarda yig'ilib qolgan bir jinsli ai miqdordagi mahsulotni n-ta Bj iste'molchilarga mos ravishda bj (j=1,2,…,n) miqdorda yetkazib berish talab qilinadi. Har bir i-ta'minotchidan har bir j-iste'molchiga bir birlik yuk tashish yo'l xarajati malum va u cij - so'mni tashkil qiladi. Yuk tashishning shunday rejasini tuzish kerakki, ta'minotchilardagi barcha yuklar olib chiqib ketilsin, iste'molchilarning barcha talablari qondirilsin va shu bilan birga yo'l xarajatlarining umumiy qiymati eng kichik bo'lsin. Masalaning matematik modelini tuzish uchun i-ta'minotchidan j-iste'molchiga yetkazib berish uchun rejalashtirilgan yuk miqdorini xij orqali belgilaymiz, u holda masalaning shartlarini quyidagi jadval ko'rinishda yozish mumkin: Jadvaldan ko'rinadiki, i-ta'minotchidan j-iste'molchiga rejadagi xij - birlik yuk yetkazib berish yo'l xarajati cij xij - so'mni tashkil qiladi. Rejaning umumiy qiymati esa, ga teng bo'ladi. Masalaning birinchi shartiga ko'ra, yani barcha yuklar olib chiqib ketilishi sharti uchun tengliklarga ega bo'lamiz; ikkinchi shartga ko'ra, yani barcha talablar to'la qondirilishi uchun tengliklarga ega bo'lamiz; Shunday qilib masalaning matematik modeli quyidagi ko'rinishni oladi: chiziqli tenglamalar sistemasining (3) xij ? 0, i=1,2,…,m; j=1,2,…,n shartlarni qanoatlantiruvchi shunday yechimini topish kerakki, bu yechim (3) chiziqli funksiyaga eng kichik qiymat bersin. Bu modelda tenglik o'rinli deb faraz qilinadi. Bunday masalalar «yopiq modelli transport masalasi» deyiladi. Teorema. Talablar hajmi zahiralar hajmiga teng bo'lgan istalgan transport masalasining optimal yechimi mavjud bo'ladi. Boshlang'ich tayanch yechimni qurish. Malumki, ixtiyoriy chiziqli dasturlash masalasining optimal yechimini topish jarayoni boshlang'ich tayanch yechimini ko'rishdan boshlanadi. Masalaning (1) va (2) sistemalari birgalikda mn - ta nomalumli m+n - ta tenglamalarda iborat. Agar (1) sistemaning tenglamalarini hadma-had qo'shsak, va alohida (2) sistemaning tenglamalarini hadma-had qo'shsak, ikkita bir xil tenglama hosil bo'ladi. Bu esa (1) va (2) dan iborat sistemada bitta chiziqli bog'lik tenglama borligini ko'rsatadi. Bu tenglama umumiy sistemadan chiqarib tashlansa, masala m+n-1 ta chiziqli bog'liq bo'lmagan tenglamalar sistemasidan iborat bo'lib qoladi. Demak, masalaning buzilmaydigan tayanch yechimi m+n-1 ta musbat komponentalardan iborat bo'ladi. Shunday qilib, transport masalasining boshlang'ich tayanch yechimi biror usul bilan topilgan bo'lsa, (xij) - matritsaning m+n-1ta komponentalari musbat bo'lib, qolganlari nolga teng bo'ladi. Agar transport masalasining shartlari va uning tayanch yechimi yuqoridagi jadval ko'rinishda berilgan bo'lsa, noldan farqli ...