<< Пред. стр. 4 (из 13) След. >>
Список литературы по разделу
Рис. 1.7
Вычислительной схеме модифицированного симплекс-метода соответствует система таблиц T1 и Т2(q). Таблица T1 (рис. 1.7) является общей для всех итераций и служит для получения строки оценок текущего базисного плана a0(?(q)). Если обозначить через ?i(?(q)) (i?0:m) строки матрицы , то из (1.26), в частности, следует, что
(1.42)
Как видно из рис. 1.7, T1 состоит из трех блоков:
> в центре содержится матрица ;
> в левом блоке таблицы на каждой итерации дописываются нулевые строки матрицы для текущего базиса;
> нижний блок, расположенный под матрицей А, на каждой итерации дополняется строкой оценок текущего плана, вычисленной по формуле (1.42).
Симплекс-таблица T2(q) , изображенная на рис. 1.8, соответствует допустимому базису КЗЛП ?(q), получаемому на q-й итерации. Столбец N(?(q)) содержит номера базисных столбцов (в последовательности вхождения в базис); столбец b(?(q)) - компонента вектора ограничений относительно текущего базиса ?(q); - матрица, обратная по отношению к матрице расширенных столбцов текущего базиса ?(q) ; графа содержит расширенный вектор условий, вводимый в базис на текущей итерации, а следующая графа - координаты этого же столбца в текущем базисе (?(q)).
Рис. 1.8
По аналогии с п. 1.4.1 опишем формальную схему алгоритма модифицированного симплекс-метода.
0-этап. Нахождение допустимого базисного плана.
1. Для поиска допустимого базиса может быть применен метод минимизации невязок, рассмотренный в п. 1.4.5. При этом для решения вспомогательной задачи используется процедура модифицированного симплекс-метода. В результате 0-этапа мы получаем допустимый базисный план x(?(q)) и соответствующие ему матрицу и вектор .
2. Заполняем центральную часть таблицы T1 , содержащую матрицу .
3. Содержимое матрицы и вектора , полученных на этапе поиска допустимого базисного плана, переносится в таблицу T2(1) . .
4. Полагаем номер текущей итерации q равным 1 и переходим к I-этапу.
I-этап. Стандартная итерация алгоритма - выполняется для очередного базисного плана x(?(q)).
1°. Проверка оптимальности текущего базисного плана. Содержимое нулевой строки таблицы T2(q) - ?0(?(q)) переписывается в соответствующую графу таблицы T1 . По формуле (1.42) рассчитываем и заполняем строку a0(?(q)). Осуществляем просмотр строки оценок a0(?(q)). Возможны два варианта:
1?. a0(?(q)) ? 0 - план, соответствующий текущему базису задачи, оптимален. Вычислительный процесс закончен. Согласно формулам (1.33) и (1.32) выписываются оптимальный план задачи х* = x(?(q)) и оптимальное значение целевой функции f(х*) = f(x(?(q))).
1". В строке оценок a0(?(q)) существует по меньшей мере один элемент a0,j(?(q)) < 0, т. е. имеющий отрицательную оценку. Следовательно, план x0(?(q)) - неоптимален. Выбирается номер l, соответствующий элементу, имеющему минимальную (максимальную по абсолютной величине) отрицательную оценку:
l-й столбец матрицы становится ведущим и должен быть введен в очередной базис. Переходим к пункту 2° алгоритма.
2°. Определение столбца, выводимого из базиса. Переписываем ведущий столбец из таблицы T1 в текущую таблицу T2(q). По формуле = заполняем соответствующий столбец в таблице T2(q). Возможны два варианта:
2'. Для всех i?1:m ai,l(?(q)) ? 0. Делается вывод о неограниченности целевой функции и завершается вычислительный процесс.
2". Существует по крайней мере один индекс i?1:m, для которого ai,l(?(q)) > 0. Согласно правилу (1.27) определяются место r и номер Nr(?(q)) для столбца, выводимого из базиса. Переходим к пункту 3° алгоритма.
3°. Пересчет относительно нового базиса элементов столбца b и матрицы . Переход к новому базису ?(q+1), который получается введением в базис ?(q) столбца аl и выводом из него столбца аr, осуществляется по формулам, аналогичным формулам (1.28)-(1.31). Они имеют вид:
(1.43)
(1.44)
(1.45)
i?1:m, i ? r, j?1:m. (1.46)
Полагаем номер текущей итерации q :=q+1 и переходим к первому пункту алгоритма.
В завершение подчеркнем, что в силу приведенных выше преимуществ именно модифицированный симплекс-метод реально применяется в программном обеспечении, предназначенном для решения канонических задач линейного программирования.
1.5.2. Пример решения ЗЛП модифицированным симплекс-методом. Приведем решение рассмотренной ранее задачи (1.34)-(1.35), основанное на использовании процедуры модифицированного симплекс-метода. По аналогии с п. 1.4.3 оно начинается с выбора очевидного исходного базиса, образуемого столбцами {5, 2, 3}. Для него уже были вычислены и поэтому заполнение начальных таблиц T1 и T2(1) не представляет труда.
На первой итерации мы переписываем нулевую строку
?0(?(q)) = (-1, -10, -10, 2)
из T2(1) в T1 и, умножив ее на матрицу , получаем строку оценок
Так как a0(?(1)) содержит отрицательные элементы, то делаем вывод о неоптимальности плана, соответствующего базису (?(1)), и, выбрав наименьшую отрицательную оценку (-88), получаем номер столбца, вводимого в базис, l= 4.
Переписываем столбец
из таблицы T1 в T2(1) и пересчитываем его координаты относительно текущего базиса, т. е. умножаем матрицу , расположенную в таблице T2(1) слева, на .
После заполнения таблицы Т2(1) данными по вводимому в но вый базис столбцу можно перейти к определению номера выводимого столбца. Эта процедура осуществляется в полной аналогии с обычным симплекс-методом. Рассмотрев отношения элементов и ai,l(?(1)) для и определив минимальное из них, находим, что r = 2. Следовательно, столбец с номером N2(?(q))=2 должен быть выведен из базиса. Таким образом, получаем очередной допустимый базис задачи с N(?(2)) = {5, 4, 3}. Элемент a2,3(?(1)) является ведущим (обведен кружком). Применив формулы (1.43)-(1.46), переходим к симплекс-таблице, соответствующей второй итерации T2(2), и полагаем индекс текущей итерации q = 2.
Повторяя те же самые действия (их легко проследить по приводимым здесь таблицам T2(2) и T2(3) , на третьей итерации мы получим оптимальный план задачи и оптимальное значение целевой функции, которые извлекаются из второго столбца таблицы T2(3). Легко заметить, что в процессе решения мы "прошли" по той же самой последовательности допустимых базисных планов, которая встречалась в п. 1.4.3.
1 .6. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
1.6.1. Понятие двойственной задачи ЛП. Пусть задана КЗЛП (1.7). Если целевая функция f(x) = cx достигает максимального значения на множестве D, то обоснованным представляется вопрос о том, каким образом можно построить верхнюю оценку для нее. Очевидно, что если через и обозначить некоторый m-мерный вектор, то
сх = сх + и(-Ах + b) = (с - иА)х + bи .
Предположим, что и можно выбрать таким образом, чтобы иА ? с . Тогда при любых x ? 0 справедливо неравенство
cх ? bи. (1.47)
Стремясь получить наилучшую оценку (1.47), мы приходим к формулировке некоторой новой экстремальной задачи, которая в некотором смысле логически сопряжена с задачей (1.7) и называется двойственной. Оговоримся, что приведенные рассуждения не носят строгого характера и предназначены только для того, чтобы подготовить читателя к приводимому ниже формальному определению двойственной задачи линейного программирования.
>Если задана каноническая задача ЛП
(1.48)
то задача ЛП
(1.49)
называется двойственной по отношению к ней. Соответственно, задача (D,f) no отношению к (D*,f*) называется прямой (или исходной) .
1.6.2. Общая схема построения двойственной задачи. Приведенное выше определение задачи, двойственной по отношению к канонической ЗЛП, может быть распространено на случай общей задачи линейного программирования.
> Если задана общая задача ЛП
(1.50)
где D определяется системой уравнений и неравенств:
...
...
x1 ? 0, ..., xj ? 0,
то двойственной по отношению к ней называется общая задача ЛП
(1.51)
где D* определяется системой уравнений и неравенств:
...
...
u1 ? 0, ..., ui ? 0
Правила построения задачи, двойственной по отношению к ОЗЛП, наглядно представлены схемой, показанной на рис. 1.9.
Рис. 1.9
Как следует из приведенной схемы при переходе от прямой задачи ЛП к двойственной:
1. Тип оптимума меняется на противоположный, т. е. максимум на минимум, и наоборот.
2. Вектор коэффициентов целевой функции с и столбец ограничений b меняются местами.
3. Матрица ограничений задачи А транспонируется.
4. Множество индексов переменных, на которые наложено условие неотрицательности в прямой задаче (например, xj ? 0 или иi ? 0), определяют номера ограничений, имеющих форму неравенств в двойственной задаче (аj и ? сj или aix ? bi).
5. Множество номеров ограничений, имеющих форму неравенств в прямой задаче (например, aix ? bi или аj и ? сj), определяют множество индексов переменных, на которые накладывается условие неотрицательности, в двойственной задаче (иi ? 0 или xj ? 0) .
>приведенного определения вытекает важное свойство - симметричность отношения двойственности, т. е. задача, двойственная по отношению к двойственной, совпадает с прямой (исходной) задачей:
Тем самым имеет смысл говорить о паре взаимно двойственных задач.
В матричной форме пара двойственных обидах задач линейного программирования может быть кратко записана как:
(1.52)
и
(1.53)
Рассмотрим процесс построения двойственной задачи на конкретном примере. Пусть задана ОЗЛП (D, f):
f(x)= 5x1 -2x2 +7x3 +4x4 -3x5 ? max,
D={x?R5? 4x1 +x2 -x3 +x4 ? 2,
5x2 +x3 -6x4 +2x5 = 4,
2x1 +3x2 +6x3 +x4 -3x5 ? 5
x2 ? x5 ? 0}
тогда двойственной к ней будет задача (D*,f*):
f*(u)= 2u1 +4u2 +5u3 ? min,
D*={u?R3? 4u1 +5x3 =5,
u1 +5u2 +3u3 ? -2,
-u1 +u2 +6u3 =7
-u1 -6u2 +u3 =4
2u2 -3u3 ? -3
u1 ?0 u3 ? 0}
1.6.3. Теоремы двойственности и их применение. Фундаментальные свойства, которыми обладают двойственные задачи линейного программирования, могут быть сформулированы в виде приводимых ниже утверждений. Их обычно называют теоремами двойственности.
Теорема 1.4. Если х,и - допустимые планы для пары двойственных задач (D, f) и (D*,f*), mo f(x) ? f* (и).
Доказательство.
Достаточно доказать теорему для случая, когда задача (D, /) является канонической. Рассмотрим пару двойственных задач
и
Из того, что вектор и является допустимым планом задачи (D*,f*) , следует, что иА ? с . Умножив левую и правую части данного неравенства на вектор x ? 0, получим равносильную систему неравенств
(иА)х ? сх ? и(Ах) ? сх.
Одновременно для вектора х, являющегося допустимым планом задачи (D, f), справедливо равенство Ах = b . Тем самым доказано, что ub ? сх . ^
Замечание. Теорема 1.4, разумеется, верна и для оптимальных планов взаимно двойственных задач: f(x*) ? f*(u*). где х* и и* - любые оптимальные планы задач (D,f) и (D*,f*) . На самом деле, как будет видно из дальнейшего, справедливо равенство f(x*) = f*(u*)
Теорема 1.5. Если для некоторых допустимых планов х и и взаимно двойственных задач (D,f) и (D*,f*) выполняется равенство то и являются оптимальными планами для этих задач.
Доказательство.
Согласно теореме 1.4, для всех допустимых планов х задачи (D,f) справедливо неравенство . По условию теоремы или, что то же самое, . Следовательно, верно утверждение: для любого x?D , т. е. х является оптимальным планом для задачи (D,f).
Рассуждения, доказывающие оптимальность плана для задачи (D*,f*), проводятся аналогично. ^
Теорема 1.6. Если целевая функция f в задаче (D, f) не ограничена сверху, то двойственная к ней задача (D*,f*) не имеет допустимых планов.
Доказательство.
Если предположить, что у двойственной задачи (D*,f*) существует хотя бы один допустимый план , то, согласно теореме 1.4, для любого допустимого плана х задачи (D,f) справедливо неравенство Последнее означает, что целевая функция f задачи (D, f) ограничена сверху. Поскольку это противоречит условию теоремы, предположение о существовании допустимых планов двойственной задачи (D*,f*) неверно. ^
Следующее утверждение, известное как теорема равновесия, используется при проверке оптимальности планов ЗЛП.
Теорема 1.7. Пусть х* и и* - оптимальные планы канонической задачи (D, f) и двойственной по отношению к ней задачи (D*,f*). Если j-я компонента плана х* строго положительна (х*j > 0), то соответствующее j-е ограничение двойственной задачи выполняется как равенство: al,j u1 +... + am,j u*m = cj ; если же j-й компонент плана х* имеет нулевое значение (x*j = 0), то j-e ограничение двойственной задачи выполняется как неравенство: al,j u1 +... + am,j u*m ? cj .
Доказательство.
Векторы х* и и*, будучи допустимыми планами соответствующих задач, удовлетворяют условиям: Ах* = b, х* ? 0 и и*А - с ? 0. Найдем скалярное произведение
(и* А - с)х* = (и*А)х* - сх* = и* (Ах*) - сх* = u* b - сх*.
Согласно замечанию к теореме 1.2, оптимальные значения целевых функций взаимно двойственных задач совпадают, т. е. u* b = cx* . Последнее означает, что (и*А - с)х* = 0. Однако скалярное произведение двух неотрицательных векторов может быть равно нулю только в том случае, когда все попарные произведения их соответствующих координат равны нулю. Следовательно, если х* > 0 , то и* aj - cj = 0, если же х*j = 0 , то возможно и* аj -cj ? 0 , что и утверждается в теореме. ^
Практическое значение теорем двойственности состоит в том, что они позволяют заменить процесс решения основной задачи на решение двойственной, которое в определенных случаях может оказаться более простым. Например, задача, область допустимых значений которой описывается двумя уравнениями, связывающими шесть переменных (т = 2, п = 6), не может быть решена графическим методом. Однако данный метод может быть применен для решения двойственной к ней задачи, которая имеет только две переменные.
Еще раз вернемся к таблице T2(q)(рис. 1.8), получаемой на финальной итерации процедуры модифицированного симплекс-метода. Более подробно рассмотрим нулевую строку матрицы , для которой было введено обозначение ?0(?(q)). Поэлементно она может быть записана в следующем виде:
Введем вектор Нетрудно проверить, что строка оценок a0(?(q)) может быть представлена следующим образом:
Согласно критерию оптимальности, на последней итерации данная строка неотрицательна, т. е. Следовательно, вектор является допустимым планом двойственной задачи.
В то же время элемент b0(?(q)), содержащий текущее значение целевой функции и равный на последней итерации f(x*) , допускает представление
Согласно теореме 1.5 из равенства вытекает, что вектор служит оптимальным планом двойственной задачи: . Окончательно можно утверждать, что для оптимального базиса
(1.54)
>Таким образом, существенным преимуществом модифицированного симплекс-метода является то, что он позволяет одновременно найти оптимальные планы как прямой, так и двойственной задачи.
Читателю в качестве самостоятельного упражнения предлагается построить задачу, двойственную к (1-34)-(1.35), решение которой было приведено в п. 1.5.2, и убедиться, что вектор и = (-10, 32, 2), полученный в таблице T2(3), является для нее допустимым и оптимальным планом.
1.6.4. Экономическая интерпретация. Традиционная экономическая интерпретация двойственной задачи ЛП базируется на модели простейшей задачи производственного планирования, описанной во введении. Напомним, что в ней каждый (j-й) элемент вектора х рассматривается как план выпуска продукции данного вида в натуральных единицах, cf - цена единицы продукции j-го вида, аj - вектор, определяющий технологию расходования имеющихся т ресурсов на производство единицы продукции j-го вида, b - вектор ограничений на объемы этих ресурсов.
Предположим, что для некоторых значений A, b и с найден оптимальный план х*, максимизирующий суммарный доход Достаточно естественным представляется вопрос: как будет изменяться оптимальный план х* при изменении компонент вектора ограничений b и, в частности, при каких вариациях b оптимальный план х* останется неизменным? Данная задача получила название проблемы устойчивости оптимального плана. Очевидно, что исследование устойчивости х* имеет и непосредственное практическое значение, так как в реальном производстве объемы доступных ресурсов bi могут существенно колебаться после принятия планового решения х*.
Когда вектор ограничений b изменяется на ?b или, как еще говорят, получает приращение ?b, то возникают соответствующие вариации для оптимального плана х*(b+?b) и значения целевой функции f(х*(b+?b)). Допустим, приращение ?b таково, что оно не приводит к изменению оптимального базиса задачи, т. е. х*(b+?b) ? 0. Определим функцию F(b), возвращающую оптимальное значение целевой функции задачи (D(b),f) для различных значений вектора ограничений b
(1.55)
Рассмотрим отношение ее приращения F(b+?b)-F(b) к приращению аргумента ?b. Если для некоторого i устремить ?bi ? 0, то мы получим :
(1.56)
Учитывая, что в соответствии с теоремой 1.5
(1.57)
и подставив (1.57) в (1.56), приходим к выражению
(1.58)
>Из формулы (1.58) вытекает экономическая интерпретация оптимальных переменных двойственной задачи. Каждый элемент может рассматриваться как предельная (мгновенная) оценка вклада i-го ресурса в суммарный доход F при оптимальном решении х*. Грубо говоря, величина равна приросту дохода, возникающему при увеличении ресурса i на единицу при условии оптимального использования ресурсов.
В различных источниках компоненты оптимального плана двойственной задачи также называются двойственными оценками или теневыми ценами, а Л. В. Канторович предлагал такой термин, как объективно обусловленные оценки.
На основе теорем двойственности для пары задач ЛП в общей форме могут быть сформулированы некоторые важные (с точки зрения экономической интерпретации) следствия.
>Если при использовании оптимального плана прямой задачи i-е ограничение выполняется как строгое неравенство, то оптимальное значение соответствующей двойственной переменной равно нулю, т. е. если
<< Пред. стр. 4 (из 13) След. >>
Список литературы по разделу