Автор работы: Пользователь скрыл имя, 25 Сентября 2013 в 23:17, курсовая работа
На основе поставленной цели были определены задачи:
o изучить симплексный метод решения задач линейного программирования;
o рассмотреть решение симплексным методом в MS Excel;
o разработать свое приложение для решения задачи симплексным методом.
Рис.2 Окно параметров надстройки «Поиск решения»
Щелкнув на кнопке Solver (Выполнить), запустите процесс поиска решения.
Рис.3 Результаты поиска решения
Параметры средства «Поиск решения». Максимальное время – служит для ограничения времени, отпущенного на поиск решения задачи. В этом поле можно ввести время в секундах, не превышающее 32 767 (примерно девять часов); значение 100, используемое по умолчанию, вполне приемлемо для решения большинства простых задач.
Предельное число итераций – управляет временем решения задачи путем ограничения числа вычислительных циклов (итераций).
Относительная погрешность – определяет точность вычислений. Чем меньше значение этого параметра, тем выше точность вычислений.
Допустимое отклонение – предназначен для задания допуска на отклонение от оптимального решения, если множество значений влияющей ячейки ограничено множеством целых чисел. Чем больше значение допуска, тем меньше времени требуется на поиск решения.
Сходимость – применяется только к нелинейным задачам. Когда относительное изменение значения в целевой ячейке за последние пять итераций становится меньше числа, указанного в поле Сходимость, поиск прекращается.
Линейная модель – служит для ускорения поиска решения путем применения к задаче оптимизации линейной модели. Нелинейные модели предполагают использование нелинейных функций, фактора роста и экспоненциального сглаживания, что замедляет вычисления.
Неотрицательные значения – позволяет установить нулевую нижнюю границу для тех влияющих ячеек, для которых не было задано соответствующее ограничение в диалоговом окне Добавить ограничение.
Автоматическое
Показывать результаты итераций – приостанавливает поиск решения для просмотра результатов отдельных итераций.
Загрузить модель – после щелчка на этой кнопке отрывается одноименное диалоговое окно, в котором можно ввести ссылку на диапазон ячеек, содержащих модель оптимизации.
Сохранить модель – служит для отображения на экране одноименного диалогового окна, в котором можно ввести ссылку на диапазон ячеек, предназначенный для хранения модели оптимизации.
Оценка линейная – выберите этот переключатель для работы с линейной моделью.
В результате исследования основных алгоритмов решения задач ЛП, было принято решение поставленную задачу планирования производства решать симплекс методом. Это обусловлено тем, что симплекс метод является эффективным алгоритмом и наиболее универсальным методом, которым можно решить любую задачу линейного программирования. В качестве вспомогательного средства, для составления конкретной задачи планирования производства (подбора таких значений, чтобы задача имела решение) было использовано средство «Поиск решения» в MS Excel.
В данном приложении рассматривается четыре особых случая, встречающихся при использовании симплекс-метода:
Вырожденность
В ходе выполнения симплекс-метода проверка условия допустимости может привести к неоднозначному выбору исключаемой переменной. В этом случае на следующей итерации одна или более базисных переменных примут нулевое значение. Тогда новое решение будет вырожденным.
С практической точки зрения вырожденность объясняется тем, что в исходной задаче присутствует по крайней мере одно избыточное ограничение.
С вычислительной и теоретической точек зрения вырожденность может привести к следующим последствиям: в процессе вычислений может возникнуть зацикливание. Поэтому может возникнуть ситуация, когда при реализации симплекс-метода некоторая последовательность будет повторяться, не изменяя значения целевой функции и не приводя к завершению вычислительного процесса.
Альтернативные оптимальные решения
Когда прямая (если рассматривается двухмерная задача ЛП, в общем случае — гиперплоскость), представляющая целевую функцию, параллельна прямой (гиперплоскости), соответствующей связывающему неравенству (которое в точке оптимума выполняется как точное равенство), целевая функция принимает одно и то оке оптимальное значение на некотором множестве точек границы области допустимых решений. Эти решения называются альтернативными оптимальными решениями.
Неограниченные решения
В некоторых задачах ЛП значения переменных могут неограниченно возрастать без нарушения ограничений. Это говорит о том, что пространство допустимых решений не ограничено, по крайней мере, по одному направлению. В результате этого целевая функция может возрастать (задача максимизации) или убывать (задача минимизации) неограниченно.
Неограниченность решения задачи свидетельствует только об одном: модель разработана не достаточно корректно.
Правило выявления неограниченности решения следующее. Если на какой-либо симплекс-итерации коэффициенты в ограничениях для какой-нибудь небазисной переменной будут неположительными, значит, пространство решений не ограничено в направлении возрастания этой переменной. Кроме того, если коэффициент этой переменной в строке отрицателен, когда рассматривается задача максимизации, или положителен в задаче минимизации, целевая функция также не ограничена.
В некоторых плохо построенных моделях ЛП пространство допустимых решений может быть неограниченным даже тогда, когда задача имеет конечное (ограниченное) оптимальное решение. Такое может случиться, если при построении ограничений допущены ошибки.
Отсутствие допустимых решений
Если ограничения задачи ЛП несовместны (т.е. они не могут выполняться одновременно), то задача не имеет допустимых решений. Такая ситуация не может возникнуть, если все неравенства, составляющие систему ограничений, имеют тип "<" с неотрицательными правыми частями, так как в этом случае дополнительные переменные могут составить допустимое решение. Для других типов ограничений мы используем искусственные переменные. И хотя в оптимальном решении все искусственные переменные в силу штрафов равны нулю, такой исход возможен только тогда, когда задача имеет непустое пространство допустимых решений. В противном случае в оптимальном решении будет присутствовать хотя бы одна положительная искусственная переменная.
С практической точки зрения отсутствие допустимых решений свидетельствует о том, что задача плохо сформулирована.
Описание работы приложения:
Рис. 4 Вид главного окна приложения
Рассмотрим задачу линейного программирования вида:
Приведем задачу к каноническому виду, вводя дополнительные переменные:
Занесем данные в таблицу и выполним симплексные преобразования.
БП |
|
|||||||
|
5 |
10 |
9 |
28 |
0 |
0 | |||
0 0 |
5 4 |
1 1 |
6 1 |
3 1 |
6 4 |
1 0 |
0 1 | |
0 |
-5 |
-10 |
-9 |
-28 |
0 |
0 | ||
28 |
3/6 |
1/6 |
1 |
1/2 |
1 |
1/6 |
0 | |
0 |
2/3 |
1/3 |
-3 |
-1 |
0 |
-2/3 |
1 | |
23 1/3 |
-1/3 |
18 |
5 |
0 |
4 2/3 |
0 | ||
28 |
1/2 |
0 |
2 1/2 |
1 |
1 |
1/2 |
-1/2 | |
5 |
2 |
1 |
-9 |
-3 |
0 |
-2 |
3 | |
24 |
0 |
15 |
4 |
0 |
4 |
1 | ||
Оптимальный план задачи имеет вид: X*(2; 0; 0; 0,5). Целевая функция при этом равна .
Рассмотрим решение этой же задачи в MS Excel:
X*(2; 0; 0; 0,5), Fmax = 24.
Проверим также решение этой задачи в созданном приложении.
В ходе выполнения работы были решены следующие задачи:
В итоге мы пришли к выводу, что при решении данной задачи, любым из описанных в курсовой работе способом, получается один и тот же ответ.
Листинг приложения.
unit Unit1;
interface
uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, Grids, StdCtrls;
type TForm1 = class(TForm) lbl1: TLabel; lbl2: TLabel; edt1: TEdit; edt2: TEdit; lbl3: TLabel; lbl4: TLabel; StrinGrid: TStringGrid; StrinGrid21: TStringGrid; rb1: TRadioButton; rb2: TRadioButton; btn2: TButton; btn3: TButton; btn4: TButton; btn1: TButton; procedure edt1Change(Sender: TObject); procedure edt2Change(Sender: TObject); procedure btn3Click(Sender: TObject); procedure btn4Click(Sender: TObject); procedure btn2Click(Sender: TObject); procedure btn1Click(Sender: TObject); private { Private declarations } public { Public declarations } end;
var Form1: TForm1; i,j,n,m,k,obch,i0,j0,Mw,bpr, str:string; a:array[1..100,1..100] of real; b,f,d,restr,zn,bzap: array[1..100] of real; basis,nb: array [1..100] of integer; bol,sr,rez,c,l,v,c1,v1,l1,
sz,sz1:array [0..100,0..100] of real; x10,x20,x11,x21,e1,e2,gradx, Maxl,fx,kx:integer; a1,b1: real;
implementation
uses Unit2;
{$R *.dfm}
//**************СимплексМетод* procedure VvodDannyh; begin for i:=1 to m do for j:=1 to n do begin str:=Form1.StrinGrid.Cells[j, for k:=1 to length(str) do if str[k]='.' then str[k]:=','; a[i,j]:=StrToFloat(str); end; for i:=1 to m do begin str:=Form1.StrinGrid.Cells[n+ for k:=1 to length(str) do if str[k]='.' then str[k]:=','; b[i]:=StrToFloat(str); end; for i:=1 to n do begin str:=Form1.StrinGrid21.Cells[ for k:=1 to length(str) do if str[k]='.' then str[k]:=','; f[i]:=StrToFloat(str); end; end;
procedure VvodNewPerem; begin for j:=n+1 to n+kolDop do f[j]:=0; r:=0; for i:=1 to m do for j:=n+kolDop+1 to obch do if basis[i]=0 then begin f[j]:=Mw; if j=n+kolDop+i-r then begin a[i,j]:=1; basis[i]:=j; end else a[i,j]:=0; end else inc(r); end;
procedure simplex; begin for j:=1 to obch do begin d[j]:=0; for i:=1 to m do begin d[j]:=d[j]+f[basis[i]]*a[i,j]; end; d[j]:=d[j]-f[j]; end; j0:=1; bol:=d[1]; if Form1.rb1.Checked then begin for j:=2 to obch do if d[j]<bol then begin bol:=d[j]; j0:=j; end; end else begin for j:=2 to obch do if d[j]>bol then begin bol:=d[j]; j0:=j; end; end; end; procedure Max; var A1:array [1..100,1..100]of real; d1,b1: array [1..100]of real; begin neogr:=0; while bol<0 do begin k:=0; for i:=1 to m do begin restr[i]:=0; if (a[i,j0]>0 ) and (b[i]>0) then begin restr[i]:=b[i]/a[i,j0] ; k:=k+1; end; end; if k<>0 then begin sr:=100000000; i0:=1; for i:=1 to m do if restr[i]<>0 then if restr[i]<sr then begin sr:=restr[i]; i0:=i; end; basis[i0]:=j0; for i:=1 to m do for j:=1 to obch do begin if i=i0 then begin b1[i]:=b[i]/a[i0,j0]; if j<>j0 then begin A1[i,j]:=a[i,j]/a[i0,j0]; end; end else begin A1[i,j]:=(a[i,j]*a[i0,j0]-a[ b1[i]:=(b[i]*a[i0,j0]-b[i0]*a[ end; end; for i:=1 to m do begin if i<>i0 then a1[i,j0]:=0; end; a1[i0,j0]:=1; for i:=1 to m do for j:=1 to obch do begin a[i,j]:=A1[i,j]; b[i]:=b1[i]; end; simplex; end else begin if a[i,j0]<=0 then neogr:=neogr+1; end; if neogr=m then begin form2.Show; form2.lbl1.Caption:='Функция неограничена сверху'; form2.StrinGrid2StrinGrid. exit; end; end; end;
procedure Min; var A1:array [1..100,1..100]of real; d1,b1: array [1..100]of real; begin while bol>0 do begin neogr:=0; k:=0; for i:=1 to m do if (a[i,j0]>0 ) and (b[i]>0) then begin restr[i]:=0; restr[i]:=b[i]/a[i,j0] ; k:=k+1; end; if k<>0 then begin sr:=restr[1]; i0:=1; for i:=2 to m do if restr[i]<>0 then if restr[i]>sr then begin sr:=restr[i]; i0:=i; end; basis[i0]:=j0; for i:=1 to m do for j:=1 to obch do begin if i=i0 then begin b1[i]:=b[i]/a[i0,j0]; if j<>j0 then begin A1[i,j]:=a[i,j]/a[i0,j0]; end; end else begin A1[i,j]:=(a[i,j]*a[i0,j0]-a[ b1[i]:=(b[i]*a[i0,j0]-b[i0]*a[ end; end; for i:=1 to m do begin if i<>i0 then a1[i,j0]:=0; end; a1[i0,j0]:=1; for i:=1 to m do for j:=1 to obch do begin a[i,j]:=A1[i,j]; b[i]:=b1[i]; end; simplex; end else begin if a[i,j0]<=0 then neogr:=neogr+1; end; if neogr=m then begin form2.Show; form2.lbl4.Caption:='Функция неограничена снизу!'; form2.StrinGrid2StrinGrid. exit; end; end; end;
procedure TForm1.btn1Click(Sender: TObject); var i:integer; begin if Sender=btn1 then n:=StrToInt(edt1.Text); m:=StrToInt(edt2.Text); StrinGrid.ColCount:=n+3; StrinGrid.RowCount:=m+1; StrinGrid21.RowCount:=2; StrinGrid21.ColCount:=n+1; Form2.StrinGrid2StrinGrid. for i:=0 to n-1 do begin StrinGrid.Cells[i+1,0]:='a'+ StrinGrid21.Cells[i+1,0]:='x'+ end; for i:=0 to m-1 do StrinGrid.Cells[0,i+1]:= StrinGrid.Cells[n+2,0]:='b'; StrinGrid.Cells[n+1,0]:='знак' StrinGrid21.Cells[0,1]:='F(X)= end;
procedure TForm1.edt2Change(Sender: TObject); begin if (edt2.Text<>'') then begin n:= StrToInt(edt2.Text); StrinGrid.ColCount:=n+3; StrinGrid21.ColCount:=n+1; strinGrid.FixedCols:=1; end else begin StrinGrid.ColCount:=1; StrinGrid21.ColCount:=1; end; for i:=1 to n do begin StrinGrid.Cells[i,0]:=' X'+IntToStr(i); StrinGrid21.Cells[i,0]:=' X'+IntToStr(i); end; StrinGrid.Cells[n+1,0]:= 'Знак'; StrinGrid.Cells[n+2,0]:=' B'; StrinGrid21.Cells[0,1]:='F(X)=
end;
procedure TForm1.edt1Change(Sender: TObject); begin if (edt1.Text<>'') then begin m:= StrToInt(edt1.Text); StrinGrid.RowCount:=m+1; StrinGrid.FixedRows:=1; end else StrinGrid.RowCount:=1; for i:=1 to m do StrinGrid.Cells[0,i]:='Огр'+ end;
procedure TForm1.btn2Click(Sender: TObject); begin Form1.edt1.Clear; form1.edt2.Clear; form2.lbl1.Caption:=''; form2.lbl2.Caption:=''; form2.lbl3.Caption:=''; form2.lbl4.Caption:=''; for i := 0 to 100 do for j := 0 to 100 do begin form1.StrinGrid.Cells[i,j] := ''; end; for i := 0 to 100 do for j := 0 to 100 do begin form1.StrinGrid21.Cells[i,j] := ''; end; for i := 0 to 100 do for j := 0 to 100 do begin form2.StrinGrid2StrinGrid. end; end;
procedure TForm1.btn4Click(Sender: TObject); begin form1.Close; form2.Close; end;
procedure TForm1.btn3Click(Sender: TObject); var A1:array [1..100,1..100]of real; d1,b1: array [1..100]of real; begin Form2.lbl2.Caption:=''; Form2.lbl3.Caption:=''; form2.lbl4.Caption:=''; for j:=1 to 100 do for i:=1 to 100 do begin a[i,j]:=0; A1[i,j]:=0; end; for i:=1 to 100 do begin b[i]:=0; b1[i]:=0; d1[i]:=0; f[i]:=0; basis[i]:=0; nb[i]:=0; end; KolDop:=0;
VvodDannyh; kolDop:=0; Mw:=-10000; for i:=1 to m do begin if b[i]<0 then begin for j:=1 to n do begin a[i,j]:=-a[i,j]; end; b[i]:=-b[i]; if (Form1.StrinGrid.Cells[n+1,i]= then begin Form1.StrinGrid.Cells[n+1,i]:= Form1.StrinGrid.Cells[n+2,i]:= for k:=1 to n do Form1.StrinGrid.Cells[k,i]:= end else if (Form1.StrinGrid.Cells[n+1,i]= then begin Form1.StrinGrid.Cells[n+1,i]:= Form1.StrinGrid.Cells[n+2,i]:= for k:=1 to n do Form1.StrinGrid.Cells[k,i]:= end end; end; for i:=1 to m do begin if (Form1.StrinGrid.Cells[n+1,i]= then begin inc(kolDop); a[i,n+kolDop]:=-1; end else if (Form1.StrinGrid.Cells[n+1,i]= then begin inc(kolDop); a[i,n+kolDop]:=1; end end; kab:=0; for j:=1 to n+kolDop do begin r:=0; for i:=1 to m do begin if a[i,j]=0 then r:=r+1 else begin if ((a[i,j]>0)and (b[i]>0))or ((a[i,j]<0)and (b[i]<0)) then knet:=i; end; end; if r=m-1 then begin if nb[knet]=0 then begin kab:=kab+1; nb[knet]:=j; end; end; end;
for i:=1 to m do begin if nb[i]<>0 then begin if a[i,nb[i]]<>1 then begin if ((a[i,nb[i]]>0)and(b[i]>0))or ((a[i,nb[i]]<0)and(b[i]<0)) then for j:=1 to n+kolDop do begin if a[i,j]<>0 then a[i,j]:=a[i,j]/a[i,nb[i]]; if b[i]<>0 then b[i]:=b[i]/a[i,nb[i]]; end; end; end; end; kab:=0; for i:=1 to m do if a[i,nb[i]]=1 then begin basis[i]:=nb[i]; inc(kab); end; obch:=n+m+kolDop-kab; if kab<m then VvodNewPerem;
simplex; if rb1.Checked then Max else Min;
r:=0; for i:=1 to m do begin for j:=n+KolDop+1 to obch do if basis[i]=j then inc(r); end; if r=0 then begin for j:=1 to obch do begin neogr:=0; if d[j]>=0 then begin for i:=1 to m do if a[i,j]<0 then neogr:=neogr+1; end; if neogr=m then begin form2.Show; form2.lbl4.Caption:='Функция неограничена сверху!' ; form2.StrinGrid2StrinGrid. exit; end; end; if form2.lbl4.Caption<>'Функция неограничена сверху!' then begin //Form7.StringGrid1.RowCount:= //Form7.StringGrid1.ColCount:= //Form7.StringGrid1.Visible:= bpr:=0; k:=0; for j:=1 to n+KolDop do for i:=1 to n+KolDop do begin if j=basis[i] then begin k:=k+1; if b[j]>=0 then bpr:=bpr+1; end; end; if bpr=k then begin for i:=1 to m do for j:=1 to n+KolDop do Form2.StrinGrid2StrinGrid.
for i:=1 to m do begin Form2.StrinGrid2StrinGrid. end;
for j:=1 to n+KolDop do Form2.StrinGrid2StrinGrid. rez:=0; bpr:=0; for j:=1 to obch do begin if d[j]=0 then bpr:=bpr+1; end; if bpr>m then begin Form2.lbl4.Caption:=' Form2.lbl2.Caption:=Form2. for j:=1 to n+KolDop do begin bpr:=0; for i:=1 to m do begin if j=basis[i] then begin bpr:=1; rez:=rez+b[i]*f[j]; Form2.lbl2.Caption:=Form2. end; end; if bpr=0 then Form2.lbl2.Caption:=Form2. if j<>n+KolDop then Form2.lbl2.Caption:=Form2. end; Form2.lbl2.Caption:=Form2. for j:=1 to n+KolDop do begin r:=0; if d[j]=0 then begin for i:=1 to m do begin if j=basis[i] then r:=r+1; end; if r=0 then j0:=j; end; end; k:=0; for i:=1 to m do begin restr[i]:=0; if (a[i,j0]>0 ) and (b[i]>0) then begin restr[i]:=b[i]/a[i,j0] ; k:=k+1; end; end; if k<>0 then begin sr:=1000000000; i0:=1; for i:=2 to m do if restr[i]<>0 then if restr[i]<sr then begin sr:=restr[i]; i0:=i; end; basis[i0]:=j0; for i:=1 to m do for j:=1 to obch do begin if i=i0 then begin b1[i]:=b[i]/a[i0,j0]; if j<>j0 then begin A1[i,j]:=a[i,j]/a[i0,j0]; end; end else begin A1[i,j]:=(a[i,j]*a[i0,j0]-a[ b1[i]:=(b[i]*a[i0,j0]-b[i0]*a[ end; end; for i:=1 to m do begin if i<>i0 then a1[i,j0]:=0; end; a1[i0,j0]:=1; for i:=1 to m do for j:=1 to obch do begin a[i,j]:=A1[i,j]; b[i]:=b1[i]; end; end; for j:=1 to obch do begin d[j]:=0; for i:=1 to m do begin d[j]:=d[j]+f[basis[i]]*a[i,j]; end; d[j]:=d[j]-f[j]; end; form2.StrinGrid2StrinGrid. Form2.lbl2.Caption:=Form2. for j:=1 to n+KolDop do begin bpr:=0; for i:=1 to m do begin if j=basis[i] then begin bpr:=1; rez:=rez+b[i]*f[j]; Form2.lbl2.Caption:=Form2. end; end; if bpr=0 then Form2.lbl2.Caption:=Form2. if j<>n+KolDop then Form2.lbl2.Caption:=Form2. end; Form2.lbl2.Caption:=Form2.
end; if Form2.lbl4.Caption<>' begin Form2.lbl2.Caption:='( '; for j:=1 to n+KolDop do begin bpr:=0; for i:=1 to m do begin if j=basis[i] then begin bpr:=1; rez:=rez+b[i]*f[j]; Form2.lbl2.Caption:=Form2. end; end; if bpr=0 then Form2.lbl2.Caption:=Form2. if j<>n+KolDop then Form2.lbl2.Caption:=Form2. end; Form2.lbl2.Caption:=Form2. Form2.StrinGrid2StrinGrid. for i:=1 to m do Form2.StrinGrid2StrinGrid. for j:=1 to n+KolDop do Form2.StrinGrid2StrinGrid. Form2.StrinGrid2StrinGrid. Form2.StrinGrid2StrinGrid. if rb1.Checked then Form2.lbl3.Caption:='F max = ' else Form2.lbl3.Caption:='F min = ' ; Form2.lbl3.Caption:=Form2. end; end; end; end else begin Form2.lbl4.Caption:='Нет решения!!!'; Form2.StrinGrid2StrinGrid. end; Form2.Show; end; end. end.
unit Unit2;
interface
uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, Grids;
type TForm2 = class(TForm) lbl1: TLabel; lbl2: TLabel; lbl3: TLabel; lbl4: TLabel; StrinGrid2StrinGrid: TStringGrid; btn1: TButton; procedure btn1Click(Sender: TObject); private { Private declarations } public { Public declarations } end;
var Form2: TForm2;
implementation
{$R *.dfm}
procedure TForm2.btn1Click(Sender: TObject); begin Form2.Close; end;
end. |