Быть может, более естественной характеристикой задачи (£, С) является не число m линейных ограничений, задающих многогранное множество £, а число mц - линейных ограничений, задающих многогранное множество V(£)*). Между тем легко привести примеры, когда при небольших m и n число mц будет достаточно велико.
«Нерегулярность» сказывается и в следующем факте, подмеченном рядом исследователей: иногда удается существенно сократить число итераций за счет перенумерации переменных.
Наконец, имеет место немонотонность приближения псевдоплана Хr к оптимальному плану X* – с ростом r расстояние ρ(Хr, X*) не обязательно уменьшается и лишь на последней итерации обязательно становится равным нулю.
Большое влияние на число итераций оказывает правило выбора порождающей строки. Здесь также имеет место «нерегулярность» – в то время как одно правило приводит к успеху за десятки итераций, другое не дает решения после тысяч итераций.
При решении задач целочисленного линейного программирования по методу отсечения имеются как успехи, так и неудачи.
К наиболее успешным работам следует отнести:
1) Задачи покрытия, в том числе задачи, связанные с минимизацией булевых функций.
2) Применение к задачам оптимального кодирования.
3) Применение к задаче оптимального извлечения информации из параллельных систем памяти.
Наиболее характерными задачами, для которых имела место неудача, являются:
1) Задачи коммивояжера.
2) Задача теории расписаний.
3) Некоторые из обобщенных задач покрытия.
В настоящий момент отсутствует исчерпывающее объяснение удач или неудач различных вычислительных экспериментов. Все же для задачи коммивояжера и задачи теории расписаний является правдоподобным следующее соображение.
Формулировка этих задач на языке ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ является «неестественной». Для задачи сравнительно небольшой в «естественной» формулировке, в модели ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ фигурирует большое количество ограничений и переменных. Возможно, что для этих задач более перспективными являются комбинаторные методы (например, метод ветвей и границ для задачи коммивояжера). Впрочем, последнее утверждение является спорным, так как комбинаторные методы очень чувствительны к специфике задач, введению дополнительных условий и т.п.
По-видимому, успех в решении задач покрытия связан с тем, что удалось напасть на класс задач, практически важных и в то же время успешно решаемых. Было бы весьма интересно точно охарактеризовать класс задач покрытия, хорошо решаемых по методу отсечения. Это тем более интересно, что построены примеры обобщенных задач покрытия, для которых возникают значительные вычислительные трудности.
И вообще, выделение отдельных классов эффективно решаемых задач – важная и интересная проблема.
Заключение
Подведем некоторые итоги. Метод отсечения находится в стадии развития и совершенствования. При реализации этого метода возникают трудности, носящие, по-видимому, не только технический, но и принципиальный характер. В настоящий момент можно говорить о решении с помощью метода отсечения задач не более чем среднего размера (сотни переменных и десятки ограничений).
Наиболее перспективными для дальнейших исследований по методу отсечения представляются следующие направления:
1) Исследование строения множеств £ц и V(£ц).
2) Исследование свойств правильных отсечений.
3) Указание новых способов построения правильных отсечений.
4) Развитие новых классов алгоритмов метода отсечения (например, прямых алгоритмов).
5) Выделение отдельных классов эффективно решаемых задач.
Список литературы
1. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование, М.: Наука, – 1969.
2. Лященко И.Н. Линейное и нелинейное программирование, М.: Наука, – 1985.
3. Санович К.М. Исследование операций, М.: Наука, – 1989.
Приложение
1. ПРОГРАММА, РЕАЛИЗУЮЩАЯ ПЕРВЫЙ АЛГОРИТМ ГОМОРИ
#include<ctype.h>
#include<string.h>
#include<conio.h>
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
class simplex {int n; // число переменных +1
int m; // число ограничений
int *basis;
int *mi;
float *mc;
int flag;
public:simplex (int m1, FILE *fp, int f);
~simplex()
{if(mi) free(mi);
if(mc) free(mc);
if(basis) free(basis);
}
void printsimtable (int g);
void iterac();
void resultat();
};
simplex:simplex (int m1, FILE *fp, int f)
{FILE *fp1;
int fl, i;
if((fp1=fopen («hell1», «w+»))==NULL) {printf («Ошибка выделения памяти!»);
exit(1);
};
m=m1;
n=0;
basis=NULL;
flag=f;
fl=1;
do {fread(&c, sizeof (struct koef), 1, fp);
if (! feof(fp))
{do {fread(&i, sizeof(int), 1, fp1);
if (! feof(fp1) && i==c.ind)
{fl=0;
break;
}
} while (! feof(fp1));
if(fl) {fwrite (&c.ind, sizeof(int), 1, fp1);
n++;
fflush(fp1);
}
else fl=1;
rewind(fp1);
}
} while (! feof(fp));
rewind(fp);
if (m>n-1) {printf («Число ограничений больше или равно числу переменных»);
getch();
exit(1);
}
mi=(int *) malloc (sizeof(int)*n);
mc=(float *) malloc (sizeof(float)*n*(m+1));
if (! mc ||! mi) {printf («Ошибка выделения памяти!»);
getch();
exit(1);
}
fread (mi, sizeof(int), n, fp1);
qsort (mi, n, sizeof(int), sort);
fclose(fp1);
remove («hell1»);
for (fl=0; fl<m+1; fl++)
for (i=0; i<n; i++)
*(mc+fl*n+i)=0;
fl=m;
do {fread(&c, sizeof (struct koef), 1, fp);
if (! feof(fp))
{if (c.ind)
{for (i=1; i<n; i++)
if (c.ind==*(mi+i))
{*(mc+fl*n+i)=*(mc+fl*n+i)+c.coef;
break;
}
}
else{*(mc+fl*n)=c.coef;
if (fl==m) fl=0;
else fl++;
}
}
} while (! feof(fp));
}
void simplex:iterac()
{int i, j, fl, fl1, k, l;
float s, min;
for (i=1; i<n; i++)
{if(*(mc+m*n+i)!=0)
{fl=1;
for (j=0; j<m; j++)
if(*(mc+j*n+i)!=0) {fl=0;
break;
}
if(fl) {printf («Не все перменные целевой функции входят в ограничения»);
getch();
exit(1);
}
}
}
basis=(int *) malloc (sizeof(int)*m);
if(! basis) {printf («Ошибка выделения памяти»);
getch();
exit(1);
}
for (i=0; i<m; i++)
*(basis+i)=0;
i=0;
do
{fl=1;
fl1=0;
for (j=1; j<n; j++)
if(*(mc+i*n+j)>0) {fl=0;
break;
}
if(fl) {printf («Переменные должны быть положительны»);
getch();
exit(1);
}
s=*(mc+i*n+j);
for (l=0; l<n; l++)
*(mc+i*n+l)=*(mc+i*n+l)/s;
for (l=0; l<=m; l++)
if (l!=i) {s=*(mc+l*n+j);
for (k=0; k<n; k++)
*(mc+n*l+k)=*(mc+l*n+k) – s*(*(mc+i*n+k));
}
for (l=0; l<m; l++)
{s=0;
for (k=1; k<n; k++)
s=s+fabs(*(mc+l*n+k));
if (s==0) {if(*(mc+l*n)==0) printf («Уравнения линейно зависимы»);
else printf («Система ограничений несовместна»);
getch();
exit(1);
}
}
*(basis+i)=j;
for (l=0; l<m; l++)
if(*(mc+l*n)<0)
for (k=0; k<n; k++)
*(mc+l*n+k)= – (*(mc+l*n+k));
for (l=0; l<m; l++)
if((*(basis+l)==0)||(*(mc+l*n+(*(basis+l)))<0)) {i=l; fl1=1; break;}
} while(fl1);
printsimtable(0);
do {min=100000;
fl=0;
for (l=1; l<n; l++)
{if(*(mc+m*n+l)>0) {fl=1;
fl1=1;
for (k=0; k<m; k++)
if(*(mc+k*n+l)>0)
{fl1=0;
s=*(mc+k*n)/(*(mc+k*n+l));
if (s<min) {min=s;
i=k;
j=l;
}
}
if(fl1) {printf («Решения нет»);
getch();
exit(1);
}
break;
}
}
if(fl) {s=*(mc+i*n+j);
for (l=0; l<n; l++)
*(mc+i*n+l)=*(mc+i*n+l)/s;
for (l=0; l<=m; l++)
if (l!=i) {s=*(mc+l*n+j);
for (k=0; k<n; k++)
*(mc+l*n+k)=*(mc+l*n+k) – s*(*(mc+i*n+k));
}
printsimtable(0);
*(basis+i)=j;
}
} while(fl);
}
void simplex:resultat()
{int i, j, fl;
if (flag==-1) printf («Минимальное значение функции цели равно % 8.2f\n»,*(mc+m*n));
else printf («Максимальное значение функции цели равно % 8.2f\n», – (*(mc+m*n)));
printf («Оптимальный план:»);
for (i=1; i<n; i++)
{fl=0;
for (j=0; j<m; j++)
if(*(mi+i)==*(basis+j)) {fl=1;
break;
}
if(fl) printf («x % 02d=%-5.2f\n»,*(mi+i),*(mc+j*n));
else printf («x % 02d=0 \n»,*(mi+i));
printf(«»);
}
}
void simplex:printsimtable (int g)
{int i, j, k, v=g, raz;
clrscr();
raz=n-1–6*(v+1);
if((raz<=0)&&(abs(raz)<6)) raz=6+raz;
else if (raz>0) raz=6;
else return;
for (j=0; j<3; j++)
{if (j!=1) {printf(«* * *»);
for (i=0; i<raz; i++)
printf(» *»);
if (raz<6) printf («\n»);
}
else {if(*(mc+m*n)>=0) printf («* *%8.2f *»,*(mc+m*n));
else printf («* * -%-7.2f *», – (*(mc+m*n)));
for (i=1; i<=raz; i++)
if(*(mc+n*k+6*v+i)>=0) printf («%8.2f *»,*(mc+n*k+6*v+i));
else printf («-%-7.2f *», – (*(mc+n*k+6*v+i)));
if (raz<6) printf («\n»);
}
}
for (i=0; i<20+raz*10; i++)
printf(«*»);
getch();
rewind(fp);
simplex ob (no, fp, f);
gomori();
ob.iterac();
ob.resultat();
}