Hàm đa thức - Chương 8: Tối ưu hóa

u hao nguyên liệu để sản xuất các sản phẩm cho ở bảng sau:
Sản phẩm A
Sản phẩm B
Nguyên liệu 1
2
1
Nguyên liệu 2
1
2
Nguyên liệu 3
0
1
Số liệu này cho thấy để sản xuất một đơn vị sản phẩm A cần dùng 2 đơn vị nguyên liệu 1, một đơn vị nguyên liệu 2 và để sản xuất một đơn vị sản phẩm B cần dùng 1 đơn vị nguyên liệu 1, hai đơn vị nguyên liệu 2, 1 đơn vị nguyên liệu 3. Trong kho của nhà máy hiện có dự trữ 8 đơn vị nguyên liệu 1, 7 đơn vị nguyên liệu 2 và 3 đơn vị nguyên liệu 3. Tiền lãi một đơn vị sản phảm A là 4.000.000 đ, một đơn vị sản phẩm B là 5.000.000đ. Lập kế hoạch sản xuất sao cho công ty thu được tiền lãi lớn nhất.
Bài toán này là bài toán tìm cực trị có điều kiện. Gọi x1 là lượng sản phẩm A và x2 là lượng sản phẩm B ta đi đến mô hình toán học:
f(x) = 4x1 + 5x2 ® max
với các ràng buộc :	
2x1 + x2 £ 8	(ràng buộc về nguyên liệu 1)
	x1 + 2x2 £ 7	(ràng buộc về nguyên liệu 2)
	x2 £ 3	(ràng buộc về nguyên liệu 3)
	x1 ³ 0,x2 ³ 0
Một cách tổng quát ta có bài toán được phát biểu như sau: Cho hàm mục tiêu CTX ® max với điều kiện ràng buộc AX £ B và X ³ 0. Thuật toán để giải bài toán gồm hai giai đoạn 
tìm một phương án cực biên một đỉnh
kiểm tra điều kiện tối ưu đối với phương án tìm được ở giai đoạn 1. Nếu điều kiện tối ưu được thoả mãn thì phương án đó là tối ưu. Nếu không ta chuyển sang phương án mới.
Chương trình giải bài toán được viết như sau:
Chương trình 8-4
//simplex;
#include 
#include 
int m,n,n1,it,i,j,h1,h2,hi,m1,ps,pz,v,p;
float bv[20];
float a[20][20];
float h,mi,x,z;
void don_hinh()
 {
	int t;
	float hi;
	if (p!=2)
	 for (i=1;i<=m;i++)
	bv[i]=n+i;
	if (p==2)
	 {
	h1=n;
	h2=m;
	 }
	else
	 {
	h1=m;
	h2=n;
	 }
	for (i=1;i<=m1;i++)
	 for (j=1;j<=h1;j++)
	{
	 a[i][h2+j]=0.0;
	 if (i==j)
	a[i][h2+j]=1.0;
	}
	it=0;
	t=1;
	while (t)
	 {
	it=it+1;
	if (it<(m*n*5))
	 {
	mi=a[m1][1];
	ps=1;
	for (j=2;j<=n1-1;j++)
	 if (a[m1][j]<mi)
	{
	 mi=a[m1][j];
	 ps=j;
	}
	if (mi>-0.00001)
	 {
	z=a[m1][n1];
	t=0;
	 }
	mi=1e+20;
	pz=0;
	for (i=1;i<=m1-1;i++)
	 {
	if (a[i][ps]<=0.0)
	 continue;
	h=a[i][n1]/a[i][ps];
	if (h<mi)
	 {
	mi=h;
	pz=i;
	 }
	 }
	if (pz==0)
	 {
	if (p==2)
	 {
	printf("Khong ton tai nghiem\n");
	t=0;
	 }
	else
	 {
	printf("Nghiem khong bi gioi han\n");
	t=0;
	 }
	 }
	if (p==1)
	 bv[pz]=ps;
	hi=a[pz][ps];
	for (j=1;j<=n1;j++)
	 a[pz][j]=a[pz][j]/hi;
	if (pz!=1)
	 for (i=1;i<=pz-1;i++)
	{
	 hi=a[i][ps];
	 for (j=1;j<=n1;j++)
	a[i][j]=a[i][j]-hi*a[pz][j];
	}
	for (i=pz+1;i<=m1;i++)
	 {
	hi=a[i][ps];
	for (j=1;j<=n1;j++)
	 a[i][j]=a[i][j]-hi*a[pz][j];
	 }
	 }
	else
	 printf("Nghiem bat thuong");
	 }
 }
void main()
 {
	clrscr();
	printf("PHUONG PHAP DON HINH\n");
	printf("\n");
	flushall();
	printf("Cho bai toan tim max(1) hay min(2)(1/2)? : ");
	scanf("%d",&p);
	printf("Cho so bien n = ");
	scanf("%d",&n);
	printf("Cho so dieu kien bien m = ");
	scanf("%d",&m);
	n1=n+m+1;
	if (p==2)
	 m1=n+1;
	else
	 m1=m+1;
	printf("Cho ma tran cac dieu kien bien\n");
	for (i=1;i<=m;i++)
	 for (j=1;j<=n;j++)
	if (p==2)
	 {
	printf("a[%d][%d] = ",i,j);
	scanf("%f",&a[j][i]);
	 }
	else
	 {
	printf("a[%d][%d] = ",i,j);
	scanf("%f",&a[i][j]);
	 }
	printf("\n");
	printf("Cho ma tran ve phai\n");
	for (i=1;i<=m;i++)
	 if (p==2)
	{
	 printf("b[%d] = ",i);
	 scanf("%f",&a[m1][i]);
	 }
	else
	 {
	printf("b[%d] = ",i);
	scanf("%f",&a[i][n1]);
	 }
	printf("\n");
	printf("Cho ham muc tieu\n");
	for (j=1;j<=n;j++)
	 if (p==2)
	{
	 printf("z[%d] = ",j);
	 scanf("%f",&a[j][n1]);
	}
	 else
	{
	 printf("z[%d] = ",j);
	 scanf("%f",&a[m1][j]);
	}
	if (p==2)
	 hi=m;
	else
	 hi=n;
	for (j=1;j<=hi;j++)
	 a[m1][j]=-a[m1][j];
	a[m1][n1]=0.0;
	don_hinh();
	printf("\n");
	printf("NGHIEM TOI UU HOA\n");
	if (p==2)
	 printf("Bai toan cuc tieu tieu chuan\n");
	else
	 printf("Bai toan cuc dai tieu chuan\n");
	printf("sau %d buoc tinh",it);
	printf("\n");
	for (j=1;j<=n;j++)
	 {
	if (p==2)
	 x=a[m1][m+j];
	else
	 {
	v=0;
	for (i=1;i<=m;i++)
	 if (bv[i]==j)
	{
	 v=i;
	 i=m;
	}
	if (v==0)
	 x=0.0;
	else
	 x=a[v][n1];
	 }
	printf("x[%d] = %10.5f\n",j,x);
	 }
	printf("\n");
	printf("Gia tri toi uu cua ham muc tieu = %10.5f\n",z);
	getch();
 }
Dùng chương trình này giải bài toán có hàm mục tiêu :
	z = 80x1 + 56x2 + 48x3 ® min
với ràng buộc :	3x1 + 4x2 + 2x3 ³ 15
	2x1 + 3x2 + x3 ³ 9
	 x1 + 2x2 + 6x3 ³ 18
	 x2 + x3 ³ 5
	 x1,x2,x3 ³ 0
Ta cần nhập vào chương trình là tìm min,với số biến n =3,số điều kiện biên m = 4,các hệ số a[1,1] = 3 ; a[1,2] = 4 ; a[1,3] = 2 ; a[2,1] = 2; a[2,2] = 3 ; a[2,3] = 1 ; a[3,1] = 1 ; a[3,2] = 2 ; a[3,3] = 6 ; a[4,1] = 0 ; a[4,2] = 1 ; a[4,3] = 1 ; b[1] = 15 ; b[2] = 9 ; b[3] = 18; b[4] = 5 ; z[1] = 80 ; z[2] = 56 ; z[3] = 48 và nhận được kết quả :
	x[1] = 0 ; x[2] = 2.5 ; x[3] =2.5 và trị của hàm mục tiêu là 260
§5. PHƯƠNG PHÁP THẾ VỊ
	Trong vận tải ta thường gặp bài toán vận tải phát biểu như sau: có n thùng hàng của một hãng xây dựng cần chuyển tới n địa điểm khác nhau. Giá vận tới tới mỗi địa điểm đã cho. Tìm phương án vận chuyển để giá thành là cực tiểu.
	Một cách tổng quát bài toán được phát biểu:
Ví dụ: Cần vận chuyển 6 thùng hàng tới 6 địa điểm với giá thành cho ở bảng sau:
 Thùng 1 2 3 4 5 6 ® địa điểm
Để giải bài toán ta dùng thuật toán Hungary như sau: 
trừ mỗi dòng cho số min của dòng đó ta có:
trừ mỗi cột cho số min của cột đó
Mục tiêu của thuật toán Hungary là biến đổi ma trận giá thành sao cho có thể đọc giá trị tối ưu từ ma trận. Điều này được thực hiện khi mỗi hàng và cột chứa ít nhất một số 0. Nếu ta vẽ một đoạn thẳng qua mỗi hàng và cột chứa số 0 thì khi đó số đoạn thẳng tối thiểu qua tất cả các số 0 phải là 6. Trong ma trận trên ta chỉ mới dùng 5 đoạn thẳng nghĩa là chưa có giá trị tối ưu. Để biến đổi tiếp tục ta tìm trị min của các phần tử chưa nằm trên bất kì đoạn thẳng nào. Trị số đó là 7. Lấy các phần tử không nằm trên đoạn thẳng nào trừ đi 7 và công các phần tử nằm trên hai đoạn thẳng với 7 ta có ma trận:
Do số đoạn thẳng tối thiểu còn là 5 nên ta lặp lại bước trên và nhận được ma trận mới:
Số đoạn thẳng cần để qua hết các số 0 là 6 nghĩa là ta đã tìm được trị tối ưu.Ta đánh dấu 6 số 0 sao cho mỗi hàng và mỗi cột chỉ có 1 số được đánh dấu. Chỉ số các số 0 được đánh dấu cho ta trị tối ưu:
	a15 = 0 nghĩa là thùng 1 được vận chuyển tới địa điểm 5
	a24 = 0 nghĩa là thùng 2 được vận chuyển tới địa điểm 4
	a32 = 0 nghĩa là thùng 3 được vận chuyển tới địa điểm 2
	a46 = 0 nghĩa là thùng 4 được vận chuyển tới địa điểm 6
	a53 = 0 nghĩa là thùng 5 được vận chuyển tới địa điểm 3
	a61 = 0 nghĩa là thùng 6 được vận chuyển tới địa điểm 1
	Chương trình viết theo thuật toán trên như sau :
Chương trình 8-5
// van_tru;
#include 
#include 
void main()
 {
	int a[20][20],z[20][20],p[20][2];
	float x[20][20],w[20][20];
	float c[20],r[20];
	int t,c1,i,j,k,k2,k3,k5,l,l1,m,n,r1,s;
	float m1,q;
 clrscr();
	printf("Cho so an so n = ");
	scanf("%d",&n);
	printf("Cho cac he so cua ma tran x\n");
	for (i=1;i<=n;i++)
	 for (j=1;j<=n;j++)
	{
	 printf("x[%d][%d] = ",i,j);
	 scanf("%f",&x[i][j]);
	 w[i][j]=x[i][j];
	}
	for (i=1;i<=n;i++)
	 {
	c[i]=0.0;
	r[i]=0.0;
	p[i][1]=0.0;
	p[i][2]=0.0;
	a[i][1]=0.0;
	a[i][2]=0.0;
	 }
	for (i=1;i<=2*n;i++)
	 {
	z[i][1]=0.0;
	z[i][2]=0.0;
	 }
	for (i=1;i<=n;i++)
	 {
	m1=9999.0;
	for (j=1;j<=n;j++)
	 if (x[i][j]<m1)
	m1=x[i][j];
	for (j=1;j<=n;j++)
	 x[i][j]=x[i][j]-m1;
	 }
	for (j=1;j<=n;j++)
	 {
	m1=9999.0;
	for (i=1;i<=n;i++)
	 if (x[i][j]<m1)
	m1=x[i][j];
	for (i=1;i<=n;i++)
	 x[i][j]=x[i][j]-m1;
	 }
	l=1;
	for (i=1;i<=n;i++)
	 {
	j=1;
mot: if (j>n)
	 continue;
	 if (x[i][j]!=0)
	 {
	j=j+1;
	goto mot;
	 }
	else
	 if (i==1)
	{
	 a[l][1]=i;
	 a[l][2]=j;
	 c[j]=1.0;
	 l=l+1;
	}
	 else
	{
	 l1=l-1;
	 for (k=1;k<=l1;k++)
	{
	 if (a[k][2]!=j)
	continue;
	 else
	{
	 j=j+1;
	 goto mot;
	}
	}
	}
	 }
	l=l-1;
	if (l!=n)
	 {
	m=1;
hai: for (i=1;i<=n;i++)
	 {
	j=1;
ba: if (j>n)
	 continue;
	else
	 if ((x[i][j]!=0)||(c[j]!=0)||(r[i]!=0))
	{
	 j=j+1;
	 goto ba;
	}
	 else
	{
	 p[m][1]=i;
	 p[m][2]=j;
	 m=m+1;
	 for (k=1;k<=l;k++)
	if (a[k][1]!=i)
	 continue;
	else
	 {
	r[i]=1.0;
	c[a[k][2]]=0.0;
	goto sau;
	 }
	}
	 }
	k2=m-1;
	r1=p[k2][1];
	c1=p[k2][2];
	k3=l;
	k=1;
	s=1;
bon: if (k==1)
	 {
	z[k][1]=r1;
	z[k][2]=c1;
	k=k+1;
	goto bon;
	 }
	else
	 {
	if (s==1)
	 {
	for (j=1;j<=k3;j++)
	 if (a[j][2]==c1)
	{
	 r1=a[j][1];
	 s=2;
	 z[k][1]=r1;
	 z[k][2]=c1;
	 k=k+1;
	 goto bon;
	}
	k=k-1;
	 }
	else
	 {
	for (j=1;j<=k2;j++)
	 if (p[j][1]==r1)
	{
	 c1=p[j][2];
	 s=1;
	 z[k][1]=r1;
	 z[k][2]=c1;
	 k=k+1;
	 goto bon;
	}
	 else
	continue;
	k=k-1;
	 }
	 }
	k5=1;
nam: if (k5==k)
	 {
	l=l+1;
	a[l][1]=z[k][1];
	a[l][2]=z[k][2];
	if (l!=n)
	 {
	for (i=1;i<=n;i++)
	 {
	r[i]=0.0;
	c[i]=0.0;
	p[i][1]=0;
	p[i][2]=0;
	 }
	for (i=1;i<=l;i++)
	 c[a[i][2]]=1.0;
	m=1;
	goto hai;
sau: m1=9999;
	for (i=1;i<=n;i++)
	 if (r[i]==0.0)
	for (j=1;j<=n;j++)
	 if (c[j]==0.0)
	if (x[i][j]<m1)
	 m1=x[i][j];
	for (i=1;i<=n;i++)
	 for (j=1;j<=n;j++)
	{
	 if ((r[i]!=0.0)||(c[j]!=0.0))
	if ((r[i]!=1.0)||(c[j]!=1.0))
	 continue;
	else
	 x[i][j]=x[i][j]+m1;
	 else
	x[i][j]=x[i][j]-m1;
	}
	goto hai;
	 }
	 }
	else
	 {
	for (i=1;i<=l;i++)
	 if ((a[i][1]==z[k5+1][1]))
	if ((a[i][2]==z[k5+1][2]))
	 break;
	a[i][1]=z[k5][1];
	a[i][2]=z[k5][2];
	k5=k5+2;
	goto nam;
	 }
	 }
	q=0.0;
	for (i=1;i<=n;i++)
	 q+=w[a[i][1]][a[i][2]];
	printf("Gia thanh cuc tieu : %10.5f\n",q);
	printf("\n");
	printf("Cuc tieu hoa\n");
	for (i=1;i<=n;i++)
	 printf("%d%10c%d\n",a[i][1],' ',a[i][2]);
	getch();
 }
	Chạy chương trình ta nhận được giá thành cực tiểu là 181