Министерствообразования и науки Российской Федерации
Федеральноеагентство по образованию
ИРКУТСКИЙГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
КафедраАвтоматизированных систем
ПОЯСНИТЕЛЬНАЯЗАПИСКА
к курсовомупроекту по дисциплине
ТеорияПринятия Решения
ЗАДАЧАСОСТАВЛЕНИЯ ОПТИМАЛЬНОГО ГРАФИКА РЕМОНТА ИНСТРУМЕНТА
Иркутск 2009 г
Содержание
1. ПОСТАНОВКА ЗАДАЧИ
2. ОБОСНОВАНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ
3. КРАТКИЕ СВЕДЕНИЯ О МЕТОДЕ РЕШЕНИЯ ЗАДАЧИ
3.1 ТАБЛИЧНЫЙ СИМПЛЕКС-МЕТОД
3.2 МЕТОД ИСКУССТВЕННЫХ ПЕРЕМЕННЫХ
4. ПРОВЕРКА ДОСТОВЕРНОСТИ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ
5. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ
6. ЛИСТИНГ ПРОГРАММЫ, РЕАЛИЗУЮЩИЙ АЛГОРИТМ ЗАДАЧИ
7. РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ
7.1 СИСТЕМНЫЕ ТРЕБОВАНИЯ
7.2 ОПИСАНИЕ ВОЗМОЖНОСТЕЙ
7.3 ОСНОВНОЕ ОКНО ПРОГРАММЫ
7.4 ГЛАВНОЕ МЕНЮ ПРОГРАММЫ
7.5 ИСПОЛЬЗОВАНИЕ
7.5.1 Ввод данных
7.5.2 Расчет графика ремонта и покупки
7.5.3 Результат работы программы
7.6 ИСПОЛЬЗОВАНИЕ ИНЖЕНЕРНОГО РЕЖИМА
8. РЕШЕНИЕ ЗАДАЧИ КУРСОВОЙ РАБОТЫ НА ПЭВМ ПО ИСХОДНЫМ ДАННЫМИНДИВИДУАЛЬНОГО ВАРИАНТА
9. СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
/>/>1. Постановка задачи
Пусть для выполнениянекоторой производственной программы, рассчитанной на /> последовательных дней,требуется к началу />го дня /> единиц специальногоинструмента, который к концу дня весь изнашивается.
Поэтому часть (или весь)этого инструмента в конце />го днясдается в обычный ремонт, часть (или весь) в срочный ремонт, а часть (или весь)изношенного инструмента может не сдаваться в ремонт, оставаясь, например, наскладе использованного инструмента. Обычный ремонт инструмента длится /> дней и стоит/> рублей за единицуинструмента, а срочный ремонт инструмента длится /> днейи стоит /> рублей за единицуинструмента. Новый инструмент стоит /> рублей.
Требуется так составитьграфик ремонта и покупки инструмента, чтобы при минимальных издержкахобеспечить предприятие инструментом в течение /> последовательныхдней.
Конкретные числовыеусловия задачи:
/> сутки
/> кол-во единиц
/> сутки
/> рублей
/> сутки
/> рублей
/> рублей 7
40 />
0 />
20 /> 3 2 2 4 6
Решить поставленнуюзадачу методом симплекс-таблиц, основанном на методе полного исключения Гаусса,применив для нахождения начального допустимого базисного решения методискусственных переменных.
Разработанный программный продуктдолжен обрабатывать числовые значения из заданного диапазона:
а) количествопоследовательных дней может быть или 6, или 7, или 8 дней; при этом день, когда/>, может быть любым изпринятого диапазона;
б) количествоединиц инструмента может быть взято из диапазона 15..45;
в)длительность обычного ремонта может быть или 2 суток, или 3 суток, или 4 суток;а его стоимость или 1 руб. за единицу инструмента, или 2 руб. за единицуинструмента, или 3 руб. за единицу инструмента;
г) длительностьсрочного ремонта может быть или 1 сутки, или 2 суток, или 3 суток; а егостоимость или 3 руб. за единицу инструмента, или 4 руб. за единицу инструмента,или 5 руб. за единицу инструмента;
д) стоимость нового инструментаили 5 руб. за единицу инструмента, или 6 руб. за единицу инструмента, или 7руб. за единицу инструмента.
модель решениезадача график ремонт
/>2.Обоснование математической модели
Пусть для выполнениянекоторой производственной программы, рассчитанной на семь последовательныхдней, требуется к началу />-го дня /> единиц специальногоинструмента, который к концу дня весь изнашивается, при этом r1=40; r2=40; r3=40; r4=40; r5=0; r6=20; r7=20 (5-ый день – выходной, поэтому r5=0). Часть (весь) изношенного инструмента в конце />-го дня может сдаваться вобычный ремонт, часть (весь) в срочный, а часть (весь) может не сдаваться времонт, оставаясь например на склад использованного инструмента. Так как 5-ыйдень является выходным, то в этот день производство и ремонтные службы неработают, поэтому математическая модель будет построена для 6 дней, а затемответ будет смещен относительно выходного (r1=40; r2=40; r3=40; r4=40; r5=20; r6=20 иj=6).
Пусть обычный ремонтодного инструмента длится /> дня истоит />руб., а срочный ремонтодного инструмента длится /> день истоит /> рублей. Кроме того, одинновый инструмент стоит /> рублей.
Введем следующиеобозначения:
/> число инструментов,покупаемых для использования в />й день;
/> число инструментов,сдаваемых в обычный ремонт в конце />-го дня;
/> число инструментов,сдаваемых в срочный ремонт в конце />го дня;
/>число изношенныхинструментов, оставшихся не сданными в ремонт к концу />го дня. Тогда число /> инструментов, поступающихв употребление в начале />го дня,состоит:
из /> инструментов, сданных вобычный ремонт /> дней назад иполученных из ремонта в конце />го дня;
из /> инструментов, сданных в срочныйремонт /> дней назад и полученных изремонта в конце />го дня;
из /> инструментов,приобретенных к началу />го дня, т.е.
/> />
где /> количество инструмента,купленного для использования в 1-й день; /> />, так как до началавыполнения производственной программы в ремонт не мог поступать использованныйинструмент и в первые /> дней (в данномслучае 3 дня) еще не поступит из ремонта в употребление ни одного инструмента,сданного даже в срочный ремонт, а в первые /> дней(в данном случае 4 дня) не поступит в употребление ни одного инструмента,сданного в обычный ремонт.
В конце />го дня окажутсяиспользованными /> инструментов,бывших в употреблении в этот день и /> инструментов,оставшихся не сданными в ремонт к концу />годня, т.е. />, из них /> единиц поступает в обычныйремонт, /> единиц — в срочный ремонти осталось не сданными в ремонт /> единицинструмента
/> />
При этом надо учесть, чтоинструмент, который возвратится из ремонта в конце />го(в данном случае 6-го дня) и позже, уже не понадобится. Поэтому еще за /> дней (в данном случае тридня) до конца программы не следует сдавать его в обычный ремонт, т.е.
/>
и за /> дней (в данном случае задва дня) до конца программы не следует сдавать его в срочный ремонт, т.е.
/>
За весь срок выполненияпроизводственной программы будет куплено /> инструментови израсходовано на это /> рублей;будет сдано в обычный ремонт /> инструментови израсходовано /> рублей; будетсдано в срочный ремонт /> инструментови израсходовано на это /> рублей.
Тем самым задачазаключается в минимизации общей стоимости издержек
/>
при ограничениях
/>
и условиях
/>
Для конкретных числовых значенийцелевая функция выглядит:
/>, при ограничениях:
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
xj/>0( j = 1(1)5 );
yj/>0( j = 1(1)2 );
zj/>0( j = 1(1)3 );
uj/>0( j = 1(1)6 );
Для удобства решения xj ( j=0(1)5 ); yj ( j=1(1)2 ); zj ( j=1(1)3 ); uj ( j=1(1)6 ) заменим на xk, где k=1(1)17. Ограничения примут вид:
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
xk/>0( k = 1(1)17)
Для решения задачиметодом искусственных переменных добавим в ограничения и целевую функциюпеременные x18, x19, x20, x21, x22:/>
/>,
при ограничениях:
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
xk/>0( k = 1(1)22)
/>3.Краткие сведения о методе решения задачи 3.1 Табличный симплекс-метод
Основная идеясимплекса-метода состоит в переходе от одного допустимого базисного решения кдругому таким образом, что значения целевой функции при этом непрерывновозрастают (для задач максимизации). Предположим, что ограничения задачисведены к такому виду, что в матрице А имеется единичная подматрица и всесвободные члены положительные. Иными словами, пусть матрица ограничений имеетвид
A1x1+...+Anxn+e1xn+e1xn+1+…+emxn+m=A0=[ai0],
где
/> . /> - единичный базис, ai0 ≥0
для всех i = 1, 2,..., n.Применим одну итерацию метода полного исключения к расширенной матрицеограничений Ap=[A1, ., An, e1, ., em,A0].
Преобразование Гауссаназывают симплексным преобразованием, когда направляющий элемент определяют последующим правилам:
a) направляющий столбец jвыбирают из условия, что в нем имеется хотя бы один положительный элемент;
б) направляющую строку iвыбирают так, чтобы отношение /> было минимально при условии, чтоaij>0.
При таком преобразованиив базис вводится вектор Aj и выводится вектор Аi. Теперьнадо определить, как выбрать вектор, вводимый в базис, чтобы при этом значениецелевой функции увеличилось.
Для этого используют такназываемые оценки векторов ∆j:
/> (2.2.21)
где Iб — множество индексов базисных векторов; xij — определяют из условия
/> (2.2.22)
Величины {∆j}равны симплекс-разностям для переменных {xj} с противоположнымзнаком. Следовательно, для того чтобы значение целевой функции увеличилось,необходимо выбрать направляющий столбец Аj с наибольшей по модулюотрицательной оценкой, то есть
/> .
Для решения задачисимплекс-методом на каждой итерации заполняют симплекс-таблицу 2.2.
Таблица 2.2.
/>
Последняя строка таблицы — индекснаяслужит для определения направляющего столбца. Ее элементы ∆jопределяют по формуле (2.2.21). Очевидно, для всех базисных векторов {Ai}i=1,.,m оценки ∆i=a0i=0.
Значение целевой функцииa00 определяется из соотношения
/> .
В столбце Bxзаписываем базисные переменные {xi} i= 1, ..., т. Их значенияопределяются столбиком свободных членов ai0, то есть xi =ai0, i=1, 2,.,m.
Направляющие строка Aiи столбец Aj указываются стрелками. Если в качестве направляющегоэлемента выбран aij, то переход от данной симплекс таблицы кследующей определяется соотношениями (2.2.16) — (2.2.18).
Алгоритм решения задачиЛП табличным симплексом-методом состоит из этапов.
1. Рассчитывают изаполняют начальную симплекс-таблицу с допустимым единичным базисом, включаяиндексную строку.
2. В качественаправляющего столбца выбирают Aj, для которого /> .
3. Направляющая строка Aівыбирают из условия
/>
4. Делают один шаг(итерацию) метода полного исключения Гаусса с направляющим элементом aij,для чего используют соотношения (2.2.16) — (2.2.18). В частности, элементыиндексной строки новой таблицы вычисляют в соответствии с формулой
/> /> l=1,2, ..., n.
Правильность вычисленийконтролируют по формулам непосредственного счета:
/> (2.2.23)
/> (2.2.24)
В столбце Bxновой таблицы заменяют xi на xj, а в столбце С ciна cj.
5. Если все a0l(k+1)≥0,l=1,.,n, то новое базисное решение xi= ai0(k+1),i € Iб(k+1) — оптимально. В противном случаепереходят к этапу 2 и выполняют очередную итерацию.
6. Второй, третий и четвертыйэтапы повторяют до тех пор, пока одна из итераций не закончится одним из двухисходов:
а) все a0l ≥0.Это признак (критерий) оптимальности базисного решения последнейсимплекс-таблицы;
б) найдется такой a0j=∆j3.2 Метод искусственных переменных
Пусть ограничения задачиЛП имеют вид Ax≤A0.
Если все bi ≥ 0, i = 1, 2,..., m, то свободныевекторы, образующие единичную подматрицу, составляют базис, а соответствующиеим переменные — начальное базисное решение.
В общем случае, когданекоторые ограничения имеют знак «≥», например ai1x1 + ai2x2 +...+ainxn≥bi, i=1,2,...., m,
то для приведения этихограничений к стандартной форме равенств свободные переменные надо вычесть.Тогда расширенная форма задачи будет иметь такой вид:
a11x1 + a12x2 +…+ a1nxn — 1xn+1 + 0xn+2 +…+0xn+m = b1;
a21x1+ a22x2 +…+ a2nxn +0xn+1-1xn+2+…+0xn+m = b2; (2.3.1)
….… .
am1x1+ am2x2 +...+ amnxn + 0xn+1 +0xn+2 +...-1xn+m = bm.
Свободные переменные {xn+1,…,xn+m}в этом случае уже невозможно использовать в качественачального базиса, так как xn+1>ci, (i = 1, 2, ..,m).
В случае решения задачминимизации искусственные переменные вводят в целевую функцию с большимиположительными коэффициентами (+М).
Знаки искусственныхпеременных xn+m+1,...,xn+m+kдолжны совпадать со знаками соответствующих свободныхчленов. Искусственные переменные образуют начальное базисное решение. Применивсимплекс-метод, необходимо вывести из базиса все искусственные переменные. Еслиудается доказать (или показать), что искусственные переменные полностью вывестииз базиса невозможно, то это означает, что задача не имеет решения, то есть ееограничения противоречивы.
/>4.Проверка достоверности полученных результатов
В общем случае проверкаполученных результатов после очередной итерации вычисления осуществляетсяследующим образом:
· Значения элементов строки,содержащей ∆j,вычисляются как элементы симплекс-таблицы (за исключением первойсимплекс-таблицы, где такие вычисления невозможны).
· Значения элементов строки,содержащей ∆j,вычисляются вторым способом, а именно по формулам непосредственного счета:
/>
/>
· Значения,полученные этими двумя способами, сравниваются. Если значения равны, значитвычисления проведены верно. В обратном случае, пользователю выдается сообщениеоб ошибке вычислений.
Дополнительнымсредством проверки достоверности является использование «Инженерного режима»,реализованного в программе. В данном режиме можно посмотреть каждый этапвычисления задачи.
В программе такжереализованы следующие методы обработки ошибок вычислений:
1. В случае еслипроисходит «зацикливание» программы (в данной программе, если количествоитераций больше 100), пользователю выдается сообщение об ошибке. Даннаяситуация может возникнуть в случае вырожденности матрицы – вектор, который былранее выведен из базиса, снова вводится в базис.
2. В случае если из базиса не удаетсявывести искусственные переменные, пользователю выдается сообщение об ошибке.Это означает, что ограничения задачи противоречивы и задача не имеет решения./>
5. Алгоритмрешения задачи
1. Проверка правильности ввода данных.
2. Построение симплекс-таблицы повведённым данным.
3. Добавление искусственных переменных.
4. Выбор направляющего элемента.
5. Деление направляющей строки нанаправляющий элемент.
6. Подсчет остальных элементов новойсимплекс таблицы.
7. Если во время решения достоверностьрезультатов нарушается, прекращаются дальнейшие вычисления, пользователювыдается информация об ошибке.
8. Если цикл расчета симплекс-таблиц непрекращается, принудительно прекращается процесс, пользователю выдаетсяинформация об ошибке.
9. Если из базисного решения не выведенывсе искусственные переменные, пользователю выдается информация об ошибке.
10. Если решение получено,результаты выводятся на экран.
/>/>6. Листинг программы, реализующий алгоритм задачи
const
m=25;
n=25;
type
TFirstKoef=array[1..m,1..n]of real; //начальная матрица коэфицентов
Simplex=array[1..m,1..n+m]of real; //новая матрица коэфицентов с искусственными переменными
FullSimplex=array[1..m+2,1..n+m+2] of real;
TE=array[1..n]of integer; //начальный неполный базис
TAddBas=array[1..m]of integer; //искусственные переменные вводимые для получения базиса
TFullBas=array[1..m+n] of integer; //полный базис
TTarFunc=array[1..60] of integer; //Целевая функция
var
Form1: TForm1;
Fkoef:TFirstKoef;
NumOfNewVars:integer;
fullBasis: TFullBas;
EngFull:FullSimplex;
F: File ofTrec;
TarFunc:TTarFunc;
{------------------------------------------------------------------}
function Sort(E: TE): TE;//сортировка массива типа ТЕ
var
i,k,tmp,nn,p,q:integer;
begin
p:=strtoint(Form1.Edit1.Text);
q:=strtoint(Form1.Edit3.Text);
nn:=2*(Form1.TrackBar1.Position-1)+(Form1.TrackBar1.Position-2-p)+(Form1.TrackBar1.Position-2-q);
for k:=nndownto 2 do
for i:=1 tok-1 do
ifE[i]>E[i+1] then
begin
tmp:=E[i];
E[i]:=E[i+1];
E[i+1]:=tmp;
end;
Sort:=E;
end;
{------------------------------------------------------------------}
functionNullCheck(j: integer; Fkoef: TFirstKoef): boolean; //функция проверки столбцов матрицына наличиевозможных базисных (одна «1» остальные «0»)
var
k,mm:integer;
Summ: real;
begin
Summ:=0;
mm:=2*(Form1.TrackBar1.Position-1);
for k:=1 to mmdo
Summ := Summ +Fkoef[k,j];
if summ=1 then
NullCheck:=true
else
NullCheck:=false;
end;
{------------------------------------------------------------------}
function AddVars(Basis:TE):TFullBas; //функция добавления столбцов сискусственными переменными
var
Base: TE;
newBase:TAddBas;
full:TFullBas;
j,k,count,inc,i,maxel,ncols,mm,nn,p,q:integer;
begin
p:=strtoint(Form1.Edit1.Text);
q:=strtoint(Form1.Edit3.Text);
mm:=2*(Form1.TrackBar1.Position-1);
nn:=1+2*(Form1.TrackBar1.Position-1)+(Form1.TrackBar1.Position-2-p)+(Form1.TrackBar1.Position-2-q);
for j:=1 to mmdo
newBase[j]:=0;
NumOfNewVars:=0;
Base:=Sort(Basis);
count:=1;
//код ниже реализуетпоиск и добавление искусственных переменных в случае когда их требуетсядобавить в начало и середину единичной матрицы
for j:=2 to nndo
begin
k:=Base[j]-Base[j-1];
if(k0) and (k1) then
begin
inc:=1;
for i:=1 tok-1 do
begin
newBase[count]:=Base[j-1]+inc;
count:=count+1;
inc:=inc+1;
NumOfNewVars:=NumOfNewVars+1;
end;
end;
end;
//код ниже реализуетпоиск искусственной переменной находящейся максимально близко к правому нижнемууглу единичной матрицы
maxEl:=newBase[1];
for i:=2 to mmdo
if(newBase[i]>newBase[i-1]) then
maxEl:=newBase[i];
ifmaxel
maxel:=Base[nn];
//если единичная матрицанеполная, то добавляются дополнительные переменные
if maxel
begin
ncols:=mm-maxel;
inc:=1;
for i:=countto ncols+count-1 do
begin
newBase[i]:=maxel+inc;
inc:=inc+1;
NumOfNewVars:=NumOfNewVars+1;
end;
end;
//запись векторасодержащего базисные переменные
for i:=1 to nndo
full[i]:=Basis[i];
j:=1;
for i:=nn+1 tonn+mm do
begin
full[i]:=newBase[j];
j:=j+1;
end;
AddVars:=full;
end;
{------------------------------------------------------------------}
functionArtificialVars(Fkoef: TFirstKoef):Simplex; //реализация метода искусственных переменных
var
i,j,mm,nn,p,q:integer;
Basis: TE;
Simp: Simplex;
begin
p:=strtoint(Form1.Edit1.Text);
q:=strtoint(Form1.Edit3.Text);
mm:=2*(Form1.TrackBar1.Position-1);
nn:=2*(Form1.TrackBar1.Position-1)+(Form1.TrackBar1.Position-2-p)+(Form1.TrackBar1.Position-2-q)+1;
for i:=1 to nndo
Basis[i]:=0;
for j:=1 to nndo //
for i:=1 to mm do //перебор начальнойматрицы коэфицентов по столбцам сверху вниз
begin;
Simp[i,j]:=Fkoef[i,j];
if Fkoef[i,j]=1 then//если в столбце есть еденица
if nullcheck(j,Fkoef)then //проверка является ли данный столбец базисным
Basis[j]:=i;
end;
fullBasis:=AddVars(Basis);//вызов функции для добавления искусственных столбцов чтобы получить базисноерешение
for j:=1 toNumOfNewVars do
for i:=1 to mmdo
ifi=fullBasis[nn+j] then
Simp[i,nn+j]:=1
else
Simp[i,nn+j]:=0;
ArtificialVars:=Simp;
end;
{------------------------------------------------------------------}
functionTForm1.SelectCol(fullSimp: FullSimplex):integer;
var
j,mm,nn,p,q,napravCol:integer;
maxdelt:real;
begin
p:=strtoint(Form1.Edit1.Text);
q:=strtoint(Form1.Edit3.Text);
nn:=2*(Form1.TrackBar1.Position-1)+(Form1.TrackBar1.Position-2-p)+(Form1.TrackBar1.Position-2-q);
mm:=2*(Form1.TrackBar1.Position-1);
maxdelt:=fullSimp[mm+2,4];
for j:=5 tonn+3+Numofnewvars do
iffullSimp[mm+2,j]>maxdelt then
begin
maxdelt:=fullSimp[mm+2,j];
napravCol:=j;
end;
ifmaxdelt>0 then
SelectCol:=napravCol
else
SelectCol:=-1;
end;
{------------------------------------------------------------------}
functionSelectRow(fullSimp: FullSimplex; Col: integer):integer;
var
i,mm,napravRow:integer;
minel,tmp:real;
begin
mm:=2*(Form1.TrackBar1.Position-1);
tmp:=1000;
for i:=2 tomm+1 do
if fullSimp[i,Col]>0then
begin
minel:=tmp;
tmp:=fullSimp[i,3]/fullSimp[i,Col];
if tmp
begin
minel:=tmp;
napravRow:=i;
end;
end;
SelectRow:=napravRow;
end;
{------------------------------------------------------------------}
functionDelta(fullSimp: FullSimplex;j: integer):real;
var
i,mm:integer;
delt: real;
begin
delt:=0;
mm:=2*(Form1.TrackBar1.Position-1);
for i:=2 to mmdo
delt:=delt+fullSimp[i,j]* fullSimp[i,1];
Delta:=delt-fullSimp[1,j];
end;
{------------------------------------------------------------------}
functionTForm1.NewTable(fullSimp: FullSimplex; TarFunc: TTarFunc):FullSimplex;
var
p,q,mm,nn,NapravCol,NapravRow,i,j:integer;
NapravEl:real;
NewTab: FullSimplex;
err: boolean;
begin
p:=strtoint(Form1.Edit1.Text);
q:=strtoint(Form1.Edit3.Text);
nn:=2*(Form1.TrackBar1.Position-1)+(Form1.TrackBar1.Position-2-p)+(Form1.TrackBar1.Position-2-q);
mm:=2*(Form1.TrackBar1.Position-1);
NapravCol:=SelectCol(fullSimp);
NapravRow:=SelectRow(fullSimp,NapravCol);
NapravEl:=fullSimp[NapravRow,NapravCol];
for j:=4 tonn+Numofnewvars+3 do
NewTab[1,j]:=TarFunc[j-3];
for j:=1 to 2do
for i:=1 tomm+1 do
NewTab[i,j]:=fullSimp[i,j];
NewTab[NapravRow,1]:=TarFunc[NapravCol-3];
NewTab[NapravRow,2]:=NapravCol-3;
for j:=3 tonn+Numofnewvars+3 do
NewTab[NapravRow,j]:=fullSimp[NapravRow,j]/NapravEl;
for i:=2 tomm+2 do
for j:=3 tonn+3+Numofnewvars do
ifiNapravRow then
NewTab[i,j]:=fullSimp[i,j]-NewTab[NapravRow,j]*fullSimp[i,NapravCol];
Err:=false;
for j:=3 tonn+3+Numofnewvars do
if(NewTab[mm+2,j]Delta(NewTab,j)) and (not Err) then
begin
err:=true;
NewTab[1,1]:=-1;
end;
NewTable:=NewTab;
end;
{------------------------------------------------------------------}
functionSimplexTables(Simp: Simplex):FullSimplex;
var
FS:FullSimplex;
i,j,p,q,mm,nn,a,b,c,k,basecount,iterCnt: integer;
err: boolean;
begin
p:=strtoint(Form1.Edit1.Text);
q:=strtoint(Form1.Edit3.Text);
nn:=2*(Form1.TrackBar1.Position-1)+(Form1.TrackBar1.Position-2-p)+(Form1.TrackBar1.Position-2-q);
mm:=2*(Form1.TrackBar1.Position-1);
a:=strtoint(Form1.Edit5.Text);
b:=strtoint(Form1.Edit2.Text);
c:=strtoint(Form1.Edit4.Text);
for i:=1 toForm1.TrackBar1.Position-1 do
TarFunc[i]:=a;
fori:=Form1.TrackBar1.Position to 2*Form1.TrackBar1.Position-3-p do
TarFunc[i]:=b;
fori:=2*Form1.TrackBar1.Position-2-p to 3*Form1.TrackBar1.Position-5-p-q do
TarFunc[i]:=c;
fori:=3*Form1.TrackBar1.Position-4-p-q to 4*Form1.TrackBar1.Position-6-p-q do
TarFunc[i]:=0;
fori:=4*Form1.TrackBar1.Position-5-p-q to 4*Form1.TrackBar1.Position-6-p-q+NumOfNewVars do
TarFunc[i]:=1000;
basecount:=0;
for i:=1 tomm+2 do
begin
for j:=1 tonn+NumOfNewVars+3 do
begin
if j>3 then
FS[1,j]:=Tarfunc[j-3];
if i>1 then
for k:=1 tom+n do
iffullBasis[k]=basecount then
begin
FS[i,1]:=tarFunc[k-1];
FS[i,2]:=k-1;
end;
if (i>1)and (j>2) then
FS[i,j]:=Simp[i-1,j-2];
end;
basecount:=basecount+1;
end;
for j:=3 tonn+3+Numofnewvars do
FS[mm+2,j]:=Delta(FS,j);
err:=false;
iterCnt:=0;
EngFull:=FS;
repeat
FS:=form1.NewTable(FS,TarFunc);
if FS[1,1]=-1then
err:=true;
ifiterCnt>1000 then
err:=true;
iterCnt:=iterCnt+1;
until(form1.SelectCol(FS)=-1) or (err);
for i:=2 tom+1 do
if(fs[i,1]=1000) then
err:=true;
if err then
begin
MessageDlg('При заданныхусловиях задача неразрешима!', mtError, [mbAbort],0 );
form1.n3.Enabled:=false;
form1.n6.Enabled:=false;
end;
SimplexTables:=FS;
end;
procedureTForm1.Button2Click(Sender: TObject);
begin
form1.Task;
end;
procedureTform1.Task;
var
i,j,p,q,inc,cntx,k,cnt,holiday:integer;
sklad: real;
Matr:TFirstKoef;
Tools:array[1..8] of integer;
NewTools:array[1..7] of integer;
Simp: Simplex;
Fsimp:fullsimplex;
begin
Tools[1]:=strtoint(Edit6.Text);
Tools[2]:=strtoint(Edit7.Text);
Tools[3]:=strtoint(Edit8.Text);
Tools[4]:=strtoint(Edit9.Text);
Tools[5]:=strtoint(Edit10.Text);
Tools[6]:=strtoint(Edit11.Text);
Tools[7]:=strtoint(Edit12.Text);
Tools[8]:=strtoint(Edit13.Text);
inc:=0;
for i:=1 to 8do
if Tools[i]=0then
holiday:=i;
for i:=1 to 7do
ifTools[i]0 then
NewTools[i]:=Tools[i+inc]
else
begin
inc:=1;
NewTools[i]:=Tools[i+inc]
end;
p:=strtoint(Edit1.Text);
q:=strtoint(Edit3.Text);
cntx:=2;
for i:=1 toTrackBar1.Position-1 do
begin
Matr[i,1]:=newTools[i];
if i-1>=0then
begin
Matr[i,cntx]:=1;
cntx:=cntx+1;
end;
end;
for i:=1 toTrackBar1.Position-1 do
begin
if i-p-1>0then
begin
Matr[i,cntx]:=1;
cntx:=cntx+1;
end;
end;
for i:=1 toTrackBar1.Position-1 do
begin
if i-q-1>0then
begin
Matr[i,cntx]:=1;
cntx:=cntx+1;
end;
end;
cntx:=TrackBar1.Position+1;
fori:=TrackBar1.Position to 2*(TrackBar1.Position-1) do
begin
Matr[i,1]:=newTools[i-(TrackBar1.Position-1)];
ifTrackBar1.Position-2-p >= i-(TrackBar1.Position-1) then
begin
Matr[i,cntx]:=1;
cntx:=cntx+1;
end;
end;
fori:=TrackBar1.Position to 2*(TrackBar1.Position-1) do
ifTrackBar1.Position-2-q >= i-(TrackBar1.Position-1) then
begin
Matr[i,cntx]:=1;
cntx:=cntx+1;
end;
fori:=TrackBar1.Position to 2*(TrackBar1.Position-1) do
begin
Matr[i,cntx]:=1;
ifi>TrackBar1.Position then
Matr[i,cntx-1]:=-1;
cntx:=cntx+1;
end;
Simp:=ArtificialVars(Matr);
fSimp:=SimplexTables(simp);
iffsimp[1,1]-1 then
begin
for i:=1 to StringGrid1.RowCountdo
for j:=1 to StringGrid1.ColCountdo
begin
StringGrid1.Cells[j,i]:='';
StringGrid1.Cells[0,i]:='День '+floattostr(i);
StringGrid2.Cells[j,i]:='';
StringGrid2.Cells[0,i]:='День '+floattostr(i);
end;
for j:=1 to 3do
begin
StringGrid1.Cells[j,holiday]:='Выходной';
StringGrid2.Cells[j,holiday]:='Выходной';
end;
cnt:=0;
For i:=1 toTrackBar1.Position-1 do
for j:=2 to4*Form1.TrackBar1.Position-6-p-q do
if(matr[i,j]=1) then
for k:=2 to2*TrackBar1.Position-1 do
if (fsimp[k,2]=j-1)then
begin
if i=holidaythen
cnt:=1;
ifj-1
StringGrid1.Cells[1,i+cnt]:=''+floattostr(fsimp[k,3]);
if(j-1>TrackBar1.Position-1) and (j-1
StringGrid1.Cells[2,i+cnt]:=''+floattostr(fsimp[k,3]);
if(j-1>2*Form1.TrackBar1.Position-3-p) and(j-1
StringGrid1.Cells[3,i+cnt]:=''+floattostr(fsimp[k,3]);
end;
for i:=1 toStringGrid1.RowCount do
for j:=1 to StringGrid1.ColCountdo
begin
if (StringGrid1.Cells[2,i]'')and (iholiday) then
if(i>=holiday) and (i-p-1
StringGrid2.Cells[2,i-p-2]:=StringGrid1.Cells[2,i]
else
StringGrid2.Cells[2,i-p-1]:=StringGrid1.Cells[2,i];
if (StringGrid1.Cells[3,i]'')and (iholiday) then
if(i>=holiday) and (i-q-1
StringGrid2.Cells[3,i-q-2]:=StringGrid1.Cells[3,i]
else
StringGrid2.Cells[3,i-q-1]:=StringGrid1.Cells[3,i];
end;
sklad:=0;
for i:=1 toStringGrid2.RowCount-1 do
begin
if (StringGrid2.Cells[2,i]'')and (iholiday) then
StringGrid2.Cells[1,i]:=''+floattostr(tools[i]
strtofloat(StringGrid2.Cells[2,i]));
if (StringGrid2.Cells[3,i]'')and (iholiday) then
StringGrid2.Cells[1,i]:=''+floattostr(tools[i]- strtofloat(StringGrid2.Cells[3,i]));
if (StringGrid2.Cells[3,i]'')and (iholiday) and (StringGrid2.Cells[2,i]'') then
StringGrid2.Cells[1,i]:=''+floattostr(tools[i]-strtofloat(StringGrid2.Cells[3,i])-strtofloat(StringGrid2.Cells[2,i]));
if(iholiday) and (StringGrid2.Cells[3,i]='') and (StringGrid2.Cells[2,i]='')then
StringGrid2.Cells[1,i]:=''+floattostr(tools[i]);
if(iholiday) then
sklad:=sklad+strtofloat(StringGrid2.Cells[1,i]);
end;
for i:=1 toStringGrid1.RowCount do
for j:=1 to StringGrid1.ColCountdo
begin
if (StringGrid1.Cells[j,i]='')or (StringGrid1.Cells[j,i]=' 0') then
StringGrid1.Cells[j,i]:='- ';
if (StringGrid2.Cells[j,i]='')or (StringGrid2.Cells[j,i]=' 0') then
StringGrid2.Cells[j,i]:='- ';
end;
Label20.Caption:='Суммарные затраты: '+floattostr(fsimp[2*(TrackBar1.Position-1)+2,3])+' у.е.';
Label21.Caption:='Инструментов на складе: '+ floattostr(sklad)+' шт.';
N6.Enabled:=true;
n3.Enabled:=true;
end;
end;
/>7. Руководство пользователя/> 7.1 Системные требования
Процессор: Pentium I или аналогичный AMD 400MHz и выше
ОЗУ: 64 Мб и более
ОС: Windows 98, 2000, ХР/>7.2 Описание возможностей
Данная программапредназначена для расчета графика ремонта и покупки инструмента, чтобы приминимальных издержках обеспечить предприятие инструментом в течении 6,7 или 8последовательных дней. Входными данными для программы являются: стоимостьпокупки нового инструмента (5,6,7 у.е.), срок и цена обычного ремонта ( 2, 3, 4дня за 1, 2, 3 у.е соответственно), срок и цена срочного ремонта ( 1, 2, 3 дняза 3, 4, 5 у.е соответственно), а также количество инструментов, требуемыхутром каждого дня (от 15 до 45 инструментов) и номер выходного дня, в которыекак производство так и ремонтные службы не работают.
В результатеработы программы будет составлен график оптимального ремонта и покупкиинструмента, представленный в виде двух таблиц (утро и вечер каждого дня).
В программеприсутствует «Инженерный» режим работы, с помощьюкоторого можно просмотреть этапы вычисления задачи. Этот режим предназначен дляспециалистов.
Данные, длякоторых разрабатывалась данная программа, введены по умолчанию. Поэтому длярасчета графика на основе этих данных достаточно нажать на кнопку «Рассчитать».
/>7.3 Основное окнопрограммы
/>/>7.4 Главное меню программы
Главное менюпрограммы содержит пункты: «Файл», «Режим»и «Помощь».
В пункте «Файл»находятся подпункты «Открыть», «Сохранить»и «Выход».
«Открыть» — служит для открытия файлов форматаmbs. Используется для открытия файлов с сохраненнымирезультатами расчетов в данной программе.
«Сохранить» — служит для сохранения файлов вформатеmbs. Используется для сохранения результатов расчетовв файл.
«Выход» — закрывает программу без сохранениярезультатов.
В пункте «Режим»находятся подпункты «Пользовательский» и «Инженерный».
«Пользовательский» — основной режим программы. Впрограмме используется этот режим по умолчанию.
«Инженерный» — режим проверки этапов вычисления.Предназначен для специалистов.
В пункте «Помощь»находятся подпункты «Помощь» и «Опрограмме „.
“Помощь» — содержит ссылку на данный файлсправки.
«Опрограмме „ — выводит окно с информацией о программе. />7.5 Использование
Для начала работы спрограммой запустите файлinstruments.exe./>7.5.1Ввод данных
Чтобы задатьтребуемое количество дней, переместите с помощью мыши соответствующий“ползунок» в области ввода начальных данных.
/>
Для тогочтобы задать продолжительность и стоимость обычного ремонта, на соответствующейпанели области ввода данных нажимайте с помощью мыши на стрелочки«вверх» или «вниз» в зависимости от того хотите выувеличить или уменьшить количество дней/стоимость.
/>
Для тогочтобы задать продолжительность и стоимость срочного ремонта, на соответствующейпанели области ввода данных нажимайте с помощью мыши на стрелочки«вверх» или «вниз» в зависимости от того хотите выувеличить или уменьшить количество дней/стоимость.
/>
Для тогочтобы задать стоимость покупки нового инструмента, на соответствующей панелиобласти ввода данных нажимайте с помощью мыши на стрелочки «вверх»или «вниз» в зависимости от того хотите вы увеличить или уменьшитьстоимость.
/>
Для тогочтобы задать количество инструментов, требуемых на каждый день, в области вводаданных нажимайте с помощью мыши на стрелочки «вверх» или«вниз» требуемого дня в зависимости от того хотите вы увеличить илиуменьшить количество инструментов. Под каждым полем ввода количества инструментовможно поставить с помощью щелчка мыши пометку, что именно этот день будетявляться выходным. На иллюстрации ниже 5ый день отмечен как выходной.
/>
/>7.5.2 Расчет графика ремонта и покупки
Для тогочтобы рассчитать график достаточно нажать на кнопку «Рассчитать»,находящуюся внизу главного окна программы.
/>/> 7.5.3 Результат работы программы
Результатработы программы будет выведен в области вывода результата в две таблицы.Первая таблица соответствует действиям утром каждого дня, а вторая — вечером.
/>
Например, каквидно из иллюстрации выше, утром первого дня нужно купить 40 инструментов, авечером все 40 инструментов сдать в срочный ремонт. Утром второго дня нужнокупить 40 инструментов, а вечером 20 инструментов сдать в обычный ремонт и 20 всрочный ремонт. И так далее./>7.6 Использование инженерного режима
В данномрежиме отображается симплекс-таблица, в которой находятся введенные на главнойформе данные. При нажатии на кнопку «Следующий шаг» производитсяпереход на следующую итерацию решения.
/>
/>8.Решение задачи курсовой работы на ПЭВМ по исходным данным индивидуальноговарианта
Исходные данные задачи:
/>
Начальная симплекс-таблица:
/>
Последняя симплекс-таблица:
/>
Вывод ответа:
/>
9. Список использованной литературы1. Зайченко, Ю.П. Исследование операций: учебное пособие /Ю.П.Зайченко. – 2-е изд. – Киев: Вища школа, 1979. – 392 с.2. Куцый, Н.Н. Математические методы системного анализа итеория принятия решений: пособие по курсовой работе / Н.Н. Куцый. – Иркутск:изд-во Иркутск гос. технич. ун-та, 2008. – 79 с.