Новости

РАЗРАБОТКА ПРОГРАММНОГО МОДУЛЯ

Работа добавлена:






РАЗРАБОТКА ПРОГРАММНОГО МОДУЛЯ на http://mirrorref.ru

РАЗРАБОТКА ПРОГРАММНОГО МОДУЛЯ

Введение

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

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

  1. Постановка задачи
    1. Математическая модель задачи

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

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

  1. n – количество ресурсов,m – количество работ.
  2. = 1 – единичное количество ресурса  (i = ), например: один работник; одно транспортное средство; одна научная тема и т.д.
  3. = 1 – единичное количество работы  (j = ), например: одна должность; один маршрут; одна лаборатория.
  4. – характеристика качества выполнения работы  с помощью ресурса . Например, компетентностьi-го работника при работе наj-й должности; время, за котороеi-е транспортное средство перевезет груз поj-му маршруту; степень квалификацииi-й лаборатории при работе надj-й научной темой.

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

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

, 0 – ; 1 – .

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

Общий вид транспортной задачи о назначениях представлен в таблице 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

{

publicpartialclassForm1 :Form

   {

publicstaticint[,] Matrix =newint[10, 10];

publicstaticint[,] M =newint[10, 10];

publicstaticint[,] path =newint[21, 2];

publicstaticint[] RowCover =newint[10];

publicstaticint[] ColCover =newint[10];

publicstaticint nrow;

publicstaticint ncol;

publicstaticint path_count = 0;

publicstaticint path_row_0;

publicstaticint path_col_0;

publicstaticint asgn = 0;

publicstaticint step;

public Form1()

       {

           InitializeComponent();

       }

privatevoid Form1_Load(object sender,EventArgs e)

       {

           dataGridView1.Rows.Clear();

           dataGridView2.Rows.Clear();

           textBox1.Clear();

           textBox2.Clear();

       }

privatevoid button1_Click(object sender,EventArgs e)

       {

           dataGridView1.Rows.Clear();

           dataGridView2.Rows.Clear();

           textBox2.Clear();

string fname, text;

OpenFileDialog Fd =newOpenFileDialog();

           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 =newStreamReader(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 subStringin 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;

                   }

               }

elsebreak;

           }

       }

privatevoid 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 =newRandom(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();

                   }

               }

           }

       }

privatevoid 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();

       }

privatevoid 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;

               }

           }

       }

privatevoid 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;

       }

privatevoid step_one(refint 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;

               }

           }

elseif ((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;

               }

           }

elseif ((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;

       }

privatevoid step_two(refint 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;

       }

privatevoid step_three(refint 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;

       }

privatevoid find_a_zero(refint row,refint 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;

           }

       }

privatebool star_in_row(int row)

       {

bool tmp =false;

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

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

                   tmp =true;

return tmp;

       }

privatevoid find_star_in_row(int row,refint col)

       {

           col = -1;

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

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

                   col = c;

       }

privatevoid step_four(refint 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;

                   }

               }

           }

       }

privatevoid find_star_in_col(int c,refint r)

       {

           r = -1;

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

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

                   r = i;

       }

privatevoid find_prime_in_row(int r,refint c)

       {

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

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

                   c = j;

       }

privatevoid 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;

       }

privatevoid clear_covers()

       {

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

               RowCover[r] = 0;

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

               ColCover[c] = 0;

       }

privatevoid 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;

       }

privatevoid step_five(refint 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;

       }

privatevoid find_smallest(refint 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];

       }

privatevoid step_six(refint 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;

       }

privatevoid step_seven(refint 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();

       }

privatevoid textBox1_KeyPress(object sender,KeyPressEventArgs e)

       {

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

           {

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

               {

                   e.Handled =true;

               }

           }

       }

privatevoid 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 (Exception ex)

           {

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

           }

       }

privatevoid button3_Click(object sender,EventArgs e)

       {

Application.Exit();

       }

privatevoid 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;

       }

privatevoid checkBox1_CheckedChanged(object sender,EventArgs e)

       {

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

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

       }

privatevoid 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 с.

РАЗРАБОТКА ПРОГРАММНОГО МОДУЛЯ на http://mirrorref.ru


Похожие рефераты, которые будут Вам интерестны.

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

2. Создание программного модуля обработки данных счётчиков электроэнергии на предприятии РУП «Минскэнерго» филиал «Энергосбыт»

3. Изучение закона Гука и определение модуля упругости (модуля Юнга)

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

5. Разработка тестирующего модуля для проверки знаний обучающегося персонала службы «Такси»

6. Разработка модуля обработки изображения и поиску на нём лиц человека с последующим определением эмоции на них

7. РАЗРАБОТКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ АС

8. Разработка программного обеспечения для android устройства

9. Разработка программного обеспечения для платформы Android

10. Разработка программного продукта средствами современных web-технологий