أنت هنا:برمجها»التحليل الرقمي»البرمجة الخطية»خوارزم أولي التبسيط دونتزك
كتبه البرمجة الخطية 3537
خوارزم أولي التبسيط دونتزك خوارزم أولي التبسيط دونتزك
قيم الموضوع
(1 تصويت)
 
 

 

مصطلحات
العربية: خوارزم أولي التبسيط - طريقة دونتزك
 الإنجليزية: Primal simplex algorithm - Danzig Method
الفرنسية: Algorithm de simplexe premier- Méthode du Gradient Conjigué

المبدأ 

نحسب متتالية لرؤوس متعدد الأوجه (polyèdre ) للقواعد الإجبارية (حلول القواعد المقبولة)، كل منها أفضل من سابقتها (بنسبة للدالة الاقتصادية).

الخوارزم

نبدأ بحل من قاعدة مقبولة. 

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

البرنامج الخطي على الشكل التالي : 

 

 اختيار من بين المتغيرات خارج  القاعدة، لـ x'k ، متغير داخل القاعدة:

 

 تحديد من بين المتغيرات خارج القاعدة، لـ x'n+1 ، متغير خارج القاعدة: 

 

 حذف x'k باستعمال المدارية (pivotage ) (حذف جوص)

1. تقسيم  القاعد الإجبارية l  بالمدار  .  

2.  تغيير  القاعد الإجباريةi  ، لكلi  l ، بضرب القاعد الإجبارية l  في    ونطرحها من القاعد الإجباريةi  .

3.  تغيير الدالة الاقتصادية بضرب القاعد الإجبارية l  في   ونطرحها من القاعد الإجبارية z .

نحصل على الحل الأمثل عندما تصبح جميع معاملات    للدالة الاقتصادية المعبر عنها بدلالة المتغيرات السالبة الخارجة عن القاعدة. 

مثال

لنحل البرنامج الخطي التالي:

 

الحل اليدوي

الشكل القياسي 

 

ندخل متغير مصطنع x6 

 

ندخل أيضا الدالة الاقتصادية الملحقةmax z' = -x6  .

 

 

 

 

 

 

 

 

حل مقبول    

 

 

 

نهاية الطور 1 

 

 

 

نهاية الطور    2

 

 

 

 

الحل المثالي:

z=46/3   بحيث  x1 = 8/3, x2 = 10/3, x3 = 0, x4 = 14/3, x5 = 0  

البرمجة

#include <math.h>
#include <conio.h>
#define NMAX 6
#define MMAX 6
#define VARMAX 12
 
int pl_aps_entrant(double a[MMAX][NMAX],int hb[NMAX],int m,int n,int phase); 
int pl_aps_sortant(double a[MMAX][NMAX],int m,int k); 
void pl_pivotage(double a[MMAX][NMAX],int db[MMAX],int hb[NMAX],int m,int n,int l,int k); 
void pl_aps_affich(double a[MMAX][NMAX],int db[MMAX],int hb[NMAX], int m,int n,int phase);
int pl_simplexe_primal(double a[MMAX][NMAX],double sol[VARMAX],
                        int ineq1,int ineq2, int eq,int n);
 
main()
{
 int i,j,ineq1,ineq2,eq,n,err;
 double a[MMAX][NMAX],sol[VARMAX];
 clrscr();
 /* nb de variables */
 n=2;
 /* fonction economique */
 a[0][0]=0;a[0][1]=2;a[0][2]=3;
 /* inequations en <= (nb=ineq1) */
 ineq1=3;
 a[1][0]=6;a[1][1]=1;a[1][2]=1;
 a[2][0]=-4;a[2][1]=-2;a[2][2]=-1;
 a[3][0]=-2;a[3][1]=-2;a[3][2]=1;
 /* inequations en >= (nb=ineq2) */
 ineq2=0;
 /* equations (nb=eq) */
 eq=0;
 printf("Algorithme primal du simplexe\n"); 
err=pl_simplexe_primal(a,sol,ineq1,ineq2,eq,n);
 if(err==1)printf("Solution infinie\n");
 else
 if(err==2)printf("Domaine vide\n");
 else
 {
 printf("Solution optimale:\n");
 for(i=1;i<=ineq1+ineq2+n;i++)
 printf("x%d =%23.16e\n",i,sol[i]);
 printf("Valeur optimale: z=%23.16e\n",-a[0][0]);
 }
} 

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

نحذف التعليقات من الدالةpl_simplexe_primal  ؛ في كل كرة يظهر البرنامج التبسيط (بشكل مختصر) وكذلك المتغيرات الداخلة والخارجة.

الطور 1
 x1 x2 x6
z'+ 0.0000e+00 0.0000e+00 0.0000e+00 -1.0000e+00 
z+ 0.0000e+00 2.0000e+00 3.0000e+00 0.0000e+00 
x3 6.0000e+00 1.0000e+00 1.0000e+00 0.0000e+00 
x4 -4.0000e+00 -2.0000e+00 -1.0000e+00 -1.0000e+00 
x5 -2.0000e+00 -2.0000e+00 1.0000e+00 -1.0000e+00  
 
المتغير الداخل  :x6 المتغير الخارج   : x4
 x1 x2 x4
z'+ 4.0000e+00 2.0000e+00 1.0000e+00 -1.0000e+00 
z+ 0.0000e+00 2.0000e+00 3.0000e+00 0.0000e+00 
x3 6.0000e+00 1.0000e+00 1.0000e+00 0.0000e+00 
x6 4.0000e+00 2.0000e+00 1.0000e+00 -1.0000e+00 
x5 2.0000e+00 0.0000e+00 2.0000e+00 -1.0000e+00 

  المتغير الداخل  :x1 المتغير الخارج   :x6
 x6  x2 x4
z'+ 0.0000e+00 -1.0000e+00 0.0000e+00 0.0000e+00 
z+ -4.0000e+00 -1.0000e+00 2.0000e+00 1.0000e+00 
x3 4.0000e+00 -5.0000e-01 5.0000e-01 5.0000e-01 
x1 2.0000e+00 5.0000e-01 5.0000e-01 -5.0000e-01 
x5 2.0000e+00 -0.0000e+00 2.0000e+00 -1.0000e+00 
 
الطور 2
 x2 x4
z+ -4.0000e+00 2.0000e+00 1.0000e+00 
x3 4.0000e+00 5.0000e-01 5.0000e-01 
x1 2.0000e+00 5.0000e-01 -5.0000e-01 
x5 2.0000e+00 2.0000e+00 -1.0000e+00 

 المتغير الداخل  :x2 المتغير الخارج   :x5
 x5 x4
z+ -6.0000e+00 -1.0000e+00 2.0000e+00 
x3 3.5000e+00 -2.5000e-01 7.5000e-01 
x1 1.5000e+00 -2.5000e-01 -2.5000e-01 
x2 1.0000e+00 5.0000e-01 -5.0000e-01 

 المتغير الداخل  :x4 المتغير الخارج   :x3
  x5 x3
z+ -1.5333e+01 -3.3333e-01 -2.6667e+00 
x4 4.6667e+00 -3.3333e-01 1.3333e+00 
x1 2.6667e+00 -3.3333e-01 3.3333e-01 
x2 3.3333e+00 3.3333e-01 6.6667e-01 
 
الحل المثالي  :
x1 = 2.666666666666667e+00
x2 = 3.333333333333333e+00
x3 = 0.000000000000000e+00
x4 = 4.666666666666666e+00
x5 = 0.000000000000000e+00 
 
القيمة المثالة
z= 1.533333333333333e+01 

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

  • معايير الدالة
  • a : جدول معاملات المشكل
  • sol : جدول يمثل الحل المثالي
  • ineq1 : عدد متراجحات >=
  • ineq2 : عدد متراجحات <=
  •  
  • eq : عدد المعادلات
    n : درجة المصفوفة
  •  
  • القيمة الرجعية
  • سيتم وضع حلول البرنامج في الجدول sol وقيمة هذا الحل (أي الدالة الاقتصادية) ستكون في الخانة a[0][0]i.
  •  

بنية المعطيات

  • يجب على المعطيات أن تكون على هذا الشكل في المصفوفة الرئيسية:

السطر 0 من المصفوفة a : يمثل الدالة الإقتصادية
الخانة 0 تساوي القيمة 0، أما الخانات من 1 إلى n فهي تمثل عوامل الدالة الإقتصادية

السطور من1 إلى ineq1 للمصفوفة a : تمثل المتراجحات من الصنف <= 
الخانة 0 تمثل العنصر الثاني، والخانات من 1 إلى n تمثل عوامل المتغيرات في هذه المتراجحات

السطور من ineq1+1 إلى ineq1+ineq2 للمصفوفة a :تمثل المتراجحات من صنف >= 
الخانة 0 تساوي العنصر الثاني، والخانات من 1 إلى n تمثل عوامل المتغيرات في هذه المتراجحات

السطور من ineq1+ineq2+1 إلى ineq1+ineq2+eq للمصفوفة a : تمثل المعادلات
الخانة 0 تساوي العنصر الثاني، والخانات من 1 إلى n تمثل عوامل المتغيرات في هذه المعادلات

تستدعي الدالة الرئيسية ثلاث دوال أخرى يجب أن تعرف هي أيضا في البرنامج الرئيسي وهي كالتالي:

int pl_aps_entrant(double a[MMAX][NMAX],int hb[NMAX],int m,int n,int phase) 
int pl_aps_sortant(double a[MMAX][NMAX],int m,int k) 
void pl_pivotage(double a[MMAX][NMAX],int db[MMAX],int hb[NMAX],int m, int n,int l,int k)
  • معايير الدالة pl_aps_entrant هي كالتالي :
    a  :  جدول معاملات المشكل العام
    hb: جدول يحتوي على أرقام خانات المتغيرات خارج القاعدة
  • m : عدد الإشكاليات
    n  : عدد المتغيرات
  • phase : تساوي 1 (متغير إصطناعي) أو 2.
    ترجع خلال كل مرحلة المتغير الداخل للقاعدة.

  • معايير الدالة pl_aps_sortant هي كالآتي :
    a  : جدول معاملات المشكل العام
    m : عدد الإشكاليات
  • k  : يمثل رقم خانة المتغير الداخل.
    ترجع خلال كل مرحلة المتغير الخارج من القاعدة.
  •  
  • معايير الدالة pl_pivotage هي كالآتي:
    • a  : جدول معاملات المشكل العام
    • db: جدول يحتوي على أرقام خانات متغيرات القاعدة
    • hb: جدول يحتوي على خانات متغيرات خارج القاعدة
    • m : عدد الإشكاليات
    • n  : عدد المتغيرات
    • l   : يمثل رقم خانة المتغير الخارج
    • k : يمثل رقم خانة المتغير الداخل.
    • تقوم هذه الدالة بتحويل جدول طريقة أولي التبسيط باستعمال مدارية جوص-جوردان خلال كل مرحلة
    •  
    • ملاحظة: إذا كنا نريد أن تظهر الدالة pl_simplexe_primal الحل خلال كل خطوة وقيمة السعر أيضا فيجب أن تحذف رمزي التعليقات  /*  و*/. تستدعي هذه الدالة دالة أخرى خاصة بالإظهار وهي معرفة كالتالي:
    •  void pl_aps_affich(double a[MMAX][NMAX],int db[MMAX],int hb[NMAX],int m, int n,int phase)
      • معايير هذه الدالة هي كالتالي :
    • a  :  جدول معاملات المشكل العام 
      hb: جدول يحتوي على أرقام خانات المتغيرات خارج القاعدة
      db: جدول يحتوي على أرقام خانات متغيرات القاعدة
      m : عدد الإشكاليات
      n  : عدد المتغيرات
      phase : تساوي 1 (متغير إصطناعي) أو 2.

الثوابث

الثابتة الصحيحة NMAX تساوي العدد القصوي للمتغيرات (+2).
الثابتة الصحيحة MMAX تساوي العدد القصوي للإشكاليات (+2).
الثابتة الصحيحة VARMAX تساوي NMAX+MMAX.

int pl_aps_entrant(double a[MMAX][NMAX],int hb[NMAX],int m,int n,int phase) 
{
 int i,j,k,l;
 double d,s,max;

 k=0; max=0.0;

 if(phase==2) l=0;
 else         l=m+1;

 for(j=1;j<=n;j++) 
 {
   d=a[l][j]; s=0.0;
   if((d>0)&&(hb[j]!=n+m)) 
   {
     for(i=1;i<=m;i++) s+=fabs(a[i][j]);
     d/=s;
     if(d>max) { max=d; k=j; } 
   }
 }
 return(k); 
} 

int pl_aps_sortant(double a[MMAX][NMAX],int m,int k) 
{
 int i,l;
 double rap,min;

 min=1e308;
 l=0;
 for(i=1;i<=m;i++)
   if(a[i][k]>0)
   {
     rap=a[i][0]/a[i][k];
     if(rap<min) { min=rap; l=i; } 
    }

 return(l);
} 

void pl_pivotage(double a[MMAX][NMAX],int db[MMAX],int hb[NMAX], int m,int n,int l,int k) 
{
 int i,j;
 double pivot,coef;

 pivot=a[l][k];
 for(i=0;i<=m;i++)
  if(i!=l) 
  {
    coef=a[i][k]/pivot;
    a[i][k]=-coef;
    for(j=0;j<=n;j++)
     if(j!=k) a[i][j]=a[i][j]-coef*a[l][j]; 
   }
   coef=1/pivot;
   a[l][k]=coef;

   for(j=0;j<=n;j++)
    if(j!=k) a[l][j]=coef*a[l][j];
  
   i=db[l];
   db[l]=hb[k];
   hb[k]=i; 
} 

void pl_aps_affich(double a[MMAX][NMAX],int db[MMAX],int hb[NMAX], int m,int n,int phase) 
{
 int i,j;

 printf(" ");
 for(j=1;j<=n;j++)
   if((phase==1)||(hb[j]!=n+m))
     printf(" x%d",hb[j]);
 printf("\n");

 if(phase==1)
 {
  printf("z'+");
  for(j=0;j<=n;j++)
    printf("%11.5e ",a[m+1][j]);
  printf("\n"); 
  }

 for(i=0;i<=m;i++) 
 {
   if(i==0)printf("z+ ");
   else if(db[i]!=0) printf("x%d ",db[i]);
   else printf(" "); 

   for(j=0;j<=n;j++)
     if((phase==1)||(hb[j]!=n+m))
        printf("%11.5e ",a[i][j]); 
   printf("\n"); 
  }
} 

 
int pl_simplexe_primal(double a[MMAX][NMAX],double sol[VARMAX],
 int ineq1,int ineq2, int eq,int n)
{
 int i,j,k,l,phase,m,m1;
 int db[MMAX],hb[NMAX];
 double min;
 m=ineq1+ineq2+eq;
 for(i=ineq1+1;i<=ineq1+ineq2;i++)
 for(j=0;j<=n;j++)
 a[i][j]=-a[i][j];
 for(i=1;i<=ineq1+ineq2;i++)
 db[i]=n+i;
 for(i=ineq1+ineq2+1;i<=m;i++)
 db[i]=0;
 for(j=1;j<=n;j++)
 hb[j]=j;
 if(eq!=0)
 {
 /* printf("Cr‚ation d'une base de d‚part\n"); */
 for(i=ineq1+ineq2+1;i<=m;i++)
 {
 l=i;
 k=0;
 for(j=1;j<=n;j++)
 if(a[i][j]!=0)k=j;
 if(k==0)
 {
 if(a[i][0]!=0)return(2);
 }
 else
 {
 /* pl_aps_affich(a,db,hb,m,n,2); */
 /* printf("var.entrante: x%d\n",hb[k]); */
 pl_pivotage(a,db,hb,m,n,l,k);
 hb[k]=hb[n];
 for(j=0;j<=m;j++)
 a[j][k]=a[j][n];
 n-=1;
 }
 }
 }
 n+=1;
 m1=m;
 hb[n]=n+m;
 phase=2;
 l=0;
 min=0;
 for(i=1;i<=m;i++)
 if(a[i][0]<min)
 {
 min=a[i][0];
 l=i;
 }
 if(l!=0)phase=1;
 k=1;
 if(phase==1)
 {
 /* printf("Phase 1\n"); */
 m1=m+1;
 for(j=0;j<n;j++)
 a[m1][j]=0;
 for(i=1;i<=m;i++)
 if(a[i][0]<0)
 a[i][n]=-1;
 else a[i][n]=0;
 a[0][n]=0;
 a[m1][n]=-1;
 /* pl_aps_affich(a,db,hb,m,n,phase); */
 /* printf("var.entrante: x%d var.sortante: x%d\n",hb[n],db[l]); */
 pl_pivotage(a,db,hb,m1,n,l,n);
 }
 while(phase<=2)
 {
 do
 {
 /* pl_aps_affich(a,db,hb,m,n,phase); */
 k=pl_aps_entrant(a,hb,m,n,phase);
 if(k!=0)
 {
 l=pl_aps_sortant(a,m,k);
 if(l==0)return(1);
 /* printf("var.entrante: x%d var.sortante: x%d\n",hb[k],db[l]); */
 pl_pivotage(a,db,hb,m1,n,l,k);
 }
 }
 while(k!=0);
 if(phase==1)
 {
 l=0;
 for(i=1;i<=m;i++)
 if(db[i]==n+m)l=i;
 if(l!=0)
 {
 if(fabs(a[l][0])>1e-15)return(2);
 else
 {
 for(j=1;j<=n;j++)
 if(a[l][j]!=0)
 k=j;
 /* printf("var.entrante: x%d var.sortante: x%d\n",hb[k],db[l]); */
 pl_pivotage(a,db,hb,m1,n,l,k);
 }
 }
 }
 phase+=1;
 m1-=1;
 /* if(phase==2)printf("Phase 2\n"); */
 }
 for(i=1;i<m+n;i++)
 sol[i]=0;
 for(i=1;i<=m;i++)
 sol[db[i]]=a[i][0];
 return(0);
}
مقالات أخرى من نفس الفئة « البرمجة الخطية إشكالية النقل »

أضف تعليقا

إصنعها يريد أن يتأكد أنك لست روبوتا، لذلك أحسب ما يلي:

كود امني
تحديث

عد إلى الأعلى

Main Menu-burger