II. Нахождение оптимального плана и оптимального значения целевой функции

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

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

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

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

Обычно целевая функция задается в скалярном виде.

Используются следующие четыре формы целевой функции.

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

В этом случае целевая функция просто равна одному из внешних параметров или его обратной величине

Все остальные (m – 1) внешних параметров переводятся в систему ограничений.

Физический смысл целевой функции приведенных видов заключается в том, что чем больше (или меньше) параметр y i , тем лучше при прочих равных условиях данная система, причем равенство прочих условий понимается в смысле ограничений на остальные внешние параметры. Типичные задачи с приведенной формой целевой функции: оптимизация системы по надежности (y = P (t )), помехоустойчивости, стоимости и другим внешним параметрам. Такая целевая функция имеет ясный физический (технический или экономический) смысл, объективно характеризует систему и поэтому часто используется. То есть в этом случае целевой функцией является внешний параметр системы. Он и называется целевой функцией системы. Это могут быть: точность, быстродействие, время, стоимость, надежность, масса, габариты, какой-то технологический показатель и т.п.

2. Вторая форма целевой функции – это сумма параметров одной размерности или сумма функций от этих параметров

Такая форма характерна при оптимизации по экономическим критериям, по критериям сложности и т.п.

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

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

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

Первая целевая функция наиболее важная, последняя целевая функция наименее важная.

В частном случае целевая функция этого вида записывается так:

Пример ранжирования – это (например) такая последовательность целевых функций: точность, надежность, стоимость. Смысл целевой функции третьей формы состоит в следующем. Самым главным – первым по рангу – признается некоторый i -й параметр системы – y i (например, точность). Если у некоторой системы этот i -ый параметр больше, чем у всех других систем, то независимо от значений других параметров (если только они удовлетворяют ограничениям) данная система считается лучшей. Затем по второму параметру и т.д.

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

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

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

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

где F S (y i ) – одна из k целевых функций третьей формы;

ω S – ее весовой коэффициент.

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

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

Таким образом, можно указать, что в большинстве случаев (1-я и 3-я формы) показатели качества системы оцениваются численными значениями компонентов векторной целевой функции, которые носят названия функционалов :

- - - - - - - - - - - - - - - - - -

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

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

Например, вероятность обнаружения цели радиолокатором и т.п.

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

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

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

0,5x + y = 12

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

Построим прямую, отвечающую значению функции 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 тыс. руб.

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

Для нахождения максимума целевой функции используйте функцию maximize, формат которой следующий maximize(<функция>, <система ограничений>, <опции>);

При этом условие неотрицательности переменных удобно указать опцией NONNEGATIVE.

> optimum:=maximize(f,syst_ogr,NONNEGATIVE);

Используйте команду subs, которая позволяет подставить значения переменных x 1 и x 2 в функцию f .

> fmax:=subs(x1=83/17,x2=19/17,f);

Примените функцию evalf для представления ответа в форме действительного числа с 4 значащими цифрами.

> fmax:=evalf(fmax,4);

Ознакомиться с вариантом решения задачи ЛП без пояснений можно в приложении.

Решение оптимизационных задач в специализированном пакете SimplexWin. Http://www.Simplexwin.Narod.Ru/

Данная программа предназначена для решения задач линейного программирования симплекс методом.

Задача . Найти значения переменных x 1 и x 2 , при которых

при ограничениях

Порядок выполнения работы :

Запустите программу SimplexWin и установите требуемый размер матрицы ограничений, выбрав в меню команду Настройки – Размер матрицы (рис. 13).

Рис. 13 . Определение размера матрицы.

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

Рис.14 . Ввод данных.

II. Нахождение оптимального плана и оптимального значения целевой функции.

Рис. 15 . Форма Результаты.

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

Рис. 16 . Решение задачи.

Решение оптимизационных задач в Excel

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

Задача . Найти значения переменных x 1 и x 2 , при которых

при ограничениях

Порядок выполнения работы :

I. Оформление исходных данных.

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

Рис. 17 . Экранная форма задачи (курсор в ячейке D6).

Замечание : В экранной форме на рис. 17 каждой переменной и каждому коэффициенту задачи поставлена в соответствие конкретная ячейка в Excel. Так, например, переменным задачи соответствуют ячейки B3 (), C3 (),коэффициентам целевой функции соответствуют ячейки B6 (
), C6 (
), правым частям ограничений соответствуют ячейки F10 (
), F11 (
),F12 (
)и т.д.

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

Согласно условию задачи значение целевой функции определяется выражением
. Используя обозначения соответствующих ячеек вExcel, формулу для расчета целевой функции можно записать как сумму произведений каждой из ячеек, отведенных для значений переменных задачи (B3, C3), на соответствующие ячейки, отведенные для коэффициентов целевой функции (B6, C6).

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

– поставьте курсор в ячейку D6 ;

– вызовите окно Мастер функций – шаг 1 из 2 , нажав кнопку на стандартной панели инструментов;

– в окне Функция выберите функцию СУММПРОИЗВ ;

– в появившемся окне СУММПРОИЗВ в строку Массив 1 введите выражение B$3:C$3 , а в строку Массив 2 – выражение B6 :С6 ;

– нажмите кнопку OK .

Рис. 18 . Ввод формулы для расчета ЦФ в окне Мастер функций.

После ввода ячеек в строки Массив 1 и Массив 2 в окне СУММПРОИЗВ появятся числовые значения введенных массивов (рис. 18), а в экранной форме появится текущее значение, вычисленное по введенной формуле, то есть 0 (так как в момент ввода формулы значения переменных задачи нулевые) (рис. 19).

Замечание : Символ $ перед номером строки означает, что при копировании этой формулы в другие места листа Excel номер строки 3 не изменится. Символ : означает, что в формуле использованы все ячейки, расположенные между ячейками, указанными слева и справа от двоеточия.

Левые части ограничений задачи представляют собой сумму произведений каждой из ячеек, отведенных для значений переменных задачи (B3, C3), на соответствующую ячейку, отведенную для коэффициентов конкретного ограничения (B10, C10 – 1 ограничение; B11, C11 – 2 ограничение; B12, C12 – 3 ограничение).

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

Для расчета значений левых частей ограничений выполните следующее:

– поставьте курсор в ячейку D6 и скопируйте в буфер содержимое ячейки (клавишами Ctrl+C);

– поставьте курсор поочередно в поля левой части каждого из ограничений, то есть D 10 ,D 11 , D 12 , и вставляйте в эти поля содержимое буфера (клавишами Ctrl+V) (при этом номер ячеек во втором массиве формулы будет меняться на номер той строки, в которую была произведена вставка из буфера).

После ввода на экране в полях D 10 ,D 11 , D 12 появится 0 (нулевое значение) (рис. 19).

Рис. 19 . Экранная форма задачи после вода

всех необходимых формул.

Проверьте правильность введения формул.

Для этого:

– произведите поочередно двойное нажатие левой клавиши мыши на ячейки с формулами, при этом на экране рамкой будут выделяться ячейки, используемые в формуле (рис. 20 и рис. 21).

Рис. 20

формулы в целевую ячейку D6.

Рис. 20 . Проверка правильности введения

формулы в ячейку D10 для левой части ограничений.

Задайте целевую функцию и введите ограничения в окне Поиск решения (рис. 21).

Для этого:

– поставьте курсор в ячейку D6 ;

– вызовите окно Поиск решения , выбрав на панели инструментов Данные – Поиск решения ;

– поставьте курсор в поле Установить целевую ячейку ;

– введите адрес целевой ячейки $D$6 или сделайте одно нажатие левой клавишей мыши на целевую ячейку в экранной форме, что будет равносильно вводу адреса с клавиатуры;

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

– в окне Поиск решений в поле Изменяя ячейки введите ячейки со значениями переменных $B$3:$C$3 , выделив их в экранной форме, удерживая левую кнопку мыши;

Рис. 21 . Окно Поиск решения.

– нажмите кнопку Добавить ;

– в соответствии с условием задачи выберите в поле знака необходимый знак, например, для 1 ограничения это знак ;

– в поле Ограничение введите адрес ячейки правой части, рассматриваемого ограничения, например $F$10 ;

– аналогичным образом установите соотношения между правыми и левыми частями других ограничений ($D$ 11$F$1 1 , $D$ 12$F$1 2) ;

– подтвердите ввод всех перечисленных условий нажатием кнопки OK (рис. 22 и рис. 23).

Рис. 22 . Добавления условия.

Замечание : Если при вводе условия задачи возникает необходимость в изменении или удалении внесенных ограничений, то это можно сделать на жав на кнопки Изменить или Удалить .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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