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

Если в системе ограничений задачи присутствуют только уравнения, а свободные члены в системе ограничений задачи являются неотрицательными, то говорят, что задача имеет канонический вид. Любая смешанная система приводится к системе уравнений добавлением дополнительных неотрицательных переменных со знаком «+» в неравенства типа «≤» и со знаком «-» в неравенства типа «≥». Поэтому для приведения к каноническому виду задачи линейного программирования поступаем следующим образом:

1) Если в системе ограничений задачи имеется ограничение с отрицательной правой частью, то умножаем его на -1.

2) Добавляем в каждое неравенство дополнительные неотрицательные переменные: со знаком «+» в неравенства типа «≤» и со знаком «-» в неравенства типа «≥».

Применительно к нашей системе: сначала умножим второе неравенство системы ограничений на (-1) (добиваемся, чтобы правые части всех нетривиальных ограничений имели знак «+»). Получаем систему ограничений

Теперь добавляем во второе и третье неравенства системы дополнительные переменные x ₄ и x ₅:

Таким образом, получаем канонический вид исходной задачи:

-3 x ₁+ x ₂+2 x ₃®max(min)

2. С помощью метода Жордана-Гаусса находим очередное опорное решение.

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

3. Из векторов условий A ₁, A ₂, …, A_n включаем в базис те, которые являются стандартными единичными (то есть те, у которых все координаты нулевые, кроме одной, которая равна 1; среди них обязательно окажутся те, которые соответствуют дополнительным переменным с положительным знаком). Соответствующие переменные будут включены в базис. Если число таких векторов условий равно m, то первоначальный опорный план построен: им является решение системы ограничений, полученное приравниванием свободных переменных к 0. В противном случае идём к пункту 2.

4. Допустим, переменная x_k пока не вошла в базис. Тогда выбираем уравнение, в котором отношение (где a_ik >0) будет минимальным. Это (i -е) уравнение будет ведущим: разделив его на коэффициент a_ik при x_k, добиваемся, чтобы коэффициент при x_k стал равным 1, а из остальных уравнений x_k исключаем (применяем метод Жордана-Гаусса). Процесс продолжаем до тех пор, пока базис не будет содержать m переменных.

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

Применительно к нашей задаче прежде всего замечаем, что дополнительная переменная x ₄ входит только во второе уравнение. И она уже в базисе. Так как для x ₂ min =2 достигается в первом уравнении (при определении этого min второе уравнение не участвует, так как коэффициент при x ₂ в нём равен 0), то x ₂ включаем в базис, исключив его из третьего уравнения (для этого первое уравнение вычитаем из третьего):

Две базисные переменные из первого и второго уравнений выбраны. Осталось выбрать третью базисную переменную из третьего уравнения. Переменные x ₃ и x ₅ для этого не годятся, так как коэффициенты при них отрицательны. Остаётся только x ₁. Для того, чтобы её ввести в базис необходимо, чтобы минимум отношений свободных членов к положительным коэффициентам достигался в третьем уравнении. Так оно и есть: min =2 достигается в третьем уравнении. Поэтому третье уравнение делим на 2, затем прибавляем его к первому и вычитаем из второго:

(*)

Таким образом, при x ₃=0, x ₅=0 имеем x ₁=2, x ₂=4, x ₄=2 и X ₁=(2; 4; 0; 2; 0) - первоначальный опорный план.

3. Проверим на оптимальность очередное опорное решение. Если оно оптимальное, то задача решена. В противном случае перейдём к пункту 2.

Проверка опорного плана на оптимальность проводится по следующей схеме:

3. Находятся оценки D _k = C_бA_k - c_k = - c_k для всех k =0, 1, …, n. При этом D₀ - это значение целевой функции при данном опорном плане, и D _k =0 для всех базисных переменных x_k (то есть последние вычислять необязательно, а достаточно сразу положить D _k =0).

4. Если условие оптимальности опорного плана выполнено (D _k ³0 для всех k =1, …, n при поиске максимума, D _k £0 для всех k =1, …, n при поиске минимума), то задача решена. В противном случае переходят к другому опорному плану.

Данные вычислений принято вносить в так называемые симплекс таблицы вида

Базис	Сб	Своб. члены	c 1	c 2	…	cn	q 1	q 2	…	qn
A 1	A 2	…	An
		b 1	a 11	a 12	…	a 1 n			…
		b 2	a 21	a 22	…	a 2 n			…
…	…	…	…	…	…	…	…	…	…	…
		bm	am 1	am 2	…	amn			…
D k	D1	D1	D2	…	D n	- q 1D1	- q 2D2	…	- qn D n

 

В нашем примере мы можем заполнить эту таблицу с учётом (*):

Базис

Сб

Своб. члены

-3

q 1

q 2

q 3

q 4

q 5

x 1

x 2

x 3

x 4

x 5

x 2

3/2

-1/2

x 4

3/2

1/2

x 1

-3

-1/2

-1/2

D k

Итак, для проверки оптимальности опорного плана вычисляем D _k = C_бA_k - c_k для k - индексов свободных переменных, заполняя соответствующие клетки таблицы:

 

Базис

Сб

Своб. члены

-3

q 1

q 2

q 3

q 4

q 5

x 1

x 2

x 3

x 4

x 5

x 2

3/2

-1/2

x 4

3/2

1/2

x 1

-3

-1/2

-1/2

D k

-2

Приведём сами вычисления: имеем

D₃= C_бA ₃- c ₃=(1, 0, -3)× -2=1× +0× +(-3)× -2=1,

то есть D₃=1≥0. В частности, в X ₁ минимум не достигается.

D₅= C_бA ₅- c ₅=(1, 0, -3)× -0=1× +0× +(-3)× =1,

то есть D₅=1≥0. Так как D _k ≥0 для всех k =1, 2, 3, 4, 5, то в X ₁ достигается максимум целевой функции, который равен D₀= CX =-3×2+4+2×0=-2. Минимум в этой точке не достигается. Значит, необходимо перейти к другому опорному плану.

Переход к другому опорному плану проводится по следующей схеме:

3. Для всех D _k, для которых нарушается условие оптимальности задачи, вычисляются q_k = , а по ним - величины - q_k D _k.

4. Выбирается x_k такой, что |- q_k D _k | является максимальным. Эту x_k и вводим в базис, выводя из него x_i, в которой достигается минимальное q_k, по методу Жордана-Гаусса.

В нашем примере для D₃ и D₅, для которых нарушается условие оптимальности, вычислим q ₃ и q ₅, а по ним - величины - q ₃D₃ и - q ₅D₅:

q ₃= = = = (достигается при x ₄),

- q ₃D₃=- ×1=- ,

q ₅= = =4, (достигается снова при x ₄, то есть в любом случае x ₄ будем выводить из базиса),

- q ₅D₅=-4×1=-4.

Наша таблица окончательно принимает вид

Базис	Сб	Своб. члены	-3					q 1	q 2	q 3	q 4	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 1	-3				-1/2		-1/2	-	-	-	-	-
D k	-2						-	-	-4/3	-	-4

Так как |- q ₅D₅|=|-4|>|- |=|- q ₃D₃|, то в базис будем вводить x ₅ вместо x ₄. Для этого вторую строку (второе уравнение) прибавляем к первой и третьей (первому и третьему уравнениям), и умножаем его на 2:

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

Получили новый опорный план X ₂=(4; 6; 0; 0; 4). Находим для неё оценки D _k для всех k =1, 2, 3, 4, 5:

Базис	Сб	Своб. члены	-3
x 1	x 2	x 3	x 4	x 5
x 2
x 5
x 1	-3
D k	-6			-2	-2

 

Таким образом, D₃=-2<0, D₄=-2<0, то есть D _k ≤0 для всех k =1, 2, 3, 4, 5. Значит, X ₂ - оптимальное решение задачи с точки зрения минимизации. В нём CX =-3×4+6+2×0=-6.

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

Пусть задача приведена к каноническому виду, в котором в некоторых уравнениях, скажем в i ₁-м, i ₂-м, …, 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. Получается новая задача, которая называется дополнительной или вспомогательной.

Алгоритм метода - следующий:

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

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

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

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

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

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

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

Применяем к нашей задаче описанный алгоритм:

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

-3 x ₁+ x ₂+2 x ₃ ® max(min)

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

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

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

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

 

Базис

С б

Своб. чл.

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

Искусственные переменные теперь исключены из базиса. Поэтому дальше работаем с обычной симплекс-таблицей, в которой новая третья строка (соответствующая переменной x ₁) получается делением старой третьей строки на 2. Затем эту новую третью прибавляем к старой первой и вычитаем из старой второй. В результате в новой таблице в столбце x ₁ появятся соответственно 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 =1, 2, …, 5, то есть критерий оптимальности выполнен. Поэтому X ₀=(2; 4; 0) является оптимальным решением, при котором значение целевой функции равно -2 (x ₄ в окончательном ответе не учитывается, так как она является дополнительной переменной, и не входит в первоначальную задачу).

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

-3 x ₁+ x ₂+2 x ₃- Mx ₆- Mx ₇ ® 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 ₂ и x ₃: D₂=2 M -1>0, D₃=3 M -2>0. Так как - q ₂D₂=-4 M +2 по абсолютной величине превосходит - q ₃D₃=-3 M +2, то в базис включаем x ₂. При этом min =2 достигается в строке x ₆, и из базиса исключаем x ₆. Переход к новой таблице аналогичен переходу при решении задачи на 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₁>0. Поэтому переход к новой таблице аналогичен соответствующему переходу при решении задачи на max: в базис вводится x ₁ вместо x ₇:

Базис	С б	Своб. чл.	-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₃=1>0 и D₅=1>0. Так как |- q ₅D₅|=|- q ₃D₃|, то вводим в базис x ₅ (вместо x ₄): сначала умножаем 2-ю строку на 2, а затем новую вторую строку, умноженную на ½, прибавляем к первой и третьей (фактически вторую старую прибавляем к первой и третьей):

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

 

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

2) Несимметричная пара двойственных задач удовлетворяет следующим условиям:

1. Матрицы систем ограничений задач транспонированы по отношению к друг другу.

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

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

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

5. Если целевая функция задачи максимизируется, то знаки неравенств в ограничениях задачи имеют вид «£», а если минимизируется, то имеют вид «³».

6. Во всех ограничениях задач свободные члены находятся в правой части, а члены с переменными - в левой.

Условия 1 - 6 называются условиями двойственности.

Применительно к нашей задаче сначала составим двойственную к задаче на max:

-3 x ₁+ x ₂+2 x ₃ ® max

Согласно условию 5 для пары несимметричных двойственных задач, если целевая функция задачи максимизируется, то знаки неравенств в ограничениях задачи имеют вид «£». Поэтому умножаем второе и третье неравенства системы ограничений на -1:

-3 x ₁+ x ₂+2 x ₃ ® max

Двойственная - следующая:

2 y ₁+4 y ₂-6 y ₃ ® min

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

-3 x ₁+ x ₂+2 x ₃ ® max 2 y ₁+4 y ₂-6 y ₃ ® min

задач выполнены все условия двойственности.

1. Матрицы систем ограничений задач транспонированы по отношению к друг другу:

= .

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

3. Коэффициенты -3, 1, 2 при переменных в целевой функции первой задачи являются свободными членами соответствующих ограничений второй и, наоборот, коэффициенты 2, 4, -6 при переменных в целевой функции второй задачи являются свободными членами соответствующих ограничений первой. При этом свободные члены целевых функций задач совпадают (оба равны 0).

4. Целевые функции задач оптимизируются противоположным образом: исходная задача - на максимум, а вторая - на минимум.

5. Выдержаны требования к соответствию типа экстремума целевой функции к типам неравенств в ограничениях: если целевая функция задачи максимизируется, то знаки неравенств в ограничениях задачи имеют вид «£», а если минимизируется, то имеют вид «³».

Теперь составим двойственную к задаче на минимум (min):

-3 x ₁+ x ₂+2 x ₃ ® min

Условие 5 для исходной задачи выдержано: если целевая функция задачи минимизируется, то знаки неравенств в ограничениях задачи имеют вид «³».

Двойственная - следующая:

2 y ₁+4 y ₂-6 y ₃ ® max

Убеждаемся в этом точно так же, как и в предыдущем случае.

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

Теорема 1 (первая теорема двойственности). Значения целевых функций пары двойственных задач на их оптимальных планах совпадают.

Теорема 2 (вторая теорема двойственности). Пусть X ⁰=(, , …, ) и Y ⁰=(, , …, ) - решения соответственно задач

c ₁ x ₁+ c ₂ x ₂+…+ c_nx_n ® max b ₁ y ₁+ b ₂ y ₂+…+ b_my_m ® min

(1) и (2).

Тогда они связаны соотношениями

(3)