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

max{F(x)=∑c i x i |∑a ji x i =b j , j=1,m ; x i ≥0}.

В ограничения и в функцию цели вводят так называемые «искусственные переменные» R j следующим образом:

∑a ji x+R j =b j , j=1,m ;F(x)=∑c i x i -M∑R j

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

Симплекс-таблица, которая составляется в процессе решения, используя метод искусственного базиса, называется расширенной. Она отличается от обычной тем, что содержит две строки для функции цели: одна – для составляющей F = ∑c i x i , а другая – для составляющей M ∑R j Рассмотрим процедуру решения задачи на конкретном примере.

Пример 1. Найти максимум функции F(x) = -x 1 + 2x 2 - x 3 при ограничениях:

2x 1 +3x 2 +x 3 =3,

x 1 ≥0, x 2 ≥0, x 3 ≥0 .

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

2x 1 + 3x 2 + x 3 + R 1 = 3;

x 1 + 3x 3 + R 2 = 2 ;

Функция цели F(x)-M ∑R j = -x 1 + 2x 2 - x 3 - M(R 1 +R 2).

Выразим сумму R 1 + R 2 из системы ограничений: R 1 + R 2 = 5 - 3x 1 - 3x 2 - 4x 3 , тогда F(x) = -x 1 + 2x 2 - x 3 - M(5 - 3x 1 - 3x 2 - 4x 3) .

При составлении первой симплекс-таблицы (табл. 1) будем полагать, что исходные переменные x 1 , x 2 , x 3 являются небазисными, а введенные искусственные переменные – базисными. В задачах максимизации знак коэффициентов при небазисных переменных в F- и M-строках изменяется на противоположный. Знак постоянной величины в M-строке не изменяется. Оптимизация проводится сначала по M-строке. Выбор ведущих столбца и строки, все симплексные преобразования при испльзовании метода искусственного базиса осуществляются как в обычном симплекс-методе.

Максимальный по абсолютному значению отрицательный коэффициент (-4) определяет ведущий столбец и переменную x 3 , которая перейдет в базис. Минимальное симплексное отношение (2/3) соответствует второй строке таблицы, следовательно, переменная R 2 должна быть из базиса исключена. Ведущий элемент обведен контуром.

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

x 1 =0; x 2 =7/9; F max =8/9.

Если при устранении M-строки решение не является оптимальным, то процедура оптимизации продолжается и выполняется обычным симплекс-методом. Рассмотрим пример, в котором присутствуют ограничения всех типов:≤,=,≥

Пример 2 . Найти минимальное значение функции F(x) = 2x 1 + 3x 2 - x 3 при следующих ограничениях

2x 1 +x 2 -3x 3 ≥6,

x 1 -x 2 +2x 3 =4,

x 1 +x 2 +x 3 ≤5,

x 1 ≥0, x 2 ≥0, x 3 ≥0 .

Домножим первое из ограничений на (-1) и введем в ограничения дополнительные переменные x 4 , x 5 и искусственную переменную R следующим образом:

2x 1 -x 2 +3x 3 +x 4 =-6,

x 1 -x 2 +2x 3 +R=4,

x 1 +x 2 +x 3 +x 5 =5,

Пусть x 4 , R и x 5 – базисные переменные, а x 1 , x 2 , x 3 – небазисные. Функция цели F(x)=F(x)+M∑R=2x 1 +3x 2 -x 3 +M(4-x 1 +x 2 -2x 3).

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

Выберем ведущий столбец и строку в соответствии с шагом 2 алгоритма решения. После пересчета получим табл. 5. Оптимизация решения в методе искусственного базиса (шаг 5 алгоритма) осуществляется вначале по M-строке. В результате x 3 введем в базис, а переменную R исключим из рассмотрения, сократив количество столбцов. После пересчета получим табл. 6, которая соответствует оптимальному решению задачи.

Таблица 4

базисные переменные	Свободные члены	Небазисные переменные
		x 1	x 2	x 3
x 4	-6	-2	-1	3
R	4	1	-1	2
x 5	5	1	1	1
F	0	2	3	-1
M	-4	-1	1	-2

Таблица 5

базисные переменные	Свободные члены	Небазисные переменные
		x 4	x 2	x 3
x 1	3	-1/2	1/2	-3/2
R	1	1/2	-3/2	7/2
x 5	2	1/2	1/2	5/2
F	-6	1	2	2
M	-1	-1/2	3/2	-7/2

Таблица 6

Искомый минимум функции F(x) равен свободному члену F-строки табл. 6, взятому с обратным знаком, так как min F(x) = -max(-F(x)); x 4 = x 2 = 0;

x 1 =24/7; x 3 =2/7; x 5 =9/7; F min =46/7;

Пусть решаем ЗЛП в виде

В этом случае общая схема симплекс-метода претерпевает некоторые изменения. А именно:

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

2) Если все относительные оценки (нижняя строка этой таблицы) неотрицательны, то построено оптимальное опорное решение.

3) Если существует отрицательная оценка и соответствующий ей столбец (разрешающий) состоит из неположительных элементов, то имеет место неразрешимость целевой функции Z (X ), то есть max Z (X ) ®+¥.

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

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

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

Пусть задана задача ЛП в канонической форме, то есть имеет вид (2.1.1), и в ней отсутствует единичный базис. К этой задаче строим вспомогательную задачу (ВЗ):

Здесь w 1 , w 2 ,…, w m – искусственные переменные. Запишем ограничения в векторном виде: A 1 x 1 +A 2 x 2 +…+A n x n +A n +1 w 1 +…+A n + m w m =B , где , , …, , , , …, , . Таким образом, вектора , , …, образуют единичный базис в R m , и все искусственные переменные соответствующие этим векторам будут базисными. Далее строится обычная симплекс-таблица. Если ВЗ не имеет решения в силу неограниченности целевой функции, то исходная задача также не имеет решения по той же причине. Пусть в результате знакомых по симплекс-методу необходимых преобразований получили оптимальную симплекс-таблицу к ВЗ. Очевидно, что максимальное значение целевой функции ВЗ равно 0, то есть max F =0. Если же maxF <0, то исходная задача ЛП не имеет решения в силу несовместности системы ограничений. Предположим, что max F =0. Тогда возможны такие ситуации:

1) все искусственные переменные стали свободными и были исключены из таблицы. В этом случае вычеркиваем столбцы, соответствующие искусственным переменным и последнюю строку. Вместо неё приписываем новую строку оценок, но с использованием исходной целевой функции Z (X ). Тем самым получена начальная симплекс-таблица для исходной задачи ЛП, к которой применяем симплекс-метод;

2) в оптимальном решении ВЗ хотя бы одна искусственная переменная осталась базисной. Тогда:

а) либо все числа в строках, соответствующих оставшимся базисным искусственным переменным, равны 0;

б) либо есть хоть одно отличное от 0.

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

Заметим, что если среди векторов A j , j =1,2,…,n , были вектора, которые могли бы войти в базис, то искусственные переменные вводят только в те уравнения системы ограничений, в которых отсутствует базисная переменная.

Пример. Максимизировать функцию Z =x 1 +2x 2 -2x 3 при ограничениях

Решение. Преобразуем исходную задачу линейного программирования к канонической (см. (2.1.1). Для этого введём в ограничения дополнительные неотрицательные переменные. А именно, в первое неравенство – переменную x 4 со знаком «+», во второе – x 5 со знаком «-» (см. §2.2). Система ограничений примет вид:

Эту систему запишем в векторной форме: A 1 x 1 +A 2 x 2 +A 3 x 3 +A 4 x 4 +A 5 x 5 =B , где

Очевидно, что в данной системе ограничений отсутствует единичный базис. Это означает, что среди векторов A j нет трёх необходимых единичных векторов, которые должны образовывать базис в R 3 . Однако заметим, что вектор A 4 является частью базиса. Ему соответствует базисная переменная x 4 . Необходимо найти ещё два единичных вектора. Для этого применим метод искусственного базиса. Введём искусственные переменные в те уравнения ограничений, в которых не присутствует базисная переменная x 4 и построим следующую вспомогательную задачу (ВЗ):

F =-w 1 -w 2 ®max

где w 1 , w 2 – искусственные переменные. Система ограничений ВЗ в векторном виде имеет вид: A 1 x 1 +A 2 x 2 +A 3 x 3 +A 4 x 4 +A 5 x 5 +A 6 w 1 +A 7 w 2 =B , где вектора A j , j =1,2,3,4,5 определяются также, как и выше, а и . Таким образом, вектора A 4 , A 6 , A 7 образуют базис в R 3 и им соответствуют базисные переменные (БП) – x 4 , w 1 , w 2 . Все остальные переменные, а именно x 1 , x 2 , x 3 , x 5 объявляются свободными (СП). Далее к ВЗ применяем обычный симплекс-метод. Как и раньше, см. §5.1, начальный опорный план получается, если присвоить свободным переменным значения, равные нулю. При этом базисные переменные принимают значения, равные числам в соответствующей строке столбца свободных коэффициентов В , то есть x 1 =x 2 =x 3 =x 5 =0¸ а x 4 =8, w 1 =4, w 2 =12. Строим симплекс-таблицу, соответствующую начальному опорному плану:

СП БП.	x 1	x 2	x 3	x 5	B
x 4		-3
w 1				-1
w 2		-2
F	-4		-3		-16

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

СП БП.	w 1	x 2	x 3	w 2	B
x 4	-0,5	-3	-0,5	-0,5
x 1	0,25		0,75	0,25
x 5	-0,75	-2
F

Эта таблица будет оптимальной для ВЗ. При этом все искусственные переменные стали свободными и max F =0. Вычеркивая столбцы, соответствующие искусственным переменным и последнюю строку, и приписывая новую строку оценок с использованием исходной целевой функции Z (X ), получим начальную симплекс-таблицу для исходной задачи ЛП:

СП БП.	x 2	x 3	B
x 4	-3	-0,5
x 1		0,75
x 5	-2
Z	-2	2,75

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

Пример. Минимизировать функцию при ограничениях

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

Базисное решение (допустимый план) будет иметь вид: , а , , w 1 =10, w 2 =5. Строим симплекс-таблицу к ВЗ, соответствующую начальному опорному плану:

СП БП.	x 1	x 2	x 3	x 4	B
w 1			-1
w 2				-1
x 5
x 6	-1
F	-1	-1			-15

Проводя преобразования по методу Жордана-Гаусса, на втором шаге будем иметь оптимальную симплекс-таблицу ВЗ (5.2.2). Вычеркивая столбцы, соответствующие искусственным переменным и последнюю строку, и приписывая новую строку оценок с использованием целевой функции Z 1 (X ), получим начальную симплекс-таблицу для задачи (5.2.1).

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

Пусть задача приведена к каноническому виду (1.6), в котором в некоторых уравнениях, скажем в i 1 -м, i 2 -м, …, i s -м, явно не выделяются базисные переменные. Добавим в эти уравнения искусственные переменныеx m +1 , x m +2 , …, x m + s , а в целевую функцию - слагаемые ±Mx m +1 , ±Mx m +2 , …, ±Mx m + s , где M >>1 (M - достаточно большое положительное число) причём «±» - это «+», если решается задача на min, и «±» - это «-», если решается задача на max. Получается новая задача, которая называется дополнительной или вспомогательной .

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

c 1 x 1 +c 2 x 2 +…+c n x n +Mx n + m +1 +Mx n + m +2 +…+Mx n +2 m ®min

Аналогично, если задача (2.1) решается на max и придётся вводить искусственные переменные во все ограничения, то получаем следующую вспомогательную задачу:

c 1 x 1 +c 2 x 2 +…+c n x n -Mx n +1 -Mx n +2 -…-Mx n + m ®max

(5.1)

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

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

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

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

3. Решить вспомогательную задачу, и если ( , , …, , , …, ) - оптимальное решение вспомогательной задачи, где x 1 , x 2 , …, x m - основные и дополнительные переменные (из задачи в каноническом виде), x m +1 , x m +2 , …, x m + s - искусственные переменные то ( , , …, ) - решение задачи в каноническом виде. Оптимальное значение целевой функции вспомогательной задачи равно оптимальному значению исходной задачи.

При этом к вспомогательной задаче применяется обычный симплекс-метод с некоторыми своими особенностями:

1. Так как целевая функция вспомогательной задачи имеет слагаемые с коэффициентами ±M , то оценки D k имеют вид ± M , причём M - достаточно большое число. Поэтому при ≠0 знак D k фактически определяется знаком при . В связи с этим в симплекс-таблице на начальном этапе (пока в базис входят искусственные переменные) вместо одной строки D k записывают две строки и , и при применении критерия оптимальности ориентируются только на строку .

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

3. После того, как все искусственные переменные будут выведены из базиса, коэффициенты D k при M будут равны нулю, в таблице остаётся только строка =D k .

Пример. Решить пример из предыдущего параграфа методом искусственного базиса.

Решение. Напоминаем задачу:

3x 1 +x 2 +2x 3 ® max(min)

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

3x 1 +x 2 +2x 3 ® max(min)

2. В базис в виде единичного вектора входит только вектор при x 4 , то есть переменная во втором уравнении. В первое и третье уравнения системы ограничений вводим искусственные переменные x 6 и x 7:

В целевую функцию они войдут с коэффициентами M или -M в зависимости от того, решается задача на min или на max.

Решим задачу на максимум. Тогда вспомогательная задача - следующая:

3x 1 +x 2 +2x 3 -Mx 6 -Mx 7 ® max

3. Решаем полученную вспомогательную задачу с применением симплекс-таблиц:

Базис

С б

Своб. чл.

-3

-M

-M

q 2

q 3

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 6

-M

-1

min

x 4

-

x 7

-M

-1

-1

-2

-8

-2

-3

Здесь D 2 =-2M -1, D 3 =-3M -2. Коэффициенты при M записаны в строке . Имеем, что D 2 <0 и D 3 <0, то есть для переменных x 2 и x 3 нарушается критерий оптимальности. Поэтому в базис будем вводить x 2 или x 3 . Какую именно из этих переменных, и вместо какой из искусственных (вместо x 6 или вместо x 7), определяем с помощью столбцов q 2 и q 3 . На пересечении столбца q 2 и строк и числа соответственно 2 и 4 означают, что в случае включения в базис x 2 значение функции возрастёт на -q 2 D 2 =4M +2, а в случае включения в базис x 3 значение функции возрастёт на -q 3 D 3 =3M +2<-q 2 D 2 . Поэтому в базис включаем x 2 (что обеспечивает большее возрастание функции и в конечном итоге ускоряет процесс решения задачи). Так как min =2 достигается в строке x 6 , то из базиса исключаем x 6 . Строим новую симплекс-таблицу, в который уже столбец с искусственной переменной x 6 отсутствует (вычеркнут), так как искусственная переменная x 6 из дальнейшего процесса исключается. В новой таблице коэффициент при x 2 в первой строке (которая теперь соответствует новой базисной переменной x 2) равен 1, а во второй равен нулю. Поэтому первые две строки в новую таблицу переписываем из старой. Для того, чтобы в строке x 7 при x 2 получить 0, из строки x 7 в старой таблице вычитаем новую первую. Получаем следующую, очередную, таблицу:

Базис

С б

Своб. чл.

-3

-M

-M

q 1

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 2

-1

-

x 4

x 7

-M

-1

-1

min

-4

-2

Так как D k <0 только для одного значения k =1, а именно, D 1 =-2M +2<0 (напоминаем, что M - достаточно большое число, так что -2M <2 и D 1 <0), то ищем только отношения q 1 . Минимум этих отношений достигается в строке x 7: min =2. Поэтому искусственная переменная исключается из базиса, а вместо неё в базис включается x 1 .

Искусственные переменные теперь исключены из базиса. Поэтому дальше работаем с обычной симплекс-таблицей, в которой новая третья строка (соответствующая переменной x 1) получается делением старой третьей строки на 2. Затем эту новую третью прибавляем к старой первой и вычитаем из старой второй. В результате в новой таблице в столбце x 1 появятся соответственно 0, 0 и 1:

Базис	С б	Своб. чл.	-3
x 1	x 2	x 3	x 4	x 5
x 2					3/2		-1/2
x 4					3/2		1/2
x 7	-3				-1/2		-1/2
D k	-2

В полученной таблице D k ³0 для всех k X 0 =(2; 4; 0) является оптимальным решением, при котором значение целевой функции равно -2 (x 4 в окончательном ответе не учитывается, так как она является дополнительной переменной, и не входит в первоначальную задачу).

Решим задачу на минимум (min). Тогда вспомогательная задача - следующая:

3x 1 +x 2 +2x 3 -Mx 6 -Mx 7 ® max

Как и выше, решаем полученную вспомогательную задачу с применением симплекс-таблицы:

Базис

С б

Своб. чл.

-3

M

M

q 2

q 3

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 6

M

-1

min

x 4

-

x 7

M

-1

-1

-2

-1

Критерий оптимальности нарушается для переменных x 2 и x 3: D 2 =2M -1>0, D 3 =3M -2>0. Так как -q 2 D 2 =-4M +2 по абсолютной величине превосходит -q 3 D 3 =-3M +2, то в базис включаем x 2 . При этом min =2 достигается в строке x 6 , и из базиса исключаем x 6 . Переход к новой таблице аналогичен переходу при решении задачи на max:

Базис

С б

Своб. чл.

-3

-M

-M

q 1

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 2

-1

-

x 4

x 7

-M

-1

-1

min

-1

-1

Теперь D 1 >0. Поэтому переход к новой таблице аналогичен соответствующему переходу при решении задачи на max: в базис вводится x 1 вместо x 7:

Базис	С б	Своб. чл.	-3					q 3	q 5
x 1	x 2	x 3	x 4	x 5
x 2					3/2		-1/2	8/3	-
x 4					3/2		1/2	4/3
x 7	-3				-1/2		-1/2	-	-
D k	-2						-4/3	-4

Имеем D 3 =1>0 и D 5 =1>0. Так как |-q 5 D 5 |=|-q 3 D 3 |, то вводим в базис x 5 (вместо x 4): сначала умножаем 2-ю строку на 2, а затем новую вторую строку, умноженную на ½, прибавляем к первой и третьей (фактически вторую старую прибавляем к первой и третьей):

В полученной таблице D k £0 для всех k =1, 2, …, 5, то есть критерий оптимальности выполнен. Поэтому X 0 =(4; 6; 0) является оптимальным решением, при котором значение целевой функции равно -6.

Ответ: F min =-6, минимум достигается в точке X 2 =(4; 6; 0);

F max =-2, максимум достигается в точке X 1 =(2; 4; 0).

5.2. Упражнение. Решить соответствующие задачи линейного программирования из Упражнения 1.3 методом искусственного базиса.

Теория двойственности

Алгоритм метода искусственного базиса имеет следующие особенности:

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

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

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

4. Переход от решения расширенной задачи к решению исходной задачи производится с использованием доказанных выше теорем 4.1-4.3.

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

.

Решение . Составляем расширенную задачу. В левые части уравнений системы ограничений вводим неотрицательные искусственные переменные с коэффициентом (всегда) +1. Удобно справа от уравнений записать вводимые искусственные переменные. В первое уравнение вводим , во второе — . Данная задача — задача на нахождение максимума, поэтому и в целевую функцию вводятся с коэффициентом — М . Получаем

Задача имеет начальное опорное решение с единичным базисом .

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

.
.

Записываем исходные данные в симплексную таблицу (табл. 4.6).

Т а б л и ц а 4.6

При этом оценки и для удобства вычислений записываем в две строки: в первую — слагаемые , не зависящие от М , во вторую — слагаемые , зависящие от М . Значения удобно указывать без М , имея в виду однако, что оно там присутствует.

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

В третьем столбце " " за разрешающий элемент выбираем коэффициент 1 во второй строке и выполняем преобразование Жордана.

Вектор , выводимый из базиса, исключаем из рассмотрения (вычеркиваем). Получаем опорное решение с базисом (табл. 4.7). Решение не является оптимальным так как имеется отрицательная оценка = — 1.

Т а б л и ц а 4.7

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

Т а б л и ц а 4.8

Данное опорное решение является единственным оптимальным решением расширенной задачи, так как в задаче на максимум оценки для всех векторов, не входящих в базис, положительны. По теореме 4.1 исходная задача также имеет оптимальное решение, которое получается из оптимального решения расширенной задачи отбрасыванием нулевых искусственных переменных, т. е. Х * = (0,0,6,2).

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

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

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

.

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

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

С единичным базисом , . Вычисляем оценки векторов условий по базису опорного решения и записываем в симплексную таблицу так же, как в предыдущем примере. Решение не является оптимальным, так как в задаче на минимум векторы и имеют положительные оценки . Улучшаем опорные решения. Каждому опорному решению соответствует своя таблица. Все таблицы можно записать друг под другом, объединив в единую таблицу (табл. 4.9).

Т а б л и ц а 4.9

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

Переходим к четвертому опорному (оптимальному) решению

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

Ответ : при , , , .

Слово симплекс

Слово симплекс английскими буквами(транслитом) — simpleks

Слово симплекс состоит из 8 букв: е и к л м п с с

Значения слова симплекс. Что такое симплекс?

Симплекс

Симплекс (от лат. simplex - простой) (математический), простейший выпуклый многогранник данного числа измерений n. При n = 3 трёхмерный С. представляет собой произвольный, в том числе неправильный, тетраэдр.

БСЭ. - 1969-1978

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

slovar-lopatnikov.ru

СИМПЛЕКС - выпуклый многоугольник в n-мерном пространстве с n+1 вершинами, не лежащими в одной гиперплоскости. С. выделены в отдельный класс потому, что в n-мерном пространстве n точек всегда лежат в одной гиперплоскости.

Лопатников. - 2003

Саб симплекс

Саб симплекс Способ применения и дозы: Внутрь, во время или после еды и, при необходимости, перед сном. Перед применением следует активно встряхнуть флакон.

Решение ЗЛП симплекс методом с искусственным базисом

Чтобы суспензия начала поступать из пипетки…

Саб симплексДействующее вещество ›› Симетикон* (Simethicone*) Латинское название Sab simplex АТХ:›› A02DA Ветрогонные препараты Фармакологическая группа…

Словарь медицинских препаратов. — 2005

САБ® СИМПЛЕКС (SAB® SIMPLEX) Суспензия для приема внутрь от белого до серо-белого цвета, слегка вязкая, с характерным фруктовым (ванильно-малиновым) запахом. 100 мл симетикон 6.919 г…

ШОКЕ СИМПЛЕКС

ШОКЕ СИМПЛЕКС — непустое компактное выпуклое множество Xв локально выпуклом пространстве E, обладающее следующим свойством: при вложении Ев качестве гиперплоскости в пространство проектирующий конус.

Шеффилд-Симплекс

«Шеффилд-Симплекс» (англ. Sheffield-Simplex) - лёгкий пулемётный бронеавтомобиль Вооружённых сил Российской империи. Разработан британской фирмой «Sheffield-Simplex» на базе шасси собственного легкового автомобиля…

ru.wikipedia.org

Нордитропин Симплекс

Нордитропин Симплекс Показания: Задержка роста у детей вследствие недостаточности гормона роста или хронической почечной недостаточности (в препубертатном возрасте), синдрома Шерешевского - Тернера…

НОРДИТРОПИН® СИМПЛЕКС® (NORDITROPIN SimpleXx) Раствор для п/к введения 1.5 мл (1 картридж) соматропин 10 мг 1.5 мл — картриджи (1) — упаковки ячейковые контурные (1) — пачки картонные.

Справочник лекарственных препаратов "Видаль"

СТАНДАРТНЫЙ СИМПЛЕКС

СТАНДАРТНЫЙ СИМПЛЕКС — 1) С. с.- симплекс размерности пв пространстве с вершинами в точках е i=(0,…, 1,…, 0), i=0,…, п(единица стоит на i-м месте), т. е.

Математическая энциклопедия. — 1977-1985

Двойственный симплекс-метод

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

ru.wikipedia.org

Русский язык

Си́мпле́кс/.

Морфемно-орфографический словарь. - 2002

Поиск Лекций

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

Найти минимум функции F=-2×1+3×2 — 6×3 — x4 при условиях

Решение. Запишем данную задачу в форме основной задачи: найти максимум функции F1=2×1 – 3×2 + 6×3 + x4 при условиях

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

А1 = А2 = А 3= А 4= А 5= А 6=

Среди векторов А1 ,…, А 6 только два единичных (А 4 и А 5). Поэтому в левую часть третьего уравнения системы ограничений добавим дополнительную неотрицательную переменную x 7 и рассмотрим расширенную задачу, состоящую в максимизации функции

F=2×1 – 3×2 + 6×3 + x4 – Mx7

при условиях

Расширенная задача имеет опорный план X=(0; 0; 0; 24; 22; 0; 10), определяемый системой трех единичных векторов: А 4 , А5 , А7 .

Таблица 1

i	Базис	Сσ	А0	-3	—M
А1	А2	А3	А4	А5	А6	P7
А4	-2
А5
А7	—M	-1	-1
m +1			-8
m +2			-10	-1	-2

Составляем таблицу (1) I итерации, содержащую пять строк. Для заполнения 4-й и 5-й строк находим F 0 и значения разностей zj – cj (j= ):

F 0 = 24–10M;

z1–c1 = 0–M ;

z2–c2 = 4+M ;

z3–c3 = –8–2M ;

z4–c4 =0+M ;

z5–c5 =0+M ;

z6–c6 = 0+M ;

z7–c7 =0+M ;

Значения F 0 и zj–cj состоят из двух слагаемых, одно из которых содержит M , а другое – нет.

Для удобства итерационного процесса число, состоящее при M , записываем в 5-й строке, а слагаемое, которое не содержит M ,– в 4-й строке.

В 5-й строке табл.1 в столбцах векторов Аj (j = ) имеется два отрицательных числа (-1 и -2). Наличие этих чисел говорит о том, что данный опорный план расширенной задачи не является оптимальным. Переходим к новому опорному плану расширенной задачи.

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

В базис вводим вектор А3 . Чтобы определить вектор, исключаемый из базиса, находим θ=min(22/4; 10/2)=10/2. Следовательно, вектор А7 исключаем из базиса. Этот вектор не имеет смысла вводить ни в один из последующих базисов, поэтому в дальнейшем столбец данного вектора не заполняется (табл. 2 и 3).

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

Таблица2

i	Базис	Сσ	А0	-3
А1	А2	А3	А4	А5	А6
А4	-1
А5	-1
А3	1/2	-1/2	-1/2
m +1			-4

Как видно из табл. 2, для исходной задачи опорным является план Х =(0;0;5;34;2).

Проверим его на оптимальность. Для этого рассмотрим элементы 4-й строки. В этой строке в столбце вектора А6 имеется отрицательное число (-4). Следовательно, данный опорный план не является оптимальным и может быть улучшен благодаря введению в базис вектора А6. Из базиса исключается вектор А5 . Составляем таблицу III итерации.

Таблица 3

В 4-й строке табл.3 среди чисел ∆j нет отрицательных. Это означает, что найденный новый опорный план исходной задачи Х *=(0; 0; 11/2; 35; 0; 1) является оптимальным. При этом плане значение линейной формы Fmax = 68.

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

©2015-2018 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Нарушение авторских прав и Нарушение персональных данных

Метод искусственного базиса (Симплекс-метод) - Пример 1

Целевая функция:

1X 1 +5X 2 +4X 3 -3X 4 →max

2X 1 +7X 2 +1X 3 +0X 4 ≤5
1X 1 +4X 2 +2X 3 +8X 4 =6
-1X 1 +0X 2 +2X 3 +5X 4 =9

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

2X 1 +7X 2 +1X 3 +0X 4 +X5=5
1X 1 +4X 2 +2X 3 +8X 4 +R1=6
-1X 1 +0X 2 +2X 3 +5X 4 +R2=9
Переходим к формированию исходной симплекс таблицы. В строку F таблицы заносятся коэффициенты целевой функции. Так как нам необходимо найти максимум целевой функции, то в таблицу заносятся коэффициенты с противоположным знаком

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

Из данных задачи составляем исходную симплекс таблицу.

	X1	X2	X3	X4	Своб член
F	-1	-5	-4	3	0
X5	2	7	1	0	5
R1	1	4	2	8	6
R2	-1	0	2	5	9
M	0	-4	-4	-13	-15

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение.В строке M имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -13 Ведущей строкой будет та для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R1, а ведущий элемент: 8.

	X1	X2	X3	Своб член
F	-1.375	-6.5	-4.75	-2.25
X5	2	7	1	5
X4	0.125	0.5	0.25	0.75
R2	-1.625	-2.5	0.75	5.25
M	1.625	2.5	-0.75	-5.25

В строке M имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -0.75 Ведущей строкой будет та для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X4, а ведущий элемент: 0.25.

	X1	X2	X4	Своб член
F	1	3	19	12
X5	1.5	5	-4	2
X3	0.5	2	4	3
R2	-2	-4	-3	3
M	2	4	3	-3

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