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) при любых ΔХ оставался отрицательным, т. е.
Условие (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.
Рис. 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
