Будь умным!


У вас вопросы?
У нас ответы:) SamZan.ru

тематические методы исследования операций РГЗ 1 Оптимальное управление транспортными потока

Работа добавлена на сайт samzan.ru: 2016-03-30


МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ, МОЛОДЕЖИ И СПОРТА  УКРАИНЫ

ОДЕССКИЙ НАЦИОНАЛЬНЫЙ МОРСКОЙ УНИВЕРСИТЕТ

КОРАБЛЕСТРОИТЕЛЬНЫЙ ФАКУЛЬТЕТ

Кафедра «Информационные технологии»

«Математические методы исследования операций»

РГЗ №1

«Оптимальное управление транспортными потоками»

Вариант 10

     

  

Выполнил:

студент КСФ

IV курса  3 группы

Коробкин Д.И.

   

Проверил:

доц. Ширшков А.К.   

асс. Личикаки Н.К.  

Одесса  2013

  1.  
    Оптимизационные задачи – основа целенаправленного и эффективного управления.

Этапы решения оптимизационной задачи

1) разработка содержательной постановки задачи

2) разработка математической модели

3) информационная модель

4) решение задачи

5) постоптимизационный анализ решения

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

Примечание: если многовариантности решения нет, то отсутствует и оптимизация

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

  1.  Содержательная постановка     оптимизационной транспортной задачи.

Даны три пункта погрузки А1, А2, А3 с объёмами запаса а1, а2, а3.

Даны пункты назначения В1, В2, В3, В4 с объёмами спроса b1, b2, b3, b4. Даны маршруты и затраты по перевозке груза из точек Аi в точки Bj. Необходимо вычислить план перевозки, обеспечивающий доставку груза с минимальными суммарными затратами.

  1.  Математическая модель.
  2.  управляющие переменные

Общий вид матрицы задачи:

                     

 Запасы

Потребности

(– тарифы).

xij — маршрут поставки из точки Аi в точку Вj и объём по маршруту (xij>=0)

  1.  система ограничений

Ограничения по запасам:

x11 + x12 + x13 + x14 = a1

x21 + x22 + x23 + x24 = a2

x31 + x32 + x33 + x34 = a3

Ограничения по спросу:

x11 + x21 + x31 + x41 = b1

x12 + x22 + x32 + x42 = b2

x13 + x23 + x33 + x43 = b3

x14 + x24 + x34 + x44 = b4

xij>=0 (i = 1, 2, 3; j = 1, 2, 3, 4)

  1.  целевая функция — минимальная суммарная величина затрат

F = c11x11 + c12x12 + c13x13 + c14x14 + c21x21 + c22x22 + c23x23 + c24x24 + c31x31 + c32x32 + c33x33 + c34x34 - > min

  1.  Информационная модель.
  2.  Матрица, содержащая значения переменных для исходной задачи

                 

Запасы

3

5

6

4

250

4

3

2

5

260

7

3

5

2

300

Потребности

130

140

150

180

  1.  Система ограничений

Ограничения по запасам

x11 + x12 + x13 + x14 = 250

x21 + x22 + x23 + x24 = 260

x31 + x32 + x33 + x34 = 300

Ограничения по спросу:

x11 + x21 + x31 + x41 = 130

x12 + x22 + x32 + x42 = 140

x13 + x23 + x33 + x43 = 150

x14 + x24 + x34 + x44 = 180

  1.  Целевая функция:

F =  3x11 + 5x12 + 6x13 + 4x14 + 4x21 + 3x22 + 2x23 + 5x24 + 7x31 + 3x32 + 5x33 + 2x34   — > min

  1.  Расчет опорного плана транспортной задачи.

- Проверка закрытости транспортной задачи

аi = bj:

аi = 250 + 260 + 300 = 810

b = 130 + 140 + 150 + 180 = 600

Данная задача является открытой, так как аi >bj 

аi -bj  = 210

Чтобы преобразовать данную задачу к закрытой транспортной задаче, необходимо добавить фиктивную точку:

Bj+1 = (aibj) * cij = 0

- Расчет опорного плана методом северо-западного угла

 

Аi                Bj       

130

140

150

180

250

3

5

6

4

260

4

3

2

5

300

7

3

5

2

Вычислим опорный план (1-е допустимое значение)методом северо-западного угла (СЗУ)

Max x11 = min{260;150} = 150 - базисная,  x21= x31 = 0 - свободные

Max x12 = min{110;120} = 110 - базисная,  x13= x14 = 0 – свободные

Max x22 = min{300;10} = 10 - базисная,  x23 = 0 – свободная

Max x23 = min{290;170} = 170 - базисная,  x33 = 0 – свободная

Max x24 = min{120;120} = 120 - базисная,  x34 = 0 – свободная

Аi             Bj            

130

140

150

180

210

250

130 (3)

120 (5)

- (6)

- (4)

-

260

- (4)

20 (3)

150 (2)

90 (5)

-

300

- (7)

- (3)

- (5)

90 (2)

210

(В скобках указаны тарифы)

X1 = {130; 120; 20;150; 90;90;210};

F1(X1) = 3*130 + 5*120 + 3*20 + 2*150 + 5*90 + 2*90 + 0*210 = 1980

- Расчет опорного плана методом минимального элемента

            Bj    

Аi                       

150

120

170

120

330

260

№5 130 (3)

  (5)

-6

-4

120

300

- (4)

№3 110(3)

№2 150(2)

 - (5)

-

330

-7

№4 30 (3)

  (5)

№1 180(2)

90

X2={X11=130;  X15=120; X22=110; X23=150; X32=30; X34=180; X35=90}

F2=130*3+120*0+110*3+150*2+30*3+180*2+90*0=1470 у.е.

                    Расчет опорного плана методом потенциалов

Итерация 1

1) проверка невырожденности опорного плана:

N + m -1 = xбаз

3 + 5 – 1 = 7

xбаз = 7

Можно применять метод потенциалов.

Для базисных переменных вычисляем потенциалы строк Ai и столбцов Bj. ; , так как во 2й строке наибольшее количество базисных переменных.

              Bj  

Аi           

b1=130

b2=140

b3=150

b4=180

b5=210

 

250

130 (3)

120 (5)

- (6)

- (4)

-

 a 1 = 2

260

-  (4)

20 (3)

150 (2)

(-)90 (5)

(+)-

 a2 = 0

300

-(7)

- (3)

-(5)

(+)90 (2)

(-)210

a3 = -3

 

b1 =1

b2 = 3

b3 = 2

b4 = 5

b5 = 3

 

Для свободных переменных (Xij=0) вычисляем разности

Δ13=6-(2+2)= 2    Δ25=0-(0+3)= -3

Δ14=4-(2+5)= -3    Δ31=7-(-3+1)= 5

Δ15=0-(2+3)= -5    Δ32=3-(-3+3)= 3

Δ21=4-(0+1)= 3    Δ33=5-(-3+2)= 4

Критерий оптимальности. Данный базис не оптимален, т.к. есть разности Xij<0

Строим цикл пересчета нового базиса. Новая базисная переменная

maxx25= min{90,210}=90

              Bj  

Аi           

b1=130

b2=140

b3=150

b4=180

b5=210

 

250

130 (3)

(-)120(5)

- (6)

- (4)

(+)-

 a 1 =2

260

-  (4)

20 (3)

150 (2)

-(5)

90

 a2 = 0

300

-(7)

(+)-(3)

-(5)

(+)180 (2)

(-)120

a3 = 0

 

b1 =1

b2 = 3

b3 = 2

b4 = 2

b5 = 0

 

X3={X11=130;  X15=120; X22=20; X23=150; X24=90; X32=120; X34=90; X35=90}

F3=130*3+120*0+20*3+150*2+90*5+120*3+90*2+90*0=1740 у.е.

Итерация 2

Проверка невырожденности базиса. n=3, m=5 Xij=3+5-1=7. Можно применять метод потенциалов.

Для базисных переменных вычисляем потенциалы строк ai и столбцов bj. , . Результаты записываем в таблицу расположенную выше.

Для свободных переменных (Xij=0) вычисляем разности

Δ13=6-(2+2)= 2    Δ24=5-(0+2)= 3

Δ14=4-(2+2)= 0    Δ31=7-(0+1)= 6

Δ15=0-(2+0)= -2    Δ32=3-(0+3)= 0

Δ21=4-(0+1)= 3    Δ33=5-(0+2)= 3

Критерий оптимальности. Данный базис не оптимален, т.к. есть разности Xij<0

Строим цикл пересчета нового базиса. Новая базисная переменная

maxx15= min{120,120}=120.

              Bj  

Аi           

b1=130

b2=140

b3=150

b4=180

b5=210

 

250

130 (3)

(-)-(5)

- (6)

- (4)

(+)120(0)

 a 1 =0

260

-  (4)

20 (3)

150 (2)

-(5)

90(0)

 a2 = 0

300

-(7)

(+)120(3)

-(5)

(+)180 (2)

(-)  (0)

a3 = 0

 

b1 =3

b2 = 3

b3 = 2

b4 = 2

b5 = 0

 

X5={X11=130;  X15=120; X22=20; X23=150; X25=90; X31=120; X34=180}

F4=130*3+120*0+20*3+150*2+90*0+120*3+180*2=1470 у.е.

Итерация 3

Проверка невырожденности базиса. n=3, m=5 Xij=3+5-1=7. Можно применять метод потенциалов.

Для базисных переменных вычисляем потенциалы строк ai и столбцов bj.

, . Результаты записываем в таблицу расположенную выше.

Для свободных переменных (Xij=0) вычисляем разности

Δ12=5-(0+3)= 2    Δ24=5-(0+2)= 3

Δ13=6-(0+2)= 4    Δ31=7-(0+3)= 4

Δ14=4-(0+2)= 2    Δ33=5-(0+2)= 3

Δ21=4-(0+3)= 1    Δ35=5-(0+0)= 5

Критерий оптимальности.  Данное базисное решение оптимально. Задача решена. Вычислен оптимальный план перевозок, обеспечивающий минимальные суммарные затраты F4=1470 у.е. при выполнении всех заданных ограничений

  1.  Анализ  эффективности оптимального решения, составление графика  динамики изменения затрат.

В результате вычислений методами северо-западного угла, минимального тарифа и методом потенциалов были получены следующие результаты:

1) метод северо-западного угла

F11) = 1980 у.е;

2) метод минимального тарифа.

F22) = 1470 у.е;

3) метод потенциалов:

F33) = 1740 у.е;

F44) = 1470 у.е;

.

Графовая модель данной транспортной задачи:

A1 150 B1

 120

B2

A2 20

 150

 

 90 B3

 120

A3

 180 B4

B5

Вывод.

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




1. Реферат- Технология ускоренного обучения плаванию
2. ТЕМА МУЗИЧНОЇ ОСВІТИ ВЧИТЕЛІВ ГАЛИЧИНИ У МІЖВОЄННУ ДОБУ Головну увагу в музичному вихованні народу треба з
3. Право общей и долевой собственности
4. 003 1 раз в неделю Натекание вакуумной системым3 Па не более 1
5. Класс птицы, общая характеристика класса
6. по теме- Бактерии грибы Текст контрольной работы содержит 5 заданий которые направлены на проверку усво
7. Множественность преступлений
8. х гг XIX в протекал глубинный процесс формирования консервативной политической идеологии питавшейся из сл
9.  225.1 АПК Обеспечительные меры встречное обеспечение по делам по корпоративным спорам Особенности расс
10. і. 2 травня ~ Виселення з готелю.html
11. ТЕМА МЕТОДИЧНІ ВКАЗІВКИ до виконання курсової роботи для студентів спеціальності 6
12. Основные сведения о гиперболоидных зубчатых передачах Гиперболоидная зубчатая передача ~ это зубчатая п
13. Тема- Критерії вибору параметричних рядів
14. деструктивную роль и причины традиционного характера специфичные для каждой страны но исторически ока.html
15. двигательного аппарата центральной нервной сердечнососудистой иммунной и половой систем заболевания ко
16. Sezim Клуб поэзии Sezim ~ это творческое объединение группы студентов и сотрудников вуза лиц увлеченн.
17. Я ГОТОВ НА ВСЁ получат поощрительные призы.html
18. реферат дисертації на здобуття наукового ступеня кандидата хімічних наук Київ 6 Дисертаці
19. вступающего в реакцию или образующегося при реакции за единицу времени в единице объема системы
20. Формирование личности в младшем школьном возрасте