где - постоянные затраты, которые не зависят от режима обработки, мин;

Здесь - подготовительно – заключительное время на операцию, мин;

Размер партии обрабатываемых деталей;

Вспомогательное время операции, мин;

Время на обслуживание без учета времени на замену инструмента, мин;

Время на отдых рабочего, мин;

Затраты времени, связанные с заменой затупившегося инструмента и соответствующей поднастройкой технологической системы;

где - время на замену инструмента и соответствующую размерную настройку;

Диаметр и длина обрабатываемого вала;

Коэффициент для расчета скорости резания;

Скорость резания;

Глубина резания;

Здесь - показатели степени в формулах для расчета режимов резания.

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

Целевая функция стоимости на примере обработки вала имеет вид:

Здесь - расходы на материал;

Расходы в единицу времени соответственно на эксплуатацию оборудования, приспособления, по зарплате с учетом накладных расходов;

Время на замену инструмента и соответствующую размерную настройку;

Стоимость инструмента за период его эксплуатации.

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

Объемное планирование работы технологических станочных систем

Эта и все последующие лекции посвящены вопросам математического моделирования и оптимизации технологических станочных систем.

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

Постановка задачи . Имеется m – станков (m – групп станков), на которых могут быть изготовлены n – типов деталей. Трудоемкость обработки j - ой детали на i – м станке составляет , час. Известны фонды времени работы каждого станка (группы станков) – B i . Исходные данные для решения задачи представлены в таблице 14.1.

Таблица 14.1. Исходные данные для решения задачи, представленные в общем виде

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

Математическая модель для решения задачи запишется:

Ограничения :

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

Пример. Исходные данные для примера приведены в таблице 14.2.

Таблица 14.2. Исходные данные для решения задачи

Обозначим через количество деталей типа D 1 , через количество деталей типа D 2 .

Математическая модель для решения данной задачи запишется следующим образом:

Ограничения (по фонду времени работы оборудования):

Требуется найти значения и , удовлетворяющие заданным ограничениям (14.6) – (14.10) и обеспечивающие максимум целевой функции (14.11). Параметры и являются управляемыми параметрами в математической модели.

Решим задачу графо – аналитическим методом (см. лекцию 6). Графическая иллюстрация решения задачи приведена на рис. 14.1.

Рис.14.1. Графическая иллюстрация решения задачи

Вычисления для построения ограничений (14.6) – (14.8):

x 1
x 2

x 1
x 2

Проведя прямую линию, параллельную данной, находим точку касания ее границы ОДР – это точка А. Для нахождения ее координат (точки пересечения ограничений 14.7 и 14.8) решаем следующую систему уравнений:

Т.е. окончательно

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

Задача о минимальной загрузке оборудования

Эта и последующие задачи в данной лекции приводятся на уровне постановки задачи и формирования математической модели для ее решения. Все они решаются методами линейного программирования.

Имеется m станков, на которых могут быть изготовлены n типов деталей. Производительность i - го станка при изготовлении детали j - го типа составляет C ij . Величины плановых заданий A j на изготовление j - ой детали и ресурс времени B i работы i - го станка приведены в таблице 14.3.

Таблица 14.3 Исходные данные для решения задачи

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

Пусть t ij - время изготовления j - ой детали i - м станком. Составим ограничения по ресурсу времени для каждого станка:

Решение поставленной задачи состоит в минимизации линейной целевой функции (суммарного времени)

(14.14)

при ограничениях (14.12), (14.13) и условии, что все переменные .

Задача об оптимальном распределении деталей по станкам

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

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

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

(14.17)

при ограничениях (14.15), (14,16) с дополнительным условием, что все переменные .

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

Задача о производстве продукции при ограниченных запасах сырья

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

Таблица 14.4 Исходные данные для решения задачи

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

Ограничения по запасам сырья имеют вид:

(14.18)

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

при ограничениях (14.18) и дополнительных условиях .

Основы теории массового обслуживания

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

Детерминированная математическая модель отражает поведение объекта (системы, процесса) с позиций полной определенности в настоящем и будущем.

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

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

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

Понятие случайного процесса

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

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

Примеры: 1. Система S – технологическая система (участок станков). Станки время от времени выходят из строя и ремонтируются. Процесс, протекающий в этой системе, случаен.

2. Система S – самолет, совершающий рейс на заданной высоте по определенному маршруту. Возмущающие факторы – метеоусловия, ошибки экипажа и т.д., последствия – «болтанка», нарушение графика полетов и т.д.

Марковский случайный процесс

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

Пусть в настоящий момент t 0 система находится в определенном состоянии S 0 . Мы знаем характеристики состояния системы в настоящем и все, что было при t < t 0 (предысторию процесса). Можем ли мы предугадать (предсказать) будущее, т.е. что будет при t > t 0 ? В точности – нет, но какие-то вероятностные характеристики процесса в будущем найти можно. Например, вероятность того, что через некоторое время система S окажется в состоянии S 1 или останется в состоянии S 0 и т.д.

Пример . Система S – группа самолетов, участвующих в воздушном бою. Пусть x – количество «красных» самолетов, y – количество «синих» самолетов. К моменту времени t 0 количество сохранившихся (не сбитых) самолетов соответственно – x 0 , y 0 . Нас интересует вероятность того, что в момент времени численный перевес будет на стороне «красных». Эта вероятность зависит от того, в каком состоянии находилась система в момент времени t 0 , а не от того, когда и в какой последовательности погибали сбитые до момента t 0 самолеты.

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

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

Процесс называется процессом с дискретным состоянием , если его возможные состояния S 1 , S 2 , … можно заранее определить, и переход системы из состояния в состояние происходит «скачком», практически мгновенно.

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

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

S 0 - оба станка исправны;

S 1 - первый станок ремонтируется, второй исправен;

S 2 - второй станок ремонтируется, первый исправен;

S 3 - оба станка ремонтируются.

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

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

Рис.15.1. Граф состояний системы

состояние. Для нашего примера граф состояний приведен на рис.15.1.

Примечание. Переход из состояния S 0 в S 3 на рисунке не обозначен, т.к. предполагается, что станки выходят из строя независимо друг от друга. Вероятностью одновременного выхода из строя обоих станков мы пренебрегаем.

Потоки событий

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

В предыдущем примере – это поток отказов и поток восстановлений. Другие примеры: поток вызовов на телефонной станции, поток покупателей в магазине и т.д.

Поток событий можно наглядно изобразить рядом точек на оси времени O t – рис. 15.2.

Рис.15.2. Изображение потока событий на оси времени

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

Интенсивность потока событий () – это среднее число событий, приходящееся на единицу времени.

Рассмотрим некоторые свойства (виды) потоков событий.

Поток событий называется стационарным , если его вероятностные характеристики не зависят от времени.

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

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

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

Поток событий называется простейшим (или стационарным пуассоновским), если он обладает сразу тремя свойствами: 1) стационарен, 2) ординарен, 3) не имеет последствий.

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

Для простейшего потока с интенсивностью интервал T между соседними событиями имеет так называемое показательное (экспоненциальное) распределение с плотностью

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

Х1,Х2,Х3,…Хп.

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

Целевая функция. Это - выражение, значение которого инженер стремиться сделать максимальным или минимальным. Целевая функция позволяет количественно сравнить два альтернативных решения. С математической точки зрения целевая функция описывает некоторую (п+1) - мерную поверхность. Ее значение определяется проектными параметрами

М = М (х1,х2,…,хп).

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

Рисунок 1. Одномерная целевая функция.

Рисунок 2. Двумерная целевая функция.

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

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

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

Рисунок 3. При изменении знака целевой функции на противоположный в задаче на минимум, превращает ее в задачу на максимум.

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

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

С1 (X1, X2, Х3, . . ., Хп) = 0,

С2 (X1, X2, Х3, . . ., Х п) = 0,

..……………………………..

Сj(X1, X2, Х 3, . . ., Хп) = 0.

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

z1 ?r1(X1, X2, Х3, . . ., Хп) ?Z1

z2 ?r2(X1, X2, Х3, . . ., Хп) ?Z2

………………………………………

zk ?rk(X1, X2, Х3, . . ., Хп) ?Zk

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

Прямые и функциональные ограничения. Прямые ограничения имеют вид

xнi ? xi ? xвi при i ? ,

где xнi , xвi - минимально и максимально допустимые значения i-го управляемого параметра; п - размерность пространства управляемых параметров. Например для многих объектов параметры элементов не могут быть отрицательными: xнi ? 0 (геометрические размеры, электрические сопротивления, массы и т.п.).

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

• 1) типа равенств
• ш (Х) = 0; (2.1)
• 2) типа неравенств

ц (Х) › 0, (2.2)

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

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

ХД = {Х | ш(Х) = 0, ц (Х)›0, xi › xнi ,

xi ‹ xвi при i ? }.

Если ограничения (2.1) и (2.2) совпадают с условиями работоспособности, то допустимую область называют также областью работоспособности ХР.

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

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

Рисунок 4. Произвольная целевая функция может иметь несколько локальных оптимумов.

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

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

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

yi < TTi , i О ; yi > TTj , j О ;

yr = TTr ± ?yr; r О .

где yi, yj, yr - множество выходных параметров;

TTi, TTj, TTr - требуемые количественные значения соответствующих выходных параметров по техническому заданию;

Yr - допустимое отклонение r-го выходного параметра от указанного в техническом задании значения TTr.

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

Частные критерии могут применяться в случаях, когда среди выходных параметров можно выделить один основной параметр yi(Х), наиболее полно отражающий эффективность проектируемого объекта. Этот параметр принимают за целевую функцию. Примерами таких параметров являются: для энергетического объекта - мощность, для технологического автомата - производительность, для транспортного средства - грузоподъемность. Для многих технических объектов таким параметром служит стоимость. Условия работоспособности всех остальных выходных параметров объекта относят при этом к функциональным ограничениям. Оптимизация на основе такой постановки называется оптимизацией по частному критерию.

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

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

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

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

определяет среднеквадратичное приближение yj(X) к заданным техническим требованиям TTj.

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

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

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

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

где р -- количество узловых точек щj на оси переменной щ; aj - весовые коэффициенты, значения которых тем больше, чем меньшее отклонение y(Х, щj) - yTT(Х, щj) нужно получить в j-и точке.

Максиминные (минимаксные) критерии позволяют достичь одной из целей оптимального проектирования - наилучшего удовлетворения условий работоспособности.

Введем количественную оценку степени выполнения j-го условия работоспособности, обозначим ее через zj и будем называть запасом работоспособности параметра yj. Расчет запаса по j-му выходному параметру можно выполнить различными способами, например,

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

Здесь предполагается, что все соотношения сведены к виду yi < TТj. Если yi > TТj , то -yj < -TТj . Следует принимать аj >1 (рекомендуемые значения 5 ? аj ? 20), если желательно достичь выполнения j-го технического требования с заданным допуском, т. е. yj = TТj ± ?yj; aj=l, если необходимо получить максимально возможную оценку zj.

Качество функционирования технической системы характеризуется вектором выходных параметров и, следовательно, вектором Z=(zm,zm,…,zm). Поэтому целевую функцию следует формировать как некоторую функцию ц(Z) вектора оценок. Например, если в качестве целевой функции рассматривается запас только того выходного параметра, который в данной точке X является наихудшим с позиций выполнения требований ТЗ, то

где m - количество запасов работоспособности.

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

где ХД - допустимая для поиска область.

Критерий оптимизации с целевой функцией (2.6) называют максиминным критерием.

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

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

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

где оi - коэффициент, численно равный единице параметра ui .

Нормирование выходных параметров можно выполнить с помощью весовых коэффициентов, как в аддитивом критерии, или переходом от уj к запасам работоспособности zj по (2.5).

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

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

Целевая функция позволяет ответить на несколько вопросов:

Выгодно или нет то или иное событие;

В правильном ли направлении идет движение;

Насколько верно сделан выбор и т.д.

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

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

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

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

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

Существует такое понятие, как неполная оптимизация. Она может образоваться по нескольким причинам. Например:

Число попавших в максимальную точку систем ограничено (уже установлена монополия или олигополия);

Нет монополии, но отсутствуют ресурсы (недостаток квалификации на каком-либо конкурсе);

Отсутствие самой а точнее «незнание» ее (мужчина мечтает о некой красивой женщине, но неизвестно, существует ли такая в природе) и т.д.

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

Линейное программирование.

Краткие теоретические сведения

Постановка задач

Решение прямой задачи линейного программирования отвечает на следующий вопрос:

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

Решение двойственной к ней задачи отвечает на следующий вопрос:

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

Прямая задача линейного программирования может быть связана со следующей ситуацией. Имеются n способов получения прибыли (оказание n видов услуг) с объёмами x i (число штук i -й оказанных услуг) . При этом используются m видов ресурсов, запас j -го изкоторых равен b j . При этом расход каждого ресурса j и величина прибыли в каждом из процессов i линейно зависят от количества оказанных услуг i -го вида с коэффициентами a ji и c i , соответственно. Матрица А =(a ji ) m ´ n по смыслу аналогична такой же из первой части и также называется матрицей технологических, или структурных коэффициентов. Тогда оптимальный по критерию максимума получения прибыли план может быть получен из решения следующей прямой задачи линейного программирования:

Этой задаче можно поставить в соответствие расширенную матрицу следующего вида:

(4.1)

Двойственная к задаче (4) задача имеет следующий вид (z j – искомые предельные цены):

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

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

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

Целевая функция L(x) – математическое выражение, связывающее факторы (параметры) модели. Экономический смысл целевой функции отражает критерий оптимальности – показатель, имеющий экономическое содержание и служащий формализацией конкретной цели управления, например: максимизация прибыли (строка 1 в (4)), максимизация качества продукции или минимизация издержек (5.1).

Система ограничений модели – пределы, ограничивающие область допустимых (приемлемых, осуществимых) решений , фиксирующие основные внутренние и внешние свойства объекта, связанные с целью оптимизации. Уравнения связи (типа f j (x) )– математическая формализация системы ограничений (строки 2 и 3 в (4), (5.2 , 5.3)). Система ограничений отражает экономический смысл уравнений связи.

Система, состоящая из целевой функции и уравнений связи, -задача экономико- математического моделирования (ЭММ). В случае, когда целевая функция и уравнения связи линейны, а переменные управления меняются непрерывно, задача ЭММ называетсязадачей линейного программирования (ЛП) . Основное свойство множества допустимых планов (МДП) задачи ЛП - оно является выпуклым многогранником. Выпуклым называется множество, которому принадлежат все отрезки, соединяющие любые две точки этого множества. Если задача ЛП имеет решение, то оно находится в вершине МДП. Планы, находящиеся в вершинах МДП, называются базовыми. Задачи линейного программирования делятся на задачи с ограничениями в форме неравенств (общая задача ЛП) и в форме равенств (каноническая задача ЛП). При математической формализации экономических задач с помощью линейной модели получаются общие задачи ЛП – например, (4), (5). Любой общей задаче путём введения дополнительных переменных может быть сопоставлена каноническая задача. Так, задаче (4) путём введения в каждое неравенство типа “расход ресурса £ запас ресурса” (строка 2 в (4)) дополнительной переменной x n+j (неизрасходованный остаток j -го ресурса) сопоставляется следующая каноническая:

При этом размерность задачи (6) – число переменных плана - по сравнению с (4) увеличилась с n до n+m .

При решении задачи (4) важное значение имеют коэффициенты ресурсоотдачи, среди которых здесь будут использованы дифференциальные и приростные. Дифференциальный коэффициент ресурсоотдачи k ji показывает стоимость оказанных при использовании единицы j -го ресурса i –ых услуг. Те виды услуг, для которых все k ji оказываются наименьшими по всем видам услуг, являются наименее выгодными. Они не должны присутствовать в оптимальном плане. Это позволяет, путём принудительного обнуления объёмов оказания таких услуг снизить размерность задачи и, таким образом, упростить её решение. Вычисляются они следующим образом - k ji =c i /a ji .

приростной коэффициент ресурсоотдачи К j – это коэффициент пропорциональности между приращением значения целевой функции оптимального плана и вызвавшим это приращение изменением запасов j -го ресурса. Можно считать, что К j показывают, на сколько увеличится значение целевой функции исходной задачи в оптимальном плане при увеличении величины запаса j -го ресурса на единицу. С математической точки зрения является полной производной от оптимального значения целевой функции по величине запаса j -го ресурса: К j =dL opt /db j .

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

В силу этих определений задача ЛП может быть сформулирована следующим образом: среди всех точек выпуклой области, являющейся решением системы ограничений, выбрать такую, координаты которой минимизируют (максимизируют) линейную функцию F = с 1 x + с 2 y .
Заметим, что переменные x , y в ЗЛП принимают, как правило, неотрицательные значения (x ≥ 0, y ≥ 0), поэтому область расположена в I четверти координатной плоскости.

Рассмотрим линейную функцию F = с 1 x + с 2 y и зафиксируем какое-нибудь ее значение F . Пусть, к примеру, F = 0, т.е. с 1 x + с 2 y = 0. Графиком этого уравнения будет прямая, проходящая через начало координат (0;0) (рис.).
Рисунок
При изменении этого фиксированного значения F = d , прямая с 1 x + с 2 y = d будет смещаться параллельно и «зачертит» всю плоскость. Пусть D – многоугольник – область решения системы ограничений. При изменении d прямая с 1 x + с 2 y = d , при некотором значении d = d 1 достигнет многоугольника D , назовем эту точку А «точкой входа», и затем, пройдя многоугольник, при некотором значении d = d 2 будем иметь с ним последнюю общую точку В , назовем В «точкой выхода».
Очевидно, что своего наименьшего и наибольшего значения целевая функция F =с 1 x + с 2 y достигнет в точках «входа» А и «выхода» В .
Учитывая, что оптимальное значение на множестве допустимых решений целевая функция принимает в вершинах области D , можно предложить следующий план решения ЗЛП:

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

Заметим, что вектор (с 1 , с 2), перпендикулярный прямой, показывает направление роста целевой функции.

При графическом решении ЗЛП возможны два случая, которые требуют особого обсуждения.

Случай 1
Рисунок 6
При перемещении прямой с 1 x + с 2 y = d «вход» или «выход» (как на рисунке) произойдет по стороне многоугольника. Это случится, если в многоугольнике есть стороны, параллельные прямой с 1 х + с 2 у = d .
В этом случае точек «выхода» (« входа») бесчисленное множество, а именно – любая точка отрезка АВ . Это означает, что целевая функция принимает максимальное(минимальное) значение не в одной точке, а во всех точках, лежащих на соответствующей стороне многоугольника D .

Случай 2
Рассмотрим случай, когда область допустимых значений неограниченна.
В случае неограниченной области целевая функция может быть задана таким образом, что соответствующая ей прямая не имеет точки «выхода» (или «входа»). Тогда максимальное значение функции (минимальное) не достигается никогда – говорят, что функция не ограничена.
Рисунок
Необходимо найти максимальное значение целевой функции F = 4x + 6y → max , при системе ограничений
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами.
x + y = 18

x	12	9
y	6	9

0,5x + y = 12

x	12	18
y	6	3

x = 12 – параллельна оси OY ;
y = 9 – параллельна оси OX ;
x = 0 – ось OY ;
y = 0 – ось OX ;
x ≥ 0 – полуплоскость правее оси OY ;
y ≥ 0 – полуплоскость выше оси OX ;
y ≤ 9 – полуплоскость ниже y = 9;
x ≤ 12 – полуплоскость левее x = 12;
0,5x + y ≤ 12 – полуплоскость ниже прямой 0,5x + y = 12;
x + y ≤ 18 – полуплоскость ниже прямой x + y = 18.
Рисунок
Пересечением всех этих полуплоскостей является очевидно, пятиугольник ОАВСД , с вершинами в точках О (0; 0), А (0; 9), В (6; 9), С (12; 6), Д (12; 0). Этот пятиугольник и образует область допустимых решений задачи.

Рассмотрим целевую функцию задачи F = 4x + 6y → max.

x	3	0
y	–2	0

Построим прямую, отвечающую значению функции F = 0: 4x + 6y = 0. Будем двигать эту прямую параллельным образом. Из всего семейства прямых 4x + 6y = const последней вершиной, через которую пройдет прямая при выходе за границу многоугольника, будет вершина С (12; 6). Именно в ней F = 4x + 6y достигнет своего максимального значения.
Значит, при x = 12, y = 6 функция F достигает своего максимального значения F = 4 ∙ 12 + 6 ∙ 6 = 84, равного 84. Точка с координатами (12; 6) удовлетворяет всем неравенствам системы ограничений, и в ней значение целевой функции оптимально F * = 84 (оптимальное значение будем обозначать «*»).
Задача решена. Итак, необходимо выпустить 12 изделий I вида и 6 изделий II вида, при этом прибыль составит 84 тыс. руб.

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