2-mustaqil ish topshiriqlari

3.Algoritmlarni vaqt va hajmiy murakkablik bo’yicha baholashda tekis va logarifmik solishtirma mezonlar.

Chiziqli dasturlash muammosi (LP) - chiziqli cheklovlar to'plamiga rioya qilgan holda, maqsad funksiyani optimallashtirish uchun matematik model. Maqsad funksiyasi o‘zgaruvchilarning chiziqli birikmasi, cheklovlar esa chiziqli tengsizliklardir.

LP muammosining kanonik ko'rinishi quyidagicha:

Kod parchasi

Maximize:
c^Tx

Subject to:

Ax <= b
x >= 0
Koddan ehtiyotkorlik bilan foydalaning. Batafsil ma'lumot
qayerda:

c - maqsad funksiya uchun koeffitsientlar vektori

A - cheklovlar uchun koeffitsientlar matritsasi
b - cheklovlarning o'ng tomonidagi doimiylar vektori
x - o'zgaruvchilar vektori
Simpleks usuli LP muammolarini hal qilish algoritmidir. Simpleks usulining asosiy g'oyasi muammoning mumkin bo'lgan yechimidan boshlash va keyin maqsad funksiya qiymatini yaxshilash uchun yechimga qayta-qayta o'zgartirishlar kiritishdir. Simpleks usuli, agar mavjud bo'lsa, LP muammosining optimal echimini topish kafolatlanadi.

Simpleks usuli LP muammolarini hal qilish uchun kuchli vositadir. Uni amalga oshirish nisbatan oson va katta LP muammolarini hal qilish uchun ishlatilishi mumkin. Biroq, simpleks usuli ba'zi muammolar uchun sekin bo'lishi mumkin. LP muammolarini hal qilish uchun boshqa algoritmlar mavjud, ular ba'zi muammolar uchun simpleks usulidan tezroq bo'lishi mumkin.

Simpleks usulining ba'zi afzalliklari:

Bu oddiy va intuitiv algoritm.

Agar mavjud bo'lsa, LP muammosining optimal echimini topish kafolatlanadi.
Uni amalga oshirish nisbatan oson.
Simpleks usulining kamchiliklari:

Ba'zi muammolar uchun sekin bo'lishi mumkin.

Algoritm uchun yaxshi boshlanish nuqtasini topish qiyin bo'lishi mumkin.
Raqamli xatolarga sezgir bo'lishi mumkin.
Umuman olganda, simpleks usuli LP muammolarini hal qilish uchun kuchli vositadir. Uni amalga oshirish nisbatan oson va katta LP muammolarini hal qilish uchun ishlatilishi mumkin. Biroq, simpleks usuli ba'zi muammolar uchun sekin bo'lishi mumkin. LP muammolarini hal qilish uchun boshqa algoritmlar mavjud, ular ba'zi muammolar uchun simpleks usulidan tezroq bo'lishi mumkin.