Cj
|
Bi
|
x1
|
x2
|
…
|
xn
|
y1
|
y2
|
…
|
ym
|
|
s1
|
s2
|
…
|
sn
|
s n+1
= 0
|
sn+2
= 0
|
…
|
sm
= 0
|
y1
|
sn+1
|
b1
|
a11
|
a12
|
…
|
a1n
|
1
|
0
|
…
|
0
|
|
y2
|
s n+2
|
b2
|
a21
|
a22
|
…
|
a2n
|
0
|
1
|
…
|
0
|
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
ym
|
sm
|
bm
|
am1
|
am2
|
…
|
amn
|
0
|
0
|
…
|
1
|
|
Zj - Cj
|
0
|
- s1
|
- s2
|
…
|
- sn
|
0
|
0
|
…
|
0
|
|
Bazis bo’lmagan y1, y2, ... , ym 0 noma’lumlar «Bazis o’zgaruvchilar» ustuniga yoziladi.
Bazismas noma’lumlarning sn+1, sn+2, ... , sm koeffistientlari «Si» ustuniga yoziladi.
b1, b2, ... , bm ozod hadlar «Bi» ustuniga yoziladi.
Zmax =c1x1+c2x2+...+cnxn+0y1+0y2+...+0ym maqsad funksiyaning koeffistientlari Zj - Cj qatorga qarma - qarshi ishora bilan yoziladi. Bu qator indeks qator deb yuritiladi.
CHDM ning simpleks jadvalida Zj - Cj indeks qatoridagi hamma noma’lumlarning koeffistientlari musbat bo’lsa masala optimal yechimga ega bo’ladi. Simpleks usuli bilan CHDMni optimal yechimini topishda Zj - Cj indeks qatoridagi hamma noma’lumlarning koeffistientlari musbat ishoraga keltirish maqsad qilib qo’yiladi.
Simpleks jadvalida Zj - Cj indeks qatoridagi noma’lumlarining koeffistientlaridan bittasi yoki bir nechtasi manfiy bo’lganida hal qiluvchi elementni tanlashda quyidagi munosabatlar amalga oshishi mumkin.
Simpleks jadvalida hal qiluvchi ustunni (HQU) tanlash.
Agar Zj - Cj indeks qatoridagi x1, x2, ... , xn noma’lumlarning s1, s2, ..., sn koeffistientlardan birortasi manfiy ishorali son bo’lsa, shu manfiy ishorali son to’rgan ustun HQU bo’ladi.
Agar Zj - Cj indeks qatorida bunday manfiy sonlar bir nechta bo’lsa, u vaqtda HQUni tanlash uchun shu manfiy sonlarning absolyut qiymatlari bo’yicha eng kattasi olinadi. Bu sonlar ichida, ulardan bir nechtasi bir - biriga teng bo’lsa, u holda ulardan hohlagan birini olib bosh ustun uchun tanlanadi.
Simpleks jadvalida hal qiluvchi satrni (HQS) tanlash.
Simpleks jadvalida HQSni tanlash uchun Bi ozod hadlar ustunidagi hamma sonlarni (agar ularning ishorasi bir xil bo’lsa) HQUdagi mos kelgan sonlarga bo’lib, ulardan eng kichigi tanlanadi. Bu qiymat simpleks jadvadagi ustunga yoziladi. Bunday kichik sonlar bir nechta bo’lsa, ulardan xohlagan birini HQS qilib tanlash mumkin.
Simpleks jadvalini hal qiluvchi elementi (HQE) .
Simpleks jadvalidagi HQU va HQS ning kesishgan kattagidagi son hal qiluvchi element (HQE) bo’ladi.
Yangi simpleks jadvaliga o’tish.
Hal qiluvchi ustun, hal qiluvchi satr va hal qiluvchi element topilgach yangi simpleks jadvalidagi hamma sonlar Jordan chiqarish usuli yordamida topiladi, ya’ni:
hal qiluvchi satrdagi hamma elementlar hal qiluvchi elementga bo’linadi va ishorasi o’zgartirilmasdan yoziladi;
hal qiluvchi ustundagi qolgan hamma elementlar o’rniga nol yoziladi;
qolgan hamma elementlar quyidagi to’g’ri to’rtburchak formulasi yordamida topiladi:
yoki . (Bu yerda i ≠ r,j≠ k)
ark element o’rnida hosil qilinadigan brk elementni to’g’ri to’rtburchak formulasi bilan topish uchun:Jordan jadvalidan fragment 2.1.3-jadval
…
|
…
|
j- hal qiluvchi ustun
|
…
|
k-ustun
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
i–hal qiluvchi satr
|
…
|
[ aij ]
hal qiluvchi element
|
…
|
aik (i -satr va k –ustunda joylashgan element)
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
r – satr
|
…
|
arj r-satr va j –ustunda joylashgan element
|
…
|
ark r-satr va k –ustunda joylashgan element
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
Bu jarayon Zj-Cj indeks qatoridagi hamma noma’lumlarning koeffistientlari musbat bo’lguncha davom ettiriladi.
Xulosa:
Chiziqli dasturlash masalalari, matematikning o'zining optimallashga oid bo'lgan qismini tahlil qiladi. Bu turdagi masalalarda, biron bir maqsadni (masalan, hisob kitob yoki ishlab chiqarish uchun ishchi narxlari) optimallashtirish uchun har qanday cheklovlar va cheklov shartlarini yechish talab qilinadi.
Simpleks usul, chiziqli dasturlashning asosiy algoritmlaridan biri hisoblanadi. Ushbu usul, lineyni chiziqli dasturlash masalalarini yechishda ishlatiladi. Bu usulda, chiziqli funksiyani boshqa bir funksiya (maqsad funksiyasi)ga aylantiriladi, shuningdek, funksiyaning cheklov shartlari to'g'risida ham e'tibor qaratiladi.
Masala o'z ko'rinishida ko'pgina cheklov shartlarining bo'lishi mumkin. Simpleks usulidan foydalanish orqali, eng yaxshi natija olish uchun qanday yo'nalishda harakat qilish kerakligini aniqlash uchun yuqori darajada yechim topish davom etadi.
Simpleks usuli chiziqli dasturlashga oid ko'p mashhur algoritmlardan biri bo'lib, uni matematik, iqtisodiyot, kimyo, va boshqa sohalarda muhim masalalarni yechishda foydalaniladi.
Foydalanilgan adabiyotlar
1. Ne’matov A. Va b. “Matematik dasturlash va optimallash usullari”. Uslubiy qo’llanma. T.: TTYESI bosmaxonasi, 2008. 98 bet.
2. Nazirov Sh.A., Musayev M.M. va b. Delphi tilida dasturlash asoslari. O’quv qo’llanma. Toshkent-2008. 277 bet.
3. Ковалев М.Я. Примеры решения типичных задач по курсу « Исследований операций ». Минск 2004. 284 с.
|
