Некоторые выводы

7. Некоторые выводы

Попробуем охарактеризовать поведение алгоритмов метода отсечения при решении задач целочисленного линейного программирования. В качестве меры продолжительности вычислений могут рассматриваться количество симплексных итераций I и количество правильных отсечений (дополнительных линейных ограничений) D.

Для первого алгоритма Гомори и различных его обобщений I и D также тесно связаны между собой (как показывает эксперимент, в большинстве случаев решение отдельной задачи (£, С) требует сравнительно небольшого количества симплексных итераций).

Переходим к изложению отдельных свойств алгоритмов метода отсечения.

Числа I и D имеют (в среднем) тенденцию к возрастанию с увеличением числа переменных и ограничений, ростом порядка коэффициентов задачи и увеличением заполненности матрицы .

Это явление кажется естественным, но опыт показывает, что в дискретном программировании «естественное» и «правдоподобное» не всегда оказывается правильным. Точнее говоря, опыт, накопленный на задачах ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ, нельзя механически переносить на задачи ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.

Прежде всего, обращает на себя внимание «нерегулярность», «непредсказуемость» поведения алгоритмов метода отсечения. Для ряда задач оптимальное решение не удавалось получить после многих тысяч итераций, в то время как другие задачи решались за несколько десятков итераций.

Не удается установить непосредственную связь между размерами задач (т.е. числом ограничений m и переменных n) и числом итераций: неудачи были зафиксированы даже для небольших задач (m≤10, n≤10), а успехи – для задач достаточно большого размера (m = 215, n = 2600). Возможно, впрочем, что попытка установления подобной связи – это неправомерное перенесение результатов ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ в область ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.

Быть может, более естественной характеристикой задачи (£, С) является не число 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();

}