Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

Идея метода минимизации невязок

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

Не умаляя общности, можно считать, что вектор ограничений в исходной задаче неотрицателен, т. е. bi ≥ 0, i 1: m. Тогда для КЗЛП максимизации функции

на множестве, определяемом ограничениями

строится вспомогательная задача

Как видно из (1.36)-(1.39), задача (,) отличается от задачи (D, f) матрицей, получаемой в результате добавления к исходной матрице А единичной матрицы, которой соответствуют дополнительные (фиктивные) переменные хn+1,...,хn+m. Данным переменным (собственно говоря, их и называют невязками) в целевой функции отвечают коэффициенты (-1), а переменным х1,...,хn, которые являются общими для обеих задач, — нулевые коэффициенты. Существенной особенностью (,) является наличие в ней очевидного исходного базиса, образуемого добавленными столбцами, и соответствующего плана с базисными компонентами хn+i = bi ≥ 0, i 1: m. В силу структуры целевой функции в процесс поиска ее максимума процедурой симплекс-метода фиктивные переменные (невязки) хn+i должны минимизироваться желательно до нуля, что может быть достигнуто за счет последовательного перевода их в небазисные компоненты плана. Если в оптимальном плане х̃, полученном в результате решения вспомогательной задачи, последние m компонент (т. е. невязки) равны нулю, то его начальные n компонент удовлетворяют системе ограничений, определяющих область D, и легко (простым отбрасыванием невязок) может быть преобразован в стартовый допустимый план основной задачи (D, f). При этом все строки симплекс-таблицы, полученной на последней итерации вспомогательной задачи (за исключением нулевой), могут быть перенесены в первую таблицу основной задачи. Элементы же нулевой строки для вновь формируемой симплекс-таблицы вычисляются по формулам:

где β(*) — базис, полученный на последней итерации вспомогательной задачи.

В случае, когда оптимальный план вспомогательной задачи х̃ все же содержит не равные нулю фиктивные компоненты (т. е. ()<0), мы приходим к заключению об отсутствии допустимых планов у исходной задачи (D, f), т. е. D = Ø.