korobov

Очевидное базисное решение этой системы x1=0; х2=3; x3=0; x4=3; x5=0. Отсюда видно, что значения базисных неизвестных получаются при замещении в столбце В. Это решение должно удовлетворять исходной системе (а), в чем легко убедиться, подставив его в систему (а).

Пример 2. Найти все базисные решения системы уравнений

Очевидным базисным решением этой расширенной системы является: x1=0; x2=0; хз=0; v1=l; v2=3, соответствующее единичному базису столбцов матрицы системы (б'). Этому базисному решению соответствует таблица:

Единичную подматрицу, соответствующую искусственным переменным v1, v2, можно в таблицу не включать, так как эти переменные все равно будут вытеснены из базисных неизвестных и заменены истинными переменными.

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

Мы получили второе базисное решение расширенной системы (б'): x1=l, x2=0, хз=0, v1=0, v2=2.

Далее исключаем из базисных неизвестных последнюю искусственную переменную v2 и заменяем ее неизвестной x2. В результате замещения получаем таблицу:

62

При искусственных переменных v1, v2, равных нулю, решения расширенной системы (б') являются решениями исходной системы (б). Поэтому последней таблицей определяется первое базисное решение исходной системы (б): x1= -1, x2=2, хз=0.

Далее мы можем перевести xз в базисные неизвестные и вывести x2 в свободные, пересчитав последнюю таблицу с ключевым элементом 2, отмеченным в таблице рамкой. Новая таблица имеет следующий вид:

Этой таблицей определяется второе базисное решение системы (б): x1=2, x2=0, x3= 1, что легко можно проверить.

Наконец, переводя x2 в базисные неизвестные вместо х1, получаем таблицу,

соответствующую последнему базисному решению системы (б): x1=0, x2=4/3, x3= 1/3. В этом примере все базисные решения содержат значения базисных переменных, отличные от нуля, такие базисные решения называются невырожденными.

Существуют базисные решения, в которых одна или несколько базисных переменных равны нулю; такие базисные решения называются вырожденными. Этот случай нам встретился в первом примере (базисная переменная x3=0).

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

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

63

2.1.10. Опорное решение

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

планами.

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

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

базисных, т. е. во всяком случае не больше, чем Cnr , где п—число неизвестных и r—ранг

системы.

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

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

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

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

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

64

перейти от одного опорного решения не к произвольному базисному решению, а снова к опорному решению (хотя бы даже не к «лучшему»). Для этого достаточно дополнить правила замещения следующим правилом выбора ключевого элемента.

В качестве ключевого столбца (k-го) может быть выбран любой столбец матрицы системы, в котором имеется хотя бы один положительный элемент aik. Выбрав таким

системы к положительным элементам ключевого столбца. Для отрицательных и нулевых элементов ключевого столбца эти отношения не вычисляются (в дополнительном столбце чисел βi>0 делаются прочерки). Все числа βi положительны, так как мы рассматриваем невырожденную задачу.

Та (s-я) строка матрицы, для которой число βi оказывается наименьшим, выбирается в качестве ключевой строки.

Докажем, что при таком выборе ключевого элемента (ask) мы получим снова опорное решение. В формулах (2.1.29) и (2.1.30) для преобразования строк, для столбца

свободных членов следует положить aij=bi; asj=bs и bij=bi' , bsj=bs' , где bi' (i=l,2,..., m) — новые свободные члены. Таким образом, имеем формулы, по которым преобразуются свободные члены:

bi' = bi − aik bs , при i ≠ s

ask

и bi' = bs .

ask

Но по правилу выбора ключевого элемента

следовательно, имеем: bi' = bi − β aik , при i ≠ s

и bs' = β.

Число β>0, так как все числа βi положительны. Если элемент aik в ключевом столбце меньше нуля или равен ему, то соответствующее число bi' ≥ bi > 0, т. е.

положительных aik.

Таким образом, в новом невырожденном базисном решении все базисные

Здесь мы имеем очевидное опорное решение: x1=2, x2=0, x3= 0, x4= 6, x5=4

65

связанное с единичным базисом A1=[1, 0, 0]; A4=[0, I, 0]; A5=[0, 0, I].

Составляем исходную таблицу (матрицу системы) и дополняем ее контрольным столбцом ∑ и столбцом отношений βi>0.

Выберем, например, .столбец коэффициентов при неизвестной xз и запишем в столбце βi, положительные отношения чисел столбца В к числам выбранного столбца (x3). Наименьшее отношение β=2 получается в третьей строке. Поэтому переводим неизвестную xз в базисные вместо x5. Соответствующий ключевой элемент, равный 2, обведен в исходной таблице рамкой. По правилам замещения получаем следующую таблицу:

Из этой таблицы следует второе опорное решение: x1=8, x2=0, x3= 2, x4= 2, x5=0.

2.2.1. Различные формы задач линейного программирования и приведение их к канонической и стандартной формам

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

Требуется найти совокупность неотрицательных чисел х1, х2,…,хn, которые обращают в максимум (минимум) целевую функцию (линейную форму)

66

Задачу (2.2.1) – (2.2.3) при неотрицательности всех чисел хj (xj≥0, j=1,2,…,n) будем

называть общей задачей линейного программирования.

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

Пусть требуется найти неотрицательные числа х1,х2 и число х3 без ограничения по знаку, максимизирующие целевую функцию

z = x1 + 2x2 − x3

при условиях:

2x1 − x2 + x3 = 5; x1 + 2x2 − x3 ≤ 6.

В этой задаче никакого условия на знак переменной х3 не накладывается. Введем две новые неотрицательные переменные x3' и x3'' , связанные с х3 соотношением x3' - x3'' =

х3. Тогда поставленная задача окажется эквивалентной следующей общей задаче линейного программирования.

Требуется найти неотрицательные числа х1, х2, x3' , x3'' , которые обращают в максимум целевую функцию

z = x1 + 2x2 − x3' + x3''

*Все неравенства (2.2.3) взяты для однообразия со знаком ≤, так как любое неравенство противоположенного смысла (со знаком ≥) может быть превращено в неравенство со знаком ≤ умножением обеих частей его на –1.

при выполнении условий:

Если в решении последней задачи окажется, что x3' ≥ x3'' , то значение переменной х3

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

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

подчиненной условию хj≥0, двух неотрицательных переменных x'j и x'j' , связанных с хj,

соотношением хj= x'j - x'j' .

Примем следующую терминологию. Условия (2.2.2) и (2.2.3) будем называть системой ограничений задачи, а каждое условие в отдельности — ограничением. Таблица

коэффициентов A = aij m×n в системе ограничений (2.2.2) и (2.2.3) называется матрицей условий задачи. Столбцы этой матрицы Aj ={a1j,a2j,..., amj} называются векторами условий.

67

Вектор В =[b1, b2, … , bm], составленный из свободных членов ограничений, называется вектором ограничений. Вектор С=(с1,c2,…, сп), составленный из коэффициентов целевой функции, будем называть вектором коэффициентов целевой функции.

Совокупность неотрицательных чисел х1, х2,..., хn, удовлетворяющих системе ограничений задачи (2.2.2), (2.2.3), называется допустимым решением, или планом, задачи. Неотрицательный вектор Х = [х1 , x2 ,..., xn ] координаты которого составляют

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

Допустимое решение, для которого целевая функция принимает наибольшее (или наименьшее) значение, называется оптимальным решением, или оптимальным планом,

задачи.

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

В векторных обозначениях общая задача линейного программирования может быть переписана в

следующем компактном виде.

По заданной матрице условий А = || аij||mxn, т-мерному вектору ограничений В = [b1, b2,… , bm] и п-мерному вектору коэффициентов целевой функции С=(с1,с2,..., сn) найти неотрицательный вектор Х=[х1, х2,..., хn], для которого скалярное произведение

где Аi —i-я строка матрицы условий А.

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

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

По заданной матрице А = || аij||mxn, m-мерному вектору B = [b1, b2,..., bm] и п- мерному вектору С=(с1, с2,..., сn) найти п-мерный неотрицательный вектор X=[x1, х2,...,

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

Каноническая задача линейного программирования формулируется аналогично стандартной задаче.

По заданной матрице А = || аij||mxn m-мерному вектору B=[b1, b2,..., bm] и п-мерному вектору С=(с1, с2, . . ., сn) найти п-мерный неотрицательный вектор X=[x1, х2,…, хп], для которого скалярное произведение

68

Отметим следующий очевидный факт. Точка X, в которой функция f(X) принимает наибольшее (наименьшее) значение, одновременно является точкой, в которой функция

— f(X) принимает наименьшее (наибольшее) значение, при этом [f (X )]max = −[− f (X )]min и [f (X )]min = −[− f (X )]max . Таким образом, любая задача максимизации (минимизации)

может быть заменена эквивалентной задачей минимизации (максимизации).

Так, если в задаче линейного программирования требуется минимизировать функцию СХ, то, заменив, вектор С= (с1, с2, . . ., сn) противоположным вектором — С=( -с1, -c2, . . ., -сп), придем к эквивалентной задаче максимизации функции -СХ, но при этом, конечно, (СХ)min = - (- СХ)max.

Приведение задач линейного программирования к канонической форме

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

Покажем, каким образом можно преобразовать любую задачу линейного программирования в эквивалентную каноническую задачу. Начнем с рассмотрения стандартной задачи (2.2.7) – (2.2.8)

Введем в рассмотрение неизвестный неотрицательный т-мерный вектор X ' = [xn+1 , xn+2 ,..., xn+m ],

связанный с неизвестным вектором X=[x1, x2, . . ., хп] соотношением

АХ+Х' = В. (2.2.11)

Вектор X' назовем балансовым (выравнивающим) вектором. Ясно, что неотрицательные векторы X и X', удовлетворяющие векторному уравнению (2.2.11), будут удовлетворять векторному неравенству (2.2.8) . Обратно, если вектор X неотрицательный и удовлетворяет неравенству (2.2.8), то балансовый вектор X', найденный из уравнения (2.2.11), окажется неотрицательным. Таким образом, условия (2.2.8) и (2.2.11) для искомого вектора X являются эквивалентными. Поэтому каноническая задача — найти

будет эквивалентна стандартной задаче (2.2.7) — (2.2.8), поскольку вектор X, входящий в оптимальное решение задачи (2.2.12) — (2.2.14), будет, очевидно, являться оптимальным решением стандартной задачи (2.2.7) — (2.2.8). Действительно, неотрицательный вектор X, взятый из решения канонической задачи (2.2.12) — (2.2.14), будет удовлетворять условию (2.2.8) стандартной задачи и давать то же значение (СХ)макс или (СХ)мин.

При решении канонической задачи (2.2.12) — (2.2.14) надо иметь в виду, что эта задача содержит п+т неотрицательных переменных х1, х2,..., хn, хn+1,..., хn+т, и балансовые переменные хn+1, xn+2, . . ., хп+т следует считать входящими слагаемыми в целевую функцию (2.2.12) с нулевыми коэффициентами.

Пример 1. Привести к канонической форме следующую стандартную задачу линейного программирования. Найти неотрицательные числа х1, х2, x3, x4, при которых целевая функция

z = 2x1 + 4x2 + x3 + x4

имеет максимальное значение при условиях:

Путем введения балансовых неизвестных х5, х6, х7 превращаем ограничениянеравенства в уравнения. В результате указанного преобразования получим эквивалентную каноническую форму задачи в следующем виде.

Найти неотрицательные числа xj, j=1, 2, . . ., 7, обращающие в максимум целевую функцию

Оптимальные значения х1, х2, х3, х4, найденные в результате решения этой канонической задачи, являются оптимальным решением исходной стандартной задачи.

Пример 2. Привести к канонической форме следующую стандартную задачу минимизации. Найти неотрицательные числа x1, х2, x3, минимизирующие целевую функцию

z=x1-x2+x3

при условиях:

Если записать эту стандартную задачу в виде задачи (2.2.7) — (2.2.8), изменив в ограничениях знаки неравенств ≥ на ≤ путем умножения их на множитель -1, и затем прибавить к левым частям соответственно балансовые неизвестные x4 и х5, то результат получится тот же, если, не меняя знаков ограничений-неравенств, вычесть из левых частей их балансовые неизвестные x4 и x5. Выполнив указанное преобразование, получим следующую каноническую форму задачи.

Найти неотрицательные числа xj, j=1, 2, . . ., 5, минимизирующие целевую функцию z=x1-x2+x3+0 x4+0 x5

Вообще, балансовые неизвестные следует вводить в ограничения-неравенства, руководствуясь следующим элементарным правилом.

В каждое ограничение-неравенство типа a1 x1 + a2 x2 +,...,+an xn ≤ b

балансовая неизвестная входит в левую часть этого неравенства со знаком «плюс», а в случае неравенства

балансовые неизвестные xn+1, xп+2,…, xn+m—k вводятся только в ограничения-неравенства

70

(2.2.6). Таким образом, общая задача линейного программирования (2.2.4) — (2.2.6) сводится к следующей канонической задаче линейного программирования.

Требуется найти неотрицательные векторы X=[x1,x2, . . ., хп] и X'=[xn+1,. . . ., Xn-k+m ], для которых целевая функция

Пример 3. Привести к канонической форме следующую общую задачу линейного программирования. Найти неотрицательные числа x1, x2, x3, x4, для которых целевая функция

z = -x1+2x2+x3+2x4

принимает наибольшее значение при условиях:

Вводя во второе и третье ограничения-неравенства балансовые неизвестные x5 и x6 с соответствующими знаками, получим следующую эквивалентную каноническую форму задачи.

Найти неотрицательные числа xj, j=1, 2,..., 6, максимизирующие целевую функцию

z = -x1+2x2+x3+2x4+0 x5+0 x6

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

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