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

Прямая и двойственная задача линейного программирования. Геометрическая интерпретация двойственной задачи.

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

(32)

при условиях

(33)

(34)

Определение 1.12. Задача, состоящая в нахождении минимального значения функции

(35)

при условиях

(36)

(37)

называется двойственной по отношению к задаче (32) - (34). Задачи (32) - (34) и (35) - (37) образуют пару задач, называемую в линейном программировании двойственной парой. Сравнивая две сформулированные задачи, видим, что двойственная задача по отношению к исходной составляется согласно следующим правилам:

1. Целевая функция исходной задачи (32) - (34) задается на максимум, а целевая функция двойственной (35) - (37) — на минимум.

2. Матрица

(38)

составленная из коэффициентов при неизвестных в системе ограничений (33) исходной задачи (32) - (34), и аналогичная матрица

(39)

в двойственной задаче (35) - (37) получаются друг из друга транспонированием (т. е. заменой строк столбцами, а столбцов — строками).

3. Число переменных в двойственной задаче (35) - (37) равно числу соотношений в системе (33) исходной задачи (32) - (34), а число ограничений в системе (36) двойственной задачи — числу переменных в исходной задаче.

4. Коэффициентами при неизвестных в целевой функции (35) двойственной задачи (35) - (37) являются свободные члены в системе (33) исходной задачи (32) - (34), а правыми частями в соотношениях системы (36) двойственной задачи — коэффициенты при неизвестных в целевой функции (32) исходной задачи.

5. Если переменная x_j исходной задачи (32) - (34) может принимать только лишь положительные значения, то j -е условие в системе (36) двойственной задачи (35) - (37) является неравенством вида «³». Если же переменная x_j может принимать как положительные, так и отрицательные значения, то 1-е соотношение в системе (54) представляет собой уравнение. Аналогичные связи имеют место между ограничениями (33) исходной задачи (32) - (34) и переменными двойственной задачи (35) - (37). Если i -е соотношение в системе (33) исходной задачи является неравенством, то i -я переменная двойственной задачи . В противном случае переменная у_j может принимать как положительные, так и отрицательные значения.

Двойственные пары задач обычно подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения (33) прямой задачи и соотношения (36) двойственной задачи являются неравенствами вида «£». Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения.

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

(40)

при условиях

(41)

(42)

Решение. Для данной задачи

и

Число переменных в двойственной задаче равно числу уравнений в системе (41), т. е. равно трем. Коэффициентами в целевой функции двойственной задачи являются свободные члены системы уравнений (41), т.е. числа 12, 24, 18.

Целевая функция исходной задачи (40) - (42) исследуется на максимум, а система условий (41) содержит только уравнения. Поэтому в двойственной задаче целевая функция исследуется на минимум, а ее переменные могут принимать любые значения (в том числе и отрицательные). Так как все три переменные исходной задачи (40) - (42) принимают только лишь неотрицательные значения, то в системе условий двойственной задачи должны быть три неравенства вида «³». Следовательно, для задачи (40) - (42) двойственная задача такова: найти минимум функции при условиях

1.11. Для задачи, состоящей в максимизации функции

при условиях

сформулировать двойственную задачу.

Решение. Для данной задачи

,

В соответствии с общими правилами задача, двойственная по отношению к данной, формулируется следующим образом: найти минимум функции при условиях

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

(43)

при условиях

(44)

(45)

Двойственная задача: найти минимум функции

(46)

при условиях (47)

Каждая из задач двойственной пары (43) - (45) и (46), (47) фактически является самостоятельной задачей линейного программирования и может быть решена независимо одна от другой. Однако при определении симплексным методом оптимального плана одной из задач тем самым находится решение и другой задачи.

Существующие зависимости между решениями прямой и двойственной задач характеризуются сформулированными ниже леммами и теоремами двойственности.

Лемма 1.1. Если Х — некоторый план исходной задачи (43) - (45), a Y — произвольный план двойственной задачи (46), (47), то значение целевой функции исходной задачи при плане Х всегда не превосходит значения целевой функции двойственной задачи при плане Y, т. е.

Лемма 1.2. Если для некоторых планов X^* и Y^* задач (43) - (45) и (46), (47), то X^* — оптимальный план исходной задачи, а Y^* — оптимальный план двойственной задачи.

Теорема 1.9 (первая теорема двойственности). Если одна из пары двойственных задач (43) - (45) или (46), (47) имеет оптимальный план, то и другая имеет оптимальный план и значения целевых функций задач при их оптимальных планах равны между собой, т. е.

Если же целевая функция одной из пары двойственных задач не ограничена [для исходной (43) - (45) — сверху, для двойственной (46), (47) — снизу], то другая задача вообще не имеет планов.

Теорема 1.10 (вторая теорема двойственности). План задачи (43) - (45) и план задачи (46), (47) являются оптимальными планами этих задач тогда и только тогда, когда для любого выполняется равенство

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

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

составить двойственную задачу и найти решение обеих задач.

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

Рис. 7 Рис. 8

Как в исходной, так и в двойственной задаче число неизвестных равно двум. Следовательно, их решение можно найти, используя геометрическую интерпретацию задачи линейного программирования (рис. 7 и 8).

Как видно из рис. 8, максимальное значение целевая функция исходной задачи принимает в точке В. Следовательно, Х^*= (2, 6) является оптимальным планом, при котором . Минимальное значение целевая функция двойственной задачи принимает в точке Е (рис. 8). Значит, Y ^*=(1; 4) является оптимальным планом двойственной задачи, при котором Таким образом, значения целевых функций исходной и двойственной задач при их оптимальных планах равны между собой.

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

1.13. Найти решение двойственной пары задач.

Исходная задача;

Двойственная задача:

Решение. Как исходная, так и двойственная задача содержат по две переменные. Поэтому их решение находим, используя геометрическую интерпретацию задачи линейного программирования (рис. 7 и 8). Из рис. 7 видно, что исходная задача не имеет оптимального плана из-за неограниченности снизу ее целевой функции на множестве допустимых решений.

Рис. 9 Рис. 10

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

Нахождение решения двойственных задач. Рассмотрим пару двойственных задач — основную задачу линейного программирования (43) - (45) и двойственную к ней задачу (46), (47).

Предположим, что с помощью симплексного метода найден оптимальный план X^* задачи (43) - (45) и этот план определяется базисом, образованным векторами .

Обозначим через вектор-строку, составленную из коэффициентов при неизвестных в целевой функции (43) задачи (43) - (45), а через — матрицу, обратную матрице Р,составленной из компонент векторов базиса. Тогда имеет место следующее утверждение.

Теорема 1.11. Если основная задача линейного программирования имеет оптимальный план X^*, то является оптимальным планом двойственной задачи.

Таким образом, если найти симплексным методом оптимальный план задачи (43) - (45), то, используя последнюю симплекс-таблицу, можно определить и и с помощью соотношения найти оптимальный план двойственной задачи (46), (47).

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

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

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

составить двойственную задачу и найти ее решение.

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

Чтобы найти решение двойственной задачи, сначала находим решение исходной задачи методом искусственного базиса. Оно приведено в таблице 12.

Из последней симплекс-таблицы видно, что двойственная задача имеет решение

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

Таблица 12

i	Базис	Сб	Р 0			-1			- М
			P 1	P 2	P 3	p 4	p 5	Р 6
	p 4 P 5 p 6     p 4 P 5 p 1   p 2 P 5 p 1	-М     0	12 17 -4 14 15	-1 -1 -2	-1 -2 7/2 3/2 -1/2 -5/2	—2 -2 -1 -2/7 13/7 6/7 9/7	2/7 -3/7 1/7 5/7		0 1/2 -1/2 1/2 1/2 1/7 -5/7 4/7 6/7

Экономическая интерпретация двойственных задач. Экономическую интерпретацию двойственных задач и двойственных оценок рассмотрим на примере.

1.15. Для производства трех видов изделий А, В и С используется три различных вида сырья. Каждый из видов сырья может быть использован в количестве, соответственно не большем 180, 210 и 244 кг. Нормы затрат каждого из видов сырья на единицу продукции данного вида и цена единицы продукции каждого вида приведены в таблице 13.

Таблица 13

Вид сырья	Нормы затрат сырья (кг) на единицу продукции
А	В	С
I II III
Цена единицы продукции (руб.)

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

Решение. Предположим, что производится изделий А, изделий В и изделий С. Для определения оптимального плана производства нужно решить задачу, состоящую в максимизации целевой функции

(48)

при следующих условиях

(49)

(50)

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

(51)

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

(52)

(53)

Как видно, задачи (48) - (50) и (51) - (53) образуют симметричную пару двойственных задач. Решение прямой задачи дает оптимальный план производства изделий A, В и С, а решение двойственной — оптимальную систему оценок сырья, используемого для производства этих изделий. Чтобы найти решение этих задач, следует сначала отыскать решение какой-либо одной из них. Так как система ограничений задачи (48) - (50) содержит лишь неравенства вида «£», то лучше сначала найти решение этой задачи. Ее решение приведено в таблице 14.

Из этой таблицы видно, что оптимальным планом производства изделий является такой, при котором изготовляется 82 изделия В и 16 изделий С. При данном плане производства остается неиспользованным 80 кг сырья II вида, а общая стоимость изделий равна 1340 руб. Из таблицы 14 также видно, что оптимальным решением двойственной задачи является

Таблица 14

i	Базис	Сб	Р 0
				P 1	P 2	P 3	p 4	p 5	Р 6
1 2 3	p 2 P 5 p 3			19/8 23/8 -3/4 57/4	1 0 0 0	00	5/8 1/8 -1/4 23/4		-1/8 -5/8 1/4 5/4

Переменные и обозначают условные двойственные оценки единицы сырья, соответственно I и III видов. Эти оценки отличны от нуля, а сырье 1 и III видов полностью используется при оптимальном плане производства продукции. Двойственная оценка единицы сырья II вида равна нулю. Этот вид сырья не полностью используется при оптимальном плане производства продукции.

Таким образом, положительную двойственную оценку имеют лишь те виды сырья, которые полностью используются при оптимальном плане производства изделий. Поэтому двойственные оценки определяют дефицитность используемого предприятием сырья. Более того, величина данной двойственной оценки показывает, на сколько возрастает максимальное значение целевой функции прямой задачи при увеличении количества сырья соответствующего вида на 1 кг. Так, увеличение количества сырья I вида на 1 кг приведет к тому, что появится возможность найти новый оптимальный план производства изделий, при котором общая стоимость изготовляемой продукции возрастет на 5,75 руб. и станет равной 1340+5,75 = 1345,75 руб. При этом числа, стоящие в столбце вектора таблицы 14, показывают, что указанное увеличение общей стоимости изготовляемой продукции может быть достигнуто за счет увеличения выпуска изделий В на 5/8 ед. и сокращения выпуска изделий С на 1/4 ед. Вследствие этого использование сырья II вида уменьшится на 1/8 кг. Точно так же увеличение на 1 кг сырья III вида позволит найти новый оптимальный план производства изделий, при котором общая стоимость изготовляемой продукции возрастет на 1,25 руб. и составит 1340+1,25=1341,25 руб. Это будет достигнуто в результате увеличения выпуска изделий С на 1/4 ед. и уменьшения изготовления изделий В на 1/8 ед., причем объем используемого сырья II вида возрастет на 5/8 кг.

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

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

При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получаем

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

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

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

(54)

при условиях

(55)

(56)

где

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 15

i

Базис

Cб

P 0

c 1

c 2

…

ce

…

cm

cm+ 1

…

cr

…

cn

P 1

Р 2

…

Рe

Рm

Рm+ 1

Рr

Рn

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

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

Умножим второе и третье уравнения системы ограничении последней задачи на -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) является . При этом плане Так как в столбце вектора Р ₀ таблица 16 имеются два отрицательных числа (-4 и -6), а в 4-й строке отрицательных чисел нет, то в соответствии с алгоритмом двойственного симплекс-метода переходим к новой симплекс-таблице. (В данном случае это можно сделать, так как в строках векторов Р ₄и Р ₅ имеются отрицательные числа. Если бы они отсутствовали, то задача была бы неразрешима.) Вектор, исключаемый из базиса, определяется наибольшим по абсолютной величине отрицательным числом, стоящим в столбце вектора Р ₀. В данном случае это число -6. Следовательно, из базиса исключаем вектор Р ₅. Чтобы определить, какой вектор необходимо ввести в базис, находим где Имеем

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

Таблица 17

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

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

Так как в столбце вектора Р ₀ таблицы 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		8/3 14/3 2/3 32/3				1/3 -2/3 1/3 1/3	2/3 -1/3 -1/3 2/3

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

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

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

Взяв в качестве базиса векторы Р ₃, Р ₄ и Р ₅, составляем симплекс-таблицу (табл. 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 нет отрицательных чисел. Следовательно, если бы в столбце вектора Р ₀ не было отрицательных чисел, то в таблице 19 был бы записан оптимальный план. Поскольку в указанном столбце отрицательные числа имеются и такие же числа содержатся в соответствующих строках, переходим к новой симплекс-таблице (таблица 20). Для этого исключим из базиса вектор Р ₅ и введем в базис вектор Р ₁. В результате получим псевдоплан

Таблица 20

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

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

Дата добавления: 2014-12-27