36220

Теоретические основы линейного программирования. Симплекс-метод. Метод искусственного базиса

Доклад

Математика и математический анализ

Канонической формой задачи ЛП называется такая ее запись при которой 1 целевая функция должна быть минимизирована; 2 все искомые переменные должны быть неотрицательны; 3 все ограничения кроме неотрицательности переменных имеют вид равенства. Оптимальные значения переменных от такой замены не изменятся. 2 Если в исходной задаче на какойто параметр хj не наложено условие неотрицательности то можно сделать замену переменных положив где – новые переменные удовлетворяющие условию неотрицательности. 3 Преобразование неравенств в...

Русский

2013-09-21

93.5 KB

21 чел.

6 Вопрос

Теоретические основы линейного программирования. Симплекс-метод. Метод искусственного базиса.

7.2. Теоретические основы решения задач ЛП

Выпуклые множества

Def.  Пусть a, b  En – две произвольные точки. Отрезком [a, b] называется множество точек с (), определяемое соотношением: с() = a + (1–)b.         0    1.

Def. Множество S называется выпуклым, если a, b  S    [a, b]  S.

Обобщением понятия “отрезок” является понятие выпуклой оболочки.

Def. Пусть имеем k точек a1, … аk  En. Их выпуклой оболочкой называется множество точек, определяемое соотношением:

1a1 +…+kak  En, 0  j , .                                 (6.1)

При фиксированных j выражение (1) называется выпуклой комбинацией (это одна точка). При n = 2, 3 геометрическим образом выпуклой оболочки является, соответственно, многоугольник на плоскости и многогранник в пространстве с k вершинами.

Def. Точка р выпуклого множества S называется угловой, если она не может быть представлена в виде выпуклой комбинации никаких точек из S, отличных от р.

Пример – углы многоугольников на плоскости.

Каноническая форма задачи ЛП. Метод решения задачи ЛП будем излагать в предположении, что она приведена к канонической форме.

Def. Канонической формой задачи ЛП называется такая ее запись, при которой

1) целевая функция должна быть минимизирована;

2) все искомые переменные должны быть неотрицательны;

3) все ограничения (кроме неотрицательности переменных) имеют вид равенства.

Привести произвольную задачу ЛП к канонической форме достаточно просто.

1) Если в исходной задаче целевую функцию q надо максимизировать, то достаточно изменить знак функции, положив q1 = – q  mix. Оптимальные значения переменных от такой замены не изменятся.

2) Если в исходной задаче на какой-то параметр хj не наложено условие неотрицательности, то можно сделать замену переменных, положив , где – новые переменные, удовлетворяющие условию неотрицательности. Тогда при  будет хj  0, а при  будет хj  0.

3) Преобразование неравенств в равенства достигается введением вспомогательных неотрицательных переменных. Если имеем неравенство вида      …  bi, то к левой части неравенства надо прибавить вспомогательную переменную: … + xn+i = bi. Если имеем неравенство вида …  bi, то от левой части неравенства надо отнять вспомогательную переменную: … – xn+i = bi.

Пример 7.2. Имеем задачу: найти максимум q = 2х1 + 3х2 при ограничениях

.

Преобразуем к канонической форме. Положим х1 = у1 – у2;  х2 = у3 – у4. Отсюда

q1 = –2(у1 – у2) – 3(у3 – у4)  min.

.

Базисные решения. Пусть имеем задачу ЛП в канонической форме:

q = c1 x1 + c2 x2 + … + cn xn  min

a11 x1  + a12 x2  + …  + a1n xn = b1

a21 x1  +  a22 x2  + … + a2n xn = b2                                (7.1) 

………………..

  am1 x1 + am2 x2 + … + amn xn = bm . 

Будем предполагать, что rank A = m, где А – матрица системы (7.1). Это возможно только если число уравнений m меньше числа неизвестных n. Тогда система (7.1) имеет бесконечное множество решений. Чтобы выделить из этого множества какое-нибудь определенное решение, надо зафиксировать nm произвольных неизвестных и решить полученную систему относительно m оставшихся.

Def. Будем называть решение системы (7.1) допустимым, если в нем все значения xj неотрицательны, т.е. удовлетворяют ограничению, принятому в канонической форме задачи ЛП.

Особое место среди всех возможных решений системы занимают так называемые базисные решения.

Def. Решение системы (7.1) называется базисным, если в нем nm фиксированных переменных принимают нулевые значения. Если базисное решение является допустимым, но оно называется базисным допустимым.

Таким образом, конкретное базисное решение однозначно определяется выбором его нулевых компонент. Пользуясь сведениями из комбинаторики, несложно определить, что число всех различных базисных решений равно , но, вообще говоря, не все они допустимы. Забегая вперед, скажем, что решением задачи ЛП (оптимальной точкой) является одно из допустимых базисных решений.

Вспомогательные утверждения. Следующие утверждения играют важную роль в теории ЛП.

Лемма 7.1. Если система (7.1) имеет допустимые решения, то она имеет и допустимые базисные решения.

Лемма 7.2. Область D допустимых решений системы (7.1) является выпуклым множеством.

Лемма 7.3. Для того, чтобы точка х  D была угловой, необходимо и достаточно, чтобы ее координаты образовывали базисное допустимое решение системы (7.1).

Основная теорема ЛП. Данная теорема позволяет построить численную процедуру решения задачи ЛП.

Теорема 7.1. Если целевая функция q задачи ЛП имеет конечный минимум, то он достигается в одной из базисных точек.

Доказательство. Пусть система (7.1) имеет k допустимых базисных решений: x1, x2 ,…, xk, в которых целевая функция принимает значения q1, q2,…, qk, соответственно. Пусть x = 1x1 +…+ kxk – любая допустимая не угловая точка. Тогда q(x) = 1q1 +…+ kqk. Пусть q J = min {q j} (если минимум достигается одновременно при нескольких значениях j, выбираем любое из них). Так как при любом j выполняется неравенство q J   q j, то q(x) = 1q1 +…+ kqk      1qJ +…+ kqJ = qJ(1 +…+ k) = qJ. Следовательно, минимум q(x) достигается в точке xJ – базисное решение, в котором q(xJ) = qJ, что и требовалось доказать.

Следствие. При поиске решения задачи ЛП можно ограничиться перебором базисных допустимых точек системы (7.1), т.к. минимум достигается в одной из них.

7.3. Симплекс-метод

Симплекс-метод – численная процедура решения задачи ЛП, разработанная Г. Данцигом в 50-х годах 20 века. Название обусловлено тем, что первые задачи, решаемые этим методом, имели областью D допустимых решений n-мерный симплекс – многогранник с n +1 вершинами. Впоследствии процедура была распространена на общий случай. Рассмотрим простейший вариант метода, не предусматривающий возможности зацикливания, потери точности и других трудностей, встречающихся при решении задач ЛП уже средней сложности.

Алгоритм основан на теореме 7.1 и состоит в целенаправленном переборе базисных решений задачи ЛП. Перебор производится из некоторой начальной допустимой базисной точки и осуществляется так, чтобы значение целевой функции последовательно улучшалось.

Исходные предпосылки. Как и ранее, будем предполагать, что в системе (7.1) n > m = rank A, и, следовательно, в матрице А нет линейно зависимых строк. В противном случае линейно зависимые строки следует исключить из А.

Def.  Параметры из набора x1, x2 ,…, xn, равные 0 в базисном решении, будем называть небазисными переменными, остальные параметры будем называть базисными переменными. Совокупность базисных переменных называется базисом.

Число базисных переменных всегда равно rank А, т.е. m.

Поиск решения начинается в предположении, что система (7.1) разрешена относительно базисных переменных, т.е. если x1, x2 ,…, xm – базисные переменные, то система (7.1) приведена к виду:

x1 =  b1 – (a1m+1 xm+1  + a1m+2 xm+2  + …  + a1n xn )

 x2 =  b2 – (a2m+1 xm+1  + a2m+2 xm+2  + …  + a2n xn )                   (7.5) 

………………..

      xm =  bm – (am m+1 xm+1  + am m+2 xm+2  + …  + am n xn ).

Подставив данные выражения в целевую функцию, получим ее представление:

q = c0 + cm+1 xm+1 + cm+2 xm+2  + …  +  cn xn  min.

Замечание. В (7.5) использованы те же обозначения для коэффициентов, что и в (7.1), хотя в этих выражениях они различаются. Кроме того, обращаем внимание на знак “” перед скобками – в дальнейших выкладках знаки коэффициентов ai j определяются, исходя из его наличия.

Очевидно, базисным решением системы (7.5) является x0 = (b1, b2, …, bm, 0, …, 0)T и q(x0) = c0, которое получается при обнулении всех переменных в правой части. Данное решение будет допустимым, если bi  0 для всех i. Систему (7.5) назовем исходной симплекс-таблицей. На последующих итерациях симплекс-метода осуществляется переход к новым базисным решениям. Для этого надо поменять набор базисных переменных, т.е. положить отличными от 0 другие параметры. Особенность симплекс-метода состоит в том, что такой переход производится заменой только одного параметра. То есть среди небазисных переменных выбирается некоторый параметр хJ, который переводится в базис, а из базиса одновременно с этим выводится  некий параметр хK, чтобы количество базисных переменных не изменилось. Эта особенность метода позволяет сменить базис максимально экономно с точки зрения объема вычислений.

Выбор хJ для перевода в базис. Цель данной операции – выбрать для перевода такой параметр, чтобы в новой базисной точке значение целевой функции улучшилось, т.е. уменьшилось.  В исходной базисной точке x0 все небазисные переменные равны 0. Если параметр хj перевести в базис, то он станет положительным. Следовательно, целевая функция при этом уменьшится, если      сj < 0. Причем, чем сj больше по модулю, тем сильнее будет уменьшение функции.

Выбор хK для вывода из базиса. Пусть хK найден. Чтобы обновить базис надо из К-го уравнения симплекс-таблицы выразить хJ:

.  (7.6)

Выражение (7.6) подставим в остальные уравнения системы (7.5) и целевую функцию. Получим при i = 1,… K – 1, K + 1,…, m:

.    (7.7)

.

Новое базисное решение будет допустимым, если   i. Следовательно, должно быть . Правое неравенство должно выполняться, чтобы свободный член в выражении (7.6) был также неотрицательным. Поскольку в (7.5) bi  0, то должно также быть ai J > 0 для всех i. Все перечисленные требования будут удовлетворены, если номер К выбирать из условия:

.                                (7.8)

Окончание процесса. Предположим, что среди cj нет отрицательных. Значит, перевод в базис любого хj не приведет к уменьшению значения целевой функции. Следовательно, базиса лучше текущего не существует и найдено оптимальное решение задачи.

Условие отсутствия конечного решения. Предположим теперь, что при любом j, таком, что cj < 0, среди ai j нет положительных ни при каком i. Это означает, что из базиса нельзя вывести ни один из базисных параметров. С другой стороны, раз среди cj есть отрицательные, то оптимальный базис не найден. Такая ситуация означает, что конечного оптимального решения не существует, т.е. lin q (x) = – . Так бывает, когда D не ограничена.

7.4. Метод искусственного базиса (М-метод)

Как было сказано выше, для применения симплекс-метода необходимо иметь начальную симплекс-таблицу, т.е. выражение базисных переменных через небазисные. Это просто сделать, если в симплекс-таблице имеется m столбцов, которые образуют диагональную матрицу с положительными диагональными элементами и при этом все bi  0. Не теряя общности, можно считать эту матрицу единичной. Например

    .

В данном примере единичную матрицу образуют 1 и 3 столбцы.

Если такой матрицы нет, то ее достраивают, вводя искусственные переменные, при этом используют следующее правило: если среди ограничений имеем неравенство …  bi и bi  0, или равенство … = bi также при bi  0, то в левую часть этого ограничение добавляем + хn+i , а в целевую функцию добавляем + Мхn+i , где М – произвольное большое число, такое что М >> max | cj |, например, можно положить М = 100 ( max | cj | + 1). Неравенства типа …  bi не требуют добавления искусственных переменных, т.к. их функции могут выполнять вспомогательные переменные, добавляемые при приведении задачи ЛП к канонической форме. Если какие-то bi < 0, то это неравенство следует умножить на – 1.

Так как искусственные переменные  имеют в целевой функции очень большие коэффициенты, то минимум q достигается, когда они равны 0, т.е. после их вывода из базиса.

Пример 7.5. Пусть имеем задачу:

               .

Из последней системы невозможно вывести искусственный параметр x5 ни заменой его на x1 т.к.  достигается при i = 1, ни заменой на x4 т.к. при этом ai j < 0. То есть, при любой замене получим недопустимый базис. Следовательно, задача не имеет допустимого решения.


 

А также другие работы, которые могут Вас заинтересовать

85198. Общественно-политическая жизнь БССР (1945 - 1985 гг.) 27.61 KB
  Хрущевская оттепель ХХ съезд КПСС 1956 с его разобличения культа личности вызвали глубокие изменения в общественнополитического сознания. После ХХ съезд КПСС в Беларуси началась реабилитация жертв сталинских репрессий. Октябрьский 1964 пленум ЦК КПСС избрал первым секретарем партии Л. пленума ЦК КПСС который избрал Ю.
85199. Политика политической и экономической модернизации СССР и БССР в годы перестройки (вторая половина 1980-х гг.) 26.41 KB
  Требовалось реформирование политикоэкономической системы которая в основе своей сформировалась в СССР в 2030е гг. В июне 1987 Верховный Совет СССР принял Закон СССР О государственном предприятии а потом Совет Министров СССР и ЦК КПСС приняли ряд документов о радикальной экономической реформе.
85200. Духовная жизнь и культура Беларуси в 1945-1990 гг 27.2 KB
  Так же в первое послевоенное десятилетие были открыты новее вузы Бел. Значительные сдвиги произошли в развитии бел. Была издана История БССР в 5ти томах и Бел советская Энциклопедия в 12 томах.
85201. Изменения в социально-экономической и политической картине мира в конце XX - начале XXI в. Распад Восточного блока 27.13 KB
  Положив в основу общественного прогресса прежде всего эк. фактор и поставив человека в положение лишь средства для достижения своих целей, Советское гос-во все более отставало от передовых стран мира в научно-технолог. плане, в повышении производит-ти труда. В рез-те общество оказалось скованным жесткими предрассудками...
85202. Распад СССР и оформление государственного суверенитета Республики Беларусь 32.92 KB
  Собственностью республики объявлялись предприятия организации и учреждения союзного подчинения размещенные на ее территории. было принято решение об изменении символики республики и переименовании Белорусской Советской Социалистической Республики в ldquo;Республику Беларусьrdquo; или ldquo;Беларусьrdquo;. в Министерстве юстиции Республики было зарегистрировано 34 пол партии.
85203. Государственные программы развития Республики Беларусь 27.14 KB
  Геополитическое положение Республики Беларусь 1990е 2012 г. Республика Беларусь независимое государство. Республика Беларусь по своему географическому положению находится в центре Европы а также занимает срединную часть Евразийского континента в целом.
85204. Духовная и культурная жизнь белорусского народа (вторая половина 1980-х - 2012 г.) 27.56 KB
  В соответствии с законом правительство приняло программу развития белорусского языка и языков других национальностей, проживающих в республике. Программа расширяла сферы применения белорусского языка в государственных структурах, на производстве, в учебных заведениях.
85205. Основные итоги и уроки исторического пути Беларуси 27.38 KB
  Бел. народ получил возможность с оптимизмом смотреть в будущее и самостоятельно писать свою историю. В своем историческом развитии белорусский народ должен надеяться только на собственные силы. Самым большим богатством Беларуси являются люди трудолюбивые мудрые талантливые рассудительные 3.
85206. Предмет и задачи исторической науки. Формационный и цивилизационный подходы к изучению истории. Источники и литература 29.87 KB
  История – наука комплексная интегральная так как изучает всю совокупность явлений общественной жизни на протяжении всей истории общества. Литература: Всемирная Истрия; история отдельных континентов и стран; история отдельных периодов и эпох; история разных общественных периодов; история выдающихся личностей.