БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ РАДИОФИЗИКИ И ЭЛЕКТРОНИКИ

Ю. Л. Крученок

ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ

МЕТОДЫ И МОДЕЛИ

Учебное пособие

Минск

2005

Рекомендовано Ученым советом

факультета радиофизики и электроники

30 марта 2004 г., протокол № 8 Крученок Ю. Л.

Экономико-математические методы и модели: Учебное пособие. – Мн.: БГУ, 2005. – 100 с.

Излагаются материалы лекций курса "Экономико-математические методы и модели" для студентов специальности E 25 01 10 "Коммерческая деятельность" факультета радиофизики и электроники Белорусского государственного университета.

Для студентов специальностей: G 31 04 02 "Радиофизика", G 31 "Физическая электроника"; проходящих специализацию на кафедре системного анализа. Может быть полезной студентам инженерных специальностей и научно-техническим работникам, деятельность которых связана с изучением теории игр и методов оптимизации.

ПРЕДИСЛОВИЕ

Предлагаемое учебное пособие "Экономико-математические методы и модели" содержит материалы лекций, которые читаются автором студентам 3-го курса специальности "Коммерческая деятельность" факультета радиофизики и электроники БГУ. Пособие преследует собой цель изложить основные понятия теории игр и теории оптимизации, выработать у студентов навыки построения экономических моделей, оказать помощь в овладении методикой применения изложенных методов для решения практических экономических и инженерных задач.

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

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

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

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

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

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

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

Часть 1.Рациональное ведение хозяйства и экономика 1.1 Проблема рационального ведения хозяйства Основной задачей экономики является рациональное ведение хозяйства, то есть распределение ограниченных ресурсов для достижения поставленных целей. К таким задачам относится задача распределения дохода на цели потребления и на сбережения, распределение расходов на потребление между различными видами товаров и услуг, и другие. Таким образом, проблема рационального ведения хозяйства может рассматриваться как задача математической оптимизации, то есть задача определения таких значений переменных величин, удовлетворяющих ряду ограничений, при которых достигается максимум определенной функции. В качестве переменных выступают те “инструменты”, с помощью которых осуществляется конкретное распределение.

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

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

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

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

- фирмы - предприятия, производящие товары или услуги для продажи другим фирмам или потребителям;

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

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

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

Потребитель Классическая Неоклассический и другие Функция потребителя, зависящая от будущего, и от текущего Средства Уровни потребления всех Сбережения, выбор профессии.

(инструменты) товаров и услуг Ограничения Финансовые ограничения: Заданы кривые предложения, а Нормативные Распределяйте доход Сберегайте в зависимости от Целевая Зависит от занятости и от ставок заработной платы функция членов профсоюза.

Средства Заключение коллективного договора с (инструменты) предпринимателем. Прием новых членов, забастовка, Ограничения Предложение труда и спрос на труд. Сопротивление предпринимателя. Правовые ограничения.

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

Ограничения Технологическое Задана кривая спроса, а не Нормативные Приравнивайте Используйте для конкуренции правила предельные доходы от не только цены, но и другие соответствующих Используйте товарофакторов по всем видам материальные запасы так, Целевая Правительственные "функции социального функция благосостояния", зависящие от занятости, производства, покупательной способности населения, экономического роста, циклических процессов, несправедливого Средства Политика в области финансов, налогов, (инструменты) государственного долга, установления цен и Ограничения Спрос и предложение в экономике государства, Нормативные Автоматические стабилизаторы, с помощью которых правила компенсируются нежелательные изменения в экономике (например, страхование по безработице). Крупные Одним из основных элементов экономической теории является домашнее хозяйство, определяемое как группа лиц, распределяющая свой доход на покупку и потребление товаров и услуг. Проблема рационального ведения хозяйства потребителя заключается в определении количества каждого товара, которое должен приобрести потребитель при заданных ценах и известном доходе.

1.3.1. Пространство товаров. Отношение предпочтения Поведение потребителя выражается в выборе точки из “пространства товаров”. Пусть существует конечное число товаров n, количество каждого из них, приобретенное потребителем, характеризуется набором товаров x = ( х1, х2,..., хn)',где хj - количество j-го товара, приобретенного потребителем. Здесь и далее ' (штрих) означает транспонирование.

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

Тогда все возможные наборы товаров - векторы пространства товаров С={ x = ( х1, х2,..., хn)', хj>0, j=1,n} - неотрицательный октант евклидова пространства - выпуклое множество.

Выбор потребителем набора товаров зависит от вкусов потребителя.

“предпочтительнее чем” или “равноценен” - знак. Таким образом, запись хy, где х,у С, означает, что рассматриваемый потребитель либо предпочитает набор х набору у, либо не делает между ними различий.

Будем говорить, что наборы х и у безразличны для потребителя х~y, если каждый из них предпочтительнее или безразличен по отношению к другому, то есть xy и yx. Потребитель предпочитает набор х набору у х>у, если х предпочтительнее или безразличен у, а у не предпочтителен или не безразличен х.

Определение. Отношение совершенно, если для любых х,у С верно xy или yx, или одновременно.

Определение. Отношение называется полуупорядоченностью, если оно транзитивно ( для любых x,y,z C, таких что xy и yz, верно x>z) и рефлексивно ( для любого х С верно хх).

Аксиома 1. Отношение слабого предпочтения является совершенной полуупорядоченностью в пространстве С.

Следствие. Отношение безразличия транзитивно ( если х~у и у~z, то х~z), рефлексивно ( х~х ) и симметрично ( если х~у, то у~х для любых х,у,z С).

Отношение безразличия подразделяет С на классы эквивалентности попарно непересекающиеся подмножества (множества безразличия), каждое из которых состоит из всех наборов, безразличных заданному набору х: Iх={y C ; y~x}.

Аксиома 2. Слабое отношение предпочтения непрерывно, то есть предпочтительные множества Px={y C, yx} и непредпочтительные множества NPx={y C, xy} для любого х С являются замкнутыми множествами пространства С.

По этой аксиоме граничные точки образуют множество Ix=PxNPx.

Из двух аксиом следует, что существует непрерывная действительная функция, определенная на С, которую будем называть функцией полезности U(x) и для которой U(x) U(y), если ху. Конечно, такая функция не единственна. Ей может служить любая строго возрастающая функция, например, расстояние до начала координат. Если U(x) - функция полезности, то ею является и функция g[U(x)], где g(y) - строго возрастающая функция.

Аксиома ненасыщения. Для любых х,у С таких,что ху ( то есть хjуj, j=1,n) следует ху, для любых х,у С таких, что ху и ху => х>у.

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

Аксиома ненасыщения в терминах функции полезности. Если хy, то U(x) U(y); если xy и xy, то U(x)>U(y).

Если U(x) дифференцируема, то предельные полезности - первые частные производные: U(x)/x=MU(x)>0.

Аксиома строгой выпуклости. Для любых х,у С таких, что ух, верно y+(1-)xx для любого, 0p.

Это означает, что потребитель предпочитает лотерею с большей вероятностью получить предпочитаемый набор. В частности x > (p,x; (1-p),y) для p>0, то есть набор, получаемый наверняка предпочтительнее любой лотереи, содержащей его и менее предпочтительный.

Аксиома непрерывности. Если даны три набора x>y>z, то существует вероятность p, для которой (p,x; (1-p), z) ~ y, где p>0.

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

Аксиома о независимости не связанных между собой альтернатив.

Пусть заданы наборы х~y, тогда для любого z следует (p,х; (1-р),z)~ (p,y;

(1-p),z) для любого p>0.

То есть присутствие третьего набора не нарушает предпочтений.

Аксиома о приведении сложных лотерей. Пусть даны m лотерей Li=(p i1,x1; p i2,x2;...; p is,xs), i=1,m. Рассмотрим сложную лотерею L=(q 1,L1;

q 2,L2;...; q m,L m), где q i - вероятность получить лотерею Li. Тогда сложная лотерея может быть приведена к лотереи с подходящими вероятностями L ~ L'=( r1,x1; r 2,x2;...; rs,xs), где ri = q 1p 1i + q 2p 2i+...+ q mp mi, i=1,s.

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

Так как частным случаем лотереи является набор х=(1,х), функция полезности определена для всех наборов, причем U(x)>U(y) тогда и только тогда, когда x>y. В общем виде U(p 1,x1; p 2,x2;...; p s,xs) = есть полезность лотереи есть математическое ожидание полезности, равное взвешенной сумме полезностей наборов, где в качестве весов выступают вероятности.

Согласно основной теореме, если U(x) - функция полезности, то aU(x)+b, a>0 - тоже функция полезности. Ее можно построить, выбрав числовые значения для двух уровней полезности. Полезности других наборов оценивают взвешиванием вероятностями. Пусть х>y и выбраны числа U(x),U(y), причем U(x)>U(y) - уровни полезности х и у. Если x>z>y, то по аксиоме непрерывности существует p>0, что (p,x;(1-p),y)~z, следовательно, U(z)=U(p,x;(1-p),y)=pU(x)+(1-p)U(y). Если z>x, то по аксиоме непрерывности существует p>0, что x~(p,z; (1-p),y), поэтому U(x)=pU(z)+(1-p)U(y), следовательно, U(z)=U(x)/p-U(y)(1-p)/p. Таким образом, если выбраны два числа, шкала полезности фон НейманаМоргенштерна определена.

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

Пусть фирма производит один вид продукции, используя n видов затрат. Обозначим xj - количество j-го вида затрат, j=1,n, следовательно, x = (x1, x2,..., xn)' - вектор затрат. Пространство затрат I - неотрицательный октант n-мерного евклидового пространства, все затраты изменяются непрерывно. I={(x1, x2,..., xn)', xj >0}. Связь между выпуском продукции и затратами описывается производственной функцией q=f(x). Считаем, что она непрерывно дифференцируема и удовлетворяет двум аксиомам.

Аксиома 1. Существует подмножество пространства затрат экономическая область, в которой увеличение любого вида затрат не приводит к уменьшению выпуска продукции, то есть если х>y, то f(x)>f(y) при x,y из экономической области.

Очевидно, что в этой области вектор предельного продукта f(x)/x=MP(x)>0. Тогда экономическая область {x I, MP(x)0}.

Аксиома 2. Существует особая область R - выпуклое подмножество экономической области, для которой матрица Гессе функции f(x):

2f(x)/x2 - отрицательно определена для любых x R.

В области R производственные множества {x I, f(x)q o} выпуклые для любого qo 0, а также 2f(x)/x20 – фактор шкалы, b j>0 – деятельно 1.4.2. Неоклассическая теория фирмы Данная теория построена на том, что цель фирмы - максимизация прибыли путем выбора видов затрат при заданной функции f(x), заданных ценах выпуска p и ценах затрат w. Прибыль П равна годовому доходу R без издержек производства С : П=R-С, где R=pq=pf(x), C=w'x. Решая долгосрочную задачу, фирма свободна выбрать любой вектор затрат из пространства затрат. Следовательно, имеем задачу: max П(х)=pf(x)-w'x; х это задача нелинейного программирования с n+1 параметром p и w.

В краткосрочной задаче фирма выбирает вектор х из подмножества затрат, характеризуемых m ограничениями g(x) суммирование по всем выпускам дает спрос экономики на i-й фактор:

i-го фактора, так как спрос на i-й фактор не превышает предложения.

В матричной форме Bxr, где B0 - mxn-матрица технологических коэффициентов производства факторов, r - m-вектор первичных факторов.

Цены в экономике обозначим p=(p 1,p 2,..., p n)' 0, w=(w1, w2,..., w m)' 0, где p j - цена продукта j, wi - цена фактора i. Считаем, что экономика конкурента, то есть потребители и фирмы пользуются заданными ценами.

Так как считается, что средние издержки производства каждого товара не меньше цены этого товара, то, p ka kj - стоимость товара k, необходимого для производства единицы товара j; wib ij - стоимость фактора i, необходимого для производства единицы товара j. В матричном виде условие неприбыльности запишем p'A+w'Bp, или p'(I-A)w'B. Согласно предположениям относительно метода “затраты - выпуск”, и совершенной конкуренции (в производственном процессе не создается прибыли), прямая задача ЛП заключается в максимизации значения конечного продукта при выборе выпусков всех продуктов:

p'c max ; x=Ax+c; Bxr; x0; или p'(I-A)x max ; Bxr; x0.

Переменные двойственной задачи - цены: w'r min ; p'A+w'Bp; w0 w задача минимизации стоимости первоначальных факторов, при выборе значений цен факторов. В других обозначениях: w'r min ; w'Bp'(I-A);

w0. Определив упорядоченные цены p ^ =p' (I-A), сформулируем обе задачи: p^'x max, Bxr, x0; w'r min ; w'Bp ^, w0.

Для доказательства существования равновесия, нужно описать систему предпочтений - функцию спроса на товары и функцию предложения факторов. Эти функции получаются путем обобщения функций потребителей того же типа и зависят от всех цен. Спрос на j-й товар обозначают вектором cj=cj(p,w), j=1,n, а предложение i-го фактора вектором ri=ri(p,w), i=1,m. В векторных обозначениях c=c(p,w), r=r(p,w).

Считаем эти функции однозначными и непрерывными. Cуществование векторов p*, w*, x*, r*, c*, удовлетворяющих условиям x=Ax+c, Bxr, p'A+w'Bp, c=c(p,w), r=(p,w), строго доказывается при помощи теоремы Какутани о неподвижной точке.

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

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

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

Рассмотрим экономику, которая производит n товаров x1, x2,..., xn (товары и факторы). Цены характеризуются n-вектором р. Для любого набора цен существует функция спроса на товар j: xj =xj (p), полученная обобщением функций спроса потребителей и фирм. Аналогично, функция предложения товара j: yj = yj (p). Тогда E j(p)=xj(p)-yj(p), j=1,n - избыточный спрос. Обозначим E(p)=( E 1(p), E 2(p),..., En(p))'.

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

Рассмотрим пример игры, не имеющей седловой точки, представленный выше.

получить при любой из смешанных стратегий, соответствуют отрезку, соединяющему точки (0;6) и (1;-4). Поскольку игрок 1 рассматривает наихудшие варианты, то выделенная на чертеже фигура - геометрическое место точек, которое соответствует наименьшим значениям ожидаемых выигрышей игрока 1. На выделенной фигуре найдем точку с максимальной ординатой. Из уравнения -2(1-р 12)+5р 12=6(1-р 12)-4р определим абсциссу этой точки - искомую вероятность р 12*=8/17, следовательно, р 11*=9/17. Ордината искомой точки - цена игры: V=22/17.

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

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

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

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

Дадим точное определение точки равновесия. Точкой равновесия называется пара векторов р 1*, р 2*, определяющих оптимальные смешанные стратегии каждого игрока, то есть стратегии, приводящие игрока к максимально ожидаемому выигрышу при условии, что противник применяет свою оптимальную смешанную стратегию. Следовательно, р 1`П1р 2*0 - прямое ограничение.

Любой n-вектор х, удовлетворяющий ограничениям задачи (1), называют ее планом. План хo, являющийся решением задачи (1), называют оптимальным планом. План х называют базисным, если n-m его компонент равны 0, а остальным компонентам хj1, хj2,..., хjm соответствуют линейно независимые векторы условий а j1, а j2,...,а jm. I={1, 2,..., m}, J={1, 2,..., n}. Множество J ={j1, j2,..., jm} - множество базисных индексов, Jн=J\J - множество небазисных индексов. План х=х(J) - базисный, если хн=х(Jн)=0, det А =0, А=А(I,J). Матрица А называется базисной, х(J) - базисные переменные плана х, х(Jн) - небазисные переменные. Отметим, что базисный план можно построить по базисной матрице: х=А -1b, хн =0. Базисный план назовем невырожденным, если х(J)>0.

3.1.1. Критерий оптимальности. Итерация Пусть х - _базисный план с базисной матрицей _ А. Рассмотрим другой _план х=х+х. Найдем формулу приращения с`х-с`х=с`х. Так как Ах=b, Ах=b, то Ах=0 или Ах+Анхн=0, следовательно, х=-А -1Ан х н.

Отсюда имеем с`х=с`х +сн`хн=-(с`А -1Ан-сн`)хн. Рассмотрим m-вектор потенциалов: u`=u`(I)=с`А -1 и n-m-вектор оценок н`=u`Ан-сн`.

Окончательно получаем с`х=- н`хн=- jхj. Смысл оценки: j - это взятая с обратным знаком скорость изменения целевой функции в точке х при увеличении j-ой небазисной переменной базисного плана.

Теорема (критерий оптимальности). Неравенство (Jн)>0 достаточно, а в случае невырожденности и необходимо, для оптимальности базисного плана х.

Теорема. Если среди оценок базисного плана х существует оценка jo0. Следовательно, наибольшее o, при котором х остается планом задачи, равно o=io=хio/xjojo=min хj/x jjo, где минимум берется для xjjo>0, j J. Если базисный плана компонента хio=0, а компонента хjo = o>0, значит план х базисный, при этом J=(J\io) jo. Можно строго показать, _ что _при выполнении всех описанных условий новая базисная матрица А=А(I,J) невырождена.

Описанный переход называется симплексной итерацией.

Заметим, что при небольшом числе небазисных переменных рекомендуют правило выбора jo: jo = min j, j Jн.

Пусть на k-й итерации известна матрица (А -1)k =([А(I,Jk )] -1)k, которой соответствует базисный план х={х(Jk)=(А -1)k b, х(Jk н)=0}, Jk н=J\Jk.

Шаг 1: вычислим вектор u`(I)=с`(Jk )(А -1)k.

Шаг 2: вычислим оценки j =u`(I)А(I,j)- cj, j Jk н.

Шаг 3: если среди оценок j, j Jk н нет отрицательных, то получен оптимальный план х. Иначе переходим к шагу 4.

Шаг 4: если среди (Jk н) имеются отрицательные, то выберем одну из них jo0, j Jk вычислим j=хj/хjjo и запомним наименьшее o=io, io=io(k).

Шаг 8: заменим Jk+1 =(Jk \io) jo; Jk+1н =(Jk н\jo) io и вычислим элементы u ij новой обратной матрицы: u jj = u joj / хiojo, j I, u ij= = u ij- хijo u ij /хjojo, i jo, i J, j I, где u ij - элементы старой (А -1)k, пересчитаем новый базисный план и перейдем к шагу 1.

3.1.3. Геометрическая интерпретация Множество, образованное пересечением конечного числа полупространств и гиперплоскостей, называют многогранником. На рисунке изображены два многогранника в R 2 и в R 3: Х1={(х1, х2): х1+х2= =1, х1>0, х2 >0}, Х2={(х1, х2, х3): х1+х2 +х3 =1, х1>0, х2 >0, х3 >0}.

Таким образом, множество планов задачи ЛП - многогранник.

Базисному плану соответствует его вершина. Итерация - переход от вершины к соседней вершине, в которой значение целевой функции не меньше. Можно доказать, что для имеющей решение невырожденной задачи симплекс-метод конечен, количество его итераций не превосходит 2m, в то время, как количество базисных планов может достигать Сmn.

Рассмотрим вспомогательную задачу к задаче (1):

в которой x u=х(Ju), J={n+1, n+2,..., n+m} - m-вектор искусственных переменных, е` =(1, 1,..., 1) - m-вектор.

Для непустоты множества планов задачи (1) необходимо и достаточно, чтобы в решении задачи (2) хоu=0. Для задачи (2) начальный базисный план х(J)=0, х(Ju )=b, причем компонентам x u соответствует невырожденная единичная базисная матрица. Решение задачи (2) - первая фаза симплекс-метода задачи (1), а задача (2) - задача первой фазы.

При решении задачи (2) возможны три варианта: а) xоu 0; б) xоu=0, Ао состоит из векторов условий исходной задачи (1); в) xоu=0, в Ао имеются искусственные векторы условий. В случае а) ограничения задачи (1) противоречивы. В случае б) хо(J) - базисный план задачи (1) с базисной матрицей Ао - начальный базисный план задачи (1). В случае в) rank А, то оно эквивалентно равенству 1x1+2x2+…+nxn-n+1xn+1= и неравенству xn+1>0 со свободной переменной xn+1. Если в задаче не наложено ограничение на знак переменной xj, то ее заменяют на разность двух неотрицательных переменных xj=х1 j-х2 j, х1 j>0, х2j>0, используя тот факт, что любое число можно представить, как разность положительных чисел.

3.1.6. Пример. Производственная задача. Симплексная таблица Пусть на предприятии производится n типов продукции. При этом расходуются ресурсы m типов в объемах b 1, b 2,..., b m. Известны затраты а ij i-го ресурса на изготовление единицы j-й продукции и прибыль сj от реализации единицы j-й продукции. Требуется найти план производства с максимальной прибылью. Рассмотрим задачу, где 1-й и 2-й ресурс должны использоваться полностью:

Введя свободную переменную x5 и разделив 1-е равенство на перейдем к канонической форме, содержащей единичные столбцы а 1 и а 5:

В задаче первой фазы достаточно ввести одну искусственную переменную Вектор (200, 0, 0, 0, 700, 500) - базисный план задачи первой фазы с базисной матрицей А ={а 1=е1, а 5 =е3, а 6 =е2}. Для решения задачи первой фазы составим симплексную таблицу:

После заполнения таблицы вычисляем j=с А а j-сj, j=Jн с учетом того, что А=Е. Находим минимальный элемент jo= 3=-10, он отрицателен, то есть план не оптимален. Столбец а 3 назовем ведущим. Элементы х(J) (столбца b), соответствующие хijo>0 ведущего столбца, разделим на хijo и результаты занесем в -столбец, где найдем min i= o=6=50. Строку а назовем ведущей. Элемент хiojo, лежащий на пересечении ведущих строки и столбца, называется ведущим элементом хiojo=10. Заменим в базисе а (соответствует ведущей строке) на а 3 (соответствует ведущему столбцу).

Запишем единичные столбцы а 1, а 3, а 5. Строку а 3 разделим на ведущий элемент. Оставшиеся 8 элементов таблицы,_ включая и элементы столбца b, пересчитаем по правилу прямоугольника хij = хij – хioj хijo /хiojo. Например, b 1=200-500 1/10=150. Таблица будет иметь вид:

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

Составим таблицу для исходной задачи:

Подсчитав небазисные оценки, получим, что все они положительны, таким образом, получен оптимальный план хo =(150, 0, 50, 0).

3.2. Теория двойственности. Двойственный симплекс-метод Теорией двойственности ЛП называется раздел, в котором задачи ЛП исследуются с помощью вспомогательных двойственных задач.

Рассмотрим каноническую задачу которую будем называть прямой задачей. Каждому оптимальному базисному плану х с базисной матрицей А соответствует m-вектор потенциалов u(I): u`А =с`, u`Ан >сн. Подсчитаем значение функции b`u:

b`u=u`b=с`А-1 b=с`хo= с`хo. Пусть m-вектор у удовлетворяет неравенству А`у>с. Тогда b`y=y`b=у`А хo>с`хo. Значит, вектор u - решение задачи Задача (2) называется двойственной канонической задачей ЛП. Она составлена из параметров задачи (1), содержит m переменных у(I) и n основных ограничений, на у не наложены прямые ограничения.

Рассмотрим задачу ЛП в нормальной форме:

Она эквивалентна следующей канонической задаче:

Применив аналогичные рассуждения, получим задачу, двойственную Сравнивая пары задач, заключаем: каждому i-му основному ограничению одной задачи соответствует i-я переменная другой; если основное ограничение - равенство, то соответствующая переменная двойственной задачи не имеет ограничения на знак; если основное ограничение - неравенство, то соответствующая двойственная переменная неотрицательна; если переменная не имеет ограничения на знак, то соответствующее ограничение двойственной задачи - равенство; если переменная задачи неотрицательна, то соответствующее ограничение двойственной задачи - неравенство.

Приведем без доказательства несколько теорем теории двойственности.

Теорема существования. Для существования решения задачи ЛП необходимо и достаточно, чтобы не были пустыми множества ее прямых и двойственных планов.

Теорема двойственности. Для существования решения х прямой задачи ЛП необходимо и достаточно существование решения у двойственной задачи, при этом с`х=b`у.

Следствие 1. Для любой пары из прямого х и двойственного у планов выполняется неравенство с`х В терминах производственной задачи эта теорема означает: уoi - мера чувствительности максимальной прибыли к изменению i-го ресурса. Если уoi>0, то увеличение i-го ресурса ведет к увеличению максимальной прибыли и тем эффективнее, чем больше уoi. При уo iс. Двойственный план у назовем базисным с двойственной базисной матрицей А = А(I,J), если det А =0, и А`у=с, Ан`y>сн. Совокупность (а j, j J) называется двойственным базисом. Базисный двойственный план невырожденный, если на нем Ан`y>сн. Вектор (I)=А`у-с, называется копланом. Базисный коплан удовлетворяет соотношениям (J)=0, det А(I,J)=0. Вектор (J) с компонентами (J)=А-1b, (Jн)=0, называется базисным псевдопланом.

_Рассмотрим приращение двойственной целевой_ функции b`y-b`у=b`у. Из определений следует `(J)=`(J)-`(J)=y`А -с`(J)J)=у`А+у`А-с`- `=у`А. С учетом определения псевдоплана имеем Из последней формулы следует смысл компонент псевдоплана: j скорость изменения двойственной целевой функции в точке у при увеличении j-й компоненты коплана.

3.2.3.Критерий оптимальности. Итерация Пусть у - базисный двойственный план с двойственной базисной матрицей А =А(I,J), ={ =А-1 b, н =0} - базисный псевдоплан.

Теорема. (критерий оптимальности) Неравенство > 0 достаточно, а в случае невырожденности и необходимо, для оптимальности базисного двойственного плана у. Базисный псевдоплан, соответствующий у, является оптимальным, прямым планом.

Пусть критерий оптимальности не выполняется, и некоторой неотрицательные числа xioj>0, j Jн, где xij, i J, j Jн - i-я компонента вектора А а j, то ограничения прямой задачи (1) противоречивы. Это достаточное условие отсутствия прямых планов.

Пусть для каждой отрицательной _компоненты io существует x ioj0, Jн =(Jн\ jo) io. При такой замене матрица А(I,J) будет невырожденой. Переход от старого базисного коплана к новому называется итерацией двойственного симплекс-метода.

Отметим, что при выборе io часто используют правило: io= min j, j J.

Пусть на k-й итерации известны множество Jk, матрица (А-1) k и компоненты k`(J kн)=с`(J k)(А-1) k А(I,J kн)-с`(J kн), Jkн=J\Jk.

Шаг 1: вычислим вектор (Jk) =(А-1) k b.

Шаг 2: если среди j, j Jk нет отрицательных, то решение задачи (1) закончено на оптимальном плане хo={хo(Jk)=(Jk), хo(Jkн)=0}. Иначе переходим к шагу 3.

х1>0, х2>0, х3>0. xj>0, j =1,2,…,7. -у3>0; -у4>0.

Вектор (0, 0, 0, 0) - базисный двойственный план задачи с отрицательной единичной двойственной базисной матрицей А=(а 4, а 5, а 6, а 7)=-Е. Начальный базисный коплан =(1, 3, 1, 0, 0, 0, 0).

Таблица заполняется аналогично симплекс-таблице:

базис Поскольку А представляет -Е, то все параметры занесены с противоположенными знаками. Строка - компоненты коплана. Так как существуют отрицательные i (столбец b), переходим к итерации. Найдем минимальный io=5=-3. Строка io - ведущая. Для каждого хioj0 узел называется источником (Аi пункт производства, а i - объем производства), при аi - дуговой поток - количество продукта, транспортируемого из Аi в Аj.

Пусть I+i={j: (i,j) U}, I-i={j: (j,i) U} - множества узлов, которые соединены с узлом i дугами из U, начинающимися в i (I+i) или оканчивающимися в i (I-i). В узле i выполнено условие баланса, если xji = a i. То есть количество продукта, поступающего в Аi и производимого в нем, равно количеству вывозимого и потребляемого.

Совокупность х={хij: (i,j) U} дуговых потоков называется потоком сети S={I, U}, если она удовлетворяет условию баланса в каждом узле i I. Дугам (i,j) U припишем числа сij - стоимость единичного дугового транспортных расходов на плане перевозок х={хij, (i,j) U}.

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

Дугу (i,j), лишенную ориентации, назовем ребром (i,j) с граничными узлами i, j. Узел сети называют висячим, если он граничен для единственного (висячего) ребра. Последовательность ребер (i1, i2), (i2, i3),..., (ik-1, ik) назовем цепью, соединяющей узлы i1, ik. Выберем направление движения вдоль цепи. Если это направление совпадает с направлением дуги ij, то дуга (i,j) - прямая, иначе - обратная. Сеть называется связной, если любые ее два узла можно соединить цепью. Цепь {i1, i2,..., ik}, где узлы i1 и ik совпадают, называется циклом. Сеть называется деревом, если |I|=|U|+1. Для сети S={I,U} сеть S*={I,U*}, где U* U, называется частичной сетью. Частичная сеть S*, являющаяся деревом, называется деревом сети S.

Лемма 1. Сеть без циклов содержит висячее ребро.

Лемма 2. Удаление висячего ребра с висячим узлом или ребра из цикла не нарушает связности сети.

Лемма 3. Сеть является деревом тогда и только тогда, когда она не содержит циклов.

Лемма 4. Любая пара узлов дерева связана единственной цепью.

Лемма 5. Пусть S* - дерево сети. Для любой дуги (i,j) U\U*, частичная сеть S1={I,U1}, U1=U* (i, j) содержит ровно один цикл.

Множество дуг U U сети S={I,U} называется полным, если хij=0, (i,j) U, но для любой дуги (i*, j*) U имеет ненулевое решение хij 0, (i,j) U (i*, j*) система I+i(U (i*, j*)) i I-i(U (i*, j*)) Проследим преемственность предлагаемого метода и симплекс-метода.

В симплекс-методе среди векторов условий а j, j=1,n канонической задачи мы выбирали базис - полную линейно независимую систему векторов, то каждого j* Jн уравнение а jхj +а j*хj*=0 имеет ненулевое решение.

Теорема. (критерий полноты множества дуг) В сети S={I,U}, множество U U является полным тогда и только тогда, когда S ={I, U} - дерево сети.

Поток х={хij, (i,j) U} называется базисным, если хij=0, (i,j) Uн=U\U, U - полное множество дуг. Дуговые потоки хij, (i,j) U и множество дуг U - базисные, остальные - небазисные. Базисный поток невырожден, если все его базисные дуговые потоки положительны.

3.3.2. Формула приращения стоимости потока.

Пусть U - базисное множество_ дуг и х - соответствующий базисный поток. Рассмотрим другой поток х=х+х. Найдем формулу приращения стоимости потока i I сети S={I,U}, припишем число u i (потенциал узла) так, чтобы совокупность {u i, i I} удовлетворяла системе уравнений Покажем, что искомые числа существуют. Выберем любой узел i1 I и положим u i1=0. По лемме 4 любой узел i I можно соединить с i единственной цепью {i1, i2,..., i k, i} дерева S ={I,U}. Рассматривая уравнения потенциалов вдоль дуг цепи, определим потенциал u i узла i.

Например, u i2=u i1-сi1 i2, если (i1, i 2) - прямая, u i2 = u i1+сi1 i2, если (i1, i2) обратная. Аналогично по u i2 вычисляем u i3 и так далее.

Имея потенциалы узлов, найдем оценки небазисных дуг:

Так как на потоках х=х+х и х выполняются условия баланса, то для приращений хij, (i,j) U дуговых потоков удовлетворяют равенствам Умножим обе части равенств (2), (3), на хij и просуммируем по (i,j) U:

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

Пусть х - базисный поток с базиным множеством дуг U; ij, (i,j) Uн соответствующие ему оценки, вычисленные по формуле (3).

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

хij = 0, если (i, j)(io, jo), (i,j) Uн, с любым значением >0 получается поток х, при этом при увеличении стоимость потока х неограниченно убывает. Задача не имеет решения.

Рассмотрим случай, когда наряду с отрицательной оценкой не все дуги вдоль цикла прямые. В этом случае на поток х можно наложить (io, jo)циркуляцию только с конечным значением. Поскольку с увеличением стоимость потока_ уменьшается, то нужно искать максимально возможное о. Из формулы хij=х ij+хij=хij-, которая имеет место для обратных дуг, соответствующих ребрам цикла, следует, что о=i*j*=х i*j*=min хij, где минимум вычисляется по всем обратным дугам цикла, построенного по Поток х заменим на поток х по следующему правилу: потoки на прямых дугах цикла (в том числе и на (io, jo)) увеличим на о, потоки на обратных дугах цикла уменьшим на о, остальные потоки оставим без изменения. При этом стоимость потока уменьшается на величину о iojo, которая положительна для невырожденного потока х, так как о >0.

Дугу (i*, j*) удалим из множества U, но добавим дугу (io, jo). Удаление дуги (i*, j*), на которой х i*j*=0, разрушает единственный цикл в сети {I,U (io, jo)}. Следовательно, частичная сеть S ={I,U} с U =U\(i*, j*) (io, jo) - дерево, а U - базисное _множество, соответствующее новому базисному потоку. Переход хх называется итерацией метода потенциалов. Метод потенциалов для невырожденных сетевых транспортных задач конечен.

Отметим, что дугу (io, jo) часто выбирают из условия iojo = max ij.

3.3.3. Первая фаза метода потенциалов Построение начального базисного множества дуг U называется первой фазой метода потенциалов. Часто U строится методом проб. Опишeм общий метод. К сети S={I,U} добавим искусственный узел n+1 с интенсивностью а n+1= (i,n+1), если i - источник или нейтральный узел; (n+1,i), если i - сток. В расширенной сети множество искусственных дуг - базисное, и потоки вдоль базисных дуг равны абсолютным значениям интенсивностей тех узлов исходной сети, которым эти дуги инцидентны. На расширенной сети дуговых потоков - задача первой фазы.

Проведем анализ решения (х*ij, (i,j) U; х*ij, (i,j) Uи) задачи первой фазы: а) если х*ij0, (i,j) Uи, то исходная сеть не допускает потока;

б) если х*ij=0, (i,j) Uи, и U* содержит единственную искусственную дугу, удалим эту дугу из U*, получив базисное множество исходной задачи и начальный базисный поток {х*ij, (i,j) U }; в) если х*ij=0, (i,j) Uи, и базисное множество U* содержит более одной искусственной дуги, то среди дуг (i,j) U\U* найдется такая (i*,j*), что цикл, построенный из U* и дуги (i*,j*), содержит две искусственных дуги, одну из этих дуг выведем из базиса, и вместо нее введем дугу (i*,j*) U, через конечное число шагов придем к случаю б).

3.3.4. Пример. Сетевая транспортная задача Найдем оптимальный поток на сети из 6 узлов, где узел 1 - источник, узел 6 - сток, а1=10, а6 =-10. Остальные узлы - нейтральные.

Характеристики сij помещены над дугами. Для рассматриваемой сети легко строится начальное базисное множество дуг - жирные линии на рисунке. Значения базисных дуговых потоков под дугами или справа от них. Так как небазисные дуговые потоки равны 0, то они не отмечаются.

Построим потенциалы узлов, положив u 4=0 (этому узлу инцидентно наибольшее количество базисных дуг). Остальные потенциалы найдем из уравнения (2). Потенциалы запишем возле узлов. По формуле (3) вычислим оценки небазисных дуг, и результаты поместим под ними или справа. Максимальная из оценок iоjо= 35=7. Дугу (3,5) добавим к базисному множеству дуг, что приведет к цикл {3, 5, 4, 2, 3}.

Минимальный дуговой поток на обратных дугах цикла о=х i*j*=х45 =0.

Следовательно, итерация сводится к замене базисной дуги (4,5) на дугу (3,5).

Максимальная небазисная оценка 12 =6. Результаты дальнейших вычислений помещены на следующем рисунке:

Поток на следующем рисунке удовлетворяет критерию оптимальности:

Компоненты потока хо: хо 12=10, хо24=10, хо46=10,остальные хоij=0.

Рассмотрим задачу о потоке минимальной стоимости на простой сети S={I, U}, в которой множество узлов I состоит из двух непересекающихся подмножеств I1 (источников) и I2 (стоков), то есть I1 I2 =I, I1 I2 =, а множество дуг U - из всевозможных дуг вида (i,j), i I1, j I2. В этих условиях более удобной является матричная (табличная) модель транспортных задач. Введем транспортную mхn-таблицу:

Строку i I1={1, 2,..., m} припишем пункту производства Аi, а столбец j I2 ={1, 2,..., n} пункту потребления Вj. Клетка (i,j) соответствует дороге из Аi в Вj. В верхнем углу клетки (i,j) поместим сij>0 - стоимость перевозки единицы продукта из Аi в Вj. Объем а i>0 производства поместим справа от строки, объем bj>0 потребления - снизу от столбца Вj.

В нижнем углу поместим перевозки хij. Условие баланса в узлах I сводится Теорема. Для существования плана перевозок матричной транспортной задачи необходимо и достаточно, чтобы выполнялось условие общего равнялся общему объему потребления.

Так как для любого плана перевозок х выполняются соотношения 00, (i,j) U.

Свойства базисного множества клеток: в каждом столбце и каждой строке есть базисная клетка; существует строка или столбец, в которой всего одна базисная клетка; удаление базисной клетки, единственной в строке (столбце) вместе со строкой (столбцом), приводит к уменьшенной транспортной таблице, для которой уменьшенное базисное множество является базисным; любую пару из строк и столбцов можно соединить единственной цепью из U; добавление клетки к U создает единственный цикл; если U – базисное множество клеток, то базисный поток имеет вид: хij =0, (i,j) Uн, отыщем базисную клетку (i1, j 1), единственную в строке i1 (столбце j1), положим хi1j1=а i1 (х i1j1=bi1), объем bj1 заменим на bj1-х i1j1 (а i1 на а i1-хi1j1) и строку i1 (столбец j1) исключим из рассмотрения, с уменьшенной таблицей повторим те же операции; через n+m-1 шаг будет построен базисный план.

Опишем два метода построения начальных базисных планов перевозок.

Метод минимального элемента. Среди элементов сij найдем минимальный сi1j1. Положим хi1j1=min{аi1, b j1}. Если хi1j1=аi1 (х i1j1=b j1), то исключаем из рассмотрения строку i 1 (столбец j1), а число bj1 (аi1) заменяем на bj1-х i1j1 (аi1-х i1j1). С уменьшенной таблицей повторяем все снова. Через n+m-1 шаг будет найдено n+m-1 числo хij. Для остальных клеток хij=0. Полученный план перевозок будет базисным.

Метод северо-западного угла. Для клетки (1,1) - северо-западный угол - положим х11=min{a1, b 1}. Если х11=а1 (х 11=b 1), то строку 1 (столбец 1) исключаем из рассмотрения, а число b1 (а1) заменяем на b1-х 11 (а1-х 11). В сокращенной таблице выбираем северо-западный угол, и все повторяем снова. Через n+m-1 шагов будет построен начальный базисный план.

Опишем метод потенциалов на языке транспортных таблиц. Пусть х базисный план перевозок с базисным множеством клеток U. Некоторой (любой) строке i1 (столбцу j 1) припишем число u i1 (v j1) - потенциал, по базисной клетке (i1, j1) из уравнения u i1+v j1=сi1j1 найдем vj1 (u i1). Зная потенциалы u i, v j, i=1,m, j=1,n вычислим оценки ij небазисных клеток по формуле ij=u i+vj-сij, (i,j) Uн. Неравенства ij (х-х*)`f(х*)/х.

Если функция f(х) С(2), х Rn, то она выпукла тогда и только тогда, когда неотрицательна матрица вторых производных 2f(х)/х2>0, х Rn.

Критерии Сильвестра: для положительности (неотрицательности) матрицы необходимо и достаточно, чтобы все ее последовательные главные миноры были положительны (неотрицательны).

Рассмотрим свойства выпуклых множеств.

Пересечение любого числа выпуклых множеств - выпуклое множество.

выпуклого множества для любых хi, i=1,k принадлежит этому множеству.

Теорема о строгой отделимости. Пусть Х, Y - выпуклые множества, одно из которых ограничено. Если их замыкания не пересекаются, то они строго отделимы, то есть при некоторых n-векторе с0 и числе для любых х Х, у Y выполняется с`х< 0. Введем прямую (х), х Q и двойственную (), >0 функции: (х)=sup F(х, ), >0; ()=inf F(х, ), назовем прямой, задачу - двойственной задачей ВП. Множество {х: (х)- } - множеством двойственных планов. Поскольку (х)=f(х), если х Х; (х)=, если х Х, то множество прямых планов совпадает с множеством планов задачи (1), а задача (3) - с задачей (1). В силу этого и задачу (1) называют прямой задачей ВП. В случае линейных функций f(х), g(х) и множества Q={х: х>0} задача (4) совпадает с двойственной задачей ЛП.

Решения хo, o задач (3), (4) удовлетворяют следующим соотношениям двойственности: для существования решения хo прямой задачи необходимо существование решения o двойственной задачи; на решениях хo, o задач (3), (4) выполняется (хo)=( o); для любой пары (х, ) из прямого и двойственного планов верно (хo)> ( o); если на некоторой паре (х*,*) из прямого и двойственного планов верно (х*)=(*), то х*, * - решения задач (3), (4); если вдоль некоторой последовательности k, k=1, 2,... (хk, k=1, 2,...) двойственных (прямых) планов целевая функция двойственной (прямой) задачи не ограничена, то пусто множество прямых (двойственных) планов; на решениях хo, o задач (3), (4) выполняется условие дополняющей нежесткости g` (хo) o =0; решение o двойственной задачи (4) представляет вектор Лагранжа, соответствующий оптимальному плану хo задачи (1); для того, чтобы векторы хo, o были решениями задач (3), (4) необходимо и достаточно, чтобы они были компонентами седловой точки функции (2); справедлива теорема о минимаксе: min max F(х, )=max min F(х, ).

Замечание. Из существования решения двойственной задачи (4) не следует существование решения прямой задачи (3). Так, прямая задача f(х)=х21+1/х2min, g(х)=х10}, х R не имеет решения, а двойственная ()=- 2/4max, >0 имеет решение o =0.

4.4. Решение одной задачи квадратичного программирования Рассмотрим задачу с положительной nxn-матрицей D и mxn-матрицей А, rank А=m0), то точка минимума х() совпадает со стационарной точкой функции Лагранжа F(х(),)/х=0, следовательно, с+Dх()+А`=0. Таким образом, Подставив (7) в (6), получим ()=-(с`+`А)D (А`+с)/2-`b. Двойственная к (5) задача состоит в максимизации функции (), R. Поскольку АD-1А`>0, то функция () строговогнута (-() - строговыпукла). Точка ее максимума o совпадает со стационарной точкой. Из (( o)/ ) =0, то есть АD-1(с+А` o)+b=0, следует Подставив (8) в (7), получим решение задачи (5).

4.5. Двойственная задача геометрического программирования Функция f(t), t={t1, t2,..., t m} назовем позиномом, матрица {аij, i=1,n, j=1,m} - ее матрица экспонент.

Геометрическим программированием (ГП) называют раздел математики, в котором исследуются задачи минимизации позиномов на множествах, заданных позиномными неравенствами.

Рассмотрим задачу ГП:

где f(t) - позином (9). Прологарифмировав функции u i и введя новые переменные хj=ln tj, j=1,m; х m+i =ln u i, bi=-ln сi, i=1,n, от (10) перейдем к задаче ВП с линейными ограничениями:

задача, двойственная к (11) имеет вид:

Опишем множество двойственных планов: {i: ()0, i=1,n. (16) Если строки матрицы экспонент образуют положительный базис (из i а ij=0, j=1,m; i>0, i=1,n, следует i=0, i=1,n), то задача (16) имеет единственный план i=0, i=1,n. Из теории двойственности ВП следует, что задача (10) решается тривиально: tj=0, j=1,m. Исключим этот тривиальный случай. В силу однородности ограничений задачи (16) ее i=1, i>0,i=1,n;>0. (17) Так как входит только в целевую j=1,m;

функцию, вычислив в (17) максимум по, при этом = получим задачу, эквивалентную (17):

Эта задача часто проще исходной, прямой задачи (10), при этом существует класс задач, для которых ограничениям задачи (18) удовлетворяет единственная совокупность { i, i=1,n}. В этих случаях максимизация в (18) излишняя.

Пример. Для перевозки через реку 400м3 гравия нужно изготовить открытый ящик размерами t1*t2*t3 (длина, ширина, высота). Боковые стенки и дно ящика изготавливаются из материала стоимостью 10 руб./м2, передняя и задняя стенки - из материала стоимостью 20 руб./м2. Каждый рейс стоит 10 коп. При каких размерах to1, to2, to 3 общие затраты будут минимальны, если после перевозки всего гравия ящик выбрасывается?

Решение. Объем ящика t1*t2*t3 м3. На перевозку 400м3 требуется 400/(t1*t2*t 3) рейсов, это стоит 40t1-1t 2-1t 3-1руб. Стоимость материалов на изготовление ящика равна 40t2t3+20t1t3+10t1t2. Математическая модель имеет вид: f(t)=40t1-1t 2-1t 3-1+40t2t3+20t1t3+10t1t2min, t1, t2, t 3>0, то есть m=3, n=4, с1=40, с2=40, с3=20, с4=10. Матрица Тогда ограничения задачи (18) имеют вид:

-1+3+4=0, -1+2+ 4=0, -1+2+ 3=0, 1+2+ 3+ 4=1. Полученная система имеет единственное решение (2/5, 1/5, 1/5, 1/5). Тогда минимальные затраты на перевозку гравия - значение двойственной целевой функции:(40/[2/5])2/5(40/[1/5])1/ (20/[1/5])1/5(10/[1/5])1/5=100 руб. Для вычисления to1,to2,to 3 воспользуемся соотношениями хm+i=ln u i; хo m+i=ln oi, i=i, o=(o), тогда u i(to)=(o)oi, i=1,n, следовательно, 100 2/5= 40t1-1t 2-1t 3-1, 100 1/5=40t2t3, 100/5=20t1t3.

Таким образом, оптимальные размеры ящика to1=2 м, to2 =1 м, to3 =0.5 м.

Часть 5. Теория нелинейного программирования Нелинейным программированием (НП) называют раздел математики, в котором исследуются задачи оптимизации функций на множестве конечномерного пространства.

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

Рассмотрим общую задачу НП:

Как и прежде будем использовать понятия: план х; оптимальный план хo;

целевая функция f(х). Будет говорить, что функция f(х), определенная на множестве Х, полунепрерывна снизу в точке х* Х, если limf(х)=(х*), при хх*, х Х, функция f(х) полунепрерывна снизу на множестве Х, если она полунепрерывна снизу в каждой точке Х. Множество {х: f(х)0.

Достаточное условие минимума можно ипользовать только для задач, локально оптимальные планы которых удовлетворяют соотношениям:

существует >0, что f(х*)0, то разделив на o функцию (3), получим функцию (5).

единственный вектор Лагранжа.

Нормальность оптимального плана х связана с поведением функции g(х) в точке хo.

План хo называется обыкновенным, если на нем линейно независимы векторы Теорема. Оптимальный план является нормальным тогда и только тогда, когда он обыкновенный.

Следствие. Если задача (1) - нормальная, то m0 неотрицательна квадратичная форма на гиперплоскости, заданной уравнениями l`gi(хo)/ х=0, i=1,m.

Теорема. (достаточное условие локальной оптимальности) Для локальной оптимальности в задаче (1) условно стационарной точки х* достаточно, чтобы при соответствующем ей векторе Лагранжа * была положительна квадратичная форма l`2F(х*,*)/х2l>0 на гиперплоскости, заданной уравнениями l`gi(х*)/х=0, i=1,m.

5.4. Минимизация функций при ограничениях типа неравенства