Расчетно-графическая работа3

МИНИСТЕРСТВО НАУКИ И ОБРАЗОВАНИЯ УКРАИНЫ

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

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

Расчётно-графическое задание №1

ПО ДИСЦИПЛИНЕ «МАТЕМАТИЧЕСКИЕ МЕТОДЫ»

ТЕМА: «ОПТИМИЗАЦИЯ ТРАНСПОРТНЫХ ПЕРЕВОЗОК»

Выполнила

студент КСФ 3/3

Боканча А.М.

проверил:

доцент Ширшков А.С.

г.Одесса

2006 год

• Постановка задачи(Вариант 11) Из Ильичёвска,Измаила и Мариуполя необходимо вывезти 280, 300 и 320 тыс.ящиков водки «Nemiroff» соответственно. Порт Мариуполя может принять 120 тыс.тонн водки,Ротрдама—150 ,Адена--120,Бременхафена—180 тыс.тонн .Каким наиболее оптимальным методом распределить груз между портами, если тарифы перевозок между поставщиками и заданными портами можно задать такой матрицей:

	В1	В2	В3	В4
D1	^6	^4	^3	^5
D2	^7	^3	^4	^2
D3	^4	^3	^2	^5

d1=280,d2=300,d3=320

b1=120,b2=150,b3=120,b4=180

• Граф предметной области—двухдольный, взвешенный, ориентированный, полный.

b1

a1 b2

a2 b3

a3 b4

ci

• Информационная матрица модели

	Мариуполь 120	Ротрдам 150	Аден 120	Бременхафен 180
Ильичёвск 280	Х 11 ^6	Х 12 ^4	Х 13 ^3	Х 14^5
Измаил 300	Х 21 ^7	Х 22 ^3	Х 23 ^4	Х 24^2
Мариуполь 320	Х 31 ^4	Х 32^3	Х 33 ^2	Х 34 ^5

Проверим закрытость:d_i=280+300+320=900, b_j=120+150+120+180=570.Сведём систему к закрытой путём добавления фиктивной точки b₅= 900-570=330,и получим

	120	150	120	180	330
280	Х 11 ^6	Х 12 ^4	Х 13 ^3	Х 14^5	Х 15^0
300	Х 21 ^7	Х 22 ^3	Х 23 ^4	Х 24^2	Х 25^0
320	Х 31 ^4	Х 32^3	Х 33 ^2	Х 34 ^5	Х 35^0

• Решим транспортную задачу методом северо-западного угла. Недостаток этого метода в том, что не учитываются тарифы. Значения переменных вычисляются по очереди в каждом крайнем северо-западном узле по правилу max х_ij= min. В итоге получаем опорный план—первое допустимое значение.

	120	150	120	180	330
280	Х 11 ^6	Х 12 ^4	Х 13 ^3	Х 14^5	Х 15^0
300	Х 21 ^7	Х 22 ^3	Х 23 ^4	Х 24^2	Х 25^0
320	Х 31 ^4	Х 32^3	Х 33 ^2	Х 34 ^5	Х 35^0

Рассчитаем элементы:

Х ₁₁= min{280,120}=120. d1=280-120=160. b1=120-120=0

После первого шага таблица примет вид:

	120	150	120	180	330
160	120 ^6	Х 12 ^4	Х 13 ^3	Х 14^5	Х 15^0
300	---- ^7	Х 22 ^3	Х 23 ^4	Х 24^2	Х 25^0
320	---- ^4	Х 32^3	Х 33 ^2	Х 34 ^5	Х 35^0

Теперь необходимо вычислить

Х ₁₂= min{160,150}=150.

Аналогично будем повторять до тех пор , пока таблица не заполнится.

Итоговый вариант приведен ниже:

	0	0	0	0	0
0	120 ^6	150 ^4	10 ^3	---^5	----5^0
0	---- ^7	--- ^3	110 ^4	180^2	10^0
0	---- ^4	---^3	--- ^2	--- ^5	320^0

Рассчитаем значение целевой функции(минимальные суммарные транспортные затраты) по формуле

F=c_i*x_ij

F₁=120*6+150*4+10*3+110*4+180*2+10*0+320*0=2150$

• Решим транспортную задачу методом минимального элемента, в котором за счёт учёта тарифов перекрывается недостаток предыдущего метода.То есть для пути с минимальной стоимостью перевозки назначается максимальный объем груза, и снова процесс проходит итерационно.В итоге получим таблицу:

	120	150	120	180	330
280	70 ^6	--- ^4	--- ^3	--- ^5	210 ^0
300	--- ^7	--- ^3	--- ^4	180 ^2	120 ^0
320	50 ^4	150 ^3	120 ^2	--- ^5	--- ^0

Пересчитаем транспортные затраты:

F₂ =70*6+180*2+50*4+150*3+120*2=1670$.

В итоге видно, что перевозка стала на

1-100*(1670/2150)=22% выгоднее, то есть эффективность перевозки повысилась без привлечения дополнительных капитальных и эксплуатационных затрат.

• Оптимизация опорного плана методом потенциалов.

Шаг1. n+m-1=5+3-1=7—совпадает с количеством базисных переменных, значит решение не вырождено и можно применять метод потенциалов.

Шаг2. вычисляем потенциалы строк и столбцов, учитывая правило --- _i +_j =c_ij.

	120	150	120	180	330
280	70 ^6	--- ^4	--- ^3	--- ^5	210 ^0	1= 2
300	--- ^7	--- ^3	--- ^4	180 ^2	120 ^0	2= 2
320	50 ^4	150 ^3	120 ^2	--- ^5	--- ^0	3=0
	1= 4	2= 3	3= 2	4= 0	5= -2

Шаг3. Для свободных переменных вычисляем разности по формуле _ij= c_ij-(_i +_j):

₁₂ = 4-(3+2)= -1, ₁₃ = 3-(2+2)= -1, ₁₄ = 5-(0+2)= 3, ₂₁ = 7-(4+2)= 1, ₂₂ = 3-(3+2)= -2, ₂₃ = 4-(2+2)= 0, ₃₄ = 5-(0+0)= 5, ₃₅ = 0-(-2+0)= 2.

Шаг 4. Проверим критерий оптимальности решения. Так как некоторые разности <0, то решение не оптимально.

Шаг5. Строим цикл пересчёта, для этого вводим в базис свободную переменную х _22.

	120	150	120	180	330
280	-- ^6	--- ^4	--- ^3	--- ^5	^0	1= 2
300	--- ^7	^3	--- ^4	180 ^2	-- ^0	2= 2
320	^4	-- ^3	120 ^2	--- ^5	--- ^0	3=0
	1= 4	2= 3	3= 2	4= 0	5= -2

max х ₂₂ = min{150,70,120,180}=70.Получим новый базис : х ₂₂ =70, х ₃₂ =80, х ₃₁ =120,

х ₁₅=280, х ₂₅ =50, х ₂₄ =110.

К полученному решению применяем вторую операцию.

Шаг1.2 n+m-1=5+3-1=7

	120	150	120	180	330
280	--- ^6	--- ^4	--- ^3	--- ^5	280 ^0	1= 0
300	--- ^7	70 ^3	--- ^4	180 ^2	50 ^0	2= 0
320	120 ^4	80 ^3	120 ^2	--- ^5	--- ^0	3=0
	1= 4	2= 3	3= 2	4=2	5=0

Шаг2.2. вычисляем потенциалы строк и столбцов

Шаг3.2. Для свободных переменных вычисляем разности: ₁₁ = 6-(4+0)=2, ₁₂ = 4-(3+0)= 1,

₁₃ = 3-(2+0)= 1, ₁₄ =5-(2+0)=3,₂₁ = 7-(4+0)=3, ₂₃ = 4-(2+0)=2, ₃₄ = 5-(2+0)=3, ₃₅ = 0.

Шаг 4.2. Проверим критерий оптимальности решения. Так как все разности 0, то решение оптимально. Пересчитаем транспортные затраты:F_опт=70*3+180*2+120*4+80*3+120*2=1530$.

В итоге получим график динамики понижения затрат при оптимизации: