Читайте также: |
|
Исходные данные
К заданию №1.
№ | C1 | C2 | B1 | B2 | A11 | A12 | A21 | A22 |
-2 |
К заданию №2.
С = | ∞ | ||||||
∞ | |||||||
∞ | |||||||
∞ | |||||||
∞ | |||||||
∞ |
К заданию №3.
№ | A | B | α | β | γ |
0,25 | 1,5 |
К заданию №4.
№ | A | B | α2 |
0,5 | 3/4 |
К заданию №5.
№ | k | γ |
Задание №1. Графоаналитическое решение ОЗЛП
1. Математическая постановка ОЗЛП:
φ=5x1+x2→max, (0)
2x1-2x2≤4, (1)
2x1+6x2≤4, (2)
x1≥0, (3)
x2≥0, (4)
BD: 2x1-2x2=4, (1’)
CD: 2x1+6x2=4, (2’)
AC: x1=0, (3’)
AB: x2=0, (4’)
2. Записываем уравнение граничных линий допустимого многоугольника (1’) - (4’).
На плоскости (x1, x2) строим граничные линии.
3. Строим линию, пересекающую область φ.
, (5)
, (6)
4. Находим градиент целевой функции:
, (7)
, (8)
Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.
Обозначим границы области многоугольника решений.
Рассмотрим целевую функцию задачи φ=5x1+x2→max. Построим прямую, отвечающую значению функции φ=0: F=5x1+x2=0. Будем двигать эту прямую параллельным образом до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.
Из рисунка видно, что оптимальная точка D* равная , находится на пересечении линий BD и CD и ее координаты определяются путем решения одноименных уравнений (1’) и (2’).
, , (9)
, (10)
Ответ: ;
Задание № 2. Задача о коммивояжере. Метод ветвей и границ
Расстояния между пунктами заданы матрицей:
С = | ∞ | ||||||
∞ | |||||||
∞ | |||||||
∞ | |||||||
∞ | |||||||
∞ |
Решение задачи о коммивояжере методом ветвей и границ начинается с приведения матрицы (вычитания из каждой строки (столбца) матрицы C минимального элемента этой строки (столбца).
Произведем приведение матрицы C по строкам:
hν= min(i) hνi
hν | ||||||||
С’ = | ∞ | |||||||
∞ | ||||||||
∞ | ||||||||
∞ | ||||||||
∞ | ||||||||
∞ |
Произведем приведение матрицы C по столбцам:
gi = min(υ) gνi
С’ = | ∞ | ||||||
∞ | |||||||
∞ | |||||||
∞ | |||||||
∞ | |||||||
∞ | |||||||
gi |
В итоге получаем полностью приведенную (редуцированную) матрицу:
hν | ||||||||
С0 = | ∞ | |||||||
∞ | ||||||||
∞ | ||||||||
∞ | ||||||||
∞ | ||||||||
∞ | ||||||||
gi |
Величины hν и gi называются константами приведения.
Нижняя граница цикла: d0=8 ().
Шаг №1.
Определяем ребро ветвления и разобьем все множество допустимых значений Q0 относительно этого ребра на два непересекающихся подмножества () и (), т.е. , где
В приведенной матрице исследуем все нулевые переходы.
αν | ||||||||
C0 = | ∞ | 0(1) | 0(0) | |||||
0(0) | ∞ | 0(0) | ||||||
∞ | 0(3) | |||||||
0(0) | ∞ | 0(0) | ||||||
0(1) | ∞ | |||||||
0(0) | 0(2) | ∞ | ||||||
βi |
Наибольшая сумма констант приведения равна
υ34= α3 + β4 =2+1=3, следовательно,
множество разбивается на два подмножества и .
Оценка длины цикла: .
В результате получим другую сокращенную матрицу (5x5), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
hν | |||||||
∞ | |||||||
∞ | |||||||
C1= | ∞ | ||||||
∞ | |||||||
∞ | |||||||
gi |
d1=0
Шаг №2.
Определяем ребро ветвления и разобьем все множество допустимых значений Q1 относительно этого ребра на два непересекающихся подмножества .
В приведенной матрице исследуем все нулевые переходы.
αν | |||||||
∞ | 0(1) | 0(0) | |||||
0(0) | ∞ | 0(0) | |||||
C1= | 0(0) | ∞ | 0(0) | ||||
0(2) | ∞ | ||||||
0(0) | 0(2) | ∞ | |||||
βi |
Наибольшая сумма констант приведения равна
υ53=2+0=2, следовательно,
множество разбивается на два подмножества и .
Оценка длины цикла: .
Оценка на перспективном множестве:
В результате получим другую сокращенную матрицу (4x4), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
hν | ||||||
C2 = | ∞ | |||||
∞ | ||||||
∞ | ||||||
gi |
d2=0
Шаг №3.
Определяем ребро ветвления и разобьем все множество допустимых значений Q2 относительно этого ребра на два непересекающихся подмножества .
В приведенной матрице исследуем все нулевые переходы.
αν | ||||||
C2 = | ∞ | 0(1) | 0(0) | |||
0(5) | ∞ | |||||
0(0) | ∞ | 0(0) | ||||
0(0) | 0(2) | ∞ | ||||
βi |
Наибольшая сумма констант приведения равна
υ21=5+0=5, следовательно,
множество разбивается на два подмножества и .
Оценка длины цикла: .
Оценка на перспективном множестве:
В результате получим другую сокращенную матрицу (3x3), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
hν | |||||
∞ | |||||
C3 = | ∞ | ||||
∞ | |||||
gi |
d3=1
Шаг №4.
Определяем ребро ветвления и разобьем все множество допустимых значений Q3 относительно этого ребра на два непересекающихся подмножества .
В приведенной матрице исследуем все нулевые переходы.
αν | |||||
∞ | 0(2) | ||||
C3 = | ∞ | 0(4) | |||
0(4) | 0(2) | ∞ | |||
βi |
Наибольшая сумма констант приведения равна
υ46=4+0=4, следовательно,
множество разбивается на два подмножества и .
Оценка длины цикла: .
Оценка на перспективном множестве:
В результате получим другую сокращенную матрицу (2x2), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
hν | ||||
C4 = | ∞ | |||
gi |
d4=2
В соответствии с этой матрицей включаем в маршрут и .
Ответ: l* =C34+C46+C62+C21+C15+C53=1+1+3+1+3+2=11.
Дерево решения имеет следующий вид:
Дата добавления: 2015-11-30; просмотров: 50 | Нарушение авторских прав