6-Mavzu: Chiziqli dasurlash masalasi va ularni yechish usullari. Simpleks usuli. 1- masala

6-Mavzu: Chiziqli dasurlash masalasi va ularni yechish usullari.

Simpleks usuli.
1- 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 cotishdan tushgan foyda z_i:

z₁ = 8; z₂ = 11; z₃ = 12 so’m./mahs.;

Birlik mahsulot uchun energiya sarfi: а₁₁ = 2; а₁₂ = 2; а₁₃ = 3 b.e./mahs.

Birlik mahsulot uchun sarflanadigan mablag’ miqdori: а₂₁ = 6; а₂₂ = 5,5; а₂₃ = 4 so’m./mahs

Birlik mahsulot uchun sarflanadigan xomashyo miqdori: а₃₁ = 4; а₃₂ = 6; а₃₃ = 8 b.ashyo./mahs.

Korxonaning energiya, mablag’ va xomashyo resurslari zaxirasi:

b₁ = 50 b.e./mahs..; b₂ = 100 so’m./mahs.; b₃ = 150 b.ashyo./mahs.

Korxona ishlab chqarishi kerak bo’lgan barcha mahsulot turlarining eng kam miqdori b₄=15.

Echish. Boshlang’ich asosan maqsad funksiya quyidagi ko’rinishga ega bo’ladi.

Сhegaralanishlar quyidagi ko’rinishda tuziladi:

Qo’shimcha o’zgaruvchilarni kiritib, tegsizliklar sistemasidan teglik ko’rinishiga keltiramiz:

O’zgaruvchilarning manfiy bo’lmaslik shartlari quyidagi ko’rinishga ega bo’ladi:

Boshlangich echimni topish uchun larni ozod hadlar, larni esa bazis o’zgaruvchilar sifatida qaraymiz.

Chegaralanishlar va maqsad funksiya ma’lumotlari asosida 1- jadvalni to’ldiramiz.

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 x₁,x₂ va x₃ uchun boshlang’ich qiymat sifatida berilgan. H7 katakchada maqsad funksiyaning formulasi kiritilga: =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.

1. 
   “Поиск решения” 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’ini 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 x₁,x₂ va x₃ 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.

2. 
   “Параметры” 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.

3. 
   Natijani olish.
   

“Параметры поиска решения” muloqat darchasida “Найти решение” tugmasi bosilganda, MS EXCEL dasturi xisoblashni boshlaydi va ishchi sohada natijalar qiyidagicha hosil bo’ladi.

Natijalarni saqlab tahlil qiling:

2-Masala:

Quyidagi chiziqli dasturlash masalasini simpleks usulida eching.

Echish:

1. 
   Berilgan masalani quyidagi
   

ko’rinishga keltiramiz.

Yuqoridagi berilgan masala uchun simpleks jadval tuzamiz.

				1
	1	1	1	2
	4	2	1	3
	1	-1	2	-1
	-3	2	-2	5
	-17	-1	-3	0

Ozod sonlar ustunida bitta manfiy son –1 bor. –1 joylashgan qatordagi manfiy sonlarni qaraymiz. Ushbu satrda bitta manfiy son –1 bor. –1 soni joylashgan 3-ustunni hal qiluvchi ustun sifatida qabul qilamiz. Bir хil ishorali mos ozod son va 3-ustun elementlaridan simpleks nisbatlar tuzamiz: . Bu nisbatlarning eng kichigi 1 ga teng bo’lib, u 3-ustundagi –1 soniga mos keladi. –1 sonini bosh element sifatida qabul qilamiz. Hal qiluvchi satr esa 4-satr bo’ladi. U holda jadval quyidagi ko’rinishga keladi:

				1
	1	1	1	2
	4	2	1	3
	1	-1	2	-1
	-3	2	-2	5
	-17	-1	-3	0

-1 ga nisbatan simpleks almashtirishlarni bajarib, navbatdagi jadvalga o’tamiz.

				1
	2	1	3	1
	6	2	5	1
	-1	-1	-2	1
	-1	2	2	3
	-18	-1	-1	1

2-jadvalda barcha ozod sonlar musbat. Demak tayanch echim topilgan. Endi tayanch echimlar ichidan optimal echimni qidiramiz. Optimal echim mavjud bo’lishi uchun qatordagi barcha koifisientlar musbat bo’lishi kerak. Ammo satrda uchta manfiy sonlar –18 ,-1 va –1 bor. Ulardan kichigi –18 ni tanlaymiz. Ushbu ustun hal qiluvchi ustun bo’ladi. Ozod sonlar va 2-ustun koifisientlari bo’yicha simpleks nisbatlarni qaraymiz. Bu nisbatlar lardan iborat. Eng kichik nisbatga mos element 6 ni bosh element sifatida tanlab olamiz.

				1
	6 2	1	3	1
		2	5	1
	-1	-1	-2	1
	-1	2	2	3
	-18	-1	-1	1

6 ga nisbatan simpleks almashtirishlarni bajarib, navbatdagi jadvalga o’tamiz.

				1
	-1./3	1/3	4/3	2/3
	1/6	1/3	5/6	1/6
	1/6	-2/3	-7/6	7/6
	1/6	7/3	17/6	19/6
	3	5	14	4

qatordagi barcha koifisientlar musbat bo’ldi. Demak, optimal echim topildi. 1-ustundagi larni ozod sonlarga tenglaymiz, 1–satrdagi larni 0 ga tenglaymiz, ning maksimal qiymati esa qatordagi oхirgi songa teng bo’ladi:

Yuqoridagi masalani Excel dasturi yordamida echamiz.

Berilgan masalaning koeffisientlarini jadvalga kiritib chiqamiz, o’zgaruvchilarning boshlang’ich qiymatlarini 0 ga tenglab olamiz: . Ushbu qiymatlar quyidagi jadvalning 7-qatorida berilgan.

Masalani echish uchun kursorni katakka qo’yib, tugmasini bosamiz. Natijada quyidagi muloqot oynasi hosil bo’ladi:

Hosil bo’lgan muloqot oynasida «Kатегория» bo’limida «Математическое» punktini tanlab, so’ng «Выберите функцию» bo’limida «СУММПРОИЗВ» funksiyasini tanlaymiz.

So’ngra «OK» tugmasini bosamiz. Natijada quyidagi muloqot oynasi хosil bo’ladi:

Хosil bo’lgan navbatdagi muloqot oynasida «Massiv 1» darchasidagi tugmachani bosib, diapazonidagi ma’lumotlarni, «Massiv 2» darchasidagi tugmachani bosib, diapazonidagi ma’lumotlarni kiritamiz, «Massiv 2» darchasidagi diapazonni fiksirlash uchun tugmasini bosamiz:

So’ngra «OK» tugmasini bosamiz va quyidagi oynada katakda hosil bo’lgan ma’lumotni diapazoniga nusхa qilamiz. Natijada jadval quyidagi ko’rinishga keladi.

Kursorni katakka o’rnatib, «Сервис–Поиск решение» buyrug’ini beramiz.

Natijada quyidagi «Поиск решения» muloqot oynasi hosil bo’ladi.

Hosil bo’lgan muloqot oynasida «Установить целевую ячейку» darchasiga katagini, «Изменяя ячейки» darchasiga diapazonini kiritamiz. «Ограничения» darchasiga o’tib «Добавить» tugmasini bosamiz.

Hosil bo’lgan muloqot oynasida «Ссылка на ячейки» darchasiga ni kiritamiz, tengsizlikni aniqlaymiz, «Ограничение» darchasiga ni kiritib, «Добавить» tugmasini bosamiz.

diapazondagi qolgan munosabatlarni ham shu tariqa kiritib chiqamiz. Oхirgi munosabatni kiritgandan keyin «OK» tugmasini bosamiz. Natijada «Poisk resheniya» muloqot oynasiga qaytamiz:

«Параметры» tugmasini bosamiz. Natijada quyidagi muloqot oynasi hosil bo’ladi:

Oynadagi «Неотрицательное значение» parametrini belgilaymiz va «OK» tugmasini bosib, «Поиск решения» muloqot oynasiga qaytamiz va «Выполнить» tugmasini bosamiz. Natijada quyidagi oynaga o’tamiz:

«OK» tugmasini bosamiz. Natijada echim quyidagi ko’rinishda ifodalanadi:

Rasmdan ko’rinib turibdiki, barcha cheklanishlar bajariladi va echim quyidagi ko’rinishda bo’ladi: .

Mustaqil echish uchun misollar:

Quyidagi chiziqli dasturlash masalalarini grafik va simpleks usulda eching:

1)		2)
3)		4)
5)		6)