Теорема об экстремуме целевой функции

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

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

Z(X) = CX max,

AX = ,

.

Рис. 3.5

1. Докажем, что целевая функция достигает экстремума в угловой точке области допустимых решений G, от противного. Если – оптимальное решение, то . Предположим, что оптимальное решение задачи не является угловой точкой (рис.3.5). Тогда по теореме 3.1

,

где , где (j = 1, 2, …, n) – угловые точки G.

Найдем

.

Среди значений выберем наибольшее. Пусть это будет , т. е. = . Тогда

.

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

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

,

получим

т. е. решение также является оптимальным.

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

Рассмотрим систему ограничений некоторой конкретной задачи

которая в векторной записи имеет вид

,

где

Векторы называются векторами условий.

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

Положительным координатам допустимых решений ставят в соответствие векторы условий. Для решений и такими будут векторы и , соответственно. Эти системы векторов являются линейно зависимыми, так как число входящих в них векторов (4 и 3) больше размерности векторов (2). Таких решений бесконечное множество. Для базисного решения соответствующие положительным координатам единичные векторы и линейно независимые. Как известно, любая система уравнений имеет конечное число базисных решений, равное , где n – число неизвестных, r – ранг системы векторов условий. Базисные решения, координаты которых удовлетворяют условию неотрицательности, называются опорными. В дальнейшем будет показано, что они являются угловыми точками области допустимых решений задачи.

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

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

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

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

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

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

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

.

Так как последние n - m координат вектора X равны нулю, а и положительные, то последние n - m координат векторов и также равны нулю, т. е. и .

Подставим в систему ограничений.

.

Вычтем из первого равенства второе, получим

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

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

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

Доказательство. Пусть угловая точка области допустимых решений и при j = 1, 2,…, m. Чтобы доказать, что это решение является опорным, достаточно показать, что векторы , соответствующие положительным координатам решения, являются линейно независимыми. Предположим, что эти векторы линейно зависимые. Тогда существует ненулевой набор чисел такой, что

(3.2)

Так как X допустимое решение, то имеет место равенство

(3.3)

Умножим соотношение (3.2) на некоторое число и прибавим к равенству (3.3), получим

,

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

.

Для того чтобы эти векторы и удовлетворяли условиям неотрицательности, достаточно малое число e выбирать таким, что . Это возможно, так как при j = 1, 2,…, m.. При таком выборе числа векторы и считаются допустимыми. Нетрудно увидеть, что , т. е. X – выпуклая линейная комбинация и . Однако это противоречит тому, что X является угловой точкой. Следовательно, векторы линейно независимые, и решение X является опорным.

Лекция№5-6.

СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ
ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

Симплексный метод позволяет выполнить следующее:

1) найти начальное опорное решение;

2) перейти к новому опорному решению, на котором значение целевой функции будет ближе к оптимальному решению, т. е. улучшить опорное решение;

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

Название метод получил от вида области допустимых решений задачи, для которой он первоначально применялся. Область допустимых решений этой задачи имела простейший (simple) вид (рис. 3.6).

Рис. 3.6

5.1. Нахождение начального опорного решения и переход
к новому опорному решению

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

(4.1)

(4.2)

(4.3)

Будем считать, что правые части всех уравнений системы ограничений неотрицательны. Если в каком-либо уравнении правая часть отрицательная, то это уравнение нужно умножить на -1.

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

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

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

.

1. Для того чтобы правая часть уравнения с разрешающим элементом оставалась неотрицательной, должно выполняться неравенство

.

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

.

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

.

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

а) если , то ввиду того, что , , , без дополнительных условий имеем ;

б) если же , то неравенство

поделим на , получим

.

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

. (4.4)

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

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

Используя данное условие, можно найти начальное опорное решение.

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

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

.

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

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

при , (4.5)

где k – номер вектора, вводимого в базис, l – номер вектора, выводимого из базиса, – координаты опорного решения, – коэффициенты разложения вектора по базису опорного решения.

Пример 5.1. Найти начальное опорное решение и путем перебора опорных решений найти оптимальное решение задачи

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

Т а б л и ц а 5.1

,

.

,

.

, .

,

.

Сравниваем значения целевой функции на полученных опорных решениях, min{-20, 4, -28} = -28. Находим оптимальное опорное решение

.

Ответ: при .

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

5.2. Преобразование целевой функции при переходе
от одного опорного решения к другому

Пусть имеется опорное решение задачи линейного программирования (4.1)-(4.3) c базисом . Значение целевой функции задачи на этом этапе решения равно . Используя преобразование Жордана с разрешающим элементом , перейдем к другому опорному решению с базисом , т. е. введем в базис вектор и исключим . Значение целевой функции на этом этапе решения равно

.

Формулы пересчета правых частей уравнений системы при преобразовании Жордана имеют вид

; ; i = 1, 2, …, m; i ¹ l.

Используя эти формулы, получим

,

т. е. . (4.6)

Отсюда находим приращение целевой функции при переходе от одного опорного решения к другому

. (4.7)

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

(4.8)

или в векторной записи

, (4.9)

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

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

.

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

Т а б л и ц а 4.2

				-4
Б Сб
			-1	-4
			-2
			-13

;

;

.

Оценки для векторов, входящих в базис, всегда равны нулю.

Улучшение опорного решения

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

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

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

.

Решение невырожденное, поэтому параметр , вычисляемый по формуле (4.5), отличен от нуля ( > 0). Так как > 0, , то

.

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

Доказательство для задачи на минимум аналогично.

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

– в задаче на максимум ; (4.10)

– в задаче на минимум . (4.11)

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

– в задаче на максимум ; (4.12)

– в задаче на минимум . (4.13)

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

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

– в задаче на максимум ; (4.14)

– в задаче на минимум . (4.15)

Действительно, если Z(x) , , , то

,

т. е. – оптимальное решение. Для задачи на минимум доказательство аналогично.

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

. (4.16)

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

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

$ k Î {m+1, m+2, ..., n}: . (4.17)

Следствие 5 (признак отсутствия оптимального решения ввиду неограниченности целевой функции). Задача линейного программирования не имеет решения ввиду неограниченности целевой функции, если для какого-либо из векторов условий с оценкой , противоречащей признаку оптимальности, среди коэффициентов разложения по базису опорного решения нет положительного, т. е.

– в задаче на максимум и ; (4.18)

– в задаче на минимум и . (4.19)

5.4. Алгоритм симплексного метода решения задач линейного
программирования

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

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

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

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

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

4. Если выполняется признак единственности оптимального решения (следствие 3 из теоремы 4.1), то решение задачи заканчивается.

5. Если выполняется условие существования множества оптимальных решений (следствие 4 из теоремы 4.1), то путем простого перебора находят все оптимальные решения.

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

7. Если пункты 4–6 алгоритма не выполняются, то находят новое опорное решение с использованием условий следствия 1 из теоремы 4.1 и возвращаются к п. 3.

Пример 4.3. Решить симплексным методом задачу

,

Решение. Приводим задачу к каноническому виду. Для этого в левую часть первого ограничения неравенства типа " £ " вводим дополнительную переменную с коэффициентом +1. В целевую функцию переменная входит с коэффициентом 0 (т. е. не входит). Получаем

,

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

Вычисляем оценки разложений векторов условий по базису опорного решения по формуле (4.9).

;

;

;

;

;

.

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

Т а б л и ц а 4.3

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

В последней строке таблицы с оценками в столбце " " записывается значение целевой функции на опорном решении .

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

По теореме об улучшении опорного решения, если в задаче на максимум хотя бы один вектор имеет отрицательную оценку, то можно найти новое опорное решение, на котором значение целевой функции будет больше. Определим, введение какого из двух векторов приведет к большему приращению целевой функции. Приращение целевой функции находится по формуле . Вычисляем значения параметра для первого и третьего столбцов по формуле (4.5), получаем при l = 1; при l = 1 (табл. 4.3). Находим приращение целевой функции при введении в базис первого вектора и третьего вектора . Следовательно, для более быстрого приближения к оптимальному решению необходимо ввести в базис опорного решения вектор вместо первого вектора базиса , так как минимум параметра достигается в первой строке (l = 1). Производим преобразование Жордана с элементом , получаем второе опорное решение с базисом (табл. 4.4). Это решение не является оптимальным, так как вектор имеет отрицательную оценку . Для улучшения решения необходимо ввести вектор в базис опорного решения.

Т а б л и ц а 4.4

Определяем номер вектора, выводимого из базиса. Для этого вычисляем параметр для второго столбца, он равен 7 при l = 2. Следовательно, из базиса выводим второй вектор базиса . Производим преобразование Жордана с элементом , получаем третье опорное решение (табл. 4.5). Это решение является единственным оптимальным, так как для всех векторов, не входящих в базис, оценки разложений по базису опорного решения положительные .

Т а б л и ц а 4.5

Ответ: max Z(X) = 201 при .

Лекция №7.

Метод искусственного базиса

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

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

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

,

(4.20)

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

В дальнейшем для краткости записи при доказательствах используется компактная запись этой задачи

,

; (4.21)

.

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

Искусственными переменными называются неотрицательные переменные, которые вводятся в ограничения-равенства для получения начального опорного решения с базисом из единичных векторов. Каждая искусственная переменная вводится в левую часть одного из уравнений системы ограничений с коэффициентом +1 и в целевую функцию в задаче на максимум – с коэффициентом -М, а в задаче на минимум – с коэффициентом +М. Число М сколь угодно большое по сравнению с единицей (М >> 1).

В общем случае расширенная задача на максимум имеет вид

(4.22)

, j = 1, 2, ..., n+m; , i = 1, 2, ..., m

или в компактной записи

, (4.23)

.

Данная задача имеет начальное опорное решение

с единичным базисом

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

Для обосновани