//файл включения для векторных и матричных объектов
#include <winsys\geometry.h>
#include <classlib\arrays.h>
#include <values.h>
#pragma hdrstop
#include "matrix.h"
/*определяем типы "действительная матрица" и "действительный вектор"*/
typedef matrix<double> dmatrix;
typedef vector<double> dvector;
//определяем тип "массив точек"
typedef TArray<TPoint> Array;
/*набор функций, проверяющих, возможно ли движение в заданном направлении, то есть имеется ли в заданном направлении базисная ячейка*/
TPoint up(dmatrix x,TPoint cur)
{
for(long i=cur.X()-1;i>=0;i--)
if(x[i][cur.Y()]>0)/*если есть пункт, в который можно передвинуться*/
return TPoint(i,cur.Y());/*возвращаем его координаты*/
return TPoint(-1,-1);/*если не нашли - возвращаем признак ошибки*/
}
TPoint down(dmatrix x,TPoint cur)
{
for(long i=cur.X()+1;i<x.getm();i++)
if(x[i][cur.Y()]>0)
return TPoint(i,cur.Y());
return TPoint(-1,-1);
}
TPoint left(dmatrix x,TPoint cur)
{
for(long i=cur.Y()-1;i>=0;i--)
if(x[cur.X()][i]>0)
return TPoint(cur.X(),i);
return TPoint(-1,-1);
}
TPoint right(dmatrix x,TPoint cur)
{
for(long i=cur.Y()+1;i<x.getn();i++)
if(x[cur.X()][i]>0)
return TPoint(cur.X(),i);
return TPoint(-1,-1);
}
/*эта функция проверяет, есть ли пункт в заданном массиве – цикле*/
long exist(Array way,TPoint newpoint)
{
/*дополнительно проверяем координаты пункта на корректность*/
if(newpoint==TPoint(-1,-1))
return 1;
for(long i=0;i<way.GetItemsInContainer();i++)
if(way[i]==newpoint)
return 1;
return 0;
}
/*функция, определяющая, лежат ли три точки в одной строке (столбце)*/
inline long OnOneLine(TPoint p1, TPoint p2, TPoint p3)
{
return (p1.X()==p2.X()&&p1.X()==p3.X())||
(p1.Y()== p2.Y()&&p1.Y()==p3.Y());
}
/*часто повторяющиеся действия можно реализовать не только в виде функций, но и, к примеру, в виде макро. Например:
- в этом фрагменте проверяется, превышает ли число неудачных (тупиковых) попыток продвинуться в одном из четырёх возможных направлений количество этих направлений. Если это так, то пункт, из которого мы пытаемся пройти дальше, объявляется тупиковым (помечается нулём), затем изымается из массива пунктов цикла - пути перевозки груза, общее количество пунктов перевозки уменьшается на единицу и количество неудачных попыток объявляется нулевым*/
#define otkat if(tupik>4)\
{\
x[way[i].X()][way[i].Y()]=0;\
way.Detach(i);\
i--;\
tupik=0;\
}
/*- этот фрагмент выполняются после того, как определен следующий пункт, куда можно перевезти груз. При этом вначале количество неудачных попыток увеличивается на единицу - а вдруг идти в этот пункт нельзя? Затем выполняется проверка координат пункта на допустимость и наличие пункта в цикле (не провозили ли мы уже здесь груз в текущем цикле перевозок). Если всё Ок, пункт добавляется в цикл перевозок, количество неудачных попыток устанавливается в ноль, а количество пунктов перевозки в цикле увеличивается. Если же из текущей точки можно перейти в начальную, то цикл перевозок считается замкнутым и поиск новых пунктов можно прервать*/
#define addpoint tupik++;\
if(!exist(way,newpoint))\
{\
way.Add(newpoint);\
tupik=0;\
i++;\
if(i!=1&&(newpoint.X()==pq.X()\
||newpoint.Y()==pq.Y()))\
break;\
}
/*эта функция в заданной матрице перевозок ищет цикл, соответствующий перевозке из заданной точки*/
Array findway(dmatrix x, TPoint pq)
{
/*Вычёркивание тех пунктов, которые могут завести в тупик. Для этой цели вычёркиваем из матрицы все ряды, кроме строки p и столбца q, имеющие не более одной базисной клетки. Этот процесс повторяем до тех пор, пока есть что вычёркивать*/
for(long count=0,flag=1;flag;)
{
flag=0;/*вначале считаем, что вычёркивать нечего*/
for(long i=0;i<x.getm();i++)
if(i!=pq.X())
{
for(long j=count=0;j<x.getn();j++)
if(x[i][j]>0)
count++;
//если в строке только одна базисная клетка
if(count<2&&count)
{
flag=1;//взводим флаг вычёркивания
for(long j=0;j<x.getn();j++)
x[i][j]=0;//обнуляем текущую строку
}
}
//ту же операцию проводим со столбцами
for(long j=0;j<x.getn();j++)
if(j!=pq.Y())
{
for(long i=count=0;i<x.getm();i++)
if(x[i][j]>0)
count++;
if(count<2&&count)
{
flag=1;
for(long i=0;i<x.getm();i++)
x[i][j]=0;
}
}
}
long tupik=0;//количество тупиков обнуляем
/*объявляем массив для хранения координат пунктов, участвующих в цикле перевозок*/
Array way(0,0,20);
/*добавляем в массив первый (несуществующий пункт)*/
way.Add(pq);
for(long i=0;;)
{
/*пытаемся двигаться в различных направлениях так, чтобы составить цикл*/
otkat
TPoint newpoint=down(x,way[i]);
addpoint
else
{
otkat
newpoint=up(x,way[i]);
addpoint
}
otkat
newpoint=left(x,way[i]);
addpoint
else
{
otkat
newpoint=right(x,way[i]);
addpoint
}
}
/*если в цикле три точки лежат в одном ряду, вычёркиваем среднюю*/
for(long i=0;i<way.GetItemsInContainer()-2;i++)
if(OnOneLine(way[i],way[i+1],way[i+2]))
way.Detach(i+1);
return way;/*возвращаем цикл перевозок для данной точки*/
}
/*составляем матрицу методом "северо-западного угла", распределяя запасы а в соответствии с заявками b*/
dmatrix transp_getopor(dvector a, dvector b)
{
dmatrix x(a.getm(),b.getm());
for(long j=0,i=0;j<b.getm();)
{
if(a[i]>=b[j])//если запасы превышают заявки
{
x[i][j]=b[j];//удовлетворяем заявки
a[i]-=b[j]; //уменьшаем запасы
j++;/*переходим к обслуживанию следующей заявки*/
}
else//иначе
{
x[i][j]=a[i];/*удовлетворяем, сколько есть запасов*/
b[j]-=a[i]; //уменьшаем количество заявок
i++; //переходим к следующему запасу
}
}
return x;//возвращаем опорное решение
}
//передвижение груза по циклу в матрице перевозок
void movegruz(dmatrix &x,Array way)
{
/*определяем пункт с минимальной ценой в отрицательных вершинах цикла*/
double _min=x[way[1].X()][way[1].Y()];
for(long i=3;i<way.GetItemsInContainer();i++)
if(x[way[i].X()][way[i].Y()]<_min)
_min=x[way[i].X()][way[i].Y()];
/*в положительных вершинах количество груза увеличиваем, в отрицательных – уменьшаем*/
/*поиск оптимальной (минимизирующей стоимость) перевозки; возвращаемое значение - матрица, первые два столбца в которой указывают номер склада (от 0) и номер пункта назначения (тоже от 0), а последний - количество перевозимого груза ("из первого столбца во второй")*/
dmatrix transp_optim(dmatrix &x, dmatrix c)
{
long i,j,count;
for(i=0;i<x.getm();i++)
for(j=0;j<x.getn();j++)
if(!x[i][j])//если текущая ячейка пустая
{
Array way=findway(x,TPoint(i,j));/*ищем для неё цикл перевозки*/
if(getprice(c,way)<0)/*если найденный цикл имеет отрицательную цену, то мы можем улучшить положение дел,*/
{
movegruz(x,way);//перевезя по нему груз
j=x.getn();/*перезапускаем после перевозки цикл просмотра пустых ячеек*/
i=-1;
}
}
//подсчитываем количество перевозок
for(i=count=0;i<x.getm();i++)
for(j=0;j<x.getn();j++)
if(x[i][j])
count++;
dmatrix res(count,3);/*создаём матрицу, в которую заносим направление перевозки и количество груза*/
for(i=count=0;i<x.getm();i++)
for(j=0;j<x.getn();j++)
if(x[i][j])
res[count][0]=i, res[count][1]=j,
res[count][2]=x[i][j], count++;
return res;//возвращаем план перевозок
}
/*решение транспортной задачи. Эта функция принимает матрицу стоимости и вектора запасов и заявок (а и b)*/
