Разработка программного модуля

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ГОСУДАРСТВЕННОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«БЕЛОРУССКО-РОССИЙСКИЙ УНИВЕРСИТЕТ»

Кафедра «Автоматизированные системы управления»

Курсовая работа

Разработка программного модуля

по дисциплине «Системный анализ и исследование операций»

Выполнила: студентка гр. АСОИ-092

Кольцова А. С.

Руководитель: ст. преподаватель кафедры АСУ

Галинская И. Г.

Могилев 2012



Содержание

Введение

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

1.1 Математическая модель задачи

1.2 Входные данные

1.3 Выходные данные

1.4 Обработка ошибок

2. Проектирование программного модуля

2.1 Разработка структурной диаграммы программного модуляи её описание

2.2 Разработка пользовательского интерфейса

3. Реализация программного модуля

3.1 Код программы

4. Тестирование программного модуля

Заключение

Список использованных источников



Введение

Цель данной курсовой работы - разработать программный модуль для решения задачи о назначениях венгерским методом.

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

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

1.1 Математическая модель задачи

Задача о назначениях- это распределительная задача, в которой для выполнения каждой работы требуется один и только один ресурс (один человек, одна автомашина и т.д.), а каждый ресурс может быть использован на одной и только одной работе. То есть ресурсы не делимы между работами, а работы не делимы между ресурсами. Таким образом, задача о назначениях является частным случаем транспортной задачи. Задача о назначениях имеет место при назначении людей на должности или работы, автомашин на маршруты, водителей на машины, при распределении групп по аудиториям, научных тем по научно-исследовательским лабораториям и т.п. Идея метода была высказана венгерским математиком Эгервари и состоит в следующем. Строится начальный план, не удовлетворяющий в общем случае всем условиям задачи. Далее осуществляется переход к новому плану, более близкому к оптимальному. Последовательное применение этого приема за конечное число итераций приводит к решению задачи.

Исходные параметры модели задачи о назначениях:

1. n - количество ресурсов, m - количество работ.

2. = 1 - единичное количество ресурса (i = ), например: один работник; одно транспортное средство; одна научная тема и т.д.

3. = 1 - единичное количество работы (j = ), например: одна должность; один маршрут; одна лаборатория.

4. - характеристика качества выполнения работы с помощью ресурса . Например, компетентность i-го работника при работе на j-й должности; время, за которое i-е транспортное средство перевезет груз по j-му маршруту; степень квалификации i-й лаборатории при работе над j-й научной темой.

Искомые параметры:

1. - факт назначения или неназначения ресурса на работу .

, 0 - ; 1 - .

2. - целевая функция (ЦФ), общая (суммарная) характеристика качества распределения ресурсов по работам.

Общий вид транспортной задачи о назначениях представлен в таблице 1.

Таблица 1 - Общий вид транспортной матрицы задачи о назначениях

Ресурсы, Ai	Работы, Bj	Количество ресурсов
	B1	B2	…	Bm
A1	c11	c12	…	c1m	1
A2	c21	c22	…	c2m	1
…	…	…	…	…	…
An	cn1	cn2	…	cnm	1
Количество работ	1	1	…	1

Модель задачи о назначениях:

В некоторых случаях, например, когда- это компетентность, опыт работы, или квалификация работников, условие задачи может требовать максимизации ЦФ. В этом случае ЦФ заменяют на и решают задачу с ЦФ , что равносильно решению задачи с ЦФ

Специфическая структура задачи о назначениях позволила разработать так называемый венгерский методее решения. Классический венгерский метод, как и методы решения транспортной задачи, первоначально разрабатывался для ручных вычислений и сегодня, в основном, представляет только исторический интерес.

Описание алгоритма венгерского метода:

Шаг 1. Проводим предварительные преобразования матрицы C (получаем эквивалентную матрицу).

Формулы предварительных преобразований:

1) Преобразование в столбцах:

2) Преобразование в строках:

Шаг 2. Рассматривая столбцы матрицы сверху вниз поочередно, помечают звездочками нули таким образом, чтобы они не лежали в одной строке или одном столбце (отмечается первый попавшийся [но в соответствии с алгоритмом] в столбце ноль). Если количество поставленных звездочек равно n, то оптимальное решение найдено, и процесс решения закончен.

Шаг 3.

а) столбцы, в которых есть нули со звездочками, помечают сверху знаком «+», и далее эти столбцы считают занятыми;

б) просматривая строки матрицы слева направо, ищут незанятые нули. Незанятый ноль помечается знаком штрих, строку, в которой он находится, справа помечают знаком «+», и далее эту строку считают занятой. Если в строке нуля со штрихом есть ноль со звездочкой, то снимают знак занятости «+» со столбца, где находится ноль со звездочкой. Если в строке 0' нет нуля со звездочкой, переходят к шагу 5. Если в процессе поиска незанятых нулей оказалось, что незанятых нулей больше нет, а решение при этом не менялось, то переходят к шагу 4.

Шаг 4. Выбирается минимальный незанятый элемент (h). Число (h) вычитается из всех незанятых строк, и прибавляется ко всем занятым столбцам. Таким образом, получаем следующую эквивалентную матрицу. В новой матрице все пометки сохраняются. После этого повторяют выполнение шага 3 в части «б».

Шаг 5. Производим построение цепочки из нулей. Начиная от последнего отмеченного 0', двигаясь по столбцу к 0*, далее по строке к 0', и так далее, пока это возможно. Внутри цепочки знаки * снимаются, а вместо штрихов ставятся звездочки. После этого все знаки, кроме *, снимаются (штрихи, плюсы), и возвращаются к шагу 2.

1.2 Входные данные

Входными данными является матрица назначений.

1) При выборе матрицы из файла каждый ее элемент является целым положительным числом. Пользователь сам вводит размерность матрицы и ее элементы в текстовый файл;

2) При создании тестовой матрицы вводится ее размерность (число от 1 до 10) и затем она заполняется целыми случайными числами в программно заданном диапазоне.

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

1.3 Выходные данные

Результатом работы программы являются выходные данные:

1) Конечная расчетная матрица выводится в текстовое поле, доступ к которому пользователю запрещен.

2) Минимальное или максимальное значение целевой функции, которое выводится в текстовое поле, доступ к которому пользователю запрещен.

Искомые элементы исходной матрицы соответствуют позициям независимых нулей конечной матрицы и обозначаются в начальной матрице красным цветом. Сумма этих элементов дает целевую функцию.

1.4 Обработка ошибок

В данной программе предусмотрена обработка ошибок на случай ввода пользователем некорректных данных. Основные ошибки и реакция программы на них указаны в таблице 2.

Таблица 2 - Обработка ошибок

Причина возникновения ошибки	Реакция программы	Метод ее исправления
Ввод в текстовый файл любого символа вместо целого значения размерности матрицы	Сообщение «Некорректно записана размерность матрицы в файле!»	Повторно и корректно ввести размерность матрицы в файл
Ввод в текстовый файл любого символа вместо целого значения любого из элементов матрицы	Сообщение «Некорректно записан элемент матрицы в файле! »	Повторно и корректно ввести элементы матрицы в файл
Некорректный ввод значения в текстовое поле	Сообщение «Введенное число некорректно! Введите значение от 1 до 10!»	Заново ввести данные
Не выбрано, к чему стремится целевая функция	По умолчанию целевая функция будет стремиться к максимуму	Выбрать нужный пункт

2. Проектирование программного модуля

2.1 Структурная диаграмма программного модуля

Структурная диаграмма программного модуля представлена на рисунке 1.

Структурная диаграмма включает пять уровней. Первый уровень - Form1 - пользовательская форма с текстовыми полями для ввода и вывода данных, пятью кнопками и двумя переключателями. Второй уровень состоит из одиннадцати процедур, которые вызываются теми или иными событиями, связанными с Form1. Третий уровень состоит из двух процедур, вызываемых процедурами второго уровня. Четвертый уровень включает в себя семь процедур, вызываемых процедурами третьего уровня. Пятый уровень содержит девять процедур, вызываемых процедурами четвертого уровня. Процедуры, которыми заканчиваются ветви структурной диаграммы, дальнейшей детализации не требуют.

Рисунок 1 - Структурная диаграмма программного модуля

Form1() - содержит метод InitializeComponent(), который загружает компилированную страницу компонента.

Form1_Load() - процедура начальной инициализации пользовательской формы.

button1_Click() - процедура, срабатывающая при нажатии кнопки «Выбрать матрицу из существующего файла», которая считывает матрицу из файла и выводит ее в элемент dataGridView1.

button2_Click() - процедура, срабатывающая при нажатии кнопки «Создать тестовую матрицу», которая считывает размерность матрицы из поля textBox1, создает матрицу заданного размера, заполняет ее случайными числами и выводит в элемент dataGridView1.

button3_Click() - процедура, срабатывающая при нажатии кнопки «Выход», которая завершает работу приложения.

button4_Click() - процедура, срабатывающая при нажатии кнопки «Очистить», которая очищает все поля формы.

button5_Click() - процедура, срабатывающая при нажатии кнопки «Решить», которая выводит оптимальное решение в текстовое поле dataGridView2 и оптимальное значение целевой функции в текстовое поле textBox2.

textBox1_KeyPress() - процедура, срабатывающая при попытке ввода любого символа в текстовое поле textBox1, которая запрещает пользователю ввод в данное текстовое поле любых символов, кроме цифр.

textBox1_TextChanged() - процедура, срабатывающая при вводе значения в текстовое поле textBox1, которая ограничивает ввод значений в диапазоне от 1 до 10.

checkBox1_CheckedChanged() - процедура, срабатывающая при изменении состояния элемента checkBox1.

checkBox2_CheckedChanged() - процедура, срабатывающая при изменении состояния элемента checkBox2.

resetMaskandCovers() - процедура, обнуляющая все элементы вспомогательной матрицы и снимающая пометки столбцов и строк.

HungarianMethod() - процедура, содержащая пошаговый алгоритм венгерского метода.

step_one() - процедура, описывающая первый шаг алгоритма.

step_two() - процедура, описывающая второй шаг алгоритма.

step_three() - процедура, описывающая третий шаг алгоритма.

step_four() - процедура, описывающая четвертый шаг алгоритма.

step_five() - процедура, описывающая пятый шаг алгоритма.

step_six() - процедура, описывающая шестой шаг алгоритма.

step_seven() - процедура, описывающая седьмой шаг алгоритма. Выводит результат работы программы.

find_a_zero() - процедура, используемая на четвертом шаге алгоритма для нахождения невыделенных нулей.

star_in_row() - процедура, используемая на четвертом шаге алгоритма для определения, находится ли в строке нуль, отмеченный звездочкой.

find_star_in_row() - процедура, используемая на четвертом шаге алгоритма для нахождения номера столбца, содержащего нуль со звездочкой.

find_star_in_col() - процедура, используемая на пятом шаге алгоритма для определения номера строки, содержащей нуль со звездочкой.

find_prime_in_row() - процедура, используемая на пятом шаге алгоритма для определения номера столбца, содержащего нуль со штрихом.

augment_path() - процедура, используемая на пятом шаге алгоритма для построения цепочки.

clear_primes() - процедура, используемая на пятом шаге алгоритма для снятия отметок со столбцов и строк.

erase_primes() - процедура, используемая на пятом шаге алгоритма для снятия штриха с нуля.

find_smallest() - процедура, используемая на шестом шаге алгоритма для определения минимального невыделенного элемента.



2.2 Разработка пользовательского интерфейса

При запуске приложения открывается основная форма (рисунок 2):

Рисунок 2 - Основная форма приложения

Пользователь может выбрать исходную матрицу назначений из файла. Для этого нужно нажать на кнопку «Выбрать матрицу из существующего файла», после чего откроется окно выбора файла (рисунок 3):

Рисунок 3 - Выбор матрицы из существующего файла

При нажатии кнопки «Открыть» или двойном щелчке мышью по файлу матрица из файла выведется в текстовое поле dataGridView1. После чего нужно выбрать, к чему стремится целевая функция, отметив нужный пункт галочкой, и нажать кнопку «Решить». Решение, представляющее собой матрицу - оптимальный вариант назначений, выведется в текстовое поле dataGridView2, а оптимальное значение целевой функции - в текстовое поле textBox2 (рисунок 4, рисунок 5). При этом искомые значения, дающие в сумме целевую функцию, будут выделены в исходной матрице красным цветом. Текстовые поля dataGridView1, dataGridView2 и textBox2 доступны пользователю только для чтения, изменять их нельзя.

Рисунок 4 - Результат работы приложения при стремлении целевой функции к максимуму



Рисунок 5 - Результат работы приложения при стремлении целевой функции к минимуму

В случае, если размерность матрицы или какой-либо из ее элементов в файле не будут являться числами, приложение выдаст сообщение об ошибке и необходимо будет повторно и корректно ввести данные в файл (рисунок 6, рисунок 7).

Рисунок 6 - Сообщение об ошибке при некорректном вводе значения размерности матрицы в файле

Рисунок 7 - Сообщение об ошибке при некорректном вводе какого-либо элемента матрицы в файл

Данное приложение также позволяет работать с тестовой матрицей. Для этого нужно ввести значение размерность матрицы в текстовое поле textBox1 и нажать кнопку «Создать тестовую матрицу». Ввод любых символов, кроме цифр, в текстовое поле textBox1 запрещен. Также размерность матрицы ограничена диапазоном от 1 до 10, поэтому при попытке пользователя ввести другое число приложение выдаст сообщение об ошибке (рисунок 8). После нажатия кнопки «Решить» матрица - оптимальный вариант назначений выведется в текстовое поле dataGridView2, а оптимальное значение целевой функции - в текстовое поле textBox2. Результат работы приложения показан на рисунках 9 и 10.



Рисунок 8 - Сообщение об ошибке при попытке ввести число, не входящее в диапазон возможных значений размерности матрицы

Рисунок 9 - Результат работы приложения при создании тестовой матрицы



Рисунок 10 - Результат работы приложения при создании тестовой матрицы

Данное приложение позволяет работать с матрицами размерностью 1х1 и 2х2. Результаты работы приложения показаны на рисунках 11 и 12.

Рисунок 11 - Результат работы приложения с матрицей 1х1

Рисунок 12 - Результат работы приложения с матрицей 2х2

При нажатии кнопки «Очистить» все поля формы будут очищены и форма примет первоначальный вид (см. рисунок 2).

При нажатии кнопки «Выход» приложение завершит работу.



3. Реализация программного модуля

3.1 Код программы

using System;

using System.IO;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

namespace WindowsFormsApplication1

{

public partial class Form1 : Form

{

public static int[,] Matrix = new int[10, 10];

public static int[,] M = new int[10, 10];

public static int[,] path = new int[21, 2];

public static int[] RowCover = new int[10];

public static int[] ColCover = new int[10];

public static int nrow;

public static int ncol;

public static int path_count = 0;

public static int path_row_0;

public static int path_col_0;

public static int asgn = 0;

public static int step;

public Form1()

{

InitializeComponent();

}

private void Form1_Load(object sender, EventArgs e)

{

dataGridView1.Rows.Clear();

dataGridView2.Rows.Clear();

textBox1.Clear();

textBox2.Clear();

}

private void button1_Click(object sender, EventArgs e)

{

dataGridView1.Rows.Clear();

dataGridView2.Rows.Clear();

textBox2.Clear();

string fname, text;

OpenFileDialog Fd = new OpenFileDialog();

Fd.Title = "Выберитефайл";

Fd.InitialDirectory = @"L:\";

Fd.Filter = "текстовые.файлы (*.txt)|*.txt;|Всефайлы|*.*";

bool flag = false;

while (flag == false)

{

if (Fd.ShowDialog() == DialogResult.OK)

{

fname = Fd.FileName;

int n;

StreamReader reader = new StreamReader(fname);

if (!Int32.TryParse(reader.ReadLine(), out n))

{

MessageBox.Show("Некорректно записана размерность матрицы в файле!");

flag = false;

}

else

{

dataGridView1.RowCount = n;

dataGridView1.ColumnCount = n;

dataGridView2.RowCount = n;

dataGridView2.ColumnCount = n;

flag = true;

}

if (flag == true)

{

nrow = 0;

do

{

text = reader.ReadLine();

if (text != null)

{

ncol = 0;

foreach (string subString in text.Split(' '))

{

if (subString.Length > 0)

{

if (!Int32.TryParse(subString, out Matrix[nrow, ncol]))

{

MessageBox.Show("Некорректно записан элемент матрицы в файле!");

flag = false;

break;

}

else

{

Matrix[nrow, ncol] = Int32.Parse(subString);

dataGridView1.Columns[ncol].Width = 15;

dataGridView1[ncol, nrow].Value = Matrix[nrow, ncol];

ncol += 1;

flag = true;

}

}

}

if (flag == false) break;

nrow += 1;

}

} while (text != null);

reader.Close();

break;

}

}

else break;

}

}

private void button2_Click(object sender, EventArgs e)

{

dataGridView1.Rows.Clear();

dataGridView2.Rows.Clear();

textBox2.Clear();

if (!string.IsNullOrEmpty(textBox1.Text))

{

nrow = int.Parse(textBox1.Text);

ncol = int.Parse(textBox1.Text);

dataGridView1.RowCount = nrow;

dataGridView1.ColumnCount = ncol;

dataGridView2.RowCount = nrow;

dataGridView2.ColumnCount = ncol;

Random r = new Random(10);

for (int i = 0; i < dataGridView1.RowCount; i++)

{

for (int j = 0; j < dataGridView1.ColumnCount; j++)

{

Matrix[i, j] = r.Next(10);

dataGridView1.Columns[j].Width = 15;

dataGridView1.Rows[i].Cells[j].Value = Matrix[i, j].ToString();

}

}

}

}

private void button5_Click(object sender, EventArgs e)

{

for (int i = 0; i < dataGridView1.RowCount; i++)

{

for (int j = 0; j < dataGridView1.ColumnCount; j++)

{

dataGridView1[j, i].Style.ForeColor = Color.Black;

Matrix[i, j] = Convert.ToInt32(dataGridView1.Rows[i].Cells[j].Value);

}

}

resetMaskandCovers();

step = 1;

HungarianMethod();

}

private void HungarianMethod()

{

bool done = false;

while (!done)

{

switch (step)

{

case 1:

step_one(ref step);

break;

case 2:

step_two(ref step);

break;

case 3:

step_three(ref step);

break;

case 4:

step_four(ref step);

break;

case 5:

step_five(ref step);

break;

case 6:

step_six(ref step);

break;

case 7:

step_seven(ref step);

done = true;

break;

}

}

}

private void resetMaskandCovers()

{

for (int r = 0; r < nrow; r++)

{

RowCover[r] = 0;

for (int c = 0; c < ncol; c++)

{

M[r, c] = 0;

}

}

for (int c = 0; c < ncol; c++)

ColCover[c] = 0;

}

private void step_one(ref int step)

{

int min_in_row, max_in_col, min_in_col;

if ((checkBox1.Checked == true) && (checkBox2.Checked == false))

{

for (int c = 0; c < ncol; c++)

{

max_in_col = Matrix[0, c];

for (int r = 0; r < nrow; r++)

if (Matrix[r, c] > max_in_col)

max_in_col = Matrix[r, c];

for (int r = 0; r < nrow; r++)

Matrix[r, c] = max_in_col - Matrix[r, c];

}

for (int r = 0; r < nrow; r++)

{

min_in_row = Matrix[r, 0];

for (int c = 0; c < ncol; c++)

if (Matrix[r, c] < min_in_row)

min_in_row = Matrix[r, c];

for (int c = 0; c < ncol; c++)

Matrix[r, c] -= min_in_row;

}

}

else if ((checkBox2.Checked == true) && (checkBox1.Checked == false))

{

for (int c = 0; c < ncol; c++)

{

min_in_col = Matrix[0, c];

for (int r = 0; r < nrow; r++)

if (Matrix[r, c] < min_in_col)

min_in_col = Matrix[r, c];

for (int r = 0; r < nrow; r++)

Matrix[r, c] -= min_in_col;

}

for (int r = 0; r < nrow; r++)

{

min_in_row = Matrix[r, 0];

for (int c = 0; c < ncol; c++)

if (Matrix[r, c] < min_in_row)

min_in_row = Matrix[r, c];

for (int c = 0; c < ncol; c++)

Matrix[r, c] -= min_in_row;

}

}

else if ((checkBox1.Checked == false) && (checkBox2.Checked == false))

{

checkBox1.Checked = true;

for (int c = 0; c < ncol; c++)

{

max_in_col = Matrix[0, c];

for (int r = 0; r < nrow; r++)

if (Matrix[r, c] > max_in_col)

max_in_col = Matrix[r, c];

for (int r = 0; r < nrow; r++)

Matrix[r, c] = max_in_col - Matrix[r, c];

}

for (int r = 0; r < nrow; r++)

{

min_in_row = Matrix[r, 0];

for (int c = 0; c < ncol; c++)

if (Matrix[r, c] < min_in_row)

min_in_row = Matrix[r, c];

for (int c = 0; c < ncol; c++)

Matrix[r, c] -= min_in_row;

}

}

step = 2;

}

private void step_two(ref int step)

{

for (int r = 0; r < nrow; r++)

for (int c = 0; c < ncol; c++)

{

if (Matrix[r, c] == 0 && RowCover[r] == 0 && ColCover[c] == 0)

{

M[r, c] = 1;

RowCover[r] = 1;

ColCover[c] = 1;

}

}

for (int r = 0; r < nrow; r++)

RowCover[r] = 0;

for (int c = 0; c < ncol; c++)

ColCover[c] = 0;

step = 3;

}

private void step_three(ref int step)

{

int colcount;

for (int r = 0; r < nrow; r++)

for (int c = 0; c < ncol; c++)

if (M[r, c] == 1)

ColCover[c] = 1;

colcount = 0;

for (int c = 0; c < ncol; c++)

if (ColCover[c] == 1)

colcount += 1;

if (colcount >= ncol || colcount >= nrow)

step = 7;

else

step = 4;

}

private void find_a_zero(ref int row, ref int col)

{

int r = 0;

int c;

bool done;

row = -1;

col = -1;

done = false;

while (!done)

{

c = 0;

while (true)

{

if (Matrix[r, c] == 0 && RowCover[r] == 0 && ColCover[c] == 0)

{

row = r;

col = c;

done = true;

}

c += 1;

if (c >= ncol || done)

break;

}

r += 1;

if (r >= nrow)

done = true;

}

}

private bool star_in_row(int row)

{

bool tmp = false;

for (int c = 0; c < ncol; c++)

if (M[row, c] == 1)

tmp = true;

return tmp;

}

private void find_star_in_row(int row, ref int col)

{

col = -1;

for (int c = 0; c < ncol; c++)

if (M[row, c] == 1)

col = c;

}

private void step_four(ref int step)

{

int row = -1;

int col = -1;

bool done;

done = false;

while (!done)

{

find_a_zero(ref row, ref col);

if (row == -1)

{

done = true;

step = 6;

}

else

{

M[row, col] = 2;

if (star_in_row(row))

{

find_star_in_row(row, ref col);

RowCover[row] = 1;

ColCover[col] = 0;

}

else

{

done = true;

step = 5;

path_row_0 = row;

path_col_0 = col;

}

}

}

}

private void find_star_in_col(int c, ref int r)

{

r = -1;

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

if (M[i, c] == 1)

r = i;

}

private void find_prime_in_row(int r, ref int c)

{

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

if (M[r, j] == 2)

c = j;

}

private void augment_path()

{

for (int p = 0; p < path_count; p++)

if (M[path[p, 0], path[p, 1]] == 1)

M[path[p, 0], path[p, 1]] = 0;

else

M[path[p, 0], path[p, 1]] = 1;

}

private void clear_covers()

{

for (int r = 0; r < nrow; r++)

RowCover[r] = 0;

for (int c = 0; c < ncol; c++)

ColCover[c] = 0;

}

private void erase_primes()

{

for (int r = 0; r < nrow; r++)

for (int c = 0; c < ncol; c++)

if (M[r, c] == 2)

M[r, c] = 0;

}

private void step_five(ref int step)

{

bool done;

int r = -1;

int c = -1;

path_count = 1;

path[path_count - 1, 0] = path_row_0;

path[path_count - 1, 1] = path_col_0;

done = false;

while (!done)

{

find_star_in_col(path[path_count - 1, 1], ref r);

if (r > -1)

{

path_count += 1;

path[path_count - 1, 0] = r;

path[path_count - 1, 1] = path[path_count - 2, 1];

}

else

done = true;

if (!done)

{

find_prime_in_row(path[path_count - 1, 0], ref c);

path_count += 1;

path[path_count - 1, 0] = path[path_count - 2, 0];

path[path_count - 1, 1] = c;

}

}

augment_path();

clear_covers();

erase_primes();

step = 3;

}

private void find_smallest(ref int minval)

{

for (int r = 0; r < nrow; r++)

for (int c = 0; c < ncol; c++)

if (RowCover[r] == 0 && ColCover[c] == 0)

if (minval > Matrix[r, c])

minval = Matrix[r, c];

}

private void step_six(ref int step)

{

int minval = int.MaxValue;

find_smallest(ref minval);

for (int r = 0; r < nrow; r++)

for (int c = 0; c < ncol; c++)

{

if (RowCover[r] == 1)

Matrix[r, c] += minval;

if (ColCover[c] == 0)

Matrix[r, c] -= minval;

}

step = 4;

}

private void step_seven(ref int step)

{

int F = 0;

for (int i = 0; i < dataGridView2.ColumnCount; i++)

{

for (int j = 0; j < dataGridView2.RowCount; j++)

{

dataGridView2.Columns[i].Width = 15;

dataGridView2.Rows[i].Cells[j].Value = Matrix[i, j];

if (M[i, j] == 1)

{

dataGridView1[j, i].Style.ForeColor = Color.Red;

F += Convert.ToInt32(dataGridView1[j, i].Value);

}

}

}

textBox2.Text = F.ToString();

}

private void textBox1_KeyPress(object sender, KeyPressEventArgs e)

{

if (!(Char.IsDigit(e.KeyChar)))

{

if (e.KeyChar != (char)Keys.Back)

{

e.Handled = true;

}

}

}

private void textBox1_TextChanged(object sender, EventArgs e)

{

if (textBox1.Text == "")

return;

try

{

int number = System.Convert.ToInt32(textBox1.Text);

if (number < 1 || number > 10)

{

MessageBox.Show("Введенноечислонекорректно! Введите число от 1 до 10!");

textBox1.Text = "";

}

}

catch (Exceptionex)

{

MessageBox.Show("Введенное число некорректно! Введитечислоот 1 до 10!");

}

}

private void button3_Click(object sender, EventArgs e)

{

Application.Exit();

}

private void button4_Click(object sender, EventArgs e)

{

dataGridView1.Rows.Clear();

dataGridView1.Columns.Clear();

dataGridView2.Rows.Clear();

dataGridView2.Columns.Clear();

textBox1.Clear();

textBox2.Clear();

checkBox1.Checked = false;

checkBox2.Checked = false;

}

private void checkBox1_CheckedChanged(object sender, EventArgs e)

{

if (checkBox1.Checked == true) checkBox2.Checked = false;

if (checkBox1.Checked == false) checkBox2.Checked = true;

}

private void checkBox2_CheckedChanged(object sender, EventArgs e)

{

if (checkBox2.Checked == true) checkBox1.Checked = false;

if (checkBox2.Checked == false) checkBox1.Checked = true;

}

}

}



4. Тестирование программного модуля

В данном разделе приведем результаты работы программы при обработке тестовых данных. Тестовые результаты для сравнения получим при решении задачи о назначениях в MS Excel при помощи Поиска решения.

Возьмем матрицу 4х4, представленную на рисунке 13.

Рисунок 13 - Матрица для тестирования работы приложения

Получим оптимальные решения при помощи разработанного программного модуля. Результат работы приложения при стремлении целевой функции к максимуму показан на рисунке 14, при стремлении к минимуму - на рисунке 15.

Рисунок 14 - Результат работы приложения при стремлении целевой функции к максимуму

Рисунок 15 - Результат работы приложения при стремлении целевой функции к минимуму

Получим оптимальные решения при помощи надстройки Поиск решения в MS Excel. Диалоговое окно настроек поиска решения показано на рисунке 16. Результат работы при стремлении целевой функции к максимуму показан на рисунке 17, при стремлении к минимуму - на рисунке 18.

Рисунок 16 - Диалоговое окно настроек поиска решения



Рисунок 17 - Результат работы поиска решения при стремлении целевой функции к максимуму

Рисунок 18 - Результат работы поиска решения при стремлении целевой функции к минимуму

Далее протестируем созданное приложение на матрице 6х6 (рисунок 19) при стремлении целевой функции к максимуму (рисунок 20) и к минимуму (рисунок 21). Результаты работы поиска решения показаны на рисунках 22 и 23.

Рисунок 19 - Матрица для тестирования работы приложения

Рисунок 20 - Результат работы приложения при стремлении целевой функции к максимуму



Рисунок 21 - Результат работы приложения при стремлении целевой функции к минимуму

Рисунок 22 - Результат работы поиска решения при стремлении целевой функции к максимуму



Рисунок 23 - Результат работы поиска решения при стремлении целевой функции к минимуму

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

Заключение

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

Алгоритм венгерского метода был реализован программно в среде Visual C#. Реализованная программа имеет удобный и простой интерфейс, наглядно представляет решение задачи венгерским методом.

Список использованных источников

1. Вентцель Е. С. Исследование операций. М., «Советское радио», 1972, 552 с.

2. Исследование операций. Зайченко Ю. П. Издательское объединение «Вища школа», 1975, 320 с.

3. Волков И. К., Загоруйко Е. А. Исследование операций: Учеб. для вузов. 2-е изд. / Под ред. В. С. Зарубина, А. П. Крищенко. - М.: Изд-во МГТУ им. Н. Э. Баумана, 2002. - 436 с.

Размещено на Allbest.ru

...