Muhammad al-Xorazmiy nomidagi Toshkent axborot texnalogiyalari Universiteti mustaqil ish

Muhammad al-Xorazmiy nomidagi

Toshkent axborot texnalogiyalari

Universiteti

MUSTAQIL ISH

Gurux: 512-20

Fakultet: TTF

Fan: Diffirensial tenglamalar

Bajardi: Asqaraliyev Akbarali

Mavzu: Chiziqli dasturlash masalalari. Chiziqli dasturlash masalalarini yechisning simpleks usulini C++ da bajarish(ammiq bitta misolda ko’rsatish)

REJA:

1. 
   Simpleks usulining maazmun ahamiyati.
   
2. 
   Simpleks jadvalini tuzish.
   
3. 
   Chiziqli dasturlash masalalarini simpleks usulida yechish.
   
4. 
   C++ da simpleks usulida misoldan namuna.
   

Breilgan misol: Max: z = 0.5*x + 3*y + z + 4*w,

x + y + z + w <= 40 .. b1

-2x - y + z + w <= 10 .. b2

y - w <= 10 .. b3

#include

#include

#include

#include

#include

#define M 20

#define N 20

static const double epsilon = 1.0e-8;

int teng(double a, double b) { return fabs(a-b) < epsilon; }

typedef struct {

int m, n; // m=rows, n=columns, mat[m x n]

double mat[M][N];

} doska;

void nl(int k){ int j; for(j=0;jvoid misolni_kursatish(doska *tab, const char* mes) {

static int counter=0;

int i, j;

printf("\n%d. berilgan %s:\n", ++counter, mes);

nl(70);

printf("%-6s%5s", "col:", "b[i]");

for(j=1;jn; j++) { printf(" x%d,", j); } printf("\n");

for(i=0;im; i++) {

if (i==0) printf("max:"); else

printf("b%d: ", i);

for(j=0;jn; j++) {

if (teng((int)tab->mat[i][j], tab->mat[i][j]))

printf(" %6d", (int)tab->mat[i][j]);

else

printf(" %6.2lf", tab->mat[i][j]);

}

printf("\n");

}

nl(70);

}

/* O'qish uchun doska uchun namunaviy fayl :

4 5

0 -0.5 -3 -1 -4

40 1 1 1 1

10 -2 -1 1 1

10 0 1 0 -1

*/

void misolni_uqish(doska *tab, const char * filename) {

int err, i, j;

FILE * fp;

fp = fopen(filename, "r" );

if( !fp ) {

printf("O'qish mumkin emas %s\n", filename); exit(1);

}

memset(tab, 0, sizeof(*tab));

err = fscanf(fp, "%d %d", &tab->m, &tab->n);

if (err == 0 || err == EOF) {

printf("M yoki o'qib bo'lmaydi n\n"); exit(1);

}

for(i=0;im; i++) {

for(j=0;jn; j++) {

err = fscanf(fp, "%lf", &tab->mat[i][j]);

if (err == 0 || err == EOF) {

printf("O'qish mumkin emas A[%d][%d]\n", i, j); exit(1);

}

}

}

printf("doskani o'qish [%d qatorlar x %d ustunlar ] fayldan '%s'.\n",

tab->m, tab->n, filename);

fclose(fp);

}

void burilish(doska *tab, int row, int col) {

int i, j;

double pivot;

pivot = tab->mat[row][col];

assert(pivot>0);

for(j=0;jn;j++)

tab->mat[row][j] /= pivot;

assert( teng(tab->mat[row][col], 1. ));

for(i=0; im; i++) {

double multiplier = tab->mat[i][col];

if(i==row) continue;

for(j=0; jn; j++) { // r[i] = r[i] - z * r[row];

tab->mat[i][j] -= multiplier * tab->mat[row][j];

}

}

}

int burilish_ustunini_toping(doska *tab) {

int j, pivot_col = 1;

double eng_past = tab->mat[0][pivot_col];

for(j=1; jn; j++) {

if (tab->mat[0][j] < eng_past ) {

eng_past = tab->mat[0][j];

pivot_col = j;

}

}

printf("[0] qatoridagi aksariyat salbiy ustunlar %d = %g.\n", pivot_col, eng_past );

//printf("Most negative column in row[0] is col %d = %g.\n", pivot_col, eng_past );

if( eng_past >= 0 ) {

return -1; // All positive columns in row[0], this is optimal.

}

return pivot_col;

}

// Find the burilish_qatori, with smallest positive ratio = col[0] / col[pivot]

int find_burilish_qatori(doska *tab, int pivot_col) {

int i, burilish_qatori = 0;

double min_ratio = -1;

printf("Koeffitsientlar A[qator_i,0]/A[qator_i,%d] = [",pivot_col);

for(i=1;im;i++){

double ratio = tab->mat[i][0] / tab->mat[i][pivot_col];

printf("%3.2lf, ", ratio);

if ( (ratio > 0 && ratio < min_ratio ) || min_ratio < 0 ) {

min_ratio = ratio;

burilish_qatori = i;

}

}

printf("].\n");

if (min_ratio == -1)

return -1; // Unbounded.

printf("Muhim topildi A[%d,%d], min ijobiy nisbat=%g in row=%d.\n",

burilish_qatori, pivot_col, min_ratio, burilish_qatori);

return burilish_qatori;

}

void sust_ozgaruvchilarni_qoshing (doska *tab) {

int i, j;

for(i=1; im; i++) {

for(j=1; jm; j++)

tab->mat[i][j + tab->n -1] = (i==j);

}

tab->n += tab->m -1;

}

void check_b_positive(doska *tab) {

int i;

for(i=1; im; i++)

assert(tab->mat[i][0] >= 0);

}

// Given a column of identity matrix, find the row containing 1.

// return -1, if the column as not from an identity matrix.

int asos_ozgaruvchisini_topish (doska *tab, int col) {

int i, xi=-1;

for(i=1; i < tab->m; i++) {

if (teng( tab->mat[i][col],1) ) {

if (xi == -1)

xi=i; // found first '1', save this row number.

else

return -1; // found second '1', not an identity matrix.

} else if (!teng( tab->mat[i][col],0) ) {

return -1; // not an identity matrix column.

}

}

return xi;

}

void optimal_vektorni_kursatish(doska *tab, char *message) {

int j, xi;

printf("%s at ", message);

for(j=1;jn;j++) { // for each column.

xi = asos_ozgaruvchisini_topish (tab, j);

if (xi != -1)

printf("x%d=%3.2lf, ", j, tab->mat[xi][0] );

else

printf("x%d=0, ", j);

}

printf("\n");

}

void simplex(doska *tab) {

int loop=0;

sust_ozgaruvchilarni_qoshing (tab);

check_b_positive(tab);

misolni_kursatish(tab," o'zgaruvchilar bilan to'ldirilgan");

while( ++loop ) {

int pivot_col, burilish_qatori;

pivot_col = burilish_ustunini_toping(tab);

if( pivot_col < 0 ) {

printf("Optimal qiymat topildi =A[0,0]=%3.2lf (0 qatorida salbiy sonlar yo'q).\n",

tab->mat[0][0]);

optimal_vektorni_kursatish(tab, "Optimal vector");

break;

}

printf("O'zgaruvchini kiritish x%d asosiy bo'lishi kerak, shuning uchun pivot_col=%d.\n",

pivot_col, pivot_col);

burilish_qatori = find_burilish_qatori(tab, pivot_col);

if (burilish_qatori < 0) {

printf("cheksiz ( burilish_qatori yuq).\n");

break;

}

printf("O'zgaruvchini qoldirish x%d, so burilish_qatori=%d\n", burilish_qatori, burilish_qatori);

burilish(tab, burilish_qatori, pivot_col);

misolni_kursatish(tab,"Qaytgandan keyin ");

optimal_vektorni_kursatish(tab, "Asosiy mumkin echim ");

if(loop > 20) {

printf("Juda ko'p takrorlash > %d.\n", loop);

break;

}

}

}

doska tab = { 4, 5, { // Size of doska [4 rows x 5 columns ]

{ 0.0 , -0.5 , -3.0 ,-1.0 , -4.0, }, // Max: z = 0.5*x + 3*y + z + 4*w,

{ 40.0 , 1.0 , 1.0 , 1.0 , 1.0, }, // x + y + z + w <= 40 .. b1

{ 10.0 , -2.0 , -1.0 , 1.0 , 1.0, }, // -2x - y + z + w <= 10 .. b2

{ 10.0 , 0.0 , 1.0 , 0.0 , -1.0, }, // y - w <= 10 .. b3

}

};

int main(int argc, char *argv[]){

if (argc > 1) { // usage: cmd datafile

misolni_uqish(&tab, argv[1]);

}

misolni_kursatish(&tab,"qiymat");

simplex(&tab);

return 0;

}

Javob: