Двойственный симплекс-метод и доказательство теоремы двойственности
YA ( С.
X ( 0. Y ( 0.
Таким образом, прежде чем записать двойственную задачу для данной
исходной, систему ограничений исходной задачи необходимо привести к
соответствующему виду. Запишем, например, математическую модель
двойственной задачи для следующей исходной.
Найти минимальное значение линейной функции Z = 2x1 + x2 + 5x3 при
ограничениях
x1 – x2 – x3 ( 4,
x1 – 5x2 + x3 ( 5, xj ( 0 (j = 1, 2, 3).
2x1 – x2 + 3x3 (6,
Рассматриваемая задача относится к симметричным двойственным задачам на
отыскание минимального значения линейной функции. Для того чтобы было можно
записать двойственную задачу, ее модель должна иметь вид (3). Переход
осуществляется умножением первого неравенства на -1.
Исходная задача:
Zmin = 2x1 + x2 + 5x3 при ограничениях
-x1 + x2 + x3 ( -4,
x1 – 5x2 + x3 ( 5, xj ( 0 (j = 1, 2, 3).
2x1 – x2 + 3x3 (6,
Двойственная задача:
fmin = -4x1 + 5x2 + 6x3 при ограничениях
-y1 + y2 + 2y3 ( 2,
y1 – 5y2 - y3 ( 1, yi ( 0 (i = 1, 2, 3).
2y1 + y2 + 3y3 ( 5,
Приведем без доказательства следующую теорему. Теорема 1.1. Если при
подстановке компонент оптимального плана в систему ограничений исходной
задачи i-e ограничение обращается в неравенство, то i-я компонента
оптимального плана двойственной задачи равна нулю.
Если i-я компонента оптимального плана двойственной задачи
положительна, то i-e ограничение исходной задачи удовлетворяется ее
оптимальным решением как строгое равенство.
5. Двойственный симплексный метод
В п. 2 и п. 3 настоящего параграфа было показано, что для получения
решения исходной задачи можно перейти к двойственной и используя оценки ее
оптимального плана, определить оптимальное решение исходной задачи.
Переход к двойственной задаче не обязателен, так как если рассмотреть
первую симплексную таблицу с единичным дополнительным базисом, то легко
заметить, что в столбцах записана исходная задача, а в строках -
двойственная. Причем оценками плана исходной задачи являются Сj а оценками
плана двойственной задачи – bi. Решим "двойственную задачу по симплексной
таблице, в которой записана исходная задача; найдем оптимальный план
двойственной задачи, а вместе с ним и оптимальный план исходной задачи.
Этот метод носит название двойственного симплексного метода,
Пусть необходимо решить исходную задачу линейного программирования,
поставленную в общем виде: минимизировать функцию Z =СХ при АХ = A0, Х ( 0.
Тогда в двойственной задаче необходимо максимизировать функцию f = YA0 при
YA ( С. Допустим, что выбран такой базис D = (A1, А2, ..., Аi, ..., Аm),
при котором хотя бы одна из компонент вектора Х = D-1 A0 = (x1, x2, ...,
xi, ..., xm) отрицательная (например, xi < 0), но для всех векторов Aj
выполняется соотношение Zj – Cj ( 0 (i = 1,2, ..., n). Тогда на основании
теоремы двойственности Y = Сбаз D-1 - план двойственной задачи. Этот план
не оптимальный, так как, с одной стороны, при выбранном базисе X содержит
отрицательную компоненту и не является планом исходной задачи, а с другой
стороны, оценки оптимального плана двойственной задачи должны быть
неотрицательными.
Таким образом, вектор Аi, соответствующий компоненте xi < 0, следует
исключить из базиса исходной задачи, а вектор, соответствующий
отрицательной оценке,— включить в базис двойственной задачи.
Для выбора вектора, включаемого в базис исходной задачи, просматриваем
i-ю строку: если в ней не содержатся xij < 0, то линейная функция
двойственной задачи не ограничена на многограннике решений, а исходная
задача не имеет решений. Если же некоторые xij < 0, то для столбцов,
содержащих эти отрицательные значения, вычисляем (0j= min (xi/xij) ( 0 и
определяем вектор, соответствующий max (0j(Zj — Cj) при решении исходной
задачи на минимум и min (0j(Zj — Cj) при решении исходной задачи на
максимум. Этот вектор и включаем в базис исходной задачи. Вектор, который
необходимо исключить из базиса исходной задачи, определяется направляющей
строкой.
Если (0j= min (xi/xij) = 0, т. е. xi = 0, то xij берется за разрешающий
элемент только в том случае, если xij > 0. Такой выбор разрешающего
элемента на данном этапе не приводит к увеличению количества отрицательных
компонент вектора X. Процесс продолжаем до получения Х ( 0; при этом
находим оптимальный план двойственной задачи, следовательно, и оптимальный
план исходной задачи.
В процессе вычислений по алгоритму двойственного симплексного метода
условие Zj – Cj ( 0 можно не учитывать до исключения всех хi < 0, затем
оптимальный план находится обычным симплексным методом. Это удобно
использовать, если все хi < 0; тогда для перехода к плану исходной, задачи
за одну итерацию необходимо (0j определить не по минимуму, а по максимуму
отношений, т. е. (0j= max (xi/xij) > 0.
Двойственным симплексным методом можно решать задачи линейного
программирования, системы ограничений которых при положительном базисе
содержат свободные члены любого знака. Этот метод позволяет уменьшить
количество преобразований системы ограничений, а также размеры симплексной
таблицы.
Список используемой литературы
Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике.
«Финансы и статистика», 1998 г.
Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое
программирование. «Наука», 1980 г.
| |  скачать работу |
Двойственный симплекс-метод и доказательство теоремы двойственности |
