Пояснительная записка к курсовой работе По дисциплине «Методы оптимизации» icon

Пояснительная записка к курсовой работе По дисциплине «Методы оптимизации»






Скачать 146.55 Kb.
НазваниеПояснительная записка к курсовой работе По дисциплине «Методы оптимизации»
Вилесов И. М
Дата конвертации21.07.2013
Размер146.55 Kb.
ТипПояснительная записка
Министерство образования и науки Российской Федерации


Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Ивановский государственный энергетический университет им. В. И. Ленина»


Кафедра программного обеспечения компьютерных систем


Пояснительная записка к курсовой работе

По дисциплине «Методы оптимизации»

Тема «Методы решения транспортной задачи»


Выполнили: ст. гр. 3-42

Вилесов И. М.

Зайцев М. А.

Боровиков Л.А.

Проверил: к.т.н.

Музюкин М. А.


Иваново 2013


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

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


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

Данная задача принадлежит к группе задач, удовлетворяющих условию баланса:



Это означает, что общий запас груза на всех пунктах хранения равен суммарной потребности всех пунктов назначения.


Пусть xij – количество груза, перевозимого из пункта Ai в пункт Bj.

Суммарная стоимость перевозок имеет вид:



Где сij – затраты на перевозку единицы груза из пункта Ai в пункт Bj.

Ограничения представляются уравнениями вывоза и привоза груза:







Решение системы уравнений (1)-(3) называется планом перевозки.

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




сij – затраты на перевозку единицы груза из пункта Ai в пункт Bj будут рассчитываться по формуле:



Где:

dij - расстояние между пунктами Ai и Bj в километрах.

r - расход топлива на километр.

p – стоимость бензина.

s – скорость движения транспортных средств использующихся для перевозки товаров.

q – оплата водителя.


Метод решения



  1. Найти начальный план перевозок.

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



Для нахождения начального плана перевозок используется метод «северно-западного угла». Улучшение производится по методу «потенциалов».


Метод «северо-западного угла»

Клетки матрицы где xij > 0 называются базисными, остальные, где xij = 0 – свободными.

В матрице имеется (m+n-1) базисных клеток.

Значения xij заполняются по формуле:




Вычисление начинается с элемента x11, находящегося в северо-западном углу матрицы.


Метод «потенциалов»

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

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

Сдвиг по циклу на число t>0. Значения xij стоящие в положительных вершинах увеличиваются на число t, а значения в отрицательных вершинах уменьшаются.


Псевдокод

  1. Найти начальный план перевозок.

  2. Для каждой базисной клетки составить уравнение .

Для определенности =0. Тогда все остальные потенциалы находятся однозначно.

  1. Для каждой свободной клетки вычислить относительные оценки



  1. Если все относительные оценки не отрицательны, то найденный план перевозок будет оптимальным. Иначе найти наименьшую отрицательную оценку.

  2. Для свободной клетки с минимальной отрицательной оценкой построить означенный цикл.

  3. Выполнить сдвиг по циклу, на величину t>0, равную наименьшему из чисел, стоящих в отрицательных вершинах. Перейти к шагу 2.



Контрольный пример

Решим задачу со следующими параметрами:

  1. Количество магазинов 5.

  2. Количество складов 4.

  3. Таблица расстояний .

Потребитель 0Потребитель 1Потребитель 2Потребитель 3

  1. Потребитель 4Поставщик 015 км18 км20 км21 км25 кмПоставщик 15 км20 км23 км18 км6 кмПоставщик 223 км20 км21 км22 км15 кмПоставщик 312 км18 км16 км14 км10 кмСуммарные потребности 180

  2. Запас поставщиков:

  3. Поставщик 0 – 48

  4. Поставщик 1 – 72

  5. Поставщик 2 – 20

  6. Поставщик 3 – 40

  7. Потребности потребителей:

  8. Потребитель 0 – 57

  9. Потребитель 1 – 23

  10. Потребитель 2 – 67

  11. Потребитель 3 – 18

  12. Потребитель 4 – 15

  13. Выберем транспорт «Газель», тогда значения расход топлива будет равен 0.1, цена на бензин равна 28.7, средняя скорость равна 58 км/ч.

Тогда матрица цен будет выглядеть так:

Потребитель 0Потребитель 1Потребитель 2Потребитель 3Потребитель 4Поставщик 068.9182.6991.8896.47114.85Поставщик 122.9791.88105.6682.6927.56Поставщик 2105.6691.8896.47101.0768.91Поставщик 355.1382.6973.5164.3145.94


Начальный план перевозок:



Итерация №1:

Потребитель 0Потребитель 1Потребитель 2Потребитель 3Потребитель 4Поставщик 0804000Поставщик 14923000Поставщик 2002000Поставщик 30071815Затраты = 11756.4

Итерация №2:

Потребитель 0Потребитель 1Потребитель 2Потребитель 3Потребитель 4Поставщик 0084000Поставщик 15715000Поставщик 2002000Поставщик 30071815Затраты = 11315.36


Итерация №3(финальный результат):

Потребитель 0Потребитель 1Потребитель 2Потребитель 3Потребитель 4Поставщик 00232500Поставщик 15700015Поставщик 2002000Поставщик 30022180Затраты = 10626.24




Листинг программы

private void button1_Click(object sender, EventArgs e)

{

dataGridView1.ColumnCount = N = Convert.ToInt32(textBox1.Text) + 1;

dataGridView1.RowCount = M = Convert.ToInt32(textBox2.Text) + 1;

if (N == 1 || M == 1)

{

MessageBox.Show("Значения должны быть >0", "Ошибка");

}

rasstoyanie = new double[M - 1, N - 1];

pokupateli = new double[N - 1];

postavshiki = new double[M - 1];

cena = new double[M - 1, N - 1];

int i, j;

for (i = 0; i < M - 1; ++i)

for (j = 0; j < N - 1; ++j)

{

dataGridView1.Columns[j].Name = "Потребитель " + j;

dataGridView1.Columns[j].Width = 122;

dataGridView1.RowHeadersWidth = 122;

dataGridView1.Rows[i].HeaderCell.Value = "Поставщик " + i;

}

dataGridView1.Columns[N - 1].Name = "Запасы";

dataGridView1.Rows[M - 1].HeaderCell.Value = "Потребности";

for (i = 0; i < M - 1; i++)

{

for (j = 0; j < N - 1; j++)

{

rasstoyanie[i, j] = Convert.ToDouble(Interaction.InputBox("РасстояниемеждуПотребителем "+ j + " иПоставщиком " + i));

}

}

zapolnenie();

Proverca();//Проверка правильности ввода значений Запас и Потребность

button1.Visible = false;

button2.Visible = true;

button3.Visible = true;

}


double[,] SZU(double[] pokupatel, double[] postavshik) // методсеверозападногоугла

{

double[,] raspredelenie1 = new double[M - 1, N - 1];

for (int i = 0; i < M - 1; i++)

{

for (int k = 0; k < N - 1; k++)

{ raspredelenie1[i, k] = 0; }

}

int j = 0;

for (int i = 0; i < M - 1; i++)

{

while (postavshik[i] != 0)

{

if (pokupatel[j]

{

postavshik[i] = postavshik[i] - pokupatel[j];

raspredelenie1[i, j] = raspredelenie1[i, j] + pokupatel[j];

pokupatel[j] = 0;

j++;

}

else

{

if (pokupatel[j] >postavshik[i])

{

raspredelenie1[i, j] = raspredelenie1[i, j] + postavshik[i];

pokupatel[j] = pokupatel[j] - postavshik[i];

postavshik[i] = 0;

}

else

{

if (pokupatel[j] == postavshik[i])

{

raspredelenie1[i, j] = raspredelenie1[i, j] + pokupatel[j];

postavshik[i] = 0;

pokupatel[j] = 0;

j++;

}

}

}

}

}

return raspredelenie1;

}


private void reshenie()//Метод потенциалов

{

if (first)

{

stringstr = automobil.Text;

switch (str)

{

case "КаМАЗ": rashod = 0.12; cenabenzina = 25.5; skorost = 56; break;

case "МаЗ": rashod = 0.15; cenabenzina = 25.5; skorost = 65; break;

case "MAN": rashod = 0.10; cenabenzina = 25.5; skorost = 53; break;

case "Газель": rashod = 0.10; cenabenzina = 28.7; skorost = 58; break;

default: MessageBox.Show("Транспортное средство выбрано не верно!", "Ошибка"); return;

}

for (int i = 0; i < M - 1; i++) // расчет цен для поставки единицы груза из ai в bj

{

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

{

cena[i, j] = (rasstoyanie[i, j] * rashod * cenabenzina)

+ ((rasstoyanie[i, j] / skorost) * zarplata);

}

}

first = false;

}

double?[] alpha = new double?[M - 1];

for (int i = 0; i
{

alpha[i] = null;

}

double?[] beta = new double?[N - 1];

for (int i = 0; i
{

beta[i] = null;

}

alpha[0] = 0;

for (int i = 0; i < M - 1; i++)

{

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

{

if (raspredelenie[i, j] != 0)

{

if (alpha[i] != null)

{

beta[j] = cena[i, j] - alpha[i];

}

else

{

alpha[i] = cena[i, j] - beta[j];

}

}

}

}


double min = 0;

int x = 0, y = 0;

for (int i = 0; i < M - 1; i++)

{

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

{

if (raspredelenie[i, j] == 0)

{

double delta;

if (alpha[i] == null || beta[j] == null)

{

delta = 0;

}

else

{

delta = cena[i, j] - alpha[i].Value - beta[j].Value;

}


if (delta < min)

{

min = delta;

x = i;

y = j;

}

}

}

}

if (min >= 0)

{

MessageBox.Show("Рассчетзакончен!!!" + "\nРезультатравен " + Result.Text);

theEnd = false;

return;

}

List
cycle = FindCycle(new Point(x, y));

if (cycle != null)

{

min = raspredelenie[cycle[1].X, cycle[1].Y];

for (int i = 3; i
{

min = Math.Min(min, raspredelenie[cycle[i].X, cycle[i].Y]);

}

for (int i = 0; i
{

if (i % 2 == 0)

{

raspredelenie[cycle[i].X, cycle[i].Y] += min;

}

else

{

raspredelenie[cycle[i].X, cycle[i].Y] -= min;

}

}

double result = 0;

for (int i = 0; i
{

for (int j = 0; j
{

dataGridView1.Rows[i].Cells[j].Value = raspredelenie[i, j];

result += cena[i, j] * raspredelenie[i, j];

}

}

Result.Visible = true;

Result.Text = "Результат = " + result;

}

else

{

MessageBox.Show("Рассчетзакончен!!!" + "\nРезультатравен " + Result.Text);

theEnd = false;

return;

}

}


private List
FindCycle(Point start)//поискцикла

{

List
cycle = new List
();

cycle.Add(start);

if (this.HorizontalLine(start, start, cycle))

{

return cycle;

}

return null;

}


privateboolHorizontalLine(Point start, Point current, List
cycle)

{

for (int i = 0; i < N - 1; ++i)

{

Point newPoint = new Point(current.X, i);

if (i != current.Y&&raspredelenie[current.X, i] != 0)

{

if (i == start.Y)

{

cycle.Add(newPoint);

return true;

}


if (this.VerticalLine(start, newPoint, cycle))

{

cycle.Add(newPoint);

return true;

}

}

}


return false;

}


privateboolVerticalLine(Point start, Point current, List
cycle)

{

for (int i = 0; i < M - 1; ++i)

{

if (i != current.X&&raspredelenie[i, current.Y] != 0)

{

if (this.HorizontalLine(start, new Point(i, current.Y), cycle))

{

cycle.Add(new Point(i, current.Y));

return true;

}

}

}

return false;

}


private void Form1_SizeChanged(object sender, EventArgs e)

{

dataGridView1.Width = ClientRectangle.Width;

}


}

}

Ваша оценка этого документа будет первой.
Ваша оценка:

Похожие:

Пояснительная записка к курсовой работе По дисциплине «Методы оптимизации» iconПояснительная записка к курсовой работе на тему Гитарный симулятор по дисциплине «Методы программирования»
137kb.  
Пояснительная записка к курсовой работе По дисциплине «Методы оптимизации» iconПояснительная записка Курсовая работа по дисциплине «Методы оптимизации» тпжа 220201. 129 Пз
345.5kb.  
Пояснительная записка к курсовой работе По дисциплине «Методы оптимизации» iconПояснительная записка (релиз).docx
510.8kb.   Пояснительная записка к курсовой работе по дисциплине «теория электрической связи»
Пояснительная записка к курсовой работе По дисциплине «Методы оптимизации» iconПояснительная записка Курсовая работа по дисциплине «Методы оптимизации» тпжа 220201. 072 Пз
306.7kb.   Цель задания: Найти минимум функции методами прямого поиска и градиентными методами
Пояснительная записка к курсовой работе По дисциплине «Методы оптимизации» iconПояснительная записка Ккурсовой работе по дисциплине «Теория языков программирования и методы трансляции» на тему: "Учебный транслятор"
1021.7kb.  
Пояснительная записка к курсовой работе По дисциплине «Методы оптимизации» iconПояснительная записка к курсовой работе по дисциплине Организация ЭВМ
209.1kb.  
Пояснительная записка к курсовой работе По дисциплине «Методы оптимизации» iconПояснительная записка к курсовой работе по дисциплине «Основы Кибернетики»
109.6kb.  
Пояснительная записка к курсовой работе По дисциплине «Методы оптимизации» iconПояснительная записка к Курсовой работе по дисциплине «Функциональное и логическое программирование»
98.1kb.  
Пояснительная записка к курсовой работе По дисциплине «Методы оптимизации» iconПояснительная записка к курсовой работе по дисциплине «Объектно-ориентированное программирование»
236.6kb.  
Пояснительная записка к курсовой работе По дисциплине «Методы оптимизации» iconПояснительная записка к курсовой работе по дисциплине Теория вычислительных процессов
20.5kb.  
Разместите кнопку на своём сайте:
Рефераты


База данных защищена авторским правом ©CoolReferat 2000-2018
обратиться к администрации | правообладателям | пользователям
Основная база рефератов
Рефераты