|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Решение методом искусственного базиса
Ограничения – неравенства Ограничения – равенства
-3x1 - 5x2 + 25 -2x1 + 2x2 + 6 x1 + 2x2 – 3 xi
F = - 2x1 + x2 à min ʄ = - 2x1 – 3x2 + x5 + x6 + 5 Свободные х1, х2 Преобразуем систему для решения симплекс – методом
x3 = 25 - (3x1 + 5x2 ) x4 = 6 - ( 2x1 - 2x2 ) ξ1 = 3 - ( x1 + 2x2 - x5) ξ2 = 2 - (x1 + x2 - x6 )
F=0 – ( 2x1 – x2) ʄ = 5 – ( 2x1 + 3x2 – x5 – x6)
На данном этапе все свободные члены равны дробным числам, следовательно данный способ не может быть использован для решения данной задачи.
Вывод: задача линейного программирования решена графическим, алгебраическим методом, симплекс методом. Во всех случаях получены одинаковые решения, что говорит о корректности решения.
Решить ЗЦЛП 3.1Решение ЗЦЛП методом Гомори:
F = x1 + 2x2à max
5x1 + 7x2 ≤ 21 -x1 + 3x2 ≤ 8 x1,x2 ≥ 0 x1, x2 –целые
Приведём к канонической форме
-F = - x1 - 2x2 à min
x1 - 3x2 ≥ - 8
Решим с помощью симплекс – метода
x1 – 3x2 + 8 = x4
x4 = 8 – ( -x1 + 3x2 )
-F = 0 – ( x1 + 2x2 ) àmin
λ = 1/3
λ = 3/22
F опт = 129/22
XT ={ 7/22, 61/22 , 0 , 0 }
β1 = 7/22 – 0 = 7/22 α13 = 3/22 – 0 =3/22 α14 = 15/22 – 0 = 15/22
u1 = -7/22 – ( - 3/22 x3 – 15/22 x4 )
λ = 1/5
Fопт = 29/5
XT ={ 7/15, 8/3 , 0 , 7/15 }
β2 = 8/3 – 2 = 2/3 α2u1 = 1/3 – 0 = 1/3 α23 = 0
u2 = -2/3 – ( - 1/3 u1 – 0 x3 )
λ = -3
Fопт = 27/5
XT ={ 7/5, 2 , 0 , 17/5 }
β1 = 7/5 – 1 = 2/5 α21u2 = 3/5 – 0 = 3/5 α13 = 1/5
u2 = -2/5 – ( - 3/5 u2 – 1/5 x3 )
λ = -5
F опт = 5
XT ={ 1, 2 , 2 , 3} Целочисленное программирование. Метод ветвей и границ
Из предыдущего метода было получено:
F опт = 129/22
XT ={ 7/22, 61/22 , 0 , 0 }
Введём дополнительное ограничение на x2
x2 ≤ [61/22] x2 ≥ [61/22] + 1
x2 ≤ 2 x2 ≥ 3
Задача 1
F = x1 + 2x2 à min
5x1 + 7x2 ≤ 21 -x1 + 3x2 ≤ 8 x2 ≥ 3 x1,x2 ≥ 0
Эта задача решения не имеет
Задача 2
F = x1 + 2x2 à min
-x1 + 3x2 ≤ 8 x2 ≤ 2 x1,x2 ≥ 0
x4 = 8 – ( -x1 + 3x2 ) x5 = 2 – (x2 )
-F = 0 – ( x1 + 2x2 ) à min
λ = 1/5
F опт = 27/5
XT ={ 7/5, 2 , 0 , 17/5 , 0}
Введём дополнительное ограничение на x1
x1 ≤ [ 7/5] x1 ≥ [7/5] + 1 x1 ≤ 1 x1 ≥ 2
Задача 1
F = x1 + 2x2 à min
-x1 + 3x2 ≤ 8 x2 ≤ 2 x1 ≥ 2 x1,x2 ≥ 0
Эта задача решения не имеет.
Задача 2
F = x1 + 2x2 à min
-x1 + 3x2 ≤ 8 x2 ≤ 2 x1 ≤ 1 x1,x2 ≥ 0
x4 = 8 – ( -x1 + 3x2 ) x5 = 2 – (x2 ) x6 = 1 – ( x1 )
λ = 1
F опт = 5 XT ={ 1, 2 , 2 , 3 , 0 , 0}
Дерево ветвления задачи:
F =5 4.2Булевское программирование. Метод Баллаша Задание:
Решение задач с булевыми переменными можно производить методом ветвей и границ, как с обычными целочисленными переменными, для которых заданы граничные условия Суть этого метода сводится к следующему: 1) расположить переменные по возрастанию коэффициентов при них в целевой функции; 2) принять некоторый набор значений X, удовлетворяющий всем ограничениям; 3) значение целевой функции при удовлетворении п. 2 принять в качестве дополнительного фильтрующего ограничения (фильтра); 4) методом перебора X определить значение фильтрующего ограничения и проверить удовлетворение его заданным ограничениям; 5) если при некотором наборе X значение фильтрующего ограничения окажется для целевой функции лучшим, следует от первоначального набора перейти к новому и продолжить процедуру.
Составим математическую модель данной ЗЛП с булевскими переменными 1: 4x1 + 9x2 + 7x3+ 5x4+6x5 ≤ 30 2: 6x1 + 7x2 + 9x3 + 5x4 + 4x5 ≤ 30 3: 3x1+ 8x2 + 9x3 + 6x4 + 6x5 ≤ 30 F = 10x1 + 15x2 + 10x3 + 25x4 + 20x5 à max
Примем значение целевой функции на наборе 00000 за фильтрующее.
Фильтрующее ограничение:
Максимальное значение 70 функция достигает на наборе 01111. С помошью фильтра Баллаша колличество вычислений было сокращено на 39%. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2019-05-07; Просмотров: 158; Нарушение авторского права страницы
0 x3 = -3x1 – 5x2 + 25
- 5x1 - 7x2 ≥ -21
-5x1 – 7x2 + 21 = x3
x3 = 21 – ( 5x1 + 7x2 )
x2
X3
λ = - 22/3
U2
5x1 + 7x2 ≤ 21
x3 = 21 – ( 5x1 + 7x2 )
λ = 1
5x1 + 7x2 ≤ 21
5x1 + 7x2 ≤ 21
x3 = 21 – ( 5x1 + 7x2 )
-F = 0 – ( x1 + 2x2 ) à min
x5
F =129/22
F=27/5
. Однако применение такого метода для данных задач в ряде случаев оказывается нецелесообразным. Существуют специальные методы частичного перебора для решения таких задач, наиболее совершенный из них называется аддитивным алгоритмом Баллаша с фильтром.