Вектор, компонентами которого служат значения частных производных, то есть вектор
называется градиентом функции , вычисленным в точке.
Стандартная математическая формулировка общей задачи линейного программирования выглядит так: требуется найти экстремальное значение показателя эффективности (целевой функции)
(линейной функции элементов решения ) при линейных ограничительных условиях, накладываемых на элементы решения:
где -
заданные числа.
В стандартной форме задача линейного программирования является задачей на максимум (минимум) линейной целевой функции. Система ограничений ее состоит из одних линейных неравенств типа « <= » или « >= ». Все переменные задачи неотрицательны.
Всякую задачу линейного программирования можно сформулировать в стандартной форме . Преобразование задачи на минимум в задачу на максимум, а также обеспечение не отрицательности переменных производится так же, как и раньше. Всякое равенство в системе ограничений равносильно системе взаимопротивоположных неравенств:
Существует и другие способы преобразования системы равенств в систему неравенств, т.е. всякую задачу линейного программирования можно сформулировать в стандартной форме.
2 вариант ответа:
Стандартная
задача ЛП.
или,
в матричной записи,где-
матрица коэффициентов. Векторназывается
вектором коэффициентов линейной
формы,-
вектором ограничений.
В канонической форме задача является задачей на максимум (минимум) некоторой линейной функции F , ее система ограничений состоит только из равенств (уравнений). При этом переменные задачи х 1 , х 2 , ..., х n являются неотрицательными:
|
| |
К канонической форме можно преобразовать любую задачу линейного программирования.
Короткая запись канонической задачи ЛП:
Х=(х1, х2, …, хn), С=(с1, с2, …, сn).
2 вариант ответа:
Каноническая
задача ЛП.
или,
в матричной записи,
Двойственная
задача линейного программирования.
Рассмотрим
задачу ЛП
(1)
или,
в матричной записи,(2)
Задачей,
двойственной к (1) (двойственной задачей),
называется задача ЛП
отпеременныхвида
(3)
или,
в матричной записи,(4)
где
.
Правила
построения задачи (3) по форме записи
задачи (1) таковы: в задаче (3)
переменных столько же, сколько строк в матрицезадачи (1). Матрица ограничений в (3) - транспортированная матрица. Вектор правой части ограничений в (3) служит вектором коэффициентов максимизируемой линейной форме в (1), при этом знаки неравенств меняются на равенство. Наоборот, в качестве целевой функции в (3) выступает линейная форма, коэффициентами которой задаются вектором правой части ограничений задачи (1), при этом максимизация меняется на минимизацию. На двойственные переменныенакладывается условие неотрицательности. Задача (1), в отличии от двойственной задачи (3) называется прямой.Теорема двойственности . Если взаимодвойственные задачи (2), (4) допустимы, то они обе имеют решение и одинаковое значение .
Симметричные двойственные задачи
Разновидностью двойственных задач линейного, программирования являются двойственные симметричные задачи, в которых система ограничений как исходной, так и двойственной задач задается неравенствами, причем на двойственные переменные налагается условие неотрицательности.
Проектные параметры. Этим термином обозначают независимые переменные параметры, которые полностью и однозначно определяют решаемую задачу проектирования. Проектные параметры - неизвестные величины, значения которых вычисляются в процессе оптимизации. В качестве проектных параметров могут служить любые основные или производные величины, служащие для количественного описания системы. Так, это могут быть неизвестные значения длины, массы, времени, температуры. Число проектных параметров характеризует степень сложности данной задачи проектирования. Обычно число проектных параметров обозначают через п, а сами проектные параметры через х с соответствующими индексами. Таким образом п проектных параметров данной задачи будем обозначать через
Х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 (геометрические размеры, электрические сопротивления, массы и т.п.).
Функциональные ограничения, как правило, представляют собой условия работоспособности выходных параметров, не вошедших в целевую функцию. Функциональные ограничения могут быть:
ц (Х) › 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 рублей. Аналогично месячный доход от реализации шкафов составит С
2 х
2 рублей. Обозначив общий доход (в руб.) через Z
, можно дать следующую математическую формулировку целевой функции: определить (допустимые) значения х
1 , и х
2 , максимизирующие величину общего дохода Z
= С
1 х
1 + С
2 х
2 =
| 2 |
| ∑ |
| j=1 |
Ограничения. При решении рассматриваемой задачи должны быть учтены ограничения на расход ресурсов. Пиломатериал идет на изготовление и столов и шкафов. На один стол идет а 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 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*, рассматривая вопросы:
Будет и оптимальным и допустимым. В нашем примере исключаем переменную х 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), то решения прямой и двойственной задач будут находиться во взаимной зависимости, выраженной через соответствующие теоремы двойственности .
Очевидно, задача, двойственная двойственной, совпадает с исходной. Поэтому нет разницы, какую принять в качестве прямой, а какую - двойственной. Говорят о паре взаимно двойственных задач.
Переменные задачи
Построим модель задачи.
Решение
Прежде чем построить математическую модель задачи, ᴛ.ᴇ. записать ее с помощью математических символов, крайне важно четко разобраться с экономической ситуацией, описанной в условии. Для этого крайне важно с точки зрения экономики, а не математики, ответить на следующие вопросы:
1) Что является искомыми величинами задачи?
2) Какова цель решения? Какой параметр задачи служит критерием эффективности (оптимальности) решения, к примеру, прибыль, себестоимость, время и т.д. В каком направлении должно изменяться значение этого параметра (к max или к min) для достижения наилучших результатов?
3) Какие условия в отношении искомых величин и ресурсов задачи должны быть выполнены?
Эти условия устанавливают, как должны соотноситься друг с другом различные параметры задачи, к примеру, количество ресурса, затраченного при производстве, и его запас на складе; количество выпускаемой продукции и емкость склада, где она будет храниться; количество выпускаемой продукции и рыночный спрос на эту продукцию и т.д.
Только после экономического ответа на все эти вопросы можно приступать к записи этих ответов в математическом виде, ᴛ.ᴇ. к записи математической модели.
В задаче требуется установить, сколько краски каждого вида нужно производить. По этой причине искомыми величинами, а значит, и переменными задачи являются суточные объёмы производства каждого вида красок:
x1 – суточный объём производства краски 1-го вида, [т краски/сутки];
x2 – суточный объём производства краски 2-го вида, [т краски/сутки].
В условии задачи сформулирована цель – добиться максимального дохода от реализации продукции. Т.е. критерием эффективности служит параметр суточного дохода, который должен стремиться к максимуму. Чтобы рассчитать величину суточного дохода от продажи красок обоих видов, крайне важно знать объёмы производства красок, ᴛ.ᴇ. x1 и x2 т краски в сутки, а также оптовые цены на краски 1-го и 2-го видов – согласно условию, соответственно 3 и 2 тыс. руб. за 1 т краски. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, доход от продажи суточного объёма производства краски 1-го вида равен 3 x 1 тыс. руб. в сутки, а от продажи краски 2-го вида – 2x 2 тыс. руб. в сутки. По этой причине запишем целевую функцию в виде суммы дохода от продажи красок 1-го и 2-го видов (при допущении независимости объёмов сбыта каждой из красок)
Целевая функция - понятие и виды. Классификация и особенности категории "Целевая функция" 2017, 2018.
ГЛАВА 16. ЭФФЕКТИВНОСТЬ МЕНЕДЖМЕНТА КОНТРОЛЬНЫЕ ВОПРОСЫ 1. Чем вызвана необходимость внешнеэкономической деятельности предприятия? 2. Что благоприятствует внешнеэкономической деятельности предприятия? 3. Что является препятствием для... .
F(X) = 75X1 + 800/X1 + 78X2 + 1600/X2 . Функция выпукла, если F"(x)>0 для любого x. Проверим: ; ; ; . Значит, функция выпукла, поскольку "x>0. Следовательно, выбор оптимального числа поездов на двух участках оказывается задачей выпуклого программирования, которая может быть решена... .
В условиях рыночной системы управления производственной и сбытовой деятельностью предприятий и фирм в основе принятия хозяйственных решений лежит рыночная информация, а обоснованность решений проверяется рынком в ходе реализации товаров и услуг. При таком подходе...
Действие системы, ее поведение характеризуются не только установлением факта достижения цели, но и степенью ее достижения, определяемой с помощью целевой функции.
Целевая функция – есть обобщенный показатель системы, который характеризует степень достижения системой ее цели. Составление целевой функции одна из важнейших задач при проектировании системы. Однако нет общей теории построения целевых функций, есть только некоторые рекомендации.
Целевая функция составляется по указаниям ТЗ о критерии оптимизации путем анализа внешних параметров системы и ограничений на них.
Целевая функция должна существенно зависеть от внешних параметров или части их. В противном случае оптимизация по данной целевой функции не имеет смысла. Целевая функция представляет вектор в m -мерном пространстве внешних параметров системы
Обычно целевая функция задается в скалярном виде.
Используются следующие четыре формы целевой функции.
1. Наиболее часто используется целевая функция одного внешнего параметра
В этом случае целевая функция просто равна одному из внешних параметров или его обратной величине
Все остальные (m – 1) внешних параметров переводятся в систему ограничений.
Физический смысл целевой функции приведенных видов заключается в том, что чем больше (или меньше) параметр y i , тем лучше при прочих равных условиях данная система, причем равенство прочих условий понимается в смысле ограничений на остальные внешние параметры. Типичные задачи с приведенной формой целевой функции: оптимизация системы по надежности (y = P (t )), помехоустойчивости, стоимости и другим внешним параметрам. Такая целевая функция имеет ясный физический (технический или экономический) смысл, объективно характеризует систему и поэтому часто используется. То есть в этом случае целевой функцией является внешний параметр системы. Он и называется целевой функцией системы. Это могут быть: точность, быстродействие, время, стоимость, надежность, масса, габариты, какой-то технологический показатель и т.п.
2. Вторая форма целевой функции – это сумма параметров одной размерности или сумма функций от этих параметров
Такая форма характерна при оптимизации по экономическим критериям, по критериям сложности и т.п.
Например, при минимизации годовых приведенных затрат на систему целевая функция представляет собой сумму двух внешних параметров: годовых эксплуатационных расходов и капитальных затрат, отнесенных к сроку окупаемости системы. В этом случае каждый из этих внешних параметров системы является сложной функцией ее внутренних (подлежащих нахождению) параметров.
Целевые функции задач оптимизации по критерию сложности также имеют вторую форму, т.к. они представляются в виде суммы сложностей отдельных подсистем или блоков системы.
3. Третья форма целевой функции – ранжированная форма – представляет собой упорядоченную совокупность целевых функций первой формы с приоритетами
Первая целевая функция наиболее важная, последняя целевая функция наименее важная.
В частном случае целевая функция этого вида записывается так:
Пример ранжирования – это (например) такая последовательность целевых функций: точность, надежность, стоимость. Смысл целевой функции третьей формы состоит в следующем. Самым главным – первым по рангу – признается некоторый i -й параметр системы – y i (например, точность). Если у некоторой системы этот i -ый параметр больше, чем у всех других систем, то независимо от значений других параметров (если только они удовлетворяют ограничениям) данная система считается лучшей. Затем по второму параметру и т.д.
Процедура оптимизации в этом случае, как правило, является многошаговой. Такая оптимизация часто неосознанно применяется в технических системах. Сначала выбирают систему лучшую по точности, при одинаковой точности нескольких систем – более надежную, а затем – более дешевую. На каждом шаге при оптимизации используется только один критерий, что не противоречит концепции системного подхода (оптимизация по одному единственному критерию, см. далее).
4. Четвертая – наиболее общая – форма целевой функции представляет собой произвольную зависимость от всех или части (но не меньше двух) разнородных внешних параметров
При этом разнородные параметры преобразуются в безразмерные (или одноразмерные) и целевая функция формируется как некоторая композиция (например, среднее арифметическое) полученных безразмерных показателей.
Единую целевую функцию четвертой формы можно получить из целевых функций третьей формы путем умножения их на весовые коэффициенты и последующего суммирования :
где F S (y i ) – одна из k целевых функций третьей формы;
ω S – ее весовой коэффициент.
Однако, как указывается там же, определение весовых коэффициентов отдельных целевых функций является очень сложным.
Экстремальное значение полученной суммы будет считаться оптимальным.
Таким образом, можно указать, что в большинстве случаев (1-я и 3-я формы) показатели качества системы оцениваются численными значениями компонентов векторной целевой функции, которые носят названия функционалов :
- - - - - - - - - - - - - - - - - -
Так как системы работают в условиях случайных воздействий, то значения функционалов часто оказываются случайными величинами. Это неудобно при использовании функционалов в виде показателей качества. Поэтому в таких случаях обычно пользуются средними значениями соответствующих функционалов. Например: среднее количество изделий, выпускаемых за смену; средняя стоимость продукции и т.д.
В
некоторых случаях показатели качества
представляют собой вероятности некоторых
случайных событий. При этом в качестве
целевой функции выбирается вероятность
выполнения системой поставленной цели
(задачи)
Например, вероятность обнаружения цели радиолокатором и т.п.
