Симплекс-метод 2 (стр. 3 из 3)
Kell:=Kell+1; Bvsp[Kell]:=MakeIndex(DPy,'Y');
DPy:=DPy+1;
Xnew[I1,Kell]:=1;
if MinMax=1 then FX[Kell]:=-1
else FX[Kell]:=1;
FunctPr[Kell]:=1;
for I:=1 to SNom do
if I<>I1 then Xnew[I,Kell]:=0;
end;
if ZNAC[I1]='<=' then
begin
Kell:=Kell+1; Bvsp[Kell]:=MakeIndex(DPx,'X');
DPx:=DPx+1; Dop_X:=Dop_X+1;
Xnew[I1,Kell]:=1; FX[Kell]:=0;
for I:=1 to SNom do
if I<>I1 then Xnew[I,Kell]:=0;
end;
end;
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 SNom do Xnew[I,J]:=Xnew[I,J+1];
end;
end;
procedure OPER;
var
MAX, Z:real;
begin
KLstr:=1;
MAX:=H[1]-INT(H[I1]);
for I1:=2 to SNom do
if (H[I1]-int(H[I1]))>=MAX then
begin
MAX:=H[I1];
KLstr:=I1;
end;
SNom:=SNom+1;
Hnew[SNom]:=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[SNom,I1]:=X[KLstr,I1]-Z;
end;
ZNAC[SNom]:='>=';
end;
begin
clrscr;
Kit:=0;
Dop_X:=0;
Kx:=1;
Ky:=3;
enter;
for J:=1 to Kell do Bvsp[J]:=MakeIndex(J,'X');
for I1:=1 to SNom do DOP_PER;
MIN:=0;
if (MinMax=1) and (PriznacY=1) then
begin
MIN:=MinMax;
MinMax:=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]<Bvsp[I1] then
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 SNom do
begin
P:=Xnew[I,I1];
Xnew[I,I1]:=Xnew[I,J];
Xnew[I,J]:=P;
end;
end;
Kit:=1;
clrscr;
for I:=1 to SNom 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;
for I:=1 to SNom 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;
for J:=1 to Kell do Fo[J]:=0;
F0:=0;
for J:=1 to Kell do Fo[J]:=0;
for I1:=1 to SNom 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])<Epsilon then Fo[J]:=+0;
end;
for J:=1 to Kell do
if PriznacY<>1 then Fo[J]:=Fo[J]-FX[J];
P:=0;
for J:=1 to Kell do
if MinMax=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
writeln('В ', Kit,'-й итерации было получено оптимальное решение');
for I1:=1 to SNom do
if BS[I1][1]='Y' then
begin
writeln('Но так как из базиса не введены все Y, то ');
writeln('можно сделать вывод, что РЕШЕНИЙ НЕТ');
exit;
end;
for I:=1 to SNom do
begin
Z:=round(H[I]);
if ABS(Z-H[I])<Epsilon then H[I]:=round(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])<Epsilon then X[I,J]:=round(X[I,J]);
end;
end;
P1:=0;
for I:=1 to SNom 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 SNom do
if ABS (FRAC(X[I1,J]))>=Epsilon then
begin
P:=1;
continue;
end;
end;
if (PrOper='Y') and (P1=1) then
begin
oper;
NachKell:=Kell;
I1:=SNom; DPy:=1;
DOP_PER;
BS[SNom]:=Bvsp[Kell];
CPrnew[SNom]:=FunctPr[Kell];
Cnew[SNom]:=FX[Kell];
goto NACH;
end;
ifP1=0 thenwriteln('Решение целочисленное.');
if MIN=1 then
begin
F0:=-F0;
MinMax:=MIN;
end;
KLst:=1; Mo:=0;
for J:=1 to Kell do
if MinMax=1 then
if Fo[J]<Mo then Mo:=Fo[J];
for J:=1 to Kell do
begin
if Bvsp[J][1]<>'Y' then
if MinMax=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;
P1:=0; K_st:=0;
for J:=1 to Kell do
if ABS(Mo-Fo[J])<Epsilon then
begin
K_st:=K_st+1;
for I:=1 to SNom 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=SNom*K_st then
begin
writeln('Решений нет, так как невозможно определить ключевую строку');
exit;
end;
P1:=0;
for J:=1 to Kell do
if ABS (Mo-Fo[J])<Epsilon then
for I:=1 to Snom do
if B[I]>=0 then
begin
if B[I]<P then
if Bvsp[KLst]<>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;
for I:=1 to SNom do
if Bvsp[KLst]=BS[I] then
begin
writeln('Решений нет, так как в базисном столбце уже есть ');
writeln('такая переменная.');
exit;
end;
if CPr[KLstr]=1 then SOKR;
BS[KLstr]:=Bvsp[KLst];
Cnew[KLstr]:=FX[KLst];
CPrnew[KLstr]:=FunctPr[KLst];
for I:=1 to SNom 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;
repeat
KLst:=0;
KLstr:=0;
Kit:=Kit+1;
until (Kit=0);
end;
end.
Часть 3. Тестовые примеры.
Пример №1.
Целевая функция этой системы уравнений стремится в максимум, и имеет вид:
Программа выводит данные:
В 4-й итерации было получено оптимальное решение.
Результат решения:
Fmax=80
X1=10
X3=8
X6=12
Пример №2.
Целевая функция этой системы уравнений стремится в минимум, и имеет вид:
Программа выводит данные:
В 6-й итерации было получено оптимальное решение.
Результат решения:
Fmin=75
X3=10
X2=9
X5=45
Часть 4. Заключение.
В курсовой работе проделана работа по изучению следующих вопросов:
- Рассмотрен и дан алгоритм симплекс метода.
- Разработана программа для решения разного рода задач, ее можно применить в различных отраслях, а также были составлены текстовые примеры, показывающие простоту и экономичность работы.
- Инструкции пользователю не нужны, так как данная программа проста и практически не требует времени на освоение.
Данная программа имеет простой интерфейс, не требует дополнительных ресурсов в виде свободного места на диске. Все вычисления производятся только в оперативной памяти. Тесты, не выявили ни каких отклонений в ходе решения программой поставленных задач.
Программа имеет ограничения: количество рассмотренных уравнений и вводимых элементов уравнения не должно превышать 10.
Программа не рассчитана на неправильный ввод формата вводимых данных.
Часть 5. Литература.
1. Зайченко Ю.П., Шумилова С.А. Исследование операций.
2. Лищенко «Линейное и нелинейное программирование», М. 2003
3. А.Н. Карасев, Н.Ш. Кремер, Т.Н. Савельева «Математические методы в экономике», М.2000
4. Орлов А.И. Теория принятия решений. Учебное пособие. - М.: Издательство "Март", 2004
5. Интернет