Лабораторные работы по Основам теории систем
Задача о многомерном ранце имеет следующую математическую модель:
, (3)
где критерием является функция
,
(4)
От задачи об одномерном ранце она отличается наличием нескольких ограничений. Таким образом, математическая модель:
Пусть
– j-тый город,
откуда соответственно
.
При этом, если
в j-тый город
будет разгружаться
алкогольная
продукция, то
,
иначе
.
;
Целевой функцией или критерием будет являться максимальная благодарность сограждан:
.
Решим
задачу оценки
критерия для
каждого ограничения
в отдельности.
Пусть множество
относится
к первому
ограничению,
–
ко второму, а
–
к третьему.
1) Анализ
множества
.
(3);
(2);
(4);
(1);
(5).
Определяем начальный план:
,
;
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
меньше 500 миль,
поэтому
будет дробным:
,
=>
.
Таким образом,
начальный
опорный план:
.
;
2) Анализ
множества
.
(1);
(2);
(5);
(3);
(4).
Определяем начальный план:
,
;
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
также равно
300 миль, поэтому
будет целым:
,
=>
.
Таким образом,
опорный план:
.
;
3) Анализ
множества
.
(5);
(2);
(3);
(4);
(1).
Определяем начальный план:
,
;
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
меньше 550 миль,
поэтому
будет дробным:
,
=>
.
Таким образом,
опорный план:
.
;
4) Вычисление верхней и нижней границ.
Вычисляем верхнюю границу:
;
– третье
ограничение
более жесткое,
далее будем
исследовать
опорный план
.
Определяем опорные планы для третьего ограничения:
a)
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
равно 50 миль,
поэтому
.
Таким образом
:
.
б)
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
равно 100 миль,
поэтому
.
Таким образом
:
.
в)
В этом случае
.
Вычисляем нижнюю границу:
;
;
;
.
5) Ветвление множества D.
;
- здесь
.
-
здесь
.
6) Анализ множества D1.
a)
Определяем
начальный план
для
:
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
меньше 500 миль,
поэтому
будет дробным:
,
=>
.
Таким образом,
новый опорный
план:
.
;
б)
Определяем
начальный план
для
:
,
;
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
меньше 700 миль,
поэтому
будет дробным:
,
=>
.
Таким образом,
новый опорный
план:
.
;
в)
Определяем
начальный план
для
:
,
;
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
меньше 100
миль, поэтому
будет дробным:
,
=>
.
Таким образом,
новый опорный
план:
.
;
г) Вычисление верхней и нижней границ.
Вычисляем верхнюю границу:
;
– первое
ограничение
более жесткое.
Определяем опорные планы для первого ограничения:
–
В этом случае
.
–
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
равно 450 миль,
поэтому
.
Таким образом
:
.
–
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
равно 100
миль, поэтому
.
Таким образом
:
.
Вычисляем нижнюю границу:
Т.к.
,
то
;
;
.
7) Анализ множества D2.
Поскольку
,
то:
.
=>
;
a)
Определяем
начальный план
для
:
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
меньше 500 миль,
поэтому
будет дробным:
,
=>
.
Таким образом,
новый опорный
план:
.
;
б)
Определяем
начальный план
для
:
,
;
,
;
,
;
Таким образом,
новый опорный
план:
.
;
в)
Определяем
начальный план
для
:
,
;
В последнем
случае оставшееся
после других
городов расстояние
меньше 400
миль, поэтому
будет дробным:
,
=>
.
Таким образом,
новый опорный
план:
.
;
г) Вычисление верхней и нижней границ.
Вычисляем верхнюю границу:
;
– третье
ограничение
более жесткое.
Определяем опорные планы для третьего ограничения:
–
,
;
В
последнем
случае оставшееся
после других
городов расстояние
равно 50 миль,
поэтому
.
Таким образом:
.
–
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
равно 50 миль,
поэтому
.
Таким образом
:
.
– В этом случае
.
Вычисляем нижнюю границу:
Т.к.
,
то
;
;
.
8) Отсев неперспективного подмножества.
.
Так как
и
больше Rec,
то оба подмножества
перспективные,
но поскольку
,
то далее мы
будем исследовать
,
как более
перспективное.
;
- здесь
.
-
здесь
.
9) Анализ множества D3.
Поскольку
,
то:


a)
Определяем
начальный план
для
:
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
меньше 600 миль,
поэтому
будет дробным:
,
=>
.
Таким образом,
новый опорный
план:
.
;
б)
Определяем
начальный план
для
:
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
меньше 700 миль,
поэтому
будет дробным:
,
=>
.
Таким образом,
новый опорный
план:
.
;
в)
Определяем
начальный план
для
:
,
;
В последнем
случае оставшееся
после других
городов расстояние
меньше 350
миль, поэтому
будет дробным:
,
=>
.
Таким образом,
новый опорный
план:
.
;
г) Вычисление верхней и нижней границ.
Вычисляем верхнюю границу:
;
– третье
ограничение
более жесткое.
Определяем опорные планы для третьего ограничения:
–
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
равно 100 миль,
поэтому
.
Таким образом
:
.
–
,
;
,
;
В последнем
случае оставшееся
после других
городов расстояние
равно 300
миль, поэтому
.
Таким образом
:
.
–
В этом случае