Формы записи задач линейного программирования

2. 5. Формы записи задач линейного программирования Наиболее общая форма записи задачи линейного программирования имеет вид: L  Cо  С1x1    a11x1    Cjxj   Cn xn  max(min) a1n xn  b1  a p1x1    a pj x j    a pn xn  b p (1)      (2) a( p1)1x1    a(p1) j x j    a(p1) n xn  b p1     aq1x1    aqj x j    aqn xn  bn   (3) a1 j x j (2. 24) a(q1)1x1    a(q1) j x j    a(q1) n xn  bq1     am1x1    amj x j    amn xn  bn    d1  x1  D1     d j  xj  Dj     d n  xn  Dn  (4) (5) Задача линейного программирования включает: целевую функцию (1), которую следует максимизировать или минимизировать, ограничения, записанные в виде равенств (2), неравенств со знаком “ ≤ ” (3), неравенств со знаком “ ≥ “ (4), которые надо удовлетворить, граничные условия (5), которые показывают предельно допустимые минимальные ( d j ) и максимальные ( D j ) значения переменных. Из анализа существующих форм записи задач ЛП следуют следующие примечания: 43 – наиболее распространённым видом граничных условий в задачах ЛП является требование неотрицательности переменных, которое записывается в виде x j  0, j  1, n ; – ограничения (4) задачи могут быть приведены к виду (3) умножением обеих частей неравенств на  1 . Сокращённая форма записи задачи ЛП с учётом приведённых замечаний имеет вид L  Co  n  C j x j  max(min) j 1  aij x j  bi , i  1, p  aij x j  bi , i  p  1, m x j  0, (2. 25) j  1, n Такая форма записи задачи ЛП называется смешанной. Она характеризуется тем, что часть ограничений задачи ЛП задана в виде равенств, а другая часть – в виде неравенств. Если все ограничения задачи заданы в виде неравенств, причём все ограничения приведены к виду "" , то такая форма записи называется симметричной: L  Co  n  C j x j  max(min) j 1  aij x j  bi , x j  0, i  p  1, m (2. 26) j  1, n Если все ограничения задачи ЛП заданы в виде линейных уравнений, то такая форма записи называется канонической: L  Co  n  C j x j  max(min) j 1  aij x j  bi , x j  0, 44 i  1, p j  1, n (2. 27) При формировании ограничений в задачах ЛП следует обратить внимание на то, чтобы уравнения, входящие в систему ограничений, были бы линейно независимыми, так как они определяют мерность пространства и результаты решения. Линейно зависимыми называются такие уравнения, которые получаются в результате умножения или деления уравнения на одно и то же число, а также сложения или вычитания уравнений. Например, в системе линейных уравнений 3x1  4 x2  20 2 x1  x2  15 5 x1  3x2  35 последнее уравнение получено сложением первых двух и, следовательно, является линейно зависимым и никакой новой информации не несёт. 2. 6. Понятие о симплекс-методе линейного программирования 2. 6. 1. Методы решения задач линейного программирования Решение задач ЛП может быть осуществлено с помощью ряда методов, которые подразделяются на следующие группы: – универсальные методы, примером которых могут служить симплекс-метод, метод разрешающих множителей Л. В. Канторовича и др. [7]; – специальные методы, применяемые для решения отдельных классов задач. Они проще, но пригодны не для всех задач; – приближённые методы, отличающиеся простотой и удобством использования, особенно при ручном счёте. Это индексный метод, метод аппроксимации Фогеля и др. [1]. В настоящее время наибольшее распространение получил симплексметод, предложенный Джоном Данцигом в 1947 г. [1] и имеющий ряд модификаций. Ниже будет рассмотрен симплекс-метод в табличной модификации. Для реализации на ЭВМ в зависимости от специфики задач могут применяться и другие модификации. Для нахождения оптимального решения необходимо и достаточно перебрать опорные решения и сравнивать значения целевой функции при каждом опорном решении, т. е. в каждой вершине ОДР. Симплекс-метод как раз обеспечивает целенаправленный перебор вершин ОДР и позволяет найти вершину, соответствующую оптимальному значению целевой функции, за конечное число шагов, обычно называемых итерациями. 45 2. 6. 2. Запись задачи линейного программирования в стандартной форме Симплекс-метод обеспечивает решение задач ЛП, сформулированных в канонической форме записи, т. е. в том случае, когда все ограничения представляют собой уравнения. Если же в результате формализации задачи ограничения имеют вид неравенств, то необходимо от неравенств перейти к уравнениям. Такой переход от неравенств к уравнениям осуществляется следующим образом. Пусть в результате формализации задачи составлена система неравенств a11x1  a12 x2    a1n xn  b1 a21x1  a22 x2    a2n xn  b2 ................................... am1x1  am2 x2    amn xn  bm x j  0, j  1, n (2. 28) Переменные x1, x2 ,, xn , входящие в начальную формализованную задачу, называют основными. Для перехода от системы неравенств к системе уравнений вводят в каждое неравенство по одной дополнительной неотрицательной переменной y1, y2 ,, ym . Тогда a11x1  a12 x2    a1n xn  y1  b1 a21x1  a22 x2    a2n xn  y2  b2 ·························································· am1x1  am2 x2    amn xn  ym  bm x j  0, (2. 29) j  1, n; yi  0, i  1, m . Для системы уравнений характерно следующее: – система включает N переменных, причём N  n  m, где n и m – соответственно число основных и дополнительных переменных; – все переменные неотрицательны. 46 Система уравнений в краткой форме записи имеет вид  aij x j  yi  bi x j  0, j  1, n; yi  0, i  1, m . (2. 30) Каноническая форма записи является исходной для решения задачи ЛП симплекс-методом, но она должна быть преобразована. Так, все переменные задачи должны быть разделены на б а з и с н ы е, число которых равно m , и с в о б о д н ы е, число которых равно k , причём базисные переменные и целевая функция должны быть выражены через свободные. При этом не следует смешивать свободные переменные с основными, а базисные с дополнительными. Наиболее просто разделение переменных на базисные и свободные можно произвести в случае, когда каноническая форма задачи ЛП получена из симметричной путём введения дополнительных переменных. Мерность пространства такой задачи равна k  N  m , где N  n  m – число основных и дополнительных переменных в уравнениях; m – число ограничений. Следовательно, k  n  m  m  n . Поэтому, приняв m дополнительных переменных за базисные и выразив их через k  n основных переменных, получим первое базисное решение. В этом базисном решении все основные переменные являются свободными и равны нулю, т. к. их количество равно k , все дополнительные – базисными и равны правым частям в ограничениях. После определения первого базисного решения задачу ЛП можно записать в виде стандартной таблицы. Рассмотрим составление стандартной таблицы. Дана задача ЛП, записанная в симметричной форме, имеющая три основные переменные ( n  3 ) и четыре ограничения ( m  4 ): L  C0  C1x1  C2 x2  C3 x3  max a11x1  a12 x2  a13 x3  b 1 a21x1  a22 x2  a23 x3  b2 a31x1  a32 x2  a33 x3  b3 a41x1  a42 x2  a43 x3  b4 x j  0, j  1,3 . 47 (2. 31) Введём в задачу дополнительные переменные y1, y2 , y3 , y4 и от неравенств перейдём к уравнениям: a11x1  a12 x2  a13 x3  y1  b1 a21x1  a22 x2  a23 x3  y2  b2 a31x1  a32 x2  a33 x3  y3  b3 a41x1  a42 x2  a43 x3  y4  b4 x j  0, (2. 32) j  1,3; yi  0, i  1,4 . В данной системе N  n  m  3  4  7; k  N  m  3. Примем n  k  3 основных переменных свободными и выразим через них m  4 дополнительных переменных y i , которые станут базисными. Перепишем систему в виде y1  b1  (a11x1  a12 x2  a13 x3 ) y2  b2  (a21x1  a22 x2  a23 x3 ) (2. 33) y3  b3  (a31x1  a32 x2  a33 x3 ) y4  b4  (a41x1  a42 x2  a43 x3 ). Форма записи (2. 33) характеризуется следующим: 1) свободный член стоит на первом месте; 2) все переменные заключены в скобки, перед которыми вынесен знак “минус”; 3) во всех уравнениях в скобках заключены одни и те же переменные. В аналогичной форме запишем целевую функцию L  C0  (C1x1  C2 x2  C3 x3 )  max. (2. 34) Окончательно получаем систему L  C0  (C1x1  C2 x2  C3 x3 )  max y1  b1  (a11x1  a12 x2  a13 x3 ) y2  b2  (a21x1  a22 x2  a23 x3 ) y3  b3  (a31x1  a32 x2  a33 x3 ) y4  b4  (a41x1  a42 x2  a43 x3 ) x j  0, j  1,3 ; yi  0, i  1,4 . 48 (2. 35) Эта форма называется стандартной. В такой форме переменные, заключённые в скобках ( x1, x2 , x3 ), являются свободными, а стоящие в левых частях уравнений ( y1, y2 , y3 , y4 ) – базисными. Для сокращения записи стандартную форму принято записывать в виде таблицы коэффициентов, называемой стандартной таблицей (табл. 2. 1). Стандартная таблица является основой решения задачи ЛП симплекс-методом. С помощью стандартной таблицы можно получить ответ на ряд важных вопросов и осуществить как решение задачи, так и её последующий анализ. Рассмотрим пример записи задачи в стандартной форме: L  2 x1  2 x2  x3  min x1  x2  x3  1 2 x1  x3  5 x1  x2  2 2 x2  x3  2 x j  0, j  1,3 . Таблица 2. 1 Стандартная таблица симплекс-метода Свободный x x2 1 член x 3 C0  C1 C b1 a11 a12 a13 b2 a21 a22 a23 y3 b3 a31 a32 a33 y4 b4 a41 a42 a43 L y1 y2 49 2  C3 Приведём ограничения к симметричной форме, в первом и втором ограничениях поменяем знак неравенства на противоположный: L  2 x1  2 x2   x1  x2   2 x1 x1  x2 x3  min x3  1  x3  5  2 2 x2  x3  2 x j  0, j  1,3 . Введём дополнительные переменные: L  2 x1  2 x2   x1  x2   2 x1 x1  x2 x3  min x3  y1  1  x3  y2  5  y3  2 2 x2  x3  y4  2 x j  0, j  1,3; yi  0, i  1,4 . Перепишем условия в стандартной форме: L  0  (2 x1  2 x2  y1  1  ( x1  x2  x3 )  min x3 ) y2  5  (2 x1  0 x2  x3 ) y3  2  ( x1  x2  0 x3 ) y4  2  ( 0 x1  2 x2  x3 ) x j  0, j  1,3; yi  0, i  1,4 . Представим условия в виде стандартной таблицы (табл. 2. 2). 50 Таблица 2. 2 Стандартная таблица для симплекс-метода Свободный член x1 x2 x3 1 L y1 2 2 1 1 1 y2 5 2  1` y3 2 1 1 y4 2 2 1 1 Представление задачи ЛП в виде стандартной таблицы позволяет выявить несовместность ограничений и неограниченность целевой функции. Отсутствие ОДР, т. е. несовместность ограничений, определяется на каждой итерации поиска опорного решения с помощью признака 1. П р и з н а к 1. Ограничения будут несовместны, если на любой итерации поиска опорного решения в каждой строке, имеющей отрицательный свободный член, нет ни одного отрицательного элемента. Несовместность ограничений по табл. 2. 2 не выявлена. Неограниченность целевой функции проверяется с помощью стандартной таблицы на каждой итерации поиска как опорного, так и оптимального решений с помощью признаков 2. П р и з н а к 2 а. Целевая функция будет неограниченна снизу (т. е. min L будет отсутствовать), если в каждом столбце, у которого в строке целевой функции находится положительный элемент, нет ни одного положительного элемента. П р и з н а к 2 б. Целевая функция будет неограниченна сверху (т. е. max L будет отсутствовать), если в каждом столбце, у которого в строке целевой функции находится отрицательный элемент, нет ни одного положительного элемента. Неограниченность целевой функции по приведённой таблице (табл. 2. 2) не выявлена. Решение следует продолжить. После проведения проверки по рассмотренным признакам следует перейти к решению задачи, которое включает определение опорного и оптимального решений. 51 2. 6. 3. Нахождение опорного решения Опорным решением являются координаты любой вершины ОДР. При этом в любой вершине ОДР k переменных равны нулю, а остальные m переменных – неотрицательны. Исходя из этого, можно установить признак опорного решения. Если в стандартной таблице (см. табл. 2. 1) положить, что все n  3 свободных переменных x1, x2 , x3 равны нулю, то m  4 базисных переменных будут равны свободным членам y1  b1; y2  b2 ; y3  b3 ; y4  b4 . Поскольку в опорном решении k переменных должны быть равны нулю, а m должны быть неотрицательны, то, очевидно, что решение будет опорным, если все свободные члены будут неотрицательны: bi  0, i  1,4 . П р и з н а к 3. Решение будет опорным, если в стандартной таблице все свободные члены неотрицательны. В примере (см. табл. 2. 2) в строке y свободный член b  5 , следовательно, y  5 , и решение не явля2 2 2 ется опорным. Если первое решение, в котором все основные переменные ( x , x ,, x n ) являются свободными, а все дополнительные 1 2 ( y , y ,, y m ) – базисными, не является опорным, следует произвести 1 2 обмен переменных. Идея обмена переменных заключается в следующем. Требуется найти такой набор n свободных переменных, равных нулю, чтобы при этом остальные m базисных переменных были неотрицательны. При одном обмене (итерации) одна свободная переменная обменивается местами с одной базисной. При этом в результате обмена уменьшается либо число отрицательных свободных членов, либо абсолютное значение отрицательного свободного члена. После каждого обмена проверяется удовлетворение признаку опорного решения. Если признак удовлетворён, работа заканчивается, если нет – итерации повторяются. Идею обмена переменных рассмотрим на примере, записанном в стандартной таблице (см. табл. 2. 1). Допустим, необходимо обменить x 2 на y , т. е. x 3 2 из свободных перевести в базисные, а y 3 из базисных – в свободные. Такая операция обозначается в виде x  y . В рассматрива2 3 емом примере y  b  (a 3 3 x a 31 1 52 x a 32 2 x ) 33 3 (2. 36) поменяем местами x на y . Тогда 2 a 3 x  b  (a 32 2 3 x  y a 31 1 3 (2. 37) x ) 33 3 и окончательно a b  a 1 x  3   31 x  y  33 x  . 2 a 1 a 3 a 3 a 32  32 32 32  При этом, если выражение (2. 38) подставить вместо x (2. 38) в целевую функ- 2 цию и в остальные уравнения (см. табл. 2. 1), привести подобные члены, то вместо переменной x будет переменная y , а уравнения и целевая 2 3 функция изменятся следующим образом:   a b   a a  a a   a y1   b1  12 3    a11  12 31  x1  12 y3   a13  12 33  x3  ,   a32   a32  a32 a32             (2. 39)    C2 b3    C2 a31   C2  L  C0  y3      C1   x1  a a a 32   32 32          C2 a33       C3   x3  . a32      (2. 40) После определения опорного решения целевая функция и ограничения будут выражены через соответствующие свободные переменные, и на основе полученной стандартной таблицы можно переходить к определению оптимального решения. Чтобы облегчить работу по обмену переменных, составлен алгоритм, в основе которого лежит вышеизложенный метод модифицированных Жордановых исключений [6] . Алгоритм обмена переменных можно представить в виде пяти этапов: 1) записать условие задачи в виде стандартной таблицы; 2) выбрать разрешающий элемент; 3) заполнить нижние правые части ячеек стандартной таблицы; 4) перейти к следующей стандартной таблице; 5) проверить соответствие признакам. Рассмотрим алгоритм на примере поиска опорного решения. 53 I– й э т а п. Стандартная таблица заполняется на основании стандартной формы записи задачи. Особенностью является лишь то, что в отличие от табл. 2. 2 коэффициенты записываются не в центре ячейки, а в левом верхнем углу каждой ячейки (см. табл. 2. 3). Таблица 2. 3 Стандартная таблица первого шага поиска опорного решения y 3 Свободный член L x1 2 y2 y3 x1  y4 1 2 5 2 1 1 2 1 1 1 2 2 2 1 4 1 1 2 1 2 2 1 1 x3 2 4 y1 x2 2 1 2 э т а п. Выбор разрешающего элемента при отыскании опорного решения производится следующим образом. А. Выбрать разрешающий столбец. В строке, содержащей отрицательный свободный член, выбрать отрицательный элемент. Столбец, содержащий этот отрицательный элемент, принять в качестве разрешающего и выделить двумя чертами (табл. 2. 3). Если в строке, содержащей отрицательный свободный член, нет отрицательного элемента, значит не выполняется признак 1, т. е. ограничения являются несовместными. Если в строке несколько отрицательных элементов, то лучше брать столбец с большим по абсолютной величине отрицательным элементом (2. 39). Б. Выбрать разрешающую строку. В разрешающем столбце рассматривают все элементы, имеющие знак, одинаковый со свободным членом той же строки. В качестве разрешающей строки выбирают ту, для которой отношение свободного члена к элементу разрешающего столбца минимально. По табл. 2. 3 54  b   5 2 min i   min ,   min2,5;2  2, im a  2 1   ij  что соответствует строке с y3 . Принятую i -ю строку (по табл. 2. 3 i  3 ) выделяют двумя чертами. В. Выделить разрешающий элемент. Разрешающим элементом aij является элемент, принадлежащий j -му разрешающему столбцу и i -й разрешающей строке. По табл. 2. 3 aij  1 . Разрешающий элемент выделяют. У разрешающих строки и столбца ставят знаки обмена x j  yi (см. табл. 2. 3). 3-й э т а п. Нижнюю правую часть ячейки разрешающего элемента заполняют величиной   1/ aij ; нижние правые части ячеек разрешающей строки – элементами, стоящими в верхних левых частях каждой ячейки, умноженными на  ; разрешающего столбца – элементами, стоящими в левых верхних частях каждой ячейки, умноженными на   . Выделяют, за исключением разрешающего элемента, в разрешающей строке все верхние числа, а в разрешающем столбце – все нижние. Нижние правые части остальных ячеек стандартной таблицы заполняют произведением выделенных чисел, стоящих в том же столбце и той же строке, что и заполняемая ячейка (см. табл. 2. 3). 4-й э т а п. Составляют следующую стандартную таблицу (табл. 2. 4), в которой меняют местами обмениваемые переменные x j и yi . Остальные переменные оставляют на своих местах. В верхние левые части ячеек бывших разрешающей строки и разрешающего столбца записывают величины, стоящие в нижних правых частях тех же ячеек предыдущей таблицы (для разрешающего столбца это совпадает с выделенными элементами). В верхних левых углах остальных ячеек (см. табл. 2. 4) ставят сумму двух величин, стоящих в каждой ячейке предыдущей таблицы. 5-й э т а п. При нахождении опорного решения проверяют удовлетворение признаку 3. Если признак 3 выполнен, значит, опорное решение найдено и следует перейти к определению оптимального решения. Если решение признаку 3 не удовлетворяет, необходимо проверить удовлетворение признакам 1 и 2. Если они не удовлетворяют решению, итерацию обмена переменных следует повторить. 55 Таблица 2. 4 Стандартная таблица второго шага поиска опорного решения y Свободный член L y 4  y2 2 1 1 2 y4 2 2 -1 2 2 1 1 1 2 1 1 2 1 1 2 2 1 2 2 1 x3 4 1 3 x1 x2 2 1 1 x3 y3 2 1 2 1 Так как свободный член в строке y2 (см. табл. 2. 4) равен  1 , признак 3 опорного решения не удовлетворяется. Следовательно, это решение опорным не является. Однако, абсолютное значение отрицательного свободного члена стало меньше. Значит, найденное решение ближе к опорному, чем первое. Проверим отсутствие ОДР по признаку 1. В строке y2 с отрицательным свободным членом есть отрицательный элемент  1 . Таким образом, отсутствие ОДР не установлено. Проверим неограниченность целевой функции. В данном примере находится min L . Согласно признаку 2а в столбцах, имеющих в строке целевой функции положительные элементы (по табл. 2. 4 – все элементы положительные), должны быть положительные элементы (положительные элементы есть в каждом столбце). Значит, неограниченность целевой функции не установлена. Решение задачи следует продолжить, т. е. повторить операции обмена переменных (табл. 2. 4, 2. 5) до нахождения опорного решения (табл. 2. 5). Полученное решение (см. табл. 2. 5) является опорным, т. к. все свободные члены неотрицательны. Поскольку свободные переменные y3 , x2 , y2 равны нулю, то ненулевые координаты вершины, являющиеся опорным решением, равны y1  2, x3  1, x1  2, y1  1. При этом целевая 56 функция L  3. По признаку 2а неограниченность целевой функции не выявлена. Следовательно, необходимо перейти к определению оптимального решения. Таблица 2. 5 Стандартная таблица третьего шага поиска опорного решения и первого шага поиска оптимального решения y Свободный член L 2 x3 1  y4 y3 x2 3  3/ 2 1 2 1 4 1/ 2  1/ 2 2 4 1/ 2 1  1/ 2 2  3/ 2 1 1  1/ 2 2 6 1 1 1 8 2 2 2 1 2  3/ 2 y2 6 4 2 y1 x1 y3 3 4 1 2 1/ 2 2. 6. 4. Определение оптимального решения Оптимальным решением являются координаты такой вершины ОДР, в которой целевая функция приобретает оптимальное (т. е. максимальное или минимальное) значение. Необходимо сформулировать признак оптимальности решения. Рассмотрим целевую функцию в стандартной форме: L  C0  (C1x1  C2 x2    C j x j    Cn xn ) (2. 41) Для упрощения принимаем j  1. Тогда целевая функция L  C0  (C1x1). 57 (2. 42) Возможны следующие варианты исходных ситуаций: 1-й в а р и а н т. L  C0  (C1x1 )  max. (2. 43) Очевидно, что при x1  0 L  C0 . Если  C1  0 , то при увеличении x1 , т. е. при переводе её из состава свободных в базисные, целевая функция будет уменьшаться. Уменьшать x1 нельзя, т. к. она – свободная переменная, и нарушится условие x1  0. Следовательно, полученное решение оптимально. Если  C1  0 , то переводя x1 из свободной в базисную и увеличивая её (т. е. переходя от одного опорного решения к другому), будем увеличивать и целевую функцию. Приведённые рассуждения можно распространить и на все другие  C j , j  2, n . На основе изложенного можно сформулировать признак достижения максимума целевой функции. П р и з н а к 4 а. Целевая функция имеет максимальное значение в том случае, если все коэффициенты в строке целевой функции (кроме свободного члена) являются положительными. 2-й в а р и а н т. L  C0  (C1x1)  min (2. 44) Так же, как и в предыдущем случае, при x1  0 L  C0 . Если  C1  0 , то при увеличении x1 , т. е. при переводе её из состава свободных в базисные, целевая функция будет уменьшаться. Если  C1  0 , то любое значение x1 приведёт только к увеличению L . Таким образом, при  C1  0 решение является оптимальным. Все рассуждения можно распространить на все x j , j  1, n . Можно сформулировать признак минимального значения целевой функции. П р и з н а к 4 б. Целевая функция имеет минимальное значение в том случае, когда все коэффициенты в строке целевой функции (кроме свободного члена) являются отрицательными. 58 3-й в а р и а н т. L  C0  (C1x1)  max(min) (2. 45) Если  C1  0 , то L  C0 . Этот случай является признаком наличия альтернативного, т. е. не единственного оптимального решения. Его можно сформулировать так. П р и з н а к 4 в. Задача ЛП имеет альтернативные, т. е. не единственные значения x j , придающие целевой функции оптимальное значение в случае, когда среди  C j есть нулевые элементы. При этом максимальное или минимальное значение целевой функции определяется знаками остальных ненулевых коэффициентов  C j в строке целевой функции (без учёта свободного члена). В том случае, когда в строке целевой функции есть коэффициент, знак которого не соответствует признаку искомого оптимального решения (например, при поиске максимума функции есть отрицательные коэффициенты), то свободные переменные, имеющие эти коэффициенты, следует переводить в базисные. Остальное выполняется так же, как и при поиске опорного решения. Поясним это на продолжении предыдущего примера (табл. 2. 5, 2. 6). Последняя таблица (табл. 2. 6) удовлетворяет признаку 4б, так как все коэффициенты при переменных в строке целевой функции отрицательны. Следовательно, целевая функция имеет минимальное значение, равное min L  1. При этом переменные равны: x1  3 / 2; x2  0; x3  2; y1  1/ 2; y2  0; y3  1/ 2; y4  0 . Если сравним значение целевой функции min L  1 со значением целевой функции при опорном решении, когда L  3 , то увидим, что значение её в оптимальном решении меньше, чем в опорном. Указанное условие является признаком правильности проведения решения: от итерации к итерации целевая функция должна уменьшаться (при минимизации), или увеличиваться (при максимизации), или в крайнем случае оставаться равной её прежнему значению (когда имеет место случай вырожденности). 59 Таблица 2. 6 Стандартная таблица оптимального решения задачи Свободный член y4 x2 y2 L 1 2 2 1 y1 1/ 2  3/ 2 4  1/ 2 x3 2 1 2 x1 1/ 2  1/ 2 1  1/ 2 y3 1/ 2 1/ 2 2 1/ 2 2. 6. 5. Выбор первого базиса В том случае, когда задача ЛП задана в симметричной форме, т. е. когда ограничения заданы в виде неравенств, первым базисом являются дополнительные переменные. Выбор первого базиса в общем виде при задании ограничений в симметричной форме может быть представлен следующим образом. Пусть задана задача ЛП в симметричной форме: L  C0  n  C j x j  max(min) j 1 n  aij x j  bi , i  1, m j 1 (2. 46) x j  0, j  1, n . Введём дополнительные переменные n  aij x j  yi  bi , i  1, m , j 1 (2. 47) x j  0, j  1, n ; yi  0, i  1, m . Запишем ограничения в стандартной форме:  n  yi  bi    aij x j , i  1, m .  j 1  60 (2. 48) При такой записи все m дополнительных переменных стали базисными, а все n основных – свободными. В том случае, когда задача ЛП включает ограничения, заданные в виде уравнений, т. е. задача сформулирована в канонической или смешанной форме, выбор первого базиса может быть осуществлён с помощью введения искусственных переменных  i , равных по условию нулю. Пусть задана задача ЛП в канонической форме: L  C0  n  C j x j  max(min) j 1 n  aij x j  bi , i  1, m (2. 49) j 1 x j  0, j  1, n . Запишем ограничения в стандартной форме следующим образом:  n    i  bi    aij x j   0, i  1, m j 1 (2. 50) При такой форме записи в первый базис входят m искусственных переменных  i , равных по условию нулю. После составления первой стандартной таблицы следует все искусственные переменные вывести из базиса, а на их место ввести основные переменные, которые были свободными. После перевода искусственной переменной в свободные весь столбец, ей соответствующий, следует вычеркнуть. Таким образом, после вывода всех искусственных переменных  i в свободные и их исключения все основные переменные окажутся разделёнными на базисные и свободные, после чего решение задачи производится обычным образом. П р и м е р: L  6  2 x1  x2  3x3  2 x4  10 x5  min x1  x2  2 x3  2 x4  6 x5  2 x1  2 x2  x3  7 x4  3x5  5  x1  x2  x3  x4 x j  0, j  1,5 . 61 4 Запишем задачу в стандартной форме: L  6  ( 2 x1  x2  3x3  2 x4  10 x5 )  min 1  2  ( x1  x2  2 x3  2 x4  6 x5 ) 2  5  ( x1  2 x2  x3  7 x4  3x5 ) 3  4  ( x1  x2  x3  x4 ). Дополнительно введём вспомогательную целевую функцию l  1   2  3 и подставим в неё значения 1,  2 , 3. Тогда получим l  11  ( x1  2 x2  2 x3  4 x4  3x5 ). Составим стандартную таблицу (табл. 2. 7). Из базисных переменных необходимо вывести искусственные 1,  2 , 3 , а на их место ввести основные. Вопрос заключается в том, как выбирать при этом разрешающий столбец. При выборе разрешающего столбца возможны следующие варианты: – в качестве разрешающего столбца можно выбрать любой. При этом после вывода всех искусственных переменных приступают к отысканию опорного, а затем оптимального решения; – при выборе разрешающего столбца исходят не только из задачи минимизации вспомогательной целевой функции l . В этом случае получение min l  0 будет соответствовать опорному решению основной задачи. При решении по этому варианту предварительно требуется привести все свободные члены к виду bi  0 умножением левой и правой частей ограничения с bi  0 на  1 . После получения опорного решения необходимо перейти к нахождению оптимального решения. В данном случае без подготовки ограничений (т. к. все bi  0 ) можно воспользоваться вторым вариантом. Для обмена переменных 1  x1,  2  x2 , 3  x3 воспользуемся соответственно табл. 2. 7-2. 9. 62 Таблица 2. 7 Стандартная таблица первого базиса  1 Свободный член 11 l x1 1 2 1 2 2 5 3 4 1 -1 -1 1 2 1 1 2 12 -6 -2 -6 7 3 -2 2 1 6 -1 -1 1 -10 -2 2 1 6 4 -1 -1 -1 -4 2 2 -2 2 -2 -1 1 -3 -2 2 x5 4 3 -2 -4 x4 2 -1 L x1  x3 2 -2 6 x2 2 -2 -6 Таблица 2. 8 Стандартная таблица после первого обмена переменных  2 Свободный член 9 3 l L 1 2 x1 x2  2 3 -1 -1 3 1 63 -6 9 3 3 9 3 -3 -3 3 -1 1/3 2 -2 -3 -9 -3 -1 1/3 3 6 2 2 1 3 -9 1 -1/3 x5 6 3 -1 -1 x4 3 -3 2 x x2 3 -6 Таблица 2. 9 Стандартная таблица после второго обмена переменных  3 Свободный член 6 l 1 1 -3 3 3 -3 1/3 2 2 -1 1/3 3 1 -1/3 2 6 -1 1 -1 6 -2 x2 3 -1 x1 -6 3 -1 3 x5 -3 -6 L x4 3 1 x3  x3 -2 -6 -1 -2 В табл. 2. 10 целевая функция l  0 , что должно соответствовать опорному решению. Действительно, свободные члены для всех переменных являются положительными, значит, опорное решение найдено. Заметим, что если окажется, что вспомогательная целевая функция l  0 , то это признак того, что ограничения несовместны и ОДР отсутствует. После нахождения опорного решения следует перейти к определению оптимального решения. В данном примере ищем min L . В строке целевой функции L коэффициенты при переменных отрицательны. Значит, в соответствии с признаком 4б найденное опорное решение является оптимальным. Итак, решением будут следующие значения переменных: x1  1; x2  3 ; x3  2 ; x4  0 ; x5  0 . При этом min L  1 . Если задача ЛП задана в смешанной форме, то первый базис также будет смешанным и будет включать искусственные переменные i , i  1, p (2. 24) для равенств и дополнительные переменные yi , i  p  1, m для неравенств. После формирования первого базиса следует приступить к выведению из базиса искусственных переменных, как это было рассмотрено выше, после чего отыскать опорное и оптимальное решение в обычном порядке 64 Таблица 2. 10 Стандартная таблица после третьего обмена переменных Свободx4 x5 ный член l L x1 1 -1 -1 1 2 -1 x2 3 2 1 x3 2 -1 -2 2. 7. Двойственная задача линейного программирования Итак, задача линейного программирования в симметричной форме имеет вид n  C j x j  max(min) j 1 n  aij x j  bi , i  1, m j 1 (2. 51) x j  0, j  1, n Это прямая задача. Имеется двойственная ей задача, в которой каждой переменной прямой задачи будет соответствовать ограничение и каждому ограничению – переменная. Будем иметь дело с новым вектором переменных u1, u2 ,, um . Итак, двойственная задача, соответствующая прямой, имеет вид m  biui  min(max) i1 m  aij ui  C j , i1 j  1, n (2. 52) ui  0, i  1, m Между этими двумя задачами имеется глубокая связь, которая имеет фундаментальное значение в теории линейного программирования. 65 Рассмотрим эту связь с помощью теорем. Т е о р е м а д в о й с т в е н н о с т и 1. Допустимый вектор X  оптимален тогда и только тогда, когда существует оптимальный вектор U  двойственной задачи и CX   U B. (2. 53) То есть прямая и двойственная задачи одновременно имеют оптимальные решения тогда и только тогда, когда обе задачи имеют допустимые решения. Если одна из задач не имеет допустимого решения, то двойственная ей задача либо неограниченна, либо также не имеет допустимых решений. При удовлетворении обеих задач теореме говорят, что обе задачи взаимно двойственны. П р и м е р : проверить оптимальность векторов X   (8,0) и U   (0,3) в следующих задачах: L1  3x1  2 x2  max | L2  2u1  8u2  min  2 x1  x2  2 | x1  2 x2  8 | x1, x2  0 |  2u1  u2  3 u1  2u2  2 u1, u2  0 В этом случае надо убедиться, двойственны ли эти задачи, а затем проверить критерий оптимальности в соответствии с теоремой 1. L1  3  8  2  0  24; L2  2  0  8  3  24 . L1  L2 . Значит, X  и U  – оптимальные решения. П р и м е р : имеет ли прямая задача оптимальное решение? Прямая задача L1  x1  x2  max |  2 x1  x2  2 |  x1  2 x2  1 | x1, x2  0 | 66 Двойственная задача L2  2u1  u2  min  2u1  u2  1  u1  2u2  1 u1, u2  0 При любых положительных значениях переменных ограничения двойственной задачи соблюдаться не будут, что соответствует отсутствию допустимого решения. Значит, согласно теореме 1 целевая функция прямой задачи неограниченна. Т е о р е м а д в о й с т в е н н о с т и 2. Векторы X  и U  суть оптимальные решения соответствующих задач тогда и только тогда, когда выполняются следующие равенства: m  xj   aij ui  C j   0, j  1, n ,  i1   n  ui   a xj  bi   0, i  1, m  j 1 ij  (2. 54) Если выполняются неравенства n  aij xj  bi , то ui  0; j 1 m  aij ui  C j , то i1 xj  0. (2. 55) Э к о н о м и ч е с к а я и н т е р п р е т а ц и я 2-й т е о р е м ы д в о й с т в е н н о с т и. Допустим, рассматривается распределение видов механизированных работ с заданными объёмами по способам исполнения (комплектам машин или машинам). При этом x j , j  1, n – искомые объёмы заданных работ по возможным способам исполнения. Каждая машина характеризуется определённым ресурсом bi (количество машино-часов в плановом периоде). Задаётся матрица ( aij ) – технологическая матрица размерностью m  n , где aij показывает, какое количество машино-часов i -й машины необходимо для выполнения единицы работы. Необходимо найти такой план ( x1,, xn ), чтобы минимизировать суммарные затраты и не выйти за пределы имеющихся в наличии ресурсов. Итак, модель задачи: затраты n  C j x j  min j 1 67 при условиях: n  aij x j  bi , i  1, m x  0, j  1, n j 1 j (2. 56) При оптимальном решении имеем CX   U B . Поскольку левая часть соотношения есть затраты, то U  будет иметь смысл оценки ресурсов. Если потребление ресурса i –й машины в оптимальном решении таково, что этот ресурс используется неполностью, то ресурсу этой машины даётся нулевая оценка. aijU i – оценка выполнения единицы объёма работы машиной i . Если m  aijU i  C j , i1 то данную работу данным комплектом машин выполнять невыгодно. Таким образом, вторая теорема двойственности утверждает: а) выполнение работы данным комплектом машин, суммарная оценка выполнения единицы которой превышает цену C j , должно быть исключено из плана: m  aij ui  C j  xj  0; (2. 57) 1 i б) ресурс машины i , который не может быть полностью использован при производстве работ по оптимальному плану, получает нулевую оценку: n  aij xj  bi  ui  0. j 1 (2. 58) Рассмотрим составление двойственной задачи для прямой задачи, сформулированной в смешанном виде при наличии свободных переменных. Прямая задача n  C j x j  max(min) j 1 68 n  aij x j  bi , i  1, m1 j 1 n  aij x j  bi , i  m1  1, m j 1 (2. 59) x j  0, j  1, n1 x j  0, j  n1  1, n . Двойственная задача m  biui  min(max) i1 m  aij ui  C j , i1 m j  1, n1  aij ui  C j , i1 j  n1  1, n (2. 60) ui  0, i  1, m1 ui  0, i  m1  1, m . П р и м е р: записать задачу 5x1  3x2  4 x3 3x1  2 x2  2 x5  max  6 x4  3x5  4 7 x1  5x2  4 x3  8x4 3x1 (1) 6 (2)  2 x3  4 x4  x5  7 (3) x1, x2 , x4  0 x , x5  0 3 в двойственной постановке. Неравенство (1) нужно привести к виду “  ” и сгруппировать неравенства и равенства отдельно: 5x1  3x2  4 x3 u1 | u2 | u3 |  3x1  2 x2 3x1  2 x5  max  6 x4  3x5  4  2 x3  4 x4  x5  7 7 x1  5x2  4 x3  8x4  6 x1, x2 , x4  0 69 x , x5  0 . 3 Двойственная задача  4u1  7u2  6u3  max  3u1  3u2  6u3  5  2u1  5u3  3  2u2  4u3  4 6u1  4u2  8u3  0  3u1  u2 2 u1, u2  0 u3  0 . 70