Mavzu: chiziqli dasturlash masalalarini yechishda simplek usul algoritmi va unung tahlili

Muhammad al-xorazmiy nomidagi
Toshkent axborot texnologiyalari unversiteti

Algoritmlarni loyihalash fanidan

Mustaqil ish


Tekshirdi: MAMADALIYEV x.
Bajardi: 061-19 guruh Andasbayeva Yu.

Toshkent 2022


MAVZU: CHIZIQLI DASTURLASH MASALALARINI YECHISHDA SIMPLEK USUL ALGORITMI VA UNUNG TAHLILI

REJA

1. 
   Kirish
   
2. 
   Chiziqli dasturlash masalalarini yechishda simpleks usul algoritmi va dasturi MS Excel da yechish
   
3. 
   Chiziqli dasturlashning asosiy teoremalari.
   
4. 
   Xulosa
   
5. 
   Foydalanilgan adabiyotlar ro’yxati
   

Chiziqli dasturlash (ChD) – birinchi va puxta o'rganilgan matematik dasturlash bo'limlaridan biri. Bu "matematik dasturlash" fanining o'zi rivojlana boshlagan chiziqli dasturlash edi. Ushbu fan nomidagi "dasturlash" atamasi "kompyuter uchun dasturlash (ya'ni dastur tuzish)" atamasi bilan hech qanday aloqasi yo'q, chunki "chiziqli dasturlash" intizomi kompyuterlardan matematik, muhandislik, iqtisodiy va boshqa muammolarni echishda keng foydalanila boshlangan vaqtdan oldin ham paydo bo'lgan. "Chiziqli dasturlash" atamasi ingliz tilidagi "chiziqli dasturlash" ning noto'g'ri tarjimasidan kelib chiqqan. "Dasturlash" so'zining ma'nolaridan biri bu rejalashtirish, rejalashtirishdir.
Shuning uchun ingliz tilidagi "chiziqli dasturlash" ning to'g'ri tarjimasi "chiziqli dasturlash" emas, balki "chiziqli rejalashtirish" bo'lishi kerak, bu esa fanning mazmunini aniq aks ettiradi. Shu bilan birga, chiziqli dasturlash, nochiziqli dasturlash, matematik dasturlash va boshqalar. adabiyotimizda umumiy qabul qilingan va shuning uchun saqlanib qoladi.
Shunday qilib, chiziqli dasturlash Ikkinchi Jahon Urushidan keyin paydo bo'ldi va matematiklar, iqtisodchilar va muhandislarning e'tiborini keng amaliy qo'llash imkoniyati va matematik uyg'unlik tufayli jalb qildi va tez rivojlana boshladi.
Chiziqli dasturlash masalalari. Haqiqiy olamning chiziqli tasviri gipotezasiga asoslanishi mumkin bo'lgan chiziqli dasturlash o'sha jarayonlar va tizimlarning matematik modellarini echishda qo'llaniladi.
Chiziqli dasturlash iqtisodiy muammolarni echishda, masalan, boshqaruv va ishlab chiqarishni rejalashtirishda ishlatiladi; uskunalarni kemalarga, ustaxonalarga optimal joylashtirishni aniqlash vazifalarida; yuklarni tashishning optimal rejasini aniqlash vazifalarida (transport vazifasi); ramkalarni optimal taqsimlash muammolarida va boshqalar.
Ms Excelda yechish
Masala. Uchta turdagi (i = 1, 2, 3) mahsulot ishlab chiqaruvchi korxona foydasining maksimal qiymatini aniqlang. I-turdagi mahsulotni ishlab chiqarish uchun uch xil turdagi resurs talab etiladi: energetik, moliyaviy va xom-ashyoviy (j = 1, 2, 3). ( энергетические, финансовые и сырьевые)
Boshlangich ma’lumotlar:
1,2 va 3-tur mahsulotni sotishdan tushgan foyda zi:
z1 = 8; z2 = 11; z3 = 12 so‘m./mahs.;
Birlik mahsulot uchun energiya sarfi: а11 = 2; а12 = 2; а13 = 3 b.e./mahs.
Birlik mahsulot uchun sarflanadigan mablag‘ miqdori: а21 = 6; а22 = 5,5; а23 = 4 so‘m./mahs
Birlik mahsulot uchun sarflanadigan xom-ashyo miqdori: а31 = 4; а32 = 6; а33 = 8 b.ashyo./mahs.
Korxonaning energiya, mablag‘ va xom-ashyo resurslari zaxirasi:
b1 = 50 b.e./mahs..; b2 = 100 so‘m./mahs.; b3 = 150 b.ashyo./mahs.
Korxona ishlab chqarishi kerak bo‘lgan barcha mahsulot turlarining eng kam miqdori b4=15.
Yechish. Boshlang‘ich asosan maqsad funksiya quyidagi ko‘rinishga ega bo‘ladi. (3.1)
(1.6) ifoda va boshlang‘ich ma’lumotlarga asosan chegaralanishlar quyidagi ko‘rinishda yziladi:
(3.2)
Qo‘shimcha o‘zgaruvchilarni kiritib, tegsizliklar sistemasidan teglik ko‘rinishiga keltiramiz:
(3.2a)
O‘zgaruvchilarning manfiy bo‘lmaslik shartlari quyidagi ko‘rinishga ega bo‘ladi:
(3.3)
Boshlangich echimni topish uchun larni ozod hadlar, larni esa bazis o‘zgaruvchilar sifatida qaraymiz0.
Chegaralanishlar va maqsad funksiya ma’lumotlari asosida 3.1- jadvalni to‘ldiramiz.
3.1-jadval

							b,Z
2	2	3	1	0	0	0	50
6	5,5	4	0	1	0	0	100
4	6	8	0	0	1	0	150
-1	-1	-1	0	0	0	1	-15
8	11	12	0	0	0	0	Z=0

MS EXCEL dasturi yordamida yechish
Bu chizili dasturlash masalalarini MS EXCEL dasturi yordamida yechishni ko‘rib chiqamiz. Izoh va boshlangʻich ma’lumotlarni ishchi sohaning katakcha(yacheyka)lariga joylashtirish.
Boshlangʻich ma’lumotlarni ishchi sohaga turli qulay tartibda joylashtirish mumkin. Shulardan bir koʻrinishini koʻrib chiqamiz.

A, C, E, G ustunlardagi hamma katakchalarda masalani yechilishiga ta’sir qilmaydigan tushuntirish izohlari keltirilgan.
B2…B13, D10…D12, F10…F12 katakchalariga chap tomondagi matnga mos sonli ma’lumot kiritilgan.
H2…H4 katakchalarga nol soni, qidirilayotgan x1, x2 va x3 uchun boshlangʻich qiymat sifatida berilgan. H7 katakchada maqsad funksiyaning formulasi kiritilsa: =B2*H2+B3*H3+B4*H4, boshlangʻich qiymatlar nol bo‘lganda funksiya qiymati ham nol boʻladi.
B16…B19 katakchalarga tengsizlikning cheklanish chap qismi joylashtirilgan:
=B10*H2+D10*H3+F10*H4,
=B11*H2+D11*H3+F11*H4,
=B12*H2+D12*H3+F12*H4,
=H2+H3+H4,
bu qiymatlar qidirilayotgan o‘zgarivchilarning nol qiymatida nolga teng.
“Поиск решения” buyrug‘ini ishga tushirish va unga boshlang‘ich ma’lumotlarni kiritish.
Uskunalar panelida “Поиск решения” buyrug‘i yo‘q bo‘lsa, Файл  Параметры  Надстройки buyrug‘ini ishga tushuramiz va “Поиск решения” buyrug‘ni tanlaymiz.

“Перейти…” tugmasi bosiladi va buyruq uskunalar paneliga joylashtiriladi.

“Поиск решения” buyrugʻi bosilganda “Параметры поиска решения” muloqat darchasi ochiladi. Maqsad finksiya(Оптимизировать цельевую функцию)ning adresini H7 katakcha ko‘rsatiladi. “До:” ko‘rsatmasidan “Максимум” belgilanadi.


“Изменяя ячейки переменных” qatoriga qidirilayotgan x1, x2 va x3 o‘zgaruvchilar katakchalari ko‘rsatiladi: H2, H3 va H4.Cheklanishlarni o‘rnatish uchun “Добавить” tugmasi bosiladi.

“Добавление ограничения” muloqat darchasida quyidagi cheklanishlar o‘rnatiladi va “Добавить” tugmasi bosiladi.

So‘ngi cheklanish o‘rnatilganida “OK” tugmasi bosiladi va “Параметры поиска решения” muloqat darchasi ochiladi.
“Параметры” muloqat darchasiпa ma’lumotlar kiritish.

“Выберите метод решения” darchasida Simpleks usuli tanlanadi. “Параметры” tugmasi bosiladi va muloqat darchasi ochiladi.

“Параметры” darchasi quyidagicha to‘ldiriladi:


“OK” tugmasi bosiladi va “Параметры поиска решения” muloqat darchasi ochiladi.
Natijani olish.
“Параметры поиска решения” muloqat darchasida “Найти решение” tugmasi bosilganda, MS EXCEL dasturi hisoblashni boshlaydi va ishchi sohada natijalar qiyidagicha hosil bo‘ladi.


Natijalarni saqlang va tahlil qiling:



Amaliyotda muammoni chiziqli struktura shaklida yechish uchun algoritm sxemasini taqdim etish kamdan-kam uchraydi.
Tarmoqlanuvchi algoritmlarning ikkita asosiy ko’rinishi mavjud:

Tarmoqlanuvchi


To'liq Tugallanmagan

To'liq tarmoqlanuvchi

Algoritmda ikkala tarmoq uchun ham harakatlar bajarilishini taxmin qiladi: Agar [shart] bo'lsa, unda [1-harakat], aks holda [2-harakat].
Bunday algoritmning tuzilishi 1-rasmda keltirilgan.


1-rasm. To'liq tarmoqlanuvchi algoritm blok-sxemasi

Tugallanmagan tarmoqlanuvchi
Bu algoritmning faqat bitta yo'nalishi bo'yicha harakatlarni o'z ichiga oladi (ikkinchisi yo'q):

Agar [shart] bo'lsa, unda [harakat]

Bunday algoritmning tuzilishi 3-rasmda keltirilgan.

Shunday qilib, tarmoqlanuvchi algoritmni ishlab chiqishda quyidagilarni hisobga olishingiz kerak.
- algoritmning ushbu turi shartli qism operatsiyalari mavjud bo'lganda foydalanilishini;
- ko'pincha bir nechta arifmetik ifodalar (formulalar) bilan aniqlangan funksiyalarni hisoblash uchun ishlatiladi;
- undagi ko'rsatmalar shartning qiymatiga qarab amalga oshiriladi.
Chiziqli dasturiy muammolarni echish usullarini asoslash uchun ularning analitik isbotlarini hisobga olmagan holda bir qator muhim teoremalarni tuzamiz. Har bir teoremaning ma'nosini tushuntirish oldingi kichik bo'limda berilgan ZLP masalasini geometrik izohlash tushunchasiga yordam beradi.
Ammo, birinchi navbatda, kelgusida muhokama qilish uchun muhim bo'lgan ba'zi tushunchalarni eslaymiz.
Agar n o'zgaruvchisi (m N o'zgaruvchilar (m Maxsus holatda, cheklash tizimiga x1 va x2 ikkita o'zgaruvchilar kiritilgan bo'lsa, ushbu to'plam tekislikda ko'rsatilishi mumkin. Mumkin echimlar (x1, x2 ≥ 0) haqida gaplashayotganimiz sababli, tegishli to'plam Karteziya koordinatalari tizimining birinchi choragida joylashgan bo'ladi. Ushbu to'plam yopiq (ko'pburchak), ochiq (cheksiz ko'pburchak maydon) bo'lishi mumkin, bitta nuqtadan iborat va nihoyat, cheklash-tengsizlik tizimi qarama-qarshi bo'lishi mumkin.