Автор работы: Пользователь скрыл имя, 28 Марта 2013 в 16:04, курсовая работа
В основе симплексного метода лежит алгоритм симплексных преобразований системы уравнений. Он позволяет, исходя из известного опорного плана (базисного решения) задачи, за конечное число шагов получить ее оптимальный план. Каждый из шагов (итераций) состоит в нахождении нового плана, которому соответствует лучшее (меньшее или большее в зависимости от условия задачи) значение целевой функции, чем значение этой же функции в предыдущем плане. Процесс продолжают до получения оптимального плана. Если задача не обладает планами или экстремум линейной функции равен то симплексный метод позволяет установить это в процессе решения.
Введение…………………………………………………………………………...3
Глава 1 Теоретические основы………………………………………………...…4
Предпосылки возникновения АСУ. Понятие АСУ……………………...4
1.2 Классификация АСУ…………………………………………………….…5
1.3 Функциональные задачи и подсистемы АСУ…………………………….6
1.4 Обеспечивающие подсистемы АСУ…………………………………..…..7
Глава 2. Симплекс метод……………………………………………………..…..9
2.1 Математическое описание метода……………………………………..….9
2.2 Блок – схема алгоритма…………………………………………………..13
2.3 Пример решения задачи с использованием симплекс-метода…………14
2.4 Текст программы………………………………………………………….16
Глава 3. Практические задания и подробное решение………………………..25
Заключение…………………………………………………………………….…33
Список использованной литературы…………………………………………...34
Так как в полученной системе уравнений нет отрицательных свободных членов, то базисное решение является допустимым (0; 0; 0; 60; 100; 36).
Выразим
целевую функцию через
Х2: {60/1; 100/1; 36/1} переводим Х2 в основные переменные: из третьего уравнения, так как 36/1=36 наименьший коэффициент.
Подставим в целевую функцию =>Х2:
Рассмотрим полученную систему уравнений и целевую функцию:
Если отыскивается максимум линейной формы, и в ступени выражений нет основных переменных с положительным знаком, то критерий оптимальности выполнен и полученное базисное решение служит оптимальным (задача решена), но в примере еще есть две переменные с положительным знаком.
Переходим
к новому базисному решению {0; 5; 0;
0; 20; 50}. Из не основных переменных, входящих
в линейную форму (уравнения) с положительным
коэффициентом выбираем ту, которой
соответствует наибольший коэффициент
и переводит ступени в
Рассмотрим переменную Х1 {10; 10; 17}. Выразим из первого уравнения переменную Х1:
Рассмотрим полученную систему уравнений и целевую функцию:
Если отыскивается максимум линейной формы, и в ступени выражений нет основных переменных с положительным знаком, то критерий оптимальности выполнен и полученное базисное решение служит оптимальным (задача решена), но в примере еще есть одна переменная с положительным знаком (Х3).
Переходим к новому базисному решению {10; 0; 0; 0; 40; 20}. Из не основных переменных, входящих в линейную форму с положительным коэффициентом выбираем Х3, которой соответствует наибольший коэффициент (5) и переводит ступени в основные.
Рассмотрим переменную Х3 {0; 8; 20}. Выразим из второго уравнения переменную Х3:
Рассмотрим полученную систему уравнений и целевую функцию:
Отыскивается
максимум линейной формы, так как
в ступени выражений нет
То есть при Х1=10; Х2=0; X3=8 максимальное значение функции равно 80 (Lmax=80).
Program Simplex_Metod;
Uses crt;
label
POVZNAC, NACH;
var
Fo, FunctPr, B, H, Hnew, C, Cnew, CPr, Cprnew, FX :array[1..30] of real;
X, Xnew
BS, Bvsp,ZNAC
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, CHLEN :real;
VSP, S, PrOper
F
DPx, DPy, MinMax, Kell, SNom :integer;
Function MakeIndex (V:integer; S:char):string;
var
M,Z :string;
begin
STR (V,M);
Z:=S+M;
MakeIndex:=Z;
end;
Procedure enter;
var
BUF :string;
NEXT :boolean;
begin
clrscr;
repeat
write ('Vvedite kol-vo uravnenii: ');
readln (SNom);
if (SNom > 10) or (SNom <=0) then
begin
writeln ('Vvedite chislo ot 1 do 10: ');
readln;
end
else NEXT:=True;
until NEXT;
repeat
NEXT:=False;
write ('Kol-vo elementov: ');
readln (Kell);
if (Kell > 10) or (Kell <=0) then
begin
writeln ('Vvedite chislo ot 1 do 10: ');
readln;
end
else NEXT:=True;
until NEXT;
NachKell:=Kell;
DPx:=Kell+1;
DPy:=1;
Epsilon:=0.00001;
for I:=1 to SNom do
begin
for J:=1 to Kell do
begin
write ('Vvedite ',J,'-i element ',I,'-go uravnenij: ');
readln (Xnew [I,J]);
end;
repeat
write ('Vvedite znac: ');
readln (ZNAC [I]);
if (ZNAC [I] <> '>=') and (ZNAC [I] <> '=') and (ZNAC [I] <> '<=') then
begin
write ('Nepravilno zadan znac.');
readln;
end;
if (ZNAC [I] = '=') or (ZNAC [I] = '>=') then PriznacY:=1;
until (ZNAC [I] = '>=') or (ZNAC [I] = '=') or (ZNAC [I] = '<=');
write ('Vvedite svobodnii chlen: ');
read (B[I]);
end;
write ('Vvedite svobodnii chlen celevoi funkcii: ');
readln (CHLEN);
for J:=1 to Kell do
begin
write ('Vvedite ',J,'-i koefficient celevoi funkcii: ');
read (FX[J]);
end;
readln;
write ('Celevaj funkcij stremitsa k maksimumu (Y/N): ');
readln (BUF);
if (BUF='Y') or (PrOper='Y') then MinMax:=1
else MinMax:=2;
write ('Celochislennoe reshenie (Y/N): ');
readln (PrOper);
if (PrOper='Y')or (PrOper='Y') then PrOper:='Y'
end;
procedure DOP_PER;
begin
if ZNAC[I1]='=' then
begin
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;
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[
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
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
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('B ', Kit,'=i iteracii bilo polucheno optimalnoe reshenie');
for I1:=1 to SNom do
if BS[I1][1]='Y' then
begin
writeln('No t.k. iz bazisa ne vivedeni vse Y, to ');
writeln('mogno sdelat vivod, chto RESHENII NET');
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;
if P1=0 then writeln('Reshenie celochislennoe.');
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('Reshenii net t.k. nevozmogno opredelit kluchevyu stroky');
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('Reshenii net t.k. v bazisnom stolbce uge est ');
writeln('takaj peremennaj.');
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,
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,
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]*
end;
end;
repeat
KLst:=0;
KLstr:=0;
Kit:=Kit+1;
until (Kit=0);
end;
end.
Глава 3. Практические задания и подробное решение.
ЗАДАЧА 1
Составить модель оптимального выпуска продукции для цеха кондитерской фабрики. Виды выпускаемой продукции (М), виды основного сырья (П) и его запасы, нормы расхода сырья на единицу, уровни прибыли приведены в таблице. Рассчитать план и провести его анализ.
Виды сырья |
Расходы сырья на единицу продукции |
Общий запас сырья, ед. | |||
М1 |
М2 |
М3 | |||
|
П1 |
2 |
4 |
3 |
266 | |
П2 |
1 |
3 |
4 |
200 | |
П3 |
3 |
2 |
1 |
303 | |
Уровень прибыли на ед. продукции |
20 |
24 |
28 |
||
Содержание задачи.
Цех кондитерской фабрики вырабатывает три ассортиментные группы конфет, условно обозначенные М1, М2, М3 /в ед./.
Для их производства используются основные виды ресурсов /сырья/ трех видов, условно названных П1, П2, П3 /в ед./.
Расход каждого ресурса на производство единицы продукции является заданной величиной, определяется по рецептуре и обозначается символами а11, a12..., а33, где а - норма расхода, первая подстрочная 1 – номер ресурса, вторая подстрочная 1, 2, 3 – номер ассортиментной группы конфет.
Наличие
каждого ресурса для