lopt7 (Лекционный курс)

Лекция 76. ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯA. СИМПЛЕКС-МЕТОД ДАНЦИГАА1. Решение канонической задачиПостановка задачиНайти максимум функцииnf ( x) = ∑ c j x jj =1при ограниченияхn∑ ai j x jj =1= bi , i = 1,… , m; m < n ,x j ≥ 0 , j = 1, … , n .Задача называется канонической, а искомое решение x ∗ = ( x1∗ ,..., x n∗ )T – оптимальным.З а м е ч а н и я.1. Максимизируемая функция и ограничения линейны по x j , j = 1, … , n .2. Задача содержит ограничения на неотрицательность переменных, присутствиекоторых диктуется процедурой описанного ниже симплекс-метода.3. Будем считать, что в ограничениях все числа bi ≥ 0 , i = 1, … , m . Этого можнодобиться, умножая ограничения, где bi < 0 , на “ − 1 ”.Стратегия поискаСтратегия метода Данцига (Dantzig) решения задачи основана на особенностях постановки этой задачи.

Множество⎧⎪X = ⎨x⎪⎩n∑ ai j x j = bi ;i = 1, … , m;j =1x ∈ R n;⎫⎪x j ≥ 0; j = 1, … , n ⎬⎪⎭допустимых решений задачи, определяемое ограничениями, есть выпуклое множество,которое геометрически представляет собой выпуклый политоп, имеющий конечное числокрайних точек.Крайней точкой выпуклого множества X называется точка x ∈ X , которая не может быть выражена в виде выпуклой комбинации других точек y ∈ X , x ≠ y .Классический метод Гаусса–Жордана решения систем линейных уравнений состоит в приведении их к виду56+ a1m +1 x m +1 + … + a1s x s + … + a1n x n = b1 ,x1xk+ ak m +1 x m +1 + … + ak s x s + … + ak n x n = bk ,x m + amm +1 x m +1 + … + am s x s + … + amn x n = bm .Переменные x1 ,… , x m , входящие только в одно из уравнений системы с коэффициентами 1, а во все остальные уравнения с коэффициентами, равными нулю, называются базисными, в то время как остальные n − m переменных называются небазисными(свободными).

Базисным решением системы называется решениеx i = bi , i = 1, … , m ; x m +1 = … = xn = 0 .Базисное решение называется допустимым, если xi ≥ 0 , i = 1, … , m . Базисное решение называется невырожденным, если xi > 0 , i = 1, … , m .Множество крайних точек политопа X, определяемого ограничениями, соответствует множеству допустимых базисных решений системы, и при этом одному базисномурешению соответствует одна крайняя точка.Утверждение. Если функция f ( x ) в канонической задаче достигает максимума наполитопе X, определяемом ограничениями, то она достигает его по крайней мере в одной крайней точке этого политопа.

Если она достигает его в нескольких крайних точках, то она достигает его на любой выпуклой комбинации этих крайних точек.Теорема определяет стратегию решения задачи, реализованную с помощью симплекс-метода, – это направленный перебор базисных решений, определяющих крайниеточки политопа. Направленность перебора предполагает следующую организацию вычислительного процесса.1. Нахождение начального базисного решения.2. Переход от одного базисного решения к другому таким образом, чтобы обеспечить возрастание f ( x) .А2. Решение основной задачиПостановка задачиНайти максимум функцииnf ( x) = ∑ c j x jj =1при ограниченияхn∑ aij x j ≥ bi ,j =1n∑ aij x j ≤ bi ,i = 1, … , m ;i = m + 1, … , p ;j =1x j ≥ 0 , j = 1, … , n .Данная задача линейного программирования называется основной.

Предполагается, что bi ≥ 0 , i = 1, … , p .57Стратегия поискаДля решения основной задачи симплекс-методом она должна быть приведена кканонической задаче путем введения в каждое ограничение по одной дополнительной переменной: в каждое ограничение-неравенство со знаком « ≤ » вводится дополнительнаяпеременная со знаком « + » (она становится базисной), а в каждое ограничениенеравенство со знаком « ≥ » вводится дополнительная переменная со знаком «–».Каноническая задача записывается следующим образом:nf ( x) = ∑ c j x j → max ,j =1n∑ aij x j − x n +i = bi ,i = 1, … , m ;j =1n∑ aij x j + x n +i = bi ,i = m + 1, … , p ;j =1x1 ≥ 0, … , x n + p ≥ 0 .Так как в общем случае в уравнениях нет базисных переменных, то для того, чтобыможно было применить симплекс-метод, делается переход к М-задаче.

В каждое из mуравнений вводится искусственная переменная со знаком « + » (она становится базисной),а к целевой функции добавляется сумма искусственных переменных, умноженная на« − M ». В результате получаем задачу в расширенной форме:nf ( x) = ∑ c j x j − Mj =1nm∑ x n + p +i → max ,i =1∑ aij x j − x n +i + x n + p +i = bi ,i = 1, … , m ;j =1n∑ aij x j + x n +i = bi ,i = m + 1, … , p ;j =1x1 ≥ 0, … , x n + p + m ≥ 0 .З а м е ч а н и я.Если решается задача поиска минимума целевой функции, то при переходе к M задаче перед числом M ставится знак « + ».58Б. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯВ случае двух переменных задача линейного программирования имеет простуюгеометрическую интерпретацию и может быть решена графически с помощью следующего алгоритма.Алгоритм1. Построить множество допустимых решений.

В общем случае оно представляетсобой выпуклый многоугольник. Если ограничения в задаче несовместны, множество допустимых решений является пустым множеством, а задача поиска экстремума не имеетсмысла.2. Найти градиент целевой функции. В силу ее линейности градиент постоянен иможет быть построен в любой точке координатной плоскости (как правило, он строится вначале координат).3. Провести линию уровня функции, перпендикулярную градиенту.4. Передвигать линию уровня параллельно самой себе до касания с множествомдопустимых решений.

Точки касания являются точками экстремума.5. Классифицировать точки касания с использованием свойств градиента.В случае непустого множества допустимых решений возможны три типовые ситуации:а) задача имеет единственное решение (линия уровня касается множества допустимых решений в одной точке);б) задача имеет бесконечное множество решений (линия уровня касается множества допустимых решений вдоль стороны многоугольника);в) задача не имеет решения (множество допустимых решений не ограничено).Заметим, что графически можно решать и задачи с ограничениями типа равенств,если число ограничений на единицу или на два меньше числа переменных.

Способ решения: сведение к задаче с одной или двумя переменными соответственно. Для этого следует выразить целевую функцию и базисные переменные через свободные и воспользоваться условием неотрицательности, типичным для задач линейного программирования. Далее необходимо пользоваться приведенным алгоритмом графического решения задач линейного программирования.Пример. Решить графически следующие задачи линейного программирования:а) f ( x ) = − x1 + x 2 → extr ,б) f ( x ) = x1 → extr ,x1 + x 2 ≤ 1 ,x1 + x 2 ≤ 1 ,x1 ≥ 0, x 2 ≥ 0 ;x1 ≥ 0, x 2 ≥ 0 ;в) f ( x ) = − x1 − x 2 → extr ,x1 ≥ 1 , x 2 ≥ 1 .† Воспользуемся приведенным алгоритмом графического решения задач линейного программирования.В задаче «a» в точке A = (0; 1)T достигается максимум, а в точке B = (1; 0)T – минимум. Очевидно, и минимум, и максимум единственные.59В задаче «б» в точке C = (1; 0)T достигается максимум, а на отрезке АВ – минимум, т.е. имеется бесконечное множество решений.x2∇fx2A 1f ( x) = 0f ( x) = 11 B1B−10x2−1C∇f 11 x1 0 AA0x11∇fаб−1x1f ( x) = 0вРис.

1В задаче «в» в точке A = (1; 1)T достигается максимум, а минимума нет, так какмножество допустимых решений в направлении антиградиента (наискорейшего убыванияфункции) неограниченное. „7. ЗАДАЧИ ЛИНЕЙНОГО ЦЕЛОЧИСЛЕННОГОПРОГРАММИРОВАНИЯ. МЕТОД ВЕТВЕЙ И ГРАНИЦПостановка задачиНайти максимум функцииnf ( x) = ∑ c j x jj =1при ограниченияхn∑ aij x jj =1≤ bi , i = 1, … , m ;x j ≥ 0 , целые, j = 1, … , n .Задача называется задачей линейного целочисленного программирования.60Стратегия поискаЗадача решается симплекс-методом без учета ограничений на целочисленность переменных (эта задача обозначается ЗЛП-0).

Считается, что она имеет решение. На опти-( )мальном решении x 0∗ = ( x10∗ ,… , x n0∗ ) T вычисляется значение целевой функции f x 0∗ .Если решение x 0∗ является целочисленным, то поставленная задача решена. Еслирешение x 0∗ оказывается нецелочисленным, то значение f ( x 0∗ ) является верхней границей возможных оптимальных значений f ( x ) на целочисленных решениях. При нецелочисленном решении дальнейшая процедура решения задачи состоит в ее ветвлении надве: ЗЛП-1 и ЗЛП-2 (рис.2). Целью этого ветвления является разбиение множества допустимых решений, определяемого ограничениями, на два подмножества путем формирования дополнительных ограничений таким образом, чтобы исключить нецелочисленнуюточку x 0∗ и сделать решение, по крайней мере одной из задач, целочисленным по однойвыбранной координате x k .Координатой x k может быть:• нецелочисленная координата с наименьшим или наибольшим индексом;• нецелочисленная координата с наименьшей или наибольшей дробной частью;• нецелочисленная координата, которой соответствует наибольший коэффициентв целевой функции;• нецелочисленная координата, выбранная на основании приоритетов, определяемых физическим содержанием задачи.ЗЛП-0x 0∗ , f (x 0∗ )[ ][ ]x k ≤ x k0∗x k ≥ x k0∗ + 1ЗЛП-1x , f (x 1∗ ) > f (x 2∗ )ЗЛП-2x , f ( x 2∗ ) > fнецелочисленноенецелочисленное2∗1∗xj ≤[ ][ ]x 1j∗ЗЛП-3x , f ( x 3∗ ) < f3∗нецелочисленноеx j ≥ x 1j ∗ + 1xi ≤[x ]2∗iЗЛП-4x , f (x 4∗ ) = fЗЛП-5x , f ( x 5∗ ) < fцелочисленноенецелочисленное4∗Рис.

2615∗[ ]x i ≥ x i2∗ + 1ЗЛП-6X =∅[ ]≤ [x ] ,Для формирования дополнительных ограничений выделяется целая часть x k0∗x k0∗ . Дополнительные ограничения имеют видзначения координаты[ ]xk0∗kx k ≥ x k0∗ + 1 .Задачи ЗЛП-1 и ЗЛП-2 записываются в следующем виде:ЗЛП-1ЗЛП-2nnf ( x) = ∑ c j x j → max ,f ( x) = ∑ c j x j → max ,j =1n∑ aij x jj =1j =1n∑ aij x j≤ bi , i = 1, … , m ,j =1[ ]≤ bi , i = 1, … , m ,[ ]x k ≤ x k0∗ ,x k ≥ x k0∗ + 1 ,x j ≥ 0 , j = 1, … , n ;x j ≥ 0 , j = 1, … , n .Формирование дополнительных ограничений позволило исключить из рассмотрения оптимальное нецелочисленное решение x 0∗ и обеспечить целочисленность значенийкоординаты x k .Задачи ЗЛП-1 и ЗЛП-2 решаются самостоятельно симплекс-методом без учета требований на целочисленность значений координат x j , j = 1, … , n .

Вычисляются значенияфункции f ( x) на оптимальных решениях обеих задач. Если ни одна из них не имеет целочисленного решения, то выбирается задача для приоритетного дальнейшего ветвленияпо установленному правилу: например приоритетному ветвлению подлежит та задача, вкоторой значение f ( x ) на оптимальном нецелочисленном решении максимально. Допус-( ) ( )тим, что f x 1∗ > f x 2∗ и задача ЗЛП-1 первой ветвится на ЗЛП-3 и ЗЛП-4, которые решаются симплекс-методом без учета требований на целочисленность с последующиманализом решений. Если ни одна из задач ЗЛП-3 и ЗЛП-4 не имеет целочисленного решения, приступают к ветвлению задачи ЗЛП-2.Процесс ветвления продолжается до тех пор, пока не будет получено в одной изветвей целочисленное решение. Пусть задача ЗЛП-4 (рис.