При большом количестве переменных, свойственном реальным задачам исследования операций и принятия решений, возникают значительные вычислительные трудности. Ввиду этого решение реальных задач практически не возможно без применения вычислительной техники. Задача применения компьютеров при вычислениях решения задач принятия решений существенно упрощается изначальной ориентацией алгоритмов решения на использование вычислительной техники.
В данном разделе приведены тексты программ на С++ (Borland C++ Builder) и блок-схемы реализованых алгоритмов основных задач исследования операций и принятия решений.
Void Simplex_Method(void)
/*
Процедура Simplex_Method() реализует алгоритм
симплекс метода.
Для работы ей необходимы переменные:
Cond –
количество имеющихся ресурсов
Var –
количество товаров, которые нужно производить
my_Array_simplex –
массив вещественных чисел размера (var+3)*(cond+2) – симплекс таблица
*/
{
while(!allMinus()) //Проверить условие
нахождения решения
{
int e_str= find_e_string(); //Найти
e-столбец
if(!e_str)
{
Application->MessageBox( "Сбой в работе алгоритма
при определении e-столбца",
"Критическая ошибка",
MB_OK|MB_ICONSTOP);
return;
}
for(int i= 1; i<= cond; i++)
my_Array_simplex[(i+1)*(var+3)+var+2]
=
(my_Array_simplex[(i+1)*(var+3)+e_str] == 0.0)?
MAXDOUBLE : my_Array_simplex[(i+1)*(var+3)+var+1]/
my_Array_simplex[(i+1)*(var+3)+e_str];
int
s_str= find_s_string(); //Найти s-строку
if(!s_str)
{
Application->MessageBox( "Сбой в работе алгоритма
при определении s-строки",
"Критическая ошибка",
MB_OK|MB_ICONSTOP );
return;
}
my_Array_simplex[e_str]= s_str; //Поменять местами
s-строку и e-столбец
my_Array_simplex[s_str*(var+3)]= e_str;
double
es= my_Array_simplex[s_str*(var+3)+e_str];
my_Array_simplex[s_str*(var+3)+e_str]= 1/es;
for(int i= 1; i<= var+1; i++)
if(i!= e_str)
my_Array_simplex[s_str*(var+3)+i] /= es;
for(int
i= 1; i<= cond+1; i++)
if(i!= s_str)
for(int j= 1; j<= var+1; j++)
if(j!= e_str)
my_Array_simplex[i*(var+3)+j] -=
my_Array_simplex[i*(var+3)+e_str] *
my_Array_simplex[s_str*(var+3)+j];
for(int i= 1; i<= cond+1; i++)
if(i!= s_str)
my_Array_simplex[i*(var+3)+e_str] /= (-es);
}
}
bool allMinus(void)
/*
Процедура allMinus() проверяет условие нахождения решения
Если решение найдено, она возвращает TRUE, иначе - FALSE
*/
{
for(int i=1; i<= var; i++)
if(my_Array_simplex[1*(var+3)+i]
>= 0)
return
false;
return
true;
}
int find_e_string(void)
/*
Процедура find_e_string() ищет e-столбец
Если e-столбец найден, она возвращает его
номер, иначе - 0
*/
{
double max= -MAXDOUBLE;
int e_string= 0;
for(int i=1; i<= var; i++)
if(my_Array_simplex[i]>=1 && my_Array_simplex[i]<=var)
if(my_Array_simplex[1*(var+3)+i] > max)
{
max= my_Array_simplex[1*(var+3)+i];
e_string= i;
}
return e_string;
}
int find_s_string(void)
/*
Процедура find_s_string() ищет s-строку
Если s-строка
найдена, она возвращает его номер, иначе - 0
*/
{
double min= MAXDOUBLE;
int s_string= 0;
for(int i=1; i<= cond; i++)
if(my_Array_simplex[(i+1)*(var+3)]>=1+var &&
my_Array_simplex[i]<=var+cond)
if((my_Array_simplex[(i+1)*(var+3)+var+2] < min) &&
(my_Array_simplex[(i+1)*(var+3)+var+2] > 0))
{
min= my_Array_simplex[(i+1)*(var+3)+var+2];
s_string= i+1;
}
return s_string;
}
void ResourceDestribution (void)
/*
Данная процедура
реализует алгоритм решения задачи
о распределении ресурсов
Для
работы ей необходимы следующие переменные:
sub_systems –
количество подсистем, между которыми
нужно распределить ресурсы;
resources – количество ресурсов;
Task10Grid – объект стандартного класса TstringGrid, представляющий собой таблицу распределения ресурсов
по подсистемам.
*/
{
for(int j=
1; j <= resources; j++) /* Постепенно наращиваем
количество ресурсов */
{
myList= new TList;
int *Array= new int[2];
Array[0]= Array[1]= 0;
vary_distribution(2, j, 2, j, Array); / *Определить все
возможные комбинации j ресурсов по двум подсистемам */
delete [] Array;
for(int i= 2; i <= sub_systems; i++) /*
Постепенно
наращиваем количество подсистем */
{
int *new_Array = new int[i];
int *null_Array = new int[i];
for(int q= 0; q < i; q++)
new_Array[q] = null_Array[q] = 0;
double max= 0;
for(int l= 0; l<
myList->Count; l++) /* Перебираем все
возможные комбинации распределений */
{
double
a= 0.0, b= 0.0;
int
*_array= (int *)myList->Items[l]; /* Текущая
комбинация */
if(i==2) /* Если мы
находимся на первом шаге – 2
подсистемы */
{
if(_array[0]) a=
StrToFloat(Task10Grid->
Cells[1][_array[0]]);
if(_array[1]) b= StrToFloat(Task10Grid->
Cells[2][_array[1]]);
}
else
{
if(_array[0]) a= StrToFloat(Task10Grid->
Cells[i+sub_systems-2][_array[0]]);
if(_array[1]) b= StrToFloat(Task10Grid->
Cells[i][_array[1]]);
}
if((a+b)>=max) /* Ищем максимальное значение
прибыли */
{
max= a+b;
if(i==2)
{
new_Array[0]= _array[1];
new_Array[1]= _array[0];
}
else
{
new_Array[0]= _array[1];
if(_array[0]) {
AnsiString comb= Task10Grid->
Cells[i+2*(sub_systems-1)-1][_array[0]];
for(int g=1, h= 1; g< i; g++, h++)
/* Формируем список для визуального
представления вновь найденного
оптимального распределения */
{
if(comb[h] == ',') h++;
new_Array[g]=
StrToInt(comb[h]);
}
}
else
for(int g=1; g< i; g++)
new_Array[g]= null_Array[g];
}
}
}
Task10Grid->Cells[i+sub_systems-1][j]=
FloatToStr(max);
AnsiString title;
for(int g= 0; g < i; g ++ )
{
title+= IntToStr(new_Array[g]);
if(g!=i-1) title+= ",";
}
Task10Grid->Cells[i+2*(sub_systems-1)][j]=
title;
delete [] new_Array;
}
for (int i = 0; i < myList->Count; i++)
{
int *d_array = (int *) myList->Items[i];
delete d_array;
}
delete myList;
}
}
void vary_distribution(int S, int R, int all_S, int all_R, int *Father)
/*
Данная
процедура генерирует все возможные
варианты
распределения ресурсов по подсистемам
Входными
параметрами для нее являются:
S – количество еще свободных подсистем
R – количество еще свободных ресурсов
all_S – общее количество подсистем
all_R – общее количество ресурсов
Father – массив для передачи текущего распределения
*/
{
if(S==1)
{
Father[S-1]= R;
myList->Add(Father);
return;
}
for(int i= 0; i <= R; i++)
{
int *Array= new int[all_S];
for(int k= 0; k < all_S; k++) Array[k]= Father[k];
Array[S-1]= i;
vary_distribution(S-1, R-i, all_S, all_R, Array);
}
delete [] Father;
}
void Floid(void)
/*
Данная процедура
реализует алгоритм Флойда.
Для
работы ей необходимы следующие переменные:
vertex – количество узлов в сети
m_Array – матрица, задающая топологию сети
*/
{
m_length= new double[vertex]; // Массив длин
маршрутов
m_vertex=
new AnsiString[vertex]; // Массив вершин
for(int
j= vertex; j>=0 ; j--)
{
if(j==vertex)
{
for(int
i= 0; i< vertex; i++)
{
m_length[i]=
MAXDOUBLE; // Бесконечность
m_vertex[i]=
"*";
}
m_length[vertex-1]=
0;
}
else
for(int
i= 0; i< vertex; i++)
{
if(MAXDOUBLE == m_Array[i*vertex+j] ||
MAXDOUBLE == m_length[j]) continue;
if(i==j)
continue;
if(m_length[j]<m_length[i]-m_Array[i*vertex+j])
{
m_length[i]=
m_Array[i*vertex+j]+m_length[j];
m_vertex[i]=
IntToStr(j+1);
}
else if(abs(m_Array[i*vertex+j]+m_length[j]-
m_length[i]) < 1E-10)
if(m_vertex[i]!=
"*")
m_vertex[i]=
IntToStr(j+1)+"/"+m_vertex[i];
}
}
/* Решение найдено*/
delete
[] m_Array;
delete
[] m_length;
delete
[] m_vertex;
}
void Ford_Falkerson(void)
/*
Данная
процедура реализует алгоритм Форда-Фалкерсона.
Для
работы ей необходимы следующие переменные:
vertex – количество узлов в сети
m_Array – матрица, задающая топологию сети
ListOfEdges –
список всех дуг в сети
*/
{
m_Array= new double[vertex*vertex];
ListOfEdges= new TList;
bool flag= true;
for(int i=
0; i< vertex; i++) /* Сформировать список всех дуг и
проверить наличие циклов в сети */
for(int j= 0; j< vertex; j++)
{
if(i>=j && m_Array[vertex*i+j]!=
MAXDOUBLE)
{
if(flag&&Application->MessageBox("Данный алгоритм работает только для ациклической сети. Преобразовать сеть в ациклическую?","Предупреждение", MB_ICONSTOP|MB_YESNO)= =IDNO)
{
delete [] m_Array;
return;
}
flag= false;
m_Array[vertex*j+i]= m_Array[vertex*i+j];
m_Array[vertex*i+j]= MAXDOUBLE;
}
if(m_Array[vertex*i+j]!= MAXDOUBLE)
{
Edge* edge= new Edge(i, j);
edge->state= ZERO;
edge->c=
m_Array[vertex*i+j];
edge->c_fact=
0;
ListOfEdges->Add(edge);
}
}
Nodes=
new int[vertex]; /* Сформировать массив узлов */
double
flow= 0;
bool
possible_to_increase= true;
bool
first_step= true;
end=
find_leaf(); /* Найти узел-сток */
root=
find_root(); /* Найти узел-исток */
while(possible_to_increase)
{
for(int i=
0; i< vertex; i++) Nodes[i]=
ZERO; /*
Сбросить
служебные массивы в исходное состояние */
for (int i = 0; i < ListOfEdges->Count; i++)
((Edge*) ListOfEdges->Items[i])->state=
ZERO;
double
delta= 0.0;
if(first_step)
{
delta= find_general_path(); /* Найти основной путь */
if(delta<=EPSILON)
first_step= false; /* Первый
шаг алгоритма закончен – найдены все основные пути */
}
else
{
delta= find_additional_path(); /* Найти
дополнительный
путь */
if(delta
<= EPSILON) possible_to_increase= false;
}
for(int i = 0; i < ListOfEdges->Count; i++) /* Скорректировать
потоки */
{
if(((Edge*)
ListOfEdges->Items[i])->state==PLUS)
((Edge*) ListOfEdges->Items[i])->c_fact+=
delta;
if(((Edge*)
ListOfEdges->Items[i])->state==MINUS)
((Edge*) ListOfEdges->Items[i])->c_fact-=
delta;
}
flow+= delta; /* Новый максимальный поток */
}
/* Решение найдено */
delete [] m_Array;
delete [] Nodes;
for (int i = 0; i < ListOfEdges->Count; i++)
delete (Edge *) ListOfEdges->Items[i];
delete
ListOfEdges;
}
double find_general_path()
/*
Данная процедура
осуществляет поиск основного пути в сети.
Возвращаемое
значение – улучшение потока при добавлении найденного пути. Если путь не
найден, то возвращается ноль.
*/
{
double delta= MAXDOUBLE;
find_next(root); /* Найти следующую
вершину в пути */
if(Nodes[end]!=PLUS) return 0; /* Путь не был найден */
for(int i = 0; i < ListOfEdges->Count; i++) /* Найти
приращение потока
*/
if(((Edge*)
ListOfEdges->Items[i])->state==PLUS)
if(((Edge*) ListOfEdges->Items[i])->c-((Edge*)
ListOfEdges->Items[i])->c_fact <
delta)
delta= ((Edge*) ListOfEdges->Items[i])->c-((Edge*)
ListOfEdges->Items[i])->c_fact;
if(delta
== MAXDOUBLE) return 0;
return delta;
}
void find_next(int current)
/*
Данная
процедура ищет следующую вершину для формируемого основного пути.
*/
{
Nodes[current]= PLUS;
if(current==end) return;
bool error= true;
int i;
for(i = 0; i < ListOfEdges->Count; i++)
{
if(((Edge*) ListOfEdges->Items[i])->org==current
&& ((Edge*) ListOfEdges->Items[i])->c - ((Edge*)
ListOfEdges->Items[i])->c_fact >
EPSILON
&&
Nodes[((Edge*)ListOfEdges->Items[i])->dest]==ZERO)
{
((Edge*) ListOfEdges->Items[i])->state=
PLUS;
error= false;
find_next(((Edge*)
ListOfEdges->Items[i])->dest);
if(Nodes[end]==PLUS) break;
error= true;
}
}
if(error)
{
Nodes[current]= ZERO;
for(int i = 0; i < ListOfEdges->Count; i++)
if(((Edge*) ListOfEdges->Items[i])->dest==current && ((Edge*)
ListOfEdges->Items[i])->state==PLUS)
{
((Edge*) ListOfEdges->Items[i])->state=
ZERO;
}
}
}
double find_additional_path()
/*
Данная
процедура осуществляет поиск дополнительного
пути в сети.
Возвращаемое
значение – улучшение потока при добавлении найденного пути. Если путь не
найден, то возвращается ноль.
*/
{
double delta= MAXDOUBLE;
find_end(root); /* Найти следующую вершину */
if(Nodes[end]!=PLUS) return 0; /* Путь не был найден */
for(int
i = 0; i < ListOfEdges->Count; i++) /* Найти
приращение
потока */
{
if(((Edge*) ListOfEdges->Items[i])->state==PLUS)
if(((Edge*) ListOfEdges->Items[i])->c-((Edge*)
ListOfEdges->Items[i])->c_fact <
delta)
delta= ((Edge*) ListOfEdges->Items[i])->c-((Edge*)
ListOfEdges->Items[i])->c_fact;
if(((Edge*)
ListOfEdges->Items[i])->state==MINUS)
if(((Edge*)
ListOfEdges->Items[i])->c_fact < delta)
delta= ((Edge*)
ListOfEdges->Items[i])->c_fact;
}
if(delta == MAXDOUBLE) return 0;
return delta;
}
void find_end(int current)
/*
Данная
процедура ищет следующую вершину для формируемого основного пути.
*/
{
Nodes[current]= PLUS; /* Пометить текущую вершину */
if(current==end) return;
bool error= true;
int i;
for(i = 0; i < ListOfEdges->Count; i++)
{
if(((Edge*) ListOfEdges->Items[i])->org==current
&& ((Edge*) ListOfEdges->Items[i])->c - ((Edge*)
ListOfEdges->Items[i])->c_fact >
EPSILON
&&
Nodes[((Edge*)ListOfEdges->Items[i])->dest]==ZERO)
{
((Edge*) ListOfEdges->Items[i])->state=
PLUS;
error= false;
find_end(((Edge*) ListOfEdges->Items[i])->dest);
/* Найти следующую */
if(Nodes[end]==PLUS) break;
i= -1; /* Путь не найден, но есть возможность
отклонить потоки */
error= true;
}
}
if(error) /*
Попытка найти дополнительный путь, отклонив
имеющийся поток */
for(int i = 0; i < ListOfEdges->Count; i++)
if(((Edge*)
ListOfEdges->Items[i])->dest==current &&
((Edge*)
ListOfEdges->Items[i])->c_fact > 0 &&
((Edge*)
ListOfEdges->Items[i])->state==ZERO)
{
((Edge*) ListOfEdges->Items[i])->state=
MINUS;
Nodes[((Edge*) ListOfEdges->Items[i])->org]=
MINUS;
find_end(((Edge*)
ListOfEdges->Items[i])->org);
if(Nodes[end]==PLUS) break;
i= -1;
}
}
int find_root()
/*
Поиск
вершины-истока. Исток определяется как
вершина, в которую не входит ни одна дуга.
*/
{
for(int j = 0; j < vertex; j++)
{
bool isRoot= true;
for(int i = 0; i < vertex; i++)
{
if (m_Array[vertex*i+j] != MAXDOUBLE)
{
isRoot = false;
break;
}
}
if(isRoot) return j;
}
return -1;
}
int find_leaf()
/*
Поиск
вершины-стока. Сток определяется как вершина, из которой не выходит ни одна
дуга.
*/
{
for(int i = 0; i < vertex; i++)
{
bool isLeaf= true;
for(int j = 0; j < vertex; j++)
{
if (m_Array[vertex*i+j] != MAXDOUBLE)
{
isLeaf = false;
break;
}
}
if(isLeaf) return i;
}
return -1;
}
void Destribution(void)
/*
Данная
процедура реализует алгоритм решения задачи о назначении.
Для
ее работы необходимы следующие переменные:
nodes – количество узлов в вычислительной сети
resources – количество ресурсов (задач)
С
– матрица потерь, размером [nodes*resources]
*/
{
int *C;
int *C_old;
C_old = new int[nodes*resources]; /* Копия массива С */
for(int i = 0; i < resources; i++)
for(int
j= 0; j < nodes; j++)
{
C_old[i*nodes + j] = C[i*nodes + j];
}
}
/*в
каждом столбце выберем min и вычтем его из всех элементов этого столбца*/
for(int j = 0; j < nodes; j++)
{
int MIN = MAXINT;
int num_min = 0;
for(int i= 0; i < resources; i++)
{
if(C[i*nodes + j] < MIN) {
MIN = C[i*nodes + j];
num_min = i;
}
}
for(int i= 0; i < resources; i++) C[i*nodes + j] -= MIN;
}
/*в каждой строке найдем min и вычтем его из
всех элементов этой строки*/
for(int i = 0; i < resources; i++)
{
int MIN = MAXINT;
int num_min = 0;
for(int j= 0; j < nodes; j++)
{
if(C[i*nodes + j] < MIN) {
MIN = C[i*nodes + j];
num_min = j;
}
}
for(int j= 0; j < nodes; j++) C[i*nodes + j] -= MIN;
}
while (0 == 0)
{
/*найти
max связку и определить индекс квадратности*/
int indexOfSquare = GetSquare(C, nodes, resources);
/*проверить
индекс квадратности*/
if(indexOfSquare == min(nodes, resources)){
int L = 0;
for(int i = 0; i < resources; i++)
for(int j = 0; j < nodes; j++) {
if(C[i*nodes+j] == -1) {
L += C_old[i*nodes+j];
}
}
}
break; //решение найдено
}
else
{
/*найти минимальное опорное множество*/
int *rows;
int *columns;
rows = new int[resources];
columns = new int[nodes];
FindNewBaseSet(C, nodes, resources, rows, columns);
/*из
всех непрочеркнутых элементов выбрать min*/
int MIN = MAXLONG;
for(int i = 0; i < resources; i++)
for(int j = 0; j < nodes; j++)
if(rows[i] == 1 && columns[i] == 0
&& C[i*nodes+j] > 0 &&
C[i*nodes+j] < MIN)
MIN
= C[i*nodes+j];
/*Вычесть
MIN из всех не прочеркнутых элементов и прибавить его ко всем дважды
прочеркнутым*/
for(int i = 0; i < resources;
i++)
for(int j = 0; j < nodes; j++) {
if(rows[i] == 1 && columns[j] == 0
&& C[i*nodes+j] > 0)
C[i*nodes+j]
-= MIN;
if(rows[i] == 0 && columns[j] == 1
&& C[i*nodes+j] > 0)
C[i*nodes+j]
+= MIN;
}
for(int i = 0; i < resources; i++)
for(int j = 0; j < nodes; j++) {
if(C[i*nodes+j] < 0) C[i*nodes+j] = 0;
}
delete [] rows;
delete [] columns;
}
}
delete [] C;
delete [] C_old;
}
int GetSquare(int *C, int nodes, int resources)
/*
Поиск
максимальной связки и определение индекса квадратности
Входные
параметры:
С - матрица
size
- размерность матрицы
Функция
возвращает индекс квадратности. В результате работы функции
в
матрице С обведенные нули становятся "-1", а вычеркнутые -
"-2"
*/
{
int SquareIndex = 0; //индекс квадратности
bool flag = true;
while(flag)
{
//находим
столбец или строку, содержащий min количество нулей
int MIN_ZERO = MAXLONG;
int Col = -1;
int Row = -1;
for(int j = 0; j < nodes; j++)
{
int zero= 0;
for(int i= 0; i < resources; i++) zero += (C[i*nodes+j] =
= 0)?1:0;
if(zero < MIN_ZERO && zero > 0) {
MIN_ZERO = zero;
Col = j;
Row = -1;
}
}
for(int j = 0; j < resources; j++)
{
int zero = 0;
for(int i= 0; i < nodes; i++)
zero+=(C[j*nodes+i] == 0)?1:0;
if(zero < MIN_ZERO && zero > 0) {
MIN_ZERO = zero;
Col = -1;
Row = j;
}
}
if(Col == -1 && Row == -1) break;
SquareIndex ++;
/*обводим
один из нулей*/
if(Row == -1) {
for(int i= 0; i < resources; i++)
if(C[i*nodes+Col] == 0) {
C[i*nodes+Col] = -1;
Row = i;
break;
}
} else {
for(int i= 0; i < nodes; i++)
if(C[Row*nodes+i] == 0) {
C[Row*nodes+i] = -1;
Col = i;
break;
}
}
/*вычеркиваем
все нули в Row и Col*/
for(int i= 0; i < resources; i++) {
if(C[i*nodes+Col] == 0) C[i*nodes+Col] = -2;
}
for(int i= 0; i < nodes; i++) {
if(C[Row*nodes+i] == 0) C[Row*nodes+i] = -2;
}
}
return SquareIndex;
}
void FindNewBaseSet(int *C, int nodes, int resources, int *rows, int
*columns)
/*
Поиск
минимального опорного множества
Входные
параметры:
С
- матрица
size
- размерность матрицы
rows
- массив меток для строк
columns
- массив меток для столбцов
В
результате работы поцедуры в матрицах rows и columns: "0" - не
помеченный элемент, "1" - помечен
*/
{
for(int i = 0; i < nodes; i++) columns[i] = 0;
for(int i = 0; i < resources; i++) rows[i] = 0;
/*пометить
"*" все строки, не содержащие обведенных нулей*/
for(int i = 0; i < resources; i++) {
int squaredZero = 0;
for(int j= 0; j < nodes; j++) {
if(C[i*nodes+j] == -1) squaredZero++;
}
if(!squaredZero) rows[i] = 1;
}
bool flag = true;
while(flag)
{
flag = false;
/*пометить "*" столбец, содержащий перечеркнутый ноль, хотя бы в одной из помеченных строк*/
for(int j = 0; j < nodes; j++) {
int marked = 0;
if(columns[j]) continue;
for(int i = 0; i < resources; i++) {
if(rows[i] == 1 && C[i*nodes + j] ==
-2){
marked++;
break;
}
}
if(marked > 0) {
columns[j] = 1;
flag = true;
break;
}
}
/*пометим
"*" строку, содержащую обведенный ноль, хотя бы в одном из помеченных
столбцов*/
for(int i = 0; i < resources; i++) {
int marked = 0;
if(rows[i]) continue;
for(int j = 0; j < nodes; j++) {
if(columns[j] == 1 && C[i*nodes+j] ==
-1) {
marked++;
break;
}
}
if(marked > 0) {
rows[i] = 1;
flag = true;
break;
}
}
}
}
int Laplas(double *_array, int cond, int var)
/*
Данная процедура
реализует критерий Лапласа.
Для
работы необходимы следующие переменные:
var – количество вариантов изделия
cond – количество условий, в которых будет функционировать
изделие
_array – матрица эффективности функционирования изделий в
различных условиях. Размерность матрицы – var * cond
*/
{
int opim_var=-1;
double max= -MAXDOUBLE;
for(int i=0; i< var; i++)
{
double sum= 0;
for(int j= 0; j<cond; j++)
sum+= fabs(_array[i*cond+j]);
sum= sum/var;
if(sum > max)
{
max= sum;
opim_var= i+1;
}
}
return opim_var;
}
int Vald(double *_array, int cond, int var)
/*
Данная процедура
реализует критерий Вальда.
Для
работы необходимы следующие переменные:
var – количество вариантов изделия
cond – количество условий, в которых будет функционировать
изделие
_array – матрица эффективности функционирования изделий в
различных условиях. Размерность матрицы – var * cond
*/
{
int opim_var=-1;
double max= -MAXDOUBLE;
for(int i=0; i< var; i++)
{
double min= MAXDOUBLE;
for(int j= 0; j<cond; j++)
if(fabs(_array[i*cond+j]) < min)
{
min= fabs(_array[i*cond+j]);
}
if(min > max)
{
max= min;
opim_var= i+1;
}
}
return opim_var;
}
int Savij(double *_array, int cond, int var)
/*
Данная процедура
реализует критерий Лапласа.
Для
работы необходимы следующие переменные:
var – количество вариантов изделия
cond – количество условий, в которых будет функционировать
изделие
_array – матрица эффективности функционирования изделий в различных
условиях. Размерность матрицы – var * cond
*/
{
int
opim_var=-1;
double
max= -MAXDOUBLE;
for(int
i=0; i< var; i++)
{
double
min= MAXDOUBLE;
double
max_in_str= -MAXDOUBLE;
for(int
j= 0; j<cond; j++)
if(fabs(_array[i*cond+j])
> max_in_str)
max_in_str=
fabs(_array[i*cond+j]);
for(int
j= 0; j<cond; j++)
if((fabs(_array[i*cond+j])-max_in_str)
< min)
{
min=
(fabs(_array[i*cond+j])-max_in_str);
}
if(min
> max)
{
max=
min;
opim_var=
i+1;
}
}
return
opim_var;
}
void Solve_task16(int *result, int size)
/*
Данная
процедура реализует алгоритм Джонсона.
Необходимы
следующие переменные:
size – количество массивов
myArray – массив времен выполнения операций (j) над массивами (i)
*/
{
double *temp= new double[3*size];
for(int i= 0; i< size; i++) /* Создаем новый массив времен, объединяя операции: 1 и 2, 2 и 3 */
{
temp[i*3]= -10;
temp[i*3+1]= myArray[i*3 + 0]+myArray[i*3 + 1];
temp[i*3+2]= myArray[i*3 + 1]+myArray[i*3 + 2];
result[i]= 0;
}
bool flag= true;
double min;
int resource, start, end, choice;
start= 0;
end= size-1;
while(flag)
{
flag= false;
min = MAXDOUBLE;
/* Находим минимальное время */
for(int i= 0; i< size; i++)
{
if(temp[i*3] < 0) {
flag= true;
if(temp[i*3+1] < min) {
resource = 1;
min = temp[i*3+1];
choice = i;
}
if(temp[i*3+2] < min) {
resource = 2;
min = temp[i*3+2];
choice = i;
}
}
}
if(!flag) break;
temp[choice*3] = 10;
if (resource == 1)
{
result[start]= choice+1; /* Помещаем в начало */
start++;
} else if (resource == 2)
{
result[end]=
choice+1; /* Помещаем в конец */
end--;
}
}
delete [] temp;
}
bool Test_Data(void)
/*
Данная
процедура проверяет допустимость заданной матрицы времен.
*/
{
double minA, maxB, minC;
minA= minC= MAXDOUBLE;
maxB= 0;
for(int i= 0; i < Task16_Form->StringGrid3->RowCount-1; i++)
{
if(myArray[i*3 + 0] < minA) minA= myArray[i*3 + 0];
if(myArray[i*3 + 1] > maxB) maxB= myArray[i*3 + 1];
if(myArray[i*3 + 2] < minC) minC= myArray[i*3 + 2];
}
if((minA < maxB) && (minC < maxB)) return false;
return true;
}
void solve_2(double *result, int size)
/*
Данная процедура решает задачу об
оптимальном размещении файлов при методе доступа к ним по кратчайшему маршруту.
Параметры:
result – массив результатов размерностью size*3, каждая
его строка – {длина/вероятность, номер}
size – число файлов
Для работы необходимы следующие переменные:
MyArray – массив исходных данных размерностью size*3, каждая его строка – {длина массива, вероятность
обращения, длина/вероятность}
*/
{
for(int i= 0; i< size; i++)
{
result[size+i]= i+1;
result[i]= myArray[i*3+2];
}
int start= 0;
int end= size-1;
bool inBeginning= false;
int *array= new int[size];
for(int i= 0; i< size; i++) array[i]= 0;
int I, max_elem= 1;
/* Сортируем файлы таким образом, чтобы
величина длина/вероятности не убывала бы от центра к периферии */
while(max_elem)
{
max_elem= 0;
double max= -MAXDOUBLE;
for(int i= 0; i< size; i++)
if(!array[(int)result[i+size]-1] &&
result[i] > max)
{
max_elem= result[i+size];
max= result[i];
I= i;
}
if(max_elem)
{
array[max_elem-1]= 1;
int
another;
if(inBeginning)
{
another= start;
++start;
}
else
{
another= end;
--end;
}
swap(result[I], result[another]);
swap(result[I+size],
result[another+size]);
inBeginning=
!inBeginning;
}
}
//I - адрес (номер) файла с минимальным Y =
длина/вероятность
int
S, S1, f, f1;
double
A, B;
bool
condTransp;
condTransp
= true;
S
= I -1;
f
= I;
while(0
== 0) {
if(S
>= 0 && condTransp) {
condTransp
= false;
S1
= S + 1;
A
= B = 0;
//подсчет A[S-1]
for(int
j= 0; j <= S-1; j++)
A+=
myArray[((int)result[j+size]-1)*3+1];
//подсчет B[S+2]
for(int
j= S+2; j < size; j++)
B+=
myArray[((int)result[j+size]-1)*3+1];
if((result[S]
- result[S1])*(B - A) < 0)
/* если условие транспозиции {(Y[S] -
Y[S1])*(B[S+2] –
A[S-1]) < 0} выполняется, то... */
{
condTransp = true;
//выполнить транспозицию пары S, S1
swap(result[S],
result[S1]);
swap(result[S+size],
result[S1+size]);
S
= S - 1;
}
}
else {
if(f
< size) {
f1
= f + 1;
A
= B = 0;
//подсчет A[f-1]
for(int
j= 0; j < f-1; j++)
A+=
myArray[((int)result[j+size]-1)*3+1];
//подсчет B[f+2]
for(int
j= f+2; j < size; j++)
B+=
myArray[((int)result[j+size]-1)*3+1];
if((result[f]
- result[f1])*(B - A) < 0)
/*если условие транспозиции {(Y[f] -
Y[f1])*(B[f+2] –
A[f-1]) < 0} выполняется, то... */
{
condTransp = true;
//выполнить транспозицию пары I, f1
swap(result[f],
result[f1]);
swap(result[f+size],
result[f1+size]);
S
= f - 1;
f
= f1;
} else {
//окончить вычисления
break;
}
} else {
//окончить вычисления
break;
}
}
}
}
void solve_1(double *result, int size)
/*
Данная процедура решает задачу об оптимальном
размещении файлов при методе доступа к ним по кратчайшему маршруту.
Параметры:
result – массив результатов размерностью size*3, каждая
его строка – {длина/вероятность, номер}
size – число файлов
Для работы необходимы следующие переменные:
MyArray – массив исходных данных размерностью size*3, каждая его строка – {длина массива, вероятность
обращения, длина/вероятность}
*/
{
for(int i= 0; i< size; i++)
{
result[size+i]= i+1;
result[i]= myArray[i*3+2];
}
selectionSort(result, size);
}
void selectionSort(double *array, int n)
/*
Сортировка
массива array, размером n
*/
{
for(int
i= 0; i < n-1; i++)
{
int
min= i;
for(int
j= i+1; j < n; j++)
if(array[j]
< array[min])
min= j;
swap(array[i],
array[min]);
swap(array[i+n], array[min+n]);
}
}
void swap(double &p1, double &p2)
/*
Данная
процедура меняет местами значения p1 и p2
*/
{
double P= p1;
p1=
p2;
p2=
P;
}
void Method_of_North_West_Corner(int
origin, int destination)
/*
Нахождение опорного плана методом
северо-западного угла.
origin – число отправителей
destination – число
получателей
Stocks – массив имеющихся у
отправителей запасов
Requests – массив запросов
получателей
Result – массив, в который
записывается решение задачи
*/
{
int *Temp_Requests; //копия массива запросов
int *Temp_Stocks; //копия массива запасов
Temp_Requests = new int[destination];
Temp_Stocks
= new int[origin];
for(int
i = 0; i < origin; i++) Temp_Stocks[i] = Stocks[i];
for(int
j = 0; j < destination; j++) Temp_Requests[j] = Requests[j];
for(int
i = 0; i < origin; i++)
for(int
j = 0; j < destination; j++) Result[i*destination+j] = 0;
int
current_Stock = 0;
for(int
j = 0; j < destination; j++){
if(Temp_Requests[j]
< Temp_Stocks[current_Stock]) {
Result[current_Stock*destination
+ j] = Temp_Requests[j];
Temp_Stocks[current_Stock]
-= Temp_Requests[j];
Temp_Requests[j]
= 0;
}
else {
Result[current_Stock*destination + j] =
Temp_Stocks[current_Stock];
Temp_Requests[j]
-= Temp_Stocks[current_Stock];
Temp_Stocks[current_Stock]
= 0;
if(Temp_Requests[j]
> 0) {
j--;
}
else if( j < destination - 1) {
/*Вырожденный
план перевозок. -1 – пустая
базисная переменная*/
Result[current_Stock*destination + j+1] = -1;
}
if(current_Stock < origin - 1)
current_Stock++;
}
}
delete
[] Temp_Requests;
delete
[] Temp_Stocks;
}
int Find_Cycle(int *Cycle, int i_start, int j_start, int ij, int origin,
int destination, int direction, int from, int first_dir)
/*
Функция
нахождения цикла. Возвращает количество груза, которое нужно переместить по
циклу.
Если
цикл не найден, то будет возвращен 0.
Cycle – массив, в который записывается найденный цикл
i_start , j_start – координаты начала цикла
ij – текущая позиция в массиве Results (ij = строка*столбец)
origin – количество отправителей
destination – количество получателей
direction – знак для данного направления движения (знак + или -)
from – предыдущее направление движения
first_dir – первое направление движения
Result – массив, в который записывается
решение задачи
*/
{
int
old_value= Cycle[ij];
Cycle[ij]
= direction;
int
result = 0;
int
Shift[4] = {-1, 1, -destination, destination};
/* извлечение текущих координат */
div_t x;
x
= div(ij, destination);
int
i = x.quot;
int
j = x.rem;
/* Попытка движения по всем четырем
направлениям для поиска продолжения цикла */
for(int side = 0; side < 4; side++)
{
/* Если данную позицию нельзя рассматривать как узел цикла, то направление должно сохраниться */
if(old_value == 2 && side != from) continue;
/* Проверка на вызов процедуры в первый раз */
int main_dir = (first_dir == -1)?side:first_dir;
/* Проверка на обратное движение */
if((from==0 && side==1) || (from==1 && side==0) || (from==2
&& side==3) || (from==3 && side==2))
continue;
/*
Присвоение узлу знака или признака
промежуточности (2) */
Cycle[ij] = (from != side)?direction:2;
if((j > 0 && side==0) || (j < destination-1 && side==1) || (i > 0
&& side==2) || (i < origin-1 && side==3))
{
if(ij+Shift[side]
== i_start*destination+j_start)
{
/* Цикл найден */
int min = MAXINT;
int sum = 0;
int
void_num = 0;
for(int
l= 0; l < origin; l++)
{
for(int
k=0; k< destination; k++)
{
if(Cycle[l*destination + k] == 1 ||
Cycle[l*destination + k] == -1)
{
/* В цикл входит пустая ячейка */
if(Result[l*destination + k] == 0)
void_num++;
if(Result[l*destination + k] <= 0
&& Cycle[l*destination + k]
== 1)
Result[l*destination + k] = 0;
if(Result[l*destination + k] <= 0 &&
Cycle[l*destination + k] == -1)
void_num++;
if(void_num
> 1) break;
/* Подсчет выгоды при использовании
найденного цикла */
sum += Cycle[l*destination + k]*
C[l*destination + k];
if( Result[l*destination + k] < min
&& Cycle[l*destination + k]
== -1 &&
Result[l*destination + k] != 0 &&
Result[l*destination
+ k] != -1)
min = Result[l*destination + k];
}
}
if(void_num
> 1) break;
}
if(min < MAXINT && sum < 0 && void_num <= 1
&& first_dir != side) return min;
}
if(Cycle[ij
+ Shift[side]] == 0 || Cycle[ij + Shift[side]] == 2)
{
/* Нужно продолжить поиск */
result = Find_Cycle( Cycle, i_start, j_start, ij +
Shift[side], origin, destination,
(Cycle[ij] != 2)?
(-direction):(direction), side, main_dir);
if(result
> 0) return result;
}
}
}
Cycle[ij]
= old_value;
return
0;
}
bool DropEpsilon(int *epsilonX, int *epsilonXX, int origin, int
destination)
/*
Уберем
фиктивные переменные (фиктивные переменные появляются при обнаружении
вырожденности плана)
epsilonX –массив фиктивных изменений запасов
epsilonXX – массив фиктивных изменений перевозок
origin – количество отправителей
destination – количество
получателей
Result – массив, в который записывается решение
С
– исходная матрица стоимостей перевозок
*/
{
bool
flag = false;
for(int
i=0; i < origin; i++)
{
if(epsilonX[i] > 0) /* Есть
фиктивная переменная – нужно
забрать 1фиктивную перевозку */
{
int
max = -MAXINT;
int max_j; //столбец, в котором будем
перемещать
"нулевой" поток
for(int j = 0; j< destination; j++)
if(Result[i*destination+j] > 0 && (C[i*destination+j] >
max || epsilonXX[i*destination+j] > 0))
{
max
= C[i*destination+j];
max_j
= (max != MAXINT)?j: ((C[i*destination+j]>
C[i*destination+max_j])?j:max_j);
if(epsilonXX[i*destination+j]
> 0) max = MAXINT;
}
if(max
< 0) continue;
int
delta = min(Result[i*destination+max_j], 1);
int
min = MAXINT;
int min_i; //строка, куда будем
перемещать
"нулевой" поток
for(int k= i+1; k < origin; k++)
if(C[k*destination+max_j] < min ||
epsilonXX[k*destination+max_j] < 0)
{
min
= C[k*destination+max_j];
min_i = (min != 0)?k:((epsilonXX[k*destination+max_j]
<epsilonXX[min_i*destination+max_j])?k:min_i);
if(epsilonXX[k*destination+max_j]
< 0) min = 0;
}
if(min
== MAXINT) continue;
Result[i*destination
+ max_j] -= delta;
Result[min_i*destination+max_j]
+= delta;
epsilonX[i]
-= delta;
epsilonX[min_i]
+= delta;
flag = true;
} else if(epsilonX[i] < 0) /* Есть
фиктивная переменная –
нужно добавить 1 фиктивную перевозку */
{
int
Min = MAXINT;
int min_j; //столбец, в котором будем
перемещать
"нулевой" поток
for(int j = 0; j< destination; j++)
if(Result[i*destination+j] > 0 && (C[i*destination+j] <
Min || epsilonXX[i*destination+j]<0))
{
Min
= C[i*destination+j];
min_j = (Min !=0)?j:((epsilonXX[i*destination+j]
<epsilonXX[i*destination+min_j])?j:min_j);
if(epsilonXX[i*destination+j]
< 0) Min = 0;
}
if(Min
== MAXINT) continue;
int
max = -MAXINT;
int max_i; //строка, откуда будем
перемещать
"нулевой" поток
for(int k= i+1; k < origin; k++)
if(C[k*destination+min_j]
> max)
{
max
= C[k*destination+min_j];
max_i = (max!=MAXINT)?k:((epsilonXX[k*destination+min_j]>
epsilonXX[max_i*destination+min_j])?k:max_i);
if(epsilonXX[k*destination+min_j] > 0) max =
MAXINT;
}
if(max
< 0) continue;
int
delta = min(Result[max_i*destination+min_j], 1);
Result[i*destination+min_j]
+= delta;
Result[max_i*destination+min_j]
-= delta;
epsilonX[i]
+= delta;
epsilonX[max_i]
-= delta;
flag
= true;
}
}
return
flag;
}
void Solv_Transport(int origin, int destination)
/*
Решить
задачу методом решения транспортной задачи
origin – количество отправителей
destination – количество получателей
Result – массив, в который записывается решение
*/
{
int *Cycle; /*Массив для хранения циклов */
int *epsilonX; /*Массив для хранения фиктивных запасов */
int *epsilonXX; /*Массив
для хранения
фиктивных перевозок */
epsilonXX = new int[origin*destination];
for(int
i = 0; i< destination*origin; i++) epsilonXX[i] = 0;
epsilonX
= new int[origin];
for(int
i=0; i < origin; i++) epsilonX[i] = 0;
/* Находим опорный план методом
северо-западного угла */
Method_of_North_West_Corner(origin, destination);
/* Улучшим план перевозок */
int flag = true;
while(flag)
{
flag=
false;
for(int
i = 0; i < origin; i++)
for(int
j = 0; j < destination; j++) {
/* Найти цикл для базисной переменной [i,j] */
if(Result[i*destination+j] != 0) {
Cycle
= new int[destination*origin];
for(int
ii = 0; ii < origin; ii++)
for(int
ji = 0; ji < destination; ji++)
Cycle[ii*destination
+ ji] = 0;
int
direction = -1;
int min = Find_Cycle(Cycle, i, j, i*destination+j, origin,
destination, direction, -1, -1);
for(int
row = 0; row < origin; row++)
for(int
col= 0; col < destination; col++)
if(Cycle[row*destination+col]
== -1) {
Result[row*destination+col]
-= min;
}
else if(Cycle[row*destination+col] == 1) {
Result[row*destination+col]
+= min;
}
int base = 0; //количество базисных клеток
for(int i = 0; i < destination*origin; i++)
if(Result[i]
!= 0) base++;
if(base
< (destination + origin -1))
/* добавить фиктивные базисные переменные */
for(int j = 0; j < destination; j++)
{
if(base
== (destination + origin -1)) break;
for(int
i = 0; i < origin; i++)
if(Result[i*destination+j]
== 0
&& Cycle[i*destination+j] ==
-1)
{
Result[i*destination+j]
= 1;
epsilonX[i]
++;
epsilonXX[i*destination+j]++;
int
k = 0;
for(k
= 0; k < origin; k++)
if(Result[k*destination+j] != 0
&& Cycle[k*destination+j] ==
1)
break;
Result[k*destination+j]
-= 1;
epsilonXX[k*destination+j]--;
epsilonX[k]
--;
base++;
break;
}
}
delete
[] Cycle;
if(min
> 0) {
flag=
true;
}
}
}
}
/*Удалить фиктивные перевозки и фиктивные запасы */
DropEpsilon(epsilonX, epsilonXX, origin, destination);
delete
[] epsilonX;
delete
[] epsilonXX;
}
void Solv_Pot(int origin, int destination)
/*
Решить
задачу методом потенциалов
origin – количество отправителей
destination – количество получателей
Result –массив, в который записывается решение
*/
{
int
*PaymentsA; //платежи Ai
int
*PaymentsB; //платежи Bj
int *PsevdoCost; //матрица псевдостоимостей
int *Cycle; //матрица для хранения найденного цикла
int *epsilonX; /*массив для хранения фиктивных запасов */
int *epsilonXX; /*массив для хранения фиктивных перевозок */
epsilonX = new int[origin];
for(int
i=0; i < origin; i++) epsilonX[i] = 0;
epsilonXX
= new int[origin*destination];
for(int
i = 0; i< destination*origin; i++) epsilonXX[i] = 0;
PaymentsA
= new int[origin];
PaymentsB
= new int[destination];
PsevdoCost
= new int[origin*destination];
/* Находим опорный план методом
северо-западного угла */
Method_of_North_West_Corner(origin, destination);
/* Улучшим план перевозок, если это
необходимо */
int flag= true;
while(flag)
{
flag=
false;
/* Определяем платежи для найденного плана
перевозок */
for(int i = 0; i < origin; i++) PaymentsA[i] = MAXINT;
for(int
j = 0; j < destination; j++) PaymentsB[j] = MAXINT;
PaymentsA[0]
= 0;
bool
error = true;
while(error)
{
error
= false;
for(int
i= 0; i < origin; i++)
for(int
j = 0; j < destination; j++)
{
if(Result[i*destination+j]
!= 0)
{
if(PaymentsB[j] == MAXINT
&& PaymentsA[i] == MAXINT){
error
= true;
continue;
}
if(PaymentsB[j]
== MAXINT)
PaymentsB[j]
= C[i*destination+j] –
PaymentsA[i];
if(PaymentsA[i]
== MAXINT)
PaymentsA[i]
= C[i*destination+j] –
PaymentsB[j];
}
}
}
/* подсчитаем псевдостоимости и проверим
условие
оптимальности */
for(int i = 0; i < origin; i++)
for(int
j = 0; j < destination; j++)
{
PsevdoCost[i*destination+j] = PaymentsA[i] +
PaymentsB[j];
if(Result[i*destination+j] == 0 && C[i*destination+j] <
PsevdoCost[i*destination+j])
flag
= true;
}
if(flag)
{
/* Переносы по циклам */
bool isMoved = false;
for(int
i = 0; i < origin; i++)
{
for(int
j = 0; j < destination; j++)
if(Result[i*destination+j] == 0 &&
C[i*destination+j] <
PsevdoCost[i*destination+j])
{
Cycle
= new int[destination*origin];
for(int
ii = 0; ii < origin; ii++)
for(int
ji = 0; ji < destination; ji++)
Cycle[ii*destination
+ ji] = 0;
int
direction = 1;
int min = Find_Cycle(Cycle, i, j,
i*destination+j, origin,
destination, direction, -1,
-1);
for(int
row = 0; row < origin; row++)
for(int
col= 0; col < destination; col++)
if(Cycle[row*destination+col]
== -1) {
Result[row*destination+col] -=
min;
} else if(Cycle[row*destination+col]
== 1) {
Result[row*destination+col] +=
min;
}
int base = 0; //количество
базисных клеток
for(int i = 0; i <
destination*origin; i++)
if(Result[i]
!= 0) base++;
if(base
< (destination + origin -1))
/* добавить фиктивные базисные
переменные */
{
for(int
j = 0; j < destination; j++)
{
if(base == (destination + origin -1))
break;
for(int
i = 0; i < origin; i++)
if(Result[i*destination+j] == 0 &&
Cycle[i*destination+j] == -1)
{
Result[i*destination+j]
= 1;
epsilonX[i]
++;
epsilonXX
[i*destination+j]++;
int
k = 0;
for(k
= 0; k < origin; k++)
if(Result[k*destination+j]
!= 0 && Cycle
[k*destination+j] == 1)
break;
Result[k*destination+j]
-= 1;
epsilonXX[k*destination+j]--;
epsilonX[k]
--;
base++;
break;
}
}
flag
= true;
}
delete
[] Cycle;
if(min
> 0) {
isMoved=
true;
break;
}
}
if(isMoved)
break;
}
if(!flag)
flag= !isMoved;
}
}
/*Удалить фиктивные перевозки и запасы */
DropEpsilon(epsilonX, epsilonXX, origin, destination);
delete
[] epsilonX;
delete
[] epsilonXX;
delete
[] PsevdoCost;
delete
[] PaymentsA;
delete
[] PaymentsB;
}
