|
I
|
Bazislar
|
Bazis koef.
|
|
|
|
…
|
|
|
|
…
|
|
1
|
|
|
|
|
|
…
|
|
1
|
0
|
…
|
0
|
2
|
|
|
|
|
|
…
|
|
0
|
1
|
…
|
0
|
…
|
…
|
…
|
..
|
…
|
|
…
|
…
|
…
|
…
|
…
|
|
m
|
|
|
|
|
|
|
|
0
|
0
|
|
1
|
m+1
|
|
|
|
|
|
|
|
|
|
|
Bu jadvalga asosan 1-simpleks jadval tuziladi. Indekslar satrini taxlil qilganda satr elementlarining musbat yoki manfiyligiga e’tibor beriladi. Agar indeks satri elementlarining hammasi musbat bo’lsa, u holda mumkin bo’lgan yechimini o’zgartirib bo’lmaydi va bu yechim optimal yechim bo’ladi.
Misol.
cheklanish shartlari sistemasini qanoatlantiruvchi chiziqli funksiyani maksimum qiymatini toping.
Yechish. Tengsizliklardan tengliklarga o’tamiz:
Oxirgi sistemani vektor formada yozamiz:
birlik vektorlarni boshlang’ich tayanch yechim uchun qabul qilib, noma’lumlarni 0 ga teng deymiz. Natijada tayanch yechimni olamiz, bunga
yoyilma mos keladi.
yechimning optimalligini tekshirish uchun birinchi simpleks jadvalni tuzamiz:
1-simpleks jadval.
I
|
bazis
|
bazis koef
|
|
3
|
8
|
0
|
0
|
0
|
|
|
|
|
|
1
|
|
0
|
428
|
2
|
3
|
1
|
0
|
0
|
2
|
|
0
|
672
|
3
|
6
|
0
|
1
|
0
|
3
|
|
0
|
672
|
2
|
8
|
0
|
0
|
1
|
4
|
|
|
0
|
-3
|
-8
|
0
|
0
|
0
|
va baholarni hisoblaymiz:
, ,
, , , ,
Olingan baholar ichida ikkita, manfiy baholar mavjud bo’lib, ular boshlang’ich tayanch yechim optimal emasligini bildiradi. Bazisga bo’lgan vektorni kiritamiz. bo’lganligi uchun ochuvchi (kalit) element 8 bo’lib, u joylashgan ustun va satrlar yo’naltiruvchi bo’ladi. Demak, bazisga vektorni kiritib vektorni bazisdan chiqaramiz. 2-simpleks jadvalni tuzamiz:
2-simpleks jadval
I
|
bazis
|
bazis koef
|
|
3
|
8
|
0
|
0
|
0
|
|
|
|
|
|
1
|
|
0
|
|
|
0
|
1
|
0
|
|
2
|
|
0
|
28
|
|
0
|
0
|
1
|
|
3
|
|
0
|
84
|
|
1
|
0
|
0
|
|
4
|
|
|
672
|
-1
|
0
|
0
|
0
|
1
|
2-simpleks jadvalda
2-tayanch yechim olindi. Bu yechimga chiziqli funksiyaning
qiymati mos keladi.
satrda manfiy baho mavjud bo’lganligi uchun yechim optimal emas. Shunung uchun vektor bazisga kiritilishi kerak. bo’lib, ochuvchi (kalit) element bo’ladi.
Bazisdan vektor chiqariladi. Oldingi jadvaldagidek, Jordan-Gauss to’la yo’qotish usulidan foydalanib, boshqa satrlar elementlarni hisoblab, 3-simpleks jadvalni tuzamiz:
3-simpleks jadval
I
|
bazis
|
bazis koef
|
|
3
|
8
|
0
|
0
|
0
|
|
|
|
|
|
1
|
|
0
|
12
|
0
|
0
|
1
|
|
|
2
|
|
3
|
112
|
1
|
0
|
0
|
4
|
|
3
|
|
8
|
56
|
0
|
1
|
0
|
-1
|
|
4
|
|
|
784
|
0
|
0
|
0
|
4
|
0
|
-satrda, manfiy baholar yo’q, demak, olingan reja optimal bo’lib optimal yechim bo’ladi.
Mustaqil ish uchun topshiriqlar.
1. 2.
3. 4.
5. 6.
7. 8.
3§.Transport masalasi.
Reja:
3.1. Transport masalasini qo’yilishi.
3.2. Masalani boshlang’ich yechimini topish usullari.
Transport masalasi chiziqli programmalashtirishtirish masalalari ichida nazariy amaliy nuqtai nazaridan eng yaxshi o’zlashtirilgan masalaridan bo’lib undan sanoat va qishloq xo’jaligi mahsulotlarini tashishni optimal rejalashtirish muvaffaqiyatli ravishda foydalanilib kelinmoqda.
Transport masalasi chiziqli programmalashtirishtirish sinfiga tegishli bo’lib , uning chegaralovchi shartlaridagi tuzilgan koeffitsientlaridan tuzilgan matritsaning elementlari 0 va 1 raqamlardan iborat bo’ladi va har bir ustunda faqat ikkita element 0 dan farqli, qolganlari esa 0 ga teng bo’ladi. Transport masalasini yechish uchun uning maxsus xususiyatlarini nazarga oluvchi usullar yaratilgan bo’lib, biz ular bilan tanishamiz.
3.1. Transport masalasini qo’yilishi
Faraz qilaylik, m ta ishlab chiqarish korxonasi berilgan bo‘lsin. Bu korxonalarda mos ravishda, tonnadan bir jinsli mahsulotlar ishlab chiqarilgan bo‘lib, bu mahsulotlarni nta iste’molchilarga, mos ravishda tonnadan yetkazib berish kerak. ishlab chiqarish korxonasidan iste’molchilarga mahsulotlarni tashish uchun sarf qilinadigan xarajat pul birligiga teng. bilan esa rejalshtirilgan davr ichida ishlab chiqarish korxonasidan iste’molchilarga mahsulotning umumiy miqdorini belgilaymiz. Transport masalasini berilgan parametrlarini va belgilangan noma’lumlarni jadvalga joylashtiramiz.
1-jadval
Ishlab chiqarish
Korxonalari
(Ta’minotchilar)
|
Korxonada
ishlab
chiqarilgan
mahsulotlar
(tonna
hisobida )
|
Iste’molchilar
|
|
|
…
|
|
|
|
|
|
…
|
|
|
|
|
|
…
|
|
…
|
…
|
…
|
…
|
…
|
…
|
|
|
|
|
…
|
|
Talablar
|
|
|
|
…
|
|
Masalaning maqsadi: 1) har bir korxonada ishlab chiqarilgan mahsulotlar to’la taqsimlansin; 2) har bir iste’molchini mahsulotga bo’lgan talabi to’la qondirilsin va shu bilan bir qatorda yo’l xarajatlarining umumiy qiymati eng kichik bo’lsin.
Masalaning 1-shartini quyidagi tenglamalar sistemasi orqali ifoda qilish mumkin:
(3.1)
Masalaning 2-sharti esa quyidagi tenglamalar sistemasi orqali ifoda qilish mumkin:
(3.2)
Masalaning iqtisodiy ma’nosiga ko’ra noma’lumlar manfiy bo’lmasligi kerak, ya’ni
(3.3)
ishlab chiqarish korxonasidan iste’molchiga rejadagi birlik mahsulotni yetkazib berish uchun sarf qilinadigan xarajati pul birligiga teng bo’ladi.Rejadagi barcha mahsulotlarni tashish uchun sarf qilinadigan umumiy yo’l xarajatlari esa
funksiya orqali ifodalanadi. Masalaning shartiga ko’ra bu funksiya minimumga erishadi, ya’ni
(3.4)
(3.1)-(3.4) munosabatlar birgalikda Transport masalasining matematik modeli deb ataladi.
Agar ishlab chiqarish korxonasidagi jami bir jinsli mahsulotlar miqdori iste’molchilarning talabini to'la qondirsa, ya’ni
(3.5)
bo'lsa, yuqoridagi jadvalga asoslanib tuzilgan model yopiq modellli transport masalasi deyiladi.
Agar (3.5) tenglik bajarilmasa, ya’ni
(3.6)
o’rinli bo’lsa, ochiq modellli transport masalasi deyiladi.Bunda ikki hol bo’lishi mumkin: a) ta’minlovchilardagi yuklar jami miqdori, iste’molchilar jami talabidan kam bo’lishi, ya’ni
bunday holda, birinchisida soxta ta’minlovchi kiritish bilan masalani transport masalasining yopiq modeliga keltiriladi.
b) ta’minlovchilardagi yuklarning jami miqdori, iste’molchilar jami talabi miqdoridan ko’p bo’lishi, ya’ni
bunday holda esa, soxta iste’molchi kiritish bilan masalani transport masalasining yopiq modeliga keltirish mumkin.
Transport masalasiga doir quyidagilarni isbotsiz keltiramiz.
3.1-teorema. Har qanday yopiq modelli transport masalasi yechimga ega.
3.2-teorema. Transport masalasini shartlaridan tuzilgan matritsaning rangi m+n-1 ga teng.
Natija. Transport masalasi yechimidagi 0 dan farqli qiymatli o’zgaruvchilari soni m+n-1 ta bo’ladi.
3.3-teorema. Ixtiyoriy transport masalasi optimal yechimga ega.
Do'stlaringiz bilan baham: | 
