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


  

 

مصطلحات
العربية: خوارزم ثنائي التبسيط - طريقة ليمك
الإنجليزية: Dual simplex algorithm - Lemke Method
الفرنسية: Algorithme dual de simplexe - Méthode de Lemke

المبدأ 

نحسب متتالية لرؤوس حلول القاعدة الثنائية-المقبولة، أي لكل   موجبة (معاملات الدالة الاقتصادية معبرة بالنسبة للمتغيرات خارج القاعدة)، كل منها ينقص قيمة الدالة الاقتصادية بالنسبة لسابقتها. 

الخوارزم 

نبدأ بأي حل من القاعدة الثنائية-المقبولة. 

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

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

 

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

 

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

 

حذف بالمحورية (حذف جوص):

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

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

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

نحصل على الحل الأمثل عندما يصبح  الحل مقبولا، أي عندما تكون جميع المتغيرات موجبة   (, i = 1,...m) 

مثال 

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

 

الحل اليدوي

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

 

 

ندخل قاعدة إجبارية مصطنعة ( مع لعضوثاني مصطنع)

x1 + x2 + x6 = 1   (مع x6 0  ) 

 

نهاية الطور 1


 نهاية الطور 2  

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

 x1 = 8/3, x2 = 10/3, x3 = 0, x4 = 14/3, x5 = 0 مع    z = 46/3

البرمجة 

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

int pl_ads_sortant(double a[MMAX][NMAX],int hb[NMAX],int m,int n,int phase);
int pl_ads_entrant(double a[MMAX][NMAX],int n,int l);
void pl_pivotage(double a[MMAX][NMAX],int db[MMAX],int hb[NMAX],int m,int n,int l,int k);

void pl_ads_affich(double a[MMAX][NMAX],int db[MMAX],int hb[NMAX],int m,int n)
int pl_simplexe_dual(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 dual du simplexe\n");
 err=pl_simplexe_dual(a,sol,ineq1,ineq2,eq,n);
 if(err==2)printf("Solution infinie\n");
 else
 if(err==1)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_dual؛ في كل كرة يظهر البرنامج التبسيط (بشكل مختصر) وكذلك المتغيرات الداخلة والخارجة.  يظهر بعد ذلك حلول المثالية وقيمة كلفة النقل المرافقة للدالة الاقتصادية.

الطور 1
  x1 x2
z+ 0.0000e+00 2.0000e+00 3.0000e+00 
x3 6.0000e+00 1.0000e+00 1.0000e+00 
x4 -4.0000e+00 -2.0000e+00 -1.0000e+00 
x5 -2.0000e+00 -2.0000e+00 1.0000e+00 
x6 0.0000e+00 1.0000e+00 1.0000e+00 
المتغير الداخل  :x2 المتغير الخارج   : x6
 x1 x6
z+ 0.0000e+00 -1.0000e+00 -3.0000e+00 
x3 6.0000e+00 0.0000e+00 -1.0000e+00 
x4 -4.0000e+00 -1.0000e+00 1.0000e+00 
x5 -2.0000e+00 -3.0000e+00 -1.0000e+00 
x2 0.0000e+00 1.0000e+00 1.0000e+00 
المتغير الداخل  :x6 المتغير الخارج   : x3
 x1 x3
z+ -1.8000e+01 -1.0000e+00 -3.0000e+00 
x6 -6.0000e+00 -0.0000e+00 -1.0000e+00 
x4 2.0000e+00 -1.0000e+00 1.0000e+00 
x5 -8.0000e+00 -3.0000e+00 -1.0000e+00 
x2 6.0000e+00 1.0000e+00 1.0000e+00 
الطور 2
 x1 x3
z+ -1.8000e+01 -1.0000e+00 -3.0000e+00 
x2 6.0000e+00 1.0000e+00 1.0000e+00 
x4 2.0000e+00 -1.0000e+00 1.0000e+00 
x5 -8.0000e+00 -3.0000e+00 -1.0000e+00 
المتغير الداخل  :x1 المتغير الخارج   : x5
 x5 x3
z+ -1.5333e+01 -3.3333e-01 -2.6667e+00 
x2 3.3333e+00 3.3333e-01 6.6667e-01 
x4 4.6667e+00 -3.3333e-01 1.3333e+00 
x1 2.6667e+00 -3.3333e-01 3.3333e-01 
Sالحل المثالي  :
x1 = 2.666666666666667e+00
x2 = 3.333333333333333e+00
x3 = 0.000000000000000e+00
x4 = 4.666666666666666e+00
x5 = 0.000000000000000e+00
القيمة المثالة
V z= 1.533333333333333e+01

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

  • معايير الدالة
  • 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_ads_sortant(double a[MMAX][NMAX],int hb[NMAX],int m,int n,int phase) 
int pl_ads_entrant(double a[MMAX][NMAX],int n,int l) 
void pl_pivotage(double a[MMAX][NMAX],int db[MMAX],int hb[NMAX], int m,int n,int l,int k)

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

  • a  :  جدول معاملات المشكل العام
    hb: جدول يحتوي على أرقام خانات المتغيرات خارج القاعدة
  • m : عدد الإشكاليات
    n  : عدد المتغيرات
  • phase : تساوي 1 (متغير إصطناعي) أو 2.
    ترجع هذه الدالة المتغير الخارج من القاعدة خلال كل مرحلة.

    • معايير الدالة pl_ads_entrant هي كالآتي :
      a  : جدول معاملات المشكل العام
      n : عدد المتغيرات
    • l  : يمثل رقم خانة المتغير الخارج.
      ترجع خلال كل مرحلة المتغير الداخل للقاعدة.
  •  
  • معايير الدالة pl_pivotage هي كالآتي:
    • a  : جدول معاملات المشكل العام
    • db: جدول يحتوي على أرقام خانات متغيرات القاعدة
    • hb: جدول يحتوي على خانات متغيرات خارج القاعدة
    • m : عدد الإشكاليات
    • n  : عدد المتغيرات
    • l   : يمثل رقم خانة المتغير الخارج
    • k : يمثل رقم خانة المتغير الداخل.
    • تقوم هذه الدالة بتحويل جدول طريقة التبسيط باستعمال مدارية جوص-جوردان خلال كل مرحلة

      • ملاحظة: إذا كنا نريد أن تظهر الدالة pl_simplexe_dual الحل خلال كل خطوة وقيمة السعر أيضا فيجب أن تحذف رمزي التعليقات /* و */. تستدعي هذه الدالة دالة خاصة بالإظهار وهي معرفة كالتالي:
          • void pl_ads_affich(double a[MMAX][NMAX],int db[MMAX],int hb[NMAX],int m, int n)
            • معايير هذه الدالة هي كالتالي 
          • a  :  جدول معاملات المشكل العام 
            hb: جدول يحتوي على أرقام خانات المتغيرات خارج القاعدة
            db: جدول يحتوي على أرقام خانات متغيرات القاعدة
            m : عدد الإشكاليات
            n  : عدد المتغيرات

          • الثوابث
        الثابتة الصحيحة NMAX تساوي العدد القصوي للمتغيرات (+2).
        الثابتة الصحيحة MMAX تساوي العدد القصوي للإشكاليات (+2).
        الثابتة الصحيحة VARMAX تساوي NMAX+MMAX.
int pl_ads_sortant(double a[MMAX][NMAX],int hb[NMAX],int m,int n,int phase)
{
 int i,j,k,l;
 double d,s,min;
 l=0;
 min=0.0;
 k=0;
 if(phase==1)
 {
 for(j=1;j<=n;j++)
 if(hb[j]==n+m)k=j;
 }
 if((phase==2)||(k!=0))
 for(i=1;i<=m;i++)
 {
 d=a[i][k];
 s=0.0;
 if(d<0)
 {
 for(j=1;j<=n;j++)
 s+=fabs(a[i][j]);
 d/=s;
 if(d<min)
 {
 min=d;
 l=i;
 }
 }
 }
 return(l);
}

int pl_ads_entrant(double a[MMAX][NMAX],int n,int l)
{
 int j,k;
 double rap,min;
 min=1e308;
 k=0;
 for(j=1;j<=n;j++)
 if(a[l][j]<0)
 {
 rap=a[0][j]/a[l][j];
 if(rap<min)
 {
 min=rap;
 k=j;
 }
 }
 return(k);
}

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_ads_affich(double a[MMAX][NMAX],int db[MMAX],int hb[NMAX],
int m,int n)
{
 int i,j;
 printf(" ");
 for(j=1;j<=n;j++)
 printf(" x%d",hb[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++)
 printf("%11.5e ",a[i][j]);
 printf("\n");
 }
}

int pl_simplexe_dual(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 max;
 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_ads_affich(a,db,hb,m,n); */
 /* 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;
 }
 }
 }
 m1=m;
 phase=2;
 k=0;max=0;
 for(j=1;j<=n;j++)
 if(a[0][j]>max)
 {
 max=a[0][j];
 k=j;
 }
 if(k!=0)phase=1;
 l=1;
 if(phase==1)
 {
 /* printf("Phase 1\n"); */
 m1=m+1;
 for(j=1;j<=n;j++)
 if(a[0][j]>0)a[m1][j]=1;
 else a[m1][j]=0;
 a[m1][0]=0;
 db[m1]=n+m+1;
 /* pl_ads_affich(a,db,hb,m1,n); */
 /* printf("var.sortante: x%d var.entrante: x%d\n",db[m1],hb[k]); */
 pl_pivotage(a,db,hb,m1,n,m1,k);
 }
 while(phase<=2)
 {
 do
 {
 /* pl_ads_affich(a,db,hb,m1,n); */
 l=pl_ads_sortant(a,hb,m1,n,phase);
 if(l!=0)
 {
 k=pl_ads_entrant(a,n,l);
 if(k==0)return(1);
 /* printf("var.sortante: x%d var.entrante: x%d\n",db[l],hb[k]); */
 pl_pivotage(a,db,hb,m1,n,l,k);
 }
 }
 while(l!=0);
 if(phase==1)
 {
 k=0;
 for(j=1;j<=n;j++)
 if(hb[j]==n+1+m)k=j;
 if(k!=0)
 {
 if(fabs(a[0][k])>1e-15)return(2);
 else
 {
 for(i=1;i<=m1;i++)
 if(a[i][k]!=0)
 l=i;
 /* printf("var.sortante: x%d var.entrante: x%d\n",db[l],hb[k]); */
 pl_pivotage(a,db,hb,m1,n,l,k);
 }
 }
 }
 if(phase==1)
 {
 for(i=1;i<=m1;i++)
 if(db[i]==n+m1)l=i;
 db[l]=db[m1];
 for(j=0;j<=n;j++)
 a[l][j]=a[m1][j];
 }
 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