Chiziqli dasturlash masalalarini yechishning geometrik talqini


Download 297.8 Kb.
bet4/5
Sana13.04.2023
Hajmi297.8 Kb.
#1354708
1   2   3   4   5
Bog'liq
Chiziqli dasturlash masalalarini yechishning geometrik ma\'nosi

brs

. . .

brn

. . .

. . .

. . .

. . .

. . .

. . .

. . .

. . .

ym

bm0

bm1

bm2

. . .

bms

. . .

bmn

Z

b00

b01

b02

. . .

b0s

. . .

b0n

Chiziqli dasturlash masalasini simpleks usul yordamida yechish ikki bosqichdan iborat:


1.Boshlang‘ich tayanch planni topish.
2.Tayanch planlar ichidan masalaning optimal planini topish.
Masalaning tayanch planini tuzish.
Boshlang‘ich tayanch planni topish quyidagi algoritm bo‘yicha bajariladi:
1.Simpleks jadvaldan hal qiluvchi elementni topish:
1.1.Hal qiluvchi elementni topish oldin hal qiluvchi ustunni topishdan boshlanadi. Buning uchun ozod hadlar ustuniga qaraladi. Agar ozod xadlar ustunidagi elementlar hammasi musbat bo‘lsa, bu boshlang‘ich plan tayanch plan bo‘ladi va ikkinchi etapga o‘tiladi. Agar manfiy element mavjud bo‘lsa, ulardan modul bo‘yicha eng kattasi tanlanadi (agar bitta bo‘lsa shu element o‘zi olinadi). Misol uchun aytaylik bu element br0 bo‘lsin. Shu br0 element turgan r satr qaraladi. Agar satr elementlaridan hammasi musbat bo‘lsa, masalaning yechimi mavjud bo‘lmaydi (bu holda hisoblashlar shu joyda to‘xtatiladi). Agar satrda manfiy element mavjud bo‘lsa, ulardan modul bo‘yicha eng kattasi tanlanadi (agar bitta bo‘lsa o‘zi olinadi). Shu element turgan ustun hal qiluvchi ustun deyiladi. Misol uchun bu s-chi ustun bo‘lsin.
1.2.Hal qiluvchi satr topiladi. Ozod xadlarni hal qiluvchi ustun elementlariga bo‘lib chiqiladi va ulardan musbatlarining eng kichigi tanlanadi, ya'ni
.
Aytaylik, bu nisbatlar ichida musbatlarning eng kichigi br0/brs bo‘lsin. U holda shu brs element turgan satr hal qiluvchi satr deyiladi, brs elementning o‘zi esa hal qiluvchi element bo‘ladi.
2.Hal qiluvchi ustun va satr o‘zgaruvchilari o‘rinlari almashtiriladi, (ya'ni xs va ys yangi jadvalda o‘rinlari almashadi).
3.Jadvalda simpleks almashtirish bajariladi.
3.1.Hal qiluvchi ustun elementlari hal qiluvchi elementga bo‘lib chiqilib yangi jadvalga yoziladi, ya'ni .
3.2.Hal qiluvchi satr elementlari hal qiluvchi elementga bo‘lib chiqilib yangi jadvalga yoziladi, ya'ni .
3.3.Hal qiluvchi element 1 ga tenglashtirilib o‘ziga bo‘linadi, ya'ni .
3.4.Yangi simpleks jadvalning qolgan elementlari quyidagi formula orqali topiladi.
ёки
Yangi jadvalda bґij -elementni hisoblashda eski jadvaldan bij, bis ,brj, brs elementlarini topish quyidagicha bo‘ladi:

Download 297.8 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling