Поиск оптимального решения

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

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

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

Имеется несколько вариантов алгоритма симплекс-метода: обычный, m -метод (искусственного базиса) и др.

Рассмотрим вариант, позволяющий осуществлять наиболее
простые вычисления.

Алгоритм симплекс-метода включает несколько этапов:

1) подготовка информации (включает введение переменных
и формирование ограничений);

2) преобразование ограничений и запись их в матрицу;

3) поиск опорного решения;

4) поиск оптимального решения.

К примеру, имеем следующую экономико-математическую
задачу:

.

Преобразование ограничений связано, в первую очередь, с превращением неравенств в уравнения. Если при этом ограничения приведены к типу , то процедура вычислений значительно
упрощается. Для этого ограничения типа умножим на (-1).

Превращение неравенств в уравнения связано с введением
дополнительных переменных. В ограничениях типа дополнительные переменные обозначают величину недоиспользования
ресурсов, в ограничениях типа — величину превышения ресурсов над минимумом потребности в них.

В уравнения дополнительные переменные не вводятся (или вводятся равными нулю):

При этом всякое решение осуществляется из допущения, что

, тогда

,

,

,

.

Решение получаем поиском опорного и оптимального решений.

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

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

В первой симплексной таблице (таблица 5.1) такими базисными будут дополнительные переменные, т. е. вектор дополнительных переменных. Остальные переменные, обозначающие вектор-столбцы, будут небазисными. В таблице 5.1 небазисными будут основные переменные.

Таблица 5.1 — Симплексная таблица № 1

Базисные переменные	Свободные члены	Небазисные переменные
			…
					…
					…
					…
………………………………………………
					…
					…

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

– имеются отрицательные свободные члены;

– имеются 0-значения среди базисных переменных.

Всю информацию при допущении, что заносим в таблицу. Таблица 5.1 содержит т + 2строк (где т — число строк ограничений) и п + 2 столбцов (где п — число небазисных переменных).

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

Нахождение опорного решения предполагает замену базисных переменных небазисными или поиск нового базиса. Чтобы исключить 0 с вектора базисных переменных необходимо в 0-строке найти такой коэффициент, от деления на который коэффициента А_т,получим наименьшее положительное частное. Для этого вектор-столбец свободных членов делим на соответствующие коэффициенты столбцов . Допустим, что при делении
на коэффициенты первого столбца, т. е. отношение . Это означает, что требование не выполняется. В другом случае (при ) . Допустим, что при делении отношение меньше всех других значений.

Тогда коэффициент можно принять за разрешающий.
Он указывает на то, что 0-значение и коэффициент поменяются местами. Эта замена означает, что целевая функция (или полупространство F) переместилась параллельно самой себе и поэтому значение коэффициентов изменяется. Замена значений требует
вычислений, которые всегда осуществляются по одним и тем же правилам.

Для записи формул, по которым определяются коэффициенты новой симплексной таблицы (таблица 5.2), введем условные обозначения, в частности, — коэффициент, стоящий в строке i
и столбце j. При этом F -строка будет иметь значение i + 1, а столбец свободных членов j = 0.

Таблица 5.2 — Симплексная таблица № 2

Базисные переменные	Свободные члены,	Небазисные переменные
…………………………………………………………..

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

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

Правила:

1. Новый коэффициент (вместо разрешающего) равен обратному от него, т. е. или в данном случае .

2. Новые коэффициенты столбца разрешающего элемента равны коэффициентам предыдущей таблицы, деленным на разрешающий коэффициент с противоположным значением:

(при ),

т. е. в данном случае — при .

3. Новые коэффициенты строки разрешающего элемента равны коэффициентам предыдущей таблицы этой строки, деленным
на разрешающий коэффициент:

(при ) или , при .

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

(при ) .

Перебросив 0-значения из базисных значений в небазисные, получим в n -мерном пространстве т независимых векторов. Затем вычеркиваем 0-столбец, который в дальнейших расчетах участия не принимает. Просматривая столбец свободных членов, находим среди них отрицательные члены. Чтобы получить опорное решение, превращаем отрицательные свободные члены в положительные. Для этого базисные переменные с отрицательными свободными членами необходимо перевести в небазисные. При этом делаем столько шагов (таблиц), сколько имеется отрицательных свободных членов. За основу принимаем любую строку с отрицательным свободным членом. Лучший вариантом является та строка, среди коэффициентов которой имеется больше единиц или целых чисел. Случается, что все свободные члены являются отрицательными
и им соответствуют отрицательные коэффициенты в каком-то из столбцов. В этом случае опорное решение можно получить за один шаг, взяв в качестве разрешающего коэффициента отрицательный коэффициент, от деления на который получается наибольшее положительное частное. Таким образом, за один шаг все отрицательные свободные члены будут превращены в положительные.

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

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

Если , то получим меньшее значение, чем от деления других частных .

Допустим, что в данном случае частное — меньше всех других. Следовательно, коэффициент () является разре-
шающим.

Меняем местами и , после чегопроводим расчеты
по приведенным выше четырем правилам (таблица 5.3).

Таблица 5.3 — Симплексная таблица № 3

Базисные переменные	Свободные члены	Небазисные переменные
………………………………………………..

В этой таблице содержится опорное решение. Оно получено
при следующих значениях переменных:

.

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

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

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

Допустим, что от деления С ₃ на с ₃₂ было получено наименьшее положительное частное. Следовательно, х ₂ и х ₁ меняются местами, и мы находим новое решение по четырем правилам.

Вычисления будем продолжать до тех пор, пока в F -строке
не получим положительные значения (при решении задачи на максимум) или отрицательные (при решении задачи на минимум).

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

При использовании симплекс-метода возможны следующие четыре особых случая:

1. Вырожденность.

2. Альтернативные оптимальные решения.

3. Неограниченные решения.

4. Отсутствие допустимых решений.

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

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

Из двух ограничений ресурсного типа второе является избыточным. При графическом решении (рис. 2.4) это очевидно, но из данных симплексной таблицы такой вывод сделать не удается. При исключении из базиса дополнительной переменной, соответствующей второму ограничению, значение функционала не возрастет. В итоге получим точку A, как оптимальное решение, которое не перестает быть верным от того, что оно вырожденное.

Рис. 2.4

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

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

Альтернативные оптимальные решения. Согласно основной теореме линейного программирования, если целевая функция достигает экстремального значения более чем в одной угловой точке, то она принимает это же значение в любой точке, являющейся их выпуклой линейной комбинацией. Графическая иллюстрация для случая двух переменных приведена на рис. 2.5. Максимальное значение целевая функция получает в угловых точках A и B. Предположим, что при использовании симплекс-метода получена точка A как оптимальный план. Тогда небазисной переменной будет соответствовать нулевая оценка, так как при ее введении в базис с последующим переходом к точке B значение функционала не изменится.

Рис. 2.5

Таким образом, признаком существования альтернативных планов является наличие нулевых оценок для небазисных переменных. На практике существование альтернативных решений можно использовать для учета дополнительных соображений при выборе плана действий. Если рассмотренный пример интерпретировать как задачу об оптимальном производственном плане, то лучше выбрать точку B, чтобы меньше зависеть от изменений рыночной конъюнктуры.

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

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

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

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

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

Рис. 2.6

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

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

Однако причина отсутствия допустимых решений может быть и весьма тривиальна — неправильно поставленная десятичная запятая, или ошибочное занесение правильного числового значения, но не в ту ячейку. Чем больше размерность задачи, тем вероятнее подобные ошибки и тем труднее их искать. Для выявления таких ошибок можно рекомендовать вводить в модель переменные, которые показывали бы, сколько и какого именно ресурса недостает. Разумеется, таким переменным в функционале должны соответствовать некоторые штрафы иначе недостающие ресурсы войдут в решение, что не имеет смысла. Величины штрафов произвольны, но достаточно велики для того чтобы соответствующие переменные (будем называть их штрафными) могли войти в решение только тогда когда иначе невозможно выполнить остальные ограничения задачи. Слишком большие штрафы будут только способствовать росту ошибок округления. В соответствии с принципом “разумной достаточности” можно, например, ориентировочную цену реального ресурса увеличить на порядок.

Дата добавления: 2014-12-07