Двойственный симплекс-метод и доказательство теоремы двойственности (стр. 4 из 4)

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

Для выбора вектора, включаемого в базис исходной задачи, просматриваем i-ю строку: если в ней не содержатся x_ij < 0, то линейная функция двойственной задачи не ограничена на многограннике решений, а исходная задача не имеет решений. Если же некоторые x_ij < 0, то для столбцов, содержащих эти отрицательные значения, вычисляем q_0j= min (x_i/x_ij) ³ 0 и определяем вектор, соответствующий maxq_0j(Z_j — C_j) при решении исходной задачи на минимум и minq_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.

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

6. Список используемой литературы

1. Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. «Финансы и статистика», 1998 г.

2. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. «Наука», 1980 г.