Определение оптимальной загрузки ВС

Размещено на http://www.allbest.ru/

Министерство транспорта Российской Федерации

Федеральное агентство железнодорожного транспорта

ГОУ ВПО «Дальневосточный государственный университет путей сообщения»

Факультет Воздушных сообщений

Контрольная работа по дисциплине

«Информационные технологии на воздушном транспорте»

Выполнила: Мисько Ю.С.

студентка группы 554

Хабаровск 2009г.

1. Практическая часть

Для данного типа самолета известны: предельная коммерческая загрузка Q и полезный объем V в условных единицах. Самолет должен одним рейсом (с промежуточными посадками) обслужить 5 пунктов маршрута и возвратиться в исходный пункт, получив при этом максимальную прибыль. Матрица стоимости перелета из пункта в пункт задается таблицей 1, вследствие различных скидок она не симметричная.

Рейсом может быть перевезено два груза: один более дорогой, но тяжелый, второй полегче, но дешевый. Стоимость единицы веса груза первого вида составляет S1, второго S2.

1. Отношение удельных объемов грузов:

= 1,5;

2. Отношение полезного объема:

300 + 10n₃ = 300 + 10*7 = 370

3. Предельная коммерческая загрузка Q равна:

Q = 100 + 10n1 = 100 + 10*7 = 170

S₁ = = = 1,44

S₂ = 1

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

Таблица 1 - Матрица стоимости перелета

пункты узлы	1	2	3	4	5	6
1	?	25+7=32	45+7=52	15+7=22	30+7=37	25+7=32
2	5+7=12	?	15+7=22	1+7=8	30+7=37	30+7=37
3	20+7=27	15+7=22	?	35+7=42	5+7=12	7
4	20+7=27	15+7=22	25+7=32	?	20+7=27	20+7=27
5	10+7=17	45+7=52	25+7=32	50+7=57	?	5+7=12
6	25+7=32	5+7=12	5+7=12	10+7=17	5+7=12	?

Далее решаем задачу методом ветвей и границ. Пусть матрица стоимостей C_ij перелета из i-го пункта в j-й задана таблицей 2.

Таблица 2

Узлы	1	2	3	4	5	6
1	?	32	52	22	37	32
2	12	?	22	8	37	37
3	27	22	?	42	12	7
4	27	22	32	?	27	27
5	17	52	32	57	?	12
6	32	12	12	17	12	?

Решение:

Определим верхнюю границу маршрута Z_B(T). Верхняя граница - стоимость взятого наугад маршрута. Пусть он будет состоять из звеньев: (1.4); (4.5); (5.3); (3.6); (6.2); (2.1). Тогда в соответствии с Таблицей 2:

Z_B(T) = 22 + 27 + 32 + 7 + 12 + 12 = 112

Отсюда заключаем, что стоимость оптимального маршрута Z(T) ? 112.

Найдем нижнюю границу всего маршрута Н. Для этого проведем редукцию строк и столбцов.

Таблица 3

Узлы	1	2	3	4	5	6	Сi
1	?	10	30	0	15	10	22
2	4	?	14	0	29	29	8
3	20	15	?	35	5	0	7
4	5	0	10	?	5	5	22
5	5	40	20	45	?	0	12
6	20	0	0	5	0	?	12

Таблица 4

Узлы	1	2	3	4	5	6	Сi
1	?	10	30	0	15	10	22
2	0	?	14	0	29	29	8
3	16	15	?	35	5	0	7
4	1	0	10	?	5	5	22
5	1	40	20	45	?	0	12
6	16	0	0	5	0	?	12
Cj	4	0	0	0	0	0	Н=87

Рассматриваем варианты и делаем выбор, какое первое звено включаем в маршрут. Выбирается то звено, которое имеет максимальную величину штрафа.

Таблица 5

Узлы	1	2	3	4	5	6	Сi	Ai
1	?	10	30	0	15	10	22	10
2	0	?	14	0	29	29	8	0
3	16	15	?	35	5	0	7	5
4	1	0	10	?	5	5	22	1
5	1	40	20	45	?	0	12	1
6	16	0	0	5	0	?	12	0
Cj	4	0	0	0	0	0	Н=87
Bj	1	0	10	0	5	0

Таблица 6

Звено (i,j)	1.4	2.1	2.4	3.6	4.2	5.6	6.2	6.3	6.5
Фij	10	1	0	5	1	1	0	10	5

Из Таблицы 6 замечаем, что максимум Ф₁₄ = 10.

В качестве опорного звена выбираем (1.4). Если в маршруты мы не включаем звено (1.4), то нижней границей будет:

Z (T: 1.4) = 87+10=97

Для определения нижней границы стоимости маршрутов включающих звено (1.4), надо преобразовать матрицу стоимости. Исключаем строку 1 и столбец 4.

Таблица 7

Узлы	1	2	3	5	6
2	0	?	14	29	29
3	16	15	?	5	0
4	?	0	10	5	5
5	1	40	20	?	0
6	16	0	0	0	?

Проведем редукцию Таблицы 7.

Таблица 8

Узлы	1	2	3	5	6	Сi	Ai
2	0	?	14	29	29	0	14
3	16	15	?	5	0	0	5
4	?	0	10	5	5	0	5
5	1	40	20	?	0	0	1
6	16	0	0	0	?	0	0
Cj	0	0	0	0	0	H=0
Bj	1	0	10	5	0

Новая нижняя граница для Т, включающего (1.4) равна:

Z (Т: 1.4) = 87+0=87

Проводим вторую итерацию решения по второй матрице.

Таблица 9

Звено (i,j)	2.1	3.6	4.2	5.6	6.2
Фij	15	5	5	1	0

Максимальный штраф у звена (2.1) Ф₂₁ = 15

Новая нижняя граница для Т: 2.1 равна:

Z (Т: 2.1) = 87+15 = 102

Проверяем оставшиеся звенья на возможность подмаршрутов. В нашем случае подмаршрутом может быть следующий: (1.4); (4.2); (2.1) для уже выбранных звеньев (1.4) и (2.1). Чтобы ее исключить, надо сделать звено (4.2) запрещенным.

Таблица 10 - Третья матрица решений

Узлы	2	3	5	6
3	15	?	5	0
4	?	10	5	5
5	40	20	?	0
6	0	0	0	?

Таблица 11

Узлы	2	3	5	6	Сi	Ai
3	15	?	5	0	0	5
4	?	5	0	0	5	0
5	40	20	?	0	0	20
6	0	0	0	?	0	0
Cj	0	0	0	0	H=5
Bj	15	5	0	0

Нижняя граница для маршрута, включающего звено (2.1) равно:

Z (Т: 2.1) = 87+5 = 92

Таблица 12

Звено (i,j)	3.6	4.5	4.6	5.6	6.2	6.3	6.5
Фij	5	0	0	20	15	5	0

Максимум Ф₅₆ = 20

Новая нижняя граница для (Т: 5.6) равна:

Z (Т: 5.6) = 92+20 = 112

Вычеркиваем строку 5 столбец 6, кроме этого С₅₆ = .

Таблица 13 - Четвертая матрица решений.

Узлы	2	3	5
3	15	?	5
4	?	5	0
6	0	0	?

Проводим редукцию.

Таблица 14

Узлы	2	3	5	Сi	Ai
3	10	?	0	5	10
4	?	5	0	0	5
6	0	0	?	0	0
Cj	0	0	0	H=5
Bj	10	5	0

Нижняя граница для Т, включающая звено (5.6) равна:

Z (Т: 5.6) = 92+5 =97

Таблица 15

Звено (i,j)	3.5	4.5	6.2	6.3
Фij	10	5	10	5

Максимум Ф₃₅ = 10

Новая нижняя граница для Т: 3.5 равна:

Z (Т: 3.5) = 97+10 = 107

Таблица 16 - Пятая матрица решений

Узлы	2	3
4	?	5
6	0	0

Проведем редукцию

Таблица 17

Узлы	2	3	Сi	Ai
4	?	0	5	0
6	0	0	0	0
Cj	0	0	H=5
Bj	0	0

Нижняя граница для Т, включающая звено (3.5) равна:

Z (Т: 3.5) = 97+5 = 102

Таблица 18

Звено (i,j)	4.3	6.2	6.3
Фij	0	0	0

Максимум Ф₄₃ = 0

Новая нижняя граница для Т: 4.3 равна:

Z (Т: 4.3) = 102+0 = 102

Таблица 19 - Шестая матрица решений

Узлы	2	Сi	Ai
6	0	0	0
Cj	0	H=0
Bj	0

Новая нижняя граница, включающая (4.3) равна:

Z (Т: 4.3) = 102+0 = 102

Максимальный штраф у звена (6.2) Ф₆₂ = 0

Новая нижняя граница для Т: 6.2 равна:

Z (Т: 6.2) = 102+0 = 102

груз оптимальный прибыль



Рис.1. Промежуточное решение

Построенный полный маршрут будет оптимальным, если его стоимость не превосходит стоимости любого маршрута соответствующего другим ветвлениям дерева.

Мы замечаем, что Z (Т) = 112 > Z (Т: 1.4) = 97.

Отсюда следует, что необходимо исследовать множество маршрутов, не содержащих звена (1.4). Для исключения звена (1.4) из рассмотрения надо в Таблице 2 принять С₁₄ = .

Таблица 20 - Матрица стоимости возврата

Узлы	1	2	3	4	5	6
1	?	32	52	?	37	32
2	12	?	22	8	37	37
3	27	22	?	42	12	7
4	27	22	32	?	27	27
5	17	52	32	57	?	12
6	32	12	12	17	12	?

Делаем редукцию Таблицы 20

Таблица 21

Узлы	1	2	3	4	5	6	Сi	Ai
1	?	0	20	?	5	0	32	0
2	0	?	14	0	29	29	8	0
3	16	15	?	35	5	0	7	5
4	1	0	10	?	5	5	22	1
5	1	40	20	45	?	0	12	1
6	16	0	0	5	0	?	12	0
Cj	4	0	0	0	0	0	Н=97
Bj	1	0	10	5	5	0

Новая нижняя граница Z (Т: 1.4) = 97, что совпадает с ранее найденным значением.

Таблица 22

Звено (i,j)	1.2	1.6	2.4	3.6	4.2	5.6	6.2	6.3	6.5
Фij	0	0	5	5	1	1	0	10	5

Максимальный штраф у звена (6.3) Ф₆₃ = 10.

Новая нижняя граница для Z (Т: 6.3) = 97+10 = 107

Рис.2. Дерево окончательного решения

Оптимальным маршрутом перевозки, как видно на рисунке, является последовательность звеньев: (1,4), (2,1), (5,6), (3,5), (4,3), (6,2). Стоимость перевозки груза по нему составляет 102.

2. Определение оптимальной загрузки ВС

Определим количество груза первого и второго типов, дающее максимальную стоимость (прибыль). Обозначим вес груза первого типа - х1, второго - х2.

Тогда по условию задачи

х₁ + х₂ < Q

Ограничение на габариты груза приводит к неравенству

₁x₁ + ₂x₂ ? V или x₁ + x₂ ? V

Q = 170;

= 370

В численной форме условия - ограничения записываются:

х₁ + х₂ ? 170

3х₁ + х₂ ? 370

x₁ ?0; x₂ ? 0.

Стоимость груза составляет S₁x₁ + S₂x₂.

Пусть S₁ = 1,44; S₂ = 1.Тогда условие максимального выигрыша запишется так:

f₁ (x) = 1,44x₁ + x₂ > max

Для решения задачи воспользуемся симплекс методом, для этого вводим слабые переменные:

x₃ = 370 - 3x₁ - x₂

x₄ = 170 - x₁ - x₂

где x₃ ? 0; x₄ ? 0.

Чтобы от максимума перейти к минимуму целевой функции, условие экстремума перепишем в форме:

f = -2x₁ + x₂ > min

Уменьшаем f , увеличивая x₂ .Переведем x₂ из свободных в базисные, а x₄ - в свободные переменные. Получаем:

x₂ = 370 - x₁ - x₄

x₃ = 170 - 1,44x₁ + x₄

f = -170 - x₁ - x₄

Ей соответствует следующее базисное решение:

X₂ = (0, 170, 170, 0) и f = -170

Увеличиваем x₁ , но так чтобы x₂ и x₃ оставались неотрицательными.

x₁ = 85 - 1/2x₃ + 1/2x₄

x₂ = 85 +1/2x₃ - 3/2x₄

f = -255 + 1/2x₃ + 1/2x₄

Ей соответствует следующее базисное решение:

X₃ = (85, 85, 0, 0) и f = 255.

Оптимальное решение:

X^* = X₃ = (85 ,85 ,0 ,0).

f₁ (x) = - f (x) = 255

Введем прямоугольную систему x₁ O x₂.

Проведем прямую 3х₁ + х₂ = 370

Пусть х₁ = 0, тогда х₂ = 370, при х₂ = 0, х₁ = 123.

Наносим точки (0, 370) и (123, 0) на график и проводим прямую АВ.

Аналогично строим прямую для второго неравенства.

x₁ + х₂ = 170

х₁ = 0, х₂ = 170 х₁ = (0,170);

х₂ = 0, х₁ = 170 х₂ = (170,0).

Для построения линейной функции воспользуемся примером:

1,44х₁ + х₂ = С

Пусть С = 100, тогда х₁ = 0, х₂ = 100; (0,100)

x₂ = 0, х₁ = 69; (69, 0).

Изображаем прямую пунктирной линией, показывая, что изменяя С линия будет перемещаться параллельно самой себе.

Из рисунка следует, что решением системы неравенств при условии max f₁ является точка Р (85, 85). Ей отвечает максимум f₁= 255. Таким образом, аналитическое и геометрическое решения совпали.

Рис. 3. Геометрическое решение

Размещено на Allbest.ru

...