Линейное программирование. Геометрическая интерпретация и графический метод решения задачи линейного программирования, страница 15

2. Среди отрицательных коэффициентов b_i выбираем коэффициент b_r, наибольший по абсолютной величине, и строку r называем ведущей.

3. В ведущей строке проверяем знаки всех коэффициентов a_rj , j=1, …, n. Если все a_rj ³ 0, имеет место случай 3. Переходим к шагу 4.

4. Среди отрицательных коэффициентов a_rj ведущей строки выбираем элемент a_rs, для которого  D_s/a_rs = max (D_j/a_rj).

и называем его ведущим.

5. Выполняем жорданово преобразование симплекс-таблицы с ведущим элементом a_rs и переходим к шагу 1.

Оптимальный план прямой задачи задается списком базисных переменных и их значениями в столбце B, двойственной задачи – переменными двойственной задачи, сопоставленными базисным столбцам исходной задачи, и их значениями в оценочной строке D.

Задачи в двойственной базисной форме, к которым можно непосредственно применить изложенный алгоритм, возникают различными путями, рассмотренными в [4].

В дальнейшем двойственный симплекс-метод будет использоваться нами при решении задач целочисленного линейного программирования.

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

2.8.  Некоторые классы задач линейного программирования

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

К такому классу, в первую очередь, относится так называемая транспортная задача [4…6]. Она характеризуется следующими особенностями.

Имеется m пунктов производства некоторого однородного продукта и n пунктов его потребления. Известны запасы a_i продукта в каждом пункте-поставщике i=1, …, m, спрос b_j в каждом пункте-пот-ребителе j=1, …, n и расходы c_ij на перевозку единицы продукта из пункта i в пункт j.

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

Такая задача характеризуется ограничениями-равенствами двух видов, учитывающими запасы и спрос, а также двухиндексными переменными оптимизации x_ij , имеющими смысл объемов перевозок продукта из пункта i в пункт j.

Транспортная задача в принципе может быть решена симплекс-методом. Однако для ее решения используют специальные, более простые методы [4…6]. Упрощение процедуры решения такой задачи обусловлено структурой векторов-столбцов A_j , имеющих в данной задаче  две компоненты, равные 1, и остальные компоненты, равные 0. 

Транспортная задача имеет как обобщения, так и частные случаи. Обобщением транспортной задачи являются задачи на транспортной сети. Частным случаем транспортной задачи является задача о назначениях.

Отметим также, что в рамках ЛП помимо нахождения оптимального плана может также решаться задача анализа модели на чувствительность (или устойчивость). При таком анализе исследуется влияние изменения коэффициентов c_j, a _ij и b_i  на оптимальное решение [1,7,18].

С анализом устойчивости тесно связан раздел ЛП, называемый параметрическим программированием [6,7,27] . В его рамках с помощью параметра l, изменяющегося в некоторых пределах, задаются соответствующие диапазоны изменения  коэффициентов c_j, a _ij и b_i . При решении задачи параметрического программирования определяются диапазоны (интервалы) изменения l, в каждом из которых существует определенный оптимальный план.