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

Пусть необходимо решить исходную задачу линейного программиро­вания, поставленную в общем виде: минимизировать функцию Z =СХ при АХ = A₀, Х ≥ 0. Тогда в двойственной задаче необходимо максимизировать функцию f = YA₀ при YA ≤ С. Допустим, что выбран такой базис D = (A₁, А₂, ., А_i, ., А_m), при котором хотя бы одна из компонент вектора Х = D-1 A₀ = (x₁, x₂, ., x_i, ., x_m) отрицатель­ная (например, x_i < 0), но для всех векторов Aj выполняется соотно­шение Z_j – C_j ≤ 0 (i = 1,2, ., n). Тогда на основании теоремы двойственности Y = С_баз D-1 - план двойственной задачи. Этот план не оптимальный, так как, с одной стороны, при выбранном бази­се X содержит отрицательную компоненту и не является планом исходной задачи, а с другой стороны, оценки оптимального плана двой­ственной задачи должны быть неотрицательными.

Таким образом, вектор А_i, соответствующий компоненте x_i < 0, следует исключить из базиса исходной задачи, а вектор, соответствую­щий отрицательной оценке,— включить в базис двойственной задачи.

Для выбора вектора, включаемого в базис исходной задачи, просмат­риваем i-ю строку: если в ней не содержатся x_ij < 0, то линейная функция двойственной задачи не ограничена на многограннике реше­ний, а исходная задача не имеет решений. Если же некоторые x_ij < 0, то для столбцов, содержащих эти отрицательные значения, вычисля­ем q_0j= min (x_i/x_ij) ≥ 0 и определяем вектор, соответствующий max q_0j(Z_j — C_j) при решении исходной задачи на минимум и min q_0j(Z_j — C_j) при решении исходной задачи на максимум. Этот вектор и включаем в базис исходной задачи. Вектор, который необ­ходимо исключить из базиса исходной задачи, определяется направ­ляющей строкой.

Если q_0j= min (x_i/x_ij) = 0, т. е. x_i = 0, то x_ij берется за раз­решающий элемент только в том случае, если x_ij > 0. Такой выбор раз­решающего элемента на данном этапе не приводит к увеличению коли­чества отрицательных компонент вектора X. Процесс продолжаем до получения Х ≥ 0; при этом находим оптимальный план двойственной задачи, следовательно, и оптимальный план исходной задачи.

В процессе вычислений по алгоритму двойственного симплексного метода условие Z_j – C_j ≤ 0 можно не учитывать до исключения всех х_i < 0, затем оптимальный план находится обычным симплексным ме­тодом. Это удобно использовать, если все х_i < 0; тогда для перехода к плану исходной, задачи за одну итерацию необходимо q_0j определить не по минимуму, а по максимуму отношений, т. е. q_0j= max (x_i/x_ij) > 0.

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

1.4.Двойственность и анализ чувствительности.

Оптимальное решение в задаче линейного программирования определяется теми условиями, которые нашли отражение в модели в момент ее формирования. В реальной жизни условия в течение времени меняются, следовательно нам важны средства, которые позволяют оценить изменения в оптимальном решении. Эти изменения вызваны изменениями в параметрах модели – анализ на чувствительность – теория двойственности-1 из способов анализа.

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

Правила преобразования прямой задачи в двойственную:

1. Каждому из m ограничений прямой задачи соответствует переменная двойственной задачи.

2. Каждой из n переменных прямой задачи соответствует ограничения двойственной задачи.

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

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