Математичне програмування та дослідження операцій
Курсовая работа, 01 Декабря 2013, автор: пользователь скрыл имя
Краткое описание
Лінійне програмування є одним з важливих розділів дослідження операцій і зводиться до оптимізації лінійної цільової функції на множині, яка описується лінійними рівняннями і нерівностями. Лінійне програмування є окремим випадком математичного програмування. Одночасно воно – основа декількох методів вирішення задач цілочисельного і нелінійного програмування.
Серед спеціальних задач на практиці найчастіше зустрічається так звана задача комівояжера і різні її модифікації та узагальнення.
Содержание
ВСТУП 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
Прикрепленные файлы: 1 файл
Курсовая робота666.docx
— 562.01 Кб (Скачать документ)программирование” – Москва: Высшая школа, 1980 – 600 c.
- Калихман И.Л. Линейная алгебра и программирование. М.: Высш. Шк., 1967
- Кюнци Г.П., Крелле В. Нелинейное программирование. – М.: Сов. Радио, 1965
- Большакова И.В., Кураленко М.В. Линейное программирование – М.: Высшая школа, 2004. – 148 с.
- Вагнер Г. П. Основы исследования операций – М.: Мир, 1972-1973. -336 с.
- Ковтун В.В. “Конспект лекцій по математичному програмуванні і дослідженні операцій ”– Вінниця 2008.
- Москвіна С.М., Дубіненко С.Б., Перевозніков С.І Методичні вказівки до лабораторних робіт з курсу „Обчислювальні методи та застосування на ЕОМ” ч. І – Вінниця: ВПІ, 1992.
ДОДАТКИ
Додаток А
Міністерство освіти і науки України
Вінницький нацональний
Факультет автоматики та комп’ютерних систем управління
Кафедра комп’ютерних систем управління
Затверджено
Керівник Ковтун В.В.
___________________
“____” ________ 2008 р.
Розроблено
Студент гр. 1CI-09 Титарчук Є.О.
_______________________
“____” __________ 2011 р.
ТЕХНІЧНЕ ЗАВДАННЯ
на виконання курсової роботи
“ Розробка програмного комплексу для розв’язання задачі цілочисельного програмування типу "Задача комівояжера" ”
Найменування продукту, що розробляється: програмне забезпечення розв’язання задачі комівояжера
Галузь використання продукту: Результати роботи можуть використовуватися для автоматичного розв’язку задачі. Задачі такого типу виникають при дослідженні можливості мінімізації шляху при переміщенні між містами, а також передачі даних через мережу.
Підстава для розробки продукту:
- Навчальний план спеціальності 6.091400 - системи управління і автоматики.
- Робоча програма дисципліни “Математичне програмування та дослідження операцій”.
- Індивідуальне завдання на курсову роботу
Вимоги до програмного продукту:
- Операційна система – WINDOWS.
- Середовище програмування – довільне
- Необхідний об’єм пам’яті – не менше 64 MB
- ПЗ необхідно протестувати та зробити висновки щодо придатності його до
використання.
Все програмне забезпечення та супроводжуюча технічна документація повинні задовольняти наступним ГОСТам:
ГОСТ 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;
}
}
}
Додаток Г
Карта