Tayanch reja:
Tayanch reja uchun (1) shartlardagi noma’lumlar o’rniga nol qiymat qo’yib bazis o’zgaruvchi lar topiladi.
Berilgan ma’lumotlar asosida simpleks jadvalini tuzamiz:
Bazis o’zgaruvchilar
|
Ozod hadlar
|
x1
|
x2
|
…
|
xn
|
xn+1
|
xn+2
|
…
|
xn+m
|
xn+1
|
b1
|
a11
|
a12
|
…
|
a1n
|
1
|
0
|
…
|
0
|
xn+2
|
b2
|
a21
|
a22
|
…
|
a2n
|
0
|
1
|
…
|
0
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
xn+m
|
bm
|
am1
|
am2
|
…
|
amn
|
0
|
0
|
…
|
1
|
F
|
c0
|
c1
|
c2
|
…
|
cn
|
0
|
0
|
…
|
0
|
Topshiriq
Variant №5: Quyidagi chiziqli dasturlash masalalarini grafik va simpleks jadvallar usulida yeching:
‒ Grafik usul.
1)
Tengsizliklar sistemasini tenglamalar sistemasi ko’rinishida yozib, ularga mos kelgan to’g’ri chiziqlarni chizaylik:
L1:
L2:
L1, L2 lar – to’g’ri chiziqlarning koordinata o’qlari bilan kesishish nuqtalarining koordinatalari (0;2), (3;0), (0;1) va (4;0).
Tengsizliklar belgisi “≤”, shuning uchun bu tengsizliklar sistemasi yechimlari L1, L2 to’g’ri chiziqlar ostida joylashgan (bu to’g’ri chiziqlar ham kirgan holda).
Koordinatalari maqsad funksiyamizning koeffitsientlari bo’lgan {1;1,5} vektorni quramiz. Ushbu vektorga perpendikulyar bo’lgan to’g’ri chiziqni (qizil chiziq) pastki chap burchakdan o'ng yuqori burchakka suramiz.
To’g’ri chiziq aniqlanish sohasini birinchi marta kesib o’tgan nuqtada maqsad funksiya o’zining eng kichik qiymatiga erishadi.
To’g’ri chiziq aniqlanish sohasini oxirgi marta kesib o’tgan nuqtada maqsad funksiya o’zining eng katta qiymatiga erishadi.
Maqsad funksiya eng katta qiymatiga C nuqtada erishadi. C nuqta bir vaqtning o’zida L1, L2 to’g’ri chiziqlarga tegishli. Tenglamalar sistemasini tuzamiz:
→
Maqsad funksiyaning C (2,4;0,4) nuqtadagi qiymatini topamiz:
.
Maqsad funksiya L1 to'g'ri chiziqqa parallel bo'lganligi sababli, u DC kesmada bir xil maksimal qiymatga ega bo'ladi. D nuqtaning koordinatalarini aniqlash uchun quyidagi tenglamalar sistemasini yechamiz:
→
Maqsad funksiyamizning maksimal qiymatini topamiz:
.
‒ Simpleks usul.
2) (1)
(2)
(3)
(2) ning chap tomoniga manfiy bo’lmagan va hozircha noma’lum bo’lgan x3, x4 o’zgaruvchilarni qo’shib, tengsizliklar sistemasidan tenglamalar sistemasiga o’tamiz:
(4)
Endi (4) ni quyidagi ko’rinishda yozib olamiz:
(5)
Bu yerda x3, x4 lar bazislar (bazis o’zgaruvchilar), x1, x2 lar esa ozod noma’lumlar bo’ladi. Shuning uchun , desak, (5) ning manfiy bo’lmagan , yechimlari kelib chiqadi. Demak, birinchi bazis yechim , , , lar orqali ifodalanar ekan.
(1) dan ko’rish qiyin emaski, birinchi rejaga, ya’ni birinchi bazis yechimga ko’ra olinadigan foyda bo’lar ekan. Endi birinchi bazis yechimga mos kelgan birinchi simpleks jadvalini tuzamiz. Kelajakda bizga qulay bo’lishi uchun (4) ni quyidagi ko’rinishda yozib olamiz:
1-jadval
Bazis o’zgaruvchilar
|
Ozod hadlar
|
x1
|
x2
|
x3
|
x4
|
x3
|
1
|
1
|
2
|
1
|
0
|
x4
|
1
|
2
|
1
|
0
|
1
|
F
|
0
|
-2
|
-3
|
0
|
0
|
Bizda qo’yilgan masalaning eng katta qiymati izlanayotgani uchun, 1-jadval oxirgi yo’l elementlarining ichidan eng kichik manfiy son -3 ni olamiz (agar qo’yilgan masakaning eng kichik qiymati izlanayotgan bo’lsa, u holda oxirgi yo’l elementlari ichidan eng kichik musbat son olingan bo’lar edi). Bu -3 turgan ustun hal qiluvchi ustun bo’ladi. Endi ozod had elementlarini mos ravishda hal qiluvchi manfiy bo’lmagan ustun elementlariga bo’lib, ularning eng kichigini olamiz:
.
2 turgan yo’l hal qiluvchi yo’l, 2 ning o’zi esa hal qiluvchi element bo’ladi.
Endi hal qiluvchi elementni 1 ga aylantirib olamiz: buning uchun hal qiluvchi yo’l elementlarini 2 ga bo’lamiz:
Bazis o’zgaruvchilar
|
Ozod hadlar
|
x1
|
x2
|
x3
|
x4
|
x3
|
1/2
|
1/2
|
1
|
1/2
|
0
|
x4
|
1
|
2
|
1
|
0
|
1
|
F
|
0
|
-2
|
-3
|
0
|
0
|
Endi hal qiluvchi ustun elementlarini hal qiluvchi elementdan tashqarisini nolga aylantiramiz: ikkinchi simpleks jadvalini tuzish uchun birinchi yo’l elementlarini -1 ga ko’paytirib, ikkinchi yo’l elementlariga, so’ngra 3 ga ko’paytirib, uchinchi yo’l elementlariga qo’shamiz.
Hal qiluvchi element, bazis noma’lum x3 turgan yo’l va ozod noma’lum x2 turgan ustunning kesishish joyida turgani uchun, bazis o’zgaruvchi x3 ning o’rniga x2 olsak, natijada bazis o’zgaruvchilar x2, x4 bo’ladi.
2-jadval
Bazis o’zgaruvchilar
|
Ozod hadlar
|
x1
|
x2
|
x3
|
x4
|
x2
|
1/2
|
1/2
|
1
|
1/2
|
0
|
x4
|
1/2
|
3/2
|
0
|
-1/2
|
1
|
F
|
3/2
|
-1/2
|
0
|
3/2
|
0
|
Ikkinchi simpleks jadvalidan ko’rinadiki, ikkinchi bazis yechim
, , ,
bo’lib, maqsad funksiyamiz esa
ko’rinishda bo’ladi. Bundan ko’rinadiki, maqsad funksiyaning qiymatini x1 hisobiga oshirish mumkin. Ikkinchi jadvalga e’tibor bersak, F turgan yo’lda manfiy son faqat bitta . Shuning uchun, bu turgan ustun hal qiluvchi ustun bo’ladi. Hal qiluvchi elementni esa avvalgicha aniqlaymiz:
.
Demak, turgan yo’l hal qiluvchi yo’l bo’lib, ning o’zi esa hal qiluvchi element bo’ladi.
Bazis o’zgaruvchi x4 ning o’rniga esa x1 o’tadi. Avvalgidek hal qiluvchi elementni 1 ga aylantirib olib, so’ngra hal qiluvchi ustun elementlarini (hal qiluvchi elementdan tashqari) nolga aylantirib, 3-simpleks jadvalini tuzamiz: ikkinchi yo’l elementlarini ga ko’paytirib, birinchi yo’l elementlariga, so’ngra ga ko’paytirib, uchinchi yo’l elementlariga qo’shamiz.
Bazis o’zgaruvchilar
|
Ozod hadlar
|
x1
|
x2
|
x3
|
x4
|
x2
|
1/2
|
1/2
|
1
|
1/2
|
0
|
x1
|
1/3
|
1
|
0
|
-1/3
|
2/3
|
F
|
3/2
|
-1/2
|
0
|
3/2
|
0
|
3-jadval
Bazis o’zgaruvchilar
|
Ozod hadlar
|
x1
|
x2
|
x3
|
x4
|
x2
|
1/3
|
0
|
1
|
2/3
|
-1/3
|
x1
|
1/3
|
1
|
0
|
-1/3
|
2/3
|
F
|
5/3
|
0
|
0
|
4/3
|
1/3
|
3-simpleks jadvalining oxirgi yo’lida manfiy elementlar yo’q, shuning uchun maqsad funksiyaning qiymatini oshirish mumkin emas. Demak, qo’yilgan masalaning yechimi , bo’lib, bo’ladi.
Dastur:
#include
#include
#include
//Rustamov Olimjon 210-19
using namespace std;
#define MAX_ROWS 11
#define MAX_COLS 32
int rows;
int cols;
int bas[MAX_ROWS];
double mat[MAX_ROWS][MAX_COLS];
bool InputSize();
void InputMatrix();
void InputFunction();
void SetIndexString();
void Show();
bool CheckIsComp();
int FindMasterCol();
void ShowResult();
int FindRow(int col);
void Gauss(int col, int row);
int main(){
if (!InputSize()){
cout<<"Invalid sizes!";
cin.get();
return 0;
}
InputMatrix();
InputFunction();
SetIndexString();
Show();
while (true){
if (!CheckIsComp()){
cout<
break;
}
int col=FindMasterCol();
if (!col){
cout<
ShowResult();
break;
}
int row=FindRow(col);
Gauss(col,row);
Show();
};
return 0;
}
bool InputSize(){
int c=MAX_ROWS-2;
cout<<"Number of equations: ";
cin>>rows;
if (rows>c) return false;
c=MAX_COLS-2-c;
cout<<"Number of variables: ";
cin>>cols;
return cols <= c;
}
void InputMatrix(){
for (int i=1; i<=rows; i++){
for (int j=2; j<=cols+2; j++){
if (j == cols+2){
cout<<"Enter equation-"<
cin>>mat[i][j];}}
}
cols+=rows;
for (int i=1; i<=rows; i++) mat[i][1]=mat[i][cols+2];
}
void InputFunction(){
for(int j=2; j<=cols+1-rows; j++){
cout<<"Enter function: x["<
cin>>mat[0][j];}
}
void SetBasis(){
for (int i=1; i<=rows; i++){
bas[i]=++cols;
mat[i][bas[i]+1]=1;}
}
void SetIndexString(){
mat[rows+1][1]=0;
for (int i=1; i<=rows; i++) mat[rows+1][1]=mat[rows+1][1]+mat[i][1]*mat[0][bas[i]+1];
for (int j=2; j<=cols+1; j++) mat[rows+1][j]=0;
for (int j=2; j<=cols+1; j++){
for (int i=1; i<=rows; i++) mat[rows+1][j]=mat[rows+1][j]+mat[i][j]*mat[0][bas[i]+1];
mat[rows+1][j]=mat[rows+1][j]-mat[0][j];}
}
void Show(){
cout<
for (int i=0; i<=rows+1; i++){
if (!i) cout<
else if (i==rows+1) cout<
else cout<
for(int j=1; j<=cols+1; j++){
if (i==0){
if (j==1) cout<
else cout<
}
else{
cout<
}
bool CheckIsComp(){
for (int j=2; j<=cols+1; j++){
if (mat[rows+1][j]<0){
bool is=false;
for (int i=1; i<=rows; i++) is |= mat[i][j]>=0;
if (!is) return false; }
}
return true;
}
int FindMasterCol(){
int col;
int count=0;
for (int i=1; i<=cols; i++) if (mat[rows+1][i+1]>=0) count++;
if (count == cols) return 0;
double min=0;
for (int i=1; i<=cols; i++) if (mat[rows+1][i+1]<=min){min=mat[rows+1][i+1]; col=i;}
return col;
}
void ShowResult(){
cout<
for (int i=1; i<=rows; i++){
cout<
if (i!=rows) cout<<", ";
}
cout<<")\nF(x) = "<
}
int FindRow(int col){
bool ok=false;
int row;
double min_row;
for (int i=1; i<=rows; i++) if (mat[i][col+1]>0) {ok=true; min_row=mat[i][1]/mat[i][col+1]; row = i; break;}
if (!ok) return 0;
for (int i=1; i<=rows; i++){
if (mat[i][col+1] > 0){
double a=mat[i][1]/mat[i][col+1];
if (a
min_row=a;
row=i;}}
}
return row;
}
void Gauss(int col, int row){
for (int i=row+1; i<=rows+1; i++){
double min_one=-1;
double mnog=min_one*mat[i][col+1]/mat[row][col+1];
for (int j=1; j<=cols+1; j++) mat[i][j]=mat[i][j]+mat[row][j]*mnog;
}
for (int i=row-1; i>=1; i--){
double min_one(-1);
double mnog=min_one*mat[i][col+1]/mat[row][col+1];
for (int j=1; j<=cols+1; j++) mat[i][j]=mat[i][j]+mat[row][j]*mnog;
}
double del=mat[row][col+1];
for (int j=1; j<=cols+1; j++) mat[row][j]=mat[row][j]/del;
bas[row]=col;
}
Natija:
XULOSA
Xulosa qilib shuni aytish mumkinki, simpleks usuli algoritmi juda qiziq va dasturlashning umumiy tomonlarini qamrab olgan ekan. Simpleks usuli bo’yicha bir nechta jadvallar hosil qilinadi. Ana shu jadvallarda simpleks usuli uchun kerakli ma’lumotlar kiritiladi.
Chiziqli dasturlashning asosiy masalasini geometrik usulda yechganda tenglamalar sistemasiga va maqsad funksiyasiga kiruvchi o’zgaruvchilar soni qancha kam bo’lsa, masalani yechish shuncha osonlashadi. Agar o’zgaruvchilar soni juda ko’p bo’lsa, masalan qavariq shakl uchlarining soni bir necha million bo’lsa, u holda maqsad funksiyasining eng katta (eng kichik) qiymatlarini topish hozirgi zamon hisoblash mashinalariga ham o’g’irlik qiladi.
Shu kabi, ko’p o’zgaruvchili chiziqli dasturlash masalalarini yechish uchun maxsus usullar ishlab chiqish lozimki, ko’pyoqning uchlarini tanlash tartibsiz emas, balki maqsadli ravishda amalga oshirilsin. Chiziqli dasturlashning shu ko’rinishdagi masalalarini yechish uchun maxsus analitik usul – simpleks usuli yaratilgan.
Do'stlaringiz bilan baham: |