Формализация (алгоритм) ⇐ ПредыдущаяСтр 2 из 2
В основу алгоритма был взят алгоритм Крускала с изменением весов ребер на противоположные. 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 единиц сырья. Требования Определить сколько надо произвести единиц каждого типа, чтобы иметь максимальную прибыль, если доход от реализации единицы продукции заданы таблицей:
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 Все права принадлежат авторам размещенных материалов.
|