Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ, МОЛОДЕЖИ И СПОРТА УКРАИНЫ
ОДЕССКИЙ НАЦИОНАЛЬНЫЙ МОРСКОЙ УНИВЕРСИТЕТ
КОРАБЛЕСТРОИТЕЛЬНЫЙ ФАКУЛЬТЕТ
Кафедра «Информационные технологии»
«Математические методы исследования операций»
РГЗ №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
Вывод.
Определив динамику сумм транспортных затрат и построив график динамики изменения затрат можно сделать вывод, что из представленных методов наиболее эффективными являются: метод минимального элемента и метод потенциалов, т.к. они позволяет максимально снизить затраты, что и требуется в задаче.