5. Построение нового опорного плана

Переход к новому плану проводится пересчетом симплексной таблицы по методу Жордана-Гаусса. Сначала заменим переменные в базисе, т.е. вместо х_i в базис войдет переменная х_j, соответствующая направляющему столбцу.

Разделим все элементы ведущей строки предыдущей симплексной таблицы на разрешающий элемент и результаты деления внесем в строку следующей симплексной таблицы, соответствующего введенной в базис переменной х_j. В результате этого на месте завершающего элемента в следующей симплексной таблице будем иметь 1, а в остальных клетках j столбца, включая клетку столбца индексной строки, записываем нули. Остальные новые элементы нового плана находятся по правилу прямоугольника: ,

где СТЭ - элемент старого плана,

РЭ - разрешающий элемент,

А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

6. Полученный новый опорный план опять проверяется на оптимальность в соответствии с этапом 3 алгоритма

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

Если в направляющем столбце все коэффициенты а_ij≤0, то функция цели неограничена на множестве допустимых планов, т.е. и задачу решить нельзя.

Если в столбце симплексной таблицы содержатся два или несколько одинаковых наименьших значения, то новый опорный план будет вырожденным (одна или несколько базисных переменных станут равными нулю). Вырожденные планы могут привести к зацикливанию, т.е. многократному повторению процесса вычислений, не позволяющему завершить задачу. С целью исключения этого для выбора направляющей строки используют способ Креко, который заключается в следующем. Делим элементы строк, имеющие одинаковые наименьшее значение , на предполагаемые разрешающие элементы, а результаты заносим в дополнительные строки. За ведущую строку выбирается та, в которой раньше встречается меньшее число при чтении таблицы слева направо по столбцам.

Если в оптимальный план вошла дополнительная переменная х_n+1, то при реализации такого плана имеются недоиспользованные ресурсы i-ro вида в количестве, полученном в столбце свободных членов симплексной таблицы.

Если в индексной строке симплексной таблицы оптимального плана находится нуль, принадлежащий свободной переменной, не вошедшей в базис, а в столбце, содержащем этот-нуль, имеется хотя бы один положительный элемент, то задача имеет множество оптимальных планов. Свободную переменную, соответствующую указанному столбцу, можно внести в базис, выполнив соответствующие этапы алгоритма. В результате будет получен второй оптимальный план с другим набором базисных переменных.

Двойственная задача.

Двойственная задача формулируется следующим образом.

Определить оценку единицы каждого вида ресурсов, чтобы при заданных объемах ресурсов b_i, прибыли c_j, минимизировать оценку всех ресурсов торгового предприятия, затраченных на организацию торгового процесса.

Запишем математическую модель двойственной задачи.

Определить = (у₁, у₂,..., у_m), который удовлетворяет ограничениям

y_i≥0

и доставляет минимальное значение целевой функции

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

Для симметричной пары задач двойственная задача по отношению к исходной составляется согласно следующим правилам.

1. Число переменных в двойственной задаче равно числу ограничений в прямой задаче.

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

3. Система ограничений двойственной задачи записывается в виде неравенств противоположного смысла неравенствам системы ограничений прямой задачи.

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

5. На каждую переменную двойственной задачи накладывается условие не отрицательности

6. Двойственная задача решается на минимум, если целевая функция прямой задачи задается на максимум, и наоборот.

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

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

Установим сопряженные пары переменных прямой и двойственной задач. Запишем переменные задач в двух строчках. В первой располагаем переменные x_j по порядку номеров: сначала основные, затем - дополнительные, а во второй строке запишем переменные двойственной задачи: сначала дополнительные, затем - основные.

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