Algoritmlarni loyihalash fanidan on savollari! Kvadratur formulalarining xatoligi? Transport masalasini yechish bosqichlari?

Labotoriya topshirig‘i sharti. Masalani simpleks usul bilan yeching



Masalani yechish algoritmi (Simpleks usuli). Belgilashlar kiritamiz va simpleks jadvalni to’ldiramiz:

Simpleks usulning I bosqichida bazisga P₃ vektor kiritilib P₄ vektor chiqarildi, II bosqichida P₂ kiritildi va P₁ chiqarildi. Simpleks jadval (7) formulalar asosida almashtirilib borildi. III bosqichda optimal yechim topildi:

11. Tarmoqlanuvchi algoritmlar to'liq va qisqa shakliga doir misol va algoritm tuzish?

12. Chiziqli dasturlashning maxsus masalalari. Transport masalasi

         Transport masalasi chiziqli dasturlash masalalari ichida nazariy va amaliy nuqtai nazardan eng yaxshi o’zlashtirilgan masalalardan biri bo’lib, undan sanoat va qishloq xo’jalik mahsulotlarini tashishni optimal rejalashtirish ishlarida muvaffaqiyatli ravishda foydalanilmoqda.

         Transport masalasi maxsus chiziqli dasturlash masalalari sinfiga tegishli bo’lib, uning chegaralovchi shartlaridagi koeffitsientlardan tuzilgan (a_ij) 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, quyida biz ular bilan tanishamiz.

Transport masalasining matematik modeli va xossalari

Faraz qilaylik, A₁, A₂, . . . A_m punktlarda bir xil mahsulot ishlab chiqarilsin. Ma’lum bir vaqt oralig’ida har bir Ai(i=1..m) punktda ishlab chiqariladigan mahsulot miqdori  a_i birlikka teng bo’lsin. Ishlab chiqariladigan mahsulotlar B₁, B₂, ..., B_n punktlarda iste’mol qilinsin hamda har bir B_j(j=1,n) iste’molchining ko’rilayotgan vaqt oralig’ida mahsulotga bo’lgan talabi b_j(j=1,n) birlikka teng bo’lsin.

Bundan tashqari A₁, A₂, ..., A_m punktlarda ishlab chiqariladigan mahsulotlarning umumiy miqdori B₁ ,B₂ ,..., B_n  punktlarning mahsulotga bo’lgan talablarining umumiy miqdoriga teng, ya’ni 

tenglik o’rinli bo’lsin deb faraz qilamiz . Deylik, har bir ishlab chiqarish  punkti A_i dan hamma iste’mol qiluvchi punktga mahsulot tashish imkoniyati mavjud, hamda A_i  punktdan  B_j  punktga mahsulotni olib borish uchun sarf qilinadigan xarajat C_ij pul birligiga teng bo’lsin.

x_ij bilan rejalashtirilgan vaqt oralig’ida A_i punktdan B_j punktga olib boriladigan mahsulotning umumiy miqdorini belgilaymiz.

Transport masalasining berilgan parametrlarini va belgilangan noma’lumlarni quyidagi jadvalga joylashtiramiz.

                        

Bj Ai	B1	B2	…	Bn	Taklif miqdori
A1	C11 X11	C12 X12	…	C1n X1n	a1
A2	C21 X21	C22 X22	…	C2n X2n	a2
…	…	…	…	…	…
Am	Cm1 Xm1	Cm2 Xm2	…	Cmn Xmn	am
Talab miqdori	b1	b2	…	bn