Целевая функция. Большая энциклопедия нефти и газа

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

Х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).

Целевая функция. Если доход от реализации одного стола равен С 1 рублей, то от реализации столов в объеме х 1 штук месячный доход

составит С 1 х 1 рублей. Аналогично месячный доход от реализации шкафов составит С 2 х 2 рублей. Обозначив общий доход (в руб.) через Z , можно дать следующую математическую формулировку целевой функции: определить (допустимые) значения х 1 , и х 2 , максимизирующие величину общего дохода Z = С 1 х 1 + С 2 х 2 =

2

∑

j=1

C j x j .

Ограничения. При решении рассматриваемой задачи должны быть учтены ограничения на расход ресурсов. Пиломатериал идет на изготовление и столов и шкафов. На один стол идет а 11 (м 3) пиломатериала, тогда на столы в количестве x 1 штук потребуется а 11 x 1 (м 3) пиломатериала. На изготовление шкафов в количестве х 2 штук потребуется а 12 х 2 (м 3) пиломатериала. Всего пиломатериала потребуется а 11 х 1 + а 12 x 2 (м 3). Расход его не должен превышать величины b 1 (м 3). Тогда ограничение на пиломатериал запишем в виде неравенства

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

х 1 ≥ 0, х 2 ≥ 0,

где х 1 , х 2 - целые числа.

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

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

Для определения переменных рассмотренной модели могут использоваться методы линейного программирования. Базовым методом ЛП является симплекс-метод, разработанный Г. Данцигом . Задачу ЛП можно решить и графически. Графическое представление решения задачи поможет понять и идею симплекс-метода. Конкретизируем задачу, представив исходные данные в табл. 3.1 (данные приводятся условные).

Таблица 3.1

Ресурсы	Расход ресурсов на единицу продукции		Запас ресурсов
	Стол	Шкаф
Пиломатериалы (м 3)	0,06	0,07	42
Шурупы (кг)	0,04	0,085	34
Краска (кг)	0,035	0,12	42
Цена единицы продукции (руб.)	500	750	-

Запишем модель задачи с приведенными данными:

В дальнейшем ограничение (3.5) учитывать не будем, а решение задачи получим округлением найденных переменных задачи (3.0-3.4).

44 :: 45 :: 46 :: 47 :: Содержание

47 :: 48 :: 49 :: 50 :: 51 :: Содержание

3.2.2. Графический способ решения ЗЛП

Для определения решения ЗЛП с двумя переменными выполним следующие действия.

1. Построим множество допустимых решений Ω задачи. Данное множество Ω образуется в результате пересечения полуплоскостей (ограничений) (3.1-3.4). На рис. 3.2 множество допустимых решений показано в виде пятиугольника. Области, в которых выполняются соответствующие ограничения в виде неравенств, указываются стрелками, направленными в сторону допустимых значений переменных. Полученный многогранник Ω называют симплексом. Отсюда и название метода поиска оптимального решения.

2. Построим вектор-градиент С, составленный из производных целевой функции по переменным задачи, который указывает направление возрастания целевой функции по этим переменным. С = (С 1 , С 2) = (500,750). Начало этого вектора лежит в точке с координатами (0, 0), а конец - в точке (500, 750). Ряд параллельных штриховых линий, перпендикулярных вектору-градиенту, образует множество целевых

Функций при произвольно выбранных значениях Z . При Z = 0 прямая (целевая функция) проходит через точку (0, 0), а целевая функция Z принимает минимальное значение.

Рис. 3 2 Геометрическая интерпретация ЗЛП

3. Переместим прямую, характеризующую доход Z , в направлении вектор-градиента (для задачи max Z ) до тех пор, пока она не сместится в область недопустимых решений. На рис. 3.2 видно, что оптимальному решению соответствует точка X* = (х 1 *, х 2 *). Так как точка X* является точкой пересечения прямых (3.1) и (3.2), значения х 1 * и х 2 * определяются решением системы двух уравнений:

Решение указанной системы уравнений дает результат х 1 * = 517,4 и х 2 * =156,5. Полученное решение означает, что месячный объем производства столов должен составить 517 шт., а шкафов - 156 шт. Доход, полученный в этом случае, составит:

Z = 517 · 500 + 156 · 750 = 375500 рублей

ЗЛП со многими переменными можно решить графически, если в ее канонической записи число неизвестных n и число линейно независимых уравнений m связано соотношением n-m ≤ 2. Запишем каноническую форму ЗЛП, рассмотренную выше. Для этого введем новые переменные x 3 , x 4 и x 5 .

Для данной ЗЛП число переменных n = 5, а число линейно-независимых уравнений m = 3. Эта и другие ЗЛП в канонической форме могут быть решены графически, если n-m ≤ 2.

Выберем любые m неизвестные и выразим каждую из них через оставшиеся (n-m ) переменные. В нашем случае удобно взять переменные x 3 , x 4 и x 5 и выразить их через x 1 и x 2 .

Учитывая неотрицательность всех переменных, в том числе х 3 ≥ 0, х 4 ≥ 0 и х 5 ≥ 0, а также зависимость последних от двух переменных x 1 и х 2 , можно графически показать решение расширенной задачи с проекцией на переменные x 1 и х 2 . Полуплоскость х 3 ≥ 0 (см. рис. 3.2) совпадает с ограничением (3.1), полуплоскость х 4 ≥ 0 - с ограничением (3.2), а полуплоскость х 5 ≥ 0 - с ограничением (3.3). Точка оптимума в координатах x 1 и х 2 образуется в результате пересечения полуплоскостей х 3 и х 4: x 1 * = 517,4; х 2 = 156,5. Соответственно значения переменных х 3 Ä х 4 будут нулевыми: x 3 * =0; х 4 * = 0. Тогда из (3.9) следует, что x 5 * = 42 - 0,035·517,4 - 0,12·156,5 = 5,1. Решением ЗЛП (3.6-3.10) будет вектор X* = (517,4; 156,5; 0; 0; 5,1).

Геометрическое представление ЗЛП отражает следующее:

1) множество допустимых решений Ω выпуклое;

2) оптимальное решение не существует, если множество Ω пустое или неограниченное в направлении перемещения семейства гиперплоскостей уровня цели поиска экстремума;

3) решение находится в одной из угловых точек (вершин) множества допустимых решений Ω, получивших название базисных;

4) для канонической ЗЛП базисные решения характеризуются вектором X - (x 1 , x 2 ,..., х n), в котором значения m переменных отличны от нуля, где m - число линейно независимых уравнений задачи (число базисных переменных угловой точки множества Ω).

Для оптимального решения X* рассмотренного примера базисными переменными стали переменные x 1 , х 2 и х 5 . Оставшиеся переменные (n - m ) называют небазисными или свободными. Их значения в угловой точке равны нулю.

Обратите внимание на то, что любая базисная переменная может быть выражена через небазисные, и базисная переменная в модели (3.6)-(3.10) записывается один раз с коэффициентом единица.

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

47 :: 48 :: 49 :: 50 :: 51 :: Содержание

50 :: 51 :: 52 :: 53 :: 54 :: 55 :: 56 :: 57 :: 58 :: 59 :: 60 :: 61 :: Содержание

3.2.3. Алгебраический (симплексный) метод решения ЗЛП

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

Экстремальное решение достигается не внутри области допустимых решений Ω, а на границе ее (см. рис. 3.2); если быть еще точнее, то в одной из вершин угловых точек многоугольника, образованного в результате пересечения прямых, связанных с определенными ограничениями, либо на отрезке между двумя соседними угловыми точками. Так как экстремум обязательно достигается в одной или двух угловых точках допустимых планов, то нужно просто вычислить значения целевых функций во всех угловых точках (в нашем примере их пять) и

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

К точке оптимума можно подобраться последовательно, переходя от одной угловой точки к соседней, например, каждый раз от исходной (опорной) точки X 0 (х 1 = 0, х 2 = 0) последовательно к той соседней, которая ближе и быстрее приближает к X*. Перебор точек решения по такой схеме позволяет предложенный Р. Данцигом симплекс-метод . Для нашего примера на первом шаге (итерации) от опорной точки X 0 мы перейдем по схеме симплекс-метода к точке X 1 с координатами (700, 0) и на втором шаге перейдем к точке X*. По другому же пути к точке X* можно добраться лишь за три шага. С вычислительной точки зрения симплекс-метод реализуется через так называемые симплекс-таблицы, которые рассчитываются для каждой угловой точки, начиная с опорной. Симплекс-таблицы позволяют определить оптимальность принимаемого решения, значения переменных, оценить ресурсные параметры (ограничения) на предмет их дефицитности, и в случае неоптимального решения, указывают, как перейти к соседней точке (следующей таблице). В силу различных особенностей и постановок задач ЛП симплекс-метод имеет различные модификации: прямой, двойственный, двухэтапный .

Для реализации любого из симплекс-методов необходимо построение начального опорного плана .

Пусть система ограничений такова:

Добавив к левым частям неравенства дополнительные переменные x n+i ≥ 0, i = 1, m , получим каноническую (расширенную) задачу, стратегически эквивалентную исходной, с системой ограничений:

Тогда начальным опорным планом будет вектор

Который удовлетворяет допустимости решения (он является базисным, т.к. число ненулевых элементов равно m , и опорным, т.к. все x j ≥ 0). Пусть система ограничений такова:

Вычтя из левых частей неравенства дополнительные переменные x n+i ≥ 0, i = 1, m , получим расширенную задачу, стратегически эквивалентную исходной, с системой ограничений:

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

не удовлетворяет условиям допустимости решения (он базисный, но не опорный).

Как в первом, так и во втором случае при добавлении дополнительных переменных (они же становятся базисными переменными) в систему ограничений эти же переменные вводятся в целевую функцию с коэффициентами, равными нулю: C n+i ≥ 0, i = 1, m , т.е. в целевой функции при базисных переменных стоят нулевые коэффициенты, а при небазисных - коэффициенты С j , j = 1, n . Пусть целевая функция стремится к минимуму. Тогда значение целевой функции может быть уменьшено, если в базис вводить ту переменную x j , при которой коэффициент С j целевой функции имеет знак минус. И если все коэффициенты в целевой функции имеют знак плюс, то уменьшить ее значение не представляется возможным. Поэтому признаком оптимальности решения ЗЛП служат коэффициенты (оценки) в целевой функции при небазисных переменных.

В зависимости от выполнения условий оптимальности и допустимости применяют ту или иную схему решения ЗЛП .

Методы решения ЗЛП разбиваются на две группы:

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

Точке за конечное число шагов (итераций). К этой группе относятся прямой симплекс-метод, метод потенциалов и другие;

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

При выборе алгоритма решения задачи ЛП исходят из следующих данных. Пусть ЗЛП приведена к каноническому виду, решается на минимум и свободные коэффициенты b i ≥ 0, i = 1, m . Тогда, если в целевой функции задачи имеются отрицательные коэффициенты (условие оптимальности решения задачи не выполняется), а начальный план задачи не имеет отрицательных значений переменных (условие допустимости решения задачи выполняется), то для решения предлагаемой задачи следует воспользоваться алгоритмом прямого симплекс-метода (табл. 3.2). Двойственный симплекс-метод применяется, если условие оптимальности решения задачи выполняется, а допустимости - нет. Двухэтапный симплекс-метод применяется, если условия и оптимальности и допустимости решения задачи не выполняются.

Таблица 3.2

Рассмотрим прямой симплекс-метод решения задач ЛП на следующем примере.

Пример 3.1

Минимизировать функцию Z = -x 1 - х 2 при ограничениях: 0,5х 1 + х 2 ≤ 1;

2х 1 + х 2 ≤ 2;

х 1 , х 2 ≥ 0.

Графическое представление задачи (3.11-3.14) показано на рис. 3.3.

Рис. 3.3. Графическое представление задачи (3.11) - (3.14)

Начальной базисной опорной точкой задачи будет вектор Х 0 = (0; 0; 1; 2). Значение целевой функции в этой точке Z (X 0) = 0.

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

Таблица 3.3

В литературе описаны и другие формы записи симплекс-таблицы . По симплекс-таблице всегда можно сказать, является ли найденное решение оптимальным. В данном случае решение х 1 = 0; х 2 = 0; х 3 = 1; х 4 = 2 не является наилучшим, так как можно ввести в базис одну из переменных х 1 или х 2 (при этих переменных стоят коэффициенты со знаком минус с 1 = -1 и с 2 = - 1), уменьшив значение целевой функции. Тогда вводя в базис одну из небазисных переменных х 1 или х 2 (увеличив ее значение), следует вывести из базиса переменную х 3 или х 4 (доведя ее значение до нуля). В прямом симплекс-методе рассматриваются последовательно вопросы:

• 
  
• 
  
• 
  переход к новой канонической форме ЗЛП (к следующей итерации симплекс-таблицы).

. Целесообразно включить в базис ту переменную, коэффициент при которой имеет наименьшее значение. Коэффициенты при небазисных переменных в неоптимальном решении имеют отрицательные значения. Пусть это будет переменная x s , для которой C s = min j , с j < 0, j не∈ базису. В нашем примере c 1 = c 2 = -1, поэтому включим в базис любую переменную х 1 или х 2 (пусть х 1). Столбец в симплекс-таблице с переменной x s назовем ведущим столбцом, в нашем случае s = l.

. Если в базис включаем переменную x 1 , то это значит, что увеличиваем ее значение с нуля до каких-то определенных пределов. До каких? Обратимся к рис. 3.3. Крайним значением для переменной х 1 будет единица, при этом переменная (прямая) х 4 в ограничении (3.13) примет значение, равное нулю, то есть из базиса выйдет х 4 , а ее место займет переменная x 1 . Из уравнения (3.12) определим значение х 3 = 1 - 0,5 · 1 = 0,5. Таким образом, на следующей итерации (шаге) допустимым решением будет вектор X 1 = (1; 0; 0,5; 0). Значение целевой функции в этой точке Z (1) = -1.

Не прибегая к графическому представлению задачи, определение предельного значения x l и определение переменной х 4 , которую следует вывести из базиса, можно провести на следующем распределении. Если вывести из базиса переменную х 3 , т.е. должно быть х 3 = 0, то из (3.12) следует x l = b 1 /а 1 s = 1/0,5 = 2. Если вывести из базиса переменную х 4 , т.е. сделать х 4 = 0, то из (3.13) x l = b 2 /а 2 s = 1/1 = 1. Получается, что значение x l = 1 или x l = 2. Но при x l = 2 в уравнении (3.13) переменная х 4 = 1 - 2 - 0,5 · 0 = -1, что противоречит условию допустимости решения (3.14). Поэтому включаем в базис x l с наименьшим значением, которое определено из второго ограничения. В этом ограничении находится исключаемая переменная из базиса х 4 . В общем случае переменная x s , включаемая в базис, может увеличиваться до значения

Пусть максимум достигается в строке r , т.е. x s = b r /a rs , тогда в этой строке базисная переменная обращается в нуль, т.е. выводится из базиса. Строку r называют ведущей строкой , а элемент а rs - ведущим элементом . Если в ведущем столбце не найдутся положительные a is , то это означает, что ЗЛП не имеет области допустимых решений.

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

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

Эта таблица на итерации 2 соответствует оптимальному решению X* = X 2 = (2/3; 2/3; 0; 0).

Значение целевой функции Z (X*) = -4/3.

Таблица 3.4

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

Пример 3.2

Максимизировать функцию Z = -х 1 - х 2 при ограничениях:

0,5х 1 + х 2 ≤ 1;

2х 1 + х 2 ≥ 2;

х 1 , х 2 ≥ 0.

В канонической форме ЗЛП примет вид

Графическое представление задачи показано на рис. 3.4.

Рис. 3.4. Графическое представление задачи (3.15) - (3.18)

Составим симплекс-таблицу 3.5.

Таблица 3.5

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

Однако начальное решение Х 0 = (0; 0; 1; -2) является отрицательным.

Попытаемся решить задачу (в противоположность прямому симплекс-методу) последовательным движением от исходной недопустимой точки Х 0 к X*, рассматривая вопросы:

• 
  поиск переменной для исключения из базиса;
• 
  поиск переменной для включения в базис;
• 
  переход к новой форме ЗЛП (последующей итерации решения).

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

Будет и оптимальным и допустимым. В нашем примере исключаем переменную х 4 = -2.

Поиск переменной для включения в базис . Какую небазисную переменную включить в базис х 1 или х 2 ? В принципе любую можно включить в базис с целью движения в область допустимых решений. Из графического представления задачи (см. рис. 3.4) видно, что при включении в базис переменной х 2 мы попадаем сразу в допустимую и оптимальную точку X*. В литературе показано, что к оптимальному решению можно добраться быстрее, если выбирать для включения в базис переменную x s такую, что для нее отношение C s /|a rs | для всех элементов a rs ведущей строки будет минимальным:

Если все элементы a rj · ≥ 0, то это будет означать, что задача не имеет допустимых решений. В нашем примере минимальное отношение (3.19) достигается для переменной х 1 и равно 1/2. Решим задачу табличным способом (табл. 3.6).

Таблица 3.6

Оптимальное решение: X* = (1; 0; 1/2; 0;); Z (X* ) = -z" = -1.

Предположим, что при решении предыдущего примера (см. табл. 3.6) в базис включили бы не х 1 , а переменную х 2 , то получили бы на итерации 1 следующую табл. 3.7.

Таблица 3.7

Нулевая строка в табл. 3.7 указывает на то, что признак оптимальности решения задачи не выполнен, и промежуточное решение X 1 = (0; 2; -1; 0) является недопустимым. Далее задачу можно решать двухэтапным симплекс-методом, методом больших штрафов и другими . Рассмотрим двухэтапный симплекс-метод .

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

3/2 х 1 - х 3 - х 4 + х 5 = 1.

2. Вводим новую (фиктивную) целевую функцию W как сумму вновь вводимых дополнительных переменных, выраженную через небазисные переменные. В нашем случае W = х 5 = 1 - 3/2 x 1 + х 3 + х 4 . Вносим дополнительно строку (3) в табл. 3.8 с фиктивной целевой функцией -W - 3/2 х 1 + х 3 + х 4 = -1.

3. Применяем прямой симплекс-метод для минимизации фиктивной целевой W с пересчетом всех коэффициентов. Первый этап заканчивается, если фиктивная целевая функция W обратится в нуль W = 0, а следовательно, и дополнительные переменные тоже будут с нулевыми значениями. Далее строка с фиктивной целевой функцией и столбцы с дополнительными переменными не рассматриваются. Если в результате минимизации целевой W получим оптимальное значение W , отличное от нуля W ≠ 0, то это будет означать, что исходная ЗЛП не имеет допустимых решений.

Применяем прямой симплекс-метод для оптимизации основной

целевой функции Z . Включаем в базис переменную х 3 вместо переменной х 2 . Делаем пересчет коэффициентов на итерации 3 и получаем оптимальное решение: X* = (1; 0; 1/2; 0;); Z (X*) = -z" = -1.

Таблица 3.8

50 :: 51 :: 52 :: 53 :: 54 :: 55 :: 56 :: 57 :: 58 :: 59 :: 60 :: 61 :: Содержание

61 :: 62 :: 63 :: 64 :: 65 :: 66 :: 67 :: 68 :: 69 :: 70 :: Содержание

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

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

Рассмотрим задачу линейного программирования (3.20)-(3.22) на примере задачи использования ресурсов. Если для этой исходной ЗЛП (назовем ее прямой) ввести переменные y i для оценки ресурсных ограничений (3.21) и сделать переход к математической постановке другой задачи (двойственной или обратной) вида (3.23)-(3.25), то решения прямой и двойственной задач будут находиться во взаимной зависимости, выраженной через соответствующие теоремы двойственности .

Очевидно, задача, двойственная двойственной, совпадает с исходной. Поэтому нет разницы, какую принять в качестве прямой, а какую - двойственной. Говорят о паре взаимно двойственных задач.

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

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

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

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

при каких интенсивностях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 1 , x 2 , … , x M) = 0 F 2 (x 1 , x 2 , … , x M) = 0 … F N (x 1 , x 2 , … , x M) = 0 {\displaystyle \left\{{\begin{matrix}F_{1}(x_{1},x_{2},\ldots ,x_{M})=0\\F_{2}(x_{1},x_{2},\ldots ,x_{M})=0\\\ldots \\F_{N}(x_{1},x_{2},\ldots ,x_{M})=0\end{matrix}}\right.}

может быть сформулирована как задача минимизации целевой функции

S = ∑ j = 1 N F j 2 (x 1 , x 2 , … , x M) (1) {\displaystyle S=\sum _{j=1}^{N}F_{j}^{2}(x_{1},x_{2},\ldots ,x_{M})\qquad (1)}

Если функции гладкие, то задачу минимизации можно решать градиентными методами.

Для всякой гладкой целевой функции можно приравнять к 0 {\displaystyle 0} частные производные по всем переменным. Оптимум целевой функции будет одним из решений такой системы уравнений. В случае функции (1) {\displaystyle (1)} это будет система уравнений метода наименьших квадратов (МНК). Всякое решение исходной системы является решением системы МНК. Если исходная система несовместна, то всегда имеющая решение система МНК позволяет получить приближённое решение исходной системы. Число уравнений системы МНК совпадает с числом неизвестных, что иногда облегчает и решение совместных исходных систем.

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

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

Комбинаторная оптимизация

Типичным примером комбинаторной целевой функции является целевая функция задачи коммивояжёра. Эта функция равна длине гамильтонова цикла на графе. Она задана на множестве перестановок n − 1 {\displaystyle n-1} вершины графа и определяется матрицей длин рёбер графа. Точное решение подобных задач часто сводится к перебору вариантов.

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

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

Линейное программирование – это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием. Такие задачи находят обширные приложения в различных сферах человеческой деятельности. Систематическое изучение задач такого типа началось в 1939 – 1940 гг. в работах Л.В. Канторовича.

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

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

задача об оптимальном использовании ресурсов при производственном планировании;

задача о смесях (планирование состава продукции);

задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или);

транспортные задачи (анализ размещения предприятия, перемещение грузов).

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

математические модели большого числа экономических задач линейны относительно искомых переменных;

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

многие задачи линейного программирования, будучи решенными, нашли широкое применение;

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

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

В общем виде модель записывается следующим образом:

целевая функция

(1.1) при ограничениях

(1.2) требования неотрицательности

(1.3) где x j – переменные (неизвестные);

- коэффициенты задачи линейного программирования.

Задача состоит в нахождении оптимального значения функции (1.1) при соблюдении ограничений (1.2) и (1.3).

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

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

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

Симплекс-метод был разработан и впервые применен для решения задач в 1947 г. американским математиком Дж. Данцигом.

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

Допустимым решением (допустимым планом) задачи ЛП, данной в стандартной форме, называется упорядоченное множество чисел (х1, х2, …, хn), удовлетворяющих ограничениям; это точка в n-мерном пространстве.

Множество допустимых решений образует область допустимых решений (ОДР) задачи ЛП. ОДР представляет собой выпуклый многогранник (многоугольник).

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

Базисным называется решение, при котором все свободные переменные равны нулю.

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

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

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

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

С его помощью можно решить любую задачу линейного программирования.

В основу симплексного метода положена идея последовательного улучшения получаемого решения.

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

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

Процесс применения симплексного метода предполагает реализацию трех его основных элементов:

способ определения какого-либо первоначального допустимого базисного решения задачи;

правило перехода к лучшему (точнее, не худшему) решению;

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

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

6.1.Введение

Оптимизация. Часть 1

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

6.2.Основы теории оптимизации

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

Рассматривая некоторую произвольную систему, описываемую m уравнениями с n неизвестными, можно выделить три основных типа задач. Если m=n , задачу называют алгебраической. Такая задача обычно имеет одно решение. Если m>n, то задача переопределена и, как правило, не имеет решения. Наконец, при m

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

Проектные параметры

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

X1, x2, x3,...,xn.

Целевая функция

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

M=M(x 1 , x 2 ,...,x n).

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

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

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

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

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

замкнутой математической форме, в других случаях она может

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

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

Поиск минимума и максимума

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

Пространство проектирования

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

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

Рис.6.3.Изменением знака целевой функции на противоположный

задача на максимум превращается в задачу на минимум.

удовлетворительного решения. Ограничения делятся на две группы: ограничения - равенства и ограничения - неравенства.

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

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

C 1 (x 1 , x 2 ,...,x n)=0,

C 2 (x 1 , x 2 ,...,x n)=0,

..................

C j (x 1 , x 2 ,...,x n)=0.

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

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

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

z 1 r 1 (x 1 , x 2 ,...,x n) Z 1

z 2 r 2 (x 1 , x 2 ,...,x n) Z 2

.......................

z k r k (x 1 , x 2 ,...,x n) Z k

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

Локальный оптимум

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

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

локальных оптимумов.

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

Глобальный оптимум

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

Пример 6.1

Пусть требуется спроектировать прямоугольный контейнер объемом 1м , предназначенный для перевозки неупакованного волокна. Желательно, чтобы на изготовление таких контейнеров затрачивалось как можно меньше материала (при условии посто-янства толщины стенок это означает, что площадь поверхности должна быть минимальной), так как при этом он будет дешевле. Чтобы контейнер удобно было брать автопогрузчиком, его ширина должна быть не менее 1,5м.

Сформулируем эту задачу в виде, удобном для применения алгоритма оптимизации.

Проектные параметры: x 1 , x 2 , x 3 .

Целевая функция (которую требуется минимизировать) - площадь боковой поверхности контейнера:

A=2(x 1 x 2 +x 2 x 3 +x 1 x 3), м2.

Ограничение - равенство:

Объем = x 1 x 2 x 3 =1м3.

Ограничение - неравенство:

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

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

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

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

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

В общем виде задача ЛП имеет следующий вид:

, (5.1)

, , (5.2)

, , (5.3)

где , , – заданные постоянные величины.

Функцию (5.1) называют целевой функцией; системы (5.2), (5.3) – системой ограничений; условие (5.4) – условием неотрицательности проектных параметров.

Совокупность проектных параметров , удовлетворяющих ограничениям (5.2), (5.3) и (5.4), называют допустимым решением или планом .

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

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

,

, , (5.5)

.

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

,

.

Каноническую задачу ЛП можно также записать в матричной и векторной форме.

Матричная форма канонической задачи ЛП имеет следующий вид:

Векторная форма канонической задачи ЛП.

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

2. Градиент функции.

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

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

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

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

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

где - заданные числа.

4. Стандартная задача лп.

В стандартной форме задача линейного программирования является задачей на максимум (минимум) линейной целевой функции. Система ограничений ее состоит из одних линейных неравенств типа « <= » или « >= ». Все переменные задачи неотрицательны.

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

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

2 вариант ответа:

Стандартная задача ЛП. или, в матричной записи,где- матрица коэффициентов. Векторназывается вектором коэффициентов линейной формы,- вектором ограничений.

5. Каноническая задача лп.

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

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

Короткая запись канонической задачи ЛП:

Х=(х1, х2, …, хn), С=(с1, с2, …, сn).

2 вариант ответа:

Каноническая задача ЛП. или, в матричной записи,

6. Симметричные и несимметричные двойственные задачи.

Двойственная задача линейного программирования. Рассмотрим задачу ЛП (1) или, в матричной записи,(2) Задачей, двойственной к (1) (двойственной задачей), называется задача ЛП отпеременныхвида(3) или, в матричной записи,(4) где. Правила построения задачи (3) по форме записи задачи (1) таковы: в задаче (3)

переменных столько же, сколько строк в матрицезадачи (1). Матрица ограничений в (3) - транспортированная матрица. Вектор правой части ограничений в (3) служит вектором коэффициентов максимизируемой линейной форме в (1), при этом знаки неравенств меняются на равенство. Наоборот, в качестве целевой функции в (3) выступает линейная форма, коэффициентами которой задаются вектором правой части ограничений задачи (1), при этом максимизация меняется на минимизацию. На двойственные переменныенакладывается условие неотрицательности. Задача (1), в отличии от двойственной задачи (3) называется прямой.Теорема двойственности . Если взаимодвойственные задачи (2), (4) допустимы, то они обе имеют решение и одинаковое значение .

Симметричные двойственные задачи

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