Аудит / Институциональная экономика / Информационные технологии в экономике / История экономики / Логистика / Макроэкономика / Международная экономика / Микроэкономика / Мировая экономика / Операционный анализ / Оптимизация / Страхование / Управленческий учет / Экономика / Экономика и управление народным хозяйством (по отраслям) / Экономическая теория / Экономический анализ Главная
Экономика
Оптимизация
| Харчистов Б.Ф.. Методы оптимизации, 2004 | |
МЕТОДЫ ОТСЕЧЕНИЙ |
|
|
Методы отсечений относятся к численным методам решения дискретных задач оптимизации (методам дискретного про-граммирования). Они предназначены для решения целочисленных задач линейного программирования (ЛП). Идея методов отсечения состоит в следующем. Первоначально решается обычная ("непрерывная") задача ЛП, полученная из исходной задачи отбрасыванием требования целочисленности. Если полученное решение является целочисленным, то оно будет также решением исходной задачи. Если нет, то к ограничениям исходной задачи добавляется новое линейное ограничение, обладающее двумя свойствами: полученное нецелочисленное решение ему не удовлетворяет; все целочисленные точки допустимого множества исходной задачи ему удовлетворяют. Такое ограничение называется правильным отсечением. Затем решается расширенная непрерывная задача ЛП, т.е. непрерывная задача с добавленным ограничением. Если полученное решение не является целочисленным, добавляется новое правильное отсечение и т. д. Процесс повторяется до тех пор, пока решение очередной расширенной непрерывной задачи ЛП не окажется целочисленным. Таким образом, решение целочисленной задачи ЛП сводится к решению некоторой последовательности обычных задач ЛП. Геометрически добавление каждого такого линейного ограничения означает проведение гиперплоскости, отсекающей от многогранника допустимых решений очередной непрерывной задачи ЛП оптимальную точку с нецелочисленными координатами, но не затрагивающей ни одной из целочисленных точек этого многогранника. Поэтому методы, опирающиеся на эту идею, получили название методов отсечений. Обозначим через Lk и х(k), k=0,1,..., соответственно k-ю расширенную непрерывную задачу ЛП и ее решение. Отметим, что L0 представляет собой исходную задачу без учета требова- ний целочисленности. Задача Lk+1 получается в результате добавления к ограничениям задачи Lk (k+1)-ro правильного отсечения. Алгоритм решения целочисленной задачи ЛП методом отсечений заключается в следующем. Решается задача ЛП L0. Если задача L0 не имеет решения, то исходная задача не имеет целочисленного решения и вычисления завершаются. Находится решение х(0) . Если решение х(0) является целочисленным, то полагается х* = х(0), f *= f (х(0)) и вычисления завершаются. Если решение х(0) не является целочисленным, то полагается k = 1 и осуществляется переход к п. 3. Определяется k-е правильное отсечение, составляется задача Lk. Решается задача ЛП Lk. Если задача Lk не имеет решения, то исходная задача не имеет целочисленного решения и вычисления завершаются. Находится решение х(k). Если решение х(k) является целочисленным, то полагается х* = х(k), f * = f (х(k)) и вычисления завершаются. Если решение х(k) не является целочисленным, то полагается k = k +1 и осуществляется переход к п. 3. Конкретные способы построения правильных отсечений приводят к конкретным вычислительным алгоритмам. На практическом занятии рассматривается первый (дробный) алгоритм Гомори, предназначенный для решения полностью целочисленных задач ЛП. Рассмотрим полностью целочисленную задачу ЛП: n f (х) = Z Cj^j ^ max , j=1 I aiJ xJ- < bt, i = 1, m, j =1 xj >o, j = in, xj - целые, j = 1, n. Отметим, что для применения первого алгоритма Гомори все коэффициенты и правые части ограничений исходной задачи должны быть приведены к целочисленному виду. Первоначально решается задача L0. Пусть решение x(0) этой задачи не является целочисленным. Согласно общему алгоритму, следует определить дополнительное ограничение (1-е правильное отсечение). Пусть последняя симплекс-таблица задачи L0 имеет следующий вид: Базис Своб. член / x1 / xm x1 xn / xi Ъ1 1 0 an a1n / xm bm 0 1 am1 amn f ъ 0 0 0 С 1 cn Здесь через x', i = 1, m, обозначены базисные переменные, а через xj , j = 1, n, - свободные переменные. Такая система обозначений выбрана из соображений удобства. Строки симплекс-таблицы, которым соответствуют нецелые значения базисных переменных, т. е. нецелые bi , называют производящими. Каждая производящая строка задает правильное отсечение, которое определяется следующим образом: i-я производящая строка записывается в виде (1+о) xi+I (a ]+a i)x; = b ]+[ъ,}, j=1 где [а] и {a} - соответственно целая и дробная части действи-тельного числа а, a = [a] + {a}. Эта производящая строка задает правильное отсечение следующего вида: n -X{aj}х' + u =-{ь, ь j=1 где u1 - неотрицательная дополнительная переменная, которая (по определению) должна принимать целые значения. Выбор производящей строки для построения правильного отсечения осуществляется с помощью эмпирических правил. Первое из них предписывает выбирать производящую строку, которой соответствует max{b}, i второе - строку, которой соответствует max i / _ i n _ \ dt = {bi} X {aij} i i j =1 Если с помощью указанных правил не удается выбрать производящую строку для построения правильного отсечения, производящая строка выбирается произвольно. В результате добавления к ограничениям задачи L0 дополнительного ограничения (1-го правильного отсечения) получаем задачу L1, т. е. L0, n L1 ж Z{aij }xy + u1 =-{bi } j=1 u1 > 0. Наиболее удобным методом решения задачи L1 в указанной постановке является двойственный симплекс-метод. При этом дополнительная переменная u1 вводится в базис, а дополнительное ограничение добавляется к итоговой симплекс-таблице задачи L0. Пример. Решить методом отсечений следующую цело- численную задачу ЛП: f (x) = 7 x1 + 9x2 ^ max . x1 + 3x2 < 6 , 7 x1 + x 2 < 35 , x1 > 0 , x2 > 0 , x1,x2 - целые. Решение. Нулевой этап Записываем задачу L0 (исходная задача без учета требования целочисленности): f (x) = 7 x1 + 9x2 ^ max , - x1 + 3 x2 < 6, 7 x1 + x 2 < 35 , x1 > 0 , x2 > 0 . Решаем задачу L0 симплекс-методом. Для этого преобразуем задачу к канонической форме, вводя дополнительные переменные x3 и x4: f (x) = 7 x1 + 9x2 ^ max , - x1 + 3x2 + х3 = 6 , 7x1 + x2 + х4 = 35 , xj > 0, j = 14. В качестве базисных выберем переменные x3 и x4. Таким образом, начальный базис Б0 = [x3, x4} . В результате приходим к табл. 10.1. Из табл. 10.1 следует, что начальное допустимое базисное решение ДБР0 = (x3=6, x4=35). ДБР 0 не является оптимальным, поскольку в строке целевой функции есть отрицательные коэффициенты fx^ = -7, f = -9. Задача разрешима, поскольку в столбцах x1 и x2 есть положительные коэффициенты. Находим Б1:? 6/3=2 35/1=35 i Базис Своб. член x1 x2 x3 x4 6 -1 3 1 0 x4 35 7 1 0 1 f 0 -7 -9 0 0 fx2 < 0 fx2 < Д ^ x2 вводим в базис, min {6/3 = 2, 35/1 = 35}= 2 ^ x3 ' выводим из базиса. Таким образом, Б1 = {x2, x4}. В результате приходим к табл. 10.2. Таблица 10.2 i 9 2 33 Х 3 22 Базис Своб. член x1 x2 x3 x4 x2 2 1 3 1 1 3 0 x4 33 22 3 0 1 3 1 f 18 -10 0 3 0 Из табл. 10.2 следует, что ДБР1 = (х2 = 2, х4 = 33). ДБР1 не является оптимальным (fx =-10 < 0), задача разрешима (в столбце x1 есть положительный коэффициент). Находим Б2 : fx < 0 ^ x1 вводим в базис, x4 выводим из базиса. Таким образом, Б2 = {x1, x2}. В результате приходим к табл. 10.3.? Базис Своб. член Х1 Х2 Х3 Х4 х1 4i 2 1 0 1 22 3 22 Х2 31 2 0 1 7 22 1 22 f 63 0 0 2Ч 11 Д 11 2 41,31 22 Из табл. 10.3 следует, что ДБР2 = х, = 4 Ч, х2 = 3 - ДБР2 является оптимальным решением. Таким образом, задача L0 имеет решение х(0) = при этом f (х(0)) = 63. Поскольку х(0) не является целочисленным, то выполняем 1-й этап. Первый этап Определяем первое правильное отсечение. Производящими являются 1-я и 2-я строки итоговой симплекс-таблицы задачи L0. Поскольку (Ь1) = 2 и {b2} = 2, то первое правило не позволяет выбрать производящую строку для построения отсечения. Используем второе правило выбора производящей строки. Вычисляем d1 и d2 : d=2 3 Ч+Ч 22 71 Ч+Ч 22 22 11 8 24 , d2 = 2 v / Поскольку di < d2, то для построения 1-го правильного отсечения выбираем 2-ю строку итоговой симплекс-таблицы задачи L0. 2-й строке соответствует равенство 7 1 1 0 + - 0+ x4 = 3 + x3 + 22 22 2 (1 + 0) х2 + Следовательно, 1-е правильное отсечение имеет вид 1 1 7 Хл X Л I ^/l = " 22 3 22 4 1 2 Составляем задачу L1: L0 7 22 Li 1 3 x4 + u1 = 22 u1 > 0. Решаем задачу L1 двойственным симплекс-методом. В качестве базисных выберем переменные x1, x2, u1. Таким образом, Б0 = {x1, x2, u1}. В результате приходим к табл. 10.4. Таблица 10.4 I Базис Своб. член Х1 Х2 Х3 x4 u1 Х1 41 2 1 0 1 22 3 22 0 Х2 з1 2 0 1 7 22 1 22 0 u1 1 2 0 0 7 22 1 22 1 f 63 0 0 2Ч 11 1-1 11 0 30 Из табл. 10.4 следует, что начальное базисное решение БР0 '11 1 ^ x1 = 4Ч,х2 = 3 - u1 = . БР0 не является допустимым, по- 1 2 2 2 1 2 \ / скольку в столбце свободных членов есть отрицательный коэф- фициент bu = -1/2 < 0 . Задача разрешима, поскольку в строке u1 есть отрицательные коэффициенты. Находим Б1: bu < 0 ^ u1 выводим из базиса, min ( 28 -7 = 8, 15 1 \ Ч Ч = 30 ,11/ - 22 11 22 / 8 ^ Х3 вводим в базис. Таким образом, Б1 = {x1 , Х2, Х3}. В^В результате приходим к табл. 10.5. Таблица 10.5 Xi = 4 , X2 = 3, 1 7 2 Базис Своб. член Х1 Х2 Х3 Х4 u1 Х1 44 7 1 0 0 1 7 1 7 Х2 3 0 1 0 0 1 Х3 14 7 0 0 1 1 7 - 31 7 f 59 0 0 0 1 8 Из табл. 10.5 следует, что БР1 И' х3 = 1 - 3 7 . БР1 является допустимым и, следовательно, оптималь- ным решением. 4-, 3 V 7 У Таким образом, задача L1 имеет решение x1J = при этом f (x(1)) = 59. Поскольку x(1) не является целочисленным, то выполняем 2-й этап. Второй этап Определяем второе правильное отсечение. Производящими являются 1-я и 3-я строки итоговой симплекс-таблицы задачи L1. - 4 - 4 Поскольку (b1) = - и {b3} = Ч' то первое правило не позволяет выбрать производящую строку для построения отсечения. Используем второе правило выбора производящей строки. Вычисляем d1 и d2: / V l'd 2 = 7/ di = 7/ 4. 7' 1б - + - V7 7, о ЧЧ Поскольку d1 = d2, то второе правило не позволяет выбрать производящую строку для построения отсечения. Выберем произвольно 1-ю строку итоговой симплекс-таблицы задачи L1. Этой строке соответствует равенство 1 б 4 0+ 1 + ж u1 = 4 + - Х4 + 7 7 7 (1 + 0) x1 + Следовательно, 2-е правильное отсечение имеет вид 1 б 4 Х л Ui + u - " 7 4 7 1 2 7 Составляем задачу L2: L1, 1 б L2 4 x - л Ui + UГ) - ж 7 4 7 1 2 7 u2 > 0. Решаем задачу L2 двойственным симплекс-методом. В качестве базисных выберем переменные x1, x2, x3, Ы2. Таким образом, Б0 = {x1 ' x2 ' x3 ' U 2 }. В результате приходим к табл. 10.б. Из табл. 10.б следует, что начальное базисное решение 4 7' 4 4 БР0 x1 - 4 ' x 2 Х 3' x3 - 1 ' Ы2 - 3 7 7 . БР0 не является допус- тимым, поскольку bu = -4/7 < 0 ; задача разрешима, поскольку в строке Ы2 есть отрицательные коэффициенты. Находим Б1:? Базис Своб. член x1 x2 x3 x4 u1 u2 x1 4 7 1 0 0 1 7 1 7 0 x 2 3 0 1 0 0 1 0 *3 7 0 0 1 1 7 - 31 7 0 U2 4 7 0 0 0 1 7 6 7 1 f 59 0 0 0 1 8 0 7 91 3 bu < 0 ^ u2 выводим из базиса, = 91 3 = 7, min = 7 ^ x4 вводим в базис. / Таким образом, Б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() = (4, 3) , f = f (x( )) = 55 и вычисления завершаются.? Базис Своб. член x1 x2 x3 x4 u1 U2 x1 4 1 0 0 0 -1 1 x2 3 0 1 0 0 1 0 x3 1 0 0 1 0 -4 1 x4 4 0 0 0 1 6 -7 f 55 0 0 0 0 2 7 Ответ: х* = (4, 3), f * = 55. |
|
| << Предыдушая | Следующая >> |
| = К содержанию = | |
Похожие документы: "МЕТОДЫ ОТСЕЧЕНИЙ" |
|
|