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

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

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

Содержание

Введение

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

Введение

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

Для разработки программного модуля используется язык программирования Visual C#, и среда разработки Visual Studio 2010.

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

Во втором разделе «Проектирование программного модуля» приводится структурная диаграмма программного модуля. Здесь дается краткое описание всех уровней диаграммы с назначением всех ее блоков.

В разделе «Реализация программного модуля» приведен код программного модуля.

В разделе «Тестирование программного модуля» рассмотрена работа приложения.

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

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

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

Условие задачи сформулировано следующим образом: Фирма производит для автомобилей запасные части типа А и В. Фонд рабочего времени составляет 5000 чел.-ч в неделю. Для производства одной детали типа А требуется 1 чел.-ч, а для производства одной детали типа В - 2 чел.-ч. Производственная мощность позволяет выпускать максимум 2500 деталей типа А и 20001 деталей типа В в неделю. Для производства детали типа А уходит: 2 кг полимерного материала и 5 кг листового материала, а для производства одной детали типа В - 4 кг полимерного материала и 3 кг листового металла. Еженедельные запасы каждого материала -по 10 000 кг. Общее число производимых деталей в течение одной недели должно составлять не менее 1500 штук. Определите, сколько деталей каждого вида следует производить, чтобы обеспечить максимальный доход от продажи за неделю, если доход от продаж одной детали типа А и В составляет соответственно 1,1 руб. и 1,5 руб.

Таблица 1 - Исходные данные

Тип	Производственная мощность	Материал	Время	Прибыль
		Полимер	Лист
A	2500	2	5	1	1,1
B	2000	4	3	2	1,5
Запас	<1500	10000	10000	5000	max

Алгоритм симплекс-метода включает следующие этапы:

1) составление 1-го опорного плана;

2) проверка плана на оптимальность;

3) определение ведущих (разрешающих) столбца и строки;

4) построение нового опорного плана.

Пусть целевая функция имеет вид:

F=c1·x1+c2·x2+c3·x3+c4·x4>min (1)

Тогда система ограничений имеет вид:

a11·x1+a12·x2+a13·x3+a14·x4?b1

a21·x1+a22·x2+a23·x3+a24·x4?b2

a31·x1+a32·x2+a33·x3+a34·x4?b3

a41·x1+a42·x2+a43·x3+a44·x4?b4

x1,x2,x3,x4?0 (2)

В систему ограничений вводятся дополнительные переменные . Получают систему ограничений:

-a11·x1-a12·x2-a13·x3-a14·x4+y1=-b1

-a21·x1-a22·x2-a23·x3-a24·x4+y2=-b2

-a31·x1-a32·x2-a33·x3-a34·x4+y3=-b3

-a41·x1-a42·x2-a43·x3-a44·x4+y4=-b4

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

Таблица 2 - Общий вид симплекс-таблицы

БП	ЗБП	-x1	-x2	-x3	-x4
y1 y2 y3 y4	b1 b2 b3 b4	a11 a21 a31 a41	a12 a22 a32 a42	a13 a23 a33 a43	a14 a24 a34 a44
F	0	-c1	-c2	-c3	-c4

Последняя строка таблицы называется индексной или строкой оценок. В столбец БП занесены базисные переменные. Столбец ЗБП содержит значения свободных членов, стоящих в системе ограничений (2).

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

Алгоритм нахождения оптимального решения.

1) Просматривается индексная строка симплексной таблицы, если все оценки положительны, то оптимальное решение задачи найдено. В этом решении все небазисные переменные равны 0, а базисные - значениям столбца ЗБП.

2) Если же в индексной строке есть отрицательные оценки, то среди них находится максимальная по абсолютной величине

.

Столбец называется разрешающим. Переменную, соответствующую разрешающему столбцу, следует ввести в базис.

Для определения разрешающего элемента вводится особый коэффициент , называемый симплексным отношением. Строка с

минимальным симплексным отношением будет разрешающей. Элемент таблицы , находящийся на пересечении разрешающих строки и столбца называется разрешающим элементом, обозначается он . Далее производится пересчет симплексной таблицы:

а) разрешающий элемент заменяется на обратную величину ;

б) остальные элементы разрешающей строки делятся на разрешающий элемент;

в) остальные элементы разрешающего столбца делятся на разрешающий элемент и знак меняется на противоположный;

г) оставшиеся элементы таблицы рассчитываются по правилу прямоугольника.

Сначала вычисляется произведение , затем . Затем разность между этими произведениями делится на разрешающий элемент:

Таким образом, получается новая симплексная таблица.

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

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

Метод Гомори основан на применении симплекс-метода и метода отсечений.

Алгоритм метода:

1) сформированная задача решается симплексным методом без учета целочисленности;

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

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

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

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

Q=1,1x1+1,5x2>max

При следующих ограничениях:

2·x1+4·x2?10000(1)

5·x3+3·x4?10000 (2)

x1+x2?1500 (3)

x1, x2?0

Шаг 1. Избавимся от неравенств в ограничениях, введя в ограничения 1, 2, 3 неотрицательные балансовые переменные s1, s2, s3.

Шаг 2. Ищем в системе ограничений базисные переменные.

Из последней системы ограничений можно выделить базисные переменные s1,s2. Не все уравнения содержат базисные переменные, это значит, что исходная задача не содержит в себе допустимого базисного решения. Для его нахождения вначале составим и решим вспомогательную задачу. Такое решение еще называют решением с искусственным базисом.

Введем в уравнение 3 искусственную неотрицательную переменную r1.

Получим следующую систему ограничений, с базисными переменными s1,s2,r1.

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

G = r1

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

Для решения вспомогательной задачи симплекс-методом выразим функцию G через свободные переменные, для этого:

- вычтем из функции G уравнение 3

Функция G примет вид:

G = - x1 - x2 + s3 + 1500

Теперь мы можем сформировать начальную симплекс-таблицу.

Итерация 0-a

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

Итерация 1

Итерация 2

Итерация 3

Достигнуто оптимальное решение, т.к. в строке целевой функции нет положительных коэффициентов.

Ответ.

Оптимальное значение функции Q(x)= 4000 достигается в точке с координатами:

x1= 714.28571428571

x2= 2142.8571428571

s1= 0

s2= 0

s3= 1357.1428571429

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

Входными данными являются фонд рабочего времени, требуемое количество людей для производства одной детали типа A, требуемое количество людей для производства одной детали типа B, производственная мощность которая позволяет выпускать максимум деталей типа A в неделю, вес полимерного материала и листового материала необходимое для производства детали типа A и типа B, Ежедневные запасы каждого материала, общее число производимых деталей в течение одной недели, доход от продаж одной детали типа А и В.

Ниже в таблице 1 приведены их обозначения и диапазон возможных значений.

Таблица 1 - Обозначение и возможный диапазон входных данных

Название	Обозначение	Диапазон возможных значений
вес полимерного материала необходимое для производства детали типа A и типа B	ind[0,j] j = 0..1	Вещественные
вес листового материала необходимое для производства детали типа A и типа B	ind[1,j] j = 0..1	Вещественные
ежедневные запасы полимерного материала	ind[0,6]	Вещественные
ежедневные запасы полимерного материала	ind[1,6]	Вещественные
общее число производимых деталей в течение одной недели	ind[2,6]	Вещественные
доход от продаж одной детали типа А и В	ind[3,j] j = 0..1	Вещественные

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

Выходными данными являются количество деталей необходимое производить вида A, и количество деталей необходимое производить вида B, чтобы обеспечить максимальный доход от продажи за неделю, максимальный доход. Ниже в таблице 1 приведены их обозначения и диапазон возможных значений.

Таблица 1 - Обозначение и возможный диапазон выходных данных

Название	Обозначение	Диапазон возможных значений
количество деталей необходимое производить вида A	x1	Вещественные
количество деталей необходимое производить вида B	x2	Вещественные
максимальный доход	x3	Вещественные

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

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

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

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

Диаграмма имеет 3 уровня.

На первом уровне находится функция Main, эта функция выполняется самая первая при запуске программы, в ней вызывается главная форма.

На втором уровне находится класс Form1(), главная форма программы где находятся исходные данные, необходимые кнопки и результаты.

На третьем уровне находятся события на кнопки:

1) button1_Click - события на нажатие на кнопку «Расчитать»

2) button2_Click - события на нажатие на кнопку «Очистить»

3) button3_Click - события на нажатие на кнопку «Отчет»

4) button4_Click - события на нажатие на кнопку «О программе»

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

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

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

диаграмма симплекс метод целочисленный



Рисунок 2 - Главная форма программы

При нажатии на кнопку «Рассчитать» происходит весь процесс вычисления, если решение найдено выводится результаты на форму, если не найдено выскакивает соответствующее сообщение. При нажатии на кнопку «Очистить» происходит очищение исходных данных.

Рисунок 3 - Главная форма программы, вывод результатов

При нажатии на кнопку «Отчет» выводится весь отчет вычисления. Выводится все симплексные таблицы.



Рисунок 4 - Отчет

При нажатии на кнопку «О программе» выводятся форма с информацией о программе и разработчике.

Рисунок 5 - О программе

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

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

Файл Program.cs

using System;

using System.Collections.Generic;

using System.Linq;

using System.Windows.Forms;

namespace SimplexMetod

{

static class Program

{

/// <summary>

/// The main entry point for the application.

/// </summary>

[STAThread]

static void Main()

{

Application.EnableVisualStyles();

Application.SetCompatibleTextRenderingDefault(false);

Application.Run(new Form1());

}

}

}

Файл Form1.cs

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

using System.IO;

namespace SimplexMetod

{

public partial class Form1 : Form

{

int n, m; //размерность матрицы

double[,] ind, temp, s; //матрица индексов и свободных членов

class FunctionWithFile //класс для работы с временным файлом

{

public string Read(string path)

{

using (TextReader reader = new StreamReader(new FileStream(path, FileMode.Open)))

{

return reader.ReadToEnd();

}

}

}

public Form1()

{

InitializeComponent();

}

private void Form1_Load(object sender, EventArgs e)

{

//начальные данные на формах

dataGridView1.Rows.Add(2);

dataGridView1.Rows[0].Cells[0].Value = "A";

dataGridView1.Rows[1].Cells[0].Value = "B";

dataGridView1.Rows[2].Cells[0].Value = "Запас";

dataGridView1.Rows[0].Cells[0].ReadOnly = true;

dataGridView1.Rows[1].Cells[0].ReadOnly = true;

dataGridView1.Rows[2].Cells[0].ReadOnly = true;

dataGridView1.Rows[0].Cells[1].Value = 2500;

dataGridView1.Rows[0].Cells[2].Value = 2.0;

dataGridView1.Rows[0].Cells[3].Value = 5.0;

dataGridView1.Rows[0].Cells[4].Value = 2.0;

dataGridView1.Rows[0].Cells[5].Value = 1.1;

dataGridView1.Rows[1].Cells[1].Value = 2000;

dataGridView1.Rows[1].Cells[2].Value = 4.0;

dataGridView1.Rows[1].Cells[3].Value = 3.0;

dataGridView1.Rows[1].Cells[4].Value = 2.0;

dataGridView1.Rows[1].Cells[5].Value = 1.5;

dataGridView1.Rows[2].Cells[1].Value = 1500;

dataGridView1.Rows[2].Cells[2].Value = 10000;

dataGridView1.Rows[2].Cells[3].Value = 10000;

dataGridView1.Rows[2].Cells[4].Value = 5000;

dataGridView1.Rows[2].Cells[5].Value = "max";

dataGridView1.Rows[2].Cells[5].ReadOnly = true;

button3.Enabled = false;

}

//добавление на временный файл каждой симплексной таблицы и т.п. информации

private void save_results(string path)

{

using (TextWriter writer = File.AppendText(path))

{

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

{

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

{

writer.Write(ind[i, j].ToString("0.00"));

writer.Write(" ");

}

writer.WriteLine();

}

writer.WriteLine();

}

}

private void button1_Click(object sender, EventArgs e)

{

if (System.IO.File.Exists("temp.txt")) System.IO.File.Delete("temp.txt");

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

//обработка исключения для ввода данных

try

{

n = 5;

m = 7;

ind = new double[n, m];

temp = new double[n, m];

ind[0, 0] = Convert.ToDouble(dataGridView1.Rows[0].Cells[2].Value);

ind[0, 1] = Convert.ToDouble(dataGridView1.Rows[1].Cells[2].Value);

ind[1, 0] = Convert.ToDouble(dataGridView1.Rows[0].Cells[3].Value);

ind[1, 1] = Convert.ToDouble(dataGridView1.Rows[1].Cells[3].Value);

ind[2, 0] = ind[0, 2] = 1;

ind[2, 1] = ind[1, 3] = ind[2, 5] = 1;

ind[3, 0] = Convert.ToDouble(dataGridView1.Rows[0].Cells[5].Value);

ind[3, 1] = Convert.ToDouble(dataGridView1.Rows[1].Cells[5].Value);

ind[4, 0] = ind[2, 4] = - 1;

ind[4, 1] = -1;

ind[4, 4] = 1;

ind[0, 6] = Convert.ToDouble(dataGridView1.Rows[2].Cells[2].Value);

ind[1, 6] = Convert.ToDouble(dataGridView1.Rows[2].Cells[3].Value);

ind[2, 6] = Convert.ToDouble(dataGridView1.Rows[2].Cells[1].Value);

ind[3, 6] = 0;

ind[4, 6] = -ind[2, 6];

}

catch

{

MessageBox.Show("Ошибка ввода данных");

return;

}

int iter = 0, k=0, index_i=0, delix_k=0, qi = 4;

double delix=0, rz=0;

button3.Enabled = true;

//основной цикл

for (; ;)

{

try

{

iter++;

index_i = n - 1;

int index_j;

double max_j;

if (iter < 2)

{

index_j = -1;

max_j = 0;

for (k = 0; k < m - 1; k++)

{

if (ind[index_i, k] < 0)

{

index_j = k;

max_j = Math.Abs(ind[index_i, k]);

break;

}

}

for (int i = k; i < m - 1; i++)

{

if (ind[index_i, i] < 0)

if (Math.Abs(ind[index_i, i]) >= max_j)

{

index_j = i;

max_j = Math.Abs(ind[index_i, i]);

}

}

}

else

{

index_j = 0;

max_j = ind[index_i, index_j];

for (k = 0; k < m - 1; k++)

{

if (ind[index_i, k] > max_j)

{

index_j = k;

max_j = Math.Abs(ind[index_i, k]);

}

}

}

delix_k = -1;

delix = -1;

for (k = 0; k < n - 1; k++)

if (ind[k, index_j] > 0 && ind[k, m - 1] > 0)

{

delix = ind[k, m - 1] / ind[k, index_j];

delix_k = k;

break;

}

for (int i = k; i < n - 1; i++)

if (ind[i, index_j] > 0 && ind[i, m - 1] > 0)

if (ind[i, m - 1] / ind[i, index_j] < delix)

{

delix = ind[i, m - 1] / ind[i, index_j];

delix_k = i;

}

rz = ind[delix_k, index_j];

save_results("temp.txt");

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

if (proverka_stolbes(j, delix_k) && j >= m - 2)

{

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

ind[i, j] = ind[i, m - 1];

m = m - 1;

}

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

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

{

if (i == delix_k) temp[i, j] = ind[i, j] / rz;

else temp[i, j] = ind[i, j] - ((ind[delix_k, j] / rz) * ind[i, index_j]);

}

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

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

ind[i, j] = temp[i, j];

int n1 = n;

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

if (proverka_stroka(i)) { n = n - 1; qi--; }

if (proverka_optimalnost(qi) || iter > 100)

{

double x1 = ind[1, m - 1], x2 = ind[2, m - 1], x3 = Math.Abs(ind[3, m - 1]);

label5.Text = "Количество деталей необходимое производить деталей типа А: " + x1.ToString();

label6.Text = "Количество деталей необходимое производить деталей типа B: " + x2.ToString();

label1.Text = "Максимальный доход: " + x3.ToString();

save_results("temp.txt");

button3.Enabled = true;

break;

}

}

catch

{

MessageBox.Show("Решение не найдено!");

return;

}

}

}

//проверка на оптимальное решение

private bool proverka_optimalnost(int k)

{

bool ot = true;

for (int j = 0; j < m-1; j++)

if (ind[k, j] > 0) ot = false;

return ot;

}

//проверка столбцов, если все 0 убрать столбец

private bool proverka_stolbes(int j, int del_k)

{

bool ot = true;

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

if (i != del_k)

if (ind[i, j] != 0) ot = false;

return ot;

}

//проверка строк, если все 0 убрать строку

private bool proverka_stroka(int k)

{

bool ot = true;

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

if (ind[k, j] != 0) ot = false;

return ot;

}

//при закрытии формы удаление временного файла

private void Form1_FormClosing(object sender, FormClosingEventArgs e)

{

System.IO.File.Delete("temp.txt");

}

//очистка данных на форме

private void button2_Click(object sender, EventArgs e)

{

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

{

for (int j = 1; j < 5; j++)

dataGridView1.Rows[i].Cells[j].Value = "";

}

//textBox1.Text = textBox2.Text = textBox3.Text = "";

}

//открытие временного файла

private void button3_Click(object sender, EventArgs e)

{

System.Diagnostics.Process.Start("notepad.exe", "temp.txt");

}

private void button4_Click(object sender, EventArgs e)

{

Form F = new AboutBox1();

F.ShowDialog();

}

}

}

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

В тестировании программного модуля будет сравниваться результаты найденные на Microsoft Excel через «Поиск решения» и результаты вычислений нашей программы.

Рисунок 6 - Вычисления через «Поиск решения»

Рисунок 7 - Результаты вычислений программы

Тест показал что результаты программы совпадают с результатами вычислений через «Поиск решения».

Заключение

В данном курсовом проекте был рассмотрен симплексный метод. Алгоритм программы реализован на перспективной технологии программирования - C# (Microsoft Visual Studio 2010). Выполнены все пункты задания. При этом программа проверяет все промежуточные результаты, вводимые пользователем, и, в случае необходимости, выдает сообщения об ошибках. Такая программа может быть использована для быстрых и удобных вычислений по теме минимизация функций. Приложение информацию о программе. Тестирование показало, что приложение работает корректно.

Литература

1. Лабораторный практикум для студентов специальности 1-53 01 02 «Автоматизированные системы обработки информации» по дисциплине «Системный анализ и исследование операций»

2. Нелинейное программирование Теория и алгоритмы. Перевод с английского Т. Д. Березневой и В. А. Березнева под редакцией Д. Б. Юдина.

3. Ф. Гилл, У. Мюррей, М. Райт практическая оптимизация. Перевод с английского В.Ю.Лебедева Под редакцией А.А.Петрова.

4. ПРИКЛАДНОЕ НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ Перевод с английского И. М. БЫХОВСКОЙ и Б. Т. ВАВИЛОВА Под редакцией М, Л. БЫХОВСКОГО.

5. Экономико-математические методы и модели : учеб. пособие / Под общ. ред. А.В Кузнецова. 2-е изд. - Минск : БГЭУ, 2000. - 412 с.

6. Сборник задач и упражнений по высшей математике. Математическое программирование / Под общ. ред. А. В. Кузнецова - Минск: Вышейшая школа, 1995. - 327 с.

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