Xreferat.com » Рефераты по математике » Лабораторные работы по Основам теории систем

Лабораторные работы по Основам теории систем

задачи о многомерном ранце (вручную).

Задача о многомерном ранце имеет следующую математическую модель:

, (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 миль, поэтому . Таким образом : .

– В этом случае

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: