Оптимизация

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

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

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

Математическая  постановка (модель) задачи математического программирования (МП) выглядит следующим образом:

необходимо определить значения вектора переменных x = (x₁,x₂,…, x_n), которые удовлетворяют ограничениям вида

g _i (x₁,x₂,…, x_n)

 b_i    , для всех i = 1,…, m

и доставляют максимум или минимум целевой функции

f (x₁,x₂,…, x_n) → max (min).  

Решением (планом, вектором управления) задачи МП называется всякий вектор х из пространства Eⁿ (Eⁿ- n-мерное векторное пространство), в геометрической интерпретации – это точка векторного n-мерного пространства. Допустимым решением (планом)  задачи МП называется такое решение задачи, которое удовлетворяет ее ограничениям g _i (x₁,x₂,…, x_n)  b_i    , для всех i = 1,…, m. 

Совокупность  допустимых решений задачи называют областью допустимых решений (ОДР) задачи МП, которую, как правило, обозначают как D. Оптимальным решением х* называется такое допустимое решение, при котором целевая функция достигает своего оптимального (в нашем случае — максимального) значения, т. е. решение, удовлетворяющее условию max f(x) = f(x*). Величина f* = f(x*) называется оптимальным значением целевой функции.

Окончательным решением задачи является пара (х*, f*), состоящая из оптимального решения и оптимального значения целевой функции/            

 Если хотя  бы одна из функций g _i (x₁,x₂,…,  x_n) или f (x₁,x₂,…, x_n) нелинейная, то такая задача МП называется задачей нелинейного программирования.           

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

В общем виде задача линейного программирования (ЗЛП) может быть сформулирована как задача нахождения вектора x = (х₁, х₂, …, х_n) Eⁿ такого, что функция линейного вида z(x)=c₁x₁+ c₂x₂+ c₃x₃+ … + c_nx_n→max (или min), т.е. достигает своего максимального или минимального значения, при этом вектор x = (х₁, х₂, …, х_n) должен удовлетворять системе линейных неравенств:  

                (1.1)  

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

                        (1.2)  

Линейные неравенства  в модели ЛП  вида   

  

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

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

Дополнительно следует заметить, что в математическом смысле задача поиска максимума функции эквивалентна задаче поиска минимума.

   Þ    .

Например, точка  максимума функции f(x) = x²  очевидно равна точке минимума функции  f'(x) = -x².

Модель задачи  ЛП (1.2) можно представить в матричной форме:   

       (1.3)  

где c,x,b – векторы-столбцы из пространства Eⁿ, А-матрица коэффициентов условий {a_ij} размерности m´n.   

, , ,   

Задачу линейного  программирования, записанную в форме (1.2-1.3), называют общей задачей линейного программирования^[1].

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

Следует отметить, что оптимальное значение целевой  функции z* = z(x*) является лишь характеристикой оптимального решения x*.  Зная оптимальное решение x* всегда можно рассчитать оптимальное значение z(x*), но по оптимальному значению функции найти оптимальное решение x* не всегда возможно (если известен способ, как достичь максимальную прибыль, значение прибыли рассчитать можно, но, если известна только потенциально достижимая прибыль, способ ее достижения отнюдь не очевиден).

1.2. Схема построения  оптимизационных  моделей  

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

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

1) Что является  искомыми величинами задачи? Как лучше обозначить эти величины?

2) Какова цель  решения? Что в задаче служит критерием эффективности (оптимальности) решения, например, прибыль, себестоимость, время и т.д. В каком направлении должно изменяться значение этого критерия (к max или к min) для достижения наилучших результатов?

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

Только после  ответа на все эти вопросы можно  приступать к записи математической модели.

В общем виде схема построения математической модели состоит из следующих этапов.

Этап 1. Выбор и обозначение переменных задачи.

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

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

Искомые величины являются переменными задачи, которые, как правило, обозначаются малыми латинскими буквами с индексами, например, однотипные переменные удобно представлять в виде x = (x₁, x₂, ... ,x_n). При этом переменные могут иметь и более чем один индекс, например, x_ij или x_ikl.

Этап 2. Представление целевой функции задачи.

Цель решения  записывается в виде ЦФ, обозначаемой, например, z. Математическая формула  ЦФ z отражает способ расчета значений критерия эффективности задачи.

Этап 3. Представление ограничений задачи.

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

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

1.3. Задачи к практикуму  

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

Задача 1.1. О производстве красок.

Фабрика производит два вида красок: первый - для наружных, а второй - для внутренних работ. Для производства красок используются два ингредиента: А и В. Максимально возможные суточные запасы этих ингредиентов составляют 6 и 8 тонны соответственно. Известны расходы ингредиентов А и В на производство 1 т соответствующих красок (табл. 1.1). Изучение рынка сбыта показало, что спрос на краску второго вида никогда не превышает 2 тонн в сутки. Оптовые цены одной тонны красок равны: 3 тыс. руб. за тонну краски первого вида; 2 тыс. руб. за тонну краски второго вида.

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

Таблица 1.1 Исходные данные к задаче о производстве красок

Ингредиенты	Расход  ингредиентов, т ингредиента/т  краски		Запас, тонн ингр./ сутки
	Краска  первого вида	Краска второго  вида
А	1	2	6
В	2	1	8

 

 

Решение

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

1. Переменные  задачи.

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