WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 |
Министерство образования РФ Дальневосточный государственный университет Задача линейного программирования Методические указания по курсу "Методы оптимизации" Владивосток 2003 2 УДК 519.6 Методические указания предназначены для самостоятельной работы студентов 3 и 4 курсов, изучающих дисциплину "Методы оптимизации". В них изложены основные теоретические сведения по линейному программированию, детально разобраны задачи, приведены образцы задач, предлагавшихся на экзаменах в контрольных работах Подготовлено кафедрой процессов управления.

Составитель Горячев Л.В.

Печатается по решениюметодического совета ДВГУ.

© Дальневосточный государственный университет 2003 3 Задача линейного программирования (ЛП) является наиболее простой среди экстремальных задач с ограничениями. Студент, прослушавший курс "Методы оптимизации", должен хорошо знать свойства таких задач и уверенно владеть методами численного решения.

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

Общие свойства ЛП К рассмотрениютемы "Линейное программирование"мы приступаем после знакомства с общей теорией задач выпуклого программирования. поэтому предполагается, что теорема Куна-Таккера и свойства пары двойственных задач выпуклого программирования студентам известны, нам остается лишь кратко напомнить основные свойства задач линейного программирования, доказательства которых легко вытекают из общей теории.

Задача ЛП в достаточно общем виде может быть записана так:

(c, x) - max Ax = b где c =(c1, c2,..., cn)T — мерный вектор-столбец коэффициетов x =(x1, x2,..., xn)T — мерный вектор-столбец неизвестных A =(aij), m n — матрица коэффициентов B =(b1, b2,..., bm) — вектор-столбец коэффициентов Однако при решении удобно пользоваться канонической формой задачи:

(c, x) - max (1) Ax = b (2) x 0 (3) где A =(aij) — (m n)–матрица коэффициентов, m

В этом случае мы имеем дело с неотрицательными решениями системы уравнений.

Любая задача ЛП с помощью элементарных преобразований может быть приведена к каноническому виду.

Рассмотрим задачу ЛП в следующем виде:

(c, x) - max (4) Ax b – ограничеия-неравенства (5) x 0 – ограничения неотрицательности (6) Задачу (4)–(6) можно рассматривать как задачу выпуклого программирования, то есть целевая функция является выпуклой, а многогранное множество допустимых планов выпукло.

Согласно общей теории задача (4)–(6) может быть записана с помощьюфункций Лагранжа max min [(c, x) +(y, b - Ax)] x0 yдвойственная к ней имеет вид min max (y, b) +(c - AT y, x) y0 xВ эквивалентной форме мы можем записать (y, b) - min (7) AT y c (8) y 0 (9) Задача (7)–(9) называется двойственной (сопряженной) к задаче (4)–(6), обе они образуют пару двойственных или сопряженных задач в симметричной форме.

Другая пара двойственных задач в симметричной форме может быть получена аналогично.

прямая двойственная (c, x) - min (b, y) - max Ax b AT y c x 0 y Двойственнуюзадачу к задаче линейного программирования также легко вывести с помощьюфункции Лагранжа.

(c, x) - max (b, y) - min Ax = b AT y c x Каждой задаче ЛП в произвольной форме можно поставить в соответствие двойственнуюзадачу, руководствуясь следующими, достаточно общими правилами:

1. Каждому i – му ограничению типа неравенства или равенства соответствует переменная yj двойственной задачи и, наоборот, каждому j – му ограничениютипа равенства или неравенства двойственной задачи соответствует переменная xj прямой задачи.

2. Матрица коэффициентов A при переходе к двойственной задаче транспонируется, то есть строка коэффициентов (a1j, a2j,..., amj) в j – м ограничении двойственной задачи при переменных y1, y2,..., ym есть столбец коэффициентов при xj в ограничениях задачи.

3. Свободные члены ограничений одной из задач являются коэффициентами при соответствующих переменных в целевой функции другой задачи. При этом максимизация (минимизация) меняется на минимизацию(максимизацию).

4. В исходной (прямой) задаче ограничения–неравенства следует записать со знаком ”” при максимизации и со знаком ”” при минимизации.

5. Каждому j – му ограничению-неравенству исходной задачи, записанному в соответствии с пунктом 4, отвечает в двойственной задаче условие неотрицательности yi 0, а равенству — переменная yi без ограничений на знак, то есть произвольная. Наоборот, ограничениюнеотрицательности на xj – юпеременнуюсоответствует в двойственной задаче j – е ограничениенеравенство, а произвольной по знаку переменной xj равенство.

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

x1 -2x2 +x3 -x4 +x5 - min x1 -2x2 -x3 +3x4 -2x5 =2x1 +3x2 -2x3 -x4 +x5 x1 +3x3 -4x5 x1 0 x3 0 x5 Решение. Прежде чем уступить к построениюдвойственной задачи с помощьюэлементарных преобразований в соответствии со сформулированными правилами, приведем задачу к виду x1 -2x2 +x3 -x4 +x5 - min x1 -2x2 -x3 +3x4 -2x5 =-2x1 -3x2 +2x3 +x4 -x5 -x1 +3x3 -4x5 x1 0 x3 0 x5 В таком виде наша задача отличается от задачи (7)–(9) ограничением-равенством и отсутствием ограничения на знак переменных x2 и x4. Согласно правилам записи двойственная задача принимает вид:

6y1 -4y2 +7y3 - max y1 -2y2 +y3 -2y1 -3y2 = -y1 +2y2 +3y3 3y1 +y2 = -2y1 -y2 -4y3 y2 0 y3 Условия неотрицательности y2 и y3 наложены так, как им отвечают в исходной задаче ограничениянеравенства, а второе и четвертое ограничения имеют вид равенства, так как соответствующие им переменные x2, x3 не ограничены по знаку.



Упражнения. Составить двойственные к следующим задачам:

1. -x1 +x2 +x3-max 2. 2x1+4x2+x3- min x1-3x2 +x34 x1-2x2+x3 2x1 +x2-2x31 2x1+3x2-x3 x2 0 x3 0 x1 0 x3 Каждая пара двойственных задач обладает рядом интересных свойств. В частности, если рассмотреть пару двойственных задач в симметричной форме, например, задачи (4)–(6), и (7)–(9), то относительно их можно сформулировать следующие утверждения:

1. Для любых допустимых планов x и y прямой и двойственной задач соответственно выполняется неравенство (c, x) (y, b) Доказательство: (c, x) (AT y, x) =(y, Ax) (y, b).

2. Если x и y — планы прямой и двойственной задачи соответственно и (c, x) = (y, b), то x = y — оптимальные планы этих задач.

Доказательство следует из предыдущего утверждения, так как (c, x) (c, x) =(y, b) (y, b).

3. Если линейная форма одной пары двойственных задач неограничена, то множество планов других пусто.

Доказательство: Пусть для определенности линейная форма задачи (7)–(9) неограниченна снизу, тогда существует последовательность планов {yi} такая, что lim(yk, b) =-. Учитывая утверждения, заключаем, что прямая задача не имеет ни одного конкретного плана.

4. Если разрешима одна из пары двойственных задач, то разрешима и другая, при этом значения линейных форм задач на оптимальных планах совпадают.

Доказательство: Опять рассмотрим пару двойственных задач в симметричной форме (4)–(6), и (7)–(9).

Пусть x — оптимальный план прямой задачи. Тогда в mx согласно уже известной теореме Куна-Таккера, существуют такие вектора 0, v 0, что m n c = aT i - vjej =(1, 2,..., m)T () i i=1 j=(, b - Ax) =0 e =(e1, e2,..., en)T (v, x) =0 v =(v1, v2,..., vn)T ai =(ai1, ai2,..., ain) учитывая, что v 0, имеем AT 0, то есть вектор удовлетворяет условиям двойственной задачи. С другой стороны, умножая () на x скалярно, будем иметь (c, x) = (AT, x) = (v, x) =(, b). Таким образом, y есть оптимальный план двойственной задачи.

Это утверждение вместе с пунктом 3 составляют первую теорему двойственности.

Каждому k – му ограничениютипа неравенства одной из пары двойственных задач отвечает ограничение на знак соответствующей переменной другой задачи и наоборот. Эти пары условий называются сопряженными. Так, для вышеупомянутой пары двойственных задач пару условий ak1x1 + ak2x2 + · · · + aknbn bk и yk 0; xl 0 и a1ly1 + a2ly2 + · · · + amlym cl будут сопряженными.

5. Если в каждой паре сопряженных условий на оптимальных планах одно условие свободное, то другое — закрепленное.

Доказательство непосредственно вытекает из условий дополняющей нежесткости теоремы Куна-Таккера.

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

Наконец, локализовать точки экстремума линейной формы в задаче ЛП позволяет следующая теорема:

Если задача линейного программирования разрешима, то всегда найдется крайняя точка многогранного множества допустимых планов, в которой достигается экстремум линейной формы.

Доказательство этой теоремы в лекциях получено как следствие свойств выпуклой функции, заданной на многогранном множестве.

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

Рассмотрим задачу ЛП в каноническом виде.

(c, x) - max (10) Ax = b (11) x 0 (12) Задача имеет m+n ограничений, среди них m ограничений типа равенства и n ограничений неотрицательности. По определениюкрайняя точка удовлетворяет n линейно-независимым ограничениям задачи как точным равенствам.

Определение: План x = (x1, x2,..., xn) называется опорным, если среди ограничений задачи, которым он удовлетворяет как точным равенствам, имеется n линейно-независимых.

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

Применительно к задаче ЛП в каноническом виде понятие опорного плана можно модифицировать.

Среди n ограничений, обращаемых в равенства опорным планом, m будут обязательных (11) и остальные m - n ограничений на (13) обратятся в точные равенства на опорном плане. Без ущерба для общности изложения допустим, что имеем невырожденный опорный план, который обращает в точные равенства последние m - n ограничения неотрицательности (13). Тогда этому опорному плану отвечает система линейных уравнений с матрицей коэффициентов, составленных из первых m столбцов матрицы A и неизвестными x1, x2,..., xm. Очевидно, что любому невырожденному плану задачи ЛП канонического вида можно поставить в соответствие m линейно-независимых векторов столбцов матрицы A называемых базисом этого плана. Верно и обратное, любой совокупности m линейно-независимых векторов-столбцов матрицы A, которой отвечает неотрицательное решение системы линейных уравнений, построенной на этих столбцах, отвечает опорный план задачи. Легко видеть, что невырожденный опорный план содержит m положительных компонент. Вырожденный опорный план обращает в точные равенства более, чем n ограничений задачи; он имеет не менее, чем m положительных компонент. Геометрически вырожденность опорного плана означает, что через вершину проходит более, чем n гиперплоскостей. Таким образом, вырожденному опорному плану может отвечать несколько базисов.





Из сказанного следует, что переход от одной вершины к другой равносилен переходу от одного базиса к другому. Сформулируем правила этого перехода.

Итак, пусть мы имеем задачу ЛП канонического вида (10)–(13) и пусть известен ее опорный план x =(x, x,..., x ). Не ограничивая общности рассуждений, положим, что он не вырожден 1 2 n и базис его состоит из первых m векторов-столбцов матрицы A. Тогда имеем, что xA1 + xA2 + · · · + x Am = b (13) 1 2 m x = x = · · · = x =m+1 m+2 n Обозначим через B =(A1, A2,..., Am), тогда из (14) n x =(x, x,..., x ) =B-1b - B-1Aj x 1 2 m j j=m+Введем обозначения x1j x2j xj = B-1Aj =.

.

.

xmj Легко видеть, что xj — вектор коэффициентов разложения вектора Aj по векторам базиса A1, A2,..., Am.

При этих обозначениях n x = B-1b - Xj x, x =0, j = m +1,..., n (14) j j j=m+Допустим, что мы переходим к другому опорному плану, который отличается от нашего тем, что одна из базисных компонент замещена переменной xk (k >m). Это означает, что один из векторов базисного плана x заменяется на вектор Ak. Тогда из () мы получаем X = B-1b = B-1Ak (15), где — значение xk, которое мы должны определить. Покомпонентно равенство (15) запишется так:

x1 = x - x1k x2 = x - x2k.

.

(16).

xm = x - xmk m xk =, > Все оставшиеся xj =0, j =1, 2,..., l - 1, l +1,..., m, j = k.

Для того, чтобы план (16) был опорным, необходимо, чтобы общее число ненулевых компонент было равно m (меньше m в случае вырожденности нового опорного плана). Очевидно, что должно удовлетворять условиям xi = x - xik 0, i =1, 2,..., m i xk => Из этих условий с очевидностью вытекает, что для = 0 = min(xi/xik), при xik > 0 одна из i компонент плана (16) обратится в нуль, ее заменит xk =. Если min достигается только для одного i, то новый опорный план также невырожден, в противном случае будем иметь вырожденный опорный план. Если положить для определенности, что min достигается на i = l, то, очевидно, формулы изменения компонент опорного плана при переходе от A1, A2,..., Al-1, Al, Al+1,..., Am к базису A1, A2,..., Al, Ak, Al+1,..., Am имеют вид x l xi = x - xik i xlk x l x = k xlk При переходе к новому базису изменяются и коэффициенты разложения вектора Aj по векторам базиса. Как это происходит, видно из следующих тривиальных преобразований. Для нашего случая при базисе, состоящем из первых m векторов, имеем Aj = x1jA1 + x2jA2 + · · · + xljAl + · · · + xmjAm (17) в том числе для j = k Ak = x1kA1 + x2kA2 + · · · + xlkAl + · · · + xmkAm. Отсю да Al = (Ak - xikAi) xlk i=l и подставляя в (17), получаем разложение Aj по векторам нового базиса A1,..., Al-1, Ak, Al+1,..., Am.

xlj xlj xlj Aj =(xij - )A1 + · · · + Ak + · · · +(xmj - )Am xlk xlk xlk Таким образом, формулы пересчета коэффициентов разложения имеют вид xlj x = xij - xij, i = k ij xlk xlj xkj = xlk Здесь штрих обозначает компоненты нового вектора коэффициентов разложения вектор-столбца Aj. Замена одного базисного вектора Al на другой вектор геометрически означает переход от одной крайней точки (вершины) к другой. Однако, такой переход должен быть направленным, то есть должен вести к уменьшению линейной формы. Рассмотрим, как осуществить выбор вектора Ak, включаемого в базис, чтобы это привело к уменьшению значения целевой функции.

Для этого достаточно проследить, как изменяется значение линейной формы при смене базиса.

Используя формулы перехода от одного опорного плана к другому, можно легко получить, что на новом опорном плане x (c, x ) =(c, x) - 0(c0, xk) +0ck =(c, x) - 0(zk - ck) m где zk = cixik =(c0, xk). Вообще говоря, 0 зависит от индекса k, пренебрегая этой зависимоi=стью, мы видим, что в базис необходимо вводить вектор Ak, для которого zk - ck = max(zj - cj), zj - cj > 0 (18) j Вообще говоря, в базис можно вводить и любой другой вектор Aj, для которого zj - cj > 0, но при таком выборе значение линейной формы уменьшается наиболее быстро.

Правило выбора вектора al, замещаемого в базисе вектором Ak, мы уже вывели: l определяется индексом i, на котором достигается x x i l min = =i xik xlk Если min достигается для нескольких l, то можно взять за l любое из них.

Из (18) с очевидностьювытекает признак оптимальности опорного плана.

Теорема: Если для некоторого опорного плана x = (x, x,..., x ) справедливо zj - cj 0, 1 2 n j = 1, n, то x — оптимальный опорный план.

Доказательство теоремы дается в лекциях. Нетрудно показать при решении задачи канонического вида на максимум, критерием оптимальности будут условия zj - cj 0, j = 1, n.

При решении практической задачи, как правило, заранее неизвестно разрешима она или нет.

Это может быть обнаружено в ходе решения. В симплекс-методе достаточно просто может быть обнаружена неограниченность линейной формы на множестве допустимых планов. Из условия (7) вытекает, если для данного вектора Ap : zp - cp > 0 и всех xip 0, то величина сверху неограничена. При любом > 0 вектор X с отличными от нуля компонентами, вычисляемыми по (8), будет планом. Тогда значение линейной формы на этом плане будет (c, x) =(c, x) - (zp - cp) откуда с очевидностьюследует, что (c, x) при. Таким образом, если среди внебазисных векторов Aj, для которых j = zj - cj > 0, найдется вектор, для которого вектор коэффициентов разложения xj неположителен, то линейная форма задачи (10)–(13) неограниченна сверху.

Pages:     || 2 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.