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

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

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

1) выбирают разрешающую строку по наибольшему по абсолютной величине отрицательному элементу столбца свободных членов;
2) выбирают разрешающий столбец по наименьшему по абсолютной величине отношению элементов L строки к отрицательным элементам разрешающей строки;
3) пересчитывают симплексную таблицу по правилам обычного симплекс-метода;
4) решение проверяют на оптимальность. Признаком получения допустимого оптимального решения является отсутствие в столбце свободных членов отрицательных элементов.
Замечания
1. Если в разрешающей строке нет ни одного отрицательного элемента, задача неразрешима.
2. Если ограничения задачи заданы неравенствами типа «≥», двойственный симплекс-метод позволяет избавиться от необходимости введения искусственных переменных.

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

L = x 1 + 4x 2 → min

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

Баз.	x 1	x 2	x 3	x 4	x 5	x 6	x 7	Св.
x 4	-2	-3		1	0	0	0	-20
x 5	-5	1	-2	0	1	0	0	-12
x 6	1	2	-1	0	0	1	0	2
x 7	-1	4	-2	0	0	0	1	1
L	-1	-4	-1	0	0	0	0	0

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

Баз.	х 1	х 2	х 3	х 4	х 5	х 6	х 7	Св.
х 3			1		0	0	0	5
х 5			0		1	0	0	-2
х 6			0		0	1	0	7
х 7	0		0		0	0	1	11
L			0		0	0	0	5

Аналогично рассуждая, получим еще одну таблицу

Баз.	х 1	х 2	х 3	х 4	х 5	х 6	х 7	Св.
х 3	0		1			0	0
х 1	1		0			0	0
х 6	0		0			1	0
х 7	0		0		0	0	1	11
L	0		0			0	0

Отсутствие в столбце свободных членов отрицательных элементов свидетельствует о том, что получено оптимальное решение , .
Замечание . Если решение ЗЛП и недопустимо и неоптимально, то сначала получаем допустимое решение, используя алгоритм двойственного симплекс-метода, а затем по правилам обычного симплекс-метода получаем оптимальное решение.
Пример .
L = 5x 1 – x 2 – x 3 → max
или

Составляем исходную симплекс-таблицу

	x 1	x 2	x 3	x 4	x 5	x 6	x 7	Св.
x 4	0		-2	1	0	0	0	-9
x 5	1	-1	0	0	1	0	0	-1
x 6	-1	-1	3	0	0	1	0	-8
x 7	1	0	-1	0	0	0	1	4
L	-5	1	4	0	0	0	0	0

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

Баз.	x 1	x 2	x 3	x 4	x 5	x 6	x 7	Св.
x 2	0	1	2	-1	0	0	0	9
x 5	1	0	2	-1	1	0	0	8
x 6	-1	0	5	-1	0	1	0	1
x 7		0	-1	0	0	0	1	4
L	-5	0	2	1	0	0	0	-9

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

Баз.	x 1	x 2	x 3	x 4	x 5	x 6	x 7	Св.
x 2	0	1	2	-1	0	0	0	9
х 5	0	0	3	-1	1	0	-1	4
х 6	0	0		-1	0	1	1	5
x 1	1	0	-1	0	0	0	1	4
L	0	0	-3	1	0	0	5	11

Двойственный симплексный метод основан на теории двойственности (см. решение двойственной задачи) и используется для решения задач линейного программирования, свободные члены которых b i могут принимать любые значения, а система ограничений задана неравенствами смысла «≤», «≥» или равенством «=».

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

Инструкция для решения задач двойственным симплекс-методом . Выберите количество переменных и количество строк (количество ограничений), нажмите Далее. Полученное решение сохраняется в файле Word (см. пример решения двойственным симплекс-методом).

Количество переменных 2 3 4 5 6 7 8 9 10
Количество строк (количество ограничений) 2 3 4 5 6 7 8 9 10

При этом ограничения типа x i ≥ 0 не учитывайте.

Вместе с этим калькулятором также используют следующие:
Графический метод решения ЗЛП
Решение транспортной задачи
Решение матричной игры
С помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.
Экстремум функции двух переменных

Задачи динамического программирования
Распределить 5 однородных партий товара между тремя рынками так, чтобы получить максимальный доход от их продажи. Доход от продажи на каждом рынке G(X) зависит от количества реализованных партий товара Х и представлен в таблице.

Объем товара Х (в партиях)	Доход G(X)
	1	2	3
0	0	0	0
1	28	30	32
2	41	42	45
3	50	55	48
4	62	64	60
5	76	76	72

В P-методе оптимальный план получается в результате движения по псевдопланам. Псевдоплан - план, в котором условия оптимальности удовлетворяются, а среди значений базисных переменных x i имеются отрицательные числа. Алгоритм двойственного симплекс-метода включает следующие этапы:

1. Составление псевдоплана . Систему ограничений исходной задачи приводят к системе неравенств смысла «≤».
2. Проверка плана на оптимальность . Если в полученном опорном плане не выполняется условие оптимальности, то задача решается симплексным методом .
3. Выбор ведущих строки и столбца . Среди отрицательных значений базисных переменных выбираются наибольшие по абсолютной величине. Строка, соответствующая этому значению, является ведущей.
4. Расчет нового опорного плана . Новый план получается в результате пересчета симплексной таблицы методом Жордана-Гаусса . Далее переход к этапу 2.

Более подробный алгоритм двойственного симплекс-метода . Особенности двойственного симплекс-метода Используются при решении методом Гомори .

Пример . Предприятию необходимо выпустить по плану продукции А1 единиц, А2 единиц, А3 единиц. Каждый вид изделия может производиться на двух машинах.
Как распределить работу машин, чтобы общие затраты времени на выполнение плана были минимальны? Дана матрица затрат и ресурс времени каждой машины. Записать модель исследуемой операции в форме, допускающей использование P–метода.

Известно, что содержание n питательных веществ A, B и С в рационе должно быть не менее m1, m2, m3 единиц соответственно. Указанные питательные вещества содержат три вида продуктов. Содержание единиц питательных веществ в одном килограмме каждого из видов продукта приведено в таблице. определите дневной рацион, обеспечивающий получение необходимого количества питательных веществ при минимальных денежных затратах.

Задание : Решить задачу, используя алгоритм двойственного симплекс-метода.
Приведем систему ограничений к системе неравенств смысла ≤, умножив соответствующие строки на (-1).
Определим минимальное значение целевой функции F(X) = 4x 1 + 2x 2 + x 3 при следующих условиях-ограничений.
- x 1 - x 2 ≤-10
2x 1 + x 2 - x 3 ≤8
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В первом неравенстве смысла (≤) вводим базисную переменную x 4 . Во втором неравенстве смысла (≤) вводим базисную переменную x 5 .
-1x 1 -1x 2 + 0x 3 + 1x 4 + 0x 5 = -10
2x 1 + 1x 2 -1x 3 + 0x 4 + 1x 5 = 8
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

A =	-1 -1 0 1 0 2 1 -1 0 1

Решим систему уравнений относительно базисных переменных:
x 4 , x 5 ,
Полагая, что свободные переменные равны нулю, получим первый опорный план:
X1 = (0,0,0,-10,8)

Базис	B	x 1	x 2	x 3	x 4	x 5
x 4	-10	-1	-1	0	1	0
x 5	8	2	1	-1	0	1
F(X0)	0	-4	-2	-1	0	0

Итерация №1

План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.


Ведущей будет первая строка, а переменную x 4 следует вывести из базиса.
3. Определение новой базисной переменной. Минимальное значение θ соответствует 2-му столбцу, т.е. переменную x 2 необходимо ввести в базис.

Базис	B	x 1	x 2	x 3	x 4	x 5
x 4	-10	-1	-1	0	1	0
x 5	8	2	1	-1	0	1
F(X0)	0	-4	-2	-1	0	0
θ	0	-4: (-1) = 4	-2: (-1) = 2	-	-	-

4. Пересчет симплекс-таблицы. Выполняем преобразования симплексной таблицы методом Жордано-Гаусса .

Базис	B	x 1	x 2	x 3	x 4	x 5
x 2	10	1	1	0	-1	0
x 5	-2	1	0	-1	1	1
F(X0)	20	-2	0	-1	-2	0

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5
-10: -1	-1: -1	-1: -1	0: -1	1: -1	0: -1
8-(-10 1):-1	2-(-1 1):-1	1-(-1 1):-1	-1-(0 1):-1	0-(1 1):-1	1-(0 1):-1
0-(-10 -2):-1	-4-(-1 -2):-1	-2-(-1 -2):-1	-1-(0 -2):-1	0-(1 -2):-1	0-(0 -2):-1

Итерация №2
1. Проверка критерия оптимальности.
План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет вторая строка, а переменную x 5 следует вывести из базиса.
3. Определение новой базисной переменной. Минимальное значение θ соответствует третьему столбцу, т.е. переменную x 3 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-1).

Базис	B	x 1	x 2	x 3	x 4	x 5
x 2	10	1	1	0	-1	0
x 5	-2	1	0	-1	1	1
F(X0)	20	-2	0	-1	-2	0
θ	0	-	-	-1: (-1) = 1	-	-

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

Базис	B	x 1	x 2	x 3	x 4	x 5
x 2	10	1	1	0	-1	0
x 3	2	-1	0	1	-1	-1
F(X1)	22	-3	0	0	-3	-1

Или более подробно:

B	x 1	x 2	x 3	x 4	x 5
10-(-2 0):-1	1-(1 0):-1	1-(0 0):-1	0-(-1 0):-1	-1-(1 0):-1	0-(1 0):-1
-2: -1	1: -1	0: -1	-1: -1	1: -1	1: -1
20-(-2 -1):-1	-2-(1 -1):-1	0-(0 -1):-1	-1-(-1 -1):-1	-2-(1 -1):-1	0-(1 -1):-1

В базисном столбце все элементы положительные. Переходим к основному алгоритму симплекс-метода.

Итерация №3
1. Проверка критерия оптимальности.
Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.

Базис	B	x 1	x 2	x 3	x 4	x 5
x 2	10	1	1	0	-1	0
x 3	2	-1	0	1	-1	-1
F(X1)	22	-3	0	0	-3	-1

Оптимальный план можно записать так: x 1 = 0, x 2 = 10, x 3 = 2
F(X) = 2 10 + 1 2 = 22

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

(54)

при условиях

(55)

(56)

где

и среди чисел имеются отрицательные .

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

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

Определение 14.

Решение системы линейных уравнений (55), определяемое базисом , называется псевдопланом задачи (54) – (56), если для любого

Теорема 11.

Если в псевдоплане , определяемом базисом , есть хотя бы одно отрицательное число такое, что все , то задача (54) – (56) вообще не имеет планов.

Теорема 12.

Если в псевдоплане , определяемом базисом , имеются отрицательные числа такие, что для любого из них существуют числа a ij <0, то можно перейти к новому псевдоплану , при котором значение целевой функции задачи (54) – (56) не уменьшится.

Сформулированные теоремы дают основание для построения алгоритма двойственного симплекс-метода.

Итак, продолжим рассмотрение задачи (54) – (56). Пусть – псевдоплан этой задачи. На основе исходных данных составляют симплекс-таблицу (табл. 15), в которой некоторые элементы столбца вектора являются отрицательными числами. Если таких чисел нет, то в симплекс-таблице записан оптимальный план задачи (54) – (56), поскольку, по предположению, все . Поэтому для определения оптимального плана задачи при условии, что он существует, следует произвести упорядоченный переход от одной симплекс–таблицы к другой до тех пор, пока из столбца вектора не будут исключены отрицательные элементы. При этом все время должны оставаться неотрицательными все элементы (т +1)–й строки, т.е. для любого

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

Пусть это минимальное значение принимается при тогда в базис вводят вектор Р r . Число является разрешающим элементов. Переход к новой симплекс–таблице производят по обычным правилам симплексного метода. Итерационный процесс продолжают до тех пор, пока в столбце вектора Р 0 не будет больше отрицательных чисел. При этом находят оптимальный план исходной задачи, а следовательно, и двойственной. Если на некотором шаге окажется, что в i –й строке симплекс–таблицы (табл. 15) в столбце вектора Р 0 стоит отрицательное число b i , а среди остальных элементов этой строки нет отрицательных, то исходная задача не имеет решения.

Таким образом, отыскание решения задачи (54) – (56) двойственным симплекс-методом включает следующие этапы:

1. Находят псевдоплан задачи.

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

3. Выбирают разрешающую строку с помощью определения наибольшего по абсолютной величине отрицательного числа столбца вектора Р 0 и разрешающий столбец с помощью нахождения наименьшего по абсолютной величине отношения элементов (m +1)–и строки к соответствующим отрицательным элементам разрешающей строки.

4. Находят новый псевдоплан и повторяют все действия начиная с этапа 2.

Таблица 15

Пример 17.

Найти максимальное значение функции при условиях

Решение. Запишем исходную задачу линейного программирования в форме основной задачи: найти максимум функции при условиях

Умножим второе и третье уравнения системы ограничений последней задачи на –1 и перейдем к следующей задаче: найти максимум функции

(57)

при условиях

(58)

(59)

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

(60)

при условиях

(61)

(62)

Выбрав в качестве базиса векторы и , составим симплексную таблицу (табл. 16) для исходной задачи (57) – (59).

Таблица 16

i	Базис	С б	Р 0
				P 1	P 2	P 3	p 4	p 5
	p 3 P 4 p 5		–4 –6	–1 –1	–2

Из этой таблицы видим, что планом двойственной задачи (57) – (59) является . При этом плане Т ак как в столбце вектора Р 0 таблица 16 имеются два отрицательных числа (–4 и –6), а в 4–й строке отрицательных чисел нет, то в соответствии с алгоритмом двойственного симплекс–метода переходим к новой симплекс–таблице. (В данном случае это можно сделать, так как в строках векторов Р 4 и Р 5 имеются отрицательные числа. Если бы они отсутствовали, то задача была бы неразрешима. Вектор, исключаемый из базиса, определяется наибольшим по абсолютной величине отрицательным числом, стоящим в столбце вектора Р 0 . В данном случае это число –6. Следовательно, из базиса исключаем вектор Р 5 . Чтобы определить, какой вектор необходимо ввести в базис, находим где Имеем

Значит, в базис вводим вектор P 2 . Переходим к новой симп екс–таблице (табл. 17).

Таблица 17

i	Базис	С б	Р 0
				P 1	P 2	P 3	p 4	p 5
	p 3 P 4 p 2		–7	–3/2				–1/2

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

Так как в столбце вектора Р 0 таблицы 17 стоит отрицательное число –7, то рассмотрим элементы 2–й строки. Среди этих чисел есть одно отрицательное –3/2. Если бы такое число отсутствовало, то исходная задача была бы неразрешима. В данном случае переходим к новой симплекс-таблице (табл. 18).

Таблица 18

i	Базис	С б	Р 0
				P 1	P 2	P 3	p 4	p 5
	p 3 P 1 p 2		14/3 32/3				–2/3	–1/3 –1/3

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

Пример 18.

Найти максимальное значение функции при условиях

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

Взяв в качестве базиса векторы Р 3 , Р 4 и Р 5 , составляем симплекс-таблицу (табл. 19).

Таблица 19

i	Базис	С б	Р 0
				P 1	P 2	P 3	p 4	p 5
	p 3 P 4 p 5		–12 –18	–3	–1

В 4-й строке таблице 19 нет отрицательных чисел. Следовательно, если бы в столбце вектора Р 0 не было отрицательных чисел, то в таблице 19 был бы записан оптимальный план. Поскольку в указанном столбце отрицательные числа имеются и такие же числа содержатся в соответствующих строках, переходим к новой симплекс–таблице (таблица 20). Для этого исключим из базиса вектор Р 5 и введем в базис вектор Р 1 . В результате получим псевдоплан X=(6;0;-24;4)

Таблица 20

i	Базис	С б	Р 0
				P 1	P 2	P 3	p 4	p 5
	p 3 P 4 p 1		–24		–2/3			–1/3

Так как в строке вектора Р 3 нет отрицательных чисел, то исходная задача не имеет решения.

Рассмотрим симплекс -метод для решения задач линейного программирования (ЛП). Он основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает.

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

1. Исходную задачу переводим в канонический вид путем введения дополнительных переменных. Для неравенства вида ≤ дополнительные переменные вводят со знаком (+ ), если же вида ≥ то со знаком (— ). В целевую функцию дополнительные переменные вводят с соответствующими знаками с коэффициентом, равным 0 , т.к. целевая функция не должна при этом менять свой экономический смысл.
2. Выписываются вектора P i из коэффициентов при переменных и столбца свободных членов. Этим действием определяется количество единичных векторов. Правило – единичных векторов должно быть столько, сколько неравенств в системе ограничений.
3. После этого исходные данные вводятся в симплекс-таблицу. В базис вносятся единичные вектора, и исключая их из базиса, находят оптимальное решение . Коэффициенты целевой функции записывают с противоположным знаком.
4. Признак оптимальности для задачи ЛП – решение оптимально, если в f – строке все коэффициенты положительны. Правило нахождения разрешающего столбца – просматривается f – строка и среди ее отрицательных элементов выбирается наименьшее. Вектор P i его содержащий становится разрешающим. Правило выбора разрешающего элемента – составляются отношения положительных элементов разрешающего столбца к элементам вектора Р 0 и то число, которое дает наименьшее отношение становится разрешающим элементом, относительно которого будет произведен пересчет симплекс-таблицы. Строка, содержащая этот элемент называется разрешающей строкой. Если в разрешающем столбце нет положительных элементов, то задача не имеет решения. После определения разрешающего элемента переходят к пересчету новой симплекс – таблицы.
5. Правила заполнения новой симплекс – таблицы. На месте разрешающего элемента проставляют единицу, а другие элементы полагают равными 0 . Разрешающий вектор вносят в базис, из которого исключают соответствующий нулевой вектор, а остальные базисные вектора записывают без изменений. Элементы разрешающей строки делят на разрешающий элемент, а остальные элементы пересчитывают по правилу прямоугольников.
6. Так поступают до тех пор, пока в f – строке все элементы не станут положительными.

Рассмотрим решение задачи с использованием рассмотренного выше алгоритма.
Дано:

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

Составляем вектора:

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

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

Аналогичные расчеты выполним для всех остальных элементов симплекс – таблицы:

В полученном плане f – строка содержит один отрицательный элемент – (-5/3), вектора P 1 . Он содержит в своем столбце единственный положительный элемент, который и будет разрешающим элементом. Сделаем пересчет таблицы относительно этого элемента:

Отсутствие отрицательных элементов в f – строке означает, что найден оптимальный план :
F* = 36/5, Х = (12/5, 14/5, 8, 0, 0).

• Ашманов С. А. Линейное программирование, М: Наука, 1998г.,
• Вентцель Е.С. Исследование операций, М: Советское радио, 2001г.,
• Кузнецов Ю.Н., Кузубов В.И., Волошенко А.Б. Математическое программирование, М: Высшая школа, 1986г.

Решение линейного программирования на заказ

Заказать любые задания по этой дисциплине можно у нас на сайте. Прикрепить файлы и указать сроки можно на

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

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

при условиях

и среди чисел имеются отрицательные.

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

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

Таким образом, можно найти:

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

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

Пусть это минимальное значение принимается при j=r, тогда в базис вводят вектор Р r . Число является разрешающим элементов. Переход к новой симплекс-таблице производят по обычным правилам симплексного метода. Итерационный процесс продолжают до тех пор, пока в столбце вектора Р 0 не будет больше отрицательных чисел. При этом находят оптимальный план исходной задачи, а следовательно, и двойственной. Если на некотором шаге окажется, что в i -й строке симплекс-таблицы в столбце вектора Р 0 стоит отрицательное число b i , а среди остальных элементов этой строки нет отрицательных, то исходная задача не имеет решения.

Таким образом, отыскание решения задачи двойственным симплекс-методом включает следующие этапы:

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

Найти максимальное значение функции

при условиях :

Решение . Запишем исходную задачу линейного программирования в форме основной задачи: найти максимум функции при условиях

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

Строим симплекс таблицу:

Итерация 0:

Условие допустимости выполняется, так как в графе «Решение» все значения положительные, но не выполняется условие оптимальности, так как -строка содержит отрицательный коэффициент.Продолжаем наши действия

Итерация 1: