Глава 2. Линейные оптимизационные задачи и методы их решения

Если целевая функция (1.1) и система ограничений (1.2) являются линейно зависимыми от переменных х_1} х₂,... х_п, для решения оптимизационной задачи используются методы линейного программирования.

Линейная математическая модель в общем случае имеет следующий вид:

Z = z₁x₁ +z₂x₂+...+z_nx_n extr,

a₁₁x₁+a₁₂x₂+...+a_1nx_n < b₁,

a21X1+a22X2+...+a2nXn = b₂,

(2.1)

am1x1+a_ra2x2+.. .+^amn^xn > ^bm,

Xi > 0, i = 1, 2,... n,

Поскольку количество изделий любого вида не может быть отрицательным числом, граничными условиями будут

неотрицательные значения искомых переменных

x > 0, i = 1, 2, 3. (1.6)

Выражения (1.4), (1.5) и (1.6) представляют собой

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

Выражения (1.4) и (1.5) являются линейно зависимыми от искомых переменных х_г-, следовательно, рассматриваемая

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

Линейная математическая модель в общем случае имеет следующий вид:

где z, bj, aj_i - заданные постоянные величины, i = 1.2,...n; j = 1, 2,... m.

Задача линейного программирования формулируется следующим образом: найти экстремальное значение линейной целевой функции Z при ограничениях, заданных в форме линейных равенств и (или) неравенств, и граничных условиях, указывающих диапазон изменения переменных.

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

Допустим, что в линейной математической модели (2.1) ищется минимум целевой функции

Z = z₁x₁+z₂x₂+...+z_nx_n min.

Если по этой же математической модели нужно найти максимум целевой функции Z, то у коэффициентов целевой функции меняются знаки на противоположные и вновь ищется минимум функции Z

Z = - z₁x₁ - z₂x₂ z_nx_n min.

Таким образом, min (- ziXi- z₂x₂ z_nx_n) = max (Z1X1+ z₂x₂+...+ z_nx_n).

Этот метод является достаточно простым, наглядным и позволяет сделать некоторые общие выводы по решению оптимизационных задач методами линейного программирования. Однако применение графического метода ограничено задачами относительно небольшой размерности.

Рассмотрим математическую модель линейной оптимизационной задачи, в которой требуется найти минимум целевой функции

Z = z₁x₁+z₂x₂ ^ min,

при ограничениях a_nx1+a12x₂ < b_h «21x1+^22x2 < b2,

«31x1+^32x2 < Ьз, и граничных условиях неотрицательности переменных

Xi > 0, i = 1, 2.

После введения дополнительных переменных х₃, х₄, х₅ перейдем от ограничений-неравенств к равенствам

«₁₁x₁+«₁₂x₂ + х₃ = b₁,

«21x1+«22x2 + X4 = b2, (2.2)

«₃₁x₁+«₃₂x₂ + х₅ = b₃.

Отметим, что граничные условия неотрицательности переменных распространяются и на дополнительные переменные:

x_i >0, i = 3, 4, 5.

Отложим по горизонтальной оси значения переменной х₁, а по вертикальной оси - значения переменной х₂ (рис. 2.2.1). Учитывая граничные условия (х₁>0, x₂>0), штриховкой выделим полуплоскости допустимых значений переменных х₁ и х₂ (вправо от оси х 2 и вверх от оси х 1).

Рассмотрим одно из ограничений-равенств, например, первое

a₁₁x₁+a₁₂x₂ + х₃ = b₁ и перепишем его в виде

х₃ = - a₁₁x₁ - a₁₂x₂ + b₁.

Приравняем переменную х₃ к нулю

х₃ = a₁₁x₁ + a₁₂x₂ - b₁ = 0.

Последнее соотношение представляет собой уравнение прямой линии в плоскости х₁х₂. На этой прямой значение х₃=0.

Следовательно, по одну сторону от этой прямой х₃>0, по другую х₃<0. Учитывая граничное условие х₃>0, штриховкой выделим

полуплоскость, в которой х₃>0.

Рис. 2.1 Иллюстрация графического решения задачи

Аналогичные графические построения выполним для второго и третьего ограничений системы (2.2).

В результате выполненных графических построений на плоскости х₁х₂ выделится область Q допустимых значений переменных х₁, х₂, х₃, х₄, х₅ (рис. 2.1). Эта область представляет собой выпуклый многогранник abcde. Все допустимые решения задачи, в том числе и оптимальное решение, будут принадлежать области Q.

Z = Z\Xi+Z₂X2 = 0.

В плоскости х₁х₂ это уравнение прямой линии, проходящей через начало координат (рис. 2.1).

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

Z = z₁x₁ +z₂x₂ = 1

и построим в плоскости х₁х₂ соответствующую прямую (рис. 2.1).

Прямые Z=const являются линиями равного уровня целевой функции, поскольку на каждой такой линии значение целевой функции неизменно. Линии равного уровня параллельны между собой.

По взаимному расположению линий равного уровня Z=0 и Z=1 определим направление возрастания целевой функции Z. Это направление указано на рис. 2.1 стрелкой.

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

В соответствии с графическими построениями такой точкой будет вершина е многогранника Q (рис. 2.1). Эта вершина и будет соответствовать минимуму целевой функции, т.е. оптимальному решению задачи.

Минимальное значение целевой функции Z достигается при следующих значениях переменных:

х₂>0, х₃>0, х₄>0, х₁=0, х₅=0.

Три переменные отличаются от нуля, две переменные равны нулю. Видно, что количество не равных нулю переменных равно количеству ограничений. Остальные переменные равны нулю.

Пусть в рассмотренной выше линейной задаче требуется найти максимум целевой функции Z. Как было отмечено выше, в этом случае ищется минимум целевой функции с измененными знаками коэффициентов z,

Z = - z₁x₁ - z₂x₂ ^ min.

Ограничения и граничные условия при этом не меняются.

На рис. 2.2 выполнено графическое решение задачи. Из построения прямых

Z = - z₁x₁ - z₂x₂ = 0 и Z = - z\X\ - z₂x₂ = 1 или Z = z₁x₁ + z₂x₂ = -1

видно, что изменение знаков коэффициентов z₁ и z₂ обусловило изменение направления возрастания целевой функции на противоположное (см. стрелку на рис. 2.2). Очевидно, что в этом случае минимуму целевой функции отвечает вершина b многогранника Q.

Таким образом, задачи минимизации и максимизации целевой функции решаются совершенно одинаково. Следует только иметь в виду, что

min (- z₁x₁ - z₂x₂ -...- znXn) = max (z₁x₁+ z₂x₂ +...+ z_nx_n).

Рис. 2.2 Определение максимума целевой функции

На основании выполненного графического решения задачи линейного программирования можно сделать следующие общие выводы по решению линейной оптимизационной задачи:

оптимальное решение задачи всегда находится в одной из вершин многогранника Q, поэтому для отыскания оптимального решения достаточно рассмотреть только конечное количество решений, лежащих в вершинах многогранника Q, и не рассматривать бесконечное количество решений, лежащих на гранях и внутри этого многогранника;

в каждом решении, отвечающем одной из вершин многогранника Q, количество положительных (не равных нулю) переменных равно количеству ограничений m, остальные (n-m) переменные равны нулю;

для отыскания оптимального решения следует рассмотреть только те решения, в которых содержится m переменных, не равных нулю, и (n-m) переменных, равных нулю.

В дальнейшем отличные от нуля положительные переменные будем называть базисными, нулевые переменные - свободными. В каждом рассматриваемом решении количество базисных переменных равняется количеству ограничений m, а количество свободных переменных равняется (n-m).

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

Рассмотрим, как преобразуется исходная система ограничений- равенств в математической модели (2.2) при переходе от одного решения к другому, т.е. при переводе одной из свободных переменных в разряд базисных, а одной из базисных переменных в разряд свободных. Перепишем систему (2.2):

Начальный выбор свободных и базисных переменных может быть произвольным. Однако структура системы (2.3) такова, что в качестве базисных переменных удобно принять переменные х₃, х₄ и х₅, а в качестве свободных - переменные х₁ и х₂. В этом случае сразу же получаем некоторое исходное решение системы (2.3):

свободные переменные х₁=0, х^=0;

базисные переменные х₃=Ь₁, х₄=Ь₂, х₅=Ь₃.

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

Запишем исходную систему (2.3) в более подробном виде, а базисные переменные и коэффициенты при них выделим жирным шрифтом

Допустим, что свободную переменную х ₁ следует перевести в разряд базисных, а базисную переменную х₃ - в разряд свободных. Эта процедура достаточно проста и неоднократно использовалась при решении систем линейных уравнений в школьном курсе алгебры.

Суть процедуры заключается в следующем: из первого уравнения системы выражается переменная х 1 и подставляется во второе и третье уравнения системы. В результате такого преобразования свободная переменная х 1 становится базисной, а базисная переменная х 3 становится свободной.

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

Поделив первое уравнение на разрешающий коэффициент, получим

Выразим из этого уравнения переменную х 1

Подставляя значение х 1 во второе и третье уравнения системы (2.4), после несложных преобразований получим совместно с уравнением (2.5) новую преобразованную систему уравнений

Коэффициенты преобразованной системы (2.6) пометим штрихом и запи ш ем эту систему в более простом виде

В этой системе свободными будут переменные х₂ и х₃, а базисными - переменные Xi, х₄ и х₅. Новое решение

свободные переменные х₂=0, х₃=0; базисные переменные х₁=Ь’₁, х₄=Ь’₂, х₅=Ь’₃.

Переменная х₁ стала базисной, а переменная х₃ - свободной. В системах (2.6) и (2.7) базисные переменные и коэффициенты при них выделены жирным шрифтом.

Анализ систем (2.6) и (2.7) позволяет сформулировать три правила пересчета коэффициентов при переводе одной из базисных переменных в разряд свободных, а одной из свободных переменных в разряд базисных:

2. Все коэффициенты, не принадлежащие разрешающей строке и разрешающему столбцу, пересчитываются по выражению

a_ij ' = a_ij - aj_r a_ri /an-, (2.8)

где aij - коэффициент, лежащий на пересечении i-й строки и j-го столбца;

aij' - новое пересчитанное значение коэффициента aij; a rr - разрешающий коэффициент;

a_ir - коэфффициент, лежащий на пересечении i-й строки и разрешающего столбца;

а- - коэфффициент, лежащий на пересечении разрешающей строки и j -го столбца.

3. Все коэффициенты разрешающей строки делятся на разрешающий коэффициент ап-. Разрешающий коэффициент при этом становится равным единице a_rr=1.

4. Все коэффициенты разрешающего столбца, кроме

разрешающего коэффициента, заменяются нулями.

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

При решении реальных оптимизационных задач удобно пользоваться табличной формой записи систем уравнений. Запишем исходную систему (2.4) в виде табл. 2.1, выделив разрешающие строку и столбец.

Пересчитав по правилам 1, 2 и 3 коэффициенты этой таблицы, получим новую таблицу 2.2, отвечающую преобразованной системе (2.7).

В таблицах 2.1 и 2.2 базисные переменные и коэффициенты при них выделены жирным шрифтом.

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

Симплекс - понятие геометрическое, означающее совокупность вершин многомерного тела. Идея симплекс-метода заключается в последовательном переборе решений - в последовательном переходом от одной вершины к другой. Однако этот перебор не хаотичный, а таков, что на каждом шаге решение улучшается [4].

Метод состоит из двух этапов: на первом этапе ищется допустимое решение; на втором этапе это допустимое решение улучшается до оптимального.

Алгоритм метода рассмотрим на примере линейной модели п.2.1, где требуется найти минимум целевой функции

Z = z₁x₁+z₂x₂ ^ min, (2.9)

при ограничениях-равенствах

и граничных условиях неотрицательности переменных

Перейдем к табличной форме записи. В отличие от табл. 2.1 в исходную таблицу введем строку целевой функции (нижняя строка табл. 2.3).

Исходное решение:

х₁=0, х₂=0, x₃=b_1} x₄=b₂, x₅=b₃. (2.12)

В соответствии с выражением (2.9) исходное значение целевой функции Z=0.

1 этап. Получение допустимого решения. Любое допустимое решение должно удовлетворять системе ограничений-равенств и граничным условиям.

Исходное решение (2.12) удовлетворяет системе ограничений- равенств (2.10). Это решение будет удовлетворять граничным

условиям (2.11) в том случае, когда свободные члены b₁>0, b ₂ 0 и Ьз>0. Следовательно, условием получения допустимого решения

является неотрицательность свободных членов ограничений- равенств.

Если все bj>0 (j=1,2,...m), то полученное решение является допустимым. Далее осуществляется переход ко 2-му этапу метода.

Если среди свободных членов есть отрицательные, то выбирается любой из них и соответствующая строка принимается в качестве разрешающей. Базисная переменная, отвечающая разрешающей строке, будет переводиться в разряд свободных.

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

Свободная переменная, соответствующая разрешающему

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

Выполняется пересчет всех коэффициентов табл. 2.3 по правилам 1, 2 и 3 п. 2.2. Пересчету подвергаются и коэффициенты z_i (i=1,2,...n) целевой функции и значение целевой функции, которое находится в правом нижнем углу табл. 2.3. В силу принятой формы записи таблицы значение целевой функции получается с обратным знаком. Поэтому в соответствующей ячейке табл. 2.3 стоит величина -Z.

Разрешающая строка выбрана по отрицательному коэффициенту Ь<0. Разрешающий столбец выбран по отрицательному коэффициенту a_ji<0, который и является разрешающим коэффициентом а^. В результате пересчета коэффициентов табл. 2.3 в соответствии с правилом 2 п.2.2 (b/=bj /а„) новый свободный член Ь/ сменит знак и станет положительным.

Вычислительная процедура, т. е. выбор разрешающих строки, столбца и пересчет всех коэффициентов табл. 2.3, продолжается до выполнения условия bj>0, j=1,2,...m, при котором полученное

решение будет допустимым.

Предположим, что допустимому решению соответствует табл. 2.4. Переменные х_1; х₄ и х₅ базисные, а переменные х₂ и х₃ свободные. Допустимое решение: (2.13)

Напомним, что значение целевой функции в правом нижнем углу табл. 2.4 имеет обратный знак.

2 этап. Получение оптимального решения. Пусть оптимальному решению соответствует минимальное значение целевой функции Z. Необходимо проверить возможность улучшения полученного на первом этапе допустимого решения, то есть проверить возможность уменьшения значения целевой функции Z.

Перевод свободной переменной в базис соответствует увеличению этой переменной от нуля до некоторого положительного значения. Просмотрим коэффициенты строки целевой функции (нижней строки табл. 2.4). Очевидно, что перевод любой из свободных переменных (х₂ или х₃) в базис приведет к уменьшению целевой функции, если коэффициент при этой переменной будет отрицательным (z₂'<0 или z₃'<0). Если коэффициенты z₂'>0 и z₃'>0, перевод любой из свободных переменных (х₂ или х₃) в базис приведет к увеличению целевой функции.

Следовательно, условием получения оптимального решения при минимизации целевой функции является неотрицательность коэффициентов целевой функции z_i'>0.

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

Допустим, что коэффициент z₃'<0. Свободную переменную х₃ будем переводить в базис, а третий столбец табл. 2.3 будет разрешающим.

Для выбора разрешающей строки рассмотрим систему ограничений-равенств, соответствующую допустимому решению

Переменная х₂ свободная (х₂=0). С учетом этого перепишем систему (2.14) в более простом виде

При переводе переменной х₃ в базис (при увеличении этой переменной от нуля в положительную сторону) базисные переменные хь х₄ и х₅ будут изменяться в соответствии с равенствами (2.15). Если коэффициенты разрешающего столбца а₁₃’>0, а₂з>0 и а_зз>0, базисные переменные будут уменьшаться. При каком-то положительном значении переменной х_з одна из базисных переменных первой достигнет нуля и станет свободной.

Если есть отрицательные коэффициенты, например, а_2з'<0, то соответствующая базисная переменная х 4 будет увеличиваться и в разряд свободных не перейдет. Поэтому в разрешающем столбце принимаются во внимание только положительные коэффициенты а^.

Допустим, что коэффициенты а_1з>0 и а_зз’>0. Базисная переменная х₁ достигнет нуля при значении х_з=Ь₁'/а_1з'. Базисная переменная х_з достигнет нуля при значении х_з=Ь_з 7а_ззОчевидно, что из двух базисных переменных х 1 и х 5 первой достигнет нуля и станет свободной та переменная, для которой отношение Ь//а//=шт.

Для выбора разрешающей строки вычисляются все положительные отношения Ь//а/. Строка, отвечающая наименьшему из этих отношений Ь//а//=шт, принимается в качестве разрешающей. Базисная переменная, соответствующая разрешающей строке, будет переводиться в разряд свободных.

Разрешающий коэффициент находится на пересечении разрешающей строки и разрешающего столбца.

Выполняется пересчет всех коэффициентов табл. 2.4 по правилам 1, 2 и з п. 2.2.

Вычислительная процедура, т.е. выбор разрешающих строки, столбца и пересчет всех коэффициентов, продолжается до выполнения условия z_i>0, i=1,2,...n, при котором полученное решение будет оптимальным (достигнут минимум целевой функции Z).

При поиске максимума целевой функции Z первый этап (поиск допустимого решения) выполняется совершенно аналогично. На втором этапе условием получения оптимального решения примаксимизации целевой функции будет неположительность коэффициентов целевой функции z_i' < 0.

Алгоритм симплекс-метода:

2. Система ограничений преобразуется к виду (2.10), удобному для разделения переменных на свободные и базисные.

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

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

5. Просматривается столбец свободных членов bj. Если все ^bj > 0 то решение является допустимым и осуществляется переход к п. 7. Если есть свободные члены bj<0, то выбирается любой из них и соответствующая строка будет разрешающей.

6. Просматриваются коэффициенты aj_i разрешающей строки. Если все эти коэффициенты положительны, задача не имеет решения. Если среди коэффициентов aji разрешающей строки есть отрицательные, то выбирается любой из них и соответствующий столбец будет разрешающим.

7. Выполняется пересчет всех коэффициентов таблицы, включая значение целевой функции, которое имеет противоположный знак. Осуществляется переход к п.4.

8. Просматриваются коэффициенты Zi строки целевой функции. Если все эти коэффициенты z_i < 0 (при поиске минимума Z) или z_i > 0 (при поиске максимума Z), то текущее решение будет оптимальным. Вычислительная процедура заканчивается.

9. Если есть коэффициенты z_i > 0 (при поиске минимума Z) или z_i < 0 (при поиске максимума Z), то выбирается любой из них и соответствующий столбец будет разрешающим. Вычисляются отношения свободных членов bj к положительным коэффициентам а^ разрешающего столбца. Строка, отвечающая минимальному из этих отношений, будет разрешающей.

10. Выполняется пересчет всех коэффициентов таблицы. Осуществляется переход к п. 7.

Поиск по сайту: