Методы оптимизации. Курсовая методы оптимизации. Курсовая работа по предмету Методы оптимизации

• Название: Курсовая работа по предмету Методы оптимизации
• Анкор: Методы оптимизации
• Дата: 06.04.2021
• Размер: 347.29 Kb.
• Имя файла: Курсовая методы оптимизации.docx
• Тип: Курсовая; #191900
• страница: 2 из 2

6. Список литературы

1. 
   А.А. Мицель, А.А. Шелестов «Методы оптимизации», учебное пособие, Томск, 2004
   
2. 
   Акулич И.Л. «Математическое программирование в примерах и задачах»: Учеб. пособие для студентов эконом. спец. вузов. – М.: Высш. шк., 1986. – 319 с., ил.
   

3. Банди Б. Методы оптимизации. Вводный курс: Пер. англ. М.:

Радио связь, 1998 -128 с.

4. Липаев В. В. Проектирование программных средств:

Учеб. пособие для вузов по спец. “Автом. сист. обр. информ. и упр.”.

– М.: Высш. шк., 1990.

5. Аттетков А.В., Галкин С.В., Зарубин В.С. Методы оптимизации: Учеб.

Для вузов. Под ред. В.С. Зарубина, А.П. Крищенко. – М.: Изд-во

МГТУ им. Баумана, 2001. - 440 с.


7. Приложение к заданию 1
Текст программы
uses crt;

const h_min=0.00001;

var h,x1,x2,x1_b,x2_b,x1_b_new,x2_b_new:real;
function f(x1,x2:real):real;

begin

f:= (x1*x1)+exp((x1*x1)+(x2*x2))+(4*x1)+(3*x2);

end;
begin

clrscr;

Write('Vvedite 1 koordinatu:');

Readln(x1_b);

Write('Vvedite 2 koordinatu:');

Readln(x2_b);

Write('Vvedite dlinu shaga h:');

Readln(h);

repeat

x1:=x1_b;

x2:=x2_b;

repeat

if f(x1+h,x2)
else if f(x1-h,x2)
else break;

until false;

repeat

if f(x1,x2+h)
else if f(x1,x2-h)
else break;

until false;

x1_b_new:=x1;

x2_b_new:=x2;

if (x1_b_new=x1_b)and(x2_b_new=x2_b)

then begin

h:=h/10; {}

if (h<=h_min) then begin

BREAK;

end;

end

else begin

x1_b:=x1_b_new;

x2_b:=x2_b_new;

end;

until false;

Writeln('x1=',x1_b:2:2);

Writeln('x2=',x2_b:2:2);

Writeln('f(x1,x2)=',f(x1_b,x2_b):2:2);

readln;

end.

8. Приложение к заданию 2
Текст программы
Program simplex_metod;

Uses crt;

Label zn,st,ell,_end;
type mas=array[1..30] of real;

masb=array[1..30] of string[3];

masx=array[1..30,1..30] of real;

Var fo,functpr,b,h,hnew,c,cnew,cpr,cprnew,fx:mas;

x,xnew:masx;

bs,bvsp,znac:masb;

min,i1,i,j,kx,ky,kit,nachkell,nachy,k_st:integer;

priznacy,klstr,klst,errcode,dop_x:integer;

p,p1,mo,f0,epsilon,z:real;

vsp,s,prgomory:string;

f:text;
dpx,dpy,fm,kell,kstr:integer;
{ функция создания индексов }
Function simvb(v:integer;s:char):string;

var m,z:string;

Begin

str(v,m);

z:=s+m;

simvb:=z;

End;
{ процедура записи данных в файл }
Procedure save(x1:real;k:string;mstr:integer);

Var v:string;

Begin

Assign(f,'simplex.dat');

Append(f);

Case mstr of

0:writeln(f,'');

1:begin

if k=' ' then str(x1:1:0,v) else str(x1:10:4,v);

write(f,v);

write(f,' ');

end;

2:write(f,k);

3:writeln(f,k);

End;

Close(f);

End;
{ определение дополнительных переменных }
Procedure dop_per;

begin

if znac[i1]='=' then

begin
kell:=kell+1;bvsp[kell]:=simvb(dpy,'y');

dpy:=dpy+1;

xnew[i1,kell]:=1;

if fm=1 then fx[kell]:=-1 else fx[kell]:=1;

functpr[kell]:=1;
for i:=1 to kstr do

if i<>i1 then xnew[i,kell]:=0;
end;
if znac[i1]='>=' then

begin
kell:=kell+1;bvsp[kell]:=simvb(dpx,'x');

dpx:=dpx+1;dop_x:=dop_x+1;

xnew[i1,kell]:=-1;fx[kell]:=0;
for i:=1 to kstr do

if i<>i1 then xnew[i,kell]:=0;
kell:=kell+1;bvsp[kell]:=simvb(dpy,'y');

dpy:=dpy+1;

xnew[i1,kell]:=1;
if fm=1 then fx[kell]:=-1 else fx[kell]:=1;

functpr[kell]:=1;
for i:=1 to kstr do

if i<>i1 then xnew[i,kell]:=0;
end;
if znac[i1]='<=' then

begin
kell:=kell+1;bvsp[kell]:=simvb(dpx,'x');

dpx:=dpx+1;dop_x:=dop_x+1;

xnew[i1,kell]:=1;fx[kell]:=0;
for i:=1 to kstr do

if i<>i1 then xnew[i,kell]:=0;
end;
end;
{ процедура сокращения y }
Procedure sokr;

Var p:integer;

begin

kell:=kell-1;

for p:=nachkell+dop_x to kell do

if bvsp[p]=bs[klstr] then begin

for j:=p to kell do

bvsp[j]:=bvsp[j+1];

functpr[j]:=functpr[j+1];

fx[j]:=fx[j+1];

for i:=1 to kstr do

xnew[i,j]:=xnew[i,j+1]

end;

end;
{ процедура, выполняющая метод гомори }
Procedure gomory;

Var max,z:real;

Begin

klstr:=1;

max:=h[1]-int(h[1]);

for i1:=2 to kstr do

if (h[i1]-int(h[i1]))>=max then begin max:=h[i1]; klstr:=i1;end;

kstr:=kstr+1;

hnew[kstr]:=h[klstr]-int(h[klstr]);

for i1:=1 to kell do

begin

z:=int(x[klstr,i1]);

if x[klstr,i1]<0 then z:=z-1;

xnew[kstr,i1]:=x[klstr,i1]-z;

end;

Znac[kstr]:='>=';

End;
{ процедура, выполняющая симплекс метод }
Procedure simplex;
label povznac,nach;

Begin
{ подготовка к вводу данных }
Nachkell:=kell;

Dpx:=kell+1;dpy:=1;

Kx:=1;ky:=4;

Epsilon:=0.00001;

Clrscr;

Writeln('введите систему уравнений:');

Writeln('(коэффициенты при всех х,знак и свободные члены)');
{ ввод данных }
for i:=1 to kstr do

begin

Povznac:

writeln('введите ',i,'-е уравнение:');
{ ввод коэффициентов при x в i-том уравнении }
for j:=1 to kell do

begin

gotoxy(kx,ky);kx:=kx+6;

readln(xnew[i,j]);

end;
{ ввод знака в i-том уравнении }
kx:=kx+6;gotoxy(kx,ky);readln(znac[i]);


{проверка введенного знака на правильность}
if (znac[i]<>'>=') and (znac[i]<>'=') and (znac[i]<>'<=')

then begin

writeln('неправильно задан знак');

ky:=ky+3;kx:=1;

goto povznac;

end;
if (znac[i]='=') or (znac[i]='>=') then priznacy:=1;
{ ввод свободного члена в i-том уравнении }
kx:=kx+6;gotoxy(kx,ky);read(b[i]);

kx:=1;

ky:=ky+2;
end;
Writeln('введите коэффициенты при х в целевой функции:');
{ ввод коэффициентов при х в целевой функции }
for j:=1 to kell do

begin

gotoxy(kx,ky);kx:=kx+6;

read(fx[j]);

end;

{ подготовка индексации x }
For j:=1 to kell do

bvsp[j]:=simvb(j,'x');
{ определение дополнительных переменных }
For i1:=1 to kstr do

dop_per;
{ замена оптимальной функции с max на min при наличии

в базисе y-ков если идет исследование на минимум }
Min:=0;

If (fm=1) and (priznacy=1) then

begin

min:=fm;fm:=2;

for j:=1 to kell do

fx[j]:=-fx[j];

end;
{ сортировка дополнительных переменных по индексу }
For i1:=nachkell+1 to kell do

for j:=i1+1 to kell do

if bvsp[j]
begin

vsp:=bvsp[j];bvsp[j]:=bvsp[i1];bvsp[i1]:=vsp;

p:=fx[j];fx[j]:=fx[i1];fx[i1]:=p;

p:=functpr[j];functpr[j]:=functpr[i1];functpr[i1]:=p;

for i:=1 to kstr do

begin

p:=xnew[i,i1];xnew[i,i1]:=xnew[i,j];xnew[i,j]:=p;

end;

end;

Kit:=1;

Clrscr;
{ подготовка столбцов c,b,h }
for i:=1 to kstr do

begin

hnew[i]:=b[i];

for j:=nachkell+1 to kell do

if xnew[i,j]=1 then

begin

bs[i]:=bvsp[j];

cnew[i]:=fx[j];

cprnew[i]:=functpr[j];

end;

end;
Nach:;
Repeat
Priznacy:=0;
{ передача данных в исходные переменные c обнулением чисел,

по модулю меньших чем 0.00001 }
For i:=1 to kstr do

begin

if int(10000*hnew[i])=0 then h[i]:=+0 else h[i]:=hnew[i];

c[i]:=cnew[i];

cpr[i]:=cprnew[i];

if bs[i][1]='y' then priznacy:=1;

for j:=1 to kell do

if int(10000*xnew[i,j])=0 then x[i,j]:=+0 else x[i,j]:=xnew[i,j];

end;
{ обнуление и вывод индексации элементов индексной строки }
Save(0,' c б h ',2);

For j:=1 to kell do

begin

save(0,bvsp[j],2);

p1:=length(bvsp[j]);

if p1=2 then save(0,' ',2);

save(0,' ',2);

fo[j]:=0;

end;

save(0,'',0);
{ вывод симплекс-таблицы }
P1:=0;

For i:=1 to kstr do

begin
if cpr[i]=1 then

if c[i]<0 then save(0,'-m ',2)

else save(0,'+m ',2)

else save(c[i],'',1);
save(0,bs[i],2);

p1:=length(bs[i]); if p1=2 then save(0,' ',2);

save(0,' ',2);save(h[i],'',1);
for j:=1 to kell do

save(x[i,j],'',1);

save(0,'',0);

end;
{ вычисление значений в индексной строке }
F0:=0;

For j:=1 to kell do

fo[j]:=0;
For i1:=1 to kstr do

begin

if priznacy=1 then

if bs[i1][1]='y' then

begin

f0:=f0+h[i1];

for j:=1 to kell do

fo[j]:=fo[j]+x[i1,j];

end;

if priznacy=0 then

begin

f0:=f0+h[i1]*c[i1];

for j:=1 to kell do

fo[j]:=fo[j]+c[i1]*x[i1,j];

end;
For j:=1 to kell do

if bvsp[j][1]='y' then fo[j]:=+0

else if abs(fo[j])
end;
{ вывод значений целевой функции }
Save(0,' ',2);save(f0,'',1);

For j:=1 to kell do

begin
if priznacy<>1 then fo[j]:=fo[j]-fx[j];

save(fo[j],'',1);
end;

Save(0,'',0);
{ проверка условия оптимальности }
P:=0;

For j:=1 to kell do

if fm=1 then if fo[j]<-epsilon then

begin

p:=1;

continue;

end else

else if fo[j]>epsilon then

begin

p:=1;

continue;

end;
If p<>1 then

begin
save(0,'в ',2);save(kit,' ',1);

save(0,'-й итерации было получено оптимальное решение',3);

save(0,'т.к. При исследовании на ',2);

if fm=1 then

save(0,'максимум индексная строка не содержит отицательных элементов.',3)

else

save(0,'минимум индексная строка не содержит положительных элементов.',3);
for i1:=1 to kstr do

if bs[i1][1]='y' then

begin

save(0,'но т.к. Из базиса не выведены все y, то ',3);

save(0,'можно сделать вывод, что решений нет',3);

halt;

end;
{ округление значений массива х до целого числа,

если разность округленного и обычного значений

по модулю меньше чем 0.00001 }
For i:=1 to kstr do

begin

z:=round(h[i]);

if abs(z-h[i])
for j:=1 to kell do

begin

if x[i,j]<0 then z:=round(x[i,j]);

if abs(z-x[i,j])
end;

end;
{ проверка целочисленности решения }
P1:=0;

For i:=1 to kstr do

begin

if int(10000*frac(h[i]))<>0 then begin p1:=1;continue; end;
for j:=1 to kell do

if bs[i]=bvsp[j] then

for i1:=1 to kstr do

if abs(frac(x[i1,j]))>=epsilon then begin p1:=1;continue; end;
end;
{ составление новой базисной строки для целочисленного решения }
if (prgomory='y') and (p1=1) then

begin

gomory;

nachkell:=kell;

i1:=kstr;dpy:=1;

dop_per;

bs[kstr]:=bvsp[kell];

cprnew[kstr]:=functpr[kell];

cnew[kstr]:=fx[kell];

goto nach;

end;
if p1=0 then save(0,'данное решение является целочисленым.',3);
save(0,'при этом:',3);

if min=1 then begin f0:=-f0;fm:=min; end;

if fm=1 then

save(0,'fmax=',2)

else

save(0,'fmin=',2);
save(f0,'',1);

save(0,'',0);

for i1:=1 to kstr do

begin

save(0,' ',2);

save(0,bs[i1],2);save(0,'=',2);

save(h[i1],'',1);

save(0,'',0);

end;

halt;
end;
{ нахождение ключевого столбца }
Klst:=1;mo:=0;

For j:=1 to kell do

if fm=1 then

if fo[j]For j:=1 to kell do

begin

if bvsp[j][1]<>'y' then

if fm=1 then

begin

if fo[j]<0 then

if fo[j]>=mo then

begin

mo:=fo[j]; klst:=j;

end;

end

else

begin

if fo[j]>0 then

if fo[j]>=mo then

begin

mo:=fo[j]; klst:=j;

end;

end;

end;
save(0,'ключевой столбец: ',2);save(klst,' ',1);
{ нахождение ключевой строки }
P1:=0;k_st:=0;

For j:=1 to kell do

if abs(mo-fo[j])
begin

k_st:=k_st+1;

for i:=1 to kstr do

if x[i,klst]>0 then begin b[i]:=h[i]/x[i,klst]; p:=b[i];klstr:=i; end

else begin b[i]:=-1; p1:=p1+1; end;

end;
If p1=kstr*k_st then

begin

save(0,'',0);

save(0,'решений нет т.к. Невозможно определить ключевую строку',3);

halt;

end;
P1:=0;

For j:=1 to kell do

if abs(mo-fo[j])
for i:=1 to kstr do

if b[i]>=0 then begin

if b[i]
bs[i] then begin p:=b[i]; klstr:=i; end;
if int(10000*b[i])=int(10000*p) then

if (bs[i][1]='y') and (bs[klstr][1]='x') then

if bvsp[klst]<>bs[i] then begin p:=b[i]; klstr:=i; end;

end;
Save(0,'ключевая строка: ',2);save(klstr,' ',1);

Save(0,'',0);
For i:=1 to kstr do

if bvsp[klst]=bs[i] then

begin

save(0,'решений нет т.к. В базисном столбце уже есть ',3);

save(0,'такая переменная.',3);

halt;

end;
{ вызов процедуры сокращения y }
If cpr[klstr]=1 then sokr;

{ построение следующей симплекс-таблицы }
Bs[klstr]:=bvsp[klst];

Cnew[klstr]:=fx[klst];

Cprnew[klstr]:=functpr[klst];
For i:=1 to kstr do

begin

if i=klstr then hnew[i]:=h[i]/x[klstr,klst]

else hnew[i]:=h[i]-(h[klstr]*x[i,klst]/x[klstr,klst]);

for j:=1 to kell do

begin
if (i=klstr) and (j=klst) then xnew[i,j]:=1;
if (i=klstr) and (j<>klst) then xnew[i,j]:=x[i,j]/x[klstr,klst];
if (i<>klstr) and (j=klst) then xnew[i,j]:=0;
if (i<>klstr) and (j<>klst) then

xnew[i,j]:=x[i,j]-(x[klstr,j]*x[i,klst]/x[klstr,klst]);
end;

end;

Klst:=0;klstr:=0;

Kit:=kit+1;

Until (kit=0);
End;
{ основная программа }
Begin

Clrscr;

Kit:=0;dop_x:=0;

Assign(f,'simplex.dat');

Rewrite(f);

Close(f);
St:;
write('введите кол-во строк:');readln(kstr);

if kstr>10 then

begin

writeln('программа не расчитана на введенное кол-во строк!');

goto st;

end;
Ell:
write('введите кол-во элементов:');readln(kell);

if kell>10 then

begin

writeln('программа не расчитана на введенное кол-во элементов!');

goto ell;

end;
Zn:
write('исследуем на максимум(1) или минимум(2):');readln(fm);

if (fm<>1) and (fm<>2) then

begin

writeln('введите снова');goto zn;

end;

write('целочисленное решение(y/n): ');readln(prgomory);

if (prgomory='y') or (prgomory='y') then prgomory:='y' else prgomory:='n';
{ вызов процедуры simplex}
Simplex;
End.