Курсовая работа (т): Решение и корректировка решений близких задач линейно-квадратичного программирования

Существует также двойственный метод. Этот метод удобно использовать для решения серии задач типа (1.1) - (1.3), каждая последующая из которых получается из предыдущей добавлением к системе основных ограничений одного или нескольких ограничений.

4. Два подхода к проблеме решения близких линейно-квадратичных задач

На практике часто встречаются линейно - квадратичные задачи близкие по своим параметрам. Такие задачи можно решать каждый раз с самого начала, используя прямой метод, но поскольку у нас стоит задача корректировки близких линейно - квадратичных задач, то можно откорректировать параметры близкой ей, уже решенной задачи, и решить задачу конечным двойственным методом. Известно, что самым быстрым и экономичным для этих целей является именно двойственный метод.

И так, для решения исходной задачи и корректировки близкой ей задачи будем строить программу конечного двойственного метода.

5. Использование программы DMQP

Программа DMQP - программа конечного двойственного метода линейно-квадратичного программирования.

Как и прежде рассматриваем задачу линейно - квадратичного программирования:

,

, ,

где

 - двумерный массив основных ограничений размерности

,  - вектор-столбец размерности

,  и  - нижнее и верхнее ограничениям на переменные,

 - вектор-столбец размерности , соответствующий начальному плану задачи,

 - количество основных ограничений задачи,

 - количество переменных.

Программа корректировки решений близких задач линейно-квадратичного программирования написана на языке С.

Для решения задачи используем двойственный метод.

Программа конечного двойственного метода линейно-квадратичного программирования написана на языке фортран и скомпилирована в файл dmqp. exe.

Запуск этого файла осуществляется с помощью оператора System.

При этом формируются входной и выходной файлы.

Входной файл имеет следующую структуру:

В файле:  - транспонированный двумерный массив ,  и  соответственно равны  и ,  - размер опоры ограничений начального согласованного опорного плана,  - обратная матрица к опорной матрице,  - размер опоры целевой функции начального согласованного опорного плана,  - вектор-столбец, содержащий элементы верхнего треугольника матрицы, обратной к опорной матрице целевой функции, записанные по строчкам;  - вектор-столбец размерности , который содержит следующую информацию: индексы опорных компонент начального плана, вошедшие в опору ограничений (их количество ); индексы опорных компонент начального плана, вошедшие в опору целевой функции (их количество ); индексы неопорных компонент начального плана (их количество ).

Выходной файл содержит следующую результирующую информацию:

значение параметра kod4. Если он равен нулю, то построен оптимальный план задачи;

размерность опоры ограничений;

опору ограничений;

размерность опоры целевой функции;

опору целевой функции;

неопорные индексы;

оптимальный план задачи;

Заключение

В данной курсовой работе была сформулирована линейно - квадратичная задача. Были сформулированы понятия плана, оптимального плана, субоптимального плана. Были сформулированы теорема о достаточном условии оптимальности, критерий управляемости основного ограничения, была выведена формула приращения целевой функции. На основании полученных сведений были доказаны критерий оптимальности и достаточное условие субоптимальности. Была сформулирована двойственная задача, произведена классификация методов решения линейно - квадратичных задач. Так же в курсовой работе было описано два подхода к проблеме решения близких линейно - квадратичных задач. Для решения линейно - квадратичной задачи был выбран двойственный метод, написана программа на языке С, которая его использует. В итоге была решена поставленная задача.

Список использованных источников

1.      Габасов Р., Кириллова Ф.М. Методы линейного программирования. Ч.1 - 3. - Мн.: Изд-во БГУ, 1977, 1978, 1980.

2.      Габасов Р., Кириллова Ф.М., Тятюшкин А.И. Конструктивные методы оптимизации. Ч.1. Линейные задачи. - Мн.: Изд-во БГУ, 1983.

.        Габасов Р., Кириллова Ф.М., Костюкова О.И., Ракецкий В.М. Конструктивные методы оптимизации. Часть 4. Выпуклые задачи. - Мн.: Изд-во Университетское, 1987.

.        Ракецкий В.М. Решение общей задачи выпуклого квадратичного программирования прямым методом. - Програм. Обеспечение ЭВМ / Ин-т математики АН БССР. Мн., 1985. Вып.55. - С.113 - 123.

.        Ракецкий В.М. Решение общей задачи выпуклого квадратичного программирования двойственным методом. - Програм. Обеспечение ЭВМ / Ин-т математики АН БССР. Мн., 1985. Вып.55. - С.124 - 129.

.        Лубочкин А.В. Методы решения выпуклых задач оптимального управления. - Дисс. … канд. физ. - мат. наук. - Мн.: БГУ, 1987.

.        Численные методы оптимизации. Ч.2. Линейные задачи оптимального управления. Практикум. - Гомель: ГГУ, 2001.

Приложения

Приложение А

Текст программы корректировки решений близких задач линейно-квадратичного программирования

# include <stdio. h>

# include <math. h>

# include <string. h>

# include <process. h>

# include <alloc. h>

# include <conio. h>

# include <bios. h>

#define N_M N-M

#define M 2

#define N 10

#define O 1.0A [M] [N],[M],[N], dw [N],= 0.00001, eps2=0.00001,P [M] [M], **Pr, Q [M] [M],[N_M] [N_M],[N_M], Ma [N_M] [N_M],[N],[M],[N];i, j, k,[M],[N_M], kn,[N_M], koc,[N_M], knn,;xr,[N_M] [N_M];kod,,, UslOpt;main ();prosm (void);korect (void);obrabotka (void);callocPr (int);freePr (int);formParam (int);formElem (void);procsogl (int);gs (int, double**,*, int*);menu (int, char *nazv []);*nazv [] =

{"Обработка",

"Выход"

};menu (int kp, char *nazv [])

{ int i,k;();(i=0; i<kp; i++)("\n %d. %s", i+1,nazv [i]);("\n \n выберите пункт-->");("%d",&k);k;

}*d;*r;prosm (void)

{();("\n матрица A: \n");(i=0; i<M; i++)

{printf ("\n");(j=0; j<N; j++)(" %6.3f",A [i] [j]); }("\n вектор B: \n");(i=0; i<M; i++)(" %7.3f",B [i]);("\n вектор dn: \n");(i=0; i<N; i++)(" %5.2f",dn [i]);("\n вектор dw: \n");(i=0; i<N; i++)(" %5.2f",dw [i]);(0);

}korect (void)

{char *nazv [] ={ "Просмотр",

"Изменение B",

"Изменение dn",

"Изменение dw",

"Обработка"};nom,kp=5,s;(1)

{ clrscr ();=menu (kp,nazv);(s)

{ case 1: prosm (); break;2: {printf ("Введите эл-ты вектора\n");(i=0; i<M; i++)

{ printf (" B [%d] =", i);(" %lf",&B [i]); }}; break;3: {printf ("Введите эл-ты вектора\n");(i=0; i<N; i++)

{ printf (" dn [%d] =", i);(" %lf",&dn [i]); }}; break;4: {printf ("Введите эл-ты вектора\n");(i=0; i<N; i++)

{ printf (" dw [%d] =", i);(" %lf",&dw [i]); }}; break;5: return;: {puts ("Не тот номер");();; }

}

}

}callocPr (int n)

{i;= (double**) calloc (n, sizeof (double));(i=0; i<n; i++)[i] = (double*) calloc (n, sizeof (double));

}freePr (int n)

{i;(i=0; i<n; i++)(Pr [i]);(Pr);

}formElem (void)

{i, j, k,,,;[0] =0;[1] =N-1;= N - M;= 0;(j=0; j<N; j++)

{= 0;(i=0; i<M; i++)(j==Jop [i])

{= 1;;

}(! PrOp)

{[k] = j;++;

}

}= 0;= kn;(j=0; j<knn; j++)[j] = Jn [j];(i=0; i<M; i++)(j=0; j<M; j++)[i] [j] = A [i] [Jop [j]];(M);(j=0; j<M; j++)

{(i=0; i<M; i++)

{(k=0; k<M; k++)[i] [k] = P [i] [k];[i] = 0.0;

}[j] = 1.0;(M, Pr, v, &kod);(kod)

}(i=0; i<M; i++)[i] [j] = v [i];

}(M);(j=0; j<knn; j++)[Jnn [j]] = dn [Jnn [j]];(koc>0)(i=0; i<koc; i++)[Joc [i]] = v [i];(M);(i=0; i<M; i++)

{(j=0; j<M; j++)[i] [j] = P [i] [j];[i] = B [i];(j=0; j<kn; j++)[i] - = A [i] [Jn [j]] * x [Jn [j]];

}(M, Pr, v, &kod);(M);(kod)

{("\nОпорная матрица (ограничений) вырождена!!! \n");();

}(i=0; i<M; i++)[Jop [i]] = v [i];(M);(i=0; i<M; i++)

{(k=0; k<M; k++)[i] [k] = P [k] [i];[i] = x [Jop [i]];

}(M, Pr, v, &kod);(M);(kod)

{("\nОпорная матрица (ограничений) вырождена!!! \n");();

}(j=0; j<N; j++)

{[j] = x [j];(i=0; i<M; i++)[j] - = v [i] * A [i] [j];

}

} // formElemprocsogl (int nz)

{l [N],[M],, Thj;i, j, k,,,,;= 0;(1)

{(j=0; j<knn; j++)(Del [Jnn [j]] > eps1)[Jnn [j]] = dn [Jnn [j]] - x [Jnn [j]];(Del [Jnn [j]] < - eps1)[Jnn [j]] = dw [Jnn [j]] - x [Jnn [j]];[Jnn [j]] = 0.0;(koc>0)

{(M);(j=0; j<koc; j++)

{(i=0; i<M; i++)

{(k=0; k<M; k++)[i] [k] = P [i] [k];[i] = A [i] [Joc [j]];

}(M, Pr, v, &kod);(kod)

{("\nОпорная матрица (ограничений) вырождена!!! \n");();

}(i=0; i<M; i++)[i] [j] = v [i];

}(M);(i=0; i<koc; i++)(j=0; j<koc; j++)

{[i] [j] = 0.0;(k=0; k<M; k++)[i] [j] += Ma [k] [i] * Ma [k] [j];

}(i=0; i<koc; i++)[i] [i] += 1.0;(M);(i=0; i<M; i++)

{(k=0; k<M; k++)[i] [k] = P [i] [k];[i] = 0.0;(j=0; j<knn; j++)[i] += A [i] [Jnn [j]] * l [Jnn [j]];

}(M, Pr, Qb, &kod);(M);(kod)

{("\nОпорная матрица (ограничений) вырождена!!! \n");();

}(i=0; i<koc; i++)

{[i] = 0.0;(j=0; j<M; j++)[i] - = Ma [j] [i] * Qb [j];

}(koc);(i=0; i<koc; i++)(k=0; k<koc; k++)[i] [k] = D [i] [k];(koc, Pr, v, &kod);(koc);(kod)

{("\nОпорная матрица (цел. ф-ии) вырождена!!! \n");();

}

}(j=0; j<koc; j++)[Joc [j]] = v [j];(M);(i=0; i<M; i++)

{(j=0; j<M; j++)[i] [j] = P [i] [j];[i] = 0.0;(j=0; j<kn; j++)[i] - = A [i] [Jn [j]] * l [Jn [j]];

}(M, Pr, v, &kod);(M);(kod)

{("\nОпорная матрица (ограничений) вырождена!!! \n");();

}(j=0; j<M; j++)[Jop [j]] = v [j];(M);(i=0; i<M; i++)

{(k=0; k<M; k++)[i] [k] = P [k] [i];[i] = l [Jop [i]];

}(M, Pr, Qb, &kod);(M);(kod)

{("\nОпорная матрица (ограничений) вырождена!!! \n");();

}(j=0; j<knn; j++)

{[j] = l [Jnn [j]];(i=0; i<M; i++)[j] - = Qb [i] * A [i] [Jnn [j]];

}= 1;= - 1;(j=0; j<koc; j++)(l [Joc [j]] < - eps2)

{= (dn [Joc [j]] - x [Joc [j]]) / l [Joc [j]];(Thj < Th)

{= Thj;= j;= 0;

}

}(l [Joc [j]] > eps2)

{= (dw [Joc [j]] - x [Joc [j]]) / l [Joc [j]];(Thj < Th)

{= Thj;= j;= 0;

}

}(j=0; j<knn; j++)(Del [Jnn [j]] * v [j] < - eps1)

{= - Del [Jnn [j]] / v [j];(Thj < Th)

{= Thj;= j;= 1;

}

}(j=0; j<nz; j++)[j] += Th*l [j];(Th == 1)

{;

}(prTh)

{[koc] = Jnn [j0];++;-;(i=j0; i<knn; i++)[i] = Jnn [i+1];

}

{[knn] = Joc [j0];++;-;(i=j0; i<koc; i++)[i] = Joc [i+1];

}(M);(i=0; i<M; i++)

{(k=0; k<M; k++)[i] [k] = P [k] [i];[i] = x [Jop [i]];

}(M, Pr, v, &kod);(M);(kod)

{("\nОпорная матрица (ограничений) вырождена!!! \n");();

}(j=0; j<nz; j++)

{[j] = x [j];(i=0; i<M; i++)[j] - = v [i] * A [i] [j];

}++;

} // while (1)

}gs (int m, double **pX,copX [], int *kod)

{tol = 1E-5,bigpX, pXpX,;i, j, k, ky, imax,, jx, i0, ib;(j=0; j<m; j++)

{= fabs (pX [i] [j]);(fabs (bigpX) < pXpX)

{= pX [i] [j];= i;

}

}(fabs (bigpX) <= tol)

{

*kod = 1;1;

}(k=j; k<m; k++)

{= pX [imax] [k];[imax] [k] = pX [j] [k];[j] [k] = sav / bigpX;

}= copX [imax];[imax] = copX [j];[j] = sav / bigpX;(j==m-1);(ix=j+1; ix < m; ix++)

{(jx=j+1; jx < m; jx++)[ix] [jx] - = pX [ix] [j] * pX [j] [jx];[ix] - = copX [j] * pX [ix] [j];

}

}(ky=0; ky < m-1; ky++)

{= m-2-ky;= m-1;(k=0; k <= ky; k++)

{[ib] - = pX [ib] [i0] * copX [i0];--;

}

}

*kod=0;0;

}formParam (int nz)

{i, j;[1] [0] =1.8;[0] [0] =30.78;(j=1; j<nz; j++)

{[1] [j] =1.8;[0] [j] =A [0] [j-1] - 3.24;

}[0] =70;[1] =0;(i=0; i<nz; i++)

{[i] =-O;[i] = O;

}();("\n");t;(" Если хотите изменить, то нажмите 1=");("%d",&t);(t==1)();

} // formParamobrabotka (void)

{();nz=N;(nz);();= 1;(j=0; j<knn; j++)( ( (Del [Jnn [j]] < - eps1) &&

(fabs (x [Jnn [j]] - dn [Jnn [j]]) < eps2)) ||

( (Del [Jnn [j]] > eps1) &&

(fabs (x [Jnn [j]] - dw [Jnn [j]]) < eps2)))

{= 0;;

}(! UslSogl)(nz);= 1;(j=0; j<M; j++)( (x [Jop [j]] < dn [Jop [j]] - eps2) ||

(x [Jop [j]] > dw [Jop [j]] + eps2))

{= 0;;

}(UslOpt! = 0)

{clrscr ();("Псевдоплан оптимален!!!!");(0); }(! UslOpt)

{( (d = fopen ("dat", "wt")) == NULL)

{("dat");(-1);

}(koc);(j=0; j<koc; j++)

{(i=0; i<koc; i++)

{(k=0; k<koc; k++)[i] [k] = D [i] [k];[i] = 0.0;

}[j] = 1.0;(koc, Pr, v, &kod);(kod)

{("\nОпорная матрица (цел. ф-ии) вырождена!!! \n");();

}(i=0; i<koc; i++)[i] [j] = v [i];

}(koc);(d, "%d %d\n", M, nz);(j=0; j<nz; j++)

{(i=0; i<M; i++)(d, "%lf", A [i] [j]);(d, "\n");

}(i=0; i<M; i++)(d, "%lf", B [i]);(d, "\n");(i=0; i<nz; i++)(d, "%lf %lf\n", dn [i], dw [i]);(d, "%d\n", M);(i=0; i<M; i++)

{(j=0; j<M; j++)(d, "%lf", Q [i] [j]);(d, "\n");

}(d, "%d\n", koc);(j=0; j<koc; j++)(i=0; i<=j; i++)(d, "%lf\n", H [i] [j]);(i=0; i<M; i++)(d, "%d\n", Jop [i] + 1);(i=0; i<koc; i++)(d, "%d\n", Joc [i] + 1);(i=0; i<knn; i++)(d, "%d\n", Jnn [i] + 1);(j=0; j<nz; j++)(d, "%lf\n", x [j]);(d);("errfile. exe");("dmqp. exe");();("Результат: \n");( (r = fopen ("res", "r")) == NULL)

{("res");(-1);

}(r, "%d", &kod4);(kod4==0)

{("Jop = (");(r, "%d", &i);= i;(j=0; j<i; j++)

{(r, "%d", &k);[j] = k - 1;("%d", Jop [j]);

}(") \n");("Joc = (");(r, "%d", &i);+= i;(j=0; j<i; j++)

{(r, "%d", &k);[j] = k - 1;("%d", Joc [j]);

}(") \n");("Jnn = (");(j=0; j<nz-nn; j++)

{(r, "%d", &k);[j] = k - 1;("%d", Jnn [j]);

}(") \n");("x = (");(k=0; k<nz; k++)

{(r, "%lf", &xr);[k] = xr;("%7.3lf", x [k]);

}(") \n");();

}(r);

}

} // if (! UslOpt)

// }main (void)

{nom,kp=2,s;(3);(1)

{ clrscr ();=menu (kp,nazv);(s)

{1: obrabotka (); break;2: return;: { puts ("Смотри что вводишь");();

}

}

}

}