Книги по разным темам Pages:     | 1 |   ...   | 6 | 7 | 8 | 9 |

Базис x1 x2 xxчлен 6 -310 6/3= x35 7 1 0 1 35/1=xf 0 -7 -fx < 0, fx < fx x2 вводим в базис, 2 2 min{6 3 = 2, 35 1 = 35}= 2 x3 `выводим из базиса.

Таким образом, Б1 = {x2, x4}. В результате приходим к табл. 10.2.

Таблица 10. Своб.

Базис x1 x2 x3 xчлен 1 2 1 x3 22 1 33 3 33 0 x- = 3 3 22 f 18 -Из табл. 10.2 следует, что ДБР1 = (х2 = 2, х4 = 33). ДБРне является оптимальным ( fx = -10 < 0), задача разрешима (в столбце x1 есть положительный коэффициент). Находим Б2 :

fx < 0 x1 вводим в базис, x4 выводим из базиса.

Таким образом, Б2 = {x1, x2}. В результате приходим к табл. 10.3.

Таблица 10.Своб.

Базис x1 x2 xxчлен 1 1 x4 2 22 1 x2 2 22 6 f 63 0 2 11 1, Из табл. 10.3 следует, что ДБР2 = x1 = 4, x2 = 2 ДБР2 является оптимальным решением.

1 Таким образом, задача L0 имеет решение х(0) =, 3, 2 при этом f (х(0)) = 63.

Поскольку x(0) не является целочисленным, то выполняем 1-й этап.

Первый этап Определяем первое правильное отсечение. Производящими являются 1-я и 2-я строки итоговой симплекс-таблицы задачи L0.

1 Поскольку {b1} = и {b2} =, то первое правило не по2 зволяет выбрать производящую строку для построения отсечения. Используем второе правило выбора производящей строки.

Вычисляем d1 и d2 :

1 21 3 11 1 7 1 d1 = + =, d2 = + =.

2 22 22 24 2 22 22 Поскольку d1 < d2, то для построения 1-го правильного отсечения выбираем 2-ю строку итоговой симплекс-таблицы задачи L0. 2-й строке соответствует равенство 7 1 0 x 0 x = 3 +.

(1 + 0)x2 + + + + 3 22 22 Следовательно, 1-е правильное отсечение имеет вид 7 1 - x3 - x4 + u1 = -.

22 22 Составляем задачу L1:

L0, 7 1 L1 x3 - x4 + u1 = -, 22 22 u1 0.

Решаем задачу L1 двойственным симплекс-методом.

В качестве базисных выберем переменные x1, x2, u1. Таким образом, Б0 = {x1, x2, u1}. В результате приходим к табл. 10.4.

Таблица 10. Своб.

Базис x1 x2 x3 x4 uчлен 1 1 10 x4 2 22 1 017 x2 22 1 7 00 u1 - - 2 22 6 f 63 0 0 2 11 Из табл. 10.4 следует, что начальное базисное решение БР1 1. БР0 не является допустимым, по= x1 = 4, x2 = 3, u1 = - 2 2 скольку в столбце свободных членов есть отрицательный коэффициент bu = -1 2 < 0. Задача разрешима, поскольку в строке uесть отрицательные коэффициенты. Находим Б1:

bu < 0 u1 выводим из базиса, 28 7 15 min - = 8, - = 30 = 8 x3 вводим в базис.

11 22 11 Таким образом, Б1 = {x1, x2, x3}. В результате приходим к табл. 10.5.

Таблица 10.Своб.

Базис xx1 x3 x4 uчлен 4 x1 4 7 7 x4 x1 -7 7 f 59 Из табл. 10.5 следует, что БР1 = х1 = 4, х2 = 3, х3 = 1. БР1 является допустимым и, следовательно, оптималь ным решением.

Таким образом, задача L1 имеет решение x(1) =, 3, при этом f (x(1)) = 59.

Поскольку x(1) не является целочисленным, то выполняем 2-й этап.

Второй этап Определяем второе правильное отсечение. Производящими являются 1-я и 3-я строки итоговой симплекс-таблицы задачи L1.

4 Поскольку {b1} = и {b3} =, то первое правило не по7 зволяет выбрать производящую строку для построения отсечения. Используем второе правило выбора производящей строки.

Вычисляем d1 и d2 :

4 1 6 4 4 1 6 d1 = + =, d2 = + =.

7 7 7 7 7 7 7 Поскольку d1 = d2, то второе правило не позволяет выбрать производящую строку для построения отсечения. Выберем произвольно 1-ю строку итоговой симплекс-таблицы задачи L1.

Этой строке соответствует равенство 1 6 0 x -1 u (1 + 0)x1 + + + + = 4 +.

4 7 7 Следовательно, 2-е правильное отсечение имеет вид 1 6 - x4 - u1 + u2 = -.

7 7 Составляем задачу L2:

L1, 1 6 L2 x4 - u1 + u2 = -, 7 7 u2 0.

Решаем задачу L2 двойственным симплекс-методом.

В качестве базисных выберем переменные x1, x2, x3, u2.

Таким образом, Б0 = {x1, x2, x3, u2}. В результате приходим к табл. 10.6.

Из табл. 10.6 следует, что начальное базисное решение 4 4 БР0 = x1 = 4, x2 = 3, x3 = 1, u2 = -. БР0 не является допус 7 7 тимым, поскольку bu = - 4 7 < 0 ; задача разрешима, поскольку в строке u2 есть отрицательные коэффициенты. Находим Б1:

Таблица 10. Своб.

Базис x1 x2 x3 x4 u1 uчлен 4 1 0 01 x4 7 7 x2 3 0 1 0 0 1 0 0 11 x3 1 -7 7 4 1 0 0 0 u2 - - 7 7 f 59 0 0 0 1 8 bu < 0 u2 выводим из базиса, 1 6 min 1 - = 7, 8 - = 9 = 7 x4 вводим в базис.

7 7 Таким образом, Б1 = {x1, x2, x3, x4}. В результате приходим к табл. 10.7.

Из табл. 10.7 следует, что БР1 = (х1 = 4, х2 = 3, х3 = 1, x4 = 4). БР1 является допустимым и, следовательно, оптимальным решением.

Таким образом, задача L2 имеет решение x(2) = (4, 3), при этом f (х(2) ) = 55.

Поскольку решение x(2) является целочисленным, то точка x(2) = (4, 3) является решением исходной задачи; поэтому по лагаем х = x(2) = (4, 3), f = f (x(2)) = 55 и вычисления завершаются.

Таблица 10.Своб.

Базис x1 x2 x3 x4 u1 uчлен 4 1000 -x3 x1 0010 -xx4 4 00016 -f 55 Ответ: х = (4, 3), f = 55.

Задачи 1. Решить методом отсечений следующую целочисленную задачу ЛП:

f (x) = x1 + 2x2 max, 4x1 + 2x2 13, x1 0, x2 0, x1, x2 - целые.

2. Решить методом отсечений следующую целочисленную задачу ЛП:

f (x) = 2x1 + 3x2 max, 2x1 + 5x2 16, 6x1 + 5x2 30, x1 0, x2 0, x1, x2 - целые.

11. МЕТОД ВЕТВЕЙ И ГРАНИ - Метод ветвей и границ относится к группе комбинаторных методов дискретного программирования и является одним из наиболее распространенных методов этой группы. Центральную идею комбинаторных методов составляет замена полного перебора допустимого множества X частичным перебором. В случае метода ветвей и границ это осуществляется путем последовательного разбиения допустимого множества на подмножества (ветвления) и вычисления оценок (границ), позволяющих отбрасывать подмножества, заведомо не содержащие решения задачи.

При реализации общей схемы метода ветвей и границ для различных задач дискретного программирования необходимо, исходя из специфики этих задач, конкретизировать правила ветвления и вычисления границ.

На практическом занятии рассматривается метод ветвей и границ для задачи целочисленного линейного программирования (ЛП) следующего вида:

n f (x) = c xj max, j j =n aij x bi, i = 1, m, j j =x 0, = 1, n, j j xj - целые, j = 1, n.

Допустимое множество Х данной задачи предполагается ограниченным.

В данном случае на каждом этапе (шаге) решаются непрерывные задачи ЛП: на предварительном (нулевом) этапе - задача L0; на k-м, k = 1, 2,..., этапе - задачи L2k-1 и L2k. Задача L0, как и в методе отсечений, представляет собой исходную задачу без учета требования целочисленности; задача L, = 1,2,..., получается в результате добавления к задаче L0 дополнительных ограничений.

Верхняя граница (оценка) целевой функции f для задачи L, = 0,1,2,..., определяется следующим образом:

f (x( )), где x( ) - решение задачи L.

Если задача L не имеет решения, то полагается -.

В процессе решения строится дерево задач, в котором -я, = 0,1,2,..., вершина соответствует задаче L. Обозначим через I множество вершин, из которых возможно ветвление. Для ветвления на k-м, k =1,2,..., этапе выбирается -я, I, вершина (задача L ), которая имеет максимальную верхнюю оценку.

( Пусть в решении x( ) некоторая компонента xr ), 1 r n, не является целочисленной. Допустимое, т.е. целочисленное, значение xr должно удовлетворять одному из неравенств, представляющих собой необходимые условия целочисленности xr :

( ( либо xr [xr )], либо xr [xr )] +1, где [a] - целая часть действительного числа а.

В результате задача L разветвляется (разбивается) на две не связанные между собой задачи L2k -1 и L2k. Задача L2k -1 представляет собой задачу L с дополнительным ограничением xr [x() ], а задача L2k - задачу L с дополнительным ограничеr ( нием xr [xr )] +1, т.е.

L, L, L2k - x [xr )]; L2k x [xr )] +1.

( ( Для ускорения процесса решения вводится нижняя граница целевой функции f для целочисленного решения, обозначаемая. После решения задачи L значение определяется следующим образом:

-, если задача L не имеет решения либо x( ) = не является целочисленным;

max{ -1, }, если x( ) является целочисленным.

При этом 0 -.

Ветвление на k-м, k = 1,2,.., этапе из i-й, i I, вершины i следует прекратить, если верхняя граница целевой функции для задачи Li не больше известной на данном шаге нижней границы 2k целевой функции для целочисленного решения. Процесс решения завершается, когда отсутствуют вершины, из которых возможно ветвление, т.е. I =. При этом оптимальное зна чение f = 2k, решение x = x( ), где x( ) определятся из условия f (x( ) ) = 2k.

Итак, алгоритм решения целочисленной задачи ЛП методом ветвей и границ заключается в следующем.

1. Решается задача ЛП L0.

Если задача L0 не имеет решения, то исходная задача не имеет целочисленного решения и вычисления завершаются.

2. Находится решение x(0), вычисляется верхняя граница = f (x(0)).

Если решение x(0) является целочисленным, то полагается x = x(0), f = и вычисления завершаются.

Если решение x(0) не является целочисленным, то полагается 0 = -, k=1 и осуществляется переход к п. 3.

3. Выбирается для ветвления -я вершина из I, для которой выполняется условие i = max.

iI 4. Выбирается (произвольно) одна из нецелочисленных ( компонент xr ), осуществляется ветвление по переменной xr, составляются задачи L2k -1 и L2k.

5. Решается задача Lj, j = 2k -1, 2k.

j Если задача Lj не имеет решения, то полагается = -, j j - = и осуществляется (при j=2k) переход к п. 7.

j 6. Находится x( j ), вычисляется = f (x( j)).

Если решение x( j) является целочисленным, то полагается j j -1 j = max{, } и осуществляется (при j = 2k) переход к п. 7.

Если решение x( j) не является целочисленным, то полагаj j -ется = и осуществляется (при j = 2k) переход к п. 7.

7. Просматриваются вершины из I и прекращается ветвление, если выполняется условие i 2k, i I.

8. Проверяется условие окончания вычислений I =.

Если оно выполняется, то полагается f = 2k, = x( ), x где x( ) определяется из условия f (x( ) ) = 2k, и вычисления завершаются.

Если условие не выполняется, то полагается k = k +1 и осуществляется переход к п. 3.

Пример. Решить методом ветвей и границ следующую целочисленную задачу ЛП:

f (x) = 2x1 + 3x2 max, 5x1 + 7x2 35, 4x1 + 9x2 36, x1 0, x2 0, x1, x2 - целые.

Решение.

Предварительный (нулевой) этап Записываем задачу L0 (исходная задача без учета требования целочисленности):

f (x) = 2x1 + 3x2 max, 5x1 + 7x2 35, (1) 4x1 + 9x2 36, (2) x1 0, x2 0.

Этой задаче соответствует нулевая вершина дерева задач (см. ниже рис. 11.6).

Решаем графически задачу L0 (рис. 11.1).

xx(0) 1 f (x) x1 2 3 4 5 6 7 8 (1) (2) Рис. 11.Из рис. 11.1 следует, что задача L0 имеет решение x(0).

Точка x(0) является решением системы уравнений 5 x1 + 7 x2 = 35, 4 x1 + 9 x2 = 36.

Находим x(0) и :

45x1 + 63x2 = 63 - x1 = = 3 ;

28x1 + 63x2 = 252 17 17x1 = 5 63 9 280 40 + 7х2 = 35 7х2 = 35 -18 = х2 = = 2 ;

17 17 17 17 12 x(0) = (3, 2 );

17 12 6 = f (x(0)) = 2 3 + 3 2 = 14.

17 17 Поскольку x(0) не является целочисленным, то полагаем 0 = - и выполняем 1-й этап.

Первый этап Осуществляем ветвление из нулевой вершины.

Выбираем для ветвления нецелочисленную компоненту ( x20) = 2 ; осуществляем ветвление по переменной x2 : x2 2, x2 3 ; составляем задачи L1 и L2 :

L0, L0, L x 2; L2 x 3.

2 Записываем задачу L1:

f (x) = 2x1 + 3x2 max, 5x1 + 7x2 35, (1) 4x1 + 9x2 36, (2) x1 0, 0 x2 2.

Этой задаче соответствует первая вершина дерева задач (см. ниже рис. 11.6).

Решаем графически задачу L1 (рис. 11.2).

Из рис. 11.2 следует, что задача L1 имеет решение x(1).

Точка x(1) является решением системы уравнений 5 x1 + 7 x2 = 35, x2 = 2.

xx(1) f (x) x1 2 3 4 5 6 7 8 (1) (2) Рис. 11.Находим x(1) и :

5х1 + 7 2 = 35 5х1 = 21 х1 = 4 ;

x(1) = (4, 2);

1 1 = f (x(1)) = 2 4 + 3 2 = 14.

5 Поскольку x(1) не является целочисленным, то полагаем 1 = 0 = -.

Записываем задачу L2 :

f (x) = 2x1 + 3x2 max, 5x1 + 7x2 35, (1) 4x1 + 9x2 36, (2) x1 0, x2 3.

Этой задаче соответствует вторая вершина дерева задач (см. ниже рис. 11.6).

Решаем графически задачу L2 (рис. 11.3).

xx(2) 1 f (x) x1 2 3 4 5 6 7 8 (1) (2) Рис. 11.Из рис. 11.3 следует, что задача L2 имеет решение x(2).

Точка x(2) является решением системы уравнений 4 x1 + 9 x2 = 36, x2 = 3.

Находим x(2) и :

4х1 + 9 3 = 36 4х1 = 9 х1 = 2 ;

x(2) = (2, 3);

1 = f (x(2)) = 2 2 + 33 =13.

4 Поскольку x(2) не является целочисленным, то полагаем 2 = 1 = -.

Просматриваем вершины из I = {1, 2}.

Поскольку 1 = 14 > 2 = -, то не прекращаем ветвление из 1-й вершины. Таким образом, I = {1, 2}.

Поскольку =13 > 2 = -, то не прекращаем ветвление из 2-й вершины. Таким образом, I = {1, 2}.

Проверяем условие окончания вычислений.

Поскольку I, то выполняем 2-й этап.

Второй этап Выбираем для ветвления 1-ю вершину, поскольку выполняется условие i 1 = 14 = max.

iI ( Выбираем нецелочисленную компоненту x11) = 4 ; осуществляем ветвление по переменной x1:, x1 5 ; составляx1 ем задачи L3 и L4 :

L1, L1, L x 4; L4 x 5.

1 Записываем задачу L3 :

f (x) = 2x1 + 3x2 max, 5x1 + 7x2 35, (1) 4x1 + 9x2 36, (2) 0 x1 4, 0 x2 2.

Этой задаче соответствует третья вершина дерева задач (см. ниже рис. 11.6).

Решаем графически задачу L3 (рис. 11.4).

Из рис. 11.4 следует, что задача L3 имеет решение x(3) :

x(3) = (4, 2) ;

= f (x(3)) = 2 4 + 3 2 = 14.

Поскольку x(3) является целочисленным, то полагаем 3 = max{2, } = max{-,14} = 14.

xx(3) 1 f (x) x1 2 3 4 5 6 7 8 (1) (2) Рис. 11.Записываем задачу L4 :

f (x) = 2x1 + 3x2 max, 5x1 + 7x2 35, (1) 4x1 + 9x2 36, (2) x1 5, 0 x2 2.

Этой задаче соответствует четвертая вершина дерева задач (см.

ниже рис. 11.6).

Решаем графически задачу L4 (рис. 11.5).

Из рис. 11.5 следует, что задача L4 имеет решение x(4).

Точка x(4) является решением системы уравнений 5 x1 + 7 x2 = 35, x1 = 5.

Находим x(4) и :

5 5 + 7х2 = 35 7х2 = 10 х2 = 1 ;

x(4) = (5, 1 );

x1 f (x) x(4) x1 2 3 4 5 6 7 8 (1) (2) Рис. 11.3 = f (x(4)) = 25 + 31 = 14.

7 Поскольку x(4) не является целочисленным, то полагаем 4 = 3 = 14.

Просматриваем вершины из I = {2, 3, 4}.

Поскольку =13 < 4 =14, то прекращаем ветвление из 2-й вершины. Таким образом, I={3,4}.

Поскольку =14 = 4, то прекращаем ветвление из 3-й вершины. Таким образом, I = {4}.

Pages:     | 1 |   ...   | 6 | 7 | 8 | 9 |    Книги по разным темам