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

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

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

(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 ~ {а¹, а²} и т. д.).

• Надалі систему β={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), и процесс итеративно повто­ряется. В результате через конечное число шагов будет найден оптимальный план КЗЛП или установлен факт пустоты множе­ства допустимых планов.