Как оптимизировать метод северно-западного угла с помощью метода потенциалов? Я написал (в методе минимальной стоимости этот же код работает), но проходит только три итерации, а потом выдает, что план оптимальный.
Метод минимальной стоимости считает правильно
, а метод С-З Угла (просто метод С-З считает правильно), а с оптимизацией нет.
Ответ должен быть при оптимизации 420 (посчитано на бумаге).
В проекте исправил оформление на русский язык и написаны комментарии к коду на русском
(проблемный участок: NorthWest.сs)
Сам код метода потенциалов:
//оптимизация методом потенциалов
public static void FindSolution()
{
bool isOptimal = false;
double[] Vpotent = new double[goods.GetLength(0)];
for (int i = 0; i < Vpotent.Length; i++)
{
Vpotent[i] = 99999;
}
Upotent = new double[dataGridView.ColumnCount - 1];
for (int i = 0; i < Upotent.Length; i++)
{
Upotent[i] = 99999;
}
//нахождение макс. тарифа в заполненых ячейках
double MaxCost = 0;
int maxV = 0;
int maxU = 0;
for (int i = 0; i < cost.GetLength(0); i++)
{
for (int j = 0; j < cost.GetLength(1); j++)
{
if (goods[i, j] != 0 && cost[i, j] > MaxCost)
{
MaxCost = cost[i, j];
maxV = i;
maxU = j;
}
}
}
//расчет потенциалов
Vpotent[maxV] = 0;
Upotent[maxU] = cost[maxV, maxU] - Vpotent[maxV];
for (int sania = 0; sania < cost.GetLength(1); sania++)
{
for (int i = 0; i < cost.GetLength(0); i++)
{
for (int j = 0; j < cost.GetLength(1); j++)
{
if (goods[i, j] != 0 && (Vpotent[i] == 99999 || Upotent[j] == 99999))
{
if (Vpotent[i] == 99999 & Upotent[j] == 99999)
continue;
if (Vpotent[i] != 99999)
{
for (int k = 0; k < cost.GetLength(1); k++)
{
if (goods[i, k] != 0)
{
Upotent[k] = cost[i, k] - Vpotent[i];
}
}
}
if (Upotent[j] != 99999)
{
for (int k = 0; k < cost.GetLength(0); k++)
{
if (goods[k, j] != 0)
{
Vpotent[k] = cost[k, j] - Upotent[j];
}
}
}
}
}
}
}
//анализ текущ. плана
//матрица дельта
double[,] delta = new double[cost.GetLength(0), cost.GetLength(1)];
double Maxdelta = 0;
int maxi = int.MaxValue, maxj = int.MaxValue;
//
for (int i = 0; i < cost.GetLength(0); i++)
{
for (int j = 0; j < cost.GetLength(1); j++)
{
if (goods[i, j] == 0)
{
delta[i, j] = Vpotent[i] + Upotent[j] - cost[i, j];
if (delta[i, j] > 0)
{
isOptimal = false;
if (delta[i, j] > Maxdelta)
{
Maxdelta = delta[i, j];
maxi = i;
maxj = j;
}
}
}
}
}
if (maxi == int.MaxValue && maxj == int.MaxValue)
{
MessageBox.Show("План оптимален!");
isOptimal = true;
summa.Text = "План оптимальний. Стоимость перевозки:" + CurrentSum;
}
else
{
double MaxCostInRowWithDelta = 0;
int MaxCostInRowWithDeltaI = 0, MaxCostInRowWithDeltaJ = 0;
//находим ячейку с товаром и макс. тарифом в строке с макс. дельта
for (int j = 0; j < goods.GetLength(1); j++)
{
if (goods[maxi, j] != 0 && cost[maxi, j] > MaxCostInRowWithDelta)
{
MaxCostInRowWithDelta = cost[maxi, j];
MaxCostInRowWithDeltaI = maxi;
MaxCostInRowWithDeltaJ = j;
}
}
//находим ячейку с товаром и макс. тарифом в столбце с макс. дельта
double MaxCostInCOLUMNWithDelta = 0;
int MaxCostInColumnWithDeltaI = 0, MaxCostInColumnWithDeltaJ = 0;
for (int i = 0; i < goods.GetLength(0); i++)
{
if (goods[i, maxj] != 0 && cost[i, maxj] > MaxCostInCOLUMNWithDelta)
{
MaxCostInCOLUMNWithDelta = cost[i, maxj];
MaxCostInColumnWithDeltaI = i;
MaxCostInColumnWithDeltaJ = maxj;
}
}
//находим, сколько товара мы можем переместить
double MaxAmountWeCanAfford ;
if (goods[MaxCostInColumnWithDeltaI, MaxCostInColumnWithDeltaJ] > goods[MaxCostInRowWithDeltaI, MaxCostInRowWithDeltaJ])
{
MaxAmountWeCanAfford = goods[MaxCostInRowWithDeltaI, MaxCostInRowWithDeltaJ];
}
else
{
MaxAmountWeCanAfford = goods[MaxCostInColumnWithDeltaI, MaxCostInColumnWithDeltaJ];
}
//перемещаем товар
goods[MaxCostInRowWithDeltaI, MaxCostInRowWithDeltaJ] -= MaxAmountWeCanAfford;
goods[maxi, maxj] += MaxAmountWeCanAfford;
goods[MaxCostInColumnWithDeltaI, MaxCostInColumnWithDeltaJ] -= MaxAmountWeCanAfford;
goods[MaxCostInColumnWithDeltaI, MaxCostInRowWithDeltaJ] += MaxAmountWeCanAfford;
//вывод результата
for (int i = 0; i < dataGridView2.RowCount - 1; i++)
{
for (int j = 0; j < dataGridView2.ColumnCount - 1; j++)
{
dataGridView2.Rows[i].Cells[j].Value = goods[i, j].ToString() + "(" + cost[i, j] + ")";
}
}
CurrentSum = 0;
for (int i = 0; i < goods.GetLength(0); i++)
for (int j = 0; j < goods.GetLength(1); j++)
if (goods[i, j] > 0)
CurrentSum += goods[i, j] * cost[i, j];
summa.Text = "План приближен к оптимальному. Стоимость перевозки: " + CurrentSum;
}
}
Вот полный проект:
https://drive.google.com/file/d/1XGbuR2LM4XYn3j4c6...
P.S. Просьба, не осуждать за код (я новичок), а просто подсказать, как сделать правильно.
Простой
