خوارزم شارن وكوبر

خوارزم شارن وكوبر 

---

إشكالية النقل

---

المبدأ 

باستعمال الخوارزم أولي التبسيط، ننشأ متتالية لحلول القاعدة المقبولة التي من أجلها تكون تكاليف النقل تناقصية) على شكل مضبوط (بدون حساب جدول التبسيط). 

---

الخوارزم 

نبدأ بأي حل من أية قاعدة مقبولة، ولإنشاء الحل البدئي نستعمل طريقة  بلاص-همر Balas-Hammer .

المرحلة العادية 

تحقيق في المثالية: 

1.  حسابu_i   وv_j   بحيث :   مهما يكنij   من القاعدة.

2.  نستنتج أن معاملات الدالة الاقتصادية المعبر عنها بالنسبة للمتغيرات الخارجة عن القاعدة:   مهما يكنij  خارج عن القاعدة. 

3.  نحصل على الحل المثالي عندما تصبح كل    موجبة. 

تغيير القاعدة : 

1. نختار متغيرا داخل القاعدة  من بين المتغيرات  ، (أحد المتغيراتx_ij   بحيث0  ) 

 2.  إضافة تنشئ دورا في شبكة النقل للقوس (i₁ j₁ )، وليكن (i₁, j₁, i₂, j₂, i₃,...i_p, j_p, i₁) . 

لتكن   الكمية المنقولة على (i₁ j₁ ). 
على أقواس الدور نوازن الكمية المنقولة:
يجب إرسال  على الأقل على (i₂ j₁ )،  على الأكثر على (i₂ j₂ )،   على الأقل على (i₃ j₂ )،
وهكذا... على الأكثر على (i_p j_p )،   على الأقل على  (i₁ j_p  ).
نعطي لـ   القيمة التي تعدم المتغير أو المتغيرات الموصلة إلى القيمة الدنوية.
 المتغير    يداخل إلى القاعدة بتغيير أحد المتغيرات التي تنعدم . 

---

مثال 

حل إشكالية النقل :   

تكاليف الوحدات  10  13   4  5   7  11   2  20  7   5   5   3  10  5  15   6   9   3  5   10  8  5  7  9  الجاهزية    2   8     10  3     6       الطلب

الحل اليدوي

 الحل البدئي محصل عليه بطريقة بلاص-همر Balas-Hammer 

6  1  1  -  -  -  -  -  5  -  -  2  -  3  2  -  -  9  -  -

(الكلفة 117  ) 

حساب   u_i و    v_j 

cij من القاعدة   7   5   4   .   .   .   .   .   2   .   .   5   .   3   5   .   .    3   .   .  3  2  3  2  ui  vj   4   2   1   0   2

شبكة الكلفة الهامشية : 

خارج القاعدة   .  .   .  10  5  -1  3  17   .  7   8  .  6  .  .   4  1   . 7 2  3  2  3  2  ui  vj  4 2 1 0 2

x₂₁  داخلة إلى القاعدة  .

تغيير الحل  :

6- 1+   1     -    -    -    -  5-   -    -  2-   -  3+   2     -    -     9    -    -

=2حل جديد :

4   3   1   -   -   2   -   -   3   -   -   -   -   5   2   -   -    9   -   -

(الكلفة 115   ) 

حساب   u_i و  :v_j  

cij من القاعدة  7  5  4  . . 5 .   .   2  .  .   .  .   3   5   .   .    3   .   .  4  2  3  3  ui  vj   3  1  0   0   2

شبكة الكلفة الهامشية   : 

الحل المثالي 

خارج القاعدة   .   .    .  9  4   .  4  18  .  7  9  1  7 .   .   4  1  . 6  1  4  2  3  3  ui  vj   3  1  0   0  2

---

البرمجة 

 #include <math.h>#include <conio.h>#define NMAX 6#define MMAX 6#define PMAX 12

void pl_balas_hammer(int c[NMAX][MMAX],int s[NMAX][MMAX],int n, int m);
void pl_charnes_cooper(int c[NMAX][MMAX],int s[NMAX][MMAX],int n, int m); main(){ int i,j,n,m,ct; int c[NMAX][MMAX],s[NMAX][MMAX]; clrscr(); n=4;m=5; printf("Algorithme de Charnes-Cooper\n"); /* disponibilités */ c[1][0]=8;c[2][0]=5;c[3][0]=7;c[4][0]=9; printf("Disponibilités: "); for(i=1;i<=n;i++) printf(" %2d",c[i][0]);printf("\n"); /* demandes */ c[0][1]=6;c[0][2]=3;c[0][3]=10;c[0][4]=8;c[0][5]=2; printf("Demandes: "); for(j=1;j<=m;j++) printf(" %2d",c[0][j]);printf("\n"); /* couts unitaires */ c[1][1]=7;c[1][2]=5;c[1][3]=4;c[1][4]=13;c[1][5]=10; c[2][1]=5;c[2][2]=7;c[2][3]=20;c[2][4]=2;c[2][5]=11; c[3][1]=15;c[3][2]=5;c[3][3]=10;c[3][4]=3;c[3][5]=5; c[4][1]=10;c[4][2]=5;c[4][3]=3;c[4][4]=9;c[4][5]=6; printf("Coûts unitaires:\n"); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) printf(" %2d",c[i][j]); printf("\n"); } pl_charnes_cooper(c,s,n,m); printf("Solution optimale:\n"); ct=0; for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(s[i][j]!=-1) { printf("x(%d,%d) = %d\n",i,j,s[i][j]); ct+=s[i][j]*c[i][j]; } else printf("x(%d,%d) = %d\n",i,j,0); printf("Coût de transport: %5d\n",ct);} 

---

نتيجة البرنامج

نحذف التعليقات من الدالة pl_charnes_cooper في كل كرة يظهر البرنامج شبكة الحلول وشبكة الكلفة الهامشية، والمتغيرات الداخلة والخارجة.  يظهر بعد ذلك الحلول المثالية وقيمة كلفة النقل المرافقة.

	الجاهزية:  9 7 5 8 الطلب:  2 8 10 3 6
كلفة الوحدة   :	7 5 4 13 10 5 7 20 2 11 15 5 10 3 5 10 5 3 9 6
الحل الأولي (هلاس-همر)	6 1 1 * * * * * 5 * * 2 * 3 2 * * 9 * *
	الكلفة:   117
كلفة الهامشية	* * * 10 5 -1 3 17 * 7  8 * 6 * *  4 1 * 7 2
المتغير الداخل:(  2  ,1) المتغير الخارج: (3, 2) الحل	4 3 1 * * 2 * * 3 * * * * 5 2 * * 9 * *
	الكلفة:    115
كلفة الهامشية	* *  * 9 4 * 4 18 * 7 9 1  7 * * 4 1  * 6 1
الحل المثالي	x(1,1) = 4  x(1,2) = 3  x(1,3) = 1  x(1,4) = 0  x(1,5) = 0  x(2,1) = 2  x(2,2) = 0  x(2,3) = 0  x(2,4) = 3  x(2,5) = 0  x(3,1) = 0  x(3,2) = 0  x(3,3) = 0  x(3,4) = 5  x(3,5) = 2  x(4,1) = 0  x(4,2) = 0  x(4,3) = 9  x(4,4) = 0  x(4,5) = 0
	كلفة النقل:   115

---

الدالة الرئيسية pl_charnes_cooper

معايير هذه الدالة كالتالي:

c : جدول يحتوي على الأسعار الأولية، والجاهزية والطلبs : جدول يحتوي على الحلn : عدد الطلبات الأصليةm: عدد المبعوث إليهم

تقوم هذه الدالة بحساب أفضل حل وتضعه في الجدول sبخصوص الطلبات فيجب أن توضع في الجدول c على الشكل التالي:العمود 0 من المصفوفة c (العناصر من 1 إلى n) : التجهيزيةالصف 0 من المصفوفة c (العناصر من 1 إلى m): الطلباتالصفوف من 1 إلى n والأعمدة من 1 إلى m من المصفوفة c : السعر 

تقوم هذه الدالة باستدعاء الدالة التالية

 void pl_balas_hammer(int c[NMAX][MMAX],int s[NMAX][MMAX],int n, int m)

 معايير هذه الدالة كالآتي:

 c : جدول يحتوي على الأسعار الأولية، والجاهزية والطلب

 s : جدول يحتوي على الحل

 n : عدد الطلبات الأصلية

 m : عدد المبعوث إليهم

 ترجع هذه الدالة الحال في الجدول s الذي حدد حسب طريقة بلاص وهامر .

 الثابتة الصحيحة NMAX تساوي العدد القصوي لأماكن الشحن (أي أماكن الإنطلاق) (+2).

 الثابتة الصحيحة MMAX تساوي العدد القصوي للزبائن المرسل إليهم (+2).

 الثابتة الصحيحة PMAX تساوي NMAX+MMAX.

 ملاحظة :إذا كنا نريد أن تظهر الدالة pl_charnes_cooper الحل خلال كل خطوة وقيمة السعر أيضا فيجب أن تحذف رمزي التعليقات  /*  و*/.

void pl_balas_hammer(int c[NMAX][MMAX],int s[NMAX][MMAX],int n, int m)
{
 int i,j,k,k1,vb,t,mrl,mrc,im,jm,crl,crc;
 int tl[NMAX][MMAX],tc[NMAX][MMAX],rl[NMAX],rc[MMAX];
 for(i=1;i<=n;i++)
 {
 s[i][0]=c[i][0];
 tc[i][0]=0;
 for(j=1;j<=m;j++)
 s[i][j]=-1;
 }
 for(j=1;j<=m;j++)
 {
 s[0][j]=c[0][j];
 tl[0][j]=0;
 }
 s[0][0]=0;
 crl=1;crc=1;
 for(i=1;i<=n;i++)
 {
 for(j=1;j<=m;j++)
 tl[i][j]=0;
 tl[i][0]=1;
 for(j=2;j<=m;j++)
 {
 t=c[i][j];
 k=0;
 while((tl[i][k]>0)&&(t>c[i][tl[i][k]]))
 k=tl[i][k];
 if(tl[i][k]>0)tl[i][j]=tl[i][k];
 tl[i][k]=j;
 }
 }
 for(j=1;j<=m;j++)
 {
 for(i=1;i<=n;i++)
 tc[i][j]=0;
 tc[0][j]=1;
 for(i=2;i<=n;i++)
 {
 t=c[i][j];k=0;
 while((tc[k][j]>0)&&(t>c[tc[k][j]][j]))
 k=tc[k][j];
 if(tc[k][j]>0)tc[i][j]=tc[k][j];
 tc[k][j]=i;
 }
 }
 for(vb=1;vb<n+m;vb++)
 {
 if(crl==1)
 {
 for(i=1;i<=n;i++)
 if(tc[i][0]!=-1)
 {
 k=tl[i][0];
 while(tl[0][k]==-1)k=tl[i][k];
 k1=tl[i][k];
 while(tl[0][k1]==-1)k1=tl[i][k1];
 rl[i]=abs(c[i][k]-c[i][k1]);
 }
 }
 mrl=-1;
 for(i=1;i<=n;i++)
 if((rl[i]>mrl)&&(tc[i][0]!=-1))
 {
 mrl=rl[i];
 im=i;
 }
 if(crc==1)
 {
 for(j=1;j<=m;j++)
 if(tl[0][j]!=-1)
 {
 k=tc[0][j];
 while(tc[k][0]==-1)k=tc[k][j];
 k1=tc[k][j];
 while(tc[k1][0]==-1)k1=tc[k1][j];
 rc[j]=abs(c[k][j]-c[k1][j]);
 }
 }
 mrc=-1;
 for(j=1;j<=m;j++)
 if((rc[j]>mrc)&&(tl[0][j]!=-1))
 {
 mrc=rc[j];
 jm=j;
 }
 if(mrc>mrl)
 {
 k=tc[0][jm];
 while(tc[k][0]==-1)k=tc[k][jm];
 if(s[k][0]>s[0][jm])
 {
 s[k][jm]=s[0][jm];
 s[k][0]-=s[0][jm];
 s[0][jm]=0;
 tl[0][jm]=-1;
 crl=1;crc=0;
 }
 else
 {
 s[k][jm]=s[k][0];
 s[0][jm]-=s[k][0];
 s[k][0]=0;
 tc[k][0]=-1;
 crl=0;crc=1;
 }
 }
 else
 {
 k=tl[im][0];
 while(tl[0][k]==-1)k=tl[im][k];
 if(s[0][k]>s[im][0])
 {
 s[im][k]=s[im][0];
 s[0][k]-=s[im][0];
 s[im][0]=0;
 tc[im][0]=-1;
 crl=0;crc=1;
 }
 else
 {
 s[im][k]=s[0][k];
 s[im][0]-=s[0][k];
 s[0][k]=0;
 tl[0][k]=-1;
 crl=1;crc=0;
 }
 }
 }
}

void pl_charnes_cooper(int c[NMAX][MMAX],int s[NMAX][MMAX],int n, int m)
{
 int i,j,k,l,l1,dis,dem,ct,min,min1;
 int d[NMAX][MMAX],p[2][PMAX];
 dis=0;
 for(i=1;i<=n;i++)
 dis+=c[i][0];
 dem=0;
 for(j=1;j<=m;j++)
 dem+=c[0][j];
 if(dis>dem)
 {
 m+=1;
 for(i=1;i<=n;i++)
 c[i][m]=0;
 c[0][m]=dis-dem;
 }
 if(dis<dem)
 {
 n+=1;
 for(j=1;j<=m;j++)
 c[n][j]=0;
 c[n][0]=dem-dis;
 }
 pl_balas_hammer(c,s,n,m);
 /* ct=0;
 printf("Solution initiale (Balas-Hammer)\n");
 for(i=1;i<=n;i++)
 {
 for(j=1;j<=m;j++)
 if(s[i][j]!=-1)
 {
 printf(" %2d",s[i][j]);
 ct+=s[i][j]*c[i][j];
 }
 else printf(" *");
 printf("\n");
 }
 printf("coût: %5d\n",ct); */
 do
 {
 for(i=1;i<=n;i++)
 for(j=1;j<=m;j++)
 if(s[i][j]!=-1)d[i][j]=c[i][j];
 else d[i][j]=-1;
 d[0][1]=0;
 k=1;
 p[0][1]=0;
 p[1][1]=1;
 while(k>0)
 {
 if(p[0][k]==0)
 {
 j=p[1][k];
 i=1;
 while(d[i][j]==-1&&i<n)i++;
 if(d[i][j]!=-1)
 {
 d[i][0]=d[i][j]-d[0][j];
 d[i][j]=-1;
 k++;
 p[0][k]=1;
 p[1][k]=i;
 }
 else k--;
 }
 else
 {
 i=p[1][k];
 j=1;
 while(d[i][j]==-1&&j<m)j++;
 if(d[i][j]!=-1)
 {
 d[0][j]=d[i][j]-d[i][0];
 d[i][j]=-1;
 k++;
 p[0][k]=0;
 p[1][k]=j;
 }
 else k--;
 }
 }
 min=1;
 for(i=1;i<=n;i++)
 for(j=1;j<=m;j++)
 if(s[i][j]==-1)
 {
 d[i][j]=c[i][j]-d[i][0]-d[0][j];
 if(d[i][j]<min)
 {
 min=d[i][j];
 k=i;l=j;
 }
 }
 /* printf("Coûts marginaux\n");
 for(i=1;i<=n;i++)
 {
 for(j=1;j<=m;j++)
 if(s[i][j]==-1)printf(" %2d",d[i][j]);
 else printf(" *");
 printf("\n");
 } */
 if(min<0)
 {
 for(i=1;i<=n;i++)
 for(j=1;j<=m;j++)
 if(s[i][j]==-1)d[i][j]=0;
 else d[i][j]=1;
 d[k][l]=2;
 /* printf("Variable entrante: ( %2d, %2d)",k,l); */
 p[0][1]=k;
 p[1][1]=l;
 k=1;l=0;
 do
 {
 if(l==0)
 {
 j=p[1][k];
 i=1;
 while(d[i][j]!=1&&i<n)i++;
 if(d[i][j]==1)
 {
 d[i][j]=0;
 k++;
 p[0][k]=i;
 p[1][k]=j;
 }
 else k--;
 l=1;
 }
 else
 {
 i=p[0][k];
 j=1;
 while(d[i][j]==0&&j<m)j++;
 if(d[i][j]!=0)
 {
 d[i][j]=0;
 k++;
 p[0][k]=i;
 p[1][k]=j;
 }
 else k--;
 l=0;
 }
 }
 while(i!=p[0][1]||j!=p[1][1]);
 min1=32767;
 for(l=2;l<=k;l+=2)
 {
 i=p[0][l];
 j=p[1][l];
 if(s[i][j]<min1)min1=s[i][j];
 }
 s[p[0][1]][p[1][1]]=min1;
 for(l=3;l<k;l+=2)
 s[p[0][l]][p[1][l]]+=min1;
 ct=-1;
 for(l=2;l<k;l+=2)
 {
 i=p[0][l];
 j=p[1][l];
 s[i][j]-=min1;
 if(s[i][j]==0&&c[i][j]>ct)
 {
 ct=c[i][j];
 l1=l;
 }
 }
 s[p[0][l1]][p[1][l1]]=-1;
 /* printf(" Variable sortante: ( %2d, %2d)\n",p[0][l1],p[1][l1]);
 ct=0;
 printf("Solution\n");
 for(i=1;i<=n;i++)
 {
 for(j=1;j<=m;j++)
 if(s[i][j]!=-1)
 {
 printf(" %2d",s[i][j]);
 ct+=s[i][j]*c[i][j];
 }
 else printf(" *");
 printf("\n");
 }
 printf("coût: %5d\n",ct); */
 }
 }
 while(min<0);
} 

I'm reading: خوارزم شارن وكوبر

بقلم soufian najim

سفيان، احب أن أضع كل ما أعرف من معلومات حول الحاسوب والتقنيات الجديدة، وخطرت لي فكرة عمل مدونة تضم كل المجالات التعليمية التي أستطيع إفادتكم بها ، فأرجوا ان لاتبخلوا علي أيضا بمتابعتكم لمواضيعي كما ان تعليقاتكم تهمني وتزيد من عطائي لكم إخوتي الكرام وأي استفسار ان موجود وشكرا

قسم : الرئيسية