Методы оптимизации РЭС

6.1 Постановка задачи оптимизации РЭС

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

Оптимизация – определение наилучших в том или ином смысле значений показателей качества проектируемого объекта путем целенаправленного изменения его внутренних параметров (параметрическая оптимизация) или его структуры (структурная оптимизация). Математические методы структурной оптимизации пока разработаны слабо, поэтому применяется она редко и, в основном, при проектировании достаточно простых устройств. Параметрическая оптимизация имеет весьма солидное математическое обеспечение, поэтому играет основную роль в современном проектировании РЭС. По этим причинам в дальнейшем мы будем рассматривать только параметрическую оптимизацию, называя ее одним словом – оптимизация. При этом мы будем полагать, что нам известна математическая модель проектируемого объекта, которая может быть записана в виде , где Y и V – алгебраические векторы выходных и внутренних параметров объекта проектирования соответственно.

В схемотехническом проектировании роль внутренних параметров играют номиналы всех компонентов схемы (резисторов, емкостей, индуктивностей, п/п приборов и т.д.), а выходными обычно являются токи ветвей и узловые напряжения (точнее, их мгновенные значения или амплитуды). На основе выходных параметров устройства часто формируют его рабочие параметры и характеристики, как например, частотную зависимость коэффициент передачи по мощности, ширину переднего фронта импульса , полосу пропускания на уровне –3 дБ и пр., которые отражают потребительские свойства проектируемого устройства и могут служить его отдельными его показателями качества, которые должны удовлетворять требованиям ТЗ. При постановке задачи оптимизации выбирается либо выбирается один показатель качества устройства, требующий улучшения, либо из нескольких формируется обобщенный показатель. Поскольку не все внутренние параметры в равной мере влияют на выбранный показатель качества устройства, среди их выделяют те, изменение которых может привести к оптимальному результату. Именно из них формируют множество варьируемых параметров устройства , , которые будут участвовать в процессе оптимизации. Таким образом, математическая модель проектируемого устройства при постановке задачи оптимизации преобразуется к следующему виду:

,

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

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

,

где – множество физически реализуемых значений варьируемых переменных, которые образуют область допустимых значений вектора X.

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

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

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

При постановке задач оптимизации в САПР нужно преобразовать физические представления о назначении и степени полезности объекта в математическую формулировку экстремальной задачи, т.е. нужно сформулировать цели оптимизации и формализовать понятие оптимальности. Цели оптимизации выражаются в критерии оптимальности – правиле предпочтения сравниваемых вариантов.

Основу критерия оптимальности составляет целевая функция , аргументами которой являются управляемые параметры X. Согласно ГОСТ 23070-78, целевая функция – это функция управляемых параметров, которая в соответствии с выбранным критерием оптимальности является количественным выражением качества объекта проектирования. Другими словами, целевая функция должна оценивать количественно степень отличия существующего показателя качества проектируемого объекта от желаемого , т.е. должна быть такой, чтобы по ее значениям можно было определить степень достижения цели. В таком случае лучший вариант должен характеризоваться меньшим значением , тогда оптимизация заключается в минимизации . (В равной мере возможны целевые функции, требующие максимизации).

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

Заметим, что расстояние между двумя точками и в любом метрическом пространстве должно обладать следующими тремя свойствами:

1) и , если ;

2) ;

3) .

Каждое метрическое пространство характеризуется своим способом исчисления расстояния между точками. Для примера приведем несколько выражений, используемых для вычислений расстояний в пространствах с различными метриками:

; (6.1)

; (6.2)

; (6.3)

. (6.4)

Формула (6.1) определяет расстояние между двумя токами по прямой (пространство с эвклидовой метрикой); формула (6.2) – в пространстве, где путь между любыми двумя точками проходит вдоль ломанной прямой, отрезки которой идут вдоль координатных осей; в третьем пространстве в качестве расстояния между двумя точками принимается максимальная разность одноименных координат двух точек (6.3), а в четвертом (6.4) расстояние между двумя точками зависит от направления радиуса вектора в принятой системе координат, соединяющие эти точки. На рис.6.1,а,б,в,г показаны точки в пространстве , расположенные на равных расстояниях от начала координат, заданных формулами (6.1)-(6.4) соответственно.

Рисунок 6.1

Каждое из этих метрических пространств может использоваться, в принципе, для построения целевой функции.

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

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

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

Таким образом, итоговая математическая формулировка задачи оптимизации при проектировании имеет вид: минимизировать целевую функцию в области , заданной ограничениями и , т. е.

где . (6.5)

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

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

Частный критерий является функционалом той или иной выходной характеристики. В то же время частный критерий является многомерной функцией внутренних параметров устройства, в нашем случае вектора X.

Можно выделить два основных типа частных критериев оптимизации при проектировании РЭC: максимизирующий (или минимизирующий) и приближающий. Первый из них имеет целью найти экстремальное значение какого-либо параметра РЭС (например, G). Способ построения целевой функции, основанной на таком принципе очевиден – , если необходимо минимизировать абсолютное значение параметра G, или , если необходимо максимизировать абсолютное значение параметра G. Второй тип критерия ставит своей целью приблизить какой-либо параметр или характеристику устройства к заданной. Для составления целевой функции, основанной на втором критерии, следует использовать обобщенное понятие расстояния, определенное формулами (6.1)-(6.4). Разновидностью такого частного критерия является критерий максимального приближения одной из характеристик (например, амплитудно-частотной или переходной) объекта к заданному виду. Тогда целевая функция есть взвешенная сумма квадратов разностей ординат полученной и желаемой характеристик, взятых при M значениях независимой переменной f:

. (6.6)

Кроме среднеквадратичного критерия используется также минимаксный (чебышевский) критерий, при котором минимизируется максимальное по абсолютной величине отклонение:

. (6.7)

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

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

. (6.8)

Более широко используется аддитивный способ построения целевой функции

, (6.9)

где – весовой коэффициент.

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

6.3 Задачи линейного программирования и принципы поиска их решения

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

Таким образом, задача ЛП состоит в нахождении вектора переменных , минимизирующего линейную целевую функцию

(6.10)

при наличии ограничений в виде равенств

, (6.11)

и неравенств

, (6.12)

при условии неотрицательности всех элементов: , в предположении, что значения коэффициентов , и известны.

Задача в такой общей постановке называется основной задачей ЛП. Исторически сложились несколько видов частных задач ЛП: задача оптимального планирования, транспортная задача, задача о назначениях и т.д. Для примера можно привести формулировку задачи о рациональном питании, которая ставится следующим образом. Из имеющихся в распоряжении видов продуктов требуется составить такой рацион, который обеспечил бы организму необходимое количество питательных (белков, жиров, углеводов, витаминов, микроэлементов и т.д.) и вместе с тем требовал бы наименьших финансовых затрат. Такая задача особенно актуальна для составления рациона солдат, заключенных и студентов. Рассмотрим простую математическую модель этой задачи. Пусть имеются два вида продуктов и , содержащих питательные вещества , и . Обозначим символом количество питательного вещества (), содержащегося в единице продукта (). Кроме того нам известны: – ежесуточная потребность организма в питательном веществе и – стоимость единицы продукта . Требуется рассчитать количество продукта и количество продукта , чтобы обеспечить необходимое количество питательных веществ при минимальных затратах на пищу.

Очевидно, что общая стоимость пищи будет:

. (6.13)

Общее количество вещества в каждом из видов продуктов должно быть не меньше, чем необходимое, т.е.:

: ;

: ; (6.14)

: .

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

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

а) Максимизация целевой функции равносильна минимизации функции .

б) Ограничения в виде неравенств

и

могут быть приведены к ограничениям в виде равенств

и

путем введения в них новых фиктивных неотрицательных переменных и . Чтобы эти фиктивные переменные не влияли на целевую функцию , необходимо положить коэффициенты перед ними и в (6.11) равными нулю.

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

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

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

;

; (6.15)

.

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

Возможна также альтернативная формулировка задачи линейного программирования, в которой все ограничения имеют вид неравенств.

В ЛП принята следующая терминология:

– любое неотрицательное решение системы ограничений называется допустимым;

– допустимое решение, дающее минимум функции , называется оптимальным.

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

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

Однако следует учесть, что неизвестные , ,..., подчинены некоторым условиям (ограничениям, а также условиям неотрицательности), поэтому «точка» () пробегает не все N -мерное пространство, а лишь некоторую область в нем. Невозможность одновременного обращения в нуль всех производных функции означает, что ее минимум не может находиться внутри области допустимых значений X, и, если он вообще существует, то должен лежать на границе области. Между тем граница области, заданной с помощью системы уравнений и неравенств, представляет собой довольно сложный объект, и отыскание минимума на границе превращается в достаточно сложную самостоятельнуюзадачу.

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

при наличии следующих ограничений:

;

;

.

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

;

;

; ,

которые вытекают из ограничений в данной задаче ЛП. Стрелки на каждой граничной прямой показывают, с какой стороны прямой выполняется ограничение. Для точек внутри заштрихованной области ОАВС и на ее границах выполняются ограничения задачи.

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

при двух значениях константы и .

Эти параллельные прямые представляют собой две линии равного уровня F со значениями 0 и -68 соответственно. Целевая функция убывает в направлении, показанному на рис. 6.1 широкой стрелкой, которое противоположно направлению градиента целевой функции .

Из приведенного рисунка видно, что линия наименьшего уровня целевой функции проходит через точку B с координатами , . Результат графического решения поставленной задачи ЛП можно сформулировать так: минимум целевой функции достигается на границе области допустимых значений X в точке , .

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

;

.

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

,

,

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

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

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

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

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

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

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

6.4 Численные методы решения задач линейного программирования. Симплекс-метод

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

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

Пусть необходимо минимизировать целевую функцию

(6.16)

при наличии ограничений в виде равенств:

, (6.17)

при , .

Работа симплекс-метода начинается с любого допустимого базисного решения. Получить это решение можно, приведя систему уравнений (6.17) к следующему виду:

, . (6.18)

, а M (по числу уравнений) из N неизвестных явно выражены через остальные неизвестных.

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

.

Считая все небазисные неизвестные равными нулю:

,

из системы (6.18) найдем значения базисных неизвестных:

.

Полученное таким путем решение системы: () является базисом. Значение функции для него равно:

.

Решение задачи при помощи симплекс-метода распадается на ряд шагов. Каждый k –й шаг состоит в том, что от данного базиса k мы переходим к другому базису k +1 с таким расчетом, чтобы значение уменьшилось или, по крайней мере, не увеличилось: . Новый базис k +1 получается из старого k весьма просто: из k -го базиса удаляется одна из неизвестных и взамен нее вводится другая (из числа прежних небазисных). Разумеется, изменение базиса влечет за собой соответствующую перестройку системы (6.18). После некоторого числа таких шагов мы или приходим базису K, для которого есть искомый минимум формы , а соответствующее базисное решение является оптимальным, или же выясняем, что задача решения не имеет.

Идею метода лучше всего проследить на примерах.

Пример 1. Пусть заданная целевая функция и система ограничений приведены к виду:

;

;

;

.

Здесь неизвестные образуют базис. Соответствующее базисное решение есть

(1, 2, 3, 0, 0),

а значение целевой функции .

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

Так как увеличение приводит к увеличению , то для такой опасности не существует. Рассматривая и , находим, что может быть увеличено до 2 (и не более, иначе станет отрицательным), что дает , и . В итоге получаем новое допустимое решение (5, 0, 1,0, 2), в котором число положительных неизвестных по-прежнему равно трем. Значе­ние F для этого решения равно –2.

Новый базис теперь состоит из . Чтобы осуществить соответствующую перестройку системы ограничений, нужно выразить эти неизвестные через . Начинаем с уравнения для (нового небазисного неизвестного), из которого выражаем (новое базисное неизвестное):

;

затем выражаем и F

;

;

.

Итак, задача приведена к виду

;

;

;

.

Новое базисное решение есть

(5, 0, 1, 0, 2);

значение F для этого решения равно –2. На этом заканчивается первый шаг процесса.

Выясним, нельзя ли еще уменьшить значение F. Коэффициент при в выражении для F отрицателен, поэтому можно попытаться уменьшить F за счет увеличения (без изменения ). Первое и второе уравнения этому нисколько не препятствуют, а из третьего уравнения видно, что можно увеличить до 1/5 (и не более, иначе станет отрицательным). Полагая , , получим , , . В итоге имеем новое допустимое решение (28/5, 0, 0, 1/5, 12/5).

Новый базис теперь состоит из . Из уравнения для (нового небазисного неизвестного) выражаем (новое базисное неизвестное):

и подставляем это выражение в остальные уравнения. В итоге система принимает вид

;

;

;

.

Новое базисное решение есть

(28/5, 0, 0, 1/5, 12/5),

а соответствующее ему значение целевой функции равно –11/5. На этом заканчивается второй шаг процесса.

Так как в последнюю запись целевой функции F оба неизвестных и входят с положительными коэффициентами, минимум F достигается при . Это означает, что последнее базисное решение (28/5, 0, 0, 1/5, 12/5) является оптимальным и искомый минимум F равен –11/5. Задача решена.

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

Пример 2.

;

;

Здесь базис образован неизвестными , . Базисное решение имеет вид

(0, 0, 1, 2);

соответствующее значение формы F равно 0.

Коэффициент при в выражении для F отрицателен, поэтому пытаемся увеличить (не меняя ). Первое уравнение этому не препятствует, из второго же уравнения видно, что можно увеличить только до 2, что дает , . Новое допустимое решение есть (2, 0, 3, 0); значение F для этого решения равно –2.

Новый базис теперь состоит из , . Выражаем из второго уравнения и подставляем это выражение в первое уравнение, а также в F. Задача принимает вид

;

;

Новое базисное решение есть

(2, 0, 3, 0),

а соответствующее ему значение F равно –2.

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

6.5 Симплекс-метод в общем виде

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

, (6.19)

; (6.20)

напомним, что все свободные члены неотрицательны. Исходный базис Б здесь образован неизвестными , , …, а базисное решение есть

(, …, , 0,..., 0); (6.21)

значение F для этого решения равно

Возможны два случая.

I. Все числа , …, неположительны. Тогда минимальное значение F достигается при , т. е. базисное решение является оптимальным.

II. Среди чисел , …, имеются положительные. Пусть , где j — одно из чисел , …, N. Тогда можно попытаться, не изменяя нулевых значений всех небазисных неизвестных кроме , уменьшить значение F за счет увеличения . Однако здесь следует соблюдать некоторую осторожность, так как выбор значения влияет на значения ,…, и нужно следить за тем, чтобы ни одно из этих значений не стало отрицательным.

Полагая в (6.19) и (6.20) все числа ,…, равными нулю, кроме ,получим

.

Здесь, в свою очередь, могут представиться два случая.

A. Все величины , , …, неположительны. Тогда
при любом положительном , имеем:

, , …, ;

следовательно, значения , , …, неотрицательны. Что же касается формы F, то, взяв в качестве достаточно большое положительное число, можно (ввиду ) сделать значение F как угодно большим по абсолютной величине отрицательным числом. Таким образом, в случае А минимум F равен –¥, или, говоря точнее, не достигается.

B. Среди величин , , …, имеются положительные. Пусть , где n — одно из чисел 1, 2,..., M. Тогда нельзя увеличить более чем до — (в противном случае станет < 0). Найдем среди всех отношений , отвечающих положительным , наименьшее; пусть это будет . Таким образом, по всем n, для которых .

Число называется разрешающим элементом.

В целях краткости обозначим указанный минимум через r. Если он достигается сразу при нескольких значениях n, то в качестве i берем любое из них. Очевидно, . Ясно, что теперь , можно увеличить до r (и не более, иначе станет < 0). Полагая

, …, , , , (6.22)

найдем значения остальных неизвестных;

. (6.23)

Теперь новый базис Б' состоит из неизвестных , …, , , … ; соответствующее базисное решение есть (6.22), (6.23); значение F для этого решения равно

(6.24)

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

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

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

. (6.25)

(Здесь слева стоят неизвестные , …, ,, , … , а в правые части входят , …, ,, , … .

Штрихи служат для того, чтобы отличать коэффицие

Дата добавления: 2014-10-15; Просмотров: 2795; Нарушение авторских прав?; Мы поможем в написании вашей работы!