Решение. Построим область допустимых решений D (рис

Построим область допустимых решений D (рис. 1.4), она совпадает с областью в примере 3.

Заметим, что вектор-градиент направлен в противоположную сторону (по сравнению с рис. 1.3). Максимум достигается в единственной точке Р, являющейся точкой пересечения оси x₁ и прямой y ₂.

Рис. 1.4

Координаты точки Р можно определить, решив систему уравнений:

Ее решение x ₁=2, x ₂=0, значение функции в этой точке равно

Вывод. Задача ЛП имеет решение, когда многогранник замкнут в направлении роста целевой функции.

Рассмотренные примеры иллюстрируют четыре варианта Положения 5.

1.2.2. Основная идея симплекс-метода

Если ранг матрицы А системы (1.1) и ранг расширенной матрицы системы равен r(r£m), то r переменных могут быть выражены через остальные переменные:

(1.25)

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

Отметим важнейшие условия наличия единичного базиса:

· от каждого уравнения в него входит одна и только одна неизвестная;

· каждая переменная из этого набора входит с коэффициентом +1 и отсутствует в остальных уравнениях;

· все значения ,

Подставляя в линейную форму F (1.3) вместо базисных переменных их выражения через свободные переменные из системы (1.25), получим:

(1.26)

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

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

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

1.2.3. Реализация симплекс-метода (простейший случай)

Рассмотрим идею симплекс-метода на конкретном примере:

	(1.27)
	(1.28)
	(1.29)

Решение

Данная система уравнений совместна, так как ранги матрицы системы

и расширенной матрицы

совпадают и равны 3. Следовательно, три переменные (базисные) можно линейно выразить через две свободные переменные. Выразим, например, x₁, x₂ и x₃ через x₄ и x₅, т.е. приведем систему к единичному базису:

(1.30)

Линейная форма уже выражена через x₄ и x₅.

При x ₄ =0 и x ₅= 0, найдем значения базисных переменных x₁= 1, x₂ =2 и x₃= 3.

Таким образом, первое допустимое решение имеет вид x₁= 1 ,x₂ =2, x₃= 3, x₄ = 0, x₅= 0 или (1,2,3,0,0). При найденном допустимом решении линейная форма F имеет значение 0, т.е. F₁= 0.

Теперь попытаемся увеличить значение F:

- увеличение x₄ уменьшит F, так как перед x₄ стоит отрицательный коэффициент, а увеличение x₅ даст увеличение;

- будем увеличивать x₅ таким образом, чтобы одна из базисных переменных (x ₁ или x₂ или x₃)обратилась в ноль, а остальные базисные переменные оставались бы неотрицательными.

Анализируя первое уравнение системы (1.30), приходим к выводу, что x₅ можно увеличить неограниченно. При этом x₁ остается положительным и никогда необратиться в ноль. Из второго уравнения системы (1.30) следует, что x₅ можно увеличить до 2 (больше увеличивать нельзя, т.к. x₂ станет отрицательным). Из третьего уравнения системы (1.24) следует, что x₅ можно увеличить до 3. Принимая во внимание приведенный анализ, приходим к выводу, что x₅= 2.

Таким образом, получим второе допустимое решение x₁= 5, x₂= 0, x₃= 1, x₄ = 0, x₅= 2 или (5,0,1,0,2).

Значение линейной формы F при этом допустимом решении равно F₂= 2, т.е. значение целевой функции увеличилось.

Примем за свободные переменные x₂ и x₄., т.е. те переменные, которые в этом решении равны 0. С этой целью из второго уравнения системы (1.27) выразим x₅ .

Получим . Тогда

(1.31)

Для увеличения значения F будем увеличивать x₄. Проведя аналогичный анализ системы (1.31), заключаем, что x₄ можно увеличить до 1/5 (следует из рассмотрения второго уравнения системы (1.31)). Таким образом, получим третье допустимое решение x₁= 28/5, x₂= 0, x₃= 0, x₄= 1/5, x₅= 12/5 или (28/5, 0, 0, 1/5, 12/5). Значение линейной формы F при этом допустимом решении равно F₃=11/5, т.е. значение целевой функции увеличилось.

(1.32)

Так как в последней линейной форме обе свободные переменные входят с отрицательными коэффициентами, то наибольшее значение достигается при x₂ =0, x₃= 0.

Из этого следует, что решение (28/5, 0, 0, 1/5, 12/5) является оптимальным и F_max= 11/5.

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

Симплексные таблицы

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

	(1.33)
	(1.34)

В виде таблицы (табл.1.1) эти данные можно представить так:

Таблица 1.1

Базисные переменные		…		…			…		…		Свободные члены
		…		…					…
…		…		…		…		…	…	…	…
		…		…					…
…	…	…	…	…	…	…	…	…	…	…	….
		…		…					…
F		…		…					…

Заметим, что в строку с целевой функцией коэффициенты записываются с противоположным знаком .

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

Правила преобразования симплексной таблицы.

1. Выбирают разрешающий столбец из условия и хотя бы один элемент .

2. Выбирают q -ю разрешающую строку из условия

Элемент , стоящий на пересечении разрешающего (с индексом p) столбца и разрешающей (с индексом q) строки, называется разрешающим элементом.

3. В состав базисных переменных вводят переменную , которую записывают в строку с номером q.

4. Производят пересчет элементов разрешающей q -й строки по формуле

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

5. Вычисляют элементы всех остальных строк (при k¹p) по формуле:

Строке с номером r+ 1 соответствует строка целевой функции, столбцу с номером n+ 1 соответствует столбец свободных членов.

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

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

Анализ базируется на основной теореме симплекс-метода.

Теорема.

Если после выполнения очередной итерации (преобразования):

1) найдется хотя бы один отрицательный коэффициент , и в каждом столбце с таким коэффициентом окажется хотя бы один положительный элемент, то можно улучшить решение, выполнив следующую итерацию;

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

3) все коэффициенты окажутся неотрицательными, то оптимальное решение достигнуто.

Рассмотрим решение той же задачи (1.27) - (1.29) с помощью симплекс-таблиц.

Исходная симплекс-таблица, определяемая соотношениями (1.27) - (1.29) показана на рис. 1.5.

Базисные переменные	x1	x2	x3	x4	x5	Свободные члены
x1					-2
x2				-2
x3
F					-1

Рис.1.5. Исходная симплекс таблица

Заметим, что целевая функция в данном примере может быть записана в виде , что соответствует виду (1.34). В качестве разрешающего столбца выберем столбец, соответствующий x ₅ , поскольку в нем в строке с целевой функцией стоит отрицательный элемент (– 1).

Для определения разрешающей строки заполним вспомогательный столбец (рис. 1.6).

Первая клетка в этом столбце оставлена пустой, поскольку в соответствующей клетке столбца x₅ стоит отрицательный элемент (– 2).

Из этого столбца выбираем минимальное значение min{2;3}=2; это значение стоит во второй строке, поэтому берем её в качестве разрешающей.

Базисные переменные	x1	x2	x3	x4	x5	Свобод-ные члены	Вспомога-тельный
x1					-2
x2				-2			2/1=2
x3							3/1=3
F					-1

Рис.1.6. Выбор разрешающего столбца и разрешающей строки (они выделены) для первой итерации

Выполним преобразования указанные в п.п.4–5 для табл. 1.1. Результат приведен на рис. 1.7. Значение целевой функции F =2.

Базисные переменные	x1	x2	x3	x4	x5	Свободные члены
x1				-3
x5				-2
x3		-1
F				-1

Рис.1.7. Симплекс таблица после первой итерации

Поскольку в строке, соответствующей целевой функции, имеется отрицательный элемент –1 (столбец x ₄), необходимо выполнить еще одну итерацию.

Для определения разрешающей строки (разрешающий столбец уже очевиден - x ₄) заполним таблицу (рис.1.8.):

Базисные переменные	x1	x2	x3	x4	x5	Свободные члены	Вспомогательный
x1				-3
x5				-2
x3		-1					1/5
F				-1

Рис.1.8. Выбор разрешающего столбца и разрешающей строки для второй итерации

Выбор разрешающей строки свелся к выбору из одной строки, поскольку только в строке x ₃ стоит положительный элемент. Выполним преобразования указанные в п.п.4–5 для таблицы (рис. 1.7), результат – в таблице на рис. 1.9.

Базисные переменные	x1	x2	x3	x4	x5	Свободные члены
x1		7/5	3/5			28/5
x5		3/5	2/5			12/5
x4		-1/5	1/5			1/5
F		4/5	1/5			11/5

Рис. 1.9. Симплекс таблица после второй итерации

В строке, соответствующей целевой функции, нет отрицательных элементов, следовательно, получено оптимальное решение (28/5,0,0, 1/5, 12/5) и F_max= 11/5. Заметим, что решения совпали.

1.2.4. метод искусственного базиса

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

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

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

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

.

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

,

которая имеет предпочтительный вид

.

В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю , .

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

.

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

.

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

В этом случае вводится так называемый искусственный базис.

К левым частям ограниче­ний-равенств, не имеющих предпочтительного вида, добав­ляют искусственные переменные , .

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

Пусть исходная задача ЛП имеет вид (1.1)-(1.3), причём ни одно из ограничений не имеет предпочтительной переменной. М -задача запишется так:

	(1.35)
	(1.36)
	(1.37)

Задача (1.35) - (1.37) имеет предпочтительный план. Её начальный опорный план имеет вид

Если некоторые из уравнений (1.1) имеют предпочтительный вид, то в них не следует вводить искусственные переменные.

Теорема.

Если в оптимальном плане

(1.38)

М -задачи (1.35) - (1.37) все искусственные переменные , то план является оптимальным планом исходной задачи (1.1)-(1.3).

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

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

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

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

Дата добавления: 2015-09-03