Bài giảng Chương 2: Những khái niệm mở đầu

GẪU TỪ VỰNG 
 5.1. Phương pháp đơn hình đỗi ngẫu xây dựng một dãy hữu hạn các giả phương 
án Xo, X1, ... , Xk. Giả phương án cuối cùng Xk là phương án (vì vậy là phương án tối 
ưu) của bài toán (5) - (7) . Hàm mục tiêu xo = xo(Xr) không tăng khi r tăng. Mỗi giả 
phương án Xr ứng với bảng Tr và các tập Br , Nr . 
 1 -x1 -x2 
x0 0 -1 -1 
x1 0 -1 0 
x2 0 0 -1 
x3 38 2 11 
x4 7 1 1 
x5 5 4* -5 
 1 -x5 -x2 
x0 5/4 1/4 -9/4 
x1 5/4 1/4 -5/4 
x2 0 0 -1 
x3 71/2 -1/2 27/2 
x4 23/4 -1/4 9/4* 
x5 0 -1 0 
Bùi Thế Tâm II.7 Quy hoạch rời rạc 
Quá trình giải gồm bước lặp ban đầu (xây dựng giả phương án xuất phát Xo) và 
dãy bước lặp tổng quát. 
 5.2. Tìm cực đại từ vựng của phương án mở rộng 
~
X = ( n1o x,...,x,x ) = 1
1
, ,...,
n
j j n
j
c x x x
=
    
∑ 
với các điều kiện 
1
n
ij j i
j
a x b
=
=∑ (i = 1, ..., m) 
0 ( 1, 2, , )jx j n≥ = " 
Ký hiệu bài toán là ( , )L C hay l - bài toán. Phương pháp đơn hình đỗi ngẫu từ 
vựng gọi gọn là l - phương pháp. 
 5.3. Bước lặp r ≥ 0 tổng quát 
Có l - giả phương án Xr với x0j ≥ 0, j∈ Nr, và tương ứng Tr , Br , Nr, các cột là 
0( )rj rR j N∈ . 
Kiểm tra xem Tr có chấp nhận được hay không (tức là xio≥ 0 với mọi i = 1,..,n). 
Nếu đúng thì Xr là phương án l - tối ưu. Nếu không thì tìm biến xk loại khỏi cơ sở theo 
quy tắc: 
 k = min { i | i = 1, ... , n ; xio <0} 
Tìm xl đưa vào cơ sở theo quy tắc 
min ; 0jl r kj
kl kj
RR lex j N x
x x
  = ∈ <   
Nếu trong các số xkj (j∈ Nr) không có số âm thì bài toán không giải được. Nếu có 
thì biến đổi bảng đơn hình theo các công thức ở tiết 3 ta được Xr+1, Tr+1 , Br+1 , Nr+1 
 5.4. Tính l giả phương án Xo 
Giả sử ta xây dựng bảng đơn hình T ứng với bài toán (5) - (7) không phải 
là l -chuẩn, ứng với nó có các tập B và N. Giả sử hàm ∑
∈Nj
jx bị chặn trên tập 
(6)- (7). Khi đó ta tìm được số M sao cho: ∑
∈Nj
jx ≤ M (có thể dùng đơn hình 
thường để xác định M). 
Đưa vào biến mới 



≥
−+=
+
∈
+ ∑
0x
)x.(1Mx
1n
Nj
j1n
Viết ràng buộc mới này vào cuối bảng T, chọn xk loại khỏi cơ sớ theo 
quy tắc: k = n+1. Chọn biến xl đưa vào cơ số theo quy tắc 
Bùi Thế Tâm II.8 Quy hoạch rời rạc 
 Rl = lex min {Rj | j ∈ N } 
Thực hiện một bước biến đổi bảng đơn hình theo các công thức của tiết 3 
ta nhận được bảng To là l - chuẩn (Rj ≥ 0 với j ∈ No ) và ứng với nó ta có các 
tập Bo và No: 
 Bo = (B ∪ { l}), No = (N ∪ {n + 1})\ { l}. 
5.5. Ví dụ bằng số 
Giải bài toán sau bằng phương pháp đơn hình đối ngẫu. 
Max 3210 23 xxxx −−= 
000
2
43
1042
321
321
321
321
≥≥≥
=+−
≥++
≤−+
xxx
xxx
xxx
xxx
 , ,
Sau khi thay ràng buộc đẳng thức bằng hai ràng buộc bất đẳng thức bài toán trên 
trở thành: 
Max 3210 23 xxxx −−= 
0,0,0
2
2
43
1042
321
321
321
321
321
≥≥≥
−≤−+−
≤+−
−≤−−−
≤−+
xxx
xxx
xxx
xxx
xxx
Tiếp theo thêm các biến bù ta được bài toán: 
 Max 3210 23 xxxx −−= 
0,,,,,,
2
2
34
4210
7654321
3217
3216
3215
3214
≥
+−+−=
−+−=
+++−=
+−−=
xxxxxxx
xxxx
xxxx
xxxx
xxxx
 Ta có các bảng đơn hình sau khi thêm ràng buộc phụ : 
Bùi Thế Tâm II.9 Quy hoạch rời rạc 
 1 -x1 -x2 -x3 
x0 0.00000 -3.00000 1.00000 -2.00000 
x1 0.00000 -1.00000 0.00000 0.00000 
x2 0.00000 0.00000 -1.00000 0.00000 
x3 0.00000 0.00000 0.00000 -1.00000 
x4 10.00000 2.00000 4.00000 -1.00000 
x5 -4.00000 -3.00000 -1.00000 -1.00000 
x6 2.00000 1.00000 -1.00000 1.00000 
x7 -2.00000 -1.00000 1.00000 -1.00000 
x8 100.00000 1.00000* 1.00000 1.00000 
 Bảng 1 
 1 -x8 -x2 -x3 
x0 300.00000 3.00000 4.00000 1.00000 
x1 100.00000 1.00000 1.00000 1.00000 
x2 0.00000 - 0.00001 -1.00000 0.00000 
x3 0.00000 - 0.00001 0.00000 -1.00000 
x4 -190.00000 -2.00000 2.00000 -3.00000* 
x5 296.00000 3.00000 2.00000 2.00000 
x6 -98.00000 -1.00000 -2.00000 0.00000 
x7 98.00000 1.00000 2.00000 0.00000 
 Bảng 2 
 1 -x8 -x2 -x4 
x0 236.66667 2.33333 4.66667 0.33333 
x1 36.66667 0.33333 1.66667 0.33333 
x2 0.00000 - 0.00001 -1.00000 0.00000 
x3 63.33333 0.66667 - 0.66667 - 0.33333 
x4 0.00000 0.00000 0.00000 -1.00000 
x5 169.33333 1.66667 3.33333 0.66667 
x6 -98.00000 -1.00000* -2.00000 0.00000 
x7 98.00000 1.00000 2.00000 0.00000 
 Bảng 3 
Bùi Thế Tâm II.10 Quy hoạch rời rạc 
 1 -x6 -x2 -x4 
x0 8.00000 2.33333 0.00000 0.33333 
x1 4.00000 0.33333 1.00000 0.33333 
x2 0.00000 - 0.00001 -1.00000 0.00000 
x3 -2.00000 0.66667 -2.00000* - 0.33333 
x4 0.00000 0.00000 0.00000 -1.00000 
x5 6.00000 1.66667 0.00000 0.66667 
x6 0.00000 -1.00000 0.00000 0.00000 
x7 0.00000 1.00000 0.00000 0.00000 
 Bảng 4 
 1 -x6 -x3 -x4 
x0 8.00000 2.33333 0.00000 0.33333 
x1 3.00000 0.66667 0.50000 0.16667 
x2 1.00000 - 0.33333 - 0.50000 0.16667 
x3 0.00000 0.00000 -1.00000 0.00000 
x4 0.00000 0.00000 0.00000 -1.00000 
x5 6.00000 1.66667 0.00000 0.66667 
x6 0.00000 -1.00000 0.00000 0.00000 
x7 0.00000 1.00000 0.00000 0.00000 
 Bảng 5 
Vậy phương án tối ưu là (3, 1, 0, 0, 6, 0, 0) với trị hàm mục tiêu bằng x[0]=-8. 
5.6. Chương trình máy tính 
• Chương trình nhằm giải bài toán quy hoạch tuyến tính có dạng: 
max
1
0 →=∑
=
j
m
j
j xcx 
ij
m
j
ij bxa ≤∑
=1
, pi ,...,1= 
0≥jx , mj ,...,2,1= 
Bùi Thế Tâm II.11 Quy hoạch rời rạc 
các b[i] có thể dương và âm, phương án xuất phát không đối ngẫu chấp nhận được. Nếu 
bài toán giải có ràng buộc đẳng thức dạng: ii
m
j
ij bxa =∑
=1
thì ta thay thế bằng hai bất 
đẳng thức: ii
m
j
ij bxa ≤∑
=1
và ii
m
j
ij bxa ≥∑
=1
. 
• Sau khi thêm biến bù bài toán trên có thể viết ở dạng: 
max))((
1
0 →−−=∑
=
m
j
jj xcx 
mjxx jj ,...,2,1))(1( =−−= 
.,...,2,1))((
1
pixabx j
m
j
ijiim =−−+= ∑
=
+ 
.,...,2,10 pmjx j +=≥ 
•Trong chương trình sử dụng các biến và mảng sau: 
 - m: số biến chính, n: số biến chính và biến bù của bài toán (n=m+p), gz là một 
số dương đủ lớn và thường lấy bằng },,{max jiij cba , ss = 1 nếu bảng s là l- chuẩn 
nhưng không chấp nhận được và = 0 nếu bảng không là l- chuẩn. 
- Mảng s gồm n + 2 dòng và m+1 cột lúc đầu ghi dữ liệu của bài toán sau đó lưu 
bảng đơn hình ở mỗi bước. Dòng n+1 để chứa ràng buộc phụ (8). 
- s[0][0] hàm mục tiêu, cột 0 là cột phương án, dòng 0 là các ước lượng 
- cs : các biến ở bên trái bảng đơn hình, nc : các biến phi cơ sở 
•Cách nhập dữ liệu 
Các dữ liệu ban đầu của bài toán được ghi trong một tệp văn bản, gồm: 
- n, m,gz, ss. 
- Mảng s dữ liệu ban đầu bố trí dạng ở dưới và được ghi vào tệp dữ liệu theo từng 
dòng : 
Bùi Thế Tâm II.12 Quy hoạch rời rạc 
- Mảng cs: nhập các số 0,1,2,,n. 
- Mảng nc: nhập các số 1,2,,m. 
Với dữ liệu bài toán trong mục 5.5 thì tệp dữ liệu DN.SLI có dạng : 
7 3 100 0 
0 -3 1 -2 
0 -1 0 0 
0 0 -1 0 
0 0 0 -1 
10 2 4 -1 
-4 -3 -1 -1 
 2 1 -1 1 
-2 -1 1 -1 
0 1 2 3 4 5 6 7 
1 2 3 
•Văn bản chương trình. 
#include 
#include 
#include 
#include 
#define M 30 
#define N 30 
double s[N+2][M+1],r,gz; 
int blap,kgd, kgd2,ss,sb,cmin; 
int m,n,i,j,k,l,tg,cs[N+2],nc[M+1]; 
unsigned long far *t; long int t1,t2; char *s1,*s2; 
FILE *f1,*f2; 
 -x1 -x2 . . . . . . . . –xm 
0 -c1 -c2 . . . . . . . –cm x0 
x1 
x2 
# 
xm 
0 
0 
# 
0 
-1 0 . . . . . . . . . . 0 
0 -1 . . . . . . . . . 0 
# # % # 
0 0 . . . . . . . . . . -1 
xm+1 
# 
xn 
b1 
# 
bp 
-a11 . . . . . . . . . - a1m 
# # # 
-ap1 . . . . . . . . . .-ap,m 
Bùi Thế Tâm II.13 Quy hoạch rời rạc 
int cotquay(); 
void biendoi(); 
void inbang(int cuoi); 
int dhdoingau(); 
void main() 
{ clrscr(); 
t= (unsigned long far *)MK_FP(0,0X46C); t1=*t; 
printf("\nCo in trung gian hay khong 1/0 ? "); 
scanf("%d%*c",&tg); 
 // Nhap du lieu ban dau 
printf("\nVao ten tep so lieu : "); gets(s1); 
f1= fopen(s1,"r"); 
fscanf(f1,"%d%d%lf%d",&n,&m,&gz,&ss); 
for (i=0;i<=n;i++) for (j=0; j<=m;j++) 
 { fscanf(f1,"%lf",&r); s[i][j]=r; } 
for (i=0; i<=n;i++) fscanf(f1,"%d",&cs[i]) ; 
for (j=1; j<=m; j++) fscanf(f1,"%d",&nc[j]); 
fclose(f1); sb=1; 
 // In so lieu de kiem tra 
printf("\n n,m,gz,ss = %d %d %13.5lf %d\n",n,m,gz,ss); 
if (tg==1){ printf("\nVao ten tep chua ket qua : "); gets(s2); 
 f2=fopen(s2,"w"); 
 fprintf(f2,"\n n,m,gz,ss = %d %d %13.5lf %d\n",n,m,gz,ss); 
 } 
printf("\nBang 1, so lieu ban dau"); 
if (tg==1) fprintf(f2,"\nBang 1, so lieu ban dau"); 
inbang(0); 
if (ss==1){ 
 printf("\nBang 1, so lieu ban dau, l- chuan, khong chap nhan duoc"); 
 if (tg==1) 
 fprintf(f2,"\nBang 1, so lieu ban dau, l- chuan, khong c.nhan duoc"); 
 goto L1;} 
 // Them rang buoc phu 
cs[n+1]=n+1; s[n+1][0]=gz; 
for (j=1;j<=m; j++) s[n+1][j]=1; 
printf("\nBang 1, so lieu ban dau them rang buoc phu"); 
if (tg==1) fprintf(f2,"\nBang 1, so lieu ban dau them rang buoc phu"); 
inbang(1); 
l=n+1; 
 // Chon cot quay Rl = lexmin { Rj | j (- N } 
cmin=1; 
for (j=2;j<=m;j++) 
 { for (i=0; i<=n;i++) 
 { if (s[i][cmin] > s[i][j]) {cmin=j; break;} 
 if (s[i][cmin] < s[i][j]) break; } 
 } 
printf("\nDong quay = %d, Cot quay = %d Ptq = %13.5lf",l,cmin,s[l][cmin]); 
if (tg==1) { 
fprintf(f2,"\nDong quay = %d, Cot quay = %d Ptq = %13.5lf", 
 l,cmin,s[l][cmin]); } 
biendoi();sb++; 
printf("\nBang %d, l- chuan dau tien",sb); 
Bùi Thế Tâm II.14 Quy hoạch rời rạc 
if (tg==1) fprintf(f2,"\nBang %d, l- chuan dau tien",sb); 
inbang(0); 
L1: kgd2= dhdoingau(); 
if (kgd2==1) { 
 printf("\nBai toan phu khong giai duoc"); 
 if (tg==1) fprintf(f2,"\nBai toan phu khong giai duoc, STOP"); 
 getch(); return; } 
getch(); 
} 
 // Phan cac ham 
int cotquay() 
{ k=0; 
for (j=1; j<=m; j++) if (s[l][j]<0) { k=j; break;} 
if (k==0) return 1; 
cmin=k; 
for (j=k+1;j<=m;j++) if (s[l][j]<0) 
 { for (i=0; i<=n;i++) 
 { double t1,t2; 
 t1= s[i][cmin]/fabs(s[l][cmin]); t2=s[i][j]/fabs(s[l][j]); 
 if (t1 > t2) {cmin=j; break;} 
 if (t1 < t2) break; 
 } 
 } 
return 0; 
} 
void biendoi() 
{ for (j=0;j<=m;j++) if (j!= cmin) 
 { for (i=0;i<=n;i++) if (i!=l) 
 s[i][j]=s[i][j]-(s[l][j]/s[l][cmin])*s[i][cmin]; 
 s[l][j]=0; } 
for (i=0;i<=n;