Книги по разным темам Pages:     | 1 |   ...   | 4 | 5 | 6 | 7 | 8 |   ...   | 14 |

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

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

3.3. Варианты постановки задач математического программирования Задача линейного программирования, являясь частной задачей теории математического программирования, лучше всех исследована и описана. Тем не менее, выделим еще несколько вариантов постановки указанных выше задач [12]:

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

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

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

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

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

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

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

Задача нелинейного программирования представляет собой наиболее общий вариант постановки задачи оптимизации для непрерывных функций. Классическим методом определения экстремума функции нескольких переменных является метод, основанный на вычислении частных производных. В простейшем варианте задачи нелинейного программирования критериальная функция задана в виде нелинейного выражения E = E x1, x2,..., xn, (3.6) () а ограничения отсутствуют, критическая точка функции (3.6) определяется за счет вычисления первых частных производных, причем в критических точках их значения оказываются равными нулю E EE = 0, = 0,..., = 0.

(3.7) x1 x2 xn В зависимости от конкретного вида функции (3.6) таких точек может быть ни одной, одна или несколько. Существование критической точки является необходимым, но не достаточным условием экстремума. Для его нахождения необходимо вычислить вторые чистые и смешанные производные критериальной функции 2E 2E 2E 2E 2E 2E 2E 2E,,...,,,,...,,,...,.

2 2 x1 x2 xn x1x2 x1x3 x1xn x2x3 xn-1xn Достаточное условие существования локального экстремума формулируется следующим образом [13]: пусть функция E = E x1, x2,..., xn () 0 0 x1, x2,..., xn имеет критическую точку, определяемую за счет вычис() ления выражений (3.7). Тогда, если дифференциал второго порядка n n 2 0 0 d E, x2,..., xn = (x ) 1 E xixj, (3.8) xixj i=1 j=больше нуля, то функция E = E x1, x2,..., xn имеет минимум, а если () выражение (3.8) отрицательно, то функция E = E x1, x2,..., xn имеет () максимум при любых xi и xj, не обращающихся в нуль одновременно. Если в зависимости от xi и xj выражение (3.8) может принимать и положительные, и отрицательные значения, то экстремума в критической точке нет. Если функция (3.6) имеет несколько экстремумов, то их обычно называют локальными. В качестве оптимального решения выбирается решение, соответствующее локальному экстремуму с наибольшим (наименьшим) значением критериальной функции.

В качестве примера рассмотрим функцию двух переменных 4 4 2 E(x1, x2) = x1 + x2 - x1 - 2x1x2 - x. Приравняем к нулю ее первые частные производные E = 4x1 - 2x1 - 2x2 = 0, xE = 4x2 - 2x1 - 2x2 = 0.

x4x1 Вычитая из первого уравнения второе, имеем - 4x2 =, откуда x1 = x. Подставляя в выражения для частных производных, имеем 4x1 - 4x1 =. Получившееся уравнение имеет три решения: 0, 1, Ц1.

Тогда критическими точками являются Е(0,0), Е(1,1) и Е(Ц1,Ц1).

Вторые частные производные имеют вид 2E = 12x1 - 2, x1x2E =-2, x1x2E =-2, x2x2E = 12x2 - 2.

x2xВыберем комбинацию приращений x1 и x2 равными +1 и Ц1, поскольку такие значения соответствуют максимально возможному диапазону изменения аргументов при переходе от одной критической точки к другой [14]. Результаты вычислений вторых частных производных и дифференциала второго порядка (3.8) при различных комбинациях x1 и x2 сведены в табл. 3.1.

Таблица 3.Расчеты критических точек Критическая 2 точка 2E 2E E E 2 0 E(x1, x2 ) x1 x2 d E x1, x2 0 ( ) x2x1 x2x0 x1, x2 x1x1 x1x( ) 1 1 Ц(0,0) Ц2 Ц2 Ц2 Ц2 Ц1 1 0 1 Ц1 Ц1 Ц1 (1,1) 10 Ц2 Ц2 10 1 1 (Ц1,Ц1) Ц1 1 24 Ц1 Ц1 Ц1 Ц1 Как следует из табл. 3.1, в критической точке (0,0) локального экстремума нет, а в точках (1,1) и (Ц1,Ц1) имеют место локальные минимумы. Поскольку в рассматриваемом примере значения критериальной функции в точках (1,1) и (Ц1,Ц1) равны между собой, в качестве оптимального решения можно выбрать любое из двух предложенных. В более сложном варианте задачи нелинейного программирования приходится принимать во внимание кроме критериальной функции (3.6) еще набор m функций, обычно называемых функциями ограничения g (x1, x2,..., xn ) = 0.

(3.9) j Наличие ограничения сужает возможности отыскания экстремума.

В этом случае, как правило, экстремум функции (3.6) не совпадает с локальным экстремумом, определенным с помощью классического метода и называется условным. Для решения подобных задач обычно используется метод Лагранжа, заключающийся в построении новой специальной функции, обычно называемой функцией Лагранжа m L(x2, x,..., xn ) = E(x1, x2, xn ) + g (x1, x2,..., xn ).

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

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

g (x1, x2,..., xn ) bj.

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

Е(x1, x2,..., xn ) = С.

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

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

На рис. 3.2 и рис. 3.3 изображены множества точек, ограниченных ломанной АВСDE. Множество точек на рис. 3.3 не удовлетворяет определению (отрезок MN выходит за пределы многоугольника) и не является выпуклым.

XXC B C A B N N M A M B D ED E XXРис. 3.2. Пример выпуклого Рис. 3.3. Пример невыпуклого множества множества Функция F( X ) = F(x1, x2,..., xn ) наF(x) зывается выпуклой (рис.3.4), если удовлетворяется условие F(X1 + (1- )X2) F(X1) + (1-)F(X2) для любых точек X1,X2, входящих в ее область определения и 0 1. Если в условии поменять знак неравенства X1 X2 X Рис. 3.4. Пример выпуклой на противоположный, то получится опфункции ределение вогнутой функции. Перечислим свойства выпуклых функций:

1. Если F(X) выпукла, то - F(X) вогнута.

2. Константа F(X) = С и линейная функция F(X) =aX+b являются всюду выпуклыми и всюду вогнутыми.

3. Если функции Fi(X), i=1,2,Е, m выпуклы, то при любых действиm тельных i функция также является выпуклой.

F( X ) i i=Отличительной особенностью выпуклых функций является то обстоятельство, что любая из них имеет не более одной точки, в которой все ее частные производные обращаются в нуль. Если такая точка существует, то она и является экстремумом. В зависимости от ограничений область определения переменных может быть такой, что упомянутая точка отсутствует вообще. В этом случае экстремум следует искать где-то на границе области определения функции.

Задача выпуклого программирования в общем виде может быть сформулирована следующим образом. Пусть критериальная функЕ = Е(x1, x2,..., xn ) ция в своей области определения является либо выg (x1, x2,..., xn ) bj пуклой, либо вогнутой функцией, а все ограничения j являются функциями выпуклыми. Тогда оптимальное решение соответствует такой точке, удовлетворяющей ограничениям, в которой выпуклая функция Е = Е(x1, x2,..., xn ) достигает своего минимального значения, а вогнутая - максимального.

Поскольку задача выпуклого программирования является частным случаем задачи нелинейного программирования с одним локальным экстремумом, общий метод ее решения не отличается от рассмотренного выше. Интересен случай, когда целевая функция и функции ограничений представляют собой так называемые сепарабельные функции, т.е. функции, каждая из которых может быть представлена в виде суммы функций одной переменной n E(x1, x2,..., xn ) = (xi ), max, Ei i=n g (x1, x2,..., xn ) = (xi ).

j gij i=В этом случае существует приближенный метод решения задач выпуклого программирования, основанный на замене нелинейных функций их линейными аналогами и сведении задачи к задаче линейного программирования [11]. Пусть существует некоторая выпуклая или вогнутая функция h(x), определенная на интервале [0,a]. Разобьем интервал определения на r частей точками x0 < x1 <... < xk так, чтобы x0 = 0, xk = a и определим набор значений функции в этих точках h0,h1,...,hk. Заменим функцию h(x) между точками xk и xk+1 отрезком () прямой, проходящей через hk и hk+1 и обозначим получающуюся в этом случае ломанную как. Уравнение участка ломанной на интервале h(x) [xk, xk+1] имеет вид ) h(x) - hk x - xk ==.

hk+1 - hk xk+1 - xk Тогда x =xk+1 + (1-)xk, h(x) =hk+1 + (1-)hk.

Величина косвенно характеризует угол наклона отрезка ломанной на заданном интервале. Обозначив 1 - = k и = k+1, имеем x =k xk +k+1xk+1, h(x) =khk +k+1hk+1.

где k + k+1 = 1, k 0, k+1 0. Тогда для любого x 0,a можно [ ] записать уравнение аппроксимирующей ломанной z x = xk, k k= zz h(x) = hk, = 1, k0.

k k k=0 k=Приближенная задача в этом случае сводится к задаче линейного программирования n E(x1, x2,..., xn ) = (xi ), mx, Ei i=n g (x1, x2,..., xn ) = (xi ).

gj i=и может решаться обычными методами, используемыми для решения подобных задач.

Задача нелинейного программирования, у которой целевая функция квадратична, а ограничения линейны n n n E(x1, x2,..., xn ) = x xk + x, hjk j c j j j=1 k=1 j=n gi (x1, x2,..., xn ) = x < bi aij j j=называется задачей квадратичного программирования. Такие задачи являются частным случаем задачи выпуклого программирования и могут решаться, например, приближенным методом. Тем не менее, в литературе описаны и методы точного решения подобных задач [12].

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

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

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

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

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

Pages:     | 1 |   ...   | 4 | 5 | 6 | 7 | 8 |   ...   | 14 |    Книги по разным темам