Венгерский метод. Содержание введение 4 математическая постановка задачи 5 определение опорного плана 8

Название	Содержание введение 4 математическая постановка задачи 5 определение опорного плана 8
Анкор	Венгерский метод
Дата	08.01.2022
Размер	105.72 Kb.
Формат файла
Имя файла	VENGERSKIJ_METOD.docx
Тип	Задача #326079
страница	5 из 5

1 2 3 4 5

3.3. Программная реализация задачи

Программа реализована на языке C# в среде программирования Microsoft Visual Studio. Листинг программы приводится в приложении 1.
Данная программа реализует венгерский метод для нахождения оптимального плана перевозок.

Код программы был написан с применением справочного материала из [4].

ЗАКЛЮЧЕНИЕ

В рамках данной курсовой работе были рассмотрены транспортные задачи и способ их решения с помощью венгерского метода, а также были рассмотрены разнообразные методы нахождения опорного плана.

В процессе была проделана работа по изучению математической и компьютерной литературы. Также был разобран и решен пример по заданной теме, на основе которого была написана программная составляющая работы.

СПИСОК ЛИТЕРАТУРЫ

Аттетков А.В., Галкин С.В., Зарубин В.С. Методы оптимизации. Москва: Изд-во МГТУ им. Н. Э. Баумана, 2003. 440 с.
Банди Б. Методы оптимизации. М.: Радио и связь, 1988. 128 с.
Габасов Р., Кириллова Ф.М. Методы линейного программирования. Минск: Изд-во БГУ им. В. И. Ленина, 1978. 238 с.
Шилдт Г. C# 4.0 Полное руководство. М.: Вильямс, 2019. 1056 с.

ПРИЛОЖЕНИЕ 1

Листинг программы
public partial class Form1 : Form

{

List<int> PInt = new List<int>();

List<int> VInt = new List<int>();

Listint>> VVInt = new Listint>>();

Listint>> VPInt = new Listint>>();

public Form1()

{

InitializeComponent();

}

private void Form1_Load(object sender, EventArgs e)

{

int taskCount = 4;

int emplCount = 4;

VVInt = new Listint>>(){new List<int>() {6,15,3,12,4,2},

new List<int>() {14,3,3,7,2,1},

new List<int>() {3,2,8,15,8,12},

new List<int>() {3,14,3,15,11,10},

new List<int>() {3,13,1,9,6,6},

new List<int>() {15,10,3,4,5,10}

};

#region Если на максимум

List<int> maxStrVals = VVInt.Select(str => str.Max()).ToList();

for (int i = 0; i < VVInt.Count; i++)

for (int j = 0; j < (VVInt.Sum(x => x.Count) / VVInt.Count); j++)

VVInt[i][j] = maxStrVals[i] - VVInt[i][j];

#endregion

VVInt = hungarian(VVInt);

foreach (List<int> i in VVInt)

{

foreach (int j in i)

richTextBox1.Text+=j.ToString() + " \t ";

richTextBox1.Text += "\r\n";

}

//MessageBox.Show("");

}

Listint>> hungarian(Listint>> matrix) {

try

{

// Размерыматрицы

int height = matrix.Count, width = matrix.Sum(x => x.Count) / height;

// Значения, вычитаемые из строк (u) и столбцов (v)

// VInt u(height, 0), v(width, 0);

List<int> u = new List<int>(height);

List<int> v = new List<int>(width);

for (int a = 0; a < height; a++)

u.Add(0);

for (int a = 0; a < width; a++)

v.Add(0);

// Индекс помеченной клетки в каждом столбце

List<int> markIndices = new List<int>(width);

for (int a = 0; a < width; a++)

markIndices.Add(-1);

// Будем добавлять строки матрицы одну за другой

int count = 0;

for (int i = 0; i < height; i++)

{

List<int> links = new List<int>(width) ;

List<int> mins = new List<int>(width) ;

List<int> visited = new List<int>(width) ;

for (int a = 0; a < width; a++)

{

links.Add(-1);

mins.Add(int.MaxValue);

visited.Add(0);

}

// Разрешение коллизий (создание "чередующейся цепочки" из нулевых элементов)

int markedI = i, markedJ = -1, j = 0;

while (markedI != -1)

{

// Обновим информацию о минимумах в посещенных строках непосещенных столбцов

// Заодно поместим в j индекс непосещенного столбца с самым маленьким из них

j = -1;

for (int j1 = 0; j1 < width; j1++)

if (visited[j1] != 1)

{

if (matrix[markedI][j1] - u[markedI] - v[j1] < mins[j1])

{

mins[j1] = matrix[markedI][j1] - u[markedI] - v[j1];

links[j1] = markedJ;

}

if (j == -1 || mins[j1] < mins[j])

j = j1;

}

// Теперь нас интересует элемент с индексами (markIndices[links[j]], j)

// Произведем манипуляции со строками и столбцами так, чтобы он обнулился

int delta = mins[j];

for (int j1 = 0; j1 < width; j1++)

if (visited[j1] == 1)

{

u[markIndices[j1]] += delta;

v[j1] -= delta;

}

else

{

mins[j1] -= delta;

}

u[i] += delta;

// Если коллизия не разрешена - перейдем к следующей итерации

visited[j] = 1;

markedJ = j;

markedI = markIndices[j];

count++;

}

// Пройдем по найденной чередующейся цепочке клеток, снимем отметки с

// отмеченных клеток и поставим отметки на неотмеченные

for (; links[j] != -1; j = links[j])

markIndices[j] = markIndices[links[j]];

markIndices[j] = i;

}

// Вернем результат в естественной форме

Listint>> result = new Listint>>();

for (int j = 0; j < width; j++)

if (markIndices[j] != -1)

result.Add(new List<int>() { markIndices[j], j });

return result;

}

catch (Exception ex)

{

MessageBox.Show(ex.Message);

return new Listint>>();

}

}

}

1 2 3 4 5