|
Misollar. 1. (1)
sistema uchun formaning minimum topilsin.
Yechish. va – bazis noma`lumlar, va esa ozod noma`lumlar. da (1) dan kelib chiqadi. Shunday qilib, M bazisning o’rinli yechimiga ega bo’lamiz.
formaning bu yechimga mos qiymati bo’ladi.
Endi, da bo’lgani uchun I holga egamiz. Masalan, va ga mos o’rinli yechimda bo’ladi. Shu sababli, f ning minimum bo’lib, unga mos (2, 1, 0, 0) yechim optimaldir.
2.
cheklanish tenglamalar berilgan bo’lib, formani minimumlashtiraylik. Bu yerda bazis noma`lumlar va – ozod noma`lumlardir. qiymatlarda (1) dan ni hosil qilamiz. Demak, o’rinli yechimga qiymat mos keladi. formada, masalan, va deb olsak, (1) dan hosil bo’ladi. Bunda ga ko’ra II B holga kelamiz. Demak, bo’lib, 1 son hal qiluvchi elementni ifodalaydi.
(1) ning ikkinchi tenglamasinin ga nisbatan yechim va ni birinchi tenglamaga qo’yib, quyidagi yangi sistemani hosil qilamiz:
Bunda – yangi bazis va ozod noma`lumlar. f ning unga mos quyidagi ifodasini topamiz:
Endi, deb, ga istalgancha katta musbat qiymatni bersak, bo’ladi, ya`ni f forma minimumga erishmaydi.
3.
sistema va forma berilgan bo’lib, f ni minimumlashtirish talab qilinadi.
Yechish. (1) ning ikkinchi tenglamasini ga va birinchisini ga nisbatan yechamiz:
Bundan
sistemani hosil qilamiz. (2) dan va larning ifodalarini f ga qo’yib, quyidagini hosil qilamiz:
Endi (2) ni quyidagi shaklda yozamiz:
qiymatlarda (4) dan larni topamiz. Demak, (4) sistemani ushbu (0, 2, 0, 5, 0) o’rinli yechimga ega bo’ladi. bu yechimda f ning qiymati 5 ga teng
(3) da dir. Shu sababli f ning minimumini, (0, 2, 0, 5, 0) esa optimal yechimni ifodalaydi.
4-§. Simpleks jadvallar
Biror masalaning yechimini simpleks usul yordamida topish bir qancha bosqichlardan iborat ekanligi bizga maʼlum. Shu bosqichlarning hammasini simpleks jadvallar yordamida bajarish mumkin. Buni quyidagi misollarda ko‘rib o‘tamiz:
sistemaning manfiymas yechimlari orasida
formaga minimum qiymat ta`minlovchi yechim topilsin.
Yechim. (1) va (2) larni birgalikda olib, quyidagi sistemaga ega bo'lamiz
(2) sistemani larga ko’ra osongina yechish mumkin. Shuning uchun bu noma`lumlarni (1) sistemaning bazis noma`lumlari deb qabul qilamiz.
Bazis nomaʼlumlarni jadvalning 1-ustuniga, ozod hadlarni 2- ustuniga, ning koeffitsiyentlarini 3- ustuniga va hokazo, ning koeffitsiyentlarini oxirgi ustuniga yozib. quyidagi jadvalga ega bo’lamiz:
1-jadval
Bazis noma`lumlar
|
Ozod hadlar
|
|
|
|
|
|
|
1
|
1
|
0
|
0
|
1
|
-2
|
|
2
|
0
|
1
|
0
|
-2
|
1
|
|
3
|
0
|
0
|
1
|
3
|
1
|
f forma
|
0
|
0
|
0
|
0
|
-1
|
1
|
f formaga minimum qiymatni beruvchi optimal yechimni topish uchun { } bazisdan boshqa bazisga o‘tish lozimligini bilamiz. Bu ish jadvallar yordamida quyidagicha bajariladi:
a) f formaga mos keluvchi satr elementlari orasida musbati bo‘lsa, shu element joylashgan ustun elementlaridan musbatlarini belgilab olamiz. Bizning misolimizda oxirgi, yaʼni f formaning satrida bitta musbat 1 element bor. Bu element joylashgan oxirgi ustunda 1 dan tashqari yana ikkita musbat 1, 1 elementlar mavjud. Ular 2 va 3- satrlarda joylashgan;
b) ajratilgan musbat 1, 1 elementlar bilan bitta satrda joylashgan ozod hadlarning shu 1, 1 larga nisbatlarini tuzamiz. Bizda bu nisbatlar = 2 va = 3 buladi;
c) tuzilgan nisbatlardan eng kichigining maxraji hal qiluvchi element buladi. 1-jadvalda hal qiluvchi element to‘garakcha ichiga olingan;
d) hal qiluvchi element 0 ga teng bo‘lmasa, uni 1 ga teng qilib olish mumkin. Buning uchun shu element joylashgan satrning barcha elementlarini ga bo‘lish kifoya;
e) 1-jadval satrlarining elementlarini shunday o‘zgartiramizki, natijada hal qiluvchi 1 element turgan ustundagi shu elementdan boshqalari 0 larga aylansin. Buning uchun 1-jadvalning ikkinchi satrini larga ko‘paytirib, mos ravishda 1, 3, 4 satrlarga qo‘shamiz. Buning natijasida x2 joylashgan ustunning to‘rtinchi satrida —1 hosil bo‘lgani uchun ni bazisdan chiqarib tashlab, uning o‘rniga ni kiritamiz. U holda quyidagi yangi jadval kelib chiqadi:
2 – jadval
Bazis noma`lumlar
|
Ozod hadlar
|
|
|
|
|
|
|
5
|
1
|
0
|
0
|
-3
|
0
|
|
2
|
0
|
1
|
0
|
-2
|
1
|
|
1
|
0
|
-1
|
1
|
5
|
1
|
f forma
|
2
|
0
|
1
|
0
|
1
|
0
|
yuqorida qilingan ish natijasida avvalgi { , , } bazisdagi o‘rniga keladi va 2-jadvalda ko‘rsatilgandek, yangi { } bazis hosil bo‘ladi.
2- jadvalning oxirgi satrida faqatgina bitta musbat element mavjud bo‘lib, u joylashgan ustundadir. Shu ustunda yana bitta musobat element 5 bor. Uni hal qiluvchi element deb hisoblab, uchinchi bazisga kiritamiz. Bu ishning natijasi quyidagi jadvalda ko‘rsatilgandir:
3 – jadval
Bazis noma`lumlar
|
Ozod hadlar
|
|
|
|
|
|
|
|
1
|
|
|
0
|
0
|
|
|
0
|
|
|
0
|
1
|
|
|
0
|
|
|
1
|
0
|
f forma
|
|
0
|
|
|
0
|
0
|
3 – jadvalning ohirgi satrida birorta ham musbat element qolmadi. Demak, topilgan ( yechim optimal bo’lib, unga mos keluvchi f formaning minimum ga teng, ya`ni
sistemaning yechimlari orasida formaga minimum qiymat ta`minlovchi yechim topilsin.
Do'stlaringiz bilan baham: |
