Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
ИРКУТСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Кафедра Автоматизированных систем
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовому проекту по дисциплине
Теория Принятия Решения
ЗАДАЧА СОСТАВЛЕНИЯ ОПТИМАЛЬНОГО ГРАФИКА РЕМОНТА ИНСТРУМЕНТА
Иркутск 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. Обоснование математической модели
Пусть для выполнения некоторой производственной программы, рассчитанной на семь последовательных дней, требуется к началу -го дня единиц специального инструмента, который к концу дня весь изнашивается, при этом r
1
=40;
r
2
=40;
r
3
=40;
r
4
=40;
r
5
=0;
r
6
=20;
r
7
=20
(5-ый день – выходной, поэтому r
5
=0
). Часть (весь) изношенного инструмента в конце -го дня может сдаваться в обычный ремонт, часть (весь) в срочный, а часть (весь) может не сдаваться в ремонт, оставаясь например на склад использованного инструмента. Так как 5-ый день является выходным, то в этот день производство и ремонтные службы не работают, поэтому математическая модель будет построена для 6 дней, а затем ответ будет смещен относительно выходного (r
1
=40;
r
2
=40;
r
3
=40;
r
4
=40;
r
5
=20;
r
6
=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
+...+An
xn
+e1
xn
+e1
xn
+1+…+em
xn
+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
=a0
i
=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
=∆j
<0, что все элементы этого столбца arj
≤0, (r = 1, ., m). Это признак неограниченности целевой функции z = ∑cj
xj
на множестве допустимых решений задачи.
3.2 Метод искусственных переменных
Пусть ограничения задачи ЛП имеют вид Ax
≤A0
.
Если все bi
≥ 0, i = 1, 2,..., m, то свободные векторы, образующие единичную подматрицу, составляют базис, а соответствующие им переменные - начальное базисное решение.
В общем случае, когда некоторые ограничения имеют знак «≥», например ai
1
x1
+ ai
2
x2
+...+ain
xn
≥bi
, i=1,2,...., m,
то для приведения этих ограничений к стандартной форме равенств свободные переменные надо вычесть. Тогда расширенная форма задачи будет иметь такой вид:
a11
x1
+ a12
x2
+…+ a1
n
xn
- 1xn
+1
+ 0xn
+2
+…+0xn
+
m
= b1
;
a21
x1
+ a22
x2
+…+ a2n
xn
+0xn+1
-1xn+2
+…+0xn+m
= b2
; (2.3.1)
. . . . . . . . . . . . . . . . . . . . . .
am1
x1
+ am2
x2
+...+ amn
xn
+ 0xn+1
+ 0xn+2
+...-1xn+m
= bm
.
Свободные переменные {xn
+1
,…,xn
+
m
}в этом случае уже невозможно использовать в качестве начального базиса, так как xn
+1
<0,...,xn
+
m
<0. Поэтому в уравнения (2.3.1) дополнительно вводят искусственные переменные xn
+
m
+1
,…,xn
+
m
+
k
. Эти переменные не имеют ничего общего с реальной задачей, и потому их надо вывести из базиса как можно быстрее. Для этого перед началом итераций искусственным переменным в целевой функции приписывают для задач максимизации очень большие по модулю отрицательные коэффициенты (-М), где M>>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 of Trec;
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:=nn downto 2 do
for i:=1 to k-1 do
if E[i]>E[i+1] then
begin
tmp:=E[i];
E[i]:=E[i+1];
E[i+1]:=tmp;
end;
Sort:=E;
end;
{------------------------------------------------------------------}
function NullCheck(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 mm do
Summ := Summ + Fkoef[k,j];
if summ=1 then
NullCheck:=true
else
NullCheck:=false;
end;
{------------------------------------------------------------------}
functionAddVars(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 mm do
newBase[j]:=0;
NumOfNewVars:=0;
Base:=Sort(Basis);
count:=1;
//код ниже реализует поиск и добавление искусственных переменных в случае когда их требуется добавить в начало и середин
for j:=2 to nn do
begin
k:=Base[j]-Base[j-1];
if (k<>0) and (k<>1) then
begin
inc:=1;
for i:=1 to k-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 mm do
if (newBase[i]>newBase[i-1]) then
maxEl:=newBase[i];
if maxel<Base[nn] then
maxel:=Base[nn];
//если единичная матрица неполная, то добавляются дополнительные переменные
if maxel<mm then
begin
ncols:=mm-maxel;
inc:=1;
for i:=count to ncols+count-1 do
begin
newBase[i]:=maxel+inc;
inc:=inc+1;
NumOfNewVars:=NumOfNewVars+1;
end;
end;
//запись вектора содержащего базисные переменные
for i:=1 to nn do
full[i]:=Basis[i];
j:=1;
for i:=nn+1 to nn+mm do
begin
full[i]:=newBase[j];
j:=j+1;
end;
AddVars:=full;
end;
{------------------------------------------------------------------}
function ArtificialVars(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 nn do
Basis[i]:=0;
for j:=1 to nn do //
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 to NumOfNewVars do
for i:=1 to mm do
if i=fullBasis[nn+j] then
Simp[i,nn+j]:=1
else
Simp[i,nn+j]:=0;
ArtificialVars:=Simp;
end;
{------------------------------------------------------------------}
function TForm1.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 to nn+3+Numofnewvars do
if fullSimp[mm+2,j]>maxdelt then
begin
maxdelt:=fullSimp[mm+2,j];
napravCol:=j;
end;
if maxdelt>0 then
SelectCol:=napravCol
else
SelectCol:=-1;
end;
{------------------------------------------------------------------}
function SelectRow(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 to mm+1 do
if fullSimp[i,Col]>0 then
begin
minel:=tmp;
tmp:=fullSimp[i,3]/fullSimp[i,Col];
if tmp<minel then
begin
minel:=tmp;
napravRow:=i;
end;
end;
SelectRow:=napravRow;
end;
{------------------------------------------------------------------}
function Delta(fullSimp: FullSimplex;j: integer):real;
var
i,mm:integer;
delt: real;
begin
delt:=0;
mm:=2*(Form1.TrackBar1.Position-1);
for i:=2 to mm do
delt:=delt+fullSimp[i,j] * fullSimp[i,1];
Delta:=delt-fullSimp[1,j];
end;
{------------------------------------------------------------------}
function TForm1.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 to nn+Numofnewvars+3 do
NewTab[1,j]:=TarFunc[j-3];
for j:=1 to 2 do
for i:=1 to mm+1 do
NewTab[i,j]:=fullSimp[i,j];
NewTab[NapravRow,1]:=TarFunc[NapravCol-3];
NewTab[NapravRow,2]:=NapravCol-3;
for j:=3 to nn+Numofnewvars+3 do
NewTab[NapravRow,j]:=fullSimp[NapravRow,j]/NapravEl;
for i:=2 to mm+2 do
for j:=3 to nn+3+Numofnewvars do
if i<>NapravRow then
NewTab[i,j]:=fullSimp[i,j]-NewTab[NapravRow,j]* fullSimp[i,NapravCol];
Err:=false;
for j:=3 to nn+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;
{------------------------------------------------------------------}
function SimplexTables(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 to Form1.TrackBar1.Position-1 do
TarFunc[i]:=a;
for i:=Form1.TrackBar1.Position to 2*Form1.TrackBar1.Position-3-p do
TarFunc[i]:=b;
for i:=2*Form1.TrackBar1.Position-2-p to 3*Form1.TrackBar1.Position-5-p-q do
TarFunc[i]:=c;
for i:=3*Form1.TrackBar1.Position-4-p-q to 4*Form1.TrackBar1.Position-6-p-q do
TarFunc[i]:=0;
for i:=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 to mm+2 do
begin
for j:=1 to nn+NumOfNewVars+3 do
begin
if j>3 then
FS[1,j]:=Tarfunc[j-3];
if i>1 then
for k:=1 to m+n do
if fullBasis[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 to nn+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]=-1 then
err:=true;
if iterCnt>1000 then
err:=true;
iterCnt:=iterCnt+1;
until (form1.SelectCol(FS)=-1) or (err);
for i:=2 to m+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;
procedure TForm1.Button2Click(Sender: TObject);
begin
form1.Task;
end;
procedure Tform1.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 8 do
if Tools[i]=0 then
holiday:=i;
for i:=1 to 7 do
if Tools[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 to TrackBar1.Position-1 do
begin
Matr[i,1]:=newTools[i];
if i-1>=0 then
begin
Matr[i,cntx]:=1;
cntx:=cntx+1;
end;
end;
for i:=1 to TrackBar1.Position-1 do
begin
if i-p-1>0 then
begin
Matr[i,cntx]:=1;
cntx:=cntx+1;
end;
end;
for i:=1 to TrackBar1.Position-1 do
begin
if i-q-1>0 then
begin
Matr[i,cntx]:=1;
cntx:=cntx+1;
end;
end;
cntx:=TrackBar1.Position+1;
for i:=TrackBar1.Position to 2*(TrackBar1.Position-1) do
begin
Matr[i,1]:=newTools[i-(TrackBar1.Position-1)];
if TrackBar1.Position-2-p >= i-(TrackBar1.Position-1) then
begin
Matr[i,cntx]:=1;
cntx:=cntx+1;
end;
end;
for i:=TrackBar1.Position to 2*(TrackBar1.Position-1) do
if TrackBar1.Position-2-q >= i-(TrackBar1.Position-1) then
begin
Matr[i,cntx]:=1;
cntx:=cntx+1;
end;
for i:=TrackBar1.Position to 2*(TrackBar1.Position-1) do
begin
Matr[i,cntx]:=1;
if i>TrackBar1.Position then
Matr[i,cntx-1]:=-1;
cntx:=cntx+1;
end;
Simp:=ArtificialVars(Matr);
fSimp:=SimplexTables(simp);
if fsimp[1,1]<>-1 then
begin
for i:=1 to StringGrid1.RowCount do
for j:=1 to StringGrid1.ColCount do
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 3 do
begin
StringGrid1.Cells[j,holiday]:=' Выходной';
StringGrid2.Cells[j,holiday]:=' Выходной';
end;
cnt:=0;
For i:=1 to TrackBar1.Position-1 do
for j:=2 to 4*Form1.TrackBar1.Position-6-p-q do
if (matr[i,j]=1) then
for k:=2 to 2*TrackBar1.Position-1 do
if (fsimp[k,2]=j-1) then
begin
if i=holiday then
cnt:=1;
if j-1<=TrackBar1.Position-1 then
StringGrid1.Cells[1,i+cnt]:=' '+floattostr(fsimp[k,3]);
if (j-1>TrackBar1.Position-1) and (j-1<=2*Form1.TrackBar1.Position-3-p) then
StringGrid1.Cells[2,i+cnt]:=' '+floattostr(fsimp[k,3]);
if (j-1>2*Form1.TrackBar1.Position-3-p) and (j-1<=3*Form1.TrackBar1.Position-4-p-q) then
StringGrid1.Cells[3,i+cnt]:=' '+floattostr(fsimp[k,3]);
end;
for i:=1 to StringGrid1.RowCount do
for j:=1 to StringGrid1.ColCount do
begin
if (StringGrid1.Cells[2,i]<>'') and (i<>holiday) then
if (i>=holiday) and (i-p-1<=holiday) then
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 (i<>holiday) then
if (i>=holiday) and (i-q-1<=holiday) then
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 to StringGrid2.RowCount-1 do
begin
if (StringGrid2.Cells[2,i]<>'') and (i<>holiday) then
StringGrid2.Cells[1,i]:=' '+floattostr(tools[i]
strtofloat(StringGrid2.Cells[2,i]));
if (StringGrid2.Cells[3,i]<>'') and (i<>holiday) then
StringGrid2.Cells[1,i]:=' '+floattostr(tools[i]- strtofloat(StringGrid2.Cells[3,i]));
if (StringGrid2.Cells[3,i]<>'') and (i<>holiday) and (StringGrid2.Cells[2,i]<>'') then
StringGrid2.Cells[1,i]:=' '+floattostr(tools[i]-strtofloat(StringGrid2.Cells[3,i])-strtofloat(StringGrid2.Cells[2,i]));
if (i<>holiday) and (StringGrid2.Cells[3,i]='') and (StringGrid2.Cells[2,i]='') then
StringGrid2.Cells[1,i]:=' '+floattostr(tools[i]);
if (i<>holiday) then
sklad:=sklad+strtofloat(StringGrid2.Cells[1,i]);
end;
for i:=1 to StringGrid1.RowCount do
for j:=1 to StringGrid1.ColCount do
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 400 MHz и выше
ОЗУ: 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 с.