I этап. Условная оптимизация. Установите последовательность этапов задачи условной оптимизации


лекция_8

Оптимизация технических объектов в системах автоматизированного проектирования.

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

Проблема оптимизации имеет два основных аспекта: 1) нужно поставить задачу, формализовав понятия «наилучший», «опти­мальный»; 2) нужно решить задачу, уже имеющую матема­тическую формулировку.

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

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

Основные определения

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

Будем рассматривать объекты, имеющие неизменную структуру и различающиеся численными значениями параметров внутренних X = (х1, ..., хn) и выходных Y = (у1 y3, ..., уn). В основе постро­ения правила предпочтения лежит целевая функция, коли­чественно выражающая качество объекта и потому называемая также функцией качества. Значения целевой функции тем боль­ше, чем выше качество объекта. Применяют также функции, убываю­щие с улучшением качества. Оптимизация в первом случае есть макси­мизация, а во втором — минимизация функции качества. Аргумен­тами этой функции являются управляемые параметры — внутренние параметры, которые можно изменять на данном этапе про­ектирования. Обозначим вектор управ­ляемых параметров - X*.

Обозначим целевую функцию через F(Х), а область ее определе­ния — через ХО. Если ХО есть дискретное множество точек, то объ­ект дискретный и задача оптимизации относится к области дискрет­ного (в частном случае целочисленного) программирования, в про­тивном случае должна применяться параметрическая оптимизация непрерывных объектов.

Безусловные экстремумы. ε-Окрестностью некоторой точки Х0 будем называть множество Sε (X) точек (векторов), которые находятся от точки Х0 на расстоянии, не превышающем заданное число ε > 0:

Sε (X0) = {X| ||Х-Х0[|ε }, (1)

где ||Х — Х0||- норма вектора X — Х0, отождествляемая с рас­стоянием между точками X и Х0.

Выражение множеств в виде (1) будем использовать и в даль­нейшем, поэтому запишем словесную расшифровку (1) еще раз: множество Sε (X0) есть множество объектов X при выполнении усло­вия ||Х —Х0|| < ε.

Максимумом функции F(X) называют ее значение F(X*), если существует число ε > 0 такое, что для любой точки X  Sε (X*) (за исключением лишь самой точки X* выполняется неравенство

F(X)-F(X*)<0. (2)

Минимумом функции F(X) называют ее значение F(Х*), если при тех же условиях вместо (2) имеем F(X) — F(X*)> 0.

Точку X* называют экстремальной точкой (локальным экстремумом). Функция F(X) одноэкстремальна (унимодальна), если имеет один экстремум, и многоэкстремальна, если имеет более одного максимума (минимума).

В зависимости от характера целевых функций (многоэкстремаль­ные или одноэкстремальиые) различают одно- и многоэкстремальные задачи оптимизации.

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

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

Условные экстремумы. В задачах проектирования, как правило, присутствуют те или иные ограничения. Прежде всего, отметим прямые ограничения — ограничения вида

xi>xнi и xti<xbi, (3)

где xнi и xbt — минимально и максимально возможные значения i-го управляемого параметра.

Прямые ограничения в ряде случаев принципиально необходимы. Типичными примерами могут служить ограничения вида xi>0 для всех параметров, которые по физическим соображениям не могут быть отрицательными. Это геометрические размеры, массы, концент­рации примесей, электрические сопротивления и т. п. Во многих случаях, когда прямое ограничение не является принципиально не­обходимым, его вводят специально для того, чтобы ограничить об­ласть поиска экстремума. Область ХД в пространстве управляемых параметров, заданную прямыми ограничениями, называют допу­стимой областью

где n — размерность пространства управляемых параметров: [1 : п]— множество целых чисел в интервале [1, n].

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

Ограничения-неравенства имеют вид

(Х)>0, (4)

где  (Х) — вектор-функция.

Прямые ограничения можно рассматривать как частный случай функциональных ограничений (4).

Ограничения-равенства имеют вид

ψ (X) = О, (5)

где ψ (X) — вектор-функция.

Наличие ограничений приводит к задаче условной опти­мизации. Решение этой задачи — условный экстремум.

В задачах проектирования часто роль ограничений (4) и (5) выполняют условия работоспособности, тогда область ХР, определяе­мую как

называют областью работоспособности.

Необходимые и достаточные условия экстремума.

Классические методы безусловной оптимизации применяют в тех случаях, когда известен вид целевой функции F(X), т. е. дано ее аналитическое вы­ражение, и предполагается, что F(X) не менее чем дважды дифферен­цируема по управляемым параметрам. Тогда для определения экстре­мума используют необходимые и достаточные условия безусловного экстремума. Эти условия легко получить с помощью разложения F(X) в окрестностях экстремальной точки в ряд Тейлора для функции yj{X).

Имеем

(7)

где

градиент целевой функции; ΔХ = X — X*; Ю — матрица Гессе (ее элементы — вторые производные целевой функции по управляе­мым параметрам).

Очевидно, что условие (2) может выполняться, только если линей­ный член<grad F(X), ΔХ > равен нулю. Следовательно, необходимым условием экстремума является условие

grad F (X) = 0.

Все точки, в которых выполняется это условие, называют ста­ционарными. Но неравенство (2) не обязательно выполняет­ся в стационарной точке. Для его выполнения нужно, чтобы квад­ратичный член в (7) при любых ΔХ оставался отрицательным, т. е.

(ΔХ)tЮ(ΔХ)<0. (8)

Условие (8) есть достаточное условие максимума. Матрицу Ю, удовлетворяющую условию (8) при любых ΔХ, называют отрица­тельно - определенной матрицей, а в случае (АХ)'Ю(АХ)> 0 для любых ΔХ — положительно - определенной матрицей. Поэтому достаточные условия экст­ремума можно представить как требование отрицательной опреде­ленности матрицы Гессе для максимума или положительной опре­деленности для минимума в экстремальной точке.

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

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

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

где Λ = (λ1, λ2, ..., λp) — вектор неопределенных множителей Лагранжа;

ψ k(X) — k-е ограничение из группы ограничений-равенств; р — количество ограничений.

Значения функций Ф(Х, Λ) и F(X) при XХР совпадают, так как в области работоспособности ψ k(X) = 0. Тогда, если найдем mах Ф(Х, Λ) при XХР, то он будет одновременно , и условным максимумом функции F(X). Поэтому находим максимум Ф(Х, Λ), используя не­обходимые условия экстремума

(9)

(10)

и решая полученные уравнения (9) и (10). Из (10) видно, что ста­ционарная точка функции Ф(Х, Λ) будет принадлежать области ХР, а следовательно, она дает решение и исходной задачи условное! мак­симизации функции F(X).

Поисковая оптимизация. Об­ласть математики, исследующая вопросы теории и методы решения задач условной оптимизации, по­лучила название математического программиро­вания. Известны такие разделы математического программирова­ния, как линейное, выпуклое, ге­ометрическое и др., занимающи­еся исследованием частных случаев задач математического программи­рования. В процессе проектиро­вания технических объектов наиболее часто встречаются задачи математического программирования со следующей формулировкой: найти максимум (или минимум) целе­вой функции F(X) в области ХР, определяемой (6), где целевая функция и функции-ограничения являются нелинейными функциями управляемых параметров. Такую задачу обычно записывают в виде

(11)

Рисунок. Линии равного уровня функции с двумя максимумами.

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

Классические методы нахождения экстремумов целевых функций непосредственно в САПР практически не применяются, так как слу­чаи аналитического задания функций в задаче (11) крайне редки. Ха­рактерной ситуацией является наличие алгоритмических математи­ческих моделей. В связи с этим определение значений целевых функ­ций, функций-ограничений и их градиентов возможно только через численное решение систем уравнений, подсчет функционалов и вы­полнение других необходимых алгоритмов. В такой ситуации исполь­зуют поисковую оптимизацию, при которой поиск цели — экстремальной точки в пространств управляемых парамет­ров— осуществляется последовательными шагами, ведущими от ис­ходной точки Х0 через некоторые промежуточные отображающие точки Хк в заданную ε-окрестность точки экстремума X*.

При рассмотрении методов поисковой оптимизации полезны не­которые геометрические представления. Будем называть последо­вательность отображающих точек Xk, соединенных отрезками пря­мых, траекторией поиска. Геометрическое представление функций дается в виде поверхностей отклика (при раз­мерности пространства более двух имеем гиперповерхности отклика). В свою очередь, поверхности отклика на рисунках представляются в виде совокупности линий равного уровня. Линия равного уровня (при п> 2 — поверхность или гиперповерхность равного уровня) имеет уравнение F(X) = а и является геометрическим место точек в пространстве управляемых параметров, в которых значения целевой функции равны a.

Рисунок 2. Линии равного уровня одноэкстремальной функции

Рис. 6.3. Линии равного уровня функции с седловой точкой

Воспользуемся геометрическими представлениями для графической иллюстрации некоторых из введенных здесь понятий. Во всех случаях будем использовать двумерное пространство управляемы; параметров X = (x1, х2). На рис. 1 показаны линии равного уровня некоторой функции F(X) с двумя максимумами в точках А и Б (значения функции указаны на рисунке рядом с линиями равного уровня). Здесь точка А — точка глобального максимума, так как F(A) превы­шает значение F (Б).

На рис. 2 приведен пример одноэкстремальной функции

F(X) = — 1,1*x12— 1,5x22+2x1*x2 + x1+5, (12)

ее линии равного уровня на рисунке сплошные, точка Э — точка безусловного экстремума, Э = (1,15, 0,77).

Пусть имеется ограничение x1 + 1,5 x2 — 1 = 0, соответствующая ему линия показана на рис. 2 пунктиром. Очевидно, что точка условного экстремума Y здесь не совпадает с точкой безусловного экстремума Э.

На рис. 3 показаны линии равного уровня функции

F (X) = — 0,5*x12— 0,25x22 - x1*x2 - 3x1

Для этой функции в стационарной точке С = (1,— 2) выполняются необходимые, но не выполняются достаточные условия экстремума. Следовательно, С — седловая точка.

На рис..1 седловой точкой будет тонка В.

'Этапы вычислительного процесса при оптимизации. Перед началом поиска, выбирается некоторая исходная точка Х0 в пределах допустимой области ХД. Далее вычислительный процесс состоит из по­следовательности шагов. На каждом шаге сначала выбирается направление движения. Затем произво­дится сам шаг в пространстве управ­ляемых параметров, в результате из предыдущей точки Хk осуществляется переход в новую точку Хk+1. В этой точке вычисляется значение целевой функции F(Xk+1), благодаря чему мож­но судить о достигнутом успехе. Шаг заканчивается проверкой условий пре­кращения поиска: если условия вы­полнены, то поиск заканчивается, ина­че делается переход к новому шагу. Изложенная схема вычислений иллю­стрируется рис. 4.

Рис. 4. Схема вычислений при поисковой оптимизации.

Выше неоднократно отмечалось, что при алгоритмических математических моделях цена каждого варианта анали­за достаточно высока. В процессе же оптимизации приходится выполнять анализ многократно.

Обозначим через п1 и п2 количества вариантов анализа работы объекта на этапе вычисления целевой функции и на этапе определения направления поиска соответственно, а через n3 — количество шагов 'поиска. Пусть Тм1 — затраты машинного времени на один вариант анализа работы объекта. Тогда общее время решения задачи опти­мизации на ЭВМ

TK = TM1(n1 + n2)n3. (13)

Значения n1, п2 и п3 характеризуют эффективность принятой стра­тегии поиска с позиций затрат машинного времени, эти параметры обычно называют потерями на поиск и относят к основным критериям эффективности алгоритмов. Кроме потерь на поиск к пока­зателям эффективности относят точность определения экстремальной точки, надежность поиска, понимаемую как вероятность получения -решения задачи с заданной точностью. F

СПОСОБЫ ПОСТАНОВКИ ЗАДАЧ ПАРАМЕТРИЧЕСКОЙ ОПТИМИЗАЦИИ

Классификация критериев оптимальности.

Основная проблема по­становки экстремальных задач — формулировка целевой функции. Казалось бы, здесь не следует ожидать трудностей, так как коли­чественное выражение качества проектируемого объекта уже имеет­ся — это вектор выходных параметров Y. Однако все выходные пара­метры являются функциями вектора внутренних параметров X и, следовательно, не могут изменяться независимо друг от друга. Среди выходных параметров всегда можно найти пары таких параметров, что улучшение одного из них приводит к ухудшению другого. Такие параметры называют конфликтными параметрам и.

Поэтому при оптимизации невозможно улучшение всех выходных параметров одновременно.

Целевая функция должна быть одна и необходим переход от век тора Y(X) к скалярной функции качества F(X). Такой переход называют свертыванием векторного критерия.

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

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

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

При формулировке комплексных критериев возникает задача пре-, образования выходных параметров в некоторые безразмерные вели­чины, сравнимые между собой. Такое преобразование, иначе нормирование, означает, что устанавливаются отношения важности вы­ходных параметров. Количественно важность выходного параметра уj может оцениваться коэффициентом влияния уj на целевую функцию F(X). Для установления относительной важности выходных параметров в комплексных критериях инженер, должен располагать какими-либо ориентирами. В задачах проектирования наилучшим, а, часто и единственно корректным, является выбор относительной важности параметров с точки зрения степени выполнения ТЗ. Ориентация на ТЗ при формулировке комплексного критерия — один из важных принципов оптимизации в задачах проектирования. Иногда используют иные принципы, такие, как ориентация на мнение экс­пертов. Применение этого принципа может быть оправдано только в условиях отсутствия достаточно четко сформулированного и полного ТЗ, т. е. в случаях, когда собственно задача оптимизации объ­екта и задача формулировки ТЗ почему-либо решаются совместно. Если оптимизация ведется без учета статистического разброса параметров, то соответствующий критерий оптимальности называют детерминиpованным критерием, если разброс пара метров учитывается, то имеем критерий статистический.

Статистические критерии оптимальности более полно отражают пред­ставления о качестве объектов проектирования, однако их использо­вание, как правило, ведет к заметному увеличению затрат машинно­го времени. Поэтому чаще используют детерминированные критерии. Рассмотрим наиболее часто встречающиеся на практике способы постановки задач оптимизации. Частные критерии. В большинстве частных критериев в качестве целевой функции принимают один из выходных параметров yk(X), все остальные выходные параметры в виде соответствующих условий работоспособности относят к ограничениям. Тогда задача становится типичной задачей нелинейного программирования: max yk (X), где ХР — область, задаваемая прямыми ограничениями на управляе­мые параметры и условиями работоспособности, которые могут иметь вид неравенств уj< ТТj и равенств у j — ТТ j.

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

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

(14)

(15)

где уi и уТТi — i-e ординаты соответственно реальной и заданной характеристик; р — количество узловых точек.

Параметр yi можно рассматривать как i-й выходной параметр. И хотя в целевой функции F(X) учитывается несколько выходных параметров уi критерии (14) и (15) максимальной близости ре­зальной и заданной характеристик остаются частными, так как усло­вия работоспособности всех остальных выходных параметров должны быть отнесены к ограничениям задачи. Учет других параметров в F(X) не может быть сделан столь же просто, как ординат характеристики, из-за Неодинаковой природы этих параметров.

Мультипликативные критерии. Разделим выходные параметры объекта на три группы по типу соответствующих им условий работо­способности. К первой группе отнесем параметры у j+, имеющие условия работо­способности вида (16) у j+>TTj , т. е. параметры, для которых желательно максимальное увеличение. Вторую группу составят параметры уj- с условиями работоспособности вида

уj-<ТТi (17)

для них желательна минимизация.

Третья группа будет образована параметрами yk= с условиями ра­ботоспособности типа равенств

yk== TTk±Δyk, (18)

где Δyk — максимально допустимое по ТЗ отклонение yk= от ТТk. Мультипликативные критерии могут применяться в случаях, ког­да в ТЗ отсутствуют условия работоспособности типа равенства и вы­ходные параметры не могут принимать нулевые значения. Тогда целевая функция, подлежащая максимизации, имеет вид

(19)

где в числителе перемножаются все выходные параметры с условиями работоспособности типа (16), а в знаменателе фигурируют все пара­метры с условиями работоспособности типа (17).

studfiles.net

I этап. Условная оптимизация.

1-й шаг: k = 3.

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

Таблица 3.

0

1

2

3

4

5

0

0

0

0

1

2,8

2,8

1

2

5,4

5,4

2

3

6,4

6,4

3

4

6,6

6,6

4

5

6,9

6,9

5

2-й шаг: k = 2.

Определяем оптимальную стратегию при распределении денежных средств между вторым и третьим предприятиями. При этом рекуррентное соотношение Беллмана имеет вид:

на основе которого составлена таблица 4.

Таблица 4.

0

1

2

3

4

5

0

0+0

0

0

1

0+2,8

2+0

2,8

0

2

0+5,4

2+2,8

3,2+0

5,4

0

3

0+6,4

2+5,4

3,2+2,8

4,8+0

7,4

1

4

0+6,6

2+6,4

3,2+5,4

4,8+2,8

6,2+0

8,6

2

5

0+6,9

2+6,6

3,2+6,4

4,8+5,4

6.2+2,8

6,4+0

10,2

3

3-й шаг: k = 1.

Определяем оптимальную стратегию при распределении денежных средств между первым и двумя другими предприятиями, используя следующую формулу для расчета суммарного дохода:

на основе которого составлена таблица .

Таблица 5.

0

1

2

3

4

5

0

0+0

0

0

1

0+2,8

2,2+0

2,8

0

2

0+5,4

2,2+2,8

3+0

5,4

0

3

0+7,4

2+5,4

3+2,8

4,1+0

7,4

1

4

0+8,6

2,2+7,4

3+5,4

4,1+2,8

5,2+0

8,6

2

5

0+10,2

2,2+8,6

3+7,4

4,1+5,4

5,2+2,8

5,9

10,2

3

II этап. Безусловная оптимизация.

Определяем компоненты оптимальной стратегии.

1-й шаг. По данным из таблицы 5 максимальный доход при распределении 5 млн. руб. между тремя предприятиями составляет: . При этом первому предприятию нужно выделить млн. руб.

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

млн. руб.

По данным таблицы 4 находим, что оптимальный вариант распределения денежных средств размером 4 млн. руб. между вторым и третьим предприятиями составляет: при выделении второму предприятию млн. руб.

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

млн. руб.

По данным табл. 5.4.5. находим:млн. руб.

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

млн. руб.

studfiles.net

II этап. Безусловная оптимизация.

На этапе условной оптимизации получено, что минимальные затраты на перевозку груза из пункта 1 в пункт 10 составляют . Данный результат достигается при движении груза их пункта 1 в пункт 3. По данным таблицы 3, из пункта 3 необходимо двигаться в пункт 6, затем – в пункт 7 и из него – в конечный пункт. Таким образом, оптимальный маршрут доставки груза:(на рис. Он показан двойными стрелками).

Рис. 2. Транспортная сеть с оптимальным маршрутом.

7. Построение оптимальной последовательности операций в коммерческой деятельности

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

Из условия следует, что состояние экономической системы характеризуется двумя параметрами: количеством принятых и оформленных машин по разгрузке товара и количеством машин, отправленных с товаром в магазины. Поэтому решение будем искать на плоскости XOY, на ограниченном прямыми прямоугольнике, который является областью допустимых состояний системы. Если по оси Х отложить число (п) разгруженных машин, а по оси Y – число (m) загруженных товаром машин, то можно построить на плоскости граф состояния процесса, в котором каждая вершина характеризует состояние операции приема и отгрузки товара на оптовой базе. Ребра этого графа означают выполнение работ по приему или отправке товара на очередной машине. Каждому ребру можно сопоставить издержки, связанные с выполнением операции по разгрузке или загрузке машины.

Пример. Пусть п=6, m=4. Известны затраты по выполнению каждой операции, которые показаны на ребрах графа (рис. 1.).

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

Рис. 1. Графическая схема связи операций.

1 Этап. Условная оптимизация.

1-й шаг. k=1. На первом шаге, с задаваемым сечением A1, B1, из состояний A1 и B1 возможен только один вариант перехода в конечное состояние S1. Поэтому в вершинах A1 и B1 записываем соответственно издержки 8 и 11. Ребра A1S1 и B1S1 обозначаем стрелкой, направленной в вершину S1, как показано на рис. 2.

Рис. 2. Фрагмент связи операции шаг 1.

2-й шаг. k=2. Второй шаг оптимизации задается сечением по вершинам A2, B2, С1. Из состояний A2 и С1 возможен единственный переход в вершины A1 и B1 соответственно, поэтому в вершинах A2 и С1 записываем суммарные издержки 17 и 22 на первых двух шагах перехода в конечное состояние S1.

Из вершиныB2 возможны два варианта перехода: в вершину A1 или вершину B1. При переходе B2®A1 сумма издержек составляет 10+8=18, на переходе B2® B1 сумма составляет 13+11=24. Из двух вариантов суммарных издержек выбираем наименьшую (18) и обозначаем стрелкой условно оптимальный переход B2®A1, как показано на рис. 3.

Рис. 3. Сетевая модель операции шаг 2.

3-й шаг. k=3. На третьем шаге сечение проходит через вершины A3, B3, С2, D1. Из вершин A3 иD1 возможен единственный переход в вершины A2 и С1 соответственно. Суммарные издержки для состояния D1 равны 22+12=34. Из вершины B3 возможны два варианта перехода: в вершину A2 издержки равны 17+8=25; в вершину B2 - 18+9=27.

Рис. 4. Сетевая модель операции шаг 3.

Для вершины С2 возможен переход в вершину B2 (18+10=28) и в вершину С1 (22+12=34). Выбираем для вершин B3 и С2 наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход,как показано на рис. 4.

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

Рис. 5. Сетевая модель связи расходов операций

Минимально возможные суммарные издержки по обслуживанию всех 10 машин на оптовой базе составляют 88 у. е.

studfiles.net

Персональный сайт - 12

12. Общая характеристика линейных задач скалярной оптимизации

Задачи условной оптимизации.

Линейные задачи являются элементом более широкого класса задач – задач принятия решений при наличии ограничений, которые называются задачами условной оптимизации.

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

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

Свойства задач линейной оптимизации.

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

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

3. Целевая функция и ограничения имеют характер линейных зависимостей.

Общая задача линейного программирования.

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

  с-j, a-ij, b-i - заданные вещественные числа; k, l, m, n- целые числа.

Вектор , удовлетворяющий ограничениям задачи ЛП, называется допустимым решением (планом).

Допустимое решение , при котором целевая функция задачи ЛП принимает максимальное (минимальное)  значение, называется оптимальным решением (планом).

Задача линейного программирования в матричной форме.

 при следующих ограничениях: , X- вектор переменных размерности 1*n, C - вектор оценок задачи ЛП размерности 1*n, A - матрица размерности m*n, B- вектор ресурсов размерности m*1.

Типы задач линейного программирования.

1. A- множество типов изделий, выпускаемых на данном предприятии, c-i - прибыль от выпуска одного изделия, x-i - количество изделий i-го типа. Целевая функция выражается в векторной форме:.

2. A- множество типов изделий, B - множество технологий, c-i,j - прибыль от выпуска одного изделия i-го типа  по технологии (i принадлежит A) , j - количество изделий(j принадлежит B). Целевая функция выражается в матричной форме: .

3.  A - пункты отправления, B - пункты назначения, c-ij- цена доставки единицы продукции из i-го пункта отправления (принадлежит A) в j-й пункт назначения (принадлежит B), x-ij- количество единиц продукции. Целевая функция выражается в матричной форме: .

4.A- выполняемые работы, B- исполнители, c-ij - показатель эффективности выполнения  i-ой работы (прин. А)  j-м исполнителем (прин.B), x-ij- параметр назначения (x-ij=1 если на i-ю работу назначается j-й исполнитель, x-ij=0 в обратном случае). Целевая функция выражается в матричной форме:

Методы решения задач линейного программирования.

Тип задачи

Название задачи

Методы решения

1

Задачи общего вида

Универсальные методы

2

Задача распределенного общего вида

Универсальные методы

3

Транспортная задача

Универсальные (специальные) методы

4

Задача о назначениях

Универсальные (специальные) методы

 

Условия представления задач предметной области в виде задач линейного программирования.

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

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

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

tpr08.narod.ru


Prostoy-Site | Все права защищены © 2018 | Карта сайта