тематические методы исследования операций РГЗ 1 Оптимальное управление транспортными потока
Работа добавлена на сайт samzan.net:
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ, МОЛОДЕЖИ И СПОРТА УКРАИНЫ
ОДЕССКИЙ НАЦИОНАЛЬНЫЙ МОРСКОЙ УНИВЕРСИТЕТ
КОРАБЛЕСТРОИТЕЛЬНЫЙ ФАКУЛЬТЕТ
Кафедра «Информационные технологии»
«Математические методы исследования операций»
РГЗ №1
«Оптимальное управление транспортными потоками»
Вариант 10
Выполнил:
студент КСФ
IV курса 3 группы
Коробкин Д.И.
Проверил:
доц. Ширшков А.К.
асс. Личикаки Н.К.
Одесса 2013
-
Оптимизационные задачи – основа целенаправленного и эффективного управления.
Этапы решения оптимизационной задачи
1) разработка содержательной постановки задачи
2) разработка математической модели
3) информационная модель
4) решение задачи
5) постоптимизационный анализ решения
- Структура оптимизационной модели.
- управляющие переменные — параметры объекта, на выбор и величину которых мы можем влиять. Управляющие переменные определяют многовариантность решений.
Примечание: если многовариантности решения нет, то отсутствует и оптимизация
- система ограничений — ограниченные ресурсы объекта: материальные, производственные, финансовые, трудовые и т.д. Система ограничений определяет область допустимых решений задачи (ОДР)
- целевая функция (критерий оптимальности) — параметры, по экстремуму которых (минимум, максимум) среди допустимых решений выбирается оптимальное решение
- Содержательная постановка оптимизационной транспортной задачи.
Даны три пункта погрузки А1, А2, А3 с объёмами запаса а1, а2, а3.
Даны пункты назначения В1, В2, В3, В4 с объёмами спроса b1, b2, b3, b4. Даны маршруты и затраты по перевозке груза из точек Аi в точки Bj. Необходимо вычислить план перевозки, обеспечивающий доставку груза с минимальными суммарными затратами.
- Математическая модель.
- управляющие переменные
Общий вид матрицы задачи:
|
|
Запасы |
||||
|
Потребности |
(– тарифы).
xij — маршрут поставки из точки Аi в точку Вj и объём по маршруту (xij>=0)
- система ограничений
Ограничения по запасам:
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)
- целевая функция — минимальная суммарная величина затрат
F = c11x11 + c12x12 + c13x13 + c14x14 + c21x21 + c22x22 + c23x23 + c24x24 + c31x31 + c32x32 + c33x33 + c34x34 - > min
- Информационная модель.
- Матрица, содержащая значения переменных для исходной задачи
|
|
Запасы |
||||
|
3 |
5 |
6 |
4 |
250 |
|
|
4 |
3 |
2 |
5 |
260 |
|
|
7 |
3 |
5 |
2 |
300 |
|
|
Потребности |
130 |
140 |
150 |
180 |
- Система ограничений
Ограничения по запасам
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
- Целевая функция:
F = 3x11 + 5x12 + 6x13 + 4x14 + 4x21 + 3x22 + 2x23 + 5x24 + 7x31 + 3x32 + 5x33 + 2x34 — > min
- Расчет опорного плана транспортной задачи.
- Проверка закрытости транспортной задачи
аi = bj:
аi = 250 + 260 + 300 = 810
b = 130 + 140 + 150 + 180 = 600
Данная задача является открытой, так как аi >bj
аi -bj = 210
Чтобы преобразовать данную задачу к закрытой транспортной задаче, необходимо добавить фиктивную точку:
Bj+1 = (ai – bj) * 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) метод северо-западного угла
F1(Х1) = 1980 у.е;
2) метод минимального тарифа.
F2(Х2) = 1470 у.е;
3) метод потенциалов:
F3(Х3) = 1740 у.е;
F4(Х4) = 1470 у.е;
.
Графовая модель данной транспортной задачи:
A1 150 B1
120
B2
A2 20
150
90 B3
120
A3
180 B4
B5
Вывод.
Определив динамику сумм транспортных затрат и построив график динамики изменения затрат можно сделать вывод, что из представленных методов наиболее эффективными являются: метод минимального элемента и метод потенциалов, т.к. они позволяет максимально снизить затраты, что и требуется в задаче.
2. Тема 12. Утилитаристская этика Вопросы 1 Общий смысл и фундаментальные принципы утилитаризма
3. Лабораторная работа 6 Алгоритмы и программы реализации численных методов решений алгебраических и транс
4. ПРЕДНАУКА ДРЕВНЕВОСТОЧНОЙ КУЛЬТУРЫ Структура- Время возникновения
5. тематической формализация задачи
6. Тема- Оволодіння правовими знаннями основа формування професії юриста
7. Зарождение философии как свободного критического мышления
8. 2 Кейс Анализ фотографии рабочего времени В ходе анализа деятельности предприятия было выявлено чт
9. это фундамент на котором покоятся гражданская свобода и государственный демократизм
10. Ru Все книги автора Эта же книга в других форматах Приятного чтения Данияр Сугралинов Кирпичи
11. ЛАБОРАТОРНАЯ РАБОТА 1.4
12. реферат дисертації на здобуття наукового ступеня кандидата філологічних наук Сімферополь ' 2002 Ди
13. Створення та конфігурація віртуальних машин за допомогою VMware Player
14. РЕФЕРАТ По дисциплине- Методика преподавания в высшей школе
15. Выдающийся портрет античности Сократ
16. Ладно я выскажусь
17. тема госуправления
18. Реферат на тему- Фитопланктон как начальная стадия в рационе питания гидробионтов
19. тобто в ході визвольної війни відбувався процес державотворення викликаний всенародним прагненням до зві
20. Петр Бекетов