Здавалка
Главная | Обратная связь

Формализация (алгоритм)



В основу алгоритма был взят алгоритм Крускала с изменением весов ребер на противоположные.

1) Замена знаков всех ребер на противоположные

2) Сортировка ребер по их весам

3) Инициализация набора деревьев, где каждая вершина в графе — это отдельное дерево

4) Перебор всех ребер от первого до последнего

5) Если у текущего ребра его вершины принадлежат разным поддеревьям, то эти поддеревья объединяются, а ребро добавляется к ответу


Реализация

Для реализации алгоритма использовался язык C# 6.0.

Разработка велась в среде Visual Studio 2015.

Структура проекта:

OperationResearchLib– библиотека содержащая функции и методы.

Список классов:

· Edge – класс-структура реализующий параметры для ребра

· Vertex – класс-структура реализующий параметры для вершины

· Kruskal – основной класс для решения задачи


 

OperationResearchLib:

Edge:

public class Edge : IComparable

{

 

private Vertex firstVertex, secondVertex;

private int cost;

 

public Vertex FirstVertex

{

get

{

return firstVertex;

}

}

 

public Vertex SecondVertex

{

get

{

return secondVertex;

}

}

 

public int Cost

{

get

{

return cost;

}

}

 

public Edge(Vertex v1, Vertex v2, int cost)

{

this.firstVertex = v1;

this.secondVertex = v2;

this.cost = cost;

}

 

 

public int CompareTo(object obj)

{

Edge edge = (Edge)obj;

return this.cost.CompareTo(e.cost);

}

 

}

 

Vertex:

public class Vertex

{

private int name;

 

public int Name

{

get

{

return name;

}

}

 

public int Rank { get; set; }

public Vertex Root { get; set; }

 

public Vertex(int name)

{

this.name = name;

this.Rank = 0;

this.Root = this;

}

 

internal Vertex GetRoot()

{

if (this.Root != this)

{

this.Root = this.Root.GetRoot();

}

return this.Root;

}

 

internal static void Join(Vertex firstRoot, Vertex secondRoot)

{

if (secondRoot.Rank < firstRoot.Rank)

{

secondRoot.Root = firstRoot;

}

else

{

firstRoot.Root = secondRoot;

if (firstRoot.Rank == secondRoot.Rank)

{

secondRoot.Rank++;

}

}

}

}

 


 

Kruskal:

public class Kruskal : IKruskal

{

 

IList<Edge> IKruskal.Solve(IList<Edge> graph, out int totalCost)

{

QuickSort(graph, 0, graph.Count - 1);

IList<Edge> solvedGraph = new List<Edge>();

totalCost = 0;

 

foreach (Edge ed in graph)

{

Vertex root1 = ed.V1.GetRoot();

Vertex root2 = ed.V2.GetRoot();

 

if (root1.Name != root2.Name)

{

totalCost += ed.Cost;

Vertex.Join(root1, root2);

solvedGraph.Add(ed);

}

}

return solvedGraph;

}

 

private void QuickSort(IList<Edge> graph, int left, int right)

{

int i, j, x;

i = left; j = right;

x = graph[(left + right) / 2].Cost;

 

do

{

while ((graph[i].Cost < x) && (i < right))

{

i++;

}

 

while ((x < graph[j].Cost) && (j > left))

{

j--;

}

 

if (i <= j)

{

Edge y = graph[i];

graph[i] = graph[j];

graph[j] = y;

i++;

j--;

}

}

while (i <= j);

 

if (left < j)

{

QuickSort(graph, left, j);

}

 

if (i < right)

{

QuickSort(graph, i, right);

}

}

}

Постановка задачи

Завод производит 4 вида продукции, обозначим через gi(x) – количество единиц сырья для изготовления x единиц продукции i-го вида, ci – доход от реализации единицы продукции i-го вида, пусть всего имеется 50 единиц сырья.

Требования

Определить сколько надо произвести единиц каждого типа, чтобы иметь максимальную прибыль, если доход от реализации единицы продукции заданы таблицей:

I
Ci


Реализация сырья на единицу продукции:

X G1 G2 G3 G4


Формализация (алгоритм)

1) Расчет соотношения для каждого товара:
количество единиц сырья / (цена реализации * количество единиц продукции)

2) Сравнение полученных результатов: выбираем элементы с минимальными затратами

3) Вычет из имеющегося количества сырья сырья ячейки с минимальными затратами

4) Поиск минимального значения затрат сырья на единицу дохода среди ячеек где затраты сырья не превышают оставшегося значения

 


 

Реализация

Для реализации алгоритма использовался язык C# 6.0.

Разработка велась в среде Visual Studio 2015.

Структура проекта:

OperationResearchLib– библиотека содержащая функции и методы.

Список классов:

· RawMaterial – класс реализующий параметры для элемента

· MaterialPrice – класс реализующий параметры для элементов реализации сырья на единицу продукции

· RawMaterialProduction – класс реализующий процесс поиска предметов

 


 

OperationResearchLib:

RawMaterial:

public class RawMaterial

{

private int type;

private double unitPrice;

 

private List<MaterialPrice> listOfPrices;

 

public RawMaterial()

{

 

}

 

public void SetPrices()

{

foreach(MaterialPrice material in listOfPrices)

{

material.RealisationPrice = unitPrice;

}

}

 

public List<MaterialPrice> ListOfPrices

{

get

{

return this.listOfPrices;

}

set

{

this.listOfPrices = value;

}

}

 

public double UnitPrice

{

get

{

return this.unitPrice;

}

set

{

this.unitPrice = value;

}

}

 

public int Type

{

get

{

return this.type;

}

set

{

this.type = value;

}

}

}

 


 

MaterialPrice:

public class MaterialPrice

{

private double neededRawMaterials;

private int perMaterials;

private double realisationPrice;

 

public MaterialPrice()

{

 

}

 

public double Difference

{

get

{

return neededRawMaterials/(realisationPrice*perMaterials);

}

}

 

public double RealisationPrice

{

get

{

return this.realisationPrice;

}

set

{

this.realisationPrice = value;

}

}

 

public int PerMaterials

{

get

{

return this.perMaterials;

}

set

{

this.perMaterials = value;

}

}

 

public double NeededRawMaterials

{

get

{

return this.neededRawMaterials;

}

set

{

this.neededRawMaterials = value;

}

}

}

 


 

RawMaterialProduction:

public static class RawMaterialsProduction

{

public static List<RawMaterial> GetListForProduction(List<RawMaterial> listOfMaterials, double MaximalWeight)

{

while(MaximalWeight < 0)

{

if(MaximalWeight - listOfMaterials.Single().ListOfPrices.Min().Difference >= 0)

{

MaximalWeight = MaximalWeight - listOfMaterials.Single().ListOfPrices.Min().Difference;

}

else

{

int position = listOfMaterials.Single().ListOfPrices.IndexOf(listOfMaterials.Single().ListOfPrices.Min(element => element.Difference));

listOfMaterials.Single().ListOfPrices.RemoveAt(position);

}

 

return listOfMaterials;

}

}

}

}

 







©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.