Двоїстість в оптимізаційних задачах
Застосування теорії двоїстості для задач лінійного та нелінійного програмування, теореми двоїстості. Симплексний метод як метод отримання розв’язку прямої та двоїстої задачі. Постановка економіко-математичної задачі із застосуванням теорії двоїстості.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | украинский |
| Дата добавления | 08.03.2015 |
| Размер файла | 567,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
var s:string;
begin
s:=SGRD_A.Cells[j, i];
if s='=' then ReadZnak:=0
else
if ((s='<') or (s='<=')) then ReadZnak:=1
else
if ((s='>') or (s='>=')) then ReadZnak:=2
else
begin
SGRD_A.Cells[j, i]:='';
ReadZnak:=-1;
ERROR:=true;
ShowMessage('Неправильний ввід знаку у нерівності ' + IntToStr(i-1));
end;
end;
function TForm1.ReadReal_A(i,j:integer):real;
var is_error: boolean;
begin
is_error:=false;
if SGRD_A.Cells[j, i]='' then
begin
SGRD_A.Cells[j, i]:='0';
ReadReal_A:=0;
end
else
begin
try
StrToFloat(SGRD_A.Cells[j, i]);
except
is_error:=true;
SGRD_A.Cells[j, i]:='0';
ERROR:=true;
if i=1 then ShowMessage('Неправильний ввід коефіцієнта ЦФ біля Х' + IntToStr(j))
else
if j=n+2 then ShowMessage('Неправильний ввід коефіцієнта B' + IntToStr(i))
else
ShowMessage('Неправильний ввід коефіцієнта біля Х'+IntToStr(j)+' рівняння '+IntToStr(i-1))
end;
if is_error then ReadReal_A:=0
else ReadReal_A:=StrToFloat(SGRD_A.Cells[j, i]);
end;
end;
procedure TForm1.BtnRozmiryEnterClick(Sender: TObject);
var i:integer;
is_error:boolean;
begin
N4.Enabled:=true; // Робимо доступним пункт меню "Зчитати дані"
N2.Enabled:=false;
STB2.Visible:=false;
is_error:=false;
try
StrToInt(Edit_N.Text);
except
Edit_N.Text:='1';
is_error:=true;
ShowMessage('Неправильний ввід кількості змінних');
end;
try
StrToFloat(Edit_M.Text);
except
Edit_N.Text:='1';
is_error:=true;
ShowMessage('Неправильний ввід кількості рядків');
end;
if not is_error then
begin
//Заблокуємо для редактування поля введення розмірів ЗЛП
Edit_N.Enabled:=false;
Edit_M.Enabled:=false;
CBox_EXTREMUM.Enabled:=false;
BtnRozmiryEnter.Enabled:=false;
//Зчитаємо розміри ЗЛП
n:=StrTOInt(Edit_N.Text);
m:=StrTOInt(Edit_M.Text);
if CBox_EXTREMUM.ItemIndex=1 then extremum_max:=false
else extremum_max:=true;
//Побудова поля введення коефіцієнтів ЗЛП
Panel_A.Visible:=true;
Panel_A.Width:=Form1.Width div 2;
PanelDUO.Width:=Form1.Width div 2;
SGRD_A.Enabled:=true;
SGRD_A.RowCount:=m+3;
SGRD_A.ColCount:=n+3;
for i := 1 to n do
begin
SGRD_A.Cells[i,0]:='X' + IntTOStr(i);
SGRD_A.Cells[i,m+2]:='+';
end;
SGRD_A.Cells[n+1,0]:='знак';
SGRD_A.Cells[n+2,0]:='B';
SGRD_A.Cells[0,1]:='ЦФ';
SGRD_A.Cells[n+1,1]:='Х';
SGRD_A.Cells[n+2,1]:='Х';
for i := 2 to m+1 do
SGRD_A.Cells[0, i]:='(' + IntTOStr(i-1) + ')';
SGRD_A.Cells[0,m+2]:='Xj>0 (+,-)';
end;
end;
procedure TForm1.btn_BuildDuoClick(Sender: TObject);
var i,j:integer;
first_el:boolean;
s:string;
begin
//припустимо відсутність помилок вводу
ERROR:=false;
// Задання розміру масиву коефіцієнтів матриці А
SetLength(A, m+1, n+1);
// Задання розміру масиву коефіцієнтів ЦФ - С, та вектора вільних членів - В
SetLength(C, n+1);
SetLength(B, m+1);
SetLength(Znak, m+1);
SetLength(X_nevid, n+1);
//Зчитування вектора С
for j := 1 to n do
C[j]:= ReadReal_A(1,j);
//зчитування матриці А
for i := 1 to m do
for j := 1 to n do
A[i,j]:= ReadReal_A(i+1,j);
//Зчитування вектора B
for i := 1 to m do
B[i]:= ReadReal_A(i+1,n+2);
//Зчитування знаків нерівностей обмежень
for i := 1 to m do
Znak[i]:= ReadZnak(i+1,n+1);
//Зчитування обмежень на невід'ємність змінних
for j := 1 to n do
if SGRD_A.Cells[j,m+2]='+' then
X_nevid[j]:= true
else X_nevid[j]:= false;
// Побудова двоїстої задачі при відсутності помилок
if not ERROR then
begin
// Зміни в доступності пунктів меню
N_PZ_Standart.Enabled:=true;
N_DZ_standart.Enabled:=true;
N4.Enabled:=false;
// Зробимо видимою панель виводу результатів
PanelDUO.Visible:=true;
SGRD_A.Enabled:=false;
MemoDUO.Lines.Clear;
MemoDUO.Lines.Add(' Введена задача:');
//Вивід ЦФ прямої задачі
first_el := true;
for j := 1 to n do
if C[j]<>0 then
begin
if not first_el then
begin
if C[j]>0 then s:=s+ ' + '
else s:=s+ ' - ';
end
else
begin
first_el:=false;
if C[j]<0 then s:=s+ '-';
end;
s:=s + FloatToStr(Abs(C[j])) + ' X' + FloatToStr(j);
end;
s:=s+' -> ';
if extremum_max then s:=s + 'max'
else s:=s + 'min';
MemoDUO.Lines.Add(s);
//вивід обмежень прямої задачі
for i := 1 to m do
begin
s:='';
first_el := true;
for j := 1 to n do
if A[i,j]<>0 then
begin
if not first_el then
begin
if A[i,j]>0 then s:=s+ ' + '
else s:=s+ ' - ';
end
else
begin
first_el:=false;
if A[i,j]<0 then s:=s+ '-';
end;
s:=s + FloatToStr(ABS(A[i,j])) + ' X' + IntToStr(j);
end;
case Znak[i] of
0:s:=s+' = ';
1:s:=s+' <= ';
2:s:=s+' >= ';
end;
s:=s + FloatToStr(B[i]);
MemoDUO.Lines.Add(s);
end;
// вивід обмежень на невід'ємність змінних
s:='';
first_el := true;
for j := 1 to n do
if X_nevid[j] then
begin
if not first_el then
begin
s:=s+ ', ';
end
else first_el:=false;
s:=s + ' X' + IntToStr(j);
end;
s:=s+' >=0 ';
MemoDUO.Lines.Add(s);
end;
end;
procedure TForm1.FormResize(Sender: TObject);
begin
Panel_A.Width:=Form1.Width div 2;
PanelDUO.Width:=Form1.Width div 2;
end;
procedure TForm1.N2Click(Sender: TObject);
begin
BtnRozmiryEnterClick(Sender);
end;
procedure TForm1.N3Click(Sender: TObject);
begin
Close();
end;
procedure TForm1.N4Click(Sender: TObject);
begin
btn_BuildDuoClick(Sender);
end;
procedure TForm1.N_PSM_DZClick(Sender: TObject);
label 1;
var djmin, iter,i,j,ky,kz,nst,npk,ind,isb,isM, roz_s, roz_r, npk0, minus,
iii,n2,m2:integer;
djmin_z,djM, djmin_c, c_, mina:real;
C_dz,B_dz: array of real;
A_dz: array of array of real;
Znak_dz: array of integer; { масив знаків нерівностей обмежень
0 - рівне (=)
1 - менше рівне (<=)
2 - більше рівне (>=)}
begin
SetLength(A_dz, n+1,m+1);
SetLength(C_dz, m+1);
SetLength(B_dz, n+1);
SetLength(Znak_dz, n+1);
n2:=m;
m2:=n;
for i := 1 to n2 do
for j := 1 to m2 do
A_dz[i,j]:=A[j,i];
for i := 1 to m2 do
begin
B_dz[i]:=C[i];
if X_nevid[i] then Znak_dz[i]:=2
else Znak_dz[i]:=0;
end;
for j := 1 to n2 do
C_dz[j]:=B[j];
with STB2 do
begin
visible:=true;
iter:=0;
colcount:=n2+3;
rowcount:=m2+3;
if n2<10 then Width:=65*(n2+3)
else Width:=65*12+16;
if m2<14 then Height:=25*(m2+3)
else Height:=25*16+16;
cells[0,0]:='Початкова';
cells[1,0]:='таблиця';
cells[0,1]:='Cjб';
cells[1,1]:='Xjб';
cells[2,1]:='Bi';
cells[2,0]:='Cj';
cells[0,m2+2]:='індексний';
cells[1,m2+2]:='рядок';
for j:=1 to n2 do
begin
cells[j+2,1]:='x' + IntToStr(j);
if extremum_max then minus:=1 else minus:=-1;
cells[j+2,0]:=FloatToStr(minus*C_dz[j]);
end;
{сама табличка}
for j:=1 to n2 do
for i:=1 to m2 do
cells[j+2,i+1]:=FloatToStr(A_dz[i,j]);
{вектор B}
for i:=1 to m2 do
begin
cells[2,i+1]:=FloatToStr(B_dz[i]);
if B_dz[i]<0 then
begin
for j:=0 to n2 do
cells[2+j,i+1]:=FloatTostr(-StrToFloat(cells[2+j,i+1]));
if Znak[i]=1 then Znak[i]:=2
else if Znak[i]=2 then Znak[i]:=1;
end;
end;
{зведення до канонічного вигляду}
ky:=0;
kz:=0;
nst:=n2;
for i:=1 to m2 do
begin
if (Znak[i]=1)then
begin
ky:=ky+1;
n2:=n2+1;
colcount:=n2+3;
if n2<12 then Width:=65*(n2+3)
else Width:=65*14+16;
cells[n2+2,0]:='0';
cells[n2+2,1]:='"y'+IntToStr(ky);
for j:=1 to m2 do
if (j<>i) then cells[n2+2,j+1]:='0'
else cells[n2+2,j+1]:='1';
cells[0,i+1]:='0';
cells[1,i+1]:=cells[n2+2,1];
end;
if (Znak[i]=2)then
begin
ky:=ky+1;
n2:=n2+1;
colcount:=n2+3;
if n2<12 then Width:=65*(n2+3)
else Width:=65*14+16;
cells[n2+2,0]:='0';
cells[n2+2,1]:='"y'+IntToStr(ky);
for j:=1 to m2 do
if (j<>i) then cells[n2+2,j+1]:='0'
else cells[n2+2,j+1]:='-1';
Znak[i]:=0;
end;
end;
for i:=1 to m2 do
if (Znak[i]=0)then
begin
kz:=kz+1;
n2:=n2+1;
colcount:=n2+3;
if n2<12 then Width:=65*(n2+3)
else Width:=65*14+16;
cells[n2+2,0]:='-M';
cells[n2+2,1]:='"Z'+IntToStr(kz);
for j:=1 to m2 do
if (j<>i) then cells[n2+2,j+1]:='0'
else cells[n2+2,j+1]:='1';
cells[0,i+1]:='-M';
cells[1,i+1]:=cells[n2+2,1];
end;
npk:=1;
ind:=1;
while ind=1 do
begin
{заповнює індексний рядок}
isM:=0;
For i:= 1 To m2 do
If cells[0,npk + i]='-M' Then isM:= 1;
If isM=0 Then
begin
//memo1.Lines.Add('вітка без М');
For j:=2 To (n2+2)do
if cells[j,0]<>'-M' then
begin
If j=2 Then c_:=0
Else c_:=-StrToFloat(Cells[j,0]);
For i:=1 To m2 do
c_:=c_+StrToFloat(Cells[0,npk+i])*StrToFloat(Cells[j,npk+i]);
Cells[j,npk+m2+1]:=FloatToStr(roundto(c_,-3));
if j=3 then begin djmin_z:=c_; djmin:=j; end;
if (j>3)and(c_<djmin_z) then
begin djmin:=j; djmin_z:=c_; end;
end
else Cells[j,npk+m2+1]:='-';
end
Else
begin {isM=1}
For j:=2 To (n2+2) do
if cells[j,0]<>'-M' then
Begin
djm:=0;
If j=2 Then c_:=0
Else c_:=-StrToFloat(Cells[j,0]);
For i:=1 To m2 do
If Cells[0,npk+i]<>'-M' Then
c_:=c_+StrToFloat(Cells[0,npk + i])*StrToFloat(Cells[j,npk + i])
else djm:=djm-StrToFloat(Cells[j,npk+i]);
if djM=0 then Cells[j,npk + m2+1]:=FloatToStr(roundto(c_,-3))
Else
begin
if c_<0 then Cells[j,npk + m2+1]:=FloatToStr(roundto(djm,-3))+'M'+FloatToStr(roundto(c_,-3));
if c_=0 then Cells[j,npk + m2+1]:=FloatToStr(roundto(djm,-3))+'M';
if c_>0 then Cells[j,npk + m2+1]:=FloatToStr(roundto(djm,-3))+'M+'+FloatToStr(roundto(c_,-3));
end;
if j=3 then begin djmin_z:=djm; djmin_c:=c_; djmin:=j; end;
if (j>3)and((djM<djmin_z)or((djM=djmin_z)and(c_<djmin_c))) then
begin djmin_z:=djm; djmin_c:=c_; djmin:=j; end;
end
else Cells[j,npk + m2+1]:='0';
{next j}
End; {isM=1}
if isM=1 then
if (djmin_z>0)or((djmin_z=0)and(djmin_c>=0)) then
begin
ShowMessage('Функція не має розв"язку через несумісність умов');
goto 1;
end;
if (isM=0)and(djmin_z>=0) then
begin
//виведення результатів
MemoDUO.Lines.Add('');
MemoDUO.Lines.Add('Оптимальний план Двоїстої задачі:');
for iii := 1 to m2 do
MemoDUO.Lines.Add(Cells[1, npk+iii]+ ' = ' + Cells[0, npk+iii]);
MemoDUO.Lines.Add('Оцінки двоїстої задачі:');
for iii := 1 to n2 do
MemoDUO.Lines.Add('d' + Cells[iii+2,1] + ' = ' + Cells[iii+2, npk+m2+1]);
ShowMessage('План оптимальний');
goto 1;
end;
roz_s:=djmin;
ind:=1;
{розв'язковий рядок}
isb:=0;
i:=1;
roz_r:=0;
While ((isb=0) And (i<=m2)) do
begin
If StrToFloat(Cells[roz_s,npk+i])>0 Then
begin
isb:=1;
mina:=StrToFloat(Cells[2,npk+i])/StrToFloat(Cells[roz_s,npk+i]);
roz_r:=i;
end;
i:=i+1;
end;
If isb=0 Then begin showmessage('Функція необмежена'); goto 1; end;
For i:=1 To m2 do
If ((StrToFloat(Cells[roz_s,npk+i])>0)And(isM=0)) Or ((StrToFloat(Cells[roz_s,npk+i])>0)And(isM=1)And(Cells[0,npk+i]='-M')) Then
If (StrToFloat(Cells[2,npk+i])/StrToFloat(Cells[roz_s,npk+i]))<=mina Then
begin
mina:=StrToFloat(Cells[2,npk+i])/StrToFloat(Cells[roz_s,npk+i]);
roz_r:=i;
end;
roz_r:=roz_r+npk;
npk0:=npk;
npk:=npk+m2+2;
{переписуємо і міняємо базову змінну}
rowcount:=npk+m2+2;
if cells[0,roz_r]='-M' then
for j:=1 to n2 do
if (cells[1,roz_r]=cells[j+2,1]) then cells[j+2,npk]:='вибула';
for j:=1 to n2 do
if (cells[j+2,npk0]='вибула') then cells[j+2,npk]:='вибула';
if (npk+m2<14) then Height:=25*(npk+m2+2)
else
begin
height:=13*25;
width:=width+18;
end;
For i:=1 To (m+1) do
If (npk0+i=roz_r) Then
begin
Cells[1,npk+i]:=Cells[roz_s,1];
Cells[0,npk+i]:=Cells[roz_s,0]
end
Else
begin
Cells[1,npk+i]:=Cells[1,npk0+i];
Cells[0,npk+i]:=Cells[0,npk0+i];
end;
iter:=iter+1;
cells[0,npk0+m2+2]:='ітер '+inttostr(iter);
cells[1,npk0+m2+2]:='р.ел ('+Inttostr(roz_r-npk0)+';'+Inttostr(roz_s-2)+')';
{заповнюємо симплекс табличку}
For j:=0 To n2 do
if cells[j+2,npk]<>'вибула' then
begin
For i:=1 To m2 do
If (npk0+i=roz_r) Then
Cells[j+2,npk+i]:=FloatToStr(roundto(StrToFloat(Cells[j+2,npk0+i])/StrToFloat(Cells[roz_s,roz_r]),-3))
Else
Cells[j+2,npk+i]:=FloatToStr(roundto(StrToFloat(Cells[j+2,npk0+i])-StrToFloat(Cells[roz_s,npk0+i])*StrToFloat(Cells[j+2,roz_r])/StrToFloat(Cells[roz_s,roz_r]),-3));
end
else For i:=1 To m2 do Cells[j+2,npk+i]:='-';
end;
end;
1:end;
procedure TForm1.N_PSMClick(Sender: TObject);
label 1;
var djmin, iter,i,j,ky,kz,nst,npk,ind,isb,isM, roz_s, roz_r, npk0, minus,
iii,n2:integer;
djmin_z,djM, djmin_c, c_, mina:real;
Znak_pz : array of integer;
begin
n2:=n;
SetLength(Znak_pz, m+1);
for i := 1 to m do Znak_pz[i]:=Znak[i];
with STB2 do
begin
visible:=true;
iter:=0;
colcount:=n2+3;
rowcount:=m+3;
if n<10 then Width:=65*(n2+3)
else Width:=65*12+16;
if m<14 then Height:=25*(m+3)
else Height:=25*16+16;
cells[0,0]:='Початкова';
cells[1,0]:='таблиця';
cells[0,1]:='Cjб';
cells[1,1]:='Xjб';
cells[2,1]:='Bi';
cells[2,0]:='Cj';
cells[0,m+2]:='індексний';
cells[1,m+2]:='рядок';
for j:=1 to n2 do
begin
cells[j+2,1]:='x' + IntToStr(j);
if extremum_max then minus:=1 else minus:=-1;
cells[j+2,0]:=FloatToStr(minus*C[j]);
end;
{сама табличка}
for j:=1 to n2 do
for i:=1 to m do
cells[j+2,i+1]:=FloatToStr(A[i,j]);
{вектор B}
for i:=1 to m do
begin
cells[2,i+1]:=FloatToStr(B[i]);
if B[i]<0 then
begin
for j:=0 to n2 do
cells[2+j,i+1]:=FloatTostr(-StrToFloat(cells[2+j,i+1]));
if Znak_pz[i]=1 then Znak[i]:=2
else if Znak_pz[i]=2 then Znak_pz[i]:=1;
end;
end;
{зведення до канонічного вигляду}
ky:=0;
kz:=0;
nst:=n2;
for i:=1 to m do
begin
if (Znak_pz[i]=1)then
begin
ky:=ky+1;
n2:=n2+1;
colcount:=n2+3;
if n2<12 then Width:=65*(n2+3)
else Width:=65*14+16;
cells[n2+2,0]:='0';
cells[n2+2,1]:='"y'+IntToStr(ky);
for j:=1 to m do
if (j<>i) then cells[n2+2,j+1]:='0'
else cells[n2+2,j+1]:='1';
cells[0,i+1]:='0';
cells[1,i+1]:=cells[n2+2,1];
end;
if (Znak_pz[i]=2)then
begin
ky:=ky+1;
n2:=n2+1;
colcount:=n2+3;
if n2<12 then Width:=65*(n2+3)
else Width:=65*14+16;
cells[n2+2,0]:='0';
cells[n2+2,1]:='"y'+IntToStr(ky);
for j:=1 to m do
if (j<>i) then cells[n2+2,j+1]:='0'
else cells[n2+2,j+1]:='-1';
Znak_pz[i]:=0;
end;
end;
for i:=1 to m do
if (Znak_pz[i]=0)then
begin
kz:=kz+1;
n2:=n2+1;
colcount:=n2+3;
if n2<12 then Width:=65*(n2+3)
else Width:=65*14+16;
cells[n2+2,0]:='-M';
cells[n2+2,1]:='"Z'+IntToStr(kz);
for j:=1 to m do
if (j<>i) then cells[n2+2,j+1]:='0'
else cells[n2+2,j+1]:='1';
cells[0,i+1]:='-M';
cells[1,i+1]:=cells[n2+2,1];
end;
npk:=1;
ind:=1;
isb:=1;
while ind=1 do
begin
{заповнює індексний рядок}
isM:=0;
For i:= 1 To m do
If cells[0,npk + i]='-M' Then isM:= 1;
If isM=0 Then
begin
For j:=2 To (n2+2)do
if cells[j,0]<>'-M' then
begin
If j=2 Then c_:=0
Else c_:=-StrToFloat(Cells[j,0]);
For i:=1 To m do
c_:=c_+StrToFloat(Cells[0,npk+i])*StrToFloat(Cells[j,npk+i]);
Cells[j,npk+m+1]:=FloatToStr(roundto(c_,-3));
if j=3 then begin djmin_z:=c_; djmin:=j; end;
if (j>3)and(c_<djmin_z) then
begin djmin:=j; djmin_z:=c_; end;
end
else Cells[j,npk+m+1]:='-';
end
Else
begin {isM=1}
For j:=2 To (n2+2) do
if cells[j,0]<>'-M' then
Begin
djm:=0;
If j=2 Then c_:=0
Else c_:=-StrToFloat(Cells[j,0]);
For i:=1 To m do
If Cells[0,npk+i]<>'-M' Then
c_:=c_+StrToFloat(Cells[0,npk + i])*StrToFloat(Cells[j,npk + i])
else djm:=djm-StrToFloat(Cells[j,npk+i]);
if djM=0 then Cells[j,npk + m+1]:=FloatToStr(roundto(c_,-3))
Else
begin
if c_<0 then Cells[j,npk + m+1]:=FloatToStr(roundto(djm,-3))+'M'+FloatToStr(roundto(c_,-3));
if c_=0 then Cells[j,npk + m+1]:=FloatToStr(roundto(djm,-3))+'M';
if c_>0 then Cells[j,npk + m+1]:=FloatToStr(roundto(djm,-3))+'M+'+FloatToStr(roundto(c_,-3));
end;
if j=3 then begin djmin_z:=djm; djmin_c:=c_; djmin:=j; end;
if (j>3)and((djM<djmin_z)or((djM=djmin_z)and(c_<djmin_c))) then
begin djmin_z:=djm; djmin_c:=c_; djmin:=j; end;
end
else Cells[j,npk + m+1]:='0';
{next j}
End; {isM=1}
if isM=1 then
if (djmin_z>0)or((djmin_z=0)and(djmin_c>=0)) then
begin
ShowMessage('Функція не має розв"язку через несумісність умов');
goto 1;
end;
if (isM=0)and(djmin_z>=0) then
begin
//виведення результатів
MemoDUO.Lines.Add('');
MemoDUO.Lines.Add('Оптимальний план прямої задачі:');
for iii := 1 to m do
MemoDUO.Lines.Add(Cells[1, npk+iii]+ ' = ' + Cells[0, npk+iii]);
MemoDUO.Lines.Add('Оцінки прямої задачі:');
for iii := 1 to n2 do
MemoDUO.Lines.Add('d' + Cells[iii+2,1] + ' = ' + Cells[iii+2, npk+m+1]);
ShowMessage('План оптимальний');
goto 1;
end;
roz_s:=djmin;
ind:=1;
{розв'язковий рядок}
isb:=0;
i:=1;
roz_r:=0;
While ((isb=0) And (i<=m)) do
begin
If StrToFloat(Cells[roz_s,npk+i])>0 Then
begin
isb:=1;
mina:=StrToFloat(Cells[2,npk+i])/StrToFloat(Cells[roz_s,npk+i]);
roz_r:=i;
end;
i:=i+1;
end;
If isb=0 Then begin showmessage('Функція необмежена'); goto 1; end;
For i:=1 To m do
If ((StrToFloat(Cells[roz_s,npk+i])>0)And(isM=0)) Or ((StrToFloat(Cells[roz_s,npk+i])>0)And(isM=1)And(Cells[0,npk+i]='-M')) Then
If (StrToFloat(Cells[2,npk+i])/StrToFloat(Cells[roz_s,npk+i]))<=mina Then
begin
mina:=StrToFloat(Cells[2,npk+i])/StrToFloat(Cells[roz_s,npk+i]);
roz_r:=i;
end;
roz_r:=roz_r+npk;
npk0:=npk;
npk:=npk+m+2;
{переписуємо і міняємо базову змінну}
rowcount:=npk+m+2;
if cells[0,roz_r]='-M' then
for j:=1 to n2 do
if (cells[1,roz_r]=cells[j+2,1]) then cells[j+2,npk]:='вибула';
for j:=1 to n2 do
if (cells[j+2,npk0]='вибула') then cells[j+2,npk]:='вибула';
if (npk+m<14) then Height:=25*(npk+m+2)
else
begin
height:=13*25;
width:=width+18;
end;
For i:=1 To (m+1) do
If (npk0+i=roz_r) Then
begin
Cells[1,npk+i]:=Cells[roz_s,1];
Cells[0,npk+i]:=Cells[roz_s,0]
end
Else
begin
Cells[1,npk+i]:=Cells[1,npk0+i];
Cells[0,npk+i]:=Cells[0,npk0+i];
end;
iter:=iter+1;
cells[0,npk0+m+2]:='ітер '+inttostr(iter);
cells[1,npk0+m+2]:='р.ел ('+Inttostr(roz_r-npk0)+';'+Inttostr(roz_s-2)+')';
{заповнюємо симплекс табличку}
For j:=0 To n2 do
if cells[j+2,npk]<>'вибула' then
begin
For i:=1 To m do
If (npk0+i=roz_r) Then
Cells[j+2,npk+i]:=FloatToStr(roundto(StrToFloat(Cells[j+2,npk0+i])/StrToFloat(Cells[roz_s,roz_r]),-3))
Else
Cells[j+2,npk+i]:=FloatToStr(roundto(StrToFloat(Cells[j+2,npk0+i])-StrToFloat(Cells[roz_s,npk0+i])*StrToFloat(Cells[j+2,roz_r])/StrToFloat(Cells[roz_s,roz_r]),-3));
end
else For i:=1 To m do Cells[j+2,npk+i]:='-';
end;
end;
1:end;
procedure TForm1.N_DZ_standartClick(Sender: TObject);
var i,j:integer;
first_el:boolean;
s:string;
begin
begin
// Зміни в доступності пунктів меню
N_makeDZ.Enabled:=false;
N_makePZ.Enabled:=true;
N4.Enabled:=false;
// Зведення задачі до стандартизованого вигляду ПЗ
if extremum_max then
begin
extremum_max:=false;
for j := 1 to n do
C[j]:=-1*C[j];
end;
for i := 1 to m do
if Znak[i]=1 then
begin
Znak[i]:=2;
for j := 1 to n do
A[i,j]:=-1*A[i,j];
B[i]:=-1*B[i];
end;
// Зробимо видимою панель виводу результатів
PanelDUO.Visible:=true;
SGRD_A.Enabled:=false;
MemoDUO.Lines.Add('');
MemoDUO.Lines.Add(' Стандартизований вигляд (Двоїста задача):');
//Вивід ЦФ прямої задачі
first_el := true;
for j := 1 to n do
if C[j]<>0 then
begin
if not first_el then
begin
if C[j]>0 then s:=s+ ' + '
else s:=s+ ' - ';
end
else
begin
first_el:=false;
if C[j]<0 then s:=s+ '-';
end;
s:=s + FloatToStr(ABS(C[j])) + ' y' + FloatToStr(j);
end;
s:=s+' -> ';
if extremum_max then s:=s + 'max'
else s:=s + 'min';
MemoDUO.Lines.Add(s);
//вивід обмежень прямої задачі
for i := 1 to m do
begin
s:='';
first_el := true;
for j := 1 to n do
if A[i,j]<>0 then
begin
if not first_el then
begin
if A[i,j]>0 then s:=s+ ' + '
else s:=s+ ' - ';
end
else
begin
first_el:=false;
if A[i,j]<0 then s:=s+ '-';
end;
s:=s + FloatToStr(Abs(A[i,j])) + ' y' + FloatToStr(j);
end;
case Znak[i] of
0:s:=s+' = ';
1:s:=s+' <= ';
2:s:=s+' >= ';
end;
s:=s + FloatToStr(B[i]);
MemoDUO.Lines.Add(s);
end;
// вивід обмежень на невід'ємність змінних
s:='';
first_el := true;
for j := 1 to n do
if X_nevid[j] then
begin
if not first_el then
begin
s:=s+ ', ';
end
else first_el:=false;
s:=s + 'y' + FloatToStr(j);
end;
s:=s+' >= 0 ';
MemoDUO.Lines.Add(s);
end;
end;
procedure TForm1.N_makeDZClick(Sender: TObject);
var i,j:integer;
first_el:boolean;
s:string;
begin
begin
// Зміни в доступності пунктів меню
N_DZ_standart.Enabled:=true;
N_PZ_standart.Enabled:=true;
N4.Enabled:=false;
// Зробимо видимою панель виводу результатів
PanelDUO.Visible:=true;
SGRD_A.Enabled:=false;
MemoDUO.Lines.Add('');
MemoDUO.Lines.Add(' ДВОЇСТА ЗАДАЧА');
//Вивід ЦФ прямої задачі
first_el := true;
for i := 1 to m do
if B[i]<>0 then
begin
if not first_el then
begin
if B[i]>0 then s:=s+ ' + '
else s:=s+ ' - ';
end
else
begin
first_el:=false;
if B[i]<0 then s:=s+ '-';
end;
s:=s + FloatToStr(ABS(B[i])) + ' y' + FloatToStr(i);
end;
s:=s+' -> min';
MemoDUO.Lines.Add(s);
//вивід обмежень прямої задачі
for j := 1 to n do
begin
s:='';
first_el := true;
for i := 1 to m do
if A[i,j]<>0 then
begin
if not first_el then
begin
if A[i,j]>0 then s:=s+ ' + '
else s:=s+ ' - ';
end
else
begin
first_el:=false;
if A[i,j]<0 then s:=s+ '-';
end;
s:=s + FloatToStr(Abs(A[i,j])) + ' y' + FloatToStr(i);
end;
if X_nevid[j] then s:=s+' >= '
else s:=s+' = ';
s:=s + FloatToStr(C[j]);
MemoDUO.Lines.Add(s);
end;
// вивід обмежень на невід'ємність змінних
s:='';
first_el := true;
for i := 1 to m do
if Znak[i]<>0 then
begin
if not first_el then
begin
s:=s+ ', ';
end
else first_el:=false;
s:=s + 'y' + FloatToStr(i);
end;
s:=s+' >= 0 ';
MemoDUO.Lines.Add(s);
end;
end;
procedure TForm1.N_makePZClick(Sender: TObject);
var i,j:integer;
first_el:boolean;
s:string;
begin
begin
// Зміни в доступності пунктів меню
N_DZ_standart.Enabled:=true;
N_PZ_standart.Enabled:=true;
N4.Enabled:=false;
// Зробимо видимою панель виводу результатів
PanelDUO.Visible:=true;
SGRD_A.Enabled:=false;
MemoDUO.Lines.Add('');
MemoDUO.Lines.Add(' ПРЯМА ЗАДАЧА');
//Вивід ЦФ прямої задачі
first_el := true;
for i := 1 to m do
if B[i]<>0 then
begin
if not first_el then
begin
if B[i]>0 then s:=s+ ' + '
else s:=s+ ' - ';
end
else
begin
first_el:=false;
if B[i]<0 then s:=s+ '-';
end;
s:=s + FloatToStr(ABS(B[i])) + ' х' + FloatToStr(i);
end;
s:=s+' -> max';
MemoDUO.Lines.Add(s);
//вивід обмежень прямої задачі
for j := 1 to n do
begin
s:='';
first_el := true;
for i := 1 to m do
if A[i,j]<>0 then
begin
if not first_el then
begin
if A[i,j]>0 then s:=s+ ' + '
else s:=s+ ' - ';
end
else
begin
first_el:=false;
if A[i,j]<0 then s:=s+ '-';
end;
s:=s + FloatToStr(Abs(A[i,j])) + ' х' + FloatToStr(i);
end;
if X_nevid[j] then s:=s+' <= '
else s:=s+' = ';
s:=s + FloatToStr(C[j]);
MemoDUO.Lines.Add(s);
end;
// вивід обмежень на невід'ємність змінних
s:='';
first_el := true;
for i := 1 to m do
if Znak[i]<>0 then
begin
if not first_el then
begin
s:=s+ ', ';
end
else first_el:=false;
s:=s + 'х' + FloatToStr(i);
end;
s:=s+' >= 0 ';
MemoDUO.Lines.Add(s);
end;
end;
procedure TForm1.N_PZ_StandartClick(Sender: TObject);
var i,j:integer;
first_el:boolean;
s:string;
begin
begin
// Зміни в доступності пунктів меню
N_makeDZ.Enabled:=true;
N_makePZ.Enabled:=false;
N4.Enabled:=false;
// Зведення задачі до стандартизованого вигляду ПЗ
if not extremum_max then
begin
extremum_max:=true;
for j := 1 to n do
C[j]:=-1*C[j];
end;
for i := 1 to m do
if Znak[i]=2 then
begin
Znak[i]:=1;
for j := 1 to n do
A[i,j]:=-1*A[i,j];
B[i]:=-1*B[i];
end;
// Зробимо видимою панель виводу результатів
PanelDUO.Visible:=true;
SGRD_A.Enabled:=false;
MemoDUO.Lines.Add('');
MemoDUO.Lines.Add(' Стандартизований вигляд (Пряма задача):');
//Вивід ЦФ прямої задачі
first_el := true;
for j := 1 to n do
if C[j]<>0 then
begin
if not first_el then
begin
if C[j]>0 then s:=s+ ' + '
else s:=s+ ' - ';
end
else
begin
first_el:=false;
if C[j]<0 then s:=s+ '-';
end;
s:=s + FloatToStr(ABS(C[j])) + ' X' + FloatToStr(j);
end;
s:=s+' -> ';
if extremum_max then s:=s + 'max'
else s:=s + 'min';
MemoDUO.Lines.Add(s);
//вивід обмежень прямої задачі
for i := 1 to m do
begin
s:='';
first_el := true;
for j := 1 to n do
if A[i,j]<>0 then
begin
if not first_el then
begin
if A[i,j]>0 then s:=s+ ' + '
else s:=s+ ' - ';
end
else
begin
first_el:=false;
if A[i,j]<0 then s:=s+ '-';
end;
s:=s + FloatToStr(Abs(A[i,j])) + ' X' + FloatToStr(j);
end;
case Znak[i] of
0:s:=s+' = ';
1:s:=s+' <= ';
2:s:=s+' >= ';
end;
s:=s + FloatToStr(B[i]);
MemoDUO.Lines.Add(s);
end;
// вивід обмежень на невід'ємність змінних
s:='';
first_el := true;
for j := 1 to n do
if X_nevid[j] then
begin
if not first_el then
begin
s:=s+ ', ';
end
else first_el:=false;
s:=s + ' X' + FloatToStr(j);
end;
s:=s+' >= 0 ';
MemoDUO.Lines.Add(s);
end;
end;
procedure TForm1.N_VVIDClick(Sender: TObject);
begin
Panel_ROZMIRU.Visible:=true;
Edit_N.Enabled:=true;
Edit_M.Enabled:=true;
CBox_EXTREMUM.Enabled:=true;
BtnRozmiryEnter.Enabled:=true;
Panel_A.Visible:=false;
N2.Enabled:=true;
N_PZ_Standart.Enabled:=false;
N_DZ_standart.Enabled:=false;
end;
end.
Размещено на Allbest.ru
Подобные документы
Початковий опорний план, перехід від одного до іншого. Оптимальний розв’язок, його головні критерії. Знаходження опорного плану задачі, складання симплексної таблиці. Приклад оформлення першої та другої таблиці для розв’язку задач лінійного програмування.
лекция [479,7 K], добавлен 10.10.2013Лінійне програмування як один з найбільш популярних апаратів математичної теорії оптимального управління рішень. Опис існуючих методів розв’язку задач лінійного програмування. Завдання, основні принципи, алгоритми і головна мета лінійного програмування.
курсовая работа [363,8 K], добавлен 03.12.2009Задача лінійного програмування. Розв’язання задачі геометричним методом. Приведення системи рівнянь до канонічного вигляду. Розв’язання симплекс-методом. Розв’язок двоїстої задачі. Задача цілочислового програмування і дробово-лінійного програм.
контрольная работа [385,2 K], добавлен 04.06.2009Застосування симплекс-методу для розв’язання оптимізаційних задач лінійного програмування, що містять три змінні. Функції ітераційної обчислювальної процедури, що виконують приведення до зручного для розв’язання оптимального вигляду ЗЛП за кілька кроків.
курсовая работа [359,5 K], добавлен 18.09.2013Використання мови програмуванння Java при виконанні "задачі лінійного програмування": її лексична структура і типи даних. Методи розв’язання задачі. Особливості логічної структури програми, побудова її зручного інтерфейсу за допомогою симплекс методу.
курсовая работа [437,9 K], добавлен 24.01.2011Відомості з теорії графів, методи отримання точних розв'язків задачі їх розфарбування. Алгоритм розфарбування графу методом неявного перебору. Комп'ютерна реалізація розв’язку задачі розфарбування графів. Типові задачі та існуючі програмні продукти.
курсовая работа [335,6 K], добавлен 15.06.2015Класифікація економіко-математичних моделей. Математична модель оптимізаційної задачі. Локальний критерій оптимальності. Поняття теорії ігор. Матричні ігри двох осіб. Гра зі змішаними стратегіями. Зведення матричної гри до задачі лінійного програмування.
дипломная работа [2,9 M], добавлен 22.10.2012Теоретичні основи та приклади економічних задач лінійного програмування. Розробка математичної моделі задачі (запис цільової функції і системи обмежень) і програмного забезпечення її вирішення за допомогою "Пошуку рішень" в Excel симплекс-методом.
курсовая работа [993,9 K], добавлен 10.12.2010Розв’язок багатокритеріальної задачі лінійного програмування з отриманням компромісного рішення (для задач з кількома функціями мети) за допомогою теоретико-ігрового підходу. Матриця мір неоптимальності та рядок функції мети. Модуль опису класу.
курсовая работа [588,8 K], добавлен 15.05.2011Приклади застосування цілочисельних задач лінійного програмування у плануванні та управлінні виробництвом, геометрична інтерпретація їх розв’язків на площині. Завдання складання розкладу занять на математичному факультеті. Математична модель розкладу.
дипломная работа [933,1 K], добавлен 23.09.2012