6 Задачи линейного программирования (1013406)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Лекция 66. ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ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 ,x1xk 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 .

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций