Автор работы: Пользователь скрыл имя, 01 Декабря 2013 в 22:39, курсовая работа
Лінійне програмування є одним з важливих розділів дослідження операцій і зводиться до оптимізації лінійної цільової функції на множині, яка описується лінійними рівняннями і нерівностями. Лінійне програмування є окремим випадком математичного програмування. Одночасно воно – основа декількох методів вирішення задач цілочисельного і нелінійного програмування.
Серед спеціальних задач на практиці найчастіше зустрічається так звана задача комівояжера і різні її модифікації та узагальнення.
ВСТУП 5
1 ОГЛЯД ТА ВАРІАНТНИЙ АНАЛІЗ СУЧАСНИХ МЕТОДІВ МАТЕМАТИЧНОГО ПРОГРАМУВАННЯ ДЛЯ ДОСЛІДЖЕННЯ ОПЕРАЦІЙ 7
1.1 Класифікація задач дослідження операцій (ДО) 7
1.2 Методи розв’язання задачі комівояжера 9
1.3 Вибір методу розв’язання транспортної задачі 13
1.4 Аналіз об’єкту дослідження 13
1.5 Вибір середовища програмування 14
2 РОЗРОБКА АЛГОРИТМІЧНОГО ЗАБЕЗПЕЧЕННЯ 15
3 ПРОЕКТУВАННЯ ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ НА МОВІ UML 18
4 РОЗРОБКА ТЕСТІВ 24
5 РОЗРОБКА ДОКУМЕНТІВ ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ 28
5.1 Інструкція програмісту 28
5.2 Інструкція користувачеві 28
ВИСНОВКИ 29
программирование” – Москва: Высшая школа, 1980 – 600 c.
Додаток А
Міністерство освіти і науки України
Вінницький нацональний
Факультет автоматики та комп’ютерних систем управління
Кафедра комп’ютерних систем управління
Затверджено
Керівник Ковтун В.В.
___________________
“____” ________ 2008 р.
Розроблено
Студент гр. 1CI-09 Титарчук Є.О.
_______________________
“____” __________ 2011 р.
ТЕХНІЧНЕ ЗАВДАННЯ
на виконання курсової роботи
“ Розробка програмного комплексу для розв’язання задачі цілочисельного програмування типу "Задача комівояжера" ”
Найменування продукту, що розробляється: програмне забезпечення розв’язання задачі комівояжера
Галузь використання продукту: Результати роботи можуть використовуватися для автоматичного розв’язку задачі. Задачі такого типу виникають при дослідженні можливості мінімізації шляху при переміщенні між містами, а також передачі даних через мережу.
Підстава для розробки продукту:
Вимоги до програмного продукту:
використання.
Все програмне забезпечення та супроводжуюча технічна документація повинні задовольняти наступним ГОСТам:
ГОСТ 19.701-90
ИСО 5807-85 – ГОСТ на розробку програмних документів, схеми алгоритмів програм, даних та системи.
ГОСТ 19.781-74 – вимоги до розробки програмного забезпечення
ГОСТ 19.101-77 (СТ СЭВ 1626-79) – держстандарт на розробку програмної документації, видів програм та програмних документів.
ГОСТ 19.401-78 – Текст програми. Вимоги до змісту та оформлення.
ГОСТ 19.106-78 – вимоги до програмної документації.
ГОСТ 7.1.-84 та ДСТУ 3008-95 – розробка технічної документації.
Етапи розробки:
Порядок контролю та приймання курсової роботи:
Отримання завдання на виконання курсової роботи – «__» _______ 2011 р.
Термін здачі курсової роботи на перевірку – до «__» _______ 2011 р.
Термін захисту курсової роботи – до «__» _______ 2011 р.
Додаток Б
Лістинг програми, клас Form1
using System;
using System.Collections.Generic;
using System.Windows.Forms;
using System.Threading;
namespace CourseWork
{
public partial class Form1 : Form
{
private int[][] A;
private TextBox[][] tbA;
private int _n;
private int _oldN;
private bool _alreadyExists;
private bool _ready;
public Form1()
{
InitializeComponent();
}
private void InputCountOfTown(object sender, EventArgs e)
{
_n = Convert.ToInt32(tbCount.Text);
if (_n > 50)
{
_n = 50;
}
progressBar.Maximum = _n*_n;
progressBar.Value = 0;
progressBar.Visible = true;
if (_alreadyExists)
{
DeleteMatrix();
}
CreatMatrix();
_oldN = _n;
_alreadyExists = true;
}
private void DeleteMatrix()
{
for (int i = 0; i < _oldN; i++ )
{
for (int j = 0; j < _oldN; j++)
{
tbA[i][j].Dispose();
}
}
Panel.Invalidate();
}
private void CreatMatrix()
{
var thread = new Thread[_n];
int i;
A = new int[_n][];
for (i=0;i<_n;i++)
A[i] = new int[_n];
tbA = new TextBox[_n][];
for (i = 0; i < _n; i++)
{
tbA[i] = new TextBox[_n];
thread[i] = new Thread(CreateNewRow);
thread[i].Start(i);
}
}
private void CreateNewRow(object obj)
{
int i = (int) obj;
int j;
for (j = 0; j < _n; j++)
{
tbA[i][j] = new TextBox();
tbA[i][j].Width = 40;
tbA[i][j].Left = 5 + j * 40;
tbA[i][j].Top = 5 + i * 20;
tbA[i][j].Visible = true;
if (i != j)
{
tbA[i][j].TextChanged += TextChange;
}
else
{
tbA[i][j].Text = @"-";
tbA[i][j].Enabled = false;
}
Panel.Invoke(new MethodInvoker(()=>{Panel.
progressBar.Invoke(new MethodInvoker(()=>{
}
}
private void TextChange(object sender, EventArgs e)
{
_ready = true;
for (int i = 0; i < _n; i++)
{
for (int j = 0; j < _n; j++)
{
if (i == j)
{
tbA[i][j].Text = @"-";
A[i][j] = 1000000;
}
else
{
if (tbA[i][j].Text != String.Empty)
{
try
{
}
catch
{
}
}
}
if (tbA[i][j].Text == "")
{
_ready = false;
}
}
}
}
private void ButtonClick(object sender, EventArgs e)
{
if (_ready)
{
var greedyAlgorithm = new GreedyAlgorithm(A);
List<int> list = greedyAlgorithm.Answer();
int sum = 0;
int prev = 0;
textBox2.Text = @"1 -> ";
for (int i = 0; i < _n; i++)
{
textBox2.Text += (list[i] + 1).ToString();
if (i != _n - 1)
{
textBox2.Text += @" -> ";
}
sum += A[prev][list[i]];
prev = list[i];
}
tbSum.Text = sum.ToString();
}
else
{
MessageBox.Show(@"Потрібно заповнити всю матрицю");
}
}
}
}
Додаток В
Лістинг програми, клас GreedyAlgorithm
using System.Collections.Generic;
namespace CourseWork
{
class GreedyAlgorithm
{
private int[][] A;
private int[] column;
private int N;
private List<int> AnswerList;
public GreedyAlgorithm(int[][] matrix)
{
A = matrix;
N = matrix.Length;
column = new int[N];
AnswerList = new List<int>();
}
public List<int> Answer()
{
int j;
int s = 0;
for (int i = 0; i < N; i++)
{
j = MinInS(s);
s = j;
}
return AnswerList;
}
private int MinInS(int i)
{
int min = 1000000;
int nextPoint = 0;
for (int j=0;j<N;j++)
{
if (A[i][j] < min)
{
if (column[j] != 1)
{
min = A[i][j];
nextPoint = j;
}
}
}
AnswerList.Add(nextPoint);
column[i] = 1;
return nextPoint;
}
}
}
Додаток Г
Карта
Информация о работе Математичне програмування та дослідження операцій