Программное обеспечение вычислительной техники и автоматизированных систем

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

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

КУРСОВОЙ ПРОЕКТ

Программное обеспечение вычислительной техники и автоматизированных систем



1.1 Экономическая сущность задачи.

1.2 Математическая модель.

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

1.4 Выходные данные.

1.5 Организация диалога.

1.6 Функциональные тесты.

2. Выбранный метод решения задачи.

3. Структурное проектирование задачи.

4. Тестирование.

5. Анализ качества и надежности.

6. Анализ результатов решения задачи.

Приложения

Дата выдачи задания «___»__________

Срок окончания «____»______________

Руководитель: ___________________Веряскина И.Ю.

Рассмотрено на заседании предметно-цикловой комиссии специальных дисциплин

Протокол № _____от «______» _____________2011 г.

Председатель комиссии ____________________О.Ю. Морозова

График выполнения курсового проекта по дисциплине

«Математические методы»

Студента(тки) ___группы

(Ф.И.О.)

Специальности 230105 Программное обеспечение вычислительной техники и автоматизированных систем

Тема курсового проекта:____________________________________________________________________________________________

№ п/п	Раздел курсового проекта	Дата сдачи	Оценка, подпись преподавателя
1	Решение тестовых задач по теме
2	Постановка задачи
3	Входные, выходные данные задачи
4	Математическая модель задачи
5	Введение
6	Экономическая суть
7	Выбранный метод решения задачи
8	Структурное проектирование задачи (блок-схема)
9	Организация диалога (интерфейс программы)
10	Программа
11	Анализ надежности и качества
12	Анализ результатов решения задачи
13	Подготовка документации
14	Защита КП



Введение

Задача о назначениях является частным случаем классической транспортной задачи и, как следствие, является задачей транспортного типа.

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

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

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

Цель работы - исследовать решение задач о назначениях.

Задачи:

1. Рассмотреть теоретические основы задач о назначениях;

2. Проанализировать Венгерский метод решения задачи о назначениях.



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

Пусть иметься n работ, которые с различной долей квалификации и различной оплатой труда, смогут выполнить n работников. Имеется матрица стоимостей в которой отражена стоимость выполнения i-ым работником j-ой работы. Необходимо так закрепить работников за работами, чтобы один работник выполнял только 1 работу, одна работа выполнялась только одним работником и общая стоимость всех выполненных работ была минимальной. Критерием разрешимости задачи является то, что количество работ и количество работников должно быть одинаковым, должна присутствовать матрица, элементами которой могут быть не отрицательные числа, так как стоимость работы не может быть отрицательной.

1.1 Экономическая сущность задачи

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

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



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

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

при ограничениях:

Условием разрешимости задачи является условие баланса:

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

1) Количество работ и работников(n);

2) Матрица стоимостей.

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

1) План закрепления каждого работника за определенной работой;

2) Стоимость выполнения всех работ.



1.5 Организация диалога

Программа запускается при двойном нажатии по ярлыку программы, создаваемом на рабочем столе при установке, либо в корневом каталоге, где располагается программа.

После запуска появится главное окно программы. (Рис. 1).

Рисунок 1. Главное окно

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

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

Рисунок 2. Рандомное заполнение матрицы

Теперь нам необходимо получить ответ. Нажимаем и получаем результат исследования функции (Рис. 3).

Рисунок 3. Решение матрацы



Подведём итог: Полученная матрица имеет более простой вид, который стало гораздо легче решать в уме либо в письменном виде.

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

1.6 Функциональные тесты

Решим вышеописанную задачу о назначении вручную:

Рабочий Работа	Рабочий 1	Рабочий 2	Рабочий 3
Работа 1	7	6	33
Работа 2	19	23	37
Работа 3	12	48	41

1) Найдем минимальные элементы в строках

Рабочий Работа	Рабочий 1	Рабочий 2	Рабочий 3		Pi
Работа 1	7	6	33		6
Работа 2	19	23	37		19
Работа 3	12	48	41		12

2) Каждый минимальный элемент в строке отнять от всех элементов в строке. Получаем матрицу следующего вида.

Рабочий Работа	Рабочий 1	Рабочий 2	Рабочий 3
Работа 1	1	0	27
Работа 2	0	4	18
Работа 3	0	36	29

3) Для рабочего 3 не найдено нулевого элемента, поэтому решаем дальше. Находим минимальные элементы в столбцах.



Рабочий Работа	Рабочий 1	Рабочий 2	Рабочий 3
Работа 1	1	0	27
Работа 2	0	4	18
Работа 3	0	36	29

Pj	0	0	18

4) Минимальный элемент столбца вычитаем из всех элементов этого столбца. Получаем матрицу.

Рабочий Работа	Рабочий 1	Рабочий 2	Рабочий 3
Работа 1	1	0	9
Работа 2	0	4	0
Работа 3	0	36	11

5) Матрица представлена в более легком виде удобной для вычислений.

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

6) В вывод выходит матрица.

Рабочий Работа	Рабочий 1	Рабочий 2	Рабочий 3
Работа 1	1	0	9
Работа 2	0	4	0
Работа 3	0	36	11

7) Следовательно для подсчета стоимости оплаты необходимо подсчитать все найденные элементы в конечной матрице из начальной (т.е. индексация элементов матрица одна и та же).

Рабочий Работа	Рабочий 1	Рабочий 2	Рабочий 3
Работа 1	7	6	33
Работа 2	19	23	37
Работа 3	12	48	41

Нахождение суммы всех затрат: 12+6+37=55



2. Выбранный метод решения задачи

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

Специфические особенности задач о назначениях послужили поводом к появлению эффективного венгерского метода их решения. Основная идея венгерского метода заключается в переходе от исходной квадратной матрицы стоимости С к эквивалентной ей матрице Сэ с неотрицательными элементами и системой n независимых нулей, из которых никакие два не принадлежат одной и той же строке или одному и тому же столбцу. Для заданного n существует n! допустимых решений. Если в матрице назначения X расположить n единиц так, что в каждой строке и столбце находится только по одной единице, расставленных в соответствии с расположенными n независимыми нулями эквивалентной матрицы стоимости Сэ, то получим допустимые решения задачи о назначениях.

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



3. Тестирование

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

Работа Автосалон	Ремонт двигателя	Ремонт кузова	Ремонт салона
Автосалон 1	2	6	7
Автосалон 2	6	3	8
Автосалон 3	9	5	3

Рисунок 4. Тестирование программы

Получилась идеальная матрица в которой в каждом столбце и в каждой строке есть лишь по одному нулю.

Работа Автосалон	Ремонт двигателя	Ремонт кузова	Ремонт салона
Автосалон 1	0	4	5
Автосалон 2	3	0	5
Автосалон 3	6	2	0

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

S=2+3+3=8



4. Анализ качества и надежности

В данной программе предусмотрена следующая ошибка:

Ошибка заполнения матрицы (Рис. 5). Суть ошибки заключается в том, что если при нажатии кнопки какое-то поле из матрицы не заполнено, то выдается эта ошибка, чтобы пользователь заполнил поля.

Рисунок 5. Ошибка заполнения матрицы

Так же в программе предусмотрено окно подтверждения выхода из программы. При нажатии на (крестик) выходит окно подтверждения (Рис. 6).

Рисунок 6. Подтверждения закрытия программы



5. Анализ результатов решения задачи

С помощью данной программы были решены 10 программ.



Список используемой литературы

1. А.М. Епанешников, Программирование в среде Delphi 7.0;

2. Акулов Н. Delphi World 6 - М.: Эксмо, 2004;

3. Maкоха А.Н., Сахнюк П.А., Червяков Н.И. Дискретная математика. 2005 год;

4. Суворов К., Черемных М. Справочник Delphi. Базовые классы - СПБ: БХВ - Петербург, 2004;

5. Поган А.М., Царенко Ю.А. Программирование в Delphi - М.: Эксмо, 2007;

6. Суворов К., Черемных М. Справочник Delphi. Базовые классы - СПБ: БХВ - Петербург, 2004;

7. Ф.А. Новиков. Дискретная математика для программистов;

8. Фаронов В.В. Delphi 7.0 программирование на языке высокого уровня - М.: АСТпресс, 2005;

9. Фленов Михаил, Delphi 2009. Секреты программирования.

10. Шумаков А. Базы данных в среде Delphi 3 - М.: АСТпресс, 2003;



Приложение

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, Grids, StdCtrls, ComCtrls, jpeg, ExtCtrls;

type

mas=array [0..60] of integer;

TForm1 = class(TForm)

StringGrid1: TStringGrid;

ComboBox1: TComboBox;

Button1: TButton;

Button2: TButton;

StringGrid2: TStringGrid;

StringGrid3: TStringGrid;

StringGrid4: TStringGrid;

Image1: TImage;

Button3: TButton;

Button4: TButton;

Label1: TLabel;

Button5: TButton;

Label2: TLabel;

procedure StringGrid1KeyPress (Sender: TObject; var Key: Char);

procedure ComboBox1Change (Sender: TObject);

procedure Button1Click (Sender: TObject);

procedure Button2Click (Sender: TObject);

procedure FormClose (Sender: TObject; var Action: TCloseAction);

procedure Button3Click (Sender: TObject);

procedure Button4Click (Sender: TObject);

procedure StringGrid1SelectCell (Sender: TObject; ACol, ARow: Integer;

var CanSelect: Boolean);

private

{Private declarations}

public

{Public declarations}

end;

var

Form1: TForm1;

ps, tt, i, j:integer;

pi, pj:mas;

n:integer;

Col, Row: Integer;

o, t:string;

implementation

{$R *.dfm}

procedure TForm1. ComboBox1Change (Sender: TObject);

begin

if ComboBox1.text='2' then

begin

StringGrid1. ColCount:=2;

StringGrid1. RowCount:=2;

StringGrid2. RowCount:=2;

StringGrid3. ColCount:=2;

StringGrid4. ColCount:=2;

StringGrid4. RowCount:=2;

end;

if ComboBox1.text='3' then

begin

StringGrid1. ColCount:=3;

StringGrid1. RowCount:=3;

StringGrid2. RowCount:=3;

StringGrid3. ColCount:=3;

StringGrid4. ColCount:=3;

StringGrid4. RowCount:=3;

end;

if ComboBox1.text='4' then

begin

StringGrid1. ColCount:=4;

StringGrid1. RowCount:=4;

StringGrid2. RowCount:=4;

StringGrid3. ColCount:=4;

StringGrid4. ColCount:=4;

StringGrid4. RowCount:=4;

end;

if ComboBox1.text='5' then

begin

StringGrid1. ColCount:=5;

StringGrid1. RowCount:=5;

StringGrid2. RowCount:=5;

StringGrid3. ColCount:=5;

StringGrid4. ColCount:=5;

StringGrid4. RowCount:=5;

end;

if ComboBox1.text='6' then

begin

StringGrid1. ColCount:=6;

StringGrid1. RowCount:=6;

StringGrid2. RowCount:=6;

StringGrid3. ColCount:=6;

StringGrid4. ColCount:=6;

StringGrid4. RowCount:=6;

end;

if ComboBox1.text='7' then

begin

StringGrid1. ColCount:=7;

StringGrid1. RowCount:=7;

StringGrid2. RowCount:=7;

StringGrid3. ColCount:=7;

StringGrid4. ColCount:=7;

StringGrid4. RowCount:=7;

end;

end;

procedure TForm1. Button1Click (Sender: TObject);

var i, j: Integer;

begin



with StringGRid1 do

for i:=0 to RowCount-1 do

for j:=0 to ColCount-1 do

Cells [j, i]:='';

with StringGRid2 do

for i:=0 to RowCount-1 do

for j:=0 to ColCount-1 do

Cells [j, i]:='';

with StringGRid3 do

for i:=0 to RowCount-1 do

for j:=0 to ColCount-1 do

Cells [j, i]:='';

with StringGRid4 do

for i:=0 to RowCount-1 do

for j:=0 to ColCount-1 do

Cells [j, i]:='';

StringGrid4. Visible:=false;

StringGrid2. Visible:=false;

StringGrid3. Visible:=false;

image1. Visible:=false;

clientwidth:=400;

end;

procedure TForm1. StringGrid1KeyPress (Sender: TObject; var Key: Char);

begin

if not (Key in ['0'..'9', #8,', ','-', DecimalSeparator]) then Key:=#0;

end;

procedure TForm1. Button2Click (Sender: TObject);

var n:integer;

begin

begin

n:=combobox1.itemindex+2;

for i:=1 to n do

for j:=1 to n do

if stringgrid1. Cells [i-1, j-1]='' then

begin

showmessage ('Не все поля заполнены!');

exit;

end;

end;

for i:=0 to StringGrid1. ColCount-1 do

For j:=0 to StringGrid1. RowCount-1 do

StringGrid4. Cells [i, j]:=StringGrid1. Cells [i, j];

ps:=0;

// вычисление минимальных значений в каждой строке

// Начало

For i:=0 to StringGrid4. RowCount-1 do

begin

pi[i]:=StrToInt (StringGrid4. Cells [0, i]);

For j:=1 to StringGrid4. ColCount-1 do

if pi[i]>StrToInt (StringGrid4. Cells [j, i]) then

pi[i]:=StrToInt (StringGrid4. Cells [j, i]);

end;

For i:=0 to StringGrid4. ColCount-1 do

begin

For j:=0 to StringGrid4. RowCount-1 do

StringGrid4. Cells [j, i]:=IntToStr

(StrToInt (StringGrid4. Cells [j, i]) - pi[i]);

end;

// вычисление минимальных значений в каждом столбце

// Начало

For i:=0 to StringGrid4. ColCount-1 do

begin

pj[i]:=StrToInt (StringGrid4. Cells [i, 0]);

For j:=1 to StringGrid4. RowCount-1 do

if pj[i]>StrToInt (StringGrid4. Cells [i, j]) then

pj[i]:=StrToInt (StringGrid4. Cells [i, j]);

end;

// Конец

for i:=0 to StringGrid4. ColCount-1 do

begin

if StringGrid4. Cells [i, j]='0' then label1.caption:='asd';

end;

For i:=0 to StringGrid4. ColCount-1 do

begin

For j:=0 to StringGrid4. RowCount-1 do

StringGrid4. Cells [i, j]:=IntToStr

(StrToInt (StringGrid4. Cells [i, j]) - pj[i]);

end;

for i:=0 to StringGrid4. ColCount-1 do

begin

StringGrid2. Cells [0, i]:=IntToStr (pi[i]);

StringGrid3. Cells [i, 0]:=IntToStr (pj[i]);

end;

{for i:=0 to StringGrid4. ColCOunt-1 do

for j:=0 to StringGrid4. RowCount-1 do

begin

Repeat

ps:=ps+1;

until (StrTOInt(StringGrid4. Cells [i, j])=0);

end;}

clientwidth:=700;

StringGrid4. Visible:=True;

StringGrid2. Visible:=True;

StringGrid3. Visible:=True;

image1. Visible:=true;

end;

// конец

procedure TForm1. FormClose (Sender: TObject; var Action: TCloseAction);

var DlgRes:integer;

begin

DlgRes:= MessageBox (form1. Handle, 'Закрыть программу?', 'Сообщение', MB_YESNO or MB_ICONQUESTION);

if DlgRes = ID_NO then action:=caNone;

if DlgRes = ID_YES then application. Terminate;

end;

procedure TForm1. Button3Click (Sender: TObject);

begin

Randomize;

for i:=0 to StringGrid1. ColCount-1 do

for j:=0 to StringGrid1. RowCount-1 do

StringGrid1. Cells [i, j]:=IntToStr (Random(50)+1);

end;

procedure TForm1. Button4Click (Sender: TObject);

var b: integer;

begin

Randomize;

b:=random(6)+2;

stringgrid1.colCount:=b;

stringgrid1.rowcount:=b;

stringgrid2.rowcount:=b;

stringgrid3.colCount:=b;

stringgrid4.colCount:=b;

stringgrid4.rowcount:=b;

combobox1.itemindex:=b-2;

for i:=0 to StringGrid1. ColCount-1 do

for j:=0 to StringGrid1. RowCount-1 do

StringGrid1. Cells [i, j]:=IntToStr (Random(50)+1);

end;

программный транспортный задача

procedure TForm1. StringGrid1SelectCell (Sender: TObject; ACol,

ARow: Integer; var CanSelect: Boolean);

begin

col:=Acol;

row:=Arow;

end;

end.

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

...