Любой 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. Минимизация функций при ограничениях типа неравенства