1. Chiziqli tenglamalar tizimini yechish Chiziqli dasturlash masalasini yechishning grafik usuli Simpleks jadval usuli

x₁- x₂ =3
-5x₁-3x₂+x₃=-10
x₁+6x₂-x₃=5
x_{jError: Reference source not found}0, j=1,2,3
Z=8x₁+4x₂-2x₃ Error: Reference source not foundmax
Ye ch i sh. Ikki yoqlama masalani tuzamiz. U quyidagi ko‘rinishda bo‘ladi.
y₁+y₂-5y₃+y₄≥8
- y₂-3y₃+6y₄≥4
2y₁ +y₃ - y₄≥-2
F=4y₁+3y₂-10y₃+5y₄ Error: Reference source not foundmin

Masala shartlarini simpleks jadvalga kiritamiz.

BO‘	1	SO‘
		-y1	-y2	-y3	-y4
y5	-8	-1	-1	5	-1
y6	-4	0	1	3	-6
y7	2	-2	0	-1	1
F	0	-4	-3	10	-5

F qatorda musbat element (10 soni) mavjud, shu sabab bu son turgan ustun hal qiluvchi bo‘ladi. Bu ustunda ikkita musbat son mavjud, ulardan kattasini 5 sonini olamiz va F qator elementlarining shu qator elementlariga nisbatini qaraymiz, undan musbatlarining eng kichigini tanlaymiz, unga mos element hal qiluvchi bo‘ladi, ya'ni

Min|-4/-1; -3/-1; 10/5; -5/-1|=min{4; 3; 2; 5}=2

Demak, hal qiluvchi element 5 soniga teng. Simpleks almashtirish bajarib quyidagi jadvalga ega bo‘lamiz:

BO‘	1	SO‘
		-y1	-y2	-y5	-y4
y3	-8/5	-1/5	-1/5	1/5	-1/5
y6	4/5	3/5	8/5	-3/5	-27/5
y7	2/5	-11/5	-1/5	1/5	4/5
F	16	-2	-1	-2	-3

F qator elementlari barchasi manfiy, shu sabab ozod hadlar ustunini qaraymiz, unda manfiy element bor, u -8.5. Bu qator hal qiluvchi bo‘ladi. Yana F qator elementlarining shu qator elementlariga nisbatini qaraymiz, undan musbatlarining eng kichigini tanlaymiz, unga mos element hal qiluvchi bo‘ladi, ya'ni

Min|-2/-1/5; -1/1/5; -2/-1/5; -3/-1/5|=min{10; 5; -10; 15}=5.
Demak, hal qiluvchi element -1/5. Simpleks almashtirish bajarib quyidagi jadvalga ega bo‘lamiz:

BO‘	1	SO‘
		-y1	-y3	-y5	-y4
y2	8	1	-5	-1	1
y6	-12	-1	8	1	-7
y7	2	-2	-1	0	1
F	24	-1	-5	-3	-2

F qator elementlari barchasi manfiy, shu sabab ozod hadlar ustunini qaraymiz, unda manfiy element bor, u -12. Bu qator hal qiluvchi bo‘ladi. Yana F qator elementlarining shu qator elementlariga nisbatini qaraymiz, undan musbatlarining eng kichigini tanlaymiz, unga mos element hal qiluvchi bo‘ladi, ya'ni
Min|-1/-1; -5/8; -3/1; -2/7|=min{1; -5/8; -3; 2/7}=2/7.
Demak, hal qiluvchi element -7. Simpleks almashtirish bajarib quyidagi jadvalga ega bo‘lamiz:

BO‘	1	SO‘
		-y1	-y3	-y5	-y6
y2	44/7	6/7	-27/7	-6/7	1/7
y4	12/7	1/7	-8/7	-1/7	-1/7
y7	2/7	-15/7	1/7	1/7	1/7
F	192/7	-5/7	-51/7	-23/7	-2/7

Jadvaldan ko‘rinib turibdiki bu olingan plan optimal bo‘ladi. Demak, ikkilangan masalaning optimal yechimi y^*=(0; 44/7; 0; 12/7; 0; 0; 2/7), F_min=192/7.

Asosiy masala bilan ikkilangan masala o‘zgaruvchilari orasidagi bog‘lan-ishga ko‘ra ya'ni x_I↔y₅; x₂↔y₆; x₃↔y₇; x₄↔y₁; x₅↔y₂; x₆↔y₃; x₇↔y₄ asosiy masala yechimini ham topish mumkin , ya'ni x^*=(23/7; 2/7; 0; 5/7; 0; 5/7; 0) va Z_max=F_min bo‘lgani uchun Z_max=192/7.

Amaliy mashg‘ulot uchun misollar
Quyidagi chiziqli dasturlash masalasiga ikki yoqlama masala tuzing va uning birini yechib, ikkinchisining optimal yechimini aniqlang.

1. 2.

3. 4.

5. 6.

7. 8.

9. 10

7.Butun sonli dasturlash va uni yechish usuli
O‘zgaruvchilarga butun sonli bo‘lishlik sharti qo‘yilgan chiziqli dasturlash masalalariga butun sonli dasturlash masalasi deyiladi. Butun sonli dasturlash masalalariga sayyoh haqidagi masala, optimal jadval tuzish, transport vositalarini marshrutlashni optimallash, optimal joylashtirish masalasi va hokazolarni misol qilish mumkin.
Butun sonli dasturlash masalasi chiziqli dasturlash masalasidan qo‘shimcha shartlar bilan farq qiladi. Bu shartlarning qatnashishi butun sonli dasturlash masalasini yechish jarayonini qiyinlashtiradi. Natijada chiziqli dasturlash masalalarini yechish uchun qo‘llaniladigan usullarni butun sonli dasturlash masalalariga qo‘llash mumkin bo‘lmay qoladi.
Gomori usuli. Butun sonli dasturlash masalalarini yechish uchun uning xususiyatlarini e'tiborga oluvchi usullar yaratilgan bo‘lib, ulardan amerikalik olim R.Gomori yaratgan usul optimal yechimni beruvchi eng aniq usul hisoblanadi. Bu usulning g‘oyasi quyidagidan iborat. Berilgan butun sonli dasturlash masalasida noma'lumlarning butun bo‘lishlik shartiga e'tibor bermasdan, ularni oddiy chiziqli dasturlash masalasi sifatida simpleks usuldan foydalanib yechamiz.
Agar yechim butun sonlardan iborat bo‘lsa, u butun sonli dasturlash masalasining ham yechimi bo‘ladi. Aks holda noma'lumlarning butun bo‘lishlik shartini e'tiborga oluvchi va "kesuvchi tenglama" deb ataluvchi qo‘shimcha tenglama tuziladi.


Kesuvchi tenglamani tuzish.
1.Aytaylik, masaladagi sonlarning butun bo‘lishlik sharti tashlab yuborishdan hosil bo‘ladigan masala yechilgan va uning optimal yechimi mavjud bo‘lsin. Agar barcha x lar butun sonlar bo‘lsa, topilgan yechim butun sonli dasturlash masalaning yechimi bo‘ladi.
2.Faraz qilaylik, ba'zi x lar kasr sonlardan iborat bo‘lsin, ya'ni simpleks jadvaldagi ozod hadlar ustuni qiymatlari ichida kasr sonlar ham mavjud bo‘lsin. Ularning butun kismlarini [x] bilan belgilaymiz. U holda bu sonlarning kasr qismlari q lar quyidagicha aniqlanadi:
q_i=x_i-[x_i], q_ij=a_ij-[a_ij].
Faraz qilaylik, ba'zi q_i≠0 bo‘lsin. U holda, simpleks jadvalning tenglikni qanoatlantiruvchi k qatori uchun kesuvchi tenglama tuziladi. Buning uchun avval
q_k1x₁+ q_k2x₂+ …+ q_knx_n≥q_k
tengsizlik tuziladi, so‘ngra uni (-1) ga ko‘paytirib, x_n+1 qo‘shimcha o‘zgaruvchi kiritiladi.
-q_k1x₁- q_k2x₂- …- q_knx_n + x_n+1=q_k .
Bunday tuzilgan tenglama kesuvchi tenglama deyiladi.
3.Kesuvchi tenglamani simpleks jadvalning m+2 qatoriga joylashtiramiz va simpleks almashtirishlarni bajaramiz.
Agar hosil bo‘lgan yangi simpleks jadvalda barcha x_i lar butun sonli (ya'ni hamma q_i=x_i-[x_i]=0) bo‘lsa, topilgan yechim berilgan butun sonli dasturlash masalasining yechimi bo‘ladi. Aks holda yuqoridagi 2 va 3 punktlar yana takrorlanadi. Umuman bu jarayon masalaning butun sonli yechimi topulguncha yoki masalaning butun sonli yechimi mavjud emasligi aniqlanguncha takrorlanadi.
Misol. quyidagi chiziqli dasturlash masalasining butun sonli yechimini toping.

Masalani normal holga keltiramiz:

Masalani simpleks usulda yechamiz.

1.

BO‘	1	-x1	-x2
x3	6	2	3
x4	3	2	-3
Z	8	3	1

2.

BO‘	1	-x4	-x2		BO‘	1	-x4	-x3
x3	3	-1	6		x2	0.5	-0.17	0.17
x1	1.5	0.5	-1.5		x1	2.25	0.25	0.25
Z	3.5	-1.5	5.5		Z	0.75	-0.58	-0.92

Shunday qilib masalaning optimal plani topildi, lekin bu plan butun sonli emas. Birinchi tenglamaning kasr qismi eng katta bo‘lgani uchun, shu birinchi qatorga nisbatan kesuvchi tenglama tuzamiz:

Bu tengsizlikning ikki tomoniga (-1) ni ko‘paytirib, x₅ qo‘shimcha o‘zgaruvchini kiritamiz. Natijada quyidagiga ega bo‘lamiz:
, ya'ni
Bu oxirgi tenglamada barcha koeffitsientlarning butun qismlari nolga teng bo‘lgani sabab, ular o‘zgarishsiz qoladi. Uni jadvalning oxiriga joylashtiramiz.
4.

BO‘	1	-x4	-x3
x2	0.5	-0.17	0.17
x1	2.25	0.25	0.25
x5	-0.5	0.17	-0.17
Z	0.75	-0.58	-0.92

Simpleks almashtirish qilib quyidagi jadvalga ega bo‘lamiz.

BO‘	1	-x4	-x5
x2	0.0	0.0	1.0
x1	1.5	0.5	1.5
x3	3.0	-1.0	-6.0
Z	3.5	-1.5	-5.5

Endi simpleks jadvalning ikkinchi qatoriga nisbatan kesuvchi tenglamani tuzamiz.
Bu tengsizlikda koeffitsientlar butun qismi noldan katta bo‘lgani sabab q_i=x_i-[x_i], q_ij=a_ij-[a_ij] lardan foydalanib ularning kasr qismini ajratamiz, ya'ni
q₂=1.5-[1.5]=1.5-1=0.5, q₂₄=1.5-[1.5]=1.5-1=0.5.
Tengsizlikning ikki tomoniga (-1) ni ko‘paytirib, x₆ qo‘shimcha o‘zgaruvchini kiritamiz.
Natijada quyidagiga ega bo‘lamiz:
, ya'ni
Uni jadvalning oxiriga joylashtiramiz.
5.

BO‘	1	-x4	-x5
x2	0.0	0.0	1.0
x1	1.5	0.5	1.5
x3	3.0	-1.0	-6.0
x6	-0.5	-0.5	-0.5
Z	3.5	-1.5	-5.5

Simpleks almashtirishlar qilib quyidagi jadvalga ega bo‘lamiz.

BO‘	1	-x6	-x5
x2	0.0	1.0	0.0
x1	1.0	1.0	1.0
x3	4.0	-5.0	-2.0
x4	1.0	1.0	-2.0
Z	5.0	-4.0	-3.0

Hosil bo‘lgan simpleks jadvalda ozod hadlar ustuni elementlari butun sonlardan iborat. Demak, butun sonli dasturlash masalasi yechimi X=(1,0,4,1) bo‘ladi va Z_min=5.
Amaliy mashg‘ulot uchun misollar
Quyidagi chiziqli dasturlash masalasining butun yechimlarini aniqlang.
1. 2.

3. 4.

5. 6.

7. 8.

9. 10.

Foydalanilgan adabiyotlar


1.Акулич И.Л. Математическое программирование в примерах и задачах. - М.: Высшая школа, 1996.
2.Badalov F.B. Optimallash nazariyasi va matеmatik dasturlash. “O‘qituvchi”, T. 1989 y.
3.Кузнецов А.В., Новикова Г.И., Холод Н.И. Сборник задач по математическому программированию. Минск, Вышэйшая школа, 1985.
4.Курицкий Б.Я. Поиск оптимальных решений средствами Excel. “Санкт-Перербург”, 1997г.
5.Safaеva K., Bеknazarova N. Opеratsiyalarni tеkshirishning matеmatik usullari. “O‘qituvchi”, 1984y. 1 qism.
6.Лесин В.В., Лисовец Ю.П. Основы методов оптимизации. М. Изд. МАИ 1998.
7.Хазанова Л.Э. Математическое моделирование в эканомике. М. БЕК, 1998.