Линейное программирование. Симплекс-метод.

Осн понятия. Реш любой задачи прикладного хар-ра предполагает построения мат модели, описывающ дан процесс. Построение: 1) выбор переем 2) сост сист огранич 3) выбор целевой ф-и. Переменная задачи наз величина x1,.., xn, кот полностью характериз рассм процесс и запис в виде вектора x=(x1,.., xn). Сист ограничений, вкл в себя сист ур-й и нер-в, удовл переем задачи. Целевая ф-я – ф-я от переем, кот характеризует кач-во выпол зад и экстремуму кот надо найти. В общем виде задача линейного программирования м/б сформулирована как задача нахождения наибольшего значения линейной функции (1) на некотором множестве D Ì Rⁿ, где x Î D удовлетворяют сис­теме ограничений (2)и, возможно, ограничениям (1.3) В системе (1.2) пер­вые m ограничений являются неравенствами, а последующие — l -уравнениями. Относительно направ­ления знака неравенства будем предполагать, что левая часть меньше или равна правой. Добиться этого можно, умножив на (-1) обе части тех неравенств, которые имеют противопо­ложный знак. Ограничения (1.3), вообще говоря, могут быть рассмотрены как частный случай ограничений в форме нера­венств, но в силу особой структуры их обычно выделяют от­дельно и называют условиями неотрицательности. Канонич форма записи м/б представлена виде корд, векторной, матрич. 1) корд z(x)=c1x1+.+cnxn®max(min) сист a11x1+..+a1nxn=b1; am1x1+..+amnxn=bm. 2) векторная форма z(x)=(c1x)®max(min) сист A1x1+..+Anxn=A0; xj> =0; c=(c1,..cn)-вектор координат целевой ф-и,

векторы усл-й сист огранич.3) Матрич форма z(x)=cx® max (min) AX=A0; A=(aij); X> =0. Планом ЗЛП называется всякий вектор х из пространства Rⁿ.

Допустимым планом называется такой план ЗЛП, кото­рый удовлетворяет ограничениям (1.2)-(1.3), т. е. содержится в области D. Сама область D называется при этом областью допустимых планов. Оптимальным планом х^* называется такой допустимый план, при котором целевая функция достига­ет оптимального значения, т. е. план, удовлетворяющий условию max f(x) = f(x^*). Величина f^* = f(x^*) называется оптимальным значением целевой функции. Решением задачи называется пара (х^*, f^*), состоящая из оптимального плана и оптимального значения целевой функ­ции, а процесс решения заключается в отыскании множества всех решений ЗЛП. Переход к канонической форме. 1) ограничения в виде неравенств преобразуются в уравне­ния за счет добавления фиктивных неотрицательных переменных , которые одновременно входят в целевую функцию с коэффициентом 0, т. е. не оказывают влияния на ее значение; 2)Избавление от произвольно меняющихся перем: если xj – переем произв знака, то заменить разностью 2-х новых неотр перем. Xj=x^/j-x^//j. Графич интерпретация ЗЛП. Алгоритм: 1)строим ОДР 2) строим вектор нормали с корд (с1, с2) с т приложения в начале корд. 3) строим перпендикуляр к вектору нормали, проводим одну из линий уровня, напр, z(x)=0; 4) линия уровня перемещается до положения опорной пр. На этой опорной пр, если она сущ будет нах max, min целевой ф-и. Симплекс-метод - это метод целенаправленного перебора опорных решений, кот. за конечное число шагов позволяет либо найти оптимальное решение задачи, либо установить, что его не существует. Алгоритм симплекс-метода: 1. Привести ЗЛП к каноническому виду.2. Найти НОР с начальным базисом. Если НОР отсутствует (невозможно построить единичную подматрицу, при условии, что все ), то ЗЛП не имеет решений в виду несовместимости системы ограничений.3. Вычислить оценки разложения - вектор коэффициентов целевой функции при базисных переменных.4. Если выполняется признак единственности оптимального решения, то решение заканчивается. (Признак: Опорное решение ЗЛП на max (min) является оптимальным, если все оценки разложений векторов условий по базису данного решения неотриц.(неполож.)).5. Если выполняется условие существования бесконечного множества оптимальных решений, то путем простого перебора находят все оптим. решения. (ЗЛП имеет бесконечное множество оптим. решений, если среди оценок разложений векторов условий, не входящих в базис, есть хотя бы 1 оценка ).6. Если для какого-либо вектора условий с оценкой , противоречащей признаку оптимальности решения, среди коэффициентов разложения этого вектора по рассм-му базису нет «+» элементов (в симпелкс-таблице не удовлетворяют условию оптимальности, а элементы этого столбца «-» или =0), то ЗЛП не имеет опт. решения в виду неограниченности целевой функции.7. Если п.4-6 не выполняются, то находится новое опорное решение с использование следующего утверждения: Наибольшее изменение целевой функции при переходе от одного опорного решения к другому обеспечивается правильным выбором векторов, вводимых в базис и выводимых из него. Это можно осуществить в соотв. с условиями: На max: На min: и повторяются этапы, начиная с п.3 Теория двойственности Любой ЗЛП, кот. будем считать прямой или исходной, можно поставить в соответствие другую, кот. называется двойственная или сопряженная. Существуют общие правила составления двойственных задач: 1. Все ограничения исходной задачи должны содержать свободные коэффициенты в правой части, а коэффициенты с неизвестными в левой.2. Все ограничения неравенств исходной задачи д.б. одного знака, соотв-го типу задачи, т.е. < = в задаче на max и > = в задаче на min.3. Каждому ограничению исходной задачи соотв-ет нек-ая перем-ая в двойственной задаче, причем, если эта перем-ая соотв-ет нер-ву, то в двойственной зад. она будет неотриц., а если перем-ая соотв-ет рав-ву, то она м.б. любого знака.4. Целевая функция двойственной зад. имеет вид - свободный коэффициент функции z(x), - свободные коэффициенты в системе ограничений исходной зад., - перем-ые в двойственной задаче.5. Целевая функция двойств. зад. должна оптимизироваться противоположнымобразом:

6. Каждой перем-ой в исходной зад. соотв-ет ограничение в двойственной, причем, ограничение будет иметь вид нер-ва, если соотв-ая перем-ая и ограничение рав-во, если перем-ая любого знака. Знак нер-ва выбирается из усл-я max, либо min . Теоремы двойственности: Т1: Если одна из пары двойственных задач имеет оптим. реш-е, то и двойственная к ней также имеет оптим. реш-е, причем зн-я целевых функций на своих оптим. реш-ях совпадают. . Если одна из пары двойственных задач не имеет реш-е в виду несовместимости с-мы ограничений, то 2-я зад. не имеет реш-я в виду неограниченности целевой ф-ции, и наоборот.Т2: Для того, чтобы допустимые реш-я явл-сь оптим. реш-ями пары двойственных задач н. и д., чтобы вып-сь рав-ва:

Если при подстановке оптим. реш-я в с-му ограничений i-ое ограничение исходной зад. вып-ся как строгое нер-во, то i-ая координата оптимального реш-я двойственной задачи =0, и наоборот. Если i-я к-та оптим. реш-я двойств. зад. не =0, то i-ое ограничение исх. зад. вып-ся как равенство. Транспортные задачи Имеется m пунктов отправления A1,..Am, в кот. сосредоточен однородный продукт в количестве a1,.., am.A1,.., Am - поставщики. Этот продукт необходимо распределить между потребителями B1,.., Bn в соответствии с потребностями b1,.., bn. Известны транспортные расходы: Требуется составить такой план перевозок, при котором весь продукт вывозится в соответствии с потребителями и общая величина расходов будет min.

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