SHPORA.net :: PDA | |
Main FAQ гуманитарные науки естественные науки математические науки технические науки Двойственный симплекс-метод. Двойственный симплекс-метод, как и симплекс-метод, используется при нахождении решения задачи линейного программирования, записанной в форме основной задачи, для которой среди векторов , составленных из коэффициентов при неизвестных в системе уравнений, имеется m единичных. Вместе с тем двойственный симплекс–метод можно применять при решении задачи линейного программирования, свободные члены системы уравнений которой могут быть любыми числами (при решении задачи симплексным методом эти числа предполагались неотрицательными). Такую задачу и рассмотрим теперь, предварительно предположив, что единичными являются векторы т. е. рассмотрим задачу, состоящую в определении максимального значения функции (54) при условиях (55) (56) где и среди чисел имеются отрицательные. В данном случае есть решение системы линейных уравнений (55). Однако это решение не является планом задачи (54) – (56), так как среди его компонент имеются отрицательные числа. Поскольку векторы – единичные, каждый из векторов можно представить в виде линейной комбинации данных векторов, причем коэффициентами разложения векторов по векторам служат числа Таким образом, можно найти Определение 14. Решение системы линейных уравнений (55), определяемое базисом , называется псевдопланом задачи (54) – (56), если для любого Теорема 11. Если в псевдоплане , определяемом базисом , есть хотя бы одно отрицательное число такое, что все , то задача (54) – (56) вообще не имеет планов. Теорема 12. Если в псевдоплане , определяемом базисом , имеются отрицательные числа такие, что для любого из них существуют числа aij<0, то можно перейти к новому псевдоплану, при котором значение целевой функции задачи (54) – (56) не уменьшится. Сформулированные теоремы дают основание для построения алгоритма двойственного симплекс-метода. Итак, продолжим рассмотрение задачи (54) – (56). Пусть – псевдоплан этой задачи. На основе исходных данных составляют симплекс-таблицу (табл. 15), в которой некоторые элементы столбца вектора являются отрицательными числами. Если таких чисел нет, то в симплекс-таблице записан оптимальный план задачи (54) – (56), поскольку, по предположению, все . Поэтому для определения оптимального плана задачи при условии, что он существует, следует произвести упорядоченный переход от одной симплекс–таблицы к другой до тех пор, пока из столбца вектора не будут исключены отрицательные элементы. При этом все время должны оставаться неотрицательными все элементы (т +1)–й строки, т.е. для любого Таким образом, после составления симплекс-таблицы проверяют, имеются ли в столбце вектора отрицательные числа. Если их нет, то найден оптимальный план исходной задачи. Если же они имеются (что мы и предполагаем), то выбирают наибольшее по абсолютной величине отрицательное число. В том случае, когда таких чисел несколько, берут какое–нибудь одно из них: пусть это число bl. Выбор этого числа определяет вектор, исключаемый из базиса, т. е. в данном случае из базиса выводится вектор Pl. Чтобы определить, какой вектор следует ввести в базис, находим , где Пусть это минимальное значение принимается при , тогда в базис вводят вектор Рr. Число является разрешающим элементов. Переход к новой симплекс–таблице производят по обычным правилам симплексного метода. Итерационный процесс продолжают до тех пор, пока в столбце вектора Р0 не будет больше отрицательных чисел. При этом находят оптимальный план исходной задачи, а следовательно, и двойственной. Если на некотором шаге окажется, что в i–й строке симплекс–таблицы (табл. 15) в столбце вектора Р0 стоит отрицательное число bi, а среди остальных элементов этой строки нет отрицательных, то исходная задача не имеет решения. Таким образом, отыскание решения задачи (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 1 1 2 0 0 P1 P2 P3 p4 p5 1 2 3 4 p3 P4 p5 2 0 0 8 –4 –6 16 1 –1 –1 1 1 1 –2 1 1 0 0 0 0 1 0 0 0 0 1 0 Из этой таблицы видим, что планом двойственной задачи (57) – (59) является . При этом плане Так как в столбце вектора Р0 таблица 16 имеются два отрицательных числа (–4 и –6), а в 4–й строке отрицательных чисел нет, то в соответствии с алгоритмом двойственного симплекс–метода переходим к новой симплекс–таблице. (В данном случае это можно сделать, так как в строках векторов Р4 и Р5 имеются отрицательные числа. Если бы они отсутствовали, то задача была бы неразрешима. Вектор, исключаемый из базиса, определяется наибольшим по абсолютной величине отрицательным числом, стоящим в столбце вектора Р0. В данном случае это число –6. Следовательно, из базиса исключаем вектор Р5. Чтобы определить, какой вектор необходимо ввести в базис, находим где Имеем Значит, в базис вводим вектор P2. Переходим к новой симплекс–таблице (табл. 17). Таблица 17 i Базис Сб Р0 1 1 2 0 0 P1 P2 P3 p4 p5 1 2 3 4 p3 P4 p2 2 0 1 5 –7 3 13 1/2 –3/2 1/2 1/2 0 0 1 0 1 0 0 0 0 1 0 0 1/2 1/2 –1/2 1/2 Из этой таблицы видно, что получен новый план двойственной задачи При этом плане значение ее линейной формы равно Таким образом, с помощью алгоритма двойственного симплекс–метода произведен упорядоченный переход от одного плана двойственной задачи к другому. Так как в столбце вектора Р0 таблицы 17 стоит отрицательное число –7, то рассмотрим элементы 2–й строки. Среди этих чисел есть одно отрицательное –3/2. Если бы такое число отсутствовало, то исходная задача была бы неразрешима. В данном случае переходим к новой симплекс-таблице (табл. 18). Таблица 18 i Базис Сб Р0 1 1 2 0 0 P1 P2 P3 p4 p5 1 2 3 4 p3 P1 p2 2 1 1 8/3 14/3 2/3 32/3 0 1 0 0 0 0 1 0 1 0 0 0 1/3 –2/3 1/3 1/3 2/3 –1/3 –1/3 2/3 Как видно из таблицы 18, найдены оптимальные планы исходной и двойственной задач. Ими являются и . При этих планах значения линейных форм исходной и двойственной задач равны между собой: Пример 18. Найти максимальное значение функции при условиях Решение. Умножая первое и третье уравнения системы ограничений задачи на –1, в результате приходим к задаче нахождения максимального значения функции при условиях Взяв в качестве базиса векторы Р3, Р4 и Р5, составляем симплекс-таблицу (табл. 19). Таблица 19 i Базис Сб Р0 2 3 0 5 0 P1 P2 P3 p4 p5 1 2 3 4 p3 P4 p5 0 5 0 –12 10 –18 50 2 1 –3 3 –1 2 2 7 1 0 0 0 0 1 0 0 0 0 1 0 В 4-й строке таблице 19 нет отрицательных чисел. Следовательно, если бы в столбце вектора Р0 не было отрицательных чисел, то в таблице 19 был бы записан оптимальный план. Поскольку в указанном столбце отрицательные числа имеются и такие же числа содержатся в соответствующих строках, переходим к новой симплекс–таблице (таблица 20). Для этого исключим из базиса вектор Р5 и введем в базис вектор Р1. В результате получим псевдоплан X=(6;0;-24;4) Таблица 20 i Базис Сб Р0 2 3 0 5 0 P1 P2 P3 p4 p5 1 2 3 4 p3 P4 p1 0 5 2 –24 4 6 32 0 0 1 0 1/3 8/3 –2/3 9 1 0 0 0 0 1 0 0 2/3 1/3 –1/3 1 Так как в строке вектора Р3 нет отрицательных чисел, то исходная задача не имеет решения. |