Линейное программирование. 
Методы оптимизации. 
Алгоритмы. 
Линейное программирование

Определение 3.1. Задачей линейного программирования называют задачу оптимизации линейной функции в области, задаваемой линейными ограничениями-неравенствами и (или) линейными ограничениями-равенствами.

Математическая модель задачи линейного программирования в общем виде:

,.

, (3.1).

,.

, где .

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

Определение 3.2. Говорят, что задача ЛП имеет каноническую форму, если все ограничения являются равенствами и все входящие в задачу переменные ограничены по знаку:

, (3.2).

.

Используя векторы, , и матрицу, математическую модель (3.2) можно переписать в виде:

(3.3).

При этом является обозначением i-й строки матрицы A, векторное неравенство означает, что все координаты вектора неотрицательны, то есть. Задачу (3.3) можно переписать в виде:

.

,. (3.4).

Определение 3.3. Говорят, что задача ЛП имеет стандартную (симметричную) форму, если все ограничения являются неравенствами и все входящие в задачу переменные ограничены по знаку:

, (3.5).

.

В векторной форме эту задачу можно переписать в виде:

.

(3.6).

.

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

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

Таблица 3.1 — Эквивалентные преобразования

3.1 Свойства задач линейного программирования

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

.

Теорема 3.1.Область допустимых решений (ОДР) задачи линейного программирования X есть многогранное замкнутое выпуклое множество.

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

Упражнение. Подробное доказательство провести самостоятельно.

Определение 3.4. Базисным решением системы называется точка, если она является решением этой системы, и ее ненулевым координатам соответствуют линейно-независимые столбцы матрицы .

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

Пример. Рассмотрим систему линейных уравнений Столбцы матрицы A имеют вид.

, .

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

.

Найдем базисное решение, отвечающее базису. Небазисная переменная =0, тогда базисные переменные, найдем из системы. Получим еще одно базисное решение. Других базисных решений у данной системы нет.

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

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

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

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

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

— опорные решения, — базисные решения, не являющиеся опорными Рис. 3.1. Геометрическая интерпретация базисного и опорного решений.

Теорема 3.2. Всякое опорное решение системы является вершиной (крайней точкой) ОДР множества и наоборот.

Доказательство. Пусть А-матрица размера, и ранг .

Предположим, что координаты допустимого решения системы упорядочены так, что, где .

Тогда, система в точке примет вид.

. (3.7).

Дано: — опорное решение, то есть, и столбцы линейно независимы. Докажем, что — вершина.

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

(3.8).

Из равенства (3.8) следует, что если, то и. Следовательно,, , и верны равенства.

.

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

.

Так как, то и столбцы линейно зависимы. Получено противоречие, доказывающее, что сделанное предположение не верно, и — вершина.

Дано, что вершина области. Докажем, что — опорное решение системы .

По определению области Х имеем 0, и теперь достаточно доказать, что — базисное решение. Доказывать будем методом от противного.

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

. (3.9).

Сложим равенство с равенством (3.9), предварительно умножив его на величину. Получим. А если вместо сложения выполнить вычитание, то получим при любом .

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

Для этого решим систему неравенств относительно переменной.

для .

Проведем преобразования.

для = и >0.

И так, получены две точки, и. Это означает, что представима в виде выпуклой комбинации точек, то есть не вершина. Но это противоречит условию теоремы.

Основная теорема линейного программирования. Если задача линейного программирования разрешима, то среди её оптимальных решений всегда есть вершина (опорное решение).

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

Пусть оптимальное решение, которое по сделанному предположению не является опорным.

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

^, .

Откуда следует, что.

,.

и точки — оптимальные решения.

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

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

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

где ,.

так же оптимальное решение этой задачи.

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

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

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

.

Предположим, что матрица A имеет размер mn, где m.

Возьмем m линейно-независимых столбцов матрицы и образуем из них квадратную матрицу. Очевидно, что определитель. Оставшиеся столбцы объединим в матрицу. Обозначим — множество номеров тех столбцов, из которых составлена матрица B, — множество номеров столбцов, из которых составлена матрица N.

Разобьем вектор на 2 части: базисные переменные образуют вектор =, небазисные переменные вектор =.

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

. (3.10).

О системе линейных уравнений (3.10) говорят, что она имеет жорданову форму.

Рассмотрим базисное решение системы, отвечающее базису: =0, из равенства (3.10). Если, то — опорное решение системы.

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

===.

=, то есть.

=, где. (3.11).

Координаты вектора называют оценками замещения или просто оценками.

Замечание. Если использовать формулу (3.11) для нахождения оценок, соответствующих базисным переменным, то получим. Приходим к выводу: оценки замещения, соответствующие базисным переменным, равны 0.

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

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

Рис. 3.1. Структура симплексной таблицы.

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

Доказательство.

Дано: — оптимальное решение. Доказать: .

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

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

Потребуем, чтобы координаты точки были неотрицательны:. Это векторное неравенство можно переписать в виде системы неравенств.

для. (3.12).

Рассмотрим два возможных случая.

• 1). В p-м столбце симплексной таблицы нет положительных чисел, то есть для. Тогда для выполняются при любом > 0.
• 2). В p-м столбце симплексной таблицы есть положительные числа. Тогда, решив систему (3.12), получим неравенство для определения :

=. (3.13).

При этом, так как опорное решение предполагается невырожденным.

Сравним значения целевой функции в точках и, используя формулу (3.11):

=.

Так как > 0 и, то >, и точка не является оптимальным решением, но это противоречие.

Дано:. Доказать: — оптимальное решение.

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

Следствие 1. Для вырожденного опорного решения условие не отрицательности оценок является лишь достаточным условием его оптимальности.

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

Доказательство. Пусть. Тогда можно построить точку (см. доказательство критерия оптимальности), которая является допустимой при любом > 0. При этом =. Тогда устремив, мы получим .

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

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

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

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

Жордановы преобразования симплекс-таблицы.

Главный элемент выбирается из столбца p с отрицательной оценкой по правилу.

=.

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

• 1) Поменять местами переменные, стоящие в главной строке и в главном столбце.
• 2) Главный элемент заменить ему обратным.
• 3) Все остальные элементы главной строки разделить на главный элемент.
• 4) Все остальные элементы главного столбца разделить на главный элемент и поменять у них знаки на противоположные.
• 5) Все оставшиеся элементы пересчитать по правилу, сходному с правилом вычисления определителя второго порядка (в качестве главной диагонали нужно брать ту, на которой стоит главный элемент), и разделить на главный элемент.

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

Алгоритмическое описание симплекс-метода.

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

1) Если оценки симплекс-таблицы неотрицательны, то таблица оптимальная, и соответствующее ей опорное решение оптимальное.

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

• 2) Если в таблице есть столбец с отрицательной оценкой, и все элементы в нем не положительны, то оптимальное решение не существует, так как целевая функция неограниченна сверху в ОДР (Неразрешимость 2). Алгоритм завершает работу.
• 3) Если в таблице есть столбец с отрицательной оценкой, и в нем есть положительные элементы, то среди этих элементов выбираем главный. Для этого найдем для каждого такого элемента частное от деления правой части ограничения на этот элемент. Полученные частные сравним для того, чтобы главным элементом выбрать тот, которому соответствует наименьшее частное. Главный элемент определяет главную строку и главный столбец, так как он стоит на их пересечении.
• 4) Выполним жордановы преобразования симплекс-таблицы относительно выбранного главного элемента и перейдем к пункту 1.
• 3.3 Построение начальной симплекс-таблицы

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

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

, и пусть .

Если перейти к каноническому виду, то получим.

,.

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

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

,.

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

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

3. Рассмотрим общий случай, когда построение симплекс-таблицы не является таким простым, как в случае 1 или 2. При этом будем для построения начальной симплекс-таблицы использовать метод искусственного базиса.

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

(3.14).

, и пусть .

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

Для этой цели построим вспомогательную задачу.

(3.15).

, ,.

где — новые переменные, которые будем называть искусственными.

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

Теорема 3.4.Вспомогательная задача (3.15) всегда разрешима.

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

Теорема 3.5. У исходной задачи существует допустимое решение тогда и только тогда, когда у вспомогательной задачи максимальное значение целевой функции равно нулю.

Доказательство.

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

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

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

Следствие 2. Если оптимальное значение целевой функции вспомогательной задачи равно 0, то из оптимальной симплекс-таблицы вспомогательной задачи можно построить начальную симплекс-таблицу исходной задачи. Здесь возможны 3 случая.

• 1) Ранг матрицы ограничений исходной задачи, и задача невырожденная. Тогда, решив вспомогательную задачу, получим симплекс-таблицу, в которой искусственные переменные будут принадлежать множеству небазисных переменных. Для получения начальной симплекс-таблицы исходной задачи нужно вычеркнуть столбцы с искусственными переменными и пересчитать нижнюю строку таблицы оценок, используя целевую функцию исходной задачи
• 2) Ранг матрицы ограничений исходной задачи, и задача невырожденная. Тогда, решив вспомогательную задачу, получим симплекс-таблицу, в которой среди базисных переменных будут некоторые искусственные переменные. В строках, где базисной переменной является искусственная переменная, все элементы будут равны 0. Эти строки будут соответствовать тем уравнениям, которые являются линейной комбинацией остальных. Для перехода к первому случаю, нужно вычеркнуть строки, о которых шла речь выше.
• 3) Пусть ранг матрицы ограничений исходной задачи, и задача вырожденная. Тогда после решения вспомогательной задачи, можем получить симплексную таблицу, в которой среди базисных переменных будут некоторые искусственные переменные. Однако, в отличие от 2-го случая в этих строках будут элементы не равные нулю. Чтобы искусственную переменную вывести из базиса, достаточно выбрать в такой строке любой отличный от нуля элемент главным и выполнить относительно этого главного элемента жордановы преобразования таблицы. После того, как все искусственные переменные окажутся выведенными из числа базисных переменных, придем к таблице, отвечающей 1-му случаю.

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

• 1. Используя эквивалентные преобразования, преобразуйте данную задачу к каноническому виду с неотрицательными правыми частями.
• 2. Постройте вспомогательную задачу. Для этого из исходной преобразованной задачи возьмите только ограничения. Прибавьте к левым частям ограничений новые переменные, которые далее будем называть искусственными. Если до введения искусственных переменных матрица ограничений имела некоторые столбцы для единичной матрицы, то дублировать их введением искусственных переменных не обязательно. В качестве целевой функции вспомогательной задачи возьмите сумму искусственных переменных со знаком минус и потребуйте ее максимизации.
• 3. Решите вспомогательную задачу симплекс-методом.
• 4. Если оптимальное значение целевой функции вспомогательной задачи окажется отрицательным числом, то сделайте вывод: исходная задача не имеет допустимых решений (неразрешимость 1). Перейдите к пункту 6.
• 5. Если оптимальное значение целевой функции вспомогательной задачи равно нулю, то используйте полученную оптимальную таблицу вспомогательной задачи и постройте начальную симплексную таблицу для исходной задачи. Для этого в таблице вычеркните столбцы с искусственными небазисными переменными и пересчитайте заново оценки, используя целевую функцию исходной задачи.
• 6. Завершите работу алгоритма.