Для применения симплекс-метода с естественным базисом КЗЛП должна содержать единичную подматрицу размером mxm – в этом случае очевиден начальный опорный план (неотрицательное базисное решение системы ограничений КЗЛП).
Для определенности предположим, что первые m векторов матрицы системы уравнений составляют единичную матрицу. Тогда первоначальный опорный план очевиден – (b 1 , b 2 ,…, b m ,0,…,0).
Проверка на оптимальность опорного плана проходит с помощью признака оптимальности, переход к другому опорному плану проводится с помощью преобразований Жордана-Гаусса при использовании математического признака оптимальности. Полученный опорный план снова проверяется на оптимальность и так далее. Процесс заканчивается за конечное число шагов, причем на последнем шаге либо выявляется неразрешимость задачи (конечного оптимума нет), либо получается оптимальный опорный план и соответствующее ему оптимальное значение ЦФ.
Математический признак оптимальности состоит из следующих двух теорем:
1. Если для всех векторов А 1 , А 2 ,…, А n выполняется условие
где ,
то полученный опорный план является оптимальным.
2. Если для некоторого вектора, не входящего в базис, выполняется условие, то можно получить новый опорный план, для которого значение ЦФ будет больше исходного, при этом могут быть два случая:
- если все компоненты вектора, подлежащего вводу в базис, неположительны, то ЗЛП не имеет решения (конечного оптимума нет);
- если имеется хотя бы одна положительная компонента у вектора, подлежащего вводу в базис, то можно получить новый опорный план.
На основании признака оптимальности в базис вводится вектор А к, давший минимальную отрицательную величину симплекс разности:
Чтобы выполнялось условие неотрицательности значений опорного плана, выводится из базиса вектор А r , который дает минимальное положительное оценочное отношение

Строка А r называется направляющей, столбец А к и элемент a r к – направляющими.
Элементы направляющей строки в новой симплекс-таблице вычисляются по формулам:
а элементы i-й строки – по формулам:
Значения нового опорного плана рассчитываются по формулам:
для i = r ;
Процесс решения продолжают либо до получения оптимального плана, либо до установления неограниченности ЦФ. Если среди симплекс-разностей (оценок) оптимального плана нулевые только оценки, соответствующие базисным векторам, то это говорит о единственности оптимального плана. Если же нулевая оценка соответствует вектору, не входящему, то в общем случае это означает, что оптимальный план не единственный.
Примечание. Для использования приведенной процедуры к минимизации линейной функции f (x 1 ,x 2 ,…, x n) следует искать максимум - f (x 1 ,x 2 ,…, x n), затем полученный максимум взять с противоположным знаком. Оптимальное решение то же.
Пример. Получить решение по модели:
Эта задача (модель) линейного программирования, приведем ее к каноническому виду путем введения дополнительных переменных x 3 и x4:
КЗЛП имеет необходимое число единичных столбцов, т.е. обладает очевидным начальным опорным планом (0,0,300,150). Решение осуществляется симплекс-методом с естественным базисом с оформлением расчетов в симплекс-таблицах:

j. Оптимальные значения переменных равны: x1*=75, x2* =75 (основные переменные), x3* =0, x4* =0 (дополнительные переменные). Максимальное значение целевой функции равно 375.
Таким образом, в рассмотренной выше задаче об оптимальном использовании ограниченных ресурсов, оптимальная производственная программа состоит в выпуске 75ед. изделий первого вида и 75ед. изделий второго вида. С этой программой связана максимальная выручка от реализации готовой продукции – 375 у.е.

Номер			В	2	3	0	0
симплекс-	Базис		план					Q
таблицы
	А3	0	300	1	3	1	0	100
0	А4	0	150	1	1	0	1	150
		f(x)	0	-2	-3	0	0
	А2	3	100	1/3	1	1/3	0	300
I	А4	0	50	2/3

Признак оптимальности опорного плана. Симплекс таблица

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

при ограничениях

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

Находим начальный опорный план

Обозначим через Б множество базисных переменных, через В- множество свободных переменных. Очевидно, при, . Значения называются оценками свободных переменных.

Признак оптимальности опорного плана:

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

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

Строка функции цели называется Z-строкой или индексной строкой. Начальный опорный план Х 0 =(1/2;3/2;0;2;0) и Z(Х 0)=-9/2. Т.к. все оценки индексной строки неположительны, то план Х 0 - оптимален.

Переход к нехудщему опорному плану. Симплексные преобразования

Рассмотрим задачу

Начальный опорный план

Если все оценки свободных переменных, то план Х 0 - оптимальный. Если существуют положительные оценки свободных переменных, то столбец, которому соответствует наибольшее значение?j называется разрешающим. Обозначим его номер j o , а величину x jo введем в базис.

Т.к. ? jо > 0, то, не изменяя нулевых значений всех свободных переменных, можно уменьшить функцию Z за счет увеличения x jo .

Чтобы перейти к новому опорному плану из базиса нужно вывести одну из переменных.

Значение xj o нужно увеличить так, чтобы ни одно из значений базисных переменных x i не было отрицательным. Т.е.

Возможны два случая.

1) Все элементы разрешающего столбца j o неположительны, т.е. a ijo ? 0. Если при решении задачи на min (max) в индексной строке имеются положительные (отрицательные) оценки свободных переменных, а в столбце переменной xj o нет ни одного положительного элемента, то целевая функция не ограниченна снизу (сверху) на множестве допустимых планов задачи.

2) Если среди элементов разрешающего столбца имеются положительные, то x jo можно увеличивать до тех пор, пока не нарушается система неравенств:

Отсюда получаем

Пусть данное выражение выполняется при i=i o , тогда

Если условие выполняется при нескольких i, то в качестве i o можно выбрать любое. Строку i o называют разрешающей, элемент - разрешающим.

Новое значение целевой функции:

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

Правила симплексного преобразования:

1) В индексной строке симплекс-таблицы найти наибольший положительный (или отрицательный) элемент. Столбец соответствующий этому элементу - разрешающий.

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

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

4) Неизвестные элементы, соответствующие разрешающим столбцу и строке, меняются местами.

5) Переход к следующей таблице. Элементы разрешающей строки новой таблицы будут равны

6) Элементы разрешающего столбца равны нулю, за исключением, т.к. x jo - базисная величина.

7) Все остальные элементы находятся по формулам

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

8) вычисляем элементы индексной строки

Для контроля вычислений можно вычислить

9) алгоритм продолжается до тех пор, пока не будет достигнуто условие оптимальности.

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

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

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

Оптимальный план X (7;0;0;42;2) и Z(x)=72.

Пример задачи с искусственным базисом .

Приведем задачу к каноническому виду:

Во 2-е и 3-е уравнение введем искусственные переменные:

Составим симплексную таблицу:

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

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

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

Симплекс метод может использоваться для решения ЗЛП с любым количеством неизвестных.

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

Симплекс-метод с естественным базисом применяется, если ЗЛП задана в канонической форме записи, и матрица в КЗЛП содержит единичную подматрицу размером m´m . Для определённости положим, что первые m векторов матрицы системы уравнений составляют единичную матрицу. Тогда первоначальный план выбирается следующим образом:

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

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

1. Если для всех векторов A 1 , A 2 , … , A n выполняется условие , где , то полученный опорный план является оптимальным. В сумме для определения Z j участвуют m слагаемых, то есть в ней участвуют не все коэффициенты целевой функции c j , а лишь с номерами соответствующими номерам текущих базисных векторов A i , количество которых равно m .

2. Если для некоторого вектора, не входящего в базис, выполняется условие , то следует искать новый опорный план, для которого значение ЦФ больше, чем для текущего. При этом возможны два случая:

а) если все компоненты вектора A k , подлежащего вводу в базис, неположительны, то ЗЛП не имеет решения (конечного оптимума нет);

б) если имеется хотя бы одна положительная компонента у вектора A k , подлежащего ввода в базис, то можно получить новый опорный план.

На основании признака оптимальности в базис вводится вектор A k , давший минимальную отрицательную величину симплекс-разности:

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

Строка A r , в которой находился старый базисный вектор, называется направляющей, столбец A k и элемент a rk - направляющими.

Элементы направляющей строки в новой симплекс-таблице вычисляются по формулам:

а элементы любой другой i -й строки - по формулам:

Значения нового опорного плана рассчитываются по аналогичным формулам:

,

Процесс продолжают либо до получения оптимального плана, либо до установления неограниченности ЦФ. Если среди разностей Δ j , j=1, 2, … , n оптимального плана нулевыми являются только разности, соответствующие базисным векторам, то это говорит о единственности оптимального плана. Если же нулевая оценка соответствует вектору, не входящему в базис, то в общем случае это означает, что оптимальный план не единственный.

Пример. Решить ЗЛП по модели:

найти ,

при ограничениях

Эта ЗЛП сводится к каноническому виду путём введения дополнительных переменных x 3 и x 4 :

КЗЛП имеет необходимое количество (два) нулевых столбцов при x 3 и x 4 , то есть обладает очевидным начальным опорным планом (0,0,300,150).

Решение осуществляется симплекс-методом с естественным базисом с оформлением расчётов в симплекс-таблицах:

Номер симплекс-таблицы	Базис	с j	с j					Q
B	A 1	A 2	A 3	A 4
	← A 3
A 4
Δ	-		-2	-3			-
I	→ A 2			1/3		1/3
← A 4			2/3		-1/3
Δ	-		-1				-
II	A 2					1/2	-1/2	-
→ A 1					-1/2	3/2	-
Δ	-				1/2	3/2	-

Остановимся подробнее на заполнении симплекс-таблиц и, соответственно, получении решения КЗЛП.

В верхнюю строку общей таблицы внесены коэффициенты c j , j=1, 2, 3, 4 при переменных в ЦФ. В первые две строки нулевой симплекс-таблицы внесены вектор-столбцы B, A 1 , A 2 , A 3 , A 4 , соответствующие векторной форме записи КЗЛП. Поскольку исходным базисом является пара векторов A 3 , A 4 , они внесены в колонку под названием “Базис” нулевой симплекс-таблицы. При этом, A 3 внесён в первую строку, что определяется единицей, являющейся первым элементов этого вектора, а вектор A 4 - во вторую строку, у этого вектора единица находится во второй строке. В столбец под названием “ c i ” внесены коэффициенты целевой функции, соответствующие базисным векторам A 3 , A 4 , то есть c 3 , c 4 . Они оба равны нулю. Далее вычисляются значения разностей Δ для векторов B, A 1 , A 2 , A 3 , A 4 и заносятся в третью строку нулевой таблицы. Для вектора A 1 :

для вектора :

Аналогично , .

Для вектора B вычисление разности несколько упрощается, поскольку ему нет соответствующего коэффициента c j , j=1, 2, 3, 4 в ЦФ:

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

Для определения вектора, который мы должны ввести, ищем вектор, для которого значение разности получилось минимальным. Таким является вектор, A 2 , ему соответствует минимальное значение разности: -3. То есть индекс k из формулы (8.4) равен 2. Для определения вектора, который мы должны будем вывести из базиса, вычисляем значения Q для каждой строки по формуле (8.5) и вносим их в последнюю колонку. В данном случае в каждой строке мы должны величину элемента вектора B разделить на величину элемента вектора A 2 . В первой строке получим 300/3=100, во второй: 150/1=150. Меньше получилось отношение в первой строке, ей соответствовал базисный вектор A 3 , следовательно, индекс r в формуле (8.5) равен 1, a rk =3 (выделен в таблице рамкой), а выводить из базиса мы будем вектор A 3 (обозначено в таблице стрелкой).

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

После этого заполняется вторая симплекс-таблица. Для перерасчёта элементов векторов B, A 1 , A 2 , A 3 , A 4 используются формулы (8.6)-(8.8). Они несколько отличаются для определения элементов направляющей строки (в нашем случае первая) и для определения элементов прочих строк. Распишем вычисления нескольких элементов:

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

Как мы видим, в результате расчётов во второй симплекс-таблице с базисными векторами A 2 , A 1 все разности получились неотрицательные, что означает достижение оптимального плана (75; 75; 0; 0). Симплекс-разность для вектора В равна искомому максимальному значению ЦФ - 375.

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

123 страницы (Word-файл)

Посмотреть все страницы

Фрагмент текста работы

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

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

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

Теорема 1.2 (о существовании опорного плана)

Если линейная форма ограничена сверху на непустом множестве D, то ЗЛП разрешима, то есть существует такая точка , что .

Теорема 1.3 (признак оптимальности опорного плана)

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

(1.21)

называется симплекс – разностью или оценкой .

Теорема 1.4 (признак отсутствия оптимального плана)

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

Теорема 1.5 (признак существования лучшего опорного плана)

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

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

1. Задача должна быть приведена к каноническому виду. Система ограничений приведена к единичному базису, т.е. разрешена относительно некоторых базисных переменных (не умоляя общности, будем считать, что относительно первых m переменных) с помощью метода Жордана – Гаусса (система (1.19)). Получено соответствующее исходное опорное решение .

2. Для удобства ведения вычислений записываем все в симплекс-таблицу (табл. 1.1). Столбец «Базис» содержит список базисных переменных; следующий столбец «c j базиса» содержит коэффициенты целевой функции при базисных переменных; следующие столбцы содержат коэффициенты системы ограничений при соответствующих переменных; столбец «b i » - столбец свободных членов системы ограничений. Последняя строка содержит симплекс – разности, рассчитанные по формуле (1.21) и последняя ячейка содержит значение целевой функции =. Отметим, что симплекс – разности базисных переменных всегда равны нулю.

Таблица 1.1

		c j базиса

3. Если все симплекс – разности неотрицательны, т.е. , то опорный план оптимален.

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

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

6. Выбираем разрешающий столбец «р», которому соответствует наименьшая отрицательная оценка.

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

8. Переходим к новой симплекс – таблице, в которой будет новый базис: базисная переменная на «к» - ом месте в старом базисе меняется на новую переменную . Соответствующий вектор новой базисной переменной нужно превратить в единичный. Для этого разрешающую строку делим на , чтобы на месте разрешающего элемента появилась единица. Умножая разрешающую строку на подходящие числа и складывая её с остальными строками получаем нули в разрешающем столбце. После этого выписываем новый опорный план и пересчитываем строчку оценок. Переходим к пункту 3.

Замечание об альтернативном плане.

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

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

Пример 5. Решить ЗЛП симплекс-методом:

(1.22)

Приводим систему линейных неравенств (1.22) к каноническому виду, вводя в каждое неравенство дополнительную неотрицательную переменную. Получим систему линейных уравнений:

(1.23)

Целевая функция будет иметь вид

Составляем симплекс – таблицу:

Таблица 1.2

		c j базиса

Опорный план не является оптимальным, т.к. в строке оценок есть отрицательные элементы = - 3 и = - 2. Выбираем разрешающий столбец – первый, т.к. ему соответствует минимальная из отрицательных оценок = - 3. Для всех положительных элементов первого столбца вычисляем отношение . Находим минимальное из этих отношений: . Оно соответствует второй строке, следовательно, она будет разрешающей. Таким образом, разрешающий элемент показывает, что из базиса выводится переменная x 4 , а вместо неё в базисе будет переменная x 1 . Заполняем новую симплекс – таблицу (табл. 1.3). Для этого превращаем первый столбец в единичный. Умножаем вторую строку на (-1/2) и складываем с первой, записываем результат в первую строку новой симплекс – таблицы; аналогично, умножаем вторую строку на (1/2) и складываем с третьей; разрешающую строку делим на 2; четвертую переписываем без изменений.

Симплексный метод. Алгоритм. Признак оптимальности опорного плана.

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

Рис. Геометрическая интерпретация идеи симплекс-метода

в случае двух (рис а) и трех (рис б) переменных.

Симплекс – это выпуклый многоугольник в n – мерном пространстве с n+1 вершинами, не лежащими в одной гиперплоскости (гиперплоскость делит пространство на 2 полупространства).

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

Базисное решение – это одно из допустимых решений, находящихся в ОДР.

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

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

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

1. Построить математическую модель задачи.

1. Преобразовать полученную математическую модель в каноническую форму, у которой: правые части условий неотрицательны; условия являются равенствами (при необходимости ввести искусственные переменные).
2. Построить симплекс таблицу и найти начальный опорный план решения задачи. Множество переменных, которые являются базисными , принимаются за начальное базисное решение. Значения этих переменных равны свободным членам. Все остальные переменные равны нулю.
3. Проверка базисного решения на оптимальность осуществляется с помощью специальных оценок коэффициентов целевой функции (смотреть последнюю строку таблицы). Если задача решается на max, то все оценки должны быть неотрицательными, если на min, то все оценки должны быть неположительные.
4. Переход к новому базисному решению. Очевидно, что в оптимальный план должна быть введена такая переменная, которая в наибольшей степени увеличит целевую функцию. При решении задач на max в оптимальный план вводится продукция, производство которой наиболее выгодно. Это определяется по max положительному значению оценки коэффициентов целевой функции. Столбец таблицы, который содержит эту оценку, называется генеральным столбцом. Если хотя бы один элемент столбца положительный, то отыскивается генеральная строка (в противном случае задача не имеет оптимального решения). Если в этом столбце есть нули, то нужно брать другой столбец. Для отыскания генеральной строки все свободные члены (ресурсы) делятся на соответствующие элементы генерального столбца (норма расхода ресурса на единицу изделия). Из полученных результатов выбирается наименьший, соответствующая строка называется генеральной. Она соответствует ресурсу, который ограничивает производство на данном шаге. Элемент симплекс таблицы, находящийся на пересечении генеральной строки и столбца, называется генеральный элемент. Все элементы генеральной строки, включая свободный член, делятся на генеральный элемент. В результате генеральный элемент становится равным 1. Далее необходимо чтобы все другие элементы генерального столбца стали равными 0. генеральный столбец должен стать единичным. Все строки кроме генеральной преобразуют следующим образом: полученные элементы новой строки умножим на соответствующие элементы генерального столбца, и полученное произведение вычитаем из элементов старой строки. Значение новых базисных переменных получим в соответствующих ячейках столбца свободных членов (правило прямоугольников).
5. Полученное базисное решение проверяется на оптимальность (шаг №4). Если оно оптимально, то вычисления прекращаются, в противном случае находится новое базисное решение (шаг №5).

Признак оптимальности опорного плана

— Если решаем задачу на max то все оценки должны быть неотрицательными.

— Если решаем задачу на min то все оценки должны быть неположительными.

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

— Θ (столбец симплекс-отношений) не рисуется для строчек с отрицательными и нулевыми значениями. Из всех θ выбираем наименьшее, так делается всегда неважно на min или на max исходная задача.

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