Види математичних моделей двоїстих задач

На підставі розглянутих несиметричних і симетричних двоїстих завдань можна зробити висновок, що математичні моделі пари двоїстих завдань можуть мати один з таких видів

.Н е с и м м е т р и ч н ы е з а д а ч и

(1) Вихідна задача       Двоїста задача

    Z_min = CX;                     f_max = YA₀;

       AX = A₀;                     YA £ С.

        X ³ 0.

(2) Вихідна задача       Двоїста задача

      Z_max = CX;                     f_min = YA₀;

       AX = A₀;                       YA ³ С.

        X ³ 0.

С и м м е т р и ч н ы е з а д а ч и

(3) Вихідна задача       Двоїста задача

      Z_min = CX;                     f_max = YA₀;

       AX ³ A₀;                       YA £ С.

        X ³ 0.                            Y ³ 0.

 (4) Вихідна задача        Двоїста задача

      Z_max = CX;                     f_min = YA₀;

       AX £ A₀;                       YA ³ С.

        X ³ 0.                            Y ³ 0.

Таким чином, перш ніж записати двоїсту задачу для даної вихідної, систему обмежень вихідної задачі необхідно привести до відповідного виду. Запишемо, наприклад, математичну модель двоїстої завдання для наступного вихідної

Знайти мінімальне значення лінійної функції Z = 2x₁ + x₂ + 5x₃ при обмеженнях

x₁ – x₂ – x₃ £ 4,

x₁ – 5x₂ + x₃ ³ 5,             x_j ³ 0 (j = 1, 2, 3).

2x₁ – x₂ + 3x₃ ³6,

Розглянута задача відноситься до симетричних двоїстим задач на відшукання мінімального значення лінійної функції. Для того щоб було можна записати двоїсту задачу, її модель повинна мати вигляд (3). Перехід здійснюється множенням першого нерівності на -1.

Вихідна задача:

Z_min = 2x₁ + x₂ + 5x₃ при обмеженнях

-x₁ + x₂ + x₃ ³ -4,

x₁ – 5x₂ + x₃ ³ 5,             x_j ³ 0 (j = 1, 2, 3).

2x₁ – x₂ + 3x₃ ³6,

Двоїста задача:

f_min = -4x₁ + 5x₂ + 6x₃ при обмеженнях

-y₁ + y₂ + 2y₃ £ 2,

y₁ – 5y₂ - y₃ £ 1,             y_i ³ 0 (i = 1, 2, 3).

2y₁ + y₂ + 3y₃ £ 5,

Наведемо без доведення наступну теорему.

Теорема 1.1. Якщо при підстановці компонент оптимального плану в систему обмежень вихідної задачі i-тe обмеження звертається в нерівність, то i-та компонента оптимального плану двоїстої задачі дорівнює нулю.

Якщо i-та компонента оптимального плану двоїстої задачі позитивна, то i-те обмеження вихідної завдання задовольняється її оптимальним рішенням як суворе рівність
2. Двоїстий симлекс-метод

2.1. Основные идеи двойственного симплекс-метода.

Безпосередній додаток теорії двоїстості до обчислювальних алгоритмів лінійного програмування дозволило розробити ще один метод вирішення ЗЛП, що отримав назву двоїстого симплекс-методу, або методу послідовного уточнення оцінок. Вперше він був запропонований Лемке в 1954 р.

У процесі викладення ідей, покладених в основу двоїстого симплекс-методу, ще раз скористаємося другою геометричною інтерпретацією ЗЛП. Розглянемо деяку КЗЛП (1.48). На рис. 1.11 зображений конус К позитивних лінійних комбінацій розширених векторів умов аj для випадку m = 2, n = 6, а на рис. 1.12 - (для більшої наочності) - поперечний переріз даного конуса деякою площиною L, що проходить паралельно осі аплікат.

З кожним планом і завдання, двоїстої по відношенню до (1.48), можна взаємно однозначно пов'язати гіперплоскость, що проходить через початок координат і перпендикулярну вектору (-1, і). Допустимі плани двоїстої задачі (1.49) повинні відповідати умовам ІА ≥ с, які можна переписати у вигляді (1, і) А ≥ 0. Останнє означає, що всякий розширений вектор умов аj лежить «нижче» площини, яка визначається вектором (-1, і). Таким чином, будь-якому допустимому плану двоїстої задачі в даному прикладі відповідає деяка площина, розташована вище всіх розширених векторів, а отже, і конуса К. На рис. 1.12, де зображено поперечний переріз, конусу К відповідає багатогранник, а «гіперплощинами двоїстих планів» - пунктирні лінії, які є їхніми слідами.

За аналогією з інтерпретацією рішення прямої задачі процес рішення двоїстої задачі може бути представлений як пошук такої гіперплощини, яка лежить вище конуса К і перетинає пряму, проведену через кінець вектора b паралельно осі аплікат, в самій нижній точці.

 З геометричної ілюстрації видно, що площини, не дотичні з конусом К, свідомо не представляють інтересу, так як для будь-якої з них легко вказати площину, у якій шукана точка перетину лежить нижче. Таким чином, процес пошуку екстремуму зводиться до послідовного перебору площин, касающихся що стосуються «верхніх» граней конуса, або, як ще кажуть , опорних по відношенню до конуса. Для випадку, зображеного на рис. 1.12, такими є гіперплощини π_1,2, π_2,3, π_3,4 и π_4,5. Як можна помітити, кожна з розглянутих гіперплоскостей натягнута на деякий базовий набір розширених векторів а^j, що, власне, і використано для їх позначення (π_1,2 ~ {а¹, а²} и т. д.).

F Надалі систему β={a^j1, a^j2,...,a^jm} з т лінійно-незалежних стовпців матриці умов прямої задачі А будемо називати сполученним базисом, чи двояко допустимим базисом, якщо всякий вектор и Î R^m, задовольняє умовам, задовольняє також умовам иа^j≥c_j(jÎ1:n), тобто, є допустимим планом двоїстої задачі (1.49).

План двоїстої задачі і, відповідний парному базису β={aj1, aj2,...,ajm}, називають опорним планом. Його «опорність» полягає в тому, що в системі обмежень uаj ≥ cj (jÎ1:n), задають область визначення двоїстої задачі D*, т нерівностей з номерами jÎ N(β) звертаються в рівності.

Слід звернути увагу на те, що не всім сполученим базисам відповідають допустимі базисні плани пря­мої задачі. Зокрема, вектор b не може бути розкладений з невід'ємними коефіцієнтами по базисам {а1, а2}, {а3 , а4 } чи {а4, а5}. У зв'язку з цим систему коефіцієнтів розкладання вектора b по парному базису називають псевдопланом. В тей же час базис {а2, а3} є допустимим для прямої задачі, і, більше того, з ілюстрації видно, що він, з одного боку, визначає максимум прямої задачі (найвищу точку перетину прямої, що проходить через кінець b, з конусом К), а з іншого - мінімум двоїстої (нижчу точку перетину цієї прямої з лежачою над К опорною гіперплощиною):

Останній факт є не чим іншим, як геометричною ілюстрацією твердження теореми 1.5.

Описані вище властивості пари двоїстих задач лінійного програмування є ідейною основою двоїстого симплекс-методу, який являє собою ітеративний процес цілеспрямованого перебору сполучених (двоїсто припустимих) базисів і відповідних псевдопланів. У цьому й полягає його принципова відмінність від звичайного симплекс-методу, у якому послідовно розглядаються припустимі базисні плани прямої задачі*. Неважко здогадатися, що при певній структурі задачі шлях, запропонований двоїстим алгоритмом, може виявитися більш коротким.

Критерій оптимальності псевдоплану х у двоїстому симплекс-методі полягає в тому, що х одночасно повинен бути пдопустимим планом прямої задачі, тобто всі його компоненти повинні бути невід’ємні (х_j ≥ 0).

Але, якщо хоча б одна з компонентів псевдоплану є від’ємною, то процес покращення значення цільової функції може бути продовжений. Геометрична ілюстрація даної ситуації наведена на мал. 1.13. Тут на площині ( для m = 2) зображена система стовпців обмежень КЗЛП, з яких {а¹, а²} утворюють поточний базис. Як видно з малюнка, вектор обмежень має від’ємну координату за напрямком, що задається вектором а¹. У той же час очевидні й ті базиси (наприклад, {а², а³}), у яких b буде мати всі додатні координати. Однак це не завжди так. Приклад на мал. 1.14 ілюструє випадок відсутності припустимих планів у прямої задачі: вектор b має від’ємний компонент у поточному базисі {а¹, а²} за напрямком а², а для всіх інших небазисних стовпчиків (а³, а⁴) дана координата є додатньою, тобто b і стовпчики, що є кандидатами на введення в черговий базис, лежать у різних півплощинах, утворених прямою, що проходить через вектор а¹,

і при будь-яких базисах, відмінних від поточного, відповідає координата вектора b однаково залишиться від’ємною.

F Таким чином, у двоїстому симплекс-методі ознакою відсутності припустимих планів в

розв'язуваної КЗЛП є незаперечність яких-небудь r-х компонент у всіх стовпчиках а^j,

представлених у поточному базисі β (ar_,j(β) ≥ 0, j Î1:n) якщо br(β) < 0 l.*

С другой стороны, если b_r(β)<0 и в строке а_r(β) существуют отрицательные Координати, то псевдоплан можно улучшить выводя из базиса столбец, находящийся на r-м месте, и вводя в него некоторый вектор a^l, имеющий отрицательную r-ую координату. При наличии в векторе b(β) нескольких отрицательных компонент номер вектора, выводимого из базиса, обычно опре­деляется строкой, содержащей наименьшую (наибольшую по модулю и отрицательную) компоненту.

Принцип выбора столбца, вводимого в базис, определяется необходимостью обеспечивать то, чтобы очередной базис опре­делял опорную плоскость, ниже которой располагаются все не­базисные векторы. Для этого требуется, чтобы оценки всех не­базисных векторов а_0,j(β) ( j Î N(β)), вычисляемые по формулам

а_0,j(β) = -c_{j +} c(β)а^j(β)

 (см. (1.26)), оставались положительными. Это, в свою очередь, означает, что номер вводимого столбца l должен быть опреде­лен таким образом. Чтобы

После выбора выводимого и вводимого векторов производит­ся обычный пересчет симплекс-таблицы по формулам, анало­гичным формулам (1.28)-(1.31), и процесс итеративно повто­ряется. В результате через конечное число шагов будет найден оптимальный план КЗЛП или установлен факт пустоты множе­ства допустимых планов.

2.2. Алгоритм и табличная реализация двойственно­го симплекс-метода.

Обобщая сказанное в предыдущем пун­кте, приведем в сжатом виде алгоритм двойственного симплекс-метода для решения КЗЛП.

0-этап. Нахождение исходного сопряженного (двой­ственно допустимого базиса). Результатом 0-этапа являют­ся сопряженный базис β⁽¹⁾ и соответствующие ему псевдоплан x(β⁽¹⁾), матрица A(β⁽¹⁾) и вектор b(β⁽¹⁾), которые будут исполь­зованы на первой итерации. Полагаем номер текущей итерации q равным 1 и переходим к I-этапу.

I-этап. Стандартная итерация алгоритма — выполня­ется для очередного сопряженного базиса β^(q).

1°. Проверка оптимальности текущего псевдоплана: осу­ществляется просмотр значений b_i(β^(q)), iÎ1:m. Возможны два варианта:

1΄. Для всех iÎ1:m, b_i(β^(q)) ≥ 0. Тогда текущий псевдоплан x(β^(q)) одновременно является допустимым планом решаемой задачи, т. е. ее оптимальным планом. Вычислительный про­цесс закончен. Элементы оптимального плана х* определяют­ся по формуле

а достигаемое на нем значение целевой функции равно

1". Существует по меньшей мере один номер строки rÎ1:m, для которого b_r(β^(q))<0 . Следовательно, псевдоплан x(β^(q)) — неоптимален. Выбирается строка с номером r, такая, что

Она становится ведущей и определяет номер столбца N_r(β^(q)), который должен быть выведен из базиса. Переходим к пункту 2° алгоритма.                              

2°. Определение столбца, вводимого в базис. Рассматрива­ется ведущая строка а_r(β^(q)). Возможны два варианта:       

2'. Для всех jÎ1: n а_r,j(β^(q)) ≥ 0. Делается вывод об отсут­ствии допустимых планов у решаемой задачи (D = Ø) и за­вершается вычислительный процесс*.

2". В строке а_r(β^(q)) существует по крайней мере один эле­мент а_r,j(β^(q))<0. Согласно правилу (1.62) определяются l — номер столбца, вводимого в очередной базис. Переходим к пун­кту 3° алгоритма.

3°. Пересчет элементов матрицы А и столбца b относи­тельно нового базиса. В соответствии с формулами (1.28)-(1.31) осуществляем расчет элементов матрицы задачи A и век­тора ограничений b относительно нового базиса β^(q+1), который получается в результате вывода из базиса β^(q) столбца а^r и вво­да в него столбца а^l. Полагаем номер текущей итерации q: = q+1 и переходим к первому пункту алгоритма.

По аналогии со стандартным симплекс-методом вычислитель­ную процедуру двойственного симплекс-метода удобно офор­млять в виде таблиц, приведенных на рис. 1.5. Очевидно, что с формальной стороны их структура остается неизменной. Иног­да считается целесообразным добавить к двойственной симп­лекс-таблице строку, содержащую строку со значениями λ_j, которые вычисляются на этапе определения столбца, вводимо­го в базис.

2.3. Особенности применения двойственного симп­лекс-метода.

Алгоритм двойственного симплекс-метода (как и остальные симплекс-алгоритмы) предполагает знание исход­ного сопряженного базиса. Очевидно, что в общем случае его нахождение является достаточно непростой задачей, сводящей на нет потенциальные преимущества двойственного алгоритма. Однако в ряде случаев исходный псевдоплан может быть опре­делен достаточно легко.

Рассмотрим задачу минимизации:

при обмеженнях

где

Приведем задачу (1.66)-(1.68) к канонической форме, введя фиктивные переменные х_n+1, х_n+2, ... , х_n+m:

Задача, двойственная к (1.70)—(1.72), будет иметь вид:

Из (1.74)-(1.75) очевиден допустимый план двойственной задачи

и исходный сопряженный базис, образуемый векторами аⁿ⁺¹, аⁿ⁺², …., а^n+m. При этом начальный псевдоплан равен

Таким образом, при решении задачи вида (1.66)-(1.68) двой­ственный симплекс-метод имеет несомненные преимущества по сравнению с прямым.

Другое важное направление использования двойственного симплекс-метода связано с поиском оптимальных планов в тех задачах, условия которых претерпели некоторые изменения после того, как они уже были решены с помощью стандартной симплекс-процедуры. Типичными Прикладами таких изменений являются:

Ø  изменение компонент вектора ограничений b, что, допу­стим, может быть интерпретировано как корректиров­ка объемов доступных ресурсов в процессе управления экономическим объектом;

Ø  добавление новых ограничений к системе условий задачи, что достаточно часто случается при совершенствова­нии используемой экономико-математической модели.

В первом случае, т. е. при изменении вектора b, достоинства двойственного симплекс-метода очевидны, так как ранее найден­ный оптимальный базис можно использовать в качестве исход­ного сопряженного базиса при продолжении решения. Второй случай более подробно будет рассмотрен в гл. 4 при рассмотре­нии методов решения целочисленных задач.

В заключение отметим, что в настоящем параграфе был рас­смотрен вариант двойственного алгоритма, соответствующий стандартному симплекс-методу. Нетрудно догадаться, что су­ществует и вариант, построенный на базе модифицированного симплекса (схемы, связанной с преобразованием обратных мат­риц), но, поскольку этот вопрос представляет интерес в основ­ном с точки зрения техники организации вычислений, мы на нем останавливаться не будем. При желании с глубоким и детальным описанием данной версии алгоритма можно ознако­миться в [1]. Отметим лишь, что она обладает теми же прин­ципиальными преимуществами, что и модифицированный симп­лекс-метод.

2.4. Приклад решения ЗЛП двойственным симплекс-методом.

Рассмотрим на конкретном, Прикладе процесс реше­ния КЗЛП двойственным симплекс-методом. Для этого, опять-таки, вернемся к задаче (1.34)-(1.35), решенной в п. 1.4.3 и п. 1.5.2. Предположим, что произошли изменения в векторе ограничений b в результате которых

Содержание исходной симплекс-таблицы T⁽¹⁾ (за исключением столбца b(β⁽¹⁾)) будет идентично содержанию таблицы, полу­чающейся на последнем шаге алгоритма, рассмотренного в п. 1.4.3. Для вычисления значений b(β⁽¹⁾) в данном случае мож­но воспользоваться обратной матрицей, полученной на послед­ней итерации в п. 1.5.2:

В результате имеем:

Как видно из таблицы Т⁽¹⁾, в столбце b(β⁽¹⁾) содержатся отрицательные элементы b₁(β⁽¹⁾) = - 1/3<0), то есть базис β⁽¹⁾ ={ ⁵, ¹, ³} не является оптимальным, но в то же время легко убедиться, что он обладает свойствами сопряженного базиса. Отрицательный элемент в b(β⁽¹⁾) является единствен­ным, поэтому номер столбца, выводимого из базиса, опреде­ляется однозначно — r = 1 и N₁(β⁽¹⁾)=5. Далее рассматриваем строку a₁(β⁽¹⁾) = (0, -1/6, 0, -1/6, 1). В ней имеются отри­цательные элементы. Вычисляем λ₂ =42:(-(-1/6))=252, λ₄ =38:(-(-1/6))=228. λ₂> λ₄, следовательно, номер столбца, вводимого в базис — l = 4. Осуществляем преобразование и получаем симплекс-таблицу T⁽²⁾.

Поскольку b(β⁽²⁾) >0, то достигнутый базис N(β⁽²⁾) = {4,1,3} является оптимальным. Из Т⁽²⁾ можно выписать оптимальный план х* = (6, 0, 32/3, 2, 0) и соответствующее ему значение це­левой функции f(x*)= 444.