Методические указания по изучению дисциплины и выполнению контрольной работы Для студентов заочного факультета всех специализаций (стр. 5 из 6)

Если все проделать правильно, повторяя изложенный алгоритм расчетов, то в конце получим следующее дерево решений (рис.2).

Рис. 2

Полученный маршрут включает звенья: (1,4); (2,1); (5,6); (3,5); (4,3); (6,2). Остается проверить, является ли он самым дешевым. Для этого предусмотрена процедура возврата, и нам пригодятся рассчитанные стоимости для звеньев с черточками.

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

Мы замечаем, что Z(T)=63 > Z(T:

)=58 .

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

, затем повторить изложенный алгоритм поиска оптимального маршрута. Правда, если в последствии окажется, что нижние границы исследуемого ветвления превысят Z(Т) (в нашем случае 63), то исследование данной ветви прекращается.

Продолжаем разбор нашего примера. Опять возвращаемся к табл. 2, в которой теперь полагаем C₁₄=

. Данные для расчета матрицы стоимости возврата представляются в табл.11.

Таблица 11

Пункты	1	2	3	4	5	6
1		27	43		30	26
2	7		16	1	30	30
3	20	13		35	5	0
4	21	16	25		18	18
5	12	46	27	48		5
6	23	5	5	9	5

Проведем редукцию табл.11 и приходим к табл.12. В табл.12 для краткости одновременно указана редукция строк и столбцов. Вам всегда редукцию следует производить порознь.

Таблица 12

Пункты	1	2	3	4	5	6	Сi	Аi
1		1	17		4	0	26	1
2	1		15	0	29	29	1	1
3	15	13		35	5	0	0	5
4	0	0	9		2	2	16	0
5	2	41	22	43		0	5	2
6	13	0	0	4	0		5	0
Qj	5	0	0	0	0	0	Н=58
Bj	1	0	9	4	2	0

Новая нижняя граница Z(T:

)= 58, что совпадает с ранее найденным значением.

По значениям A_i и B_j рассчитываются штрафы (табл.13).

Таблица 13

( i, j)	1,6	2,4	3,6	4,2	5,6	6,2	6,3	6,5
Фij	1	5	5	0	2	0	9	7

Максимальный штраф у звена (6,3) Ф₆₃ = 9 поэтому выбираем звено (6,3). Если вспомнить табл.6, то в ней звено (6,3) «вплотную» приближалось к (1,4).

Все дальнейшие действия полностью повторяют изложенный ранее метод расчета. Дерево окончательного решения приведено на рис. 3.

Рис. 3

Оптимальным маршрутом перевозки (см. рис.3) является последовательность звеньев: (1,4); (4,3); (3,5); (5,6); (6,2); (2,1). Стоимость перевозки единицы груза по нему составляет 63. Это значение меньше нижних границ всех остальных ветвлений дерева решений.

Теперь можно приступить ко второй части задания.

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

Для решения этой задачи данной методички недостаточно. Необходимо обратиться к [2, п.5.3].

Определим количество груза первого и второго типов, дающее максимальную стоимость (прибыль). Обозначим вес груза первого типа – x₁ второго – x₂ .

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

x₁+ x₂

_.

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

или

.

Для примера положим, что Q = 150,

, . В численной форме условия–ограничения запишутся:

(1)

где x₁

0 ; x₂

0 .

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

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

f₁(x)=2x₁+x₂

max . (2)