Tối ưu hóa
Tối ưu tuyến tính Đồ án tốt nghiệp: Bài toán vận tải với ràng buộc hai phía (tệp đính kèm) Mô phỏng thuật toán bằng ngôn ngữ lập trình C/C+ /*-------------DO AN TOT NGHIEP DAI HOC KHOA TOAN TIN UNG DUNG----------------*//*---------------BAI TOAN VAN TAI VOI RANG BUOC HAI PHIA----------------------*/#include <stdio.h>#include <string.h>#include <conio.h>#include <stdlib.h>#include <math.h>#define MAX 50void ActiveWindow(int l,int t,int r,int b,int tcolor,int bcolor,char *S){ textmode(C80); window(l,t,r,b); textcolor(tcolor); textbackground(bcolor); clrscr(); cprintf("%-s",S);}void CacChucNang(){ ActiveWindow(22,9,60,9,YELLOW,CYAN," 1. GIAI (Q) NHAP DU LIEU TRUC TIEP"); ActiveWindow(22,10,60,10,YELLOW,CYAN," 2. GIAI (Q) NHAP DU LIEU TU FILE"); ActiveWindow(22,11,60,11,YELLOW,CYAN," 3. GIAI (P) NHAP DU LIEU TRUC TIEP"); ActiveWindow(22,12,60,12,YELLOW,CYAN," 4. GIAI (P) NHAP DU LIEU TU FILE"); ActiveWindow(22,13,60,13,YELLOW,CYAN," 5. THOAT KHOI CHUONG TRINH");}void init_MENU(){ ActiveWindow(10,5,70,5,GREEN,WHITE," CHUONG TRINH GIAI BAI TOAN VAN TAI VOI RANG BUOC HAI PHIA"); ActiveWindow(22,8,60,8,LIGHTMAGENTA,LIGHTBLUE," MENU CHUONG TRINH "); CacChucNang();}void DiChuyenVetSang(int pos){ char S[80]; switch(pos) { case 1: strcpy(S," 1. GIAI (Q) NHAP DU LIEU TRUC TIEP"); break; case 2: strcpy(S," 2. GIAI (Q) NHAP DU LIEU TU FILE"); break; case 3: strcpy(S," 3. GIAI (P) NHAP DU LIEU TRUC TIEP"); break; case 4: strcpy(S," 4. GIAI (P) NHAP DU LIEU TU FILE"); break; case 5: strcpy(S," 5. THOAT KHOI CHUONG TRINH"); break; } ActiveWindow(22,pos+8,60,pos+8,MAGENTA,WHITE,S);}void MENU(int pos){ init_MENU(); DiChuyenVetSang(pos);}void XuLy(int chon){ void GiaiBaiToanQTuBanPhim(); void GiaiBaiToanQTuFile(); void GiaiBaiToanPTuBanPhim(); void GiaiBaiToanPTuFile(); switch(chon) { case 1: GiaiBaiToanQTuBanPhim(); break; case 2: GiaiBaiToanQTuFile(); break; case 3: GiaiBaiToanPTuBanPhim(); break; case 4: GiaiBaiToanPTuFile(); break; }}int NhanPhim(){ int key = getch(); if(key == 0) key = getch(); return key;}void ChuyenVetSang(){ int pos = 1; MENU(pos); while(1) { CacChucNang(); DiChuyenVetSang(pos); int kytu = NhanPhim(); if(kytu == 13) { if(pos == 5) return; XuLy(pos); } else { if(kytu == 72) { if(pos == 1) pos = 5; else pos--; } else if(kytu == 80) { if(pos==5) pos=1; else pos++; } } }}/*****************************CHUONG TRINH CHINH*******************************/void mainMenu(){ textcolor(BLACK); textbackground(BLUE); clrscr(); ChuyenVetSang();}void main(){ mainMenu();}/*-----------------------Chuong trinh giai bai toan (Q) du lieu duoc nhap tu ban phim-----------------------*/void GiaiBaiToanQTuBanPhim(){ FILE *fptr;void KhoiTaoPACBQ(float x1[MAX][MAX], int m1, int n1); void ChuyenDoi_Q(float x1[MAX][MAX], float x2[MAX][MAX], int m1, int n1); void InPhuongAnQ(float x1[MAX][MAX], int m1, int n1); void ChuyenDoiQ(float x1[MAX][MAX], float x2[MAX][MAX], int m1, int n1); void TimChuTrinhQ(float x1[MAX][MAX], int m1, int n1); void Tim_hQ1(float x1[MAX][MAX], int m1, int n1, int o1, float BK1[100]); void Tim_hQ2(float x1[MAX][MAX], int m1, int n1, int r1, int s1, float bk1[100], float bk2[100]); void Tim_h(float x1[MAX][MAX], int m1, int n1, int r1, int s1, float bk1[100]); void GiaiHe(int n1, float A1[MAX][MAX], float B1[MAX], float x1[MAX]);void GiaiBaiToanVanTai(float A[100], float C[MAX][MAX], float x[MAX][MAX], int m, int n); void InMaTranPA(float x1[MAX][MAX], int m1, int n1); void NhapCuocPhi(float C1[MAX][MAX], int m1, int n1); void NhapThuPhat(float A1[100], int m1, int n1); void InCuocPhi(float C1[MAX][MAX], int m1, int n1); void InThuPhat(float A1[100], int m1, int n1);void InMaTranPA(float x1[MAX][MAX], int m1, int n1); void ChuyenDoi_2(float C1[MAX][MAX], float C2[MAX][MAX], int m1, int n1); float cq[MAX][MAX], c[MAX][MAX], a[100], x[MAX][MAX], xq[MAX][MAX], yq[MAX][MAX], xq1[MAX][MAX]; float uij[MAX], d[MAX][MAX], cij[MAX], cq1[MAX][MAX], cq2[MAX][MAX], bk[100], xq2[MAX][MAX],bk1[100], bk2[100]; int mq, nq, i, j, t1, t2, p, q, k, r, s, o, rq, sq, u, v, p1, q1, k1, k2; float e1, e2, h_min, f_minq, f_minvt = 0; window(1,1,80,25); textbackground(BLACK); textcolor(WHITE);clrscr(); fptr = fopen("C:\KetQuaQ.txt", "w"); printf("\n\n************************CHUONG TRINH GIAI BAI TOAN (Q)**************************\n\n"); fprintf(fptr,"\n\n************************CHUONG TRINH GIAI BAI TOAN (Q)**************************\n\n"); printf("NHAP KICH THUOC BAI TOAN\n\n"); printf("NHAP SO TRAM PHAT: "); scanf("%d", &mq); printf("NHAP SO TRAM THU: "); scanf("%d", &nq); printf("\nNHAP MA TRAN CUOC PHI CQ\n"); NhapCuocPhi(cq,mq, nq); printf("\nNHAP KHA NANG CUNG VA CAU\n"); NhapThuPhat(a, mq, nq);printf("\n\nMA TRAN CUOC PHI\n\n"); fprintf(fptr, "\n\nMA TRAN CUOC PHI\n\n"); InCuocPhi(cq, mq, nq); for(i = 0; i < mq; i++) { for(j = 0; j < nq; j++) { fprintf(fptr,"%8.1f",cq[i][j]); } fprintf(fptr, "\n"); } t1 = 0, t2 = 0; for(j = 0; j < nq; j++) t1 = t1 + a[mq+j]; for(i = 0; i < mq; i++) t2 = t2 + a[i]; a[0] = a[0] + (t1 - t2); printf("\n\nMA TRAN VE PHAI\n\n"); InThuPhat(a, mq, nq); fprintf(fptr,"\n\nMA TRAN VE PHAI\n\n"); for(i = 0; i < mq + nq; i++) fprintf(fptr, "%6.1f", a[i]); ChuyenDoi_2(c, cq, mq, nq); GiaiBaiToanVanTai(a, cq, x, mq, nq); printf("\n\nPHUONG AN CUC BIEN CUA BAI TOAN (Q)\n\n"); InMaTranPA(x, mq, nq); fprintf(fptr,"\n\nPHUONG AN TOI UU BAI TOAN VAN TAI\n\n"); for(i = 0; i < mq; i++) { for(j = 0; j < nq; j++) { if(x[i][j] > 0) fprintf(fptr, "%8.1f",x[i][j]); else fprintf(fptr,"%8.1f",0); } fprintf(fptr,"\n"); } for(i = 0; i < mq; i++) for(j = 0; j < nq; j++) { f_minvt = f_minvt + c[i][j]*x[i][j]; } fprintf(fptr,"\n\nGIA TRI HAM MUC TIEU TOI UU BAI TOAN VAN TAI %4.1f", f_minvt); printf("\n\n"); KhoiTaoPACBQ(xq, mq, nq); KhoiTaoPACBQ(xq1, mq, nq); KhoiTaoPACBQ(xq2, mq, nq); xq[0][0] = (t1 - t2); for(i = 1; i < mq; i++) xq[i][0] = 0; ChuyenDoi_Q(xq, x, mq, nq); fprintf(fptr, "\n\nPHUONG AN CUC BIEN CUA BAI TOAN (Q)\n\n"); InPhuongAnQ(xq, mq, nq); for(i = 0; i < mq; i++) { for(j = 0; j <= nq; j++) { if(xq[i][j] > 0) fprintf(fptr,"%8.1f", xq[i][j]); else fprintf(fptr,"%8.1f", 0); } fprintf(fptr,"\n"); } KhoiTaoPACBQ(cq1, mq, nq); KhoiTaoPACBQ(cq2, mq, nq); for(i = 0; i < mq; i++) cq1[i][0] = 0; ChuyenDoi_Q(cq1,c, mq, nq); ChuyenDoiQ(cq2, cq1, mq, nq);/*---------------------------Bat dau vong lap chinh---------------------------*/int dem = 0;while(true){ fprintf(fptr, "\n\n*************************************************************\n"); printf("\n\n*************************************************************\n"); printf("\n\nBUOC LAP THU %d", dem+1); fprintf(fptr,"\n\nBUOC LAP THU %d", dem + 1); ChuyenDoiQ(cq1, cq2, mq, nq); ChuyenDoiQ(yq, xq, mq, nq); for(i = 0; i < mq + nq; i++) for(j = 0; j < mq + nq; j++) { d[i][j] = 0; } for(i = 0; i < mq + nq; i++) { uij[i] = 0; cij[i] = 0; } k = 0; while(k < mq + nq) { for(i = 0; i < mq; i++) for(j = 0; j <= nq; j++) { if(xq[i][j] > 0) { goto TheVi; } }TheVi:{ if (j == 0) { p = i; q = j; xq[p][q] = 0; d[k][p] = 1; } else {p = i; q = j; xq[p][q] = 0; d[k][p] = 1; d[k][mq+q-1] = 1; }} k = k + 1; }//End sub while. ChuyenDoiQ(xq, yq, mq, nq); k = 0; for(i = 0; i < mq; i++) for(j = 0; j <= nq; j++) { if(yq[i][j] > 0) { cij[k] = cq1[i][j]; k = k + 1; } } GiaiHe(mq+nq, d, cij, uij); printf("\n\nTHE VI CUA HANG U\n\n"); for(i = 0; i < mq; i++) printf("\nu[%d] = %4.0f", i, uij[i]); fprintf(fptr,"\n\nTHE VI CUA HANG U\n\n"); for(i = 0; i < mq; i++) fprintf(fptr,"\nu[%d] = %4.0f", i, uij[i]); printf("\n\nTHE VI CUA COT V\n\n"); for(j = 0; j < nq; j++) printf("\nv[%d] = %4.0f", j, uij[mq+j]); fprintf(fptr,"\n\nTHE VI CUA COT V\n\n"); for(j = 0; j < nq; j++) fprintf(fptr,"\nv[%d] = %4.0f", j, uij[mq+j]); e1 = 1000; e2 = 1000; for(i = 0; i < mq; i++) for(j = 1; j <= nq; j++) { cq1[i][j] = cq1[i][j] - (uij[i] + uij[mq+j-1]); if(e1 > cq1[i][j]) e1 = cq1[i][j]; } r = 0; s = 0; for(i = 0; i < mq; i++) for(j = 1; j <= nq; j++) { if(cq1[i][j] == e1) { rq = i; sq = j; } } for(i = 0; i < mq; i++) if(e2 > uij[i]) e2 = uij[i]; o = 0; for(i = 0; i < mq; i++) if(e2 == uij[i]) o = i; if((e1 >= 0)&& (e2 >= 0)) goto KQ; else { if(e1 > e2) { /*Tim chu trinh cua bai toan (Q).*/ xq[o][0] = 1000; TimChuTrinhQ(xq, mq, nq); ChuyenDoiQ(xq1, xq, mq, nq); ChuyenDoiQ(xq2, xq, mq, nq); printf("\n\nCHU TRINH VUA TIM DUOC LA\n\n"); InPhuongAnQ(xq, mq, nq); fprintf(fptr,"\n\nCHU TRINH VUA TIM DUOC LA\n\n"); for(i = 0; i < mq; i++) { for(j = 0; j <= nq; j++) { if(xq[i][j] > 0) fprintf(fptr, "%8.1f", xq[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr,"\n"); } /*Tim luong hang nho nhat trong chu trinh le.*/ Tim_hQ1(xq, mq, nq, o, bk); h_min = bk[1]; for(i = 2; i < mq+nq; i = i+2) if(h_min > bk[i]&& bk[i] > 0) h_min = bk[i]; printf("\n\nLUONG HANG NHO NHAT TRONG CHU TRINH LE H_MIN = %4.0f", h_min); fprintf(fptr,"\n\nLUONG HANG NHO NHAT TRONG CHU TRINH LE H_MIN = %4.0f", h_min); ChuyenDoiQ(xq, xq1, mq, nq); /*Tim phuong an cuc bien moi.*/ for(i = 0; i < mq; i++) for(j = 0; j <= nq; j++) { if(yq[i][j] != xq1[i][j]) { xq[i][j] = yq[i][j]; } } r = o; s = 0; u = r; v = s; xq1[r][s] = 0; xq2[r][s] = 0; xq[r][s] = h_min; j = s; for(i = 0; i < mq; i++) if(xq1[i][j] > 0) xq[i][j] = xq[i][j] - h_min; k = 2; while(k < mq+nq) { j = s; for(i = 0; i < mq; i++) if(xq1[i][j] > 0) { r = i; xq1[i][j] = 0; } i = r; for(j = 0; j <= nq; j++) if(xq1[i][j] > 0) { s = j; if(xq1[i][j] == bk[k] && bk[k] > 0) xq[i][j] = bk[k] - h_min; xq1[i][j] = 0; } k = k + 2; } j = v; for(i = 0; i < mq; i++) if(xq2[i][j] > 0) { u = i; xq2[i][j] = 0; } k = 3; while(k < mq+nq) { i = u; for(j = 0; j <= nq; j++) if(xq2[i][j] > 0) { v = j; xq2[i][j] = 0; } j = v; for(i = 0; i < mq; i++) if(xq2[i][j] > 0) { u = i; if(xq2[i][j] == bk[k] && bk[k] > 0) xq[i][j] = bk[k] + h_min; xq2[i][j] = 0; } k = k + 2; } printf("\n\nPHUONG AN CUC BIEN MOI\n\n"); InPhuongAnQ(xq, mq, nq); fprintf(fptr,"\n\nPHUONG AN CUC BIEN MOI\n\n"); for(i = 0; i < mq; i++) { for(j = 0; j <= nq; j++) { if(xq[i][j] > 0) fprintf(fptr, "%8.1f", xq[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr,"\n"); } } else { xq[rq][sq] = 1000; /*Tim chu trinh tao boi rq va sq*/ TimChuTrinhQ(xq, mq, nq); ChuyenDoiQ(xq1, xq, mq, nq); ChuyenDoiQ(xq2, xq, mq, nq); printf("\n\nCHU TRINH VUA TIM LA\n\n"); InPhuongAnQ(xq, mq, nq); fprintf(fptr,"\n\nCHU TRINH VUA TIM LA\n\n"); for(i = 0; i < mq; i++) { for(j = 0; j <= nq; j++) { if(xq[i][j] > 0) fprintf(fptr, "%8.1f", xq[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr,"\n"); } /*Tim luong hang nho nhat trong chu trinh le.*/ for(i = 0; i < mq; i++) { if(xq[i][0] > 0) {Tim_hQ2(xq, mq, nq, rq, sq, bk1, bk2); for(i = 0; i < mq+nq; i++) fprintf(fptr,"\nbk1[%d] = %4.0f",i,bk1[i]); for(i = 0; i < mq+nq; i++) fprintf(fptr,"\nbk2[%d] = %4.0f",i,bk2[i]); h_min = bk2[0]; for(i = 1; i < mq+nq; i++) if(h_min > bk2[i]&& bk2[i] > 0) h_min = bk2[i]; printf("\n\nLUONG HANG NHO NHAT TRONG CHU TRINH LE H_MIN = %4.0f", h_min); fprintf(fptr,"\n\nLUONG HANG NHO NHAT TRONG CHU TRINH LE H_MIN = %4.0f", h_min);ChuyenDoiQ(xq, xq1, mq, nq); /*Tim phuong an cuc bien moi.*/ for(i = 0; i < mq; i++) for(j = 0; j <= nq; j++) { if(yq[i][j] != xq1[i][j]) { xq[i][j] = yq[i][j]; } } u = rq; v = sq; xq1[rq][sq] = 0; xq2[rq][sq] = 0; xq[rq][sq] = h_min; k = 0; k1 = 1; k2 = 0; while(k < mq+nq) { j = sq; for(i = 0; i < mq; i++) if(xq1[i][j] > 0) { if(j == 0) { rq = i; if(xq1[i][j] == bk1[k1] && bk1[k1] > 0) xq[i][j] = bk1[k1]+h_min; xq1[i][j] = 0; k1 = k1 + 1; } else { rq = i; if(xq1[i][j] = bk2[k2] && bk2[k2] > 0) xq[i][j] = bk2[k2] - h_min; xq1[i][j] = 0; k2 = k2 + 1; } } i = rq; for(j = 0; j <= nq; j++) if(xq1[i][j] > 0) { if(j == 0) { sq = j; if(xq1[i][j] == bk2[k2] && bk2[k2] > 0) xq[i][j] = bk2[k2] - h_min; xq1[i][j] = 0; k2 = k2 +1; } else { sq = j; if(xq1[i][j] == bk1[k1] && bk1[k1] > 0) xq[i][j] = bk1[k1] + h_min; xq1[i][j] = 0; k1 = k1+1; } } k = k + 1; } printf("\n\nPHUONG AN CUC BIEN MOI\n\n"); fprintf(fptr,"\n\nPHUONG AN CUC BIEN MOI\n\n"); InPhuongAnQ(xq, mq, nq); for(i = 0; i < mq; i++) { for(j = 0; j <= nq; j++) { if(xq[i][j] > 0) fprintf(fptr, "%8.1f", xq[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr,"\n"); } } else { Tim_h(xq, mq, nq, rq, sq, bk);for(k = 1; k < mq+nq; k = k+2)if(h_min > bk[k] && bk[k]>0) h_min = bk[k]; /*Tim phuong an moi.*/ for(i = 0; i < mq; i++) for(j = 0; j <= nq; j++) { if(yq[i][j] != xq1[i][j]) { xq[i][j] = yq[i][j]; yq[i][j] = 0; } } p1 = rq; q1 = sq; ChuyenDoi_2(xq2, xq1, mq, nq); xq1[rq][sq] = 0; xq2[rq][sq] = 0; xq[rq][sq] = h_min; k = 2; while(k < mq+nq) { i = rq; for(j = 0; j <= nq; j++) if(xq1[i][j] > 0) { q = j; xq1[i][j] = 0; } j = q; for(i = 0; i < mq; i++) if(xq1[i][j] > 0) { rq = i; if(xq1[i][j] == bk[k] && bk[k] > 0) xq[i][j] = bk[k] + h_min; xq1[i][j] = 0; } k = k + 2; } k = 1; while(k < mq+nq) { i = p1; for(j = 0; j <= nq; j++) if(xq2[i][j] > 0) { q1 = j; if(xq2[i][j] == bk[k] && bk[k] > 0) xq[i][j] = bk[k] - h_min; xq2[i][j] = 0; } j = q1; for(i = 0; i < mq; i++) if(xq2[i][j] > 0) { p1 = i; xq2[i][j] = 0; } k = k + 2; } printf("\n\nPHUONG AN CUC BIEN MOI\n\n"); fprintf(fptr,"\n\nPHUONG AN CUC BIEN MOI\n\n"); InPhuongAnQ(xq, mq, nq); for(i = 0; i < mq; i++) { for(j = 0; j <= nq; j++) { if(xq[i][j] > 0) fprintf(fptr, "%8.1f", xq[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr,"\n"); } } } } } dem ++;}//End main whileKQ: printf("\n\nPHUONG AN TOI UU CUA BAI TOAM (Q)\n\n");fprintf(fptr,"\n\nPHUONG AN TOI UU CUA BAI TOAM (Q)\n\n"); InPhuongAnQ(xq, mq, nq); for(i = 0; i < mq; i++) { for(j = 0; j <= nq; j++) { if(xq[i][j] > 0) fprintf(fptr, "%8.1f", xq[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr,"\n"); } f_minq = 0;for(i = 0; i < mq; i++) for(j = 0; j <= nq; j++) { f_minq = f_minq + xq[i][j]* cq2[i][j]; } printf("\n\nGIA TRI TOI UU CUA BAI TOAN (Q) F_MINQ = %4.0f", f_minq); fprintf(fptr,"\n\nGIA TRI TOI UU CUA BAI TOAN (Q) F_MINQ = %4.0f", f_minq); printf("\n\nSO BUOC LAP THU HIEN %d", dem); fprintf(fptr,"\n\nSO BUOC LAP THU HIEN %d", dem); fclose(fptr); printf("\n\nAn phim M hoac m de tro ve Menu chuong trinh"); char ch = getch(); if((ch == 'M')||(ch == 'm')) { mainMenu(); } else { exit(1); }}/*-----------------------Chuong trinh giai bai toan (Q) du lieu duoc nhap tu file--------------------------*/void GiaiBaiToanQTuFile(){FILE *fpt; FILE *fptr; void KhoiTaoPACBQ(float x1[MAX][MAX], int m1, int n1); void ChuyenDoi_Q(float x1[MAX][MAX], float x2[MAX][MAX], int m1, int n1); void InPhuongAnQ(float x1[MAX][MAX], int m1, int n1); void ChuyenDoiQ(float x1[MAX][MAX], float x2[MAX][MAX], int m1, int n1); void TimChuTrinhQ(float x1[MAX][MAX], int m1, int n1); void Tim_h(float x1[MAX][MAX], int m1, int n1, int r1, int s1, float bk1[100]); void Tim_hQ1(float x1[MAX][MAX], int m1, int n1, int o1, float BK1[100]); void Tim_hQ2(float x1[MAX][MAX], int m1, int n1, int r1, int s1, float bk1[100], float bk2[100]); void GiaiHe(int n1, float A1[MAX][MAX], float B1[MAX], float x1[MAX]);void GiaiBaiToanVanTai(float A[100], float C[MAX][MAX], float x[MAX][MAX], int m, int n); void InMaTranPA(float x1[MAX][MAX], int m1, int n1); void NhapCuocPhi(float C1[MAX][MAX], int m1, int n1); void NhapThuPhat(float A1[100], int m1, int n1); void InCuocPhi(float C1[MAX][MAX], int m1, int n1); void InThuPhat(float A1[100], int m1, int n1);void InMaTranPA(float x1[MAX][MAX], int m1, int n1); void ChuyenDoi_2(float C1[MAX][MAX], float C2[MAX][MAX], int m1, int n1); float cq[MAX][MAX], c[MAX][MAX], a[100], x[MAX][MAX], xq[MAX][MAX], yq[MAX][MAX], xq1[MAX][MAX]; float uij[MAX], d[MAX][MAX], cij[MAX], cq1[MAX][MAX], cq2[MAX][MAX], bk[100], xq2[MAX][MAX], bk1[100], bk2[100]; int mq, nq, i, j, t1, t2, p, q, k, r, s, o, rq, sq, u, v, p1, q1, k1, k2; float e1, e2, h_min, f_minq, f_minvt = 0; char fName[MAX]; window(1,1,80,25); textbackground(BLACK); textcolor(WHITE);clrscr(); printf("\n\n************************CHUONG TRINH GIAI BAI TOAN (Q)**************************\n\n"); printf("NHAP TEN FILE: "); scanf("%50s", fName); fpt = fopen(fName, "r"); if(fpt == NULL) { printf("\n LOI - KHONG TIM THAY FILE!"); getch(); exit(1); } else { fscanf(fpt, "%d", &mq); fscanf(fpt, "%d", &nq); for(i = 0; i < mq; i++) for(j = 0; j < nq; j++) { fscanf(fpt, "%f", &cq[i][j]); } for(i = 0; i < mq + nq; i++) fscanf(fpt, "%f", &a[i]); } fclose(fpt); fptr = fopen("C:\KetQuaQ.txt", "w"); fprintf(fptr,"\n\n************************CHUONG TRINH GIAI BAI TOAN (Q)**************************\n\n");printf("\n\nMA TRAN CUOC PHI\n\n"); fprintf(fptr, "\n\nMA TRAN CUOC PHI\n\n"); InCuocPhi(cq, mq, nq); for(i = 0; i < mq; i++) { for(j = 0; j < nq; j++) { fprintf(fptr,"%8.1f",cq[i][j]); } fprintf(fptr, "\n"); } t1 = 0, t2 = 0; for(j = 0; j < nq; j++) t1 = t1 + a[mq+j]; for(i = 0; i < mq; i++) t2 = t2 + a[i]; a[0] = a[0] + (t1 - t2); printf("\n\nMA TRAN VE PHAI\n\n"); InThuPhat(a, mq, nq); fprintf(fptr,"\n\nMA TRAN VE PHAI\n\n"); for(i = 0; i < mq + nq; i++) fprintf(fptr, "%6.1f", a[i]); ChuyenDoi_2(c, cq, mq, nq); GiaiBaiToanVanTai(a, cq, x, mq, nq); printf("\n\nPHUONG AN TOI UU BAI TOAN VAN TAI\n\n"); InMaTranPA(x, mq, nq); fprintf(fptr,"\n\nPHUONG TOI UU CUA BAI TOAN VAN TAI\n\n"); for(i = 0; i < mq; i++) { for(j = 0; j < nq; j++) { if(x[i][j] > 0) fprintf(fptr, "%8.1f",x[i][j]); else fprintf(fptr,"%8.1f",0); } fprintf(fptr,"\n"); } for(i = 0; i < mq; i++) for(j = 0; j < nq; j++) { f_minvt = f_minvt + c[i][j]*x[i][j]; } printf("\n\nGIA TRI HAM MUC TIEU TOI UU BAI TOAN VAN TAI LA %4.1f", f_minvt); printf("\n\n"); fprintf(fptr,"\n\nGIA TRI HAM MUC TIEU TOI UU BAI TOAN VAN TAI LA %4.1f", f_minvt); printf("\n\n"); KhoiTaoPACBQ(xq, mq, nq); KhoiTaoPACBQ(xq1, mq, nq); KhoiTaoPACBQ(xq2, mq, nq); xq[0][0] = (t1 - t2); for(i = 1; i < mq; i++) xq[i][0] = 0; ChuyenDoi_Q(xq, x, mq, nq); fprintf(fptr, "\n\nPHUONG AN CUC BIEN CUA BAI TOAN (Q)\n\n"); printf("\n\nPHUONG AN CUC BIEN CUA BAI TOAN (Q)\n\n"); InPhuongAnQ(xq, mq, nq); for(i = 0; i < mq; i++) { for(j = 0; j <= nq; j++) { if(xq[i][j] > 0) fprintf(fptr,"%8.1f", xq[i][j]); else fprintf(fptr,"%8.1f", 0); } fprintf(fptr,"\n"); } KhoiTaoPACBQ(cq1, mq, nq); KhoiTaoPACBQ(cq2, mq, nq); for(i = 0; i < mq; i++) cq1[i][0] = 0; ChuyenDoi_Q(cq1,c, mq, nq); ChuyenDoiQ(cq2, cq1, mq, nq);/*---------------------------Bat dau vong lap chinh---------------------------*/int dem = 0;while(true){ fprintf(fptr, "\n\n*************************************************************\n"); printf("\n\n*************************************************************\n"); printf("\n\nBUOC LAP THU %d", dem+1); fprintf(fptr,"\n\nBUOC LAP THU %d", dem + 1); ChuyenDoiQ(cq1, cq2, mq, nq); ChuyenDoiQ(yq, xq, mq, nq); for(i = 0; i < mq + nq; i++) for(j = 0; j < mq + nq; j++) { d[i][j] = 0; } for(i = 0; i < mq + nq; i++) { uij[i] = 0; cij[i] = 0; } k = 0; while(k < mq + nq) { for(i = 0; i < mq; i++) for(j = 0; j <= nq; j++) { if(xq[i][j] > 0) { goto TheVi; } }TheVi:{ if (j == 0) { p = i; q = j; xq[p][q] = 0; d[k][p] = 1; } else {p = i; q = j; xq[p][q] = 0; d[k][p] = 1; d[k][mq+q-1] = 1; }} k = k + 1; }//End sub while. ChuyenDoiQ(xq, yq, mq, nq); k = 0; for(i = 0; i < mq; i++) for(j = 0; j <= nq; j++) { if(yq[i][j] > 0) { cij[k] = cq1[i][j]; k = k + 1; } } GiaiHe(mq+nq, d, cij, uij); printf("\n\nTHE VI CUA HANG U\n\n"); for(i = 0; i < mq; i++) printf("\nu[%d] = %4.0f", i, uij[i]); fprintf(fptr,"\n\nTHE VI CUA HANG U\n\n"); for(i = 0; i < mq; i++) fprintf(fptr,"\nu[%d] = %4.0f", i, uij[i]); printf("\n\nTHE VI CUA COT V\n\n"); for(j = 0; j < nq; j++) printf("\nv[%d] = %4.0f", j, uij[mq+j]); fprintf(fptr,"\n\nTHE VI CUA COT V\n\n"); for(j = 0; j < nq; j++) fprintf(fptr,"\nv[%d] = %4.0f", j, uij[mq+j]); e1 = 1000; e2 = 1000; for(i = 0; i < mq; i++) for(j = 1; j <= nq; j++) { cq1[i][j] = cq1[i][j] - (uij[i] + uij[mq+j-1]); if(e1 > cq1[i][j]) e1 = cq1[i][j]; } r = 0; s = 0; for(i = 0; i < mq; i++) for(j = 1; j <= nq; j++) { if(cq1[i][j] == e1) { rq = i; sq = j; } } for(i = 0; i < mq; i++) if(e2 > uij[i]) e2 = uij[i]; o = 0; for(i = 0; i < mq; i++) if(e2 == uij[i]) o = i; if((e1 >= 0)&& (e2 >= 0)) goto KQ; else { if(e1 > e2) { /*Tim chu trinh cua bai toan (Q).*/ xq[o][0] = 1000; TimChuTrinhQ(xq, mq, nq); ChuyenDoiQ(xq1, xq, mq, nq); ChuyenDoiQ(xq2, xq, mq, nq); printf("\n\nCHU TRINH VUA TIM DUOC LA\n\n"); InPhuongAnQ(xq, mq, nq); fprintf(fptr,"\n\nCHU TRINH VUA TIM DUOC LA\n\n"); for(i = 0; i < mq; i++) { for(j = 0; j <= nq; j++) { if(xq[i][j] > 0) fprintf(fptr, "%8.1f", xq[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr,"\n"); } /*Tim luong hang nho nhat trong chu trinh le.*/ Tim_hQ1(xq, mq, nq, o, bk); h_min = bk[1]; for(i = 2; i < mq+nq; i = i+2) if(h_min > bk[i]&& bk[i] > 0) h_min = bk[i]; printf("\n\nLUONG HANG NHO NHAT TRONG CHU TRINH LE H_MIN = %4.0f", h_min); fprintf(fptr,"\n\nLUONG HANG NHO NHAT TRONG CHU TRINH LE H_MIN = %4.0f", h_min); ChuyenDoiQ(xq, xq1, mq, nq); /*Tim phuong an cuc bien moi.*/ for(i = 0; i < mq; i++) for(j = 0; j <= nq; j++) { if(yq[i][j] != xq1[i][j]) { xq[i][j] = yq[i][j]; } } r = o; s = 0; u = r; v = s; xq1[r][s] = 0; xq2[r][s] = 0; xq[r][s] = h_min; j = s; for(i = 0; i < mq; i++) if(xq1[i][j] > 0) xq[i][j] = xq[i][j] - h_min; k = 2; while(k < mq+nq) { j = s; for(i = 0; i < mq; i++) if(xq1[i][j] > 0) { r = i; xq1[i][j] = 0; } i = r; for(j = 0; j <= nq; j++) if(xq1[i][j] > 0) { s = j; if(xq1[i][j] == bk[k] && bk[k] > 0) xq[i][j] = bk[k] - h_min; xq1[i][j] = 0; } k = k + 2; } j = v; for(i = 0; i < mq; i++) if(xq2[i][j] > 0) { u = i; xq2[i][j] = 0; } k = 3; while(k < mq+nq) { i = u; for(j = 0; j <= nq; j++) if(xq2[i][j] > 0) { v = j; xq2[i][j] = 0; } j = v; for(i = 0; i < mq; i++) if(xq2[i][j] > 0) { u = i; if(xq2[i][j] == bk[k] && bk[k] > 0) xq[i][j] = bk[k] + h_min; xq2[i][j] = 0; } k = k + 2; } printf("\n\nPHUONG AN CUC BIEN MOI\n\n"); InPhuongAnQ(xq, mq, nq); fprintf(fptr,"\n\nPHUONG AN CUC BIEN MOI\n\n"); for(i = 0; i < mq; i++) { for(j = 0; j <= nq; j++) { if(xq[i][j] > 0) fprintf(fptr, "%8.1f", xq[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr,"\n"); } } else { xq[rq][sq] = 1000; /*Tim chu trinh tao boi rq va sq*/ TimChuTrinhQ(xq, mq, nq); ChuyenDoiQ(xq1, xq, mq, nq); ChuyenDoiQ(xq2, xq, mq, nq); printf("\n\nCHU TRINH VUA TIM LA\n\n"); InPhuongAnQ(xq, mq, nq); fprintf(fptr,"\n\nCHU TRINH VUA TIM LA\n\n"); for(i = 0; i < mq; i++) { for(j = 0; j <= nq; j++) { if(xq[i][j] > 0) fprintf(fptr, "%8.1f", xq[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr,"\n"); } /*Tim luong hang nho nhat trong chu trinh le.*/ for(i = 0; i < mq; i++) { if(xq[i][0] > 0) {Tim_hQ2(xq, mq, nq, rq, sq, bk1, bk2); for(i = 0; i < mq+nq; i++) fprintf(fptr,"\nbk1[%d] = %4.0f",i,bk1[i]); for(i = 0; i < mq+nq; i++) fprintf(fptr,"\nbk2[%d] = %4.0f",i,bk2[i]); h_min = bk2[0]; for(i = 1; i < mq+nq; i++) if(h_min > bk2[i]&& bk2[i] > 0) h_min = bk2[i]; printf("\n\nLUONG HANG NHO NHAT TRONG CHU TRINH LE H_MIN = %4.0f", h_min); fprintf(fptr,"\n\nLUONG HANG NHO NHAT TRONG CHU TRINH LE H_MIN = %4.0f", h_min);ChuyenDoiQ(xq, xq1, mq, nq); /*Tim phuong an cuc bien moi.*/ for(i = 0; i < mq; i++) for(j = 0; j <= nq; j++) { if(yq[i][j] != xq1[i][j]) { xq[i][j] = yq[i][j]; } } u = rq; v = sq; xq1[rq][sq] = 0; xq2[rq][sq] = 0; xq[rq][sq] = h_min; k = 0; k1 = 1; k2 = 0; while(k < mq+nq) { j = sq; for(i = 0; i < mq; i++) if(xq1[i][j] > 0) { if(j == 0) { rq = i; if(xq1[i][j] == bk1[k1] && bk1[k1] > 0) xq[i][j] = bk1[k1]+h_min; xq1[i][j] = 0; k1 = k1 + 1; } else { rq = i; if(xq1[i][j] = bk2[k2] && bk2[k2] > 0) xq[i][j] = bk2[k2] - h_min; xq1[i][j] = 0; k2 = k2 + 1; } } i = rq; for(j = 0; j <= nq; j++) if(xq1[i][j] > 0) { if(j == 0) { sq = j; if(xq1[i][j] == bk2[k2] && bk2[k2] > 0) xq[i][j] = bk2[k2] - h_min; xq1[i][j] = 0; k2 = k2 +1; } else { sq = j; if(xq1[i][j] == bk1[k1] && bk1[k1] > 0) xq[i][j] = bk1[k1] + h_min; xq1[i][j] = 0; k1 = k1+1; } } k = k + 1; } printf("\n\nPHUONG AN CUC BIEN MOI\n\n"); fprintf(fptr,"\n\nPHUONG AN CUC BIEN MOI\n\n"); InPhuongAnQ(xq, mq, nq); for(i = 0; i < mq; i++) { for(j = 0; j <= nq; j++) { if(xq[i][j] > 0) fprintf(fptr, "%8.1f", xq[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr,"\n"); } } else { Tim_h(xq, mq, nq, rq, sq, bk);for(k = 1; k < mq+nq; k = k+2)if(h_min > bk[k] && bk[k]>0) h_min = bk[k]; /*Tim phuong an moi.*/ for(i = 0; i < mq; i++) for(j = 0; j <= nq; j++) { if(yq[i][j] != xq1[i][j]) { xq[i][j] = yq[i][j]; yq[i][j] = 0; } } p1 = rq; q1 = sq; ChuyenDoi_2(xq2, xq1, mq, nq); xq1[rq][sq] = 0; xq2[rq][sq] = 0; xq[rq][sq] = h_min; k = 2; while(k < mq+nq) { i = rq; for(j = 0; j <= nq; j++) if(xq1[i][j] > 0) { q = j; xq1[i][j] = 0; } j = q; for(i = 0; i < mq; i++) if(xq1[i][j] > 0) { rq = i; if(xq1[i][j] == bk[k] && bk[k] > 0) xq[i][j] = bk[k] + h_min; xq1[i][j] = 0; } k = k + 2; } k = 1; while(k < mq+nq) { i = p1; for(j = 0; j <= nq; j++) if(xq2[i][j] > 0) { q1 = j; if(xq2[i][j] == bk[k] && bk[k] > 0) xq[i][j] = bk[k] - h_min; xq2[i][j] = 0; } j = q1; for(i = 0; i < mq; i++) if(xq2[i][j] > 0) { p1 = i; xq2[i][j] = 0; } k = k + 2; } printf("\n\nPHUONG AN CUC BIEN MOI\n\n"); fprintf(fptr,"\n\nPHUONG AN CUC BIEN MOI\n\n"); InPhuongAnQ(xq, mq, nq); for(i = 0; i < mq; i++) { for(j = 0; j <= nq; j++) { if(xq[i][j] > 0) fprintf(fptr, "%8.1f", xq[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr,"\n"); } } } } } dem ++;}//End main whileKQ: printf("\n\nPHUONG AN TOI UU CUA BAI TOAN (Q)\n\n");fprintf(fptr,"\n\nPHUONG AN TOI UU CUA BAI TOAN (Q)\n\n"); InPhuongAnQ(xq, mq, nq); for(i = 0; i < mq; i++) { for(j = 0; j <= nq; j++) { if(xq[i][j] > 0) fprintf(fptr, "%8.1f", xq[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr,"\n"); } f_minq = 0;for(i = 0; i < mq; i++) for(j = 0; j <= nq; j++) { f_minq = f_minq + xq[i][j]* cq2[i][j]; } printf("\n\nGIA TRI TOI UU CUA BAI TOAN (Q) F_MINQ = %4.0f", f_minq); fprintf(fptr,"\n\nGIA TRI TOI UU CUA BAI TOAN (Q) F_MINQ = %4.0f", f_minq); printf("\n\nSO BUOC LAP THU HIEN %d", dem); fprintf(fptr,"\n\nSO BUOC LAP THU HIEN %d", dem); fclose(fptr); printf("\n\nAn phim M hoac m de tro ve Menu chuong trinh"); char ch = getch(); if((ch == 'M')||(ch == 'm')) { mainMenu(); } else { exit(1); }}/*-----------------------Dinh Nghia Cac Ham-----------------------------------*//*-----------------------Ham nhap ma tran cuoc phi----------------------------*/void NhapCuocPhi(float C1[MAX][MAX], int m1, int n1){int i, j; for(i = 0; i < m1; i++) for(j = 0; j < n1; j++) { printf(" C1[%d,%d] = ", i, j); scanf("%f", &C1[i][j]); }}/*-----------------------Ham nhap yeu cau thu - phat--------------------------*/void NhapThuPhat(float A1[100], int m1, int n1){int i; for(i = 0; i < m1+n1; i++) { printf(" A1[%d] = ", i); scanf("%f", &A1[i]); }}/*------------------Ham in ma tran cuoc phi ra man hinh-----------------------*/void InCuocPhi(float C1[MAX][MAX], int m1, int n1){ int i, j;for(i = 0; i < m1; i++) { for(j = 0; j < n1; j++) { printf("%8.1f", C1[i][j]); } printf("\n"); }}/*------------------Ham in ma tran thu phat ra man hinh-----------------------*/void InThuPhat(float A1[100], int m1, int n1){ int i;for(i = 0; i < m1+n1; i++) printf("%8.1f", A1[i]);}/*-------------Ham tim phuong an cuc bien - Phuong phap min cuoc--------------*/void TimPACB(float A1[100], float C1[MAX][MAX], float x1[MAX][MAX], int m1, int n1){int total, s, i, j, p, q;total = 0;for(i = 0; i < m1; i++){ total = total + A1[i];}s = total;while(s > 0){int mi = 1000;for(i = 0; i < m1; i++)for (j = 0; j < n1; j++){if (C1[i][j] < mi && C1[i][j] > 0) mi = C1[i][j];} for(i = 0; i < m1; i++) for(j = 0; j < n1; j++) { if(C1[i][j] == mi) goto TT; }TT:p=i; q=j; if (A1[p] > A1[m1+q]) x1[p][q] = A1[m1+q]; else x1[p][q] = A1[p]; A1[p] = A1[p] - x1[p][q]; A1[m1+q] = A1[m1+q] - x1[p][q]; if(A1[p]== 0 && A1[m1+q]!= 0) { for (j = 0; j < n1; j++) C1[p][j] = 0;} else if(A1[m1+q] == 0) { for (i = 0; i < m1; i++) C1[i][q]=0; } s = s - x1[p][q];}}/*-----------------------------Ham tim chu trinh------------------------------*/void TimChuTrinh(float x1[MAX][MAX], int m1, int n1){int w = 0; int k, l, i, j, s, r;int BI[100];while(w < m1+n1){i = 0;while(i < m1){k = 1;for(j = 0; j < n1; j++)if(x1[i][j] > 0){BI[i] = k; s = j; k = k + 1;}if(BI[i] == 1)x1[i][s] = 0;i = i + 1;}j = 0;while(j < n1){l = 1;for(i = 0; i < m1; i++)if(x1[i][j] > 0){BI[j] = l; r = i; l = l + 1;}if(BI[j] == 1)x1[r][j] = 0;j = j + 1;}w = w + 1;}}/*---------------------------------Ham tim h_min------------------------------*/void Tim_h(float x1[MAX][MAX], int m1, int n1, int r1, int s1, float bk1[100]){int i, j, k, w;for(k = 0; k < m1+n1; k++) bk1[k]=0;bk1[0] = x1[r1][s1]; x1[r1][s1] = 0; k = 0; w = 0;while(w < m1+n1){i = r1;for(j = 0; j < n1; j++)if(x1[i][j] > 0){s1 = j; bk1[k+1] = x1[i][j]; x1[i][j] = 0; k = k + 1;} j = s1; for(i = 0; i < m1; i++) if(x1[i][j] > 0) { r1 = i; bk1[k+1] = x1[i][j]; x1[i][j] = 0; k = k + 1; } w = w + 1;}}/*-------------------------Ham chuyen doi mot chieu---------------------------*/void ChuyenDoi_1(float A1[100], float B1[100], int m1){int i; for(i = 0; i < m1; i++) A1[i] = B1[i];}/*------------------------------Ham gan hai chieu-----------------------------*/void ChuyenDoi_2(float C1[MAX][MAX], float C2[MAX][MAX], int m1, int n1){int i, j; for(i = 0; i < m1; i++) for(j = 0; j < n1; j++) { C1[i][j] = C2[i][j]; }}/*----------------------------Ham in ma tran phuong an------------------------*/void InMaTranPA(float x1[MAX][MAX], int m1, int n1){int i, j; for(i = 0; i < m1; i++) { for(j = 0; j < n1; j++) { if(x1[i][j] > 0) printf("%8.1f", x1[i][j]); else printf("%8.1f", 0); } printf("\n"); }}/*--------------------------Ham giai he phuong trinh--------------------------*/void GiaiHe(int n1, float A1[MAX][MAX], float B1[MAX], float x1[MAX]){int i = 0, j, done = 0, m, k;int max1; float c;while(!done){if (A1[i][i] == 0){max1 = 0;m = i;for (k = i+1; k < n1; k++)if (max1 < fabs(A1[k][i])){m = k;max1 = fabs(A1[k][i]);}if (m != i){for(j = i; j < n1; j++){c = A1[i][j];A1[i][j] = A1[m][j];A1[m][j] = c;}c = B1[i];B1[i] = B1[m];B1[m] = c;}if (m == i)done = 1;}if (A1[i][i] != 0){c = 1/A1[i][i];for (j = i; j < n1; j++)A1[i][j] = A1[i][j] * c;B1[i] = B1[i] * c;for(k = 0; k < n1; k++)if (k != i){c = A1[k][i];for(j = i; j < n1; j++)A1[k][j] = A1[k][j] - A1[i][j]*c;B1[k] = B1[k] - B1[i] * c;}}i++;if(i >= n1)done = 1;}if (i >= n1)for(j = 0;j < n1; j++)x1[j] = B1[j];}void GiaiBaiToanVanTai(float A[100], float C[MAX][MAX], float x[MAX][MAX], int m, int n){ float CP[MAX][MAX], d[MAX][MAX]; float y[MAX][MAX], uij[MAX], cij[MAX], x1[MAX][MAX], x2[MAX][MAX]; float bk[100]; int i, j, r, s, k, p, q, p1, q1; float f_min; float h_min = 10000; float e;void ChuyenDoi_1(float A1[100], float B1[100], int m1); void ChuyenDoi_2(float C1[MAX][MAX], float C2[MAX][MAX], int m1, int n1); void NhapCuocPhi(float C1[MAX][MAX], int m1, int n1); void NhapThuPhat(float A1[100], int m1, int n1); void InCuocPhi(float C1[MAX][MAX], int m1, int n1); void InThuPhat(float A1[100], int m1, int n1); void InMaTranPA(float x1[MAX][MAX], int m1, int n1); void TimPACB(float A1[100], float C1[MAX][MAX], float x1[MAX][MAX], int m1, int n1); void TimChuTrinh(float x1[MAX][MAX], int m1, int n1); void Tim_h(float x1[MAX][MAX], int m1, int n1, int r1, int s1, float bk1[100]); void GiaiHe(int n1, float A1[MAX][MAX], float B1[MAX], float x1[MAX]); ChuyenDoi_2(CP, C, m, n); f_min = 0; for(i = 0; i < m; i++) for(j = 0; j < n; j++) { x[i][j] = 0; y[i][j] = 0; d[i][j] = 0; } TimPACB(A, C, x, m, n); printf("\n\nMA TRAN PHUONG AN CUC BIEN VAN TAI\n\n");InMaTranPA(x, m, n); for(i = 0; i < m; i++) for(j = 0; j < n; j++) {f_min = f_min + CP[i][j]* x[i][j]; C[i][j] = CP[i][j]; }printf("\n\nGIA TRI HAM MUC TIEU CUC BIEN VAN TAI F_MIN = %5.1f", f_min);/*-------------------------Bat dau vong lap chinh-----------------------------*/while(true){ ChuyenDoi_2(y, x, m, n); for(i = 0; i < m+n; i++) for(j = 0; j < m+n; j++) { d[i][j] = 0; } k = 0; while(k < m+n-1) { for(i = 0; i < m; i++) for(j = 0; j < n; j++) if(y[i][j] > 0) { goto TheVi; }TheVi: {p = i; q = j; y[p][q] = 0; d[k][p] = 1; d[k][m+q] = 1; } k = k + 1; }//end while. for(i = 0; i < m+n; i++) { uij[i] = 0; cij[i] = 0; } k = 0; for(i = 0; i < m; i++) for(j = 0; j < n; j++) { if(x[i][j] > 0) { cij[k] = C[i][j]; k = k + 1; } } if(k < m+n) { for(i = 0; i < m+n; i++) { d[m+n-1][i] = 1; cij[m+n-1] = 0; } GiaiHe(m+n, d, cij, uij); } else GiaiHe(m+n, d, cij, uij); e = 1000; for(i = 0; i < m; i++) for(j = 0; j < n; j++) { C[i][j] = C[i][j] - (uij[i] + uij[m+j]); if(e > C[i][j]) e = C[i][j]; } r = 0; s = 0; for(i = 0; i < m; i++) for(j = 0; j < n; j++) { if(C[i][j] == e) { r = i; s = j; } }if(e >= 0) goto KQ; /*Tim chu trinh.*/ else { ChuyenDoi_2(y, x, m, n); x[r][s] = 1000; TimChuTrinh(x, m, n); ChuyenDoi_2(x1, x, m, n); } /*Tim h_min cua cac o chan trong chu trinh.*/ Tim_h(x, m, n, r, s, bk);for(k = 1; k < m+n; k = k+2)if(h_min > bk[k] && bk[k]>0) h_min = bk[k]; /*Tim phuong an moi.*/ for(i = 0; i < m; i++) for(j = 0; j < n; j++) { if(y[i][j] != x1[i][j]) { x[i][j] = y[i][j]; y[i][j] = 0; } } p1 = r; q1 = s; ChuyenDoi_2(x2, x1, m, n); x1[r][s] = 0; x2[r][s] = 0; x[r][s] = h_min; k = 2; while(k < m+n) { i = r; for(j = 0; j < n; j++) if(x1[i][j] > 0) { q = j; x1[i][j] = 0; } j = q; for(i = 0; i < m; i++) if(x1[i][j] > 0) { r = i; if(x1[i][j] == bk[k] && bk[k] > 0) x[i][j] = bk[k] + h_min; x1[i][j] = 0; } k = k + 2; } k = 1; while(k < m+n) { i = p1; for(j = 0; j < n; j++) if(x2[i][j] > 0) { q1 = j; if(x2[i][j] == bk[k] && bk[k] > 0) x[i][j] = bk[k] - h_min; x2[i][j] = 0; } j = q1; for(i = 0; i < m; i++) if(x2[i][j] > 0) { p1 = i; x2[i][j] = 0; } k = k + 2; }}KQ:printf("\n\nPHUONG AN TOI UU CUA BAI TOAN VAN TAI\n\n"); InMaTranPA(x, m, n); f_min = 0; for(i = 0; i < m; i++) for(j = 0; j < n; j++) {f_min = f_min + CP[i][j]* x[i][j]; }printf("\n\nGIA TRI HAM MUC TIEU VAN TAI F_MIN = %5.1f", f_min);}//Cac Ham Phuc Vu Cho Giai Bai Toan Q/*---------------------Khoi tao phuong an cuc bien Q--------------------------*/void KhoiTaoPACBQ(float x1[MAX][MAX], int m1, int n1){ int i, j;for(i = 0; i < m1; i++) for(j = 0; j <= n1; j++) { x1[i][j] = 0; }}/*---------------------Chuyen doi phuong an cuc bien Q------------------------*/void ChuyenDoi_Q(float x1[MAX][MAX], float x2[MAX][MAX], int m1, int n1){int i, j; for(i = 0; i < m1; i++) for(j = 1; j <= n1; j++) { x1[i][j] = x2[i][j-1]; }}/*--------------------In ra man hinh phuong an cuc bien Q---------------------*/void InPhuongAnQ(float x1[MAX][MAX], int m1, int n1){int i, j; for(i = 0; i < m1; i++) { for(j = 0; j <= n1; j++) { if(x1[i][j] > 0) { printf("%8.1f", x1[i][j]); } else printf("%8.1f", 0); } printf("\n"); }}/*---------------------Chuyen doi phuong an cuc bien Q------------------------*/void ChuyenDoiQ(float x1[MAX][MAX], float x2[MAX][MAX], int m1, int n1){int i, j; for(i = 0; i < m1; i++) for(j = 0; j <= n1; j++) { x1[i][j] = x2[i][j]; }}/*-------------------------Ham tim chu trinh cua Q----------------------------*/void TimChuTrinhQ(float x1[MAX][MAX], int m1, int n1){int w = 0; int k, l, i, j, s, r;int BI[100];while(w < m1+n1){i = 0;while(i < m1){k = 1;for(j = 0; j <= n1; j++)if(x1[i][j] > 0){BI[i] = k; s = j; k = k + 1;}if(BI[i] == 1)x1[i][s] = 0;i = i + 1;}j = 0;while(j <= n1){l = 1;for(i = 0; i < m1; i++)if(x1[i][j] > 0){BI[j] = l; r = i; l = l + 1;}if(BI[j] == 1)x1[r][j] = 0;j = j + 1;}w = w + 1;}}/*----------------Tim luong hang nho nhat trong chu trinh am------------------*/void Tim_hQ1(float x1[MAX][MAX], int m1, int n1, int o1, float bk1[100]){int i, j, k, w, s1, r1;for(k = 0; k < m1+n1; k++) bk1[k]=0;bk1[0] = x1[o1][0]; x1[o1][0] = 0; k = 0; w = 0, s1 = 0, r1 = o1;while(w < m1+n1){ j = s1; for(i = 0; i < m1; i++) if(x1[i][j] > 0) { r1 = i; bk1[k+1] = x1[i][j]; x1[i][j] = 0; k = k + 1; }i = r1;for(j = 0; j <= n1; j++)if(x1[i][j] > 0){s1 = j; bk1[k+1] = x1[i][j]; x1[i][j] = 0; k = k + 1;} w = w + 1;} printf("\n\nIn ma tran bk.\n\n"); for(i = 0; i < m1+n1; i++) printf("%4.0f", bk1[i]);}/*---------------------------------Ham tim h_min------------------------------*/void Tim_hQ2(float x1[MAX][MAX], int m1, int n1, int r1, int s1, float bk1[100], float bk2[100]){int i, j, k, k1, k2, w;for(k = 0; k < m1+n1; k++) { bk1[k]= 0; bk2[k]= 0; }bk1[0] = x1[r1][s1]; x1[r1][s1] = 0; k1 = 0; w = 0; k2 = 0;while(w < m1+n1){ j = s1; for(i = 0; i < m1; i++) if(x1[i][j] > 0) { if(j == 0) { r1 = i; bk1[k1+1] = x1[i][j]; x1[i][j] = 0; k1 = k1 + 1; } else { r1 = i; bk2[k2] = x1[i][j]; x1[i][j] = 0; k2 = k2 + 1; } } i = r1;for(j = 0; j <= n1; j++)if(x1[i][j] > 0){ if(j == 0) {s1 = j; bk2[k2] = x1[i][j]; x1[i][j] = 0; k2 = k2 + 1; } else { s1 = j; bk1[k1+1] = x1[i][j]; x1[i][j] = 0; k1 = k1+1; }} w = w + 1;}}/*-----------Giai bai toan (P) du lieu duoc nhap vao tu file du lieu----------*/void GiaiBaiToanPTuFile(){/*----------------KHAI BAO CAC HAM VA DU LIEU CUA BAI TOAN (P)----------------*/FILE *fpt; FILE *fptr; void Store_Row_Column(float X1[MAX][MAX], int Row1[100], int Column1[100], int m1, int n1); void Tim_h(float x1[MAX][MAX], int m1, int n1, int r1, int s1, float BK1[100]); void KhoiTaoPACBQ(float x1[MAX][MAX], int m1, int n1); void ChuyenDoi_Q(float x1[MAX][MAX], float x2[MAX][MAX], int m1, int n1); void InPhuongAnQ(float x1[MAX][MAX], int m1, int n1); void ChuyenDoiQ(float x1[MAX][MAX], float x2[MAX][MAX], int m1, int n1); void TimChuTrinhQ(float x1[MAX][MAX], int m1, int n1); void Tim_hQ1(float x1[MAX][MAX], int m1, int n1, int o1, float BK1[100]); int Tim_hP(float x1[MAX][MAX], int m1, int n1, int r1, int s1, float bk1[100], float bk2[100], float at[100],float ad[100]); void GiaiHe(int n1, float A1[MAX][MAX], float B1[MAX], float x1[MAX]);void GiaiBaiToanVanTai(float A[100], float C[MAX][MAX], float x[MAX][MAX], int m, int n); void InMaTranPA(float x1[MAX][MAX], int m1, int n1); void NhapCuocPhi(float C1[MAX][MAX], int m1, int n1); void NhapThuPhat(float A1[100], int m1, int n1); void InCuocPhi(float C1[MAX][MAX], int m1, int n1); void InThuPhat(float A1[100], int m1, int n1);void InMaTranPA(float x1[MAX][MAX], int m1, int n1); void ChuyenDoi_2(float C1[MAX][MAX], float C2[MAX][MAX], int m1, int n1); float cp[MAX][MAX], cp1[MAX][MAX], xp[MAX][MAX], yp[MAX][MAX], xp1[MAX][MAX], xp2[MAX][MAX], zp[MAX][MAX]; float cp2[MAX][MAX], uij[MAX], d[MAX][MAX], cij[MAX], BK[100], ad[MAX], at[MAX], atg[MAX], a[MAX], b[MAX]; int mp, np, i, j, p, q, k, r, s, o1, o2, rp, sp, u, v, k_min, p1, q1, k1, k2; int Row[100], Column[100], DelRow, DelCol, Test; float e1, e2, e3, h1_min, h2_min, h_min, f_minp, bk1[100], bk2[100]; float bSum = 0, aSum, Value; char fName[MAX]; Value = 0;window(1,1,80,25); textbackground(BLACK); textcolor(WHITE);clrscr(); printf("\n\n********************CHUONG TRINH GIAI BAI TOAN TONG QUAT (P)********************\n\n"); printf("\nNHAP TEN FILE DU LIEU: "); scanf("%20s", &fName); fpt = fopen(fName, "r"); if(fpt == NULL) { printf("\nLOI - KHONG TIM THAY FILE DU LIEU!"); getch(); exit(1); } else { fscanf(fpt, "%d", &mp); fscanf(fpt, "%d", &np); for(i = 0; i < mp; i++) for(j = 0; j < np; j++) { fscanf(fpt, "%f", &cp[i][j]); } for(i = 0; i < mp; i++)fscanf(fpt, "%f", &ad[i]);for(i = 0; i < mp; i++)fscanf(fpt, "%f", &at[i]); for(j = 0; j < np; j++) fscanf(fpt, "%f", &b[j]); } fclose(fpt); fptr = fopen("C:\\KetQua_P.txt", "w"); fprintf(fptr,"\n\n********************CHUONG TRINH GIAI BAI TOAN TONG QUAT (P)********************\n\n"); printf("\n\nSO TRAM PHAT %d, \n\nSO TRAM THU %d", mp, np); fprintf(fptr, "\n\nSO TRAM PHAT %d, \n\nSO TRAM THU %d", mp, np);printf("\n\nIN MA TRAN CUOC PHI\n\n"); InCuocPhi(cp, mp, np); fprintf(fptr,"\n\nIN MA TRAN CUOC PHI\n\n"); for(i = 0; i < mp; i++) { for(j = 0; j < np; j++) { fprintf(fptr,"%8.1f",cp[i][j]); } fprintf(fptr, "\n"); } printf("\n\nIN VECTO CUNG THAP\n\n"); fprintf(fptr, "\n\nIN VECTO CUNG THAP\n\n"); for(i = 0; i < mp; i++) printf("%4.0f", ad[i]); for(i = 0; i < mp; i++) fprintf(fptr, "%4.0f", ad[i]); printf("\n\nIN VECTO CUNG CAO\n\n"); for(i = 0; i < mp; i++) printf("%4.0f", at[i]); fprintf(fptr,"\n\nIN VECTO CUNG CAO\n\n"); for(i = 0; i < mp; i++) fprintf(fptr,"%4.0f", at[i]); printf("\n\nIN VECTO CAU\n\n"); fprintf(fptr, "\n\nIN VECTO CAU\n\n"); for(j = 0; j < np; j++) printf("%4.0f", b[j]); for(j = 0; j < np; j++) fprintf(fptr, "%4.0f", b[j]); for(j = 0; j < np; j++) bSum = bSum + b[j];/*---------------------THUAT TOAN TAO CAN BANG THU PHAT-----------------------*/ k_min = 0;while (k_min < mp) { if(k_min == 0) { aSum = at[0]; for(i = 1; i < mp; i++) aSum = aSum + ad[i]; } else { aSum = 0; for(i = 0; i <= k_min; i++) aSum = aSum + at[i]; for(j = k_min + 1; j < mp; j++) aSum = aSum + ad[j]; } if(aSum >= bSum) { goto TT; } k_min = k_min + 1; }TT:for(i = 0; i < k_min; i++) atg[i] = at[i]; for(i = k_min + 1; i < mp; i++) atg[i] = ad[i]; aSum = 0; for(i = 0; i < mp; i++) aSum = aSum + atg[i]; atg[k_min] = bSum - aSum; for(i = 0; i < mp; i++) a[i] = atg[i]; for(j = 0; j < np; j++) a[mp+j] = b[j]; printf("\n\nIN VECTO VE PHAI CAN BANG THU PHAT\n\n"); for(i = 0; i < mp+np; i++) printf("%5.0f", a[i]); fprintf(fptr, "\n\nIN VECTO VE PHAI CAN BANG THU PHAT\n\n"); for(i = 0; i < mp+np; i++) fprintf(fptr, "%5.0f", a[i]);/*------------------GIAI BAI TOAN VAN TAI CAN BANG THU PHAT-------------------*/ChuyenDoi_Q(cp1, cp, mp, np); ChuyenDoiQ(cp2, cp, mp, np); KhoiTaoPACBQ(xp, mp, np); KhoiTaoPACBQ(xp1, mp, np); KhoiTaoPACBQ(xp2, mp, np); GiaiBaiToanVanTai(a, cp, zp, mp, np); fprintf(fptr,"\n\nPHUONG AN TOI UU BAI TOAN VAN TAI\n\n"); for(i = 0; i < mp; i++) { for(j = 0; j < np; j++) { if(zp[i][j] > 0) fprintf(fptr,"%8.1f", zp[i][j]); else fprintf(fptr,"%8.1f", 0); } fprintf(fptr,"\n"); } float f_minvt = 0; for(i = 0; i < mp; i++) for(j = 0; j < np; j++) { f_minvt = f_minvt + cp2[i][j]*zp[i][j]; } printf("\n\n"); fprintf(fptr,"\n\nGIA TRI HAM MUC TIEU TOI UU BAI TOAN VAN TAI LA %4.1f", f_minvt);/*-------------------TAO PHUONG AN CUC BIEN CHO BAI TOAN (P)------------------*/ ChuyenDoi_Q(xp, zp, mp, np); for(i = 0; i < k_min; i++) xp[i][0] = at[i] - ad[i]; xp[k_min][0] = atg[k_min] - ad[k_min]; for(i = k_min + 1; i < mp; i++) xp[i][0] = 0; printf("\n\nPHUONG AN CUC BIEN CUA BAI TOAN (P)\n\n"); InPhuongAnQ(xp, mp, np); fprintf(fptr, "\n\nPHUONG AN CUC BIEN CUA BAI TOAN (P)\n\n"); for(i = 0; i < mp; i++) { for(j = 0; j <= np; j++) { if(xp[i][j] > 0) fprintf(fptr,"%8.1f", xp[i][j]); else fprintf(fptr,"%8.1f", 0); } fprintf(fptr,"\n"); } ChuyenDoiQ(yp, xp, mp, np); for(i = 0; i < mp; i++) if(xp[i][0] == (at[i] - ad[i])) { xp[i][0] = 0; } Store_Row_Column(xp, Row, Column, mp, np); ChuyenDoiQ(xp, yp, mp, np);/*------------------BAT DAU VONG LAP CHINH CUA BAI TOAN (P)-------------------*/int dem = 0;while(true){ printf("\n\n******************************************************************\n\n"); printf("BUOC LAP THU %d", dem +1); fprintf(fptr, "BUOC LAP THU %d", dem +1); ChuyenDoiQ(cp, cp1, mp, np); ChuyenDoiQ(yp, xp, mp, np); for(i = 0; i < mp + np; i++) { uij[i] = 0; cij[i] = 0; } for(i = 0; i < mp + np; i++) for(j = 0; j < mp + np; j++) { d[i][j] = 0; } for(i = 0; i < mp + np; i++) fprintf(fptr,"\n(%d, %d)", Row[i], Column[i]); k = 0; while(k < mp + np) { if(Column[k] != 0) {d[k][Row[k]] = 1; d[k][mp + Column[k] - 1] = 1; } else { d[k][Row[k]] = 1; } k = k + 1; } k = 0; while(k < mp + np) { cij[k] = cp[Row[k]][Column[k]]; k = k + 1; } ChuyenDoiQ(xp, yp, mp, np); /* printf("\n\nMa tran d\n\n"); for(i = 0; i < mp + np; i++) { for(j = 0; j < mp + np; j++) { fprintf(fptr,"%8.1f", d[i][j]); } fprintf(fptr,"\n"); } printf("\n\nMa tran cij\n\n"); for(i = 0; i < mp + np; i++) printf("%8.1f", cij[i]); */ GiaiHe(mp+np, d, cij, uij); printf("\n\nIN THE VI HANG U\n\n"); for(i = 0; i < mp; i++) printf("\nU[%d] = %4.0f",i, uij[i]); printf("\n\nIN THE VI COT V\n\n"); for(j = 0; j < np; j++) printf("\nV[%d] = %4.0f",j, uij[mp+j]); fprintf(fptr, "\n\nIN THE VI HANG U\n\n"); for(i = 0; i < mp; i++) fprintf(fptr, "\nU[%d] = %4.0f",i, uij[i]); fprintf(fptr, "\n\nIN THE VI COT U\n\n"); for(j = 0; j < np; j++) fprintf(fptr,"\nV[%d] = %4.0f", j, uij[mp+j]);/*------------------------KIEM TRA TIEU CHUAN TOI UU--------------------------*/ e1 = 1000; e2 = 1000; e3 = -1000; for(i = 0; i < mp; i++) for(j = 1; j <= np; j++) { cp[i][j] = cp[i][j] - (uij[i] + uij[mp + j - 1]); if(e1 > cp[i][j]) e1 = cp[i][j]; } for(i = 0; i < mp; i++) for(j = 1; j <= np; j++) { if(cp[i][j] == e1) { rp = i; sp = j; } } for(i = 0; i < mp ; i++) if((e2 > uij[i]) && (xp[i][0] == 0)) { e2 = uij[i]; o1 = i; } for(i = 0; i < mp; i++) if((e3 < uij[i]) && (xp[i][0] == (at[i]- ad[i]))) { e3 = uij[i]; o2 = i; } /* fprintf(fptr,"\n\nGia tri e1 la: %4.0f", e1); fprintf(fptr,"\n\nGia tri e2 la: %4.0f", e2); fprintf(fptr,"\n\nGia tri e3 la: %4.0f", e3); fprintf(fptr,"\n\nGia tri o1 la: %4d", o1); fprintf(fptr,"\n\nGia tri o2 la: %4d", o2); */ if((e1 >= 0) && (e2 >= 0) && (e3 <= 0)) goto KQ; else { if(e3 > 0) { for(i = 0; i < mp; i++) if(xp[i][0] == (at[i] - ad[i])) xp[i][0] = 0; xp[o2][0] = 1000; TimChuTrinhQ(xp, mp, np); ChuyenDoiQ(xp1, xp, mp, np); ChuyenDoiQ(xp2, xp, mp, np); printf("\n\nCHU TRINH VUA TIM LA\n\n"); InPhuongAnQ(xp, mp, np); fprintf(fptr, "\n\nCHU TRINH VUA TIM LA\n\n"); for(i = 0; i < mp; i++) { for(j = 0; j <= np; j++) { if(xp[i][j] > 0) fprintf(fptr, "%8.1f", xp[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr, "\n"); } h2_min = 1000; Tim_hQ1(xp, mp, np, o2, BK); h1_min = BK[0]; for(i = 3; i < mp+np; i = i+2) if(h1_min > BK[i]&& BK[i] > 0) h1_min = BK[i];for(i = 0; i < mp; i++)xp[i][0] = xp1[i][0]; for(i = 0; i < mp; i++) if((xp[i][0] > 0) && (xp[i][0] < (at[i] - ad[i]))) h2_min = at[i] - ad[i]; h2_min = h2_min - BK[1]; if(h1_min >= h2_min) h_min = h2_min; else h_min = h1_min; printf("\n\nLUONG HANG NHO NHAT h_min = %4.0f", h_min); fprintf(fptr, "\n\nLUONG HANG NHO NHAT h_min = %4.0f", h_min); ChuyenDoiQ(xp, xp1, mp, np);r = o2; s = 0; k = 0; j = s; for(i = 0; i < mp; i++) { if(xp[i][j] > 0 && h_min == (at[i] - ad[i] - xp[i][j])) { DelRow = i; DelCol = j; goto QQ; } }while(k < mp + np) { j = s; for(i = 0; i < mp; i++) { if(xp[i][j] > 0 && h_min == xp[i][j]) { DelRow = i; DelCol = j; goto QQ; } if(xp[i][j] > 0 && h_min != xp[i][j]) { xp[i][j] = 0; r = i; } } i = r; for(j = 0; j <= np; j++) { if(xp[i][j] > 0 && h_min == xp[i][j]) { DelRow = i; DelCol = j; goto QQ; } if(xp[i][j] > 0 && h_min != xp[i][j]) { xp[i][j] = 0; s = j; } } k = k + 1; }QQ: for(k = 0; k < mp + np; k++) if(Row[k] == DelRow && Column[k] == DelCol) { Row[k] = o2; Column[k] = 0; }ChuyenDoiQ(xp, xp1, mp, np); for(i = 0; i < mp; i++) for(j = 0; j <= np; j++) { if(yp[i][j] != xp1[i][j]) { xp[i][j] = yp[i][j]; } } r = o2; s = 0; u = r; v = s; xp1[r][s] = 0; xp2[r][s] = 0; xp[r][s] = yp[r][s] - h_min; j = s; for(i = 0; i < mp; i++) if(xp1[i][j] > 0) xp[i][j] = xp[i][j] + h_min; k = 2; while(k < mp+np) { j = s; for(i = 0; i < mp; i++) if(xp1[i][j] > 0) { r = i; xp1[i][j] = 0; } i = r; for(j = 0; j <= np; j++) if(xp1[i][j] > 0) { s = j; if(xp1[i][j] == BK[k] && BK[k] > 0) xp[i][j] = BK[k] + h_min; xp1[i][j] = 0; } k = k + 2; } j = v; for(i = 0; i < mp; i++) if(xp2[i][j] > 0) { u = i; xp2[i][j] = 0; } k = 3; while(k < mp + np) { i = u; for(j = 0; j <= np; j++) if(xp2[i][j] > 0) { v = j; xp2[i][j] = 0; } j = v; for(i = 0; i < mp; i++) if(xp2[i][j] > 0) { u = i; if(xp2[i][j] == BK[k] && BK[k] > 0) xp[i][j] = BK[k] - h_min; xp2[i][j] = 0; } k = k + 2; } printf("\n\nPHUONG AN CUC BIEN MOI\n\n"); InPhuongAnQ(xp, mp, np); fprintf(fptr, "\n\nPHUONG AN CUC BIEN MOI\n\n"); for(i = 0; i < mp; i++) { for(j = 0; j <= np; j++) { if(xp[i][j] > 0) fprintf(fptr, "%8.1f", xp[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr, "\n"); } } else { if((e2 < 0) && (e2 <= e1)) { for(i = 0; i < mp; i++) if(xp[i][0] == (at[i] - ad[i])) xp[i][0] = 0; xp[o1][0] = 1000; TimChuTrinhQ(xp, mp, np); ChuyenDoiQ(xp1, xp, mp, np); ChuyenDoiQ(xp2, xp, mp, np); printf("\n\nCHU TRINH VUA TIM LA\n\n"); InPhuongAnQ(xp, mp, np); fprintf(fptr, "\n\nCHU TRINH VUA TIM LA\n\n"); for(i = 0; i < mp; i++) { for(j = 0; j <= np; j++) { if(xp[i][j] > 0) fprintf(fptr, "%8.1f", xp[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr, "\n"); } Tim_hQ1(xp, mp, np, o1, BK); h_min = BK[1]; for(i = 2; i < mp + np; i = i + 2) if(h_min > BK[i]&& BK[i] > 0) h_min = BK[i]; printf("\n\nLUONG HANG NHO NHAT h_min = %4.0f", h_min); fprintf(fptr, "\n\nLUONG HANG NHO NHAT h_min = %4.0f", h_min); ChuyenDoiQ(xp, xp1, mp, np); k = 0; r = o1; s = 0; xp[r][s] = 0; while(k < mp + np) { j = s; for(i = 0; i < mp; i++) { if(xp[i][j] > 0 && xp[i][j] == h_min) { DelRow = i; DelCol = j; goto QQ1; } if(xp[i][j] > 0 && xp[i][j] != h_min) { r = i; xp[i][j] = 0; } } i = r; for(j = 0; j <= np; j++) { if(xp[i][j] > 0 && xp[i][j] == h_min) { DelRow = i; DelCol = j; goto QQ1; } if(xp[i][j] > 0 && xp[i][j] != h_min) { s = j; xp[i][j] = 0; } } k = k + 1; }QQ1: for(k = 0; k < mp + np; k++) if(Row[k] == DelRow && Column[k] == DelCol) { Row[k] = o1; Column[k] = 0; } ChuyenDoiQ(xp, xp1, mp, np); for(i = 0; i < mp; i++) for(j = 0; j <= np; j++) { if(yp[i][j] != xp1[i][j]) { xp[i][j] = yp[i][j]; } } r = o1; s = 0; u = r; v = s; xp1[r][s] = 0; xp2[r][s] = 0; xp[r][s] = h_min; j = s; for(i = 0; i < mp; i++) if(xp1[i][j] > 0) xp[i][j] = xp[i][j] - h_min; k = 2; while(k < mp + np) { j = s; for(i = 0; i < mp; i++) if(xp1[i][j] > 0) { r = i; xp1[i][j] = 0; } i = r; for(j = 0; j <= np; j++) if(xp1[i][j] > 0) { s = j; if(xp1[i][j] == BK[k] && BK[k] > 0) xp[i][j] = BK[k] - h_min; xp1[i][j] = 0; } k = k + 2; } j = v; for(i = 0; i < mp; i++) if(xp2[i][j] > 0) { u = i; xp2[i][j] = 0; } k = 3; while(k < mp+np) { i = u; for(j = 0; j <= np; j++) if(xp2[i][j] > 0) { v = j; xp2[i][j] = 0; } j = v; for(i = 0; i < mp; i++) if(xp2[i][j] > 0) { u = i; if(xp2[i][j] == BK[k] && BK[k] > 0) xp[i][j] = BK[k] + h_min; xp2[i][j] = 0; } k = k + 2; } printf("\n\nPHUONG AN CUC BIEN MOI\n\n"); InPhuongAnQ(xp, mp, np); fprintf(fptr, "\n\nPHUONG AN CUC BIEN MOI\n\n"); for(i = 0; i < mp; i++) { for(j = 0; j <= np; j++) { if(xp[i][j] > 0) fprintf(fptr, "%8.1f", xp[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr, "\n"); } } if((e1 < 0) && (e1 <= e2)) { for(i = 0; i < mp; i++) if(xp[i][0] == (at[i] - ad[i])) xp[i][0] = 0; xp[rp][sp] = 1000; TimChuTrinhQ(xp, mp, np); ChuyenDoiQ(xp1, xp, mp, np); ChuyenDoiQ(xp2, xp, mp, np); printf("\n\nCHU TRINH VUA TIM LA\n\n"); InPhuongAnQ(xp, mp, np); fprintf(fptr, "\n\nCHU TRINH VUA TIM LA\n\n"); for(i = 0; i < mp; i++) { for(j = 0; j <= np; j++) { if(xp[i][j] > 0) fprintf(fptr, "%8.1f", xp[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr, "\n"); } i = 0; Test = 0; while(i < mp) { if(xp[i][0] > 0) { Test = Test + 1; } i = i + 1; } if(Test != 0) { Value = Tim_hP(xp, mp, np, rp, sp, bk1, bk2, at, ad); ChuyenDoiQ(xp, xp1, mp, np); fprintf(fptr, "\nIn bk1, bk2\n"); for(i = 0; i < mp + np; i++) { fprintf(fptr, "\nbk1[%d] = %5.0f", i, bk1[i]); } for(i = 0; i < mp + np; i++) { fprintf(fptr, "\nbk2[%d] = %5.0f", i, bk2[i]); } h1_min = 1000; h2_min = 1000; for(i = 1; i < mp+np; i++) if((h1_min > bk2[i])&& bk2[i] > 0) h1_min = bk2[i]; h2_min = Value; if(h1_min >= h2_min) h_min = h2_min; else h_min = h1_min; printf("\n\nLUONG HANG NHO NHAT h_min = %4.0f", h_min); fprintf(fptr, "\n\nLUONG HANG NHO NHAT h_min = %4.0f", h_min); ChuyenDoiQ(xp, xp1, mp, np);r = rp; s = sp; k = 0; i = rp; DelRow = 0; DelCol = 0;while(k < mp + np) { i = r; for(j = 0; j <= np; j++) { if((j == 0) && (xp[i][j] > 0) && (h_min == Value)) { DelRow = i; DelCol = j; goto QQ2; } if(xp[i][j] > 0 && h_min == xp[i][j]) { DelRow = i; DelCol = j; goto QQ2; } if(xp[i][j] > 0 && h_min != xp[i][j]) { xp[i][j] = 0; s = j; } } j = s; for(i = 0; i < mp; i++) { if(xp[i][j] > 0 && h_min == xp[i][j]) { DelRow = i; DelCol = j; goto QQ2; } if(xp[i][j] > 0 && h_min != xp[i][j]) { xp[i][j] = 0; r = i; } } k = k + 1; }QQ2: for(k = 0; k < mp + np; k++) if(Row[k] == DelRow && Column[k] == DelCol) { Row[k] = rp; Column[k] = sp; } ChuyenDoiQ(xp, xp1, mp, np); for(i = 0; i < mp; i++) for(j = 0; j <= np; j++) { if(yp[i][j] != xp1[i][j]) { xp[i][j] = yp[i][j]; } } r = rp; s = sp; xp1[r][s] = 0; xp2[r][s] = 0; xp[r][s] = h_min; k = 0; k1 = 1; k2 = 0; while(k < mp + np) { i = rp; for(j = 0; j <= np; j++) { if(xp1[i][j] > 0) { if(j == 0) { sp = j; if(xp1[i][j] == bk1[k1] && bk1[k1] > 0) xp[i][j] = bk1[k1] + h_min; xp1[i][j] = 0; k1 = k1 + 1; } else { sp = j; if(xp1[i][j] == bk2[k2] && bk2[k2] > 0) xp[i][j] = bk2[k2] - h_min; xp1[i][j] = 0; k2 = k2 + 1; } } } j = sp; for(i = 0; i < mp; i++) { if(xp1[i][j] > 0) { if(j == 0) { rp = i; if(xp1[i][j] == bk2[k2] && bk2[k2] > 0) xp[i][j] = bk2[k2] - h_min; xp1[i][j] = 0; k2 = k2 + 1; } else { rp = i; if(xp1[i][j] = bk1[k1] && bk1[k1] > 0) xp[i][j] = bk1[k1] + h_min; xp1[i][j] = 0; k1 = k1 + 1; } } } k = k + 1; } printf("\n\nPHUONG AN CUC BIEN MOI\n\n"); InPhuongAnQ(xp, mp, np); fprintf(fptr, "\n\nPHUONG AN CUC BIEN MOI\n\n"); for(i = 0; i < mp; i++) { for(j = 0; j <= np; j++) { if(xp[i][j] > 0) fprintf(fptr, "%8.1f", xp[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr, "\n"); } } if(Test == 0) { h_min = 1000; Tim_h(xp, mp, np, rp, sp, BK); for(k = 1; k < mp+np; k = k+2)if(h_min > BK[k] && BK[k]>0) h_min = BK[k]; printf("\n\nLUONG HANG NHO NHAT h_min = %4.0f", h_min); fprintf(fptr, "\n\nLUONG HANG NHO NHAT h_min = %4.0f", h_min); ChuyenDoiQ(xp, xp1, mp, np); r = rp; s = sp; k = 0; DelRow = 0; DelCol = 0;while(k < mp + np) { i = r; for(j = 0; j <= np; j++) { if(xp[i][j] > 0 && h_min == xp[i][j]) { DelRow = i; DelCol = j; goto QQ3; } if(xp[i][j] > 0 && h_min != xp[i][j]) { xp[i][j] = 0; s = j; } } j = s; for(i = 0; i < mp; i++) { if(xp[i][j] > 0 && h_min == xp[i][j]) { DelRow = i; DelCol = j; goto QQ3; } if(xp[i][j] > 0 && h_min != xp[i][j]) { xp[i][j] = 0; r = i; } } k = k + 1; }QQ3: for(k = 0; k < mp + np; k++) if(Row[k] == DelRow && Column[k] == DelCol) { Row[k] = rp; Column[k] = sp; } ChuyenDoiQ(xp, xp1, mp, np); for(i = 0; i < mp; i++) for(j = 0; j <= np; j++) { if(yp[i][j] != xp1[i][j]) xp[i][j] = yp[i][j]; } p1 = rp; q1 = sp;xp1[rp][sp] = 0; xp2[rp][sp] = 0; xp[rp][sp] = h_min; k = 2; while(k < mp+np) { i = rp; for(j = 0; j <= np; j++) if(xp1[i][j] > 0) { q = j; xp1[i][j] = 0; } j = q; for(i = 0; i < mp; i++) if(xp1[i][j] > 0) { rp = i; if(xp1[i][j] == BK[k] && BK[k] > 0) xp[i][j] = BK[k] + h_min; xp1[i][j] = 0; } k = k + 2; } k = 1; while(k < mp+np) { i = p1; for(j = 0; j <= np; j++) if(xp2[i][j] > 0) { q1 = j; if(xp2[i][j] == BK[k] && BK[k] > 0) xp[i][j] = BK[k] - h_min; xp2[i][j] = 0; } j = q1; for(i = 0; i < mp; i++) if(xp2[i][j] > 0) p1 = i; xp2[i][j] = 0; k = k + 2; } printf("\n\nPHUONG AN CUC BIEN MOI\n\n"); InPhuongAnQ(xp, mp, np); fprintf(fptr, "\n\nPHUONG AN CUC BIEN MOI\n\n"); for(i = 0; i < mp; i++) { for(j = 0; j <= np; j++) { if(xp[i][j] > 0) fprintf(fptr, "%8.1f", xp[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr, "\n"); } } } } } dem = dem + 1;}KQ: printf("\n\nPHUONG AN TOI CUA BAI TOAN (P)\n\n");InPhuongAnQ(xp, mp, np); fprintf(fptr, "\n\nPHUONG AN TOI CUA BAI TOAN (P)\n\n");for(i = 0; i < mp; i++) { for(j = 0; j <= np; j++) { if(xp[i][j] > 0) fprintf(fptr, "%8.1f", xp[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr, "\n"); } f_minp = 0;for(i = 0; i < mp; i++) for(j = 0; j <= np; j++) { f_minp = f_minp + xp[i][j]* cp1[i][j]; } printf("\n\nGIA TRI HAM MUC TIEU TOI UU CUA (P) F_MINP = %4.1f", f_minp); fprintf(fptr,"\n\nGIA TRI HAM MUC TIEU TOI UU CUA (P) F_MINP = %4.1f", f_minp); printf("\n\nSO BUOC LAP THUC HIEN %d", dem); fprintf(fptr, "\n\nSO BUOC LAP THUC HIEN %d", dem);fclose(fptr); printf("\n\nAn phim M hoac m de tro ve Menu chuong trinh"); char ch = getch(); if((ch == 'M')||(ch == 'm')) { mainMenu(); } else { exit(1); }}/*------------Giai bai toan (P) du lieu duoc nhap vao tu ban phim-------------*/void GiaiBaiToanPTuBanPhim(){/*----------------KHAI BAO CAC HAM VA DU LIEU CUA BAI TOAN (P)----------------*/ FILE *fptr; void Store_Row_Column(float X1[MAX][MAX], int Row1[100], int Column1[100], int m1, int n1); void Tim_h(float x1[MAX][MAX], int m1, int n1, int r1, int s1, float BK1[100]); void KhoiTaoPACBQ(float x1[MAX][MAX], int m1, int n1); void ChuyenDoi_Q(float x1[MAX][MAX], float x2[MAX][MAX], int m1, int n1); void InPhuongAnQ(float x1[MAX][MAX], int m1, int n1); void ChuyenDoiQ(float x1[MAX][MAX], float x2[MAX][MAX], int m1, int n1); void TimChuTrinhQ(float x1[MAX][MAX], int m1, int n1); void Tim_hQ1(float x1[MAX][MAX], int m1, int n1, int o1, float BK1[100]); int Tim_hP(float x1[MAX][MAX], int m1, int n1, int r1, int s1, float bk1[100], float bk2[100], float at[100],float ad[100]); void GiaiHe(int n1, float A1[MAX][MAX], float B1[MAX], float x1[MAX]);void GiaiBaiToanVanTai(float A[100], float C[MAX][MAX], float x[MAX][MAX], int m, int n); void InMaTranPA(float x1[MAX][MAX], int m1, int n1); void NhapCuocPhi(float C1[MAX][MAX], int m1, int n1); void NhapThuPhat(float A1[100], int m1, int n1); void InCuocPhi(float C1[MAX][MAX], int m1, int n1); void InThuPhat(float A1[100], int m1, int n1);void InMaTranPA(float x1[MAX][MAX], int m1, int n1); void ChuyenDoi_2(float C1[MAX][MAX], float C2[MAX][MAX], int m1, int n1); float cp[MAX][MAX], cp1[MAX][MAX], xp[MAX][MAX], yp[MAX][MAX], xp1[MAX][MAX], xp2[MAX][MAX], zp[MAX][MAX]; float cp2[MAX][MAX], uij[MAX], d[MAX][MAX], cij[MAX], BK[100], ad[MAX], at[MAX], atg[MAX], a[MAX], b[MAX]; int mp, np, i, j, p, q, k, r, s, o1, o2, rp, sp, u, v, k_min, p1, q1, k1, k2; int Row[100], Column[100], DelRow, DelCol, Test; float e1, e2, e3, h1_min, h2_min, h_min, f_minp, bk1[100], bk2[100]; float bSum = 0, aSum, Value; char fName[MAX]; Value = 0;window(1,1,80,25); textbackground(BLACK); textcolor(WHITE);clrscr(); fptr = fopen("C:\\KetQua_P.txt", "w"); printf("\n\n********************CHUONG TRINH GIAI BAI TOAN TONG QUAT (P)********************\n\n"); fprintf(fptr,"\n\n************************CHUONG TRINH GIAI BAI TOAN TONG QUAT (P)**************************\n\n"); printf("NHAP KICH THUOC BAI TOAN\n\n"); printf("NHAP SO TRAM PHAT: "); scanf("%d", &mp); printf("NHAP SO TRAM THU: "); scanf("%d", &np); printf("\nNHAP MA TRAN CUOC PHI CQ\n"); NhapCuocPhi(cp, mp, np); printf("\nNHAP KHA NANG CUNG THAP\n"); for(i = 0; i < mp; i++) { printf("ad[%d] = ", i); scanf("%f", &ad[i]); } printf("\nNHAP KHA NANG CUNG CAO\n"); for(i = 0; i < mp; i++) { printf("at[%d] = ", i); scanf("%f", &at[i]); } printf("\nNHAP KHA NANG CAU\n"); for(j = 0; j < np; j++) { printf("b[%d] = ", j); scanf("%f", &b[j]); }printf("\n\nMA TRAN CUOC PHI\n\n"); fprintf(fptr, "\n\nMA TRAN CUOC PHI\n\n"); InCuocPhi(cp, mp, np); fprintf(fptr,"\n\n********************CHUONG TRINH GIAI BAI TOAN TONG QUAT (P)********************\n\n"); printf("\n\nSO TRAM PHAT %d, \n\nSO TRAM THU %d", mp, np); fprintf(fptr, "\n\nSO TRAM PHAT %d, \n\nSO TRAM THU %d", mp, np);printf("\n\nIN MA TRAN CUOC PHI\n\n"); InCuocPhi(cp, mp, np); fprintf(fptr,"\n\nIN MA TRAN CUOC PHI\n\n"); for(i = 0; i < mp; i++) { for(j = 0; j < np; j++) { fprintf(fptr,"%8.1f",cp[i][j]); } fprintf(fptr, "\n"); } printf("\n\nIN VECTO CUNG THAP\n\n"); fprintf(fptr, "\n\nIN VECTO CUNG THAP\n\n"); for(i = 0; i < mp; i++) printf("%4.0f", ad[i]); for(i = 0; i < mp; i++) fprintf(fptr, "%4.0f", ad[i]); printf("\n\nIN VECTO CUNG CAO\n\n"); for(i = 0; i < mp; i++) printf("%4.0f", at[i]); fprintf(fptr,"\n\nIN VECTO CUNG CAO\n\n"); for(i = 0; i < mp; i++) fprintf(fptr,"%4.0f", at[i]); printf("\n\nIN VECTO CAU\n\n"); fprintf(fptr, "\n\nIN VECTO CAU\n\n"); for(j = 0; j < np; j++) printf("%4.0f", b[j]); for(j = 0; j < np; j++) fprintf(fptr, "%4.0f", b[j]); for(j = 0; j < np; j++) bSum = bSum + b[j];/*---------------------THUAT TOAN TAO CAN BANG THU PHAT-----------------------*/ k_min = 0;while (k_min < mp) { if(k_min == 0) { aSum = at[0]; for(i = 1; i < mp; i++) aSum = aSum + ad[i]; } else { aSum = 0; for(i = 0; i <= k_min; i++) aSum = aSum + at[i]; for(j = k_min + 1; j < mp; j++) aSum = aSum + ad[j]; } if(aSum >= bSum) { goto TT; } k_min = k_min + 1; }TT:for(i = 0; i < k_min; i++) atg[i] = at[i]; for(i = k_min + 1; i < mp; i++) atg[i] = ad[i]; aSum = 0; for(i = 0; i < mp; i++) aSum = aSum + atg[i]; atg[k_min] = bSum - aSum; for(i = 0; i < mp; i++) a[i] = atg[i]; for(j = 0; j < np; j++) a[mp+j] = b[j]; printf("\n\nIN VECTO VE PHAI CAN BANG THU PHAT\n\n"); for(i = 0; i < mp+np; i++) printf("%5.0f", a[i]); fprintf(fptr, "\n\nIN VECTO VE PHAI CAN BANG THU PHAT\n\n"); for(i = 0; i < mp+np; i++) fprintf(fptr, "%5.0f", a[i]);/*------------------GIAI BAI TOAN VAN TAI CAN BANG THU PHAT-------------------*/ChuyenDoi_Q(cp1, cp, mp, np); ChuyenDoiQ(cp2, cp, mp, np); KhoiTaoPACBQ(xp, mp, np); KhoiTaoPACBQ(xp1, mp, np); KhoiTaoPACBQ(xp2, mp, np); GiaiBaiToanVanTai(a, cp, zp, mp, np); fprintf(fptr,"\n\nPHUONG AN TOI UU BAI TOAN VAN TAI\n\n"); for(i = 0; i < mp; i++) { for(j = 0; j < np; j++) { if(zp[i][j] > 0) fprintf(fptr,"%8.1f", zp[i][j]); else fprintf(fptr,"%8.1f", 0); } fprintf(fptr,"\n"); } float f_minvt = 0; for(i = 0; i < mp; i++) for(j = 0; j < np; j++) { f_minvt = f_minvt + cp2[i][j]*zp[i][j]; } printf("\n\n"); fprintf(fptr,"\n\nGIA TRI HAM MUC TIEU TOI UU BAI TOAN VAN TAI LA %4.1f", f_minvt);/*-------------------TAO PHUONG AN CUC BIEN CHO BAI TOAN (P)------------------*/ ChuyenDoi_Q(xp, zp, mp, np); for(i = 0; i < k_min; i++) xp[i][0] = at[i] - ad[i]; xp[k_min][0] = atg[k_min] - ad[k_min]; for(i = k_min + 1; i < mp; i++) xp[i][0] = 0; printf("\n\nPHUONG AN CUC BIEN CUA BAI TOAN (P)\n\n"); InPhuongAnQ(xp, mp, np); fprintf(fptr, "\n\nPHUONG AN CUC BIEN CUA BAI TOAN (P)\n\n"); for(i = 0; i < mp; i++) { for(j = 0; j <= np; j++) { if(xp[i][j] > 0) fprintf(fptr,"%8.1f", xp[i][j]); else fprintf(fptr,"%8.1f", 0); } fprintf(fptr,"\n"); } ChuyenDoiQ(yp, xp, mp, np); for(i = 0; i < mp; i++) if(xp[i][0] == (at[i] - ad[i])) { xp[i][0] = 0; } Store_Row_Column(xp, Row, Column, mp, np); ChuyenDoiQ(xp, yp, mp, np);/*------------------BAT DAU VONG LAP CHINH CUA BAI TOAN (P)-------------------*/int dem = 0;while(true){ printf("\n\n******************************************************************\n\n"); printf("BUOC LAP THU %d", dem +1); fprintf(fptr, "BUOC LAP THU %d", dem +1); ChuyenDoiQ(cp, cp1, mp, np); ChuyenDoiQ(yp, xp, mp, np); for(i = 0; i < mp + np; i++) { uij[i] = 0; cij[i] = 0; } for(i = 0; i < mp + np; i++) for(j = 0; j < mp + np; j++) { d[i][j] = 0; } for(i = 0; i < mp + np; i++) fprintf(fptr,"\n(%d, %d)", Row[i], Column[i]); k = 0; while(k < mp + np) { if(Column[k] != 0) {d[k][Row[k]] = 1; d[k][mp + Column[k] - 1] = 1; } else { d[k][Row[k]] = 1; } k = k + 1; } k = 0; while(k < mp + np) { cij[k] = cp[Row[k]][Column[k]]; k = k + 1; } ChuyenDoiQ(xp, yp, mp, np); printf("\n\nMa tran d\n\n"); for(i = 0; i < mp + np; i++) { for(j = 0; j < mp + np; j++) { fprintf(fptr,"%8.1f", d[i][j]); } fprintf(fptr,"\n"); } printf("\n\nMa tran cij\n\n"); for(i = 0; i < mp + np; i++) printf("%8.1f", cij[i]); GiaiHe(mp+np, d, cij, uij); printf("\n\nIN THE VI HANG U\n\n"); for(i = 0; i < mp; i++) printf("\nU[%d] = %4.0f",i, uij[i]); printf("\n\nIN THE VI COT V\n\n"); for(j = 0; j < np; j++) printf("\nV[%d] = %4.0f",j, uij[mp+j]); fprintf(fptr, "\n\nIN THE VI HANG U\n\n"); for(i = 0; i < mp; i++) fprintf(fptr, "\nU[%d] = %4.0f",i, uij[i]); fprintf(fptr, "\n\nIN THE VI COT U\n\n"); for(j = 0; j < np; j++) fprintf(fptr,"\nV[%d] = %4.0f", j, uij[mp+j]);/*------------------------KIEM TRA TIEU CHUAN TOI UU--------------------------*/ e1 = 1000; e2 = 1000; e3 = -1000; for(i = 0; i < mp; i++) for(j = 1; j <= np; j++) { cp[i][j] = cp[i][j] - (uij[i] + uij[mp + j - 1]); if(e1 > cp[i][j]) e1 = cp[i][j]; } for(i = 0; i < mp; i++) for(j = 1; j <= np; j++) { if(cp[i][j] == e1) { rp = i; sp = j; } } for(i = 0; i < mp ; i++) if((e2 > uij[i]) && (xp[i][0] == 0)) { e2 = uij[i]; o1 = i; } for(i = 0; i < mp; i++) if((e3 < uij[i]) && (xp[i][0] == (at[i]- ad[i]))) { e3 = uij[i]; o2 = i; } /*fprintf(fptr,"\n\nGia tri e1 la: %4.0f", e1); fprintf(fptr,"\n\nGia tri e2 la: %4.0f", e2); fprintf(fptr,"\n\nGia tri e3 la: %4.0f", e3); fprintf(fptr,"\n\nGia tri o1 la: %4d", o1); fprintf(fptr,"\n\nGia tri o2 la: %4d", o2);*/ if((e1 >= 0) && (e2 >= 0) && (e3 <= 0)) goto KQ; else { if(e3 > 0) { for(i = 0; i < mp; i++) if(xp[i][0] == (at[i] - ad[i])) xp[i][0] = 0; xp[o2][0] = 1000; TimChuTrinhQ(xp, mp, np); ChuyenDoiQ(xp1, xp, mp, np); ChuyenDoiQ(xp2, xp, mp, np); printf("\n\nCHU TRINH VUA TIM LA\n\n"); InPhuongAnQ(xp, mp, np); fprintf(fptr, "\n\nCHU TRINH VUA TIM LA\n\n"); for(i = 0; i < mp; i++) { for(j = 0; j <= np; j++) { if(xp[i][j] > 0) fprintf(fptr, "%8.1f", xp[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr, "\n"); } h2_min = 1000; Tim_hQ1(xp, mp, np, o2, BK); h1_min = BK[0]; for(i = 3; i < mp+np; i = i+2) if(h1_min > BK[i]&& BK[i] > 0) h1_min = BK[i];for(i = 0; i < mp; i++)xp[i][0] = xp1[i][0]; for(i = 0; i < mp; i++) if((xp[i][0] > 0) && (xp[i][0] < (at[i] - ad[i]))) h2_min = at[i] - ad[i]; h2_min = h2_min - BK[1]; if(h1_min >= h2_min) h_min = h2_min; else h_min = h1_min; printf("\n\nLUONG HANG NHO NHAT h_min = %4.0f", h_min); fprintf(fptr, "\n\nLUONG HANG NHO NHAT h_min = %4.0f", h_min); ChuyenDoiQ(xp, xp1, mp, np);r = o2; s = 0; k = 0; j = s; for(i = 0; i < mp; i++) { if(xp[i][j] > 0 && h_min == (at[i] - ad[i] - xp[i][j])) { DelRow = i; DelCol = j; goto QQ; } }while(k < mp + np) { j = s; for(i = 0; i < mp; i++) { if(xp[i][j] > 0 && h_min == xp[i][j]) { DelRow = i; DelCol = j; goto QQ; } if(xp[i][j] > 0 && h_min != xp[i][j]) { xp[i][j] = 0; r = i; } } i = r; for(j = 0; j <= np; j++) { if(xp[i][j] > 0 && h_min == xp[i][j]) { DelRow = i; DelCol = j; goto QQ; } if(xp[i][j] > 0 && h_min != xp[i][j]) { xp[i][j] = 0; s = j; } } k = k + 1; }QQ: for(k = 0; k < mp + np; k++) if(Row[k] == DelRow && Column[k] == DelCol) { Row[k] = o2; Column[k] = 0; }ChuyenDoiQ(xp, xp1, mp, np); for(i = 0; i < mp; i++) for(j = 0; j <= np; j++) { if(yp[i][j] != xp1[i][j]) { xp[i][j] = yp[i][j]; } } r = o2; s = 0; u = r; v = s; xp1[r][s] = 0; xp2[r][s] = 0; xp[r][s] = yp[r][s] - h_min; j = s; for(i = 0; i < mp; i++) if(xp1[i][j] > 0) xp[i][j] = xp[i][j] + h_min; k = 2; while(k < mp+np) { j = s; for(i = 0; i < mp; i++) if(xp1[i][j] > 0) { r = i; xp1[i][j] = 0; } i = r; for(j = 0; j <= np; j++) if(xp1[i][j] > 0) { s = j; if(xp1[i][j] == BK[k] && BK[k] > 0) xp[i][j] = BK[k] + h_min; xp1[i][j] = 0; } k = k + 2; } j = v; for(i = 0; i < mp; i++) if(xp2[i][j] > 0) { u = i; xp2[i][j] = 0; } k = 3; while(k < mp + np) { i = u; for(j = 0; j <= np; j++) if(xp2[i][j] > 0) { v = j; xp2[i][j] = 0; } j = v; for(i = 0; i < mp; i++) if(xp2[i][j] > 0) { u = i; if(xp2[i][j] == BK[k] && BK[k] > 0) xp[i][j] = BK[k] - h_min; xp2[i][j] = 0; } k = k + 2; } printf("\n\nPHUONG AN CUC BIEN MOI\n\n"); InPhuongAnQ(xp, mp, np); fprintf(fptr, "\n\nPHUONG AN CUC BIEN MOI\n\n"); for(i = 0; i < mp; i++) { for(j = 0; j <= np; j++) { if(xp[i][j] > 0) fprintf(fptr, "%8.1f", xp[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr, "\n"); } } else { if((e2 < 0) && (e2 <= e1)) { for(i = 0; i < mp; i++) if(xp[i][0] == (at[i] - ad[i])) xp[i][0] = 0; xp[o1][0] = 1000; TimChuTrinhQ(xp, mp, np); ChuyenDoiQ(xp1, xp, mp, np); ChuyenDoiQ(xp2, xp, mp, np); printf("\n\nCHU TRINH VUA TIM LA\n\n"); InPhuongAnQ(xp, mp, np); fprintf(fptr, "\n\nCHU TRINH VUA TIM LA\n\n"); for(i = 0; i < mp; i++) { for(j = 0; j <= np; j++) { if(xp[i][j] > 0) fprintf(fptr, "%8.1f", xp[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr, "\n"); } Tim_hQ1(xp, mp, np, o1, BK); h_min = BK[1]; for(i = 2; i < mp + np; i = i + 2) if(h_min > BK[i]&& BK[i] > 0) h_min = BK[i]; printf("\n\nLUONG HANG NHO NHAT h_min = %4.0f", h_min); fprintf(fptr, "\n\nLUONG HANG NHO NHAT h_min = %4.0f", h_min); ChuyenDoiQ(xp, xp1, mp, np); k = 0; r = o1; s = 0; xp[r][s] = 0; while(k < mp + np) { j = s; for(i = 0; i < mp; i++) { if(xp[i][j] > 0 && xp[i][j] == h_min) { DelRow = i; DelCol = j; goto QQ1; } if(xp[i][j] > 0 && xp[i][j] != h_min) { r = i; xp[i][j] = 0; } } i = r; for(j = 0; j <= np; j++) { if(xp[i][j] > 0 && xp[i][j] == h_min) { DelRow = i; DelCol = j; goto QQ1; } if(xp[i][j] > 0 && xp[i][j] != h_min) { s = j; xp[i][j] = 0; } } k = k + 1; }QQ1: for(k = 0; k < mp + np; k++) if(Row[k] == DelRow && Column[k] == DelCol) { Row[k] = o1; Column[k] = 0; } ChuyenDoiQ(xp, xp1, mp, np); for(i = 0; i < mp; i++) for(j = 0; j <= np; j++) { if(yp[i][j] != xp1[i][j]) { xp[i][j] = yp[i][j]; } } r = o1; s = 0; u = r; v = s; xp1[r][s] = 0; xp2[r][s] = 0; xp[r][s] = h_min; j = s; for(i = 0; i < mp; i++) if(xp1[i][j] > 0) xp[i][j] = xp[i][j] - h_min; k = 2; while(k < mp + np) { j = s; for(i = 0; i < mp; i++) if(xp1[i][j] > 0) { r = i; xp1[i][j] = 0; } i = r; for(j = 0; j <= np; j++) if(xp1[i][j] > 0) { s = j; if(xp1[i][j] == BK[k] && BK[k] > 0) xp[i][j] = BK[k] - h_min; xp1[i][j] = 0; } k = k + 2; } j = v; for(i = 0; i < mp; i++) if(xp2[i][j] > 0) { u = i; xp2[i][j] = 0; } k = 3; while(k < mp+np) { i = u; for(j = 0; j <= np; j++) if(xp2[i][j] > 0) { v = j; xp2[i][j] = 0; } j = v; for(i = 0; i < mp; i++) if(xp2[i][j] > 0) { u = i; if(xp2[i][j] == BK[k] && BK[k] > 0) xp[i][j] = BK[k] + h_min; xp2[i][j] = 0; } k = k + 2; } printf("\n\nPHUONG AN CUC BIEN MOI\n\n"); InPhuongAnQ(xp, mp, np); fprintf(fptr, "\n\nPHUONG AN CUC BIEN MOI\n\n"); for(i = 0; i < mp; i++) { for(j = 0; j <= np; j++) { if(xp[i][j] > 0) fprintf(fptr, "%8.1f", xp[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr, "\n"); } } if((e1 < 0) && (e1 <= e2)) { for(i = 0; i < mp; i++) if(xp[i][0] == (at[i] - ad[i])) xp[i][0] = 0; xp[rp][sp] = 1000; TimChuTrinhQ(xp, mp, np); ChuyenDoiQ(xp1, xp, mp, np); ChuyenDoiQ(xp2, xp, mp, np); printf("\n\nCHU TRINH VUA TIM LA\n\n"); InPhuongAnQ(xp, mp, np); fprintf(fptr, "\n\nCHU TRINH VUA TIM LA\n\n"); for(i = 0; i < mp; i++) { for(j = 0; j <= np; j++) { if(xp[i][j] > 0) fprintf(fptr, "%8.1f", xp[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr, "\n"); } i = 0; Test = 0; while(i < mp) { if(xp[i][0] > 0) { Test = Test + 1; } i = i + 1; } if(Test != 0) { Value = Tim_hP(xp, mp, np, rp, sp, bk1, bk2, at, ad); ChuyenDoiQ(xp, xp1, mp, np); fprintf(fptr, "\nIn bk1, bk2\n"); for(i = 0; i < mp + np; i++) { fprintf(fptr, "\nbk1[%d] = %5.0f", i, bk1[i]); } for(i = 0; i < mp + np; i++) { fprintf(fptr, "\nbk2[%d] = %5.0f", i, bk2[i]); } h1_min = 1000; h2_min = 1000; for(i = 1; i < mp+np; i++) if((h1_min > bk2[i])&& bk2[i] > 0) h1_min = bk2[i]; h2_min = Value; if(h1_min >= h2_min) h_min = h2_min; else h_min = h1_min; printf("\n\nLUONG HANG NHO NHAT h_min = %4.0f", h_min); fprintf(fptr, "\n\nLUONG HANG NHO NHAT h_min = %4.0f", h_min); ChuyenDoiQ(xp, xp1, mp, np);r = rp; s = sp; k = 0; i = rp; DelRow = 0; DelCol = 0;while(k < mp + np) { i = r; for(j = 0; j <= np; j++) { if((j == 0) && (xp[i][j] > 0) && (h_min == Value)) { DelRow = i; DelCol = j; goto QQ2; } if(xp[i][j] > 0 && h_min == xp[i][j]) { DelRow = i; DelCol = j; goto QQ2; } if(xp[i][j] > 0 && h_min != xp[i][j]) { xp[i][j] = 0; s = j; } } j = s; for(i = 0; i < mp; i++) { if(xp[i][j] > 0 && h_min == xp[i][j]) { DelRow = i; DelCol = j; goto QQ2; } if(xp[i][j] > 0 && h_min != xp[i][j]) { xp[i][j] = 0; r = i; } } k = k + 1; }QQ2: for(k = 0; k < mp + np; k++) if(Row[k] == DelRow && Column[k] == DelCol) { Row[k] = rp; Column[k] = sp; } ChuyenDoiQ(xp, xp1, mp, np); for(i = 0; i < mp; i++) for(j = 0; j <= np; j++) { if(yp[i][j] != xp1[i][j]) { xp[i][j] = yp[i][j]; } } r = rp; s = sp; xp1[r][s] = 0; xp2[r][s] = 0; xp[r][s] = h_min; k = 0; k1 = 1; k2 = 0; while(k < mp + np) { i = rp; for(j = 0; j <= np; j++) { if(xp1[i][j] > 0) { if(j == 0) { sp = j; if(xp1[i][j] == bk1[k1] && bk1[k1] > 0) xp[i][j] = bk1[k1] + h_min; xp1[i][j] = 0; k1 = k1 + 1; } else { sp = j; if(xp1[i][j] == bk2[k2] && bk2[k2] > 0) xp[i][j] = bk2[k2] - h_min; xp1[i][j] = 0; k2 = k2 + 1; } } } j = sp; for(i = 0; i < mp; i++) { if(xp1[i][j] > 0) { if(j == 0) { rp = i; if(xp1[i][j] == bk2[k2] && bk2[k2] > 0) xp[i][j] = bk2[k2] - h_min; xp1[i][j] = 0; k2 = k2 + 1; } else { rp = i; if(xp1[i][j] = bk1[k1] && bk1[k1] > 0) xp[i][j] = bk1[k1] + h_min; xp1[i][j] = 0; k1 = k1 + 1; } } } k = k + 1; } printf("\n\nPHUONG AN CUC BIEN MOI\n\n"); InPhuongAnQ(xp, mp, np); fprintf(fptr, "\n\nPHUONG AN CUC BIEN MOI\n\n"); for(i = 0; i < mp; i++) { for(j = 0; j <= np; j++) { if(xp[i][j] > 0) fprintf(fptr, "%8.1f", xp[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr, "\n"); } } if(Test == 0) { h_min = 1000; Tim_h(xp, mp, np, rp, sp, BK); for(k = 1; k < mp+np; k = k+2)if(h_min > BK[k] && BK[k]>0) h_min = BK[k]; printf("\n\nLUONG HANG NHO NHAT h_min = %4.0f", h_min); fprintf(fptr, "\n\nLUONG HANG NHO NHAT h_min = %4.0f", h_min); ChuyenDoiQ(xp, xp1, mp, np); r = rp; s = sp; k = 0; DelRow = 0; DelCol = 0;while(k < mp + np) { i = r; for(j = 0; j <= np; j++) { if(xp[i][j] > 0 && h_min == xp[i][j]) { DelRow = i; DelCol = j; goto QQ3; } if(xp[i][j] > 0 && h_min != xp[i][j]) { xp[i][j] = 0; s = j; } } j = s; for(i = 0; i < mp; i++) { if(xp[i][j] > 0 && h_min == xp[i][j]) { DelRow = i; DelCol = j; goto QQ3; } if(xp[i][j] > 0 && h_min != xp[i][j]) { xp[i][j] = 0; r = i; } } k = k + 1; }QQ3: for(k = 0; k < mp + np; k++) if(Row[k] == DelRow && Column[k] == DelCol) { Row[k] = rp; Column[k] = sp; } ChuyenDoiQ(xp, xp1, mp, np); for(i = 0; i < mp; i++) for(j = 0; j <= np; j++) { if(yp[i][j] != xp1[i][j]) xp[i][j] = yp[i][j]; } p1 = rp; q1 = sp;xp1[rp][sp] = 0; xp2[rp][sp] = 0; xp[rp][sp] = h_min; k = 2; while(k < mp+np) { i = rp; for(j = 0; j <= np; j++) if(xp1[i][j] > 0) { q = j; xp1[i][j] = 0; } j = q; for(i = 0; i < mp; i++) if(xp1[i][j] > 0) { rp = i; if(xp1[i][j] == BK[k] && BK[k] > 0) xp[i][j] = BK[k] + h_min; xp1[i][j] = 0; } k = k + 2; } k = 1; while(k < mp+np) { i = p1; for(j = 0; j <= np; j++) if(xp2[i][j] > 0) { q1 = j; if(xp2[i][j] == BK[k] && BK[k] > 0) xp[i][j] = BK[k] - h_min; xp2[i][j] = 0; } j = q1; for(i = 0; i < mp; i++) if(xp2[i][j] > 0) p1 = i; xp2[i][j] = 0; k = k + 2; } printf("\n\nPHUONG AN CUC BIEN MOI\n\n"); InPhuongAnQ(xp, mp, np); fprintf(fptr, "\n\nPHUONG AN CUC BIEN MOI\n\n"); for(i = 0; i < mp; i++) { for(j = 0; j <= np; j++) { if(xp[i][j] > 0) fprintf(fptr, "%8.1f", xp[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr, "\n"); } } } } } dem = dem + 1;}KQ: printf("\n\nPHUONG AN TOI CUA BAI TOAN (P)\n\n");InPhuongAnQ(xp, mp, np); fprintf(fptr, "\n\nPHUONG AN TOI CUA BAI TOAN (P)\n\n");for(i = 0; i < mp; i++) { for(j = 0; j <= np; j++) { if(xp[i][j] > 0) fprintf(fptr, "%8.1f", xp[i][j]); else fprintf(fptr, "%8.1f", 0); } fprintf(fptr, "\n"); } f_minp = 0;for(i = 0; i < mp; i++) for(j = 0; j <= np; j++) { f_minp = f_minp + xp[i][j]* cp1[i][j]; } printf("\n\nGIA TRI HAM MUC TIEU TOI UU CUA (P) F_MINP = %4.1f", f_minp); fprintf(fptr,"\n\nGIA TRI HAM MUC TIEU TOI UU CUA (P) F_MINP = %4.1f", f_minp); printf("\n\nSO BUOC LAP THUC HIEN %d", dem); fprintf(fptr, "\n\nSO BUOC LAP THUC HIEN %d", dem);fclose(fptr); printf("\n\nAn phim M hoac m de tro ve Menu chuong trinh"); char ch = getch(); if((ch == 'M')||(ch == 'm')) { mainMenu(); } else { exit(1); }}/*------------------------Ham Luu Tru Hang Cot--------------------------------*/void Store_Row_Column(float X1[MAX][MAX], int Row1[100], int Column1[100], int m1, int n1){int i, j, k; k = 0; for(i = 0; i < m1; i++) for(j = 0; j <= n1; j++) { if(X1[i][j] > 0) { Row1[k] = i; Column1[k] = j; k = k + 1; } }}/*---------------------------------Ham tim h_min------------------------------*/int Tim_hP(float x1[MAX][MAX], int m1, int n1, int r1, int s1, float bk1[2*MAX], float bk2[2*MAX], float at[2*MAX],float ad[2*MAX]){int i, j, k, k1, k2, w;for(k = 0; k < m1 + n1; k++) { bk1[k]= 0; bk2[k]= 0; }bk1[0] = x1[r1][s1]; x1[r1][s1] = 0; k1 = 1; w = 0; k2 = 0;float Value = 0;while(w < m1+n1){ i = r1;for(j = 0; j <= n1; j++) {if(x1[i][j] > 0){ if(j == 0) { s1 = j; bk1[k1] = x1[i][j]; Value = (at[i] - ad[i]) - x1[i][j]; x1[i][j] = 0; k1 = k1+1; } else { s1 = j; bk2[k2] = x1[i][j]; x1[i][j] = 0; k2 = k2 + 1; } } } j = s1; for(i = 0; i < m1; i++) { if(x1[i][j] > 0) { if(j == 0) { r1 = i; bk2[k2] = x1[i][j]; x1[i][j] = 0; k2 = k2 + 1; } else { r1 = i; bk1[k1] = x1[i][j]; x1[i][j] = 0; k1 = k1 + 1; } } } w = w + 1; } return Value;} |
Post a Comment