1. Предмет и задачи матпро. Постановка общей задачи МП. Матпро – это раздел матем-ки, в кот-ой разраб-ся числовые м-ды решения многомерных задач с ограничениями. Чтобы решить задачу матем. м-дами необходимо составить модель. Мат. модель – это с-ма матем. выражений, которая описывает хар-ки изучаемого объекта и взаимосвязи м/у ними. Матпро включает: ленейное пргр-е, динамическое прогр-е, целочисленное прогр-е, дробнолинейное прогр-е и т. д. Постановкой общей задачи МП: определить значение неизв-ых х1,х2,…хn, при которых выпол-ся ограничения gi(x1,x2,….xn) (<=,=, >=) bi(i=1,m)(1) и доставляется экстремум функции Z=f(x1,x2,…xn) –extr-(2) целевая функция или функция цели. Значение переменных (х1,х2,…хn) наз-ся решением задачи или планом. План удовлетворяющий ограничениям (1) наз-ся допустимым. Допустимый план, при котором значения достигают экстремума наз-ся оптимальным. Задачи МП: определение оптимального плана, опред-е оптимального объема выпуска продукции, опред-е оптим-го сочитания посевов с/хоз-ых культур, формир-е оптим-го пакета активов, максимиз-щий прибыль банка и т. д. Экономические примеры задач, решаемых методами МП. Компания имеет 2 склада и 3 оптовых покупателей. Запасы на складах составляют 120 и 180 тыс. ед., а потребность покупателей 70,140,90тыс. ед. Стоимость транспортировки 1тысячи продукции приведена в матрице {x11+x12+x13=120 {x21+x22+x23=180 {x11+x21=7 xiJ>=0 (i=1,2) (j=1,3) {x12+x2=140 {x13+x23=90 Предприятие может производить 2 вида продукции(П1,П2), используя для этого 3вида ресурсов сырье, оборудование и труд.
Определить оптим. план выпуска продукции. Обозначим х1,х2 количество продукции П1 и П2 в оптимальном плане. Прибыль опишется функцией: f= 35x1+49x2 – max 1x1+3x2<=210} 3x1+2x2<=210} 3x1+x2<=180 } x1>=0,x2>=0 | 2. Различные формы записи ЗЛП (общая, каноническая, симметрическая) Задачи МП: определение оптимального плана, опред-е оптимального объема выпуска продукции, опред-е оптим-го сочитания посевов с/хоз-ых культур, формир-е оптим-го пакета активов, максимиз-щий прибыль банка и т. д. Общей ЗЛП называют задачу максимизации (минимизации) линейной функции f=Уcj*xj-max(min) (1) при линейных ограничениях ∑aij *xj{=<,=,>=}bi (i=1,n) (2) при условии xj>=0(j=1,n1), xj-произвольное (j=n1+1,n )(3) где cj, aij, bi-постоянные числа. Симметрической формой записи ЗЛП наз-ся задача максимизации функции (1) при линейных ограничениях в неравенствах со знаком < либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком > либо = и неотрицательных переменных. Канонической формой записи ЗЛП наз-ся задача максимальной функции (1) при линейных ограничениях равенствах и неотрицательных переменных. Любая другая форма называется смешенной. min f(x) = - max(-f(x)) Преобразование нерав-ва в уравнение и наоборот осущ-ся на основе Леммы: всякому решению х1…хn нерав-ва a1x1+…+anxn<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>=0(7) и наоборот. Всякому решению x1…xn, xn+1 уравнения 6 и неравенства 7 соответствует решение x1…xn неравенства 5. Чтобы от зад сим формы перейти к зад канонич вида, необходимо ввести балансовые (выравнивающие) переменные. Это основано на теореме о неравенстве: любое нерав-во можно представить в виде ур-я или простейшего нерав-ва. | 3. Геометрическая интерпретация целевой функции и ограничения ЗЛП. Геометрическая формулировка ЗЛП. Пусть дана задача f=c1x1+c2x2-max (1) a11x1+a12x2<=b1 } am1x1+am2x2<=bm} x1>=0, x2>=0 (3) План задачи (х1,х2) – точка на плоскости. Каждое неравенство с-мы 2 предст. собой полуплоскость. Полуплоскость –выпуклое множество. Выпуклым наз-ся множество в которым точки отрезка соединяющие (х1 и х2) принадлежащие этому множеству то же принадлежат множеству. С-ма 2 представляет собой пересечение полуплоскастей. При пересечении могут получиться: 1)выпуклая многоугольная замкнутая область. 2) выпуклая открытая многоугольная область 3) единственная точка 4) пустое множество 5) луч и отрезок Геометрическая интерпретация целевой функции: ф-ция 1 представляет собой семейство параллельных прямых, которые наз-ют линиями уровня(линиями постоянного значения целевой функции). Частные производные функции по х1 и х2 показывают скорость возрастания целевой функции вдоль координат осей. Вектор-градиент показывает направление найскорейшего возрастания целевой функции. Для задачи 1-3 вектор-градиент = (с1;с2) Выходит из точки (0,0) и направлен в точку с координатами (с1;с2). Вектор-градиент перпендикулярен линиям уровня. Пересечение полуплоскастей принято наз-ть областью допустимых рещений(ОДР). | ||||||||||||||||||||
4. Графический метод решения ЗЛП. Графический способ целесообразно использовать для решения задач с двумя переменными, записанных в симметричной форме, а также для задач со многими переменными при условии, что в их канонической записи содержится на более двух свободных переменных. Порядок решения ЗЛП графическим способом: 1. Построить ОДЗ; 2. Построить вектор С; 3. Перпендикулярно С построить линию уровня f=0; 4. Перемещая линию уровня в градиентном направлении найти точку максимума или минимума ОДЗ; 5. Найти координаты точки максимума (минимума) и значение функции в этой точке. В ходе решения ЗЛП граф. способом могут получаться след. результаты: 1. Оптимальный план единственный: линия уровня и ОДЗ в крайнем положении имеют одну общую точку; 2. Оптимальных планов бесконечное множество: в разрешающем положении линия уровня проходит через грань ОДЗ; 3. Задача не имеет решения: ОДЗ=ш; 4. Целевая функция не ограничена, в этом случаи добавляется еще одно ограничение. Граф. способом можно решать задачи с большим чем 2 количественных переменных. Если в канонической форме задачи разность м/у количеством линейно-независимых уравнений (r ) и количеством переменных n ровна 2. Для решения такой задачи: 1. преобразуют модель к симметрической форме, в результате получается задача ЗЛП с двумя независимыми; 2. решить ЗЛП граф. способом; 3. координаты точки экстремума подставить в уравнение канонич. записи и найти значение остальных переменных. | 5. Опорные планы ЗЛП. Соответствие между опорными планами и вершинами многогранника планов. Рассмотрим задачу: F=c1x1+c2x2+cnxn-max (1) a11x1+…a1nxn<=b1 } am1x1+…+amnxn<=bm } (2) xj>=0, ( j=1,n) (3) Чтобы задача 1-3 имела решение (2) должна быть совместной и иметь неотрицательное решение. Это возможно если число линейно-независимых уравнений с-мы ( r ) не больше числа переменных (r<=n). При r=n –с-ма имеет единст. решение; r<n с-ма имеет бесконечное множество решений. Множество векторов а1 и …an будет содержать линейно-независимую подсистему векторов (базис), состоящую из n-векторов. Предположим, что вектор a1..am линейно-независимы, тогда общее решение с-мы (2) может быть получено путем размещения ее относительно переменных х1…хm (базисных переменных). Хi=Bi0-(n-m;J=1)УBij*Xj+m ( i=1,m ) (4) Подставим Xi в целевую функцию, получим F= Boo-(n-m; j=1)УBoj*Xj+m (5) Базисное решение получается путем подстановки вместо переменных Xj+m (j=1,n-m) нулей. Переменные, которые стоят в правой части (4) наз-ся свободными. Если в базисном решении значение всех базисных переменных неотрицательное, решение наз-ся опорным. Каждому опорному плану (1-3) соответствует вершина многогранника плана и наоборот, каждой вершине многогранника плана соотвтствует опорный план задачи 1-3. Опорных планов задачи 1-3 не более, чем число сочетаний из m по n, поэтому выбирая все опорные планы можно определить тот, для которого целевая функция принимает экстремальные значения. 6. Основная теорема ЛП. Принципиальная схема решения ЗЛП, вытекающая из этой теоремы. Если ЗЛП имеет решение, то целевая функция достигает экстремального значения хотя бы в одной из крайних точек многогранника плана. Если целевая функция достигает экстремального значения более чем в одной крайней точке то она достигает одно и то, являющейся их выпуклой линейной комбинацией. же значения в любой точке. При решении ЗЛП в ручную удобно использовать табличную запись.
| 7. Симплексный метод решения ЗЛП. Общая идея симплекс-метода. Одним из универсальных методов явл-ся симплесный метод. В симплексном м-де осущ-ся направленный перебор опорных планов, в том смысле, что при переходе от одного опорного плана к другому целевая функция возрастает. Пусть задача записана в канонической форме: f=(n; j=1)УCj*Xj (max) (n;j=1)Уaij*xj=aio (i=1,m) Xj>=0 (j=1,n) Если задача разрешима, то ее оптимальный план совпадает по крайней мере с одним из опорных решений с-мы уравнений. Именно этот опорный план и отыскивается симплекс-методом в результате упорядоченного перебора опорных планов. Упорядоченность понимается в том смысле, что при переходе от одного опорного плана к другому соответствующие им значения целевой функции возрастают. Поэтому симплекс-метод наз-ют м-дом последовательного улучшения плана. Общая идея симпл. метода состоит в том что симпл. м-д разбивается на 2 этапа: 1. нахождение начального опорного плана; 2. последовательное улучшение вплоть до нахождения оптимального, в котором целевая функция достигает максим. значения. 8. Признак оптимальности опорного плана ЗЛП. Признак опорного плана явл-ся неотрицательность элементов столбца свободных членов, не считая элементов f-строки. Признаком оптимального плана - если в симплексной таблице содержится опорный план, все элементы f-строки, которые неотрицательны (не считая свободного члена bоо), то этот опорный план является оптимальным. Если в соотношении f=boo-(n-m;j=1)Уboj*Xj+m значение всех свободных переменных равно нулю, то целевая функция будет равна свободному члену f(векторXo)=boo. При увеличении значений свободных переменных функция начнет умен-ся, следовательно при плане Хо функция принимает экстремальное значение. |
. Определить план при транспортировки, при котором суммарные затраты минимальные. А1, А2 –склад, В1,В2,В3 –потребители. Обозначим ч/з хij-количество продукции, перевозимое со склада Аi(i=1,2) потребителю Bj(j=1,3). Затраты на транспортировку могут быть описаны функцией. f=8x11+5x12+6x13+4x21+9x22+7x23 –min9. Нахождение начального опорного плана ЗЛП. Для нахождения начального опорного плана можно предложить следующий алгоритм: 1. записать задачу в форме жордановой таблицы так, чтобы все элементы столбца свободных членов были неотрицательными, т. е. выполнялось неравенство аio>=0 (i=1,m). Те уравнения с-мы, в которых свободные члены отрицательны, предварительно умножаются на -1. 2.
Таблицу преобразовывать шагами жордановых исключений, замещая нули в левом столбце соответствующими х. При этом на каждом шаге разрешающим может быть выбран любой столбец, содержащий хотя бы один положительный элемент. Разрешающая строка определяется по наименьшему из отношений свободных членов к соответствующем положительным элементам разрешающего столбца. Если в процессе исключений встретится 0-строка, все элементы которой - нули, а свободный член отличен от нуля, то с-ма ограничительных уравнений решений не имеет. Если же встретится 0-строка, в которой, кроме свободного члена, других положительных элементов нет, то с-ма ограничительных уравнений не имеет неотрицательных решений Если с-ма ограничительных уравнений совместна, то через некоторое число шагов все нули в левом столбце будут замещены х и тем самым получен некоторый базис, а следовательно, и отвечающий ему опорный план. | 10. Нахождение оптимального опорного плана ЗЛП. Начальный опорный план Хо исследуется на оптимальность. Если в f-строке нет отрицательных элементов (не считая свободного члена), - план оптимален. Если в f - строке нет также и нулевых элементов, то оптимальный план единственный; если же среди элементов есть хотя бы один нулевой, то оптимальных планов бесконечное множество. Если в f-строке есть хотя бы один отрицательный элемент, а в соответствующем ему столбце нет положительных, то целевая функция не ограничена в допустимой области. Задача не разрешима. Если в f - строке есть хотя бы один отрицательный элемент, а в каждом столбце с таким элементом есть хотя бы один положительный, то можно перейти к новому опорному плану, более близкому к оптимальному. Для этого столбец с отриц-ом элементом в f-строке берут за разрешающий; опред-ют по минимальному симплексному отношению разрешающую строку и делают шаг жорданова исключения. Полученный опорный план вновь исследуется на оптимальность. Это повторяется до тех пор, пока не будет найден оптимальный опорный план либо установлена неразрешимость задачи. 11. Признак неограниченности целевой функции на множестве планов и геометрическая иллюстрация. Признаком неограниченности целевой функции является получение в процессе поиска оптимал-го плана столбца с отрицательном элементом в f-строке, не содержащего ни одного положит. элемента. | 12. Признак бесконечности множества оптимальных планов и геометрическая иллюстрация. Признаком бесконечности множ-ва планов явл-ся наличие в f-строке симплексной т-це, содержащей оптимал. план, хотя бы одного нулевого элем-та не считая свободного члена. Пусть найден оптим. план Х1*, при чем в f-строке один нулевой элемент. Другой оптим. план Х2* можно найти, выбрав в качестве разреш-го столбец с нулевым элементом в f-строке. Остальные оптим. планы можно определить как линейную комбинацию: Х1*= лХ1*+(1-л)Х2* 0=<л<=л 13. Признак неразрешимости ЗЛП и геометрическая иллюстрация. При нахождении базисного решения начальный опорный план может не выделиться. В этом случаи необходимо построить начальный опорный план по след. правилам: 1. записать с-му уравнений канонич. Формы задачи в виде 0-равенств. Свободные члены должны быть неотрицательными. 2. записать полученную с-му в симплексную таблицу. 3. В качестве разреш-го столбца выбир-ся столбец, содер-й хотя бы один положит. элемент. Разреш-ая строка выбир-ся по наименьшему симплексному отношению. Относительно разр-го элемента проводится симпл-ое преобразование: переводит одну свободную переменную в базис. Разреш-ие столбцы в след. симпл-ую таблицу можно не вписывать. После того, как в левом заглавном столбце все нули будут заменены на переменные, т. е. опорный план найден, необходимо продолжить поиск оптимального. Признаком несовместимости с-мы ограничений явл-ся получение в процессе отыскания опорного плана 0-строки с положительным свободным членом и неположит. элементами этой строки. |
14. Алгоритм симплекс-метода. 1. привести модель задачи к канонической форме; 2. найти начальный опорный план; 3. записать задачу в симпл. таблицу; 4. если содержащейся в таблице план явл-ся оптимальным выписывается ответ. Если нет, то выполняется следующий пункт; 5. прперейти к новому опорному плану, к новой симп. таблице. Для того чтобы перейти к новому опорному плану достаточно заменить одну базисную переменную свободной. Переменную, включаемую в базис и соответствующей ей разрешающий столбец определяют по наибольшему по модулю отрицательному элементу f-строки. Переменную, исключающую из базиса и соответствующую ей разрешающую строку определяют по наименьшему симплексному отношению, т. е. отношению элементов единичного столбца к соответствующему элементу разрешающего столбца. Симплексное отношение – величина неотрицательная. На пересечении разрешающей строки и разрешающего столбца расположен разрешающий элемент, относительно которого выполняется симплексное преобразование по след. правилу: 1. элементы разрешающей строки делятся на разрешающий элемент; 2. элементы разрешающего столбца делятся на разрешающий элемент и меняют знак на противоположный; 3. остальные элементы таблицы перещитываются по правилу прямоугольника.: bij bis bkj=(bkj*bis-bij*bks)/bi bkj bks | 15. Понятие двойственности в ЛП. Симметричные двойственные задачи и их экономическая интерпретация. К любой задаче ЛП можно построить др задачу, тесно связ с усл-еи исходной задачи. При чем решая одну из них автом-ки получаем реш-е для др задачи. За исх задачу можно принимать любую из 2ух. Она наз прямой, а 2ая – двойственной. Дадим экономическую интерпретацию пары двойственных задач. Рассмотрим задачу рационального использования ресурсов. Пусть предприятие располагает ресурсами b1,b2,…bm, которые могут использ-ся для выпуска n-видов продукции. Пусть также известны стоимость единицы j-вида продукции cj (j=1,n) и норма потребления i-го ресурса (i=1,m) на производство единицы j-й продукции – aij. Требуется определить объем производства продукции каждого вида xj (j=1,n), максимизирующий суммарную стоимость f= c1x1+…+cnxn (1) При этом расход ресурсов не должен превышать их наличия: a11x1+…+a1nxn<=b1 } …………………….. } (2) am1x1+…+amnxn<=bm } Все известные по своему экономическому смыслу неотрицательны: Xj>=0 (j=1,n). (3) Заметим, что это задача образуют симметричную двойственную задачу. | 16. Несимметричные двойственные задачи. Связь между элементами моделей задач двойственной пары. Соответствие между переменными двойственных задач. Возьмем ЗЛП на максимум в канонической форме: Max Z=(n;j=1) Уcj*xj (n;j=1) Уaij*xj=bi (i=1,m) Xj>=0 (j=1,n). В пару взаимнодвойственных симметричных задач f=(n;A=1) Уcj*xj – max P= (m;i=1)Уbi*xi – min (n;j=1)Уaij*xj<=bj i=1,m (m;i=1) Уaij*yi>=cj j=1,n Xj>=0, j=1,n yi>=0 i=1,m Вводим дополнительные переменные и приводим их к каноническому виду: f=(n;j=1)У - max P= (m;i=1)Уbi*xi –min (n;j=1)Уaij*xj+xn+1=bi i=1,m (m;i=1)Уaij*yi-ym+y=cj j=1,n Xj>=0 j=1,n yi>=0, i=1,m Xn+1>=0 i=1,m ym+j>=0 j=1,n Между переменными прямой двойственной задачи можно установить соответствие: Х1 X2 … Xn Xn+1 Xn+2 … Xn+m Уm+1 Ym+2 … Ym+n Y1 Y2 … Yn Это соответствие можно сформировать словесно: основным переменным исходной задачи ставятся дополнительные переменные двойственной задачи, а дополнительным переменным исходной ставятся в соответствие основные двойственные. |
17.теорема двойственности. Нах оптим плана двойств задачи по решению прямой Т. Двойственности:1)для разрешимости 1 из двойств задач необх и дост чтобы каждая из задач имела хотя бы 1 решение 2)чтобы планы x=(…), u=.. явл оптимальными решениями пары двойств задач, необх и дост чтобы вып равенство Сумма(j=1, n) CjXj=Сумма(i=1,m) BiUi Прямая задача: сколько и какой продукции xj(j=1,n) надо произвести, чтобы при заданных стоимостях единицы продукции сj, объёмах имеющихся ресурсов bi и нормах расходов aij максимизировать выпуск продукции в стоимостном выражении? Двойственная задача: какова должна быть оценка единицы каждого из ресурсов yi, чтобы при заданных bi, ci, aij минимизировать общую оценку затрат на все ресурсы? ПРИМЕР: построить двойственную задачу к предложенной: maxZ=100x1+110x2+120x3 0,7x1+0,7x2+0,7x3<=700 0,3x1+0,3x2+0,2x3<=300 0,2x2+0,3x3<=150 X1>=0, x2>=0, x3>=0 Решение: minf=700y1+300y2+150y3 0,7y1+0,3y2>=100 0,7y1+0,3y2+0,2y3>=110 0,7y1+0,2y2+0,3y3>=120 Y1.=0, y2>=0, y3>=120 Y1>=0 y2>=0, y3>=0. 18.Теорема об оценках и ее эконом. интерпритация. Теорема (об оценках): двойственные оценки показывают приращение функции цели, вызванное малым изменением свободного члена, соотв. ограничения двойственной задачи. yi*= Дf max /Д bi i=1, m или yi*=(f max)’ bi Д f max = Дbi yi* если Д bi=1, то Дf max = yi* следовательно стоимост. оценка рес-са показ-т, как изменится выручка, если кол-во рес-са увелич-ся на 1 ед. | 20.Формул-ка и матем. модель трансп. задачи(ТЗ) по критерию ст-ти. Особ-ти модели как ЗЛП. У m поставщиков А1, А2, …, Аm имеется a1, a2, …,am единиц однородного груза, к-рый д. б. доставлен n потребителям В1, В2, …, Вn в кол-вах b1, b2,…,bn. Известна стоимость(Cij) доставки ед-цы груза из пункта Ai в пункт Bj (j=от 1 до m). Необх-мо найти такой план транспорт-ки прод-ии при к-ром суммарные затраты минимальны. Обозначим ч/з xij объем перевозки груза из i-го пункта в j-ый (i=от 1 до m; j=от 1 до n). Тогда матрица X=(xij)m*n и есть план транспортировки груза Удельные трансп. издержки запис-ся в форме матрицы С=[cij]m *n и наз-ся она матрицей тарифов. Экономико-матем. модель ТЗ должна отражать все условия и цель задачи в математич. форме. Переменные xij(i=от 1 до m;j=от 1 до n) должны удовлетворять ограничениям по запасам, потребностям и условиям неотрицательности: xij>=0 (i=от 1 до m; j=от 1 до n)(2) Цель ТЗ – минимизировать общие затраты на реализацию плана перевозок, к-рые можно представить функцией f=c1.1 x1.1+c1.2 x1.2+…+c1.n x1.n+…+cm.1 xm.1+cm.2 xm.2+…+ cm. n xm. n =(i=от 1 до m)У(j=от 1 до n)Уcij xij. (3) Математически ТЗ ставится так. Даны система ограничений (1) при условии (2) и линейная функция (3). Требуется среди множ-ва решений системы (1) найти такое неотрицат. решение, при к-ром линейная функция (3) принимает min значение. План перевозок X=(xij)m*n называется допустимым, если он удовлетворяет ограничениям (1) и (2). Допустимый план перевозок, доставляющий минимум целевой функции (3), наз-ся оптимальным. Теорема: для того чтобы ТЗ имела допустимые планы, необходимо и достаточно выполнение равенства
Если равенство не выполняется, в задачу вводится фиктивный поставщик или потребитель. При > - фикт потр-ль, при < - фикт поставщик. | 21. ТЗ с открытой и закрытой моделью. Преобразование открытой модели в закрытую модель. Модель ТЗ наз-ют закрытой, если суммарный объем груза, имеющегося у поставщиков, равен суммарному спросу потребителей, т. е. выполняется равенство
Для разрешимости ТЗ с открытой моделью необходимо преобразовать ее в закрытую. Так, при выполнении первого условия необходимо ввести фиктивный (n+1)-й пункт назначения Bn+1, т. е. в матрице задачи предусматривается дополнительный столбец. Спрос фиктивного потребителя
а все тарифы – одинаковыми, чаще всего равными нулю, т. е. C i, n+1=0 (i=от 1 до m). Аналогично при выполнении 2 условия вводится фиктивный поставщик, запас груза у которого равен
А тарифы дополнительной строки распределительной таблицы равны нулю, т. е. C m+1,j =0. (j=от 1 до n) При преобразовании открытой задачи в закрытую целевая функция не меняется, так как все слагаемые, соответствующие дополнительным перевозкам, равны нулю. |
(1)
(4)
(4) Если равенство не выполняется (< или >), то модель наз-ют открытой.
22.Интервал устойчивости двойственных оценок. Двойственные оценки справедливы в допустимом интервале устойчивости, к-рый для ресурса pl, l=1,m имеет вид [bl+Дbl ; bl+Дbl ] , где Дbl – нижний придел уменьшения соответствующего рес-са; Дbl – верхний предел увеличения. Эти величины (придел измен-ия колич. рес-сов) опред-ся по матрице обратной к матрице коэф-тов ограничений. По формулам
23. Теорема о ранге матрицы системы ограничительных уравнений ТЗ и ее прикладное значение. Теорема: Ранг матрицы А трансп. задачи на единицу меньше числа уравнений: r(A)=m+n-1. 24. Циклы в транспортной таблице. Свойства циклов. Циклом в транспортной таблице называют набор клеток, в к-ром две и только две соседние клетки расположены в одной строке или одном столбце и последняя клетка набора лежит в той же строке или столбце, что и первая. Упомянутый набор клеток можно записать в виде
Графическим изображением цикла является замкнутая ломаная линия (контур), звенья которой расположены только в строках и столбцах таблицы. Каждое звено соединяет две и только две соседние клетки цикла. Вершины цикла помечаются знаками «+» и «-» поочередно, начиная со свободной клетки. Таким образом, план ТЗ является опорным тогда и только тогда, когда из занятых им m+n-1 клеток нельзя образовать ни одного цикла. | 25. Способы построения нач опорного плана ТЗ (Наимен Эл-та, северо-зап угла, Фогеля) Опорный план можно построить несколькими способами. Правило «северо-западного угла». Суть сост в том, что 1ой загружается левая верхняя клетка (1.1). а затем двигаемся от нее по строке вправо или по столбцу вниз. В клетку (1.1) занесем меньшее из чисел а1, в1. Если закрывается строка, то след загружается клетка (2.1); если же закр-тся столбец, то след загружается клетка (1.2). Итак, каждый раз загружается клетка, соседняя либо по строке, либо по столбцу. Последней будет загружена клетка (m;n). В результате загруженные клетки расположатся вдоль диагонали (1;1) – (m;n), поэтому способ «северо-западного угла» называют еще диагональным способом. Способ «минимального элемента». Суть: 1ой в табл загружается клетка с наимен тарифом. В клетку запис-ся max возмо знач-е поставки. Затем из рассмотрения исключают строку, соответств-ю поставщику, запасы кот полностью израсх, или столбец, соответств-й потр-лю, спрос кот полностью удовлетворен. Из оставшихся клеток табл снова выбирают клетку с наимен тарифом. Процесс распред-я заканчивается, когда все запасы поставщиков исчерпаны, а спрос потр-лей полностью удовл. В рез получаем опорный план, котй должен содержать m+n-1 загруженых клеток. В процессе заполнения таблицы могут быть одновременно исключены строка или столбец. Так бывает, когда полностью исчерпывается запас груза и полностью удовлетворяется спрос ( вырожденная задача). В этом случае в свободные клетки надо записать число 0 – «нуль-загрузку», условно считая такую клетку занятой. Однако число 0 записывается в те свободные клетки, к-рые не образуют циклов с ранее занятыми клетками. Метод «Фогеля». Суть: по строкам и столбцам опред-ся разность между 2мя наимен тарифами. Из этих разностей выбир-ся наибольшая и в соответствующей строке (столбце) загружается клетка с наимен тарифом. Закрывающаяся строка (столбец) исключ-ся из дальнейшего рассмотрения. Описанная операция повторяется m+n-1 раз. Если наиболразность окаж-ся сразу в нескольких строках (столбцах), то выбир-т ту строку (столбец), в к-рой придется загружать клетку с наимен тарифом. Если и эти показ-ли будут одинак, то выбирают клетку, в к-рую придется записать большую поставку. | 26+27+28. Признак оптим-ти опорного плана. Оценка свободной клетки трансп. таблицы. процедура преобраз-я опорного плана ТЗ в новый опорный план. В соответствии с теорией двойственности, если xij*=0, то ui+vj<=cij, т. е.разность
Чтобы осуществить переход от одного опорного плана к другому необходимо загрузить перспективную клетку. Для этой клетки составляется цикл. Нужно доказать, что для каждой свободной клетки трансп. таблицы, содержащей опорный план, сущ-ет цикл, причем только единственный. Вершины цикла помечаются знаками «+» и «-» поочередно, начиная со свободной клетки. Далее выбир-ся наименьшая из загрузок клеток, отмеченная «-». Она обозначается |
dkl>0
dkl<0
- наз-ся оценкой свободной клетки и ее величина показ, как измен-ся общая ст-ть перевозок, если по маршруту (ij) провести единицу груза. Таким образом признаком оптимальности опорного плана ТЗ является неотрицательность оценок свобод. клеток. Если среди оценок есть отриц-ые, то чтобы уменьшить общую ст-ть перевозов нужно загрузить первую очередь клетку с наибол по модулю отрицат оценкой. Такую клетку наз-ют перспективной. Если в распределит-ой таблице, содержащей оптим. план, имеются своб клетки с нулевыми оценками, то задача имеет не единственный оптим. план. Загружая свободную клетку с нулевой оценкой, можно найти еще один оптим. опорный план. И так для каждой свободной клетки с нулевой оценкой.
число л добавляется к загрузке клеток, помеченных «+», и вычитается из загрузки клеток, отмеченных «-». Клетка по к-рой выбрано число л освобождается. Если освобождается одновременно несколько клеток, то свободной остается та, в к-рой наибольший тариф. В остальные освободившиеся вписывается загрузка 0.29. Потенциалы поставщиков и потр-лей, их вычисление и экон. смысл. Пусть дана модель ТЗ закрытого типа. Построим модель двойственной к ней задачи. f= (i=от1 до m)У(j=от 1 до n)Уcij xij →min (j=от 1 до n)У xij = ai i=от1 до m ui (i=от1 до m) Уxij = bj j=от1 до n vj xij>=0 i=от1 до m ; j=от1 до n Двойственная задача F=(i=от1 до m)У ai ui + (j=от1 до n) Уbj vj → max ui – произвольное, i=от1 до m vj – произвольное, j=от1 до n ui+vj <= cij Каждому пост-ку ставится в соответствие ui. Каждому потребителю ставится в соответствие vj. Эти потенциалы характ-т возможность пост-ков и потребителей изменять величину общих зат-т, меняя величину запасов и спрос. Из второй теоремы двойственности следует, что каждому xij*>0 соотв-ет равенство ui+vj=cij (1). Таким образом чтобы определить значение потенциалов, необходимо для каждой загруж-й клетки составить уравнение типа (1). В полученной таким образом системе будет m+n-1 уравнений и m+n неизвестных. Чтобы найти частное решение одну любую переменную приравнивают к любому произвольному числу. Тогда значение остальных переменных определяется однозначно. 30.Связь между оценками св клеток и потенциалами. Разность
| 31. Алгоритм метода потенциалов. 1. Проверить, выполняется ли для задачи рав-во 2. Условие задачи записывается в форме транспорт. таблицы 3. Строится начальный опорный план 4. Определяются потенциалы пост-ков и потреб-лей 5. Вычисляются оценки свободных клеток. Если все они не отрицательные – план оптимальный и нужно выписать ответ. Матрицу перевозок Х и определить величину затрат на транспортировку. Если план не явл-ся оптимальным, т. е.среди оценок есть отриц-ые, то выбир-т перспективную клетку с наибольшей по величине отриц. оценкой и переходят по величине к след. 6. Загруж-т перспективную клетку. Оформл-т нов. опорн. план в виде трансп. таблицы. Переходят к пункту 4. 32.Основное неравенство теории двойственности: для любых допустимых планов x и y пары взаимнодвойственных задач справедливо неравенство z(x)<=f(y). Его экономическое содержание состоит в том, что для любого допустимого плана производства x и любого допустимого вектора оценок y общая созданная стоимость не превосходит суммарной оценки ресурсов. Критерий оптимальности Канторовича (достаточный признак оптимальности): если для некоторых допустимых планов x* и y* являются оптимальными планами соответствующих задач. Экономический смысл критерия следующий: план проихводства X и вектор оценок ресурсов Y являются оптимальными, если цена всей произведенной продукции и суммарная оценка ресурсов совпадают. 33.Теорема существования оптимальных планов пары двойственных задач: для существования оптимального плана любой из пары двойственных задач необходимо и достаточно существования допустимого плана для каждой из них. | 34. 1ая теорема двойственности. если одна из двойственных задач имеет оптим план, то и другая решима, т. е. имеет опт. план. При этом экстремальные значен. целевых функций совпадают (j=от 1 до n) Уcjxj*= (i=от 1 до m)Уbiyi* если в исходн. задаче целевая функция неограничена на множестве планов, то в двойственной задаче система ограничений несовместна. 35. 2ая теорема двойств-ти и ее экон. интерпритация. Для того, чтобы допустимые решения пары двойственных задач были оптимальными, необходимо и достаточно выполнение условия: xj*(∑aij yi*-cj)=0, j от 1 до n, yi*(∑aij xj*-bi)=0, I от 1 до m. Это условия дополняющей нежесткости. Из них следует: если какое-либо ограничение двойств. задачи обращ-ся оптималь. планом в строгое равенство, то соответствующая компонента опт. плана двойственной задачи должно равняться нулю. Если же какая-то компонента опт. плана равна нулю, то соответствующее ограничение двойств. задачи обращается опт. планом в строгое равенство хj*>0 следовательно (i= от 1 до m)Уaij yi*=cj (затраты на пр-во продукции=цене) – Если продукция вошла в опт. план, то если затраты>цены, объем пр-ва=0 Уaij yi* >cj следовательно xj*=0 yi*>0 следовательно (j=от 1 до n) Уaij xj*=bi (рас-ды рес-ов =запас рес-ов). (j=от 1 до n) Уaij xj* <bi следовательно yi*=0 Смысл теоремы сводится к следующему: -если стоимост. оценка рес-ов расход-х на пр-во ед. прод-ии=цене, то этот вид прод-ии входит в оптим. план ; -если затраты превышают цену, то прод-ию производить не следует; - еслирасход рес-ов=запасу, то стоимост. оценка этого рес-са положительна. Такой рес-с наз-ся дефицитным. Наибелее дефицит. рес-с обладает наибольшей оценкой; -если рес-с израсходован неполностью, то его стоимост. оценка = 0. |
- наз-ся оценкой свободной клетки Если в опт плане есть своб клетки с отриц оценками, то из них выбирается клетка с макс по модулю оценкой(перспективная) и загружается макс возможной поставкой. Чтобы загрузить перспективную клетку, нужно составить для нее цикл. Он существует, причем единственный. Вершины его отмечаются знаками + и – поочередно, начиная с перспективной клетки. Далее выбирается наименьшая загрузка клетки, отмеченной минусом. Это число(л) добавляется к загрузке клеток, отмеченных +, и вычитается от тех, что отмечены -. Эта процедура называется сдвиг л по циклу. В рез-те загружается 1 клетка, и должна освободиться 1 клетка. Если освобождается больше чем 1 клетка, то свободной нужно оставить только одну, ту, у которой тариф наибольший. В остальные освобождающиеся вписать нулевую загрузку.
если нет, то в задачу вводится фиктивный поставщик или потребитель36. Теорема о сущ-ии плана трансп задачи. Для его сущ-я необх-мо и достат-но выполн-я усл-я 38. Теорема о ранге матрицы ТЗ. Ранг матрицы А трансп. задачи на единицу меньше числа уравнений: r(A)=m+n-1. 39. Алгоритм построения начального опорного плана ЗЛП. Для нахождения начального опорного плана можно предложить следующий алгоритм: 1. записать задачу в форме жордановой таблицы так, чтобы все элементы столбца свободных членов были неотрицательными, т. е. выполнялось неравенство аio>=0 (i=1,m). Те уравнения с-мы, в которых свободные члены отрицательны, предварительно умножаются на -1. 2.
Таблицу преобразовывать шагами жордановых исключений, замещая нули в левом столбце соответствующими х. При этом на каждом шаге разрешающим может быть выбран любой столбец, содержащий хотя бы один положительный элемент. Разрешающая строка определяется по наименьшему из отношений свободных членов к соответствующем положительным элементам разрешающего столбца. Если в процессе исключений встретится 0-строка, все элементы которой - нули, а свободный член отличен от нуля, то с-ма ограничительных уравнений решений не имеет. Если же встретится 0-строка, в которой, кроме свободного члена, других положительных элементов нет, то с-ма ограничительных уравнений не имеет неотрицательных решений Если с-ма ограничительных уравнений совместна, то через некоторое число шагов все нули в левом столбце будут замещены х и тем самым получен некоторый базис, а следовательно, и отвечающий ему опорный план. | 40. Алгоритм построения оптимального опорного плана ЗЛП. Начальный опорный план Хо исследуется на оптимальность. Если в f-строке нет отрицательных элементов (не считая свободного члена), - план оптимален. Если в f - строке нет также и нулевых элементов, то оптимальный план единственный; если же среди элементов есть хотя бы один нулевой, то оптимальных планов бесконечное множество. Если в f-строке есть хотя бы один отрицательный элемент, а в соответствующем ему столбце нет положительных, то целевая функция не ограничена в допустимой области. Задача не разрешима. Если в f - строке есть хотя бы один отрицательный элемент, а в каждом столбце с таким элементом есть хотя бы один положительный, то можно перейти к новому опорному плану, более близкому к оптимальному. Для этого столбец с отриц-ом элементом в f-строке берут за разрешающий; опред-ют по минимальному симплексному отношению разрешающую строку и делают шаг жорданова исключения. Полученный опорный план вновь исследуется на оптимальность. Это повторяется до тех пор, пока не будет найден оптимальный опорный план либо установлена неразрешимость задачи. 45. Вырожденность и ее устранение при решении задач симплекс-методом. Если среди своб эл-тов есть хотя бы один, равный 0, то план задачи явл вырожденным (опорный или оптим). Геом-ки это означ, что через опорную точку многогранника проходит более n гиперплоскостей вида x1=x2=…=Хn=0. При выборе разреш эл-та наимен симпл отн-ем будет min (Bi/Ais)=0/Ais=0. Вел целевой ф-ции останется прежней, изменится набор баз переменных. В этом случае разреш эл-т выбир-ся по наимен симпл отн-ю своб эл-тов соотв-но к эл-там разреш столбца, исключая нулевое отн-е. | 46. Признак бесконечности множества оптимальных планов и геометрическая иллюстрация. Признаком бесконечности множ-ва планов явл-ся наличие в f-строке симплексной т-це, содержащей оптимал. план, хотя бы одного нулевого элем-та не считая свободного члена. Пусть найден оптим. план Х1*, при чем в f-строке один нулевой элемент. Другой оптим. план Х2* можно найти, выбрав в качестве разреш-го столбец с нулевым элементом в f-строке. Остальные оптим. планы можно определить как линейную комбинацию: Х1*= лХ1*+(1-л)Х2* 0=<л<=л |
. Для любой трансп задачи сущ-ет план.47.Постановка и математич модель ЗЦЛП. В задачах с неделимыми объектами на переменные накладываются условия целочисленности. Иногда эти условия распространяются на все переменные, иногда—на часть переменных. Рассматривают полностью целочисленную задачу f=(n, j=1)∑CjXi max (n, j=1)∑AijXj=bi, i=1,m xj≥0, j=1,n xi-целое, j=1,n Теперь в отличие от общей задачи линейного программирования, оптимальный план не обязательно будет в вершине многогранника планов. Существуют следующие методы решения целочисленных задач: 1.Методы отсечения 2.Комбинаторные 3.Приближенные методы.. Формирование отсекающего неравенства. Идея решения ЗЦЛП методом отсечения и его геометрическая иллюстрация. Идея методов отсечения состоит в следующем: задача решается без учета условия целочисленности. Если полученное решение не является целочисленным, то к условию задачи добавляют новое ограничение, кот называется правильным отсечением. Оно должно удовлетворять 3 условиям: 1.Ограничение должно быть линейным 2.Оно должно отсекать найденное целочисленное решение 3.Оно не должно отсекать не одного целочисленного плана. Расширенная задача подлежит решению, если полученный оптимальный план не целочисленный. Выведем формулу для записи отсекающего неравенства. Допустим, что при решении задачи симпл методом мы получили определенную таблицу. Пусть среди элементов единичного столбца этой матрицы есть дробные-вk. запишем соответствующее ему уравнение Xk=вk-(n-m, s=1)∑бkm+sXm+s Преобразуя это уравнение представим свободные члены и коэфиц как ∑ целой и дробной части. Xk=([вk]-(n-m, s=1)∑[бkm+s]Xm+s)+({вk}-(n-m, s=1)∑ {бkm+s}Xm+s) Сумма в первых скобках-целое число, во вторых-дробное. Для того, чтобы Хк было целым, надо, чтобы и сумма во вторых скобках была целой. Обозначим ее Sk={вk}-(n-m, s=1)∑ {бkm+s}Xm+s Чтобы s было целым оно должно быть не положительным (n-m, s=1)∑ {бkm+1}Xm+1≥{вk} (1) | 48.Алгоритм метода Гомори. 1.Симплекс-методом находят оптимальный план задачи. Если все компоненты оптимального плана целые, то он –оптимальный. В противном случае переходят к пункту 2 2.Среди нецелых компонент следует выбрать ту, у которой дробная часть является наибольшей и по соответствующей этой строке симплексной таблицы сформулировать правильное отсечение по формуле (n-m, s=1)∑ {бkm+1}Xm+1≥{вk} 3.Сформулированное неравенство преобразовать в эквивалентное нулевое равенство и включить в симплексную таблицу с нецелочисленным оптимальным планом 4.Полученную расширенную задачу решают симплекс-методом. Если полученный план не является целочисленным нова переходят к пункту 2. Если в процессе решения появится строка с нецелым свободным членом и целыми остальными коэффициентами, то соответствующее уравнение не имеет решения в целых числах. В таком случае и исходная задача неразрешима в целых числах. Метод Гомори имеет ограниченое применение. С его помощью целесообразно решать небольшие задачи, т. к. число интераций может быть очень большим. | 49.Метод ветвей и границ решения целочисленных задач. Этот метод относится к группе комбинаторных. Применение этих методов заменяет полный перебор планов их частным перебором. Идея метода: пусть дана ЗЦЛП f=(n, j=1)∑CjXi max (n, j=1)∑AijXj=bi, i=1,m xj≥0, j=1,n xi-целое, j=1,n Сначала в ОДЗ этой задачи определяется оптимальный план без учета условия целочисленности. Если в полученном решении некоторые переменные имеют дробное значение, то выбирают любую из дробных переменных и разветвляют исходную задачу на 2 подзадачи f =∑CjXj max f =∑CjXj max (n, j=1)∑AijXj≤bi, i=1,m (n, j=1)∑AijXj≤bi, i=1,m Xk≤[Xk˚] Xk≥[Xk˚]+1 Xj≥0 Xj≥0 Xj-целое, j=1,n Xj-целое, j=1,n Если после решения этих подзадач неизвестные не будут целочисленные, то выбирается задача с большим значением целевой функции и по неизвестной Задача разбивается на 2 новые подзадачи. На каждом последующем шаге сравниваются целевые функции неразветвленных задач и ветвиться задача с большим значением целевой функции. |
50.Понятие о динамич прог. Особ-ти реш-я задач. Динамич программирование—математический метод для нахождения оптим решений многошаговых задач. Многошаговым явл процесс, развивающийся во врем и распадающийся на ряд шагов, или этапов. Одна из особ-тей метода динамич прог сост в том, что принятые решя по отн-ю к многошаг процессам рассм-ся не как единичный акт, а как целый комплекс взаимосвяз решений. Эту послед-ть взаимосвяз решений наз стратегией. Цель оптим план-я—выбрать стратегию, обеспеч получ-е наилучшего рез-та с т. зр. заранее выбранного критерия. Такую стратегию наз оптим. Др важной особ-тью метода явл незав-ть оптим реш-я, принимаемого на очередном шаге, от предыстории, т. е. от того, каким обр оптимизируемый процесс достиг теперешнего сост-я. Оптим реш-е выбир-ся лишь с учетом факторов, характе-ющих процесс в данный момент. Метод динам программ характеризуется также тем, что выбор оптим реш-я на каждом шаге должен произв-ся с учетом его последствий в будущем. Это означает, что, оптимизируя процесс на каждом отдел шаге, ни в коем случае нельзя забыть обо всех последующих шагах. Принцип оптимальности Беллмана. Рекуррентное соотношение Беллмана. Метод динам прогр позволяет одну задачу со многими переменными заменить рядом последовательно решаемых задач с меньшим числом переменных. Решение осуществляется по шагам. Осн принцип, на котором баз-ся оптим-ция многошаг процесса, а также особ-ти вычислит метода—принцип оптим-ти Беллмана. Оптим повед-е обладает тем св-вом, что каковы бы ни были начальное сост-е и нач реш-е, последующие реш-я должны быть оптим относит-но сост-я, получ в рез первонач решя. Математически он записывается вырем вида: fn-1(Sl)=optimum(Rl+1(Sl, Ul+1)+fn-(l+1)(Sl+1)) (1) ul+1 (l=0,n-1) Optimum в выражении означ max или min в завис от усл-я задачи. Все вычисл-я, дающие возм-ть найти оптим знач-е эф-та, достигаемого за n шагов, fn(S0), проводятся по формуле (1), кот носит назв-е осн функционального ур-ия Беллмана или рекуррентное соотн-е. При вычислении очередного знач-я ф-ции fn-1 исп-ся знач-е ф-ции fn-(l+1), получ на предыдущем шаге, и непосредственное знач-е эф-та Rl+1(Sl, Ul+1), достигаемого в рез выбора решения Ul+1 при заданном сост-ии с-мы Sl. Процесс вычисл-я знач-я ф-ции fn-1(l=0,n-1) Осущ-ся при естеств нач условии f0(Sn)=0, кот означ-, что за пределами конечного сост-я с-мы эф-т равен 0. | Вычислительная схема метода динамического программирования. Оптим реш-е задачи методом динамич прог нах-ся на осн функционального уря fn-1(Sl)=optimum(Rl+1(Sl, Ul+1)+fn-(l+1)(Sl+1)) (1) ul+1 (l=0,n-1) Чтобы определить его, необх-мо: 1.записать функц ур-е для последнего сост-я процесса (ему соответствует l=n-1) fn-1(Sl-1)=optimum(Rn(Sn-1,Un)+f0(Sn)) ul+1 2. найти Rn(Sn-1,Un) из дискретного набора его значений при некот фиксир Sn-1 и Un из соотв допустимых обл (так как f0(Sn)=0, то f1(Sn-1)= optimum(Rn(Sn-1,Un) Un В рез после 1ого шага известно реш-е Un и соотв знач-е ф-ции f1(Sn-1) 3.Уменьшить знач-е l на единицу и записать соотв функц ур-е. При l=n-k (k= 2,n) оно имеет вид fk(Sn-k)=optimum(Rn-k+1(Sn-k, Un-k+1)+fk-1(Sn-k+1)) (2) Un-k+1 4.найти условно-оптим реш-е на основе выр-я (2) 5.проверить, чему равно знач-е l. Если l=0, расчет условно-оптим реш-ий закончен, при этом найдено оптим реш-е задачи для 1ого сост-я процесса. Если l не равно 0, перейти к выполнению п.3. 6.Вычислить оптим реш-е задачи для каждого послед шага процесса, двигаясь от конца расчетов к началу. | 51. Задача о выборе кратчайшего пути по сети дорог и реш-е ее методом динамич прог. Надо перевезти груз из А в Б, известна сеть дорог, их соединяющих. Каждой дуге приписана стоимость перевозки груза. Надо определить наиболее экономичный маршрут. Рассматривается некоторый управляемый процесс. В результате управления система переводится из состояния S0 в состояние S. Предположим, что управление может разбиться на n шагов, на кождом из которых выбирается одно из множества допустимых управлений Un (n=1,N). Элементы множества Un и Sn определяются из условия задачи. На каждом шаге достигается эффект Zn. Общий эффект это сумма эффектом, достигнутых на каждом шаге. Тогда задача динам программир будет формулироваться: Определит такое допустимое управление U*=(U1, U2, .. ,UN), переводящее систему из состояния S0 в состояние SN, при котором общий эффект Решение задач методом динамического программирования осуществляется на основе принципа оптимальности. S4=10, S5=11 S3=min(12+S4, 9+S5)=min(12+10? 9+11)=20 S2=min(8+S4, 15+S5)=min(8+10, 15+11)=18 S1=min(4+S2, 7+S3)=min(4+18, 7+20)=22 |
52. Задача об оптим распред-ии ср-в м/у предпр-ями на расшир-е пр-ва и реш-е ее методом динамич прог. В 1 из праздничных дней в 3 пункта города необх-мо отправить 5 автолавок с прод пит-я. За прошедшие годы изучен спрос насел-я, что задается табл. Необх-ио опред-ть max товарооб-т от 3 пунктов города, в кот посылается 5 автолавок.
Функц ур-е: F#(5)=max0<=x<=5(g3(x)+f2(5-x)) F2(5)=max0<=x<=5(g2(x)+f1(5-x)) F1(x)=g1(x) F2(5)=max0<=x<=5=(14+0, 10+4, 8+6, 4+5, 3+12, 15+0)=15 Вспом табл:
F3(5)max=18 млн ден ед Х3*=1 Х2*=4 Х1*=0 Или Х3*=1 Х2*=1 Х1*=3 | 54.Постановка задачи НЛП. Трудности, возник при реш-ии задач НЛП. Понятие выпуклой и вогнутой функции. Общая задача нелин прог ставится след обр: треб-ся найти знач-е n переменных x1,x2,…,xn, кот удовл-ют m ур-ям и нерав-вам цi=(x1,x2,…,xn){≥,=.≤}bi (i=1,m) и максим-ют ф-цию z=f(x1,x2,…,xn) Трудности реш-ия задач связ с тем, что в нелинх задачах допустимая обл м. б. невыпуклой, может иметь бесконечное число крайних точек, целевая ф-я может достигать экстремума не только на границе, но и внутри обл и иметь неск лок экстремумов. С геом т. зр. задача нелин прог сводится к нах-ю выпуклой обл-, определяемой с-мой ограничений и точкой, через кот проходит линия ур-я поверх-ти, задаваемая целевой ф-цией, соотв-ющая наибол (наимен) знач-ю ф-ции. Функция f(x), определенная на выпуклом множестве Х называется выпуклой, если для любых точек х1,х2 из этого множества и любого 0≤л≤1 справедливо неравенство f(лx1+(1-лx2)≤лf(x1)+(1-л)f(x2) (1) Если в соотношении 0<л<1 и любых х1 и х2 принадлежит Х (х1≠х2) имеет место строгое неравенство, то f(x)—строго выпуклая. Примерами выпуклых множеств является квадрат, круг, пирамида. Функция f(x), определенная на выпуклом множестве Х называется вогнутой, если для любых точек х1,х2 из этого множества и любого 0≤л≤1 справедливо неравенство f(лx1+(1-лx2)≥лf(x1)+(1-л)f(x2) (2) Если в соотношении 0<л<1 и любых х1 и х2 принадлежит Х (х1≠х2) имеет место строгое неравенство, то f(x)—строго вогнута. f(x)=f(x1,x2,..xn)—дифференцирована в точке Х0, то градиентом функции f(x) называется n мерный вектор, координаты которого равна частным производным. Grad f(X0)= f(X0). | 55. Графич метод реш-я задач НЛП. Реш-ся как и в ЛП. Строится ОДР. Придается целевой ф-ции пост знач-е const. Опред-ся линия уровня.
r=3 f=0 x2=-2x1 k1=-2 Находим ур-е ОС: X2=k2*x1 K1*k2=-1 усл-е перпендик-ти -2k2=-1 K2=1/2 X2=1/2x1
x2=1/2x1 x1*=1,2 f max=2*1/2 Граф метод ограничен тем, что применим для случая 2 переменных, простейших случ 3 переменных. |
x1>=0, x2>=0 f=2x1+x2(max)
x2*=0,6
+0,6
=3
56.Метод Лагранжа решения задач НЛП. Точка усл экстремума х2=х12 Х2’=2х1=0, х1=0, х2=0, х*=(0,0) Доп огранич-е: х1=1 Х2max=12=1 Чтобы найти точку усл экстр ф-ции, строится ф-ция Лагранжа, учит-ющая доп огранич-я. Метод применим, когда с-ма огр-ий предст собой рав-во. Целевая ф-ция непрер, диффер-ма, им производную по крайней мере 2 порядка. На переменные не наклад-ся усл неотрицат-ти, целочисл-ти. Ф-ция Лагранжа строится, чтобы усл экстр заменить на безусл. В с-му орг-ий L(X1,X2,X3,..Xn, л1,л2,…,лm)=f(x1,x2,..,xn)+(m, i=1)∑лi(bi-цi(x1,x2,…,xn)) Найти частные производные ф-ции Лагранжа по всем переменным, приравнять к 0. Решить с-му ур-ий, опуская множ-ли лi. В рез получим стационарную точку усо экстр. Чтобы опред-ть в ней max/min, надо найти 2ой диффер-л ф-ции Лагранжа по ф-ле:
Если Если Если 57. Градиентный метод реш-я задач НЛП. В ОДР выбир-ся произвол точка х0. Если их нее переместить по разным направл-ям на одинак расстояние, то приращ-е цел ф-ции будет неодинак. Вектор с координатами частных производных цел ф-ции наз градиентом. В каждой точке свой градиент. Им помлед-ть точек x0<x1<x2<x3<…<Cопт Точка опт достигается за бесконечное число шагов, иногда за конечное. Пример. Определить параметр л из усл перпендик-ти линии ур. (grad f)X0+(grad f)X1=0 F=x12+x22-2x1-2x2(min) X0=(1,3)
Grad f=(2x1-2, 2x2-2)(1,3)=(0,4) | 58. Метод искусств базиса реш-я задач ЛП симплекс методом. Если с-ма огр-ий предст-ся в виде равенств, то с пом балансовых переменных, кот практически равны 0, задача предст-ся в канонич форме, и балансовые искусств переменные приним-ся за базисные. Х1+2х2=8 4х1+3х2=17 Х1>=0 x2>=0 F(x)=2x1+3x2(max) С искусств переменными: X1+2x2+x3=8 4x1+3x2+x4=17 Xj>=0, j=1,2,3,4 F(x)=2x1+3x2-m(x3+x4)(max) m-достаточно большое число Баланс переменные: Х3=8-х1-2х2 х4=17-4х1-3х2 Строит исх табл преобразований, где одной индексной строкой опред-ем эл-ты, не связ с m, а 2ой – эл-ты, связ с искусств перем.
При переходе искусств баз переем в своб столбей, соотв своб переем, опускаются.
Х*=(х1*, х2*)=(2,3) F(x*)=2x1+3x2-m(8-x1-2x2+17-4x1-3x2)=2x1+3x2-25M+5Mx1+5Mx2(max)=13 |
вводим столько множ-лей лi, сколько равенств. Если i=1,…,m, то л1, л2, …, лm. Ф-ция Лагранжа запис-ся след обр:
>0, то им min
<0, то им max
, то надо провести доп расчеты, кот в итоге приведут к отсутствию реш-я
grad f=(0,0,…,0)X0
| Предмет и задачи МП. Экон примеры. Постановка общей задачи МП. Задача ЛП и разл формы ее мат. записи (общая, каноническая, симметричная). Преобр-е одной формы записи ЗЛП в др. Целевая ф-ция и ее св-ва, интерпр-ция. Осн понятия планов: допуст, баз, оптим. ОДР ЗЛП. Граф метод реш-я ЗЛП. Опорные планы ЗЛП. Соотв-е м/у опорными планами и вершинами многогранника планов. Осн теорема ЛП. Принцип схема реш-я ЗЛП, вытек из этой теор. Симпл метод реш-я ЗЛП. Общая идея. Геом ил-ция. Признак оптим-ти опорного плана ЗЛП Нах-е нач опорного плана ЗЛП. Нах-е оптим - опорного плана ЗЛП Признак неогр-ти цел ф-ции на мн-ве планов и геом ил-ция. Признак бескон-ти мн-ва оптим планов (альтерн оптимум) и геом ил-ция. Признак неразреш-ти ЗЛП и геом ил-ция Алгоритм симплекс-метода. Понятие двойств-ти в ЛП. Симметр двойств задачи и их экон интерп-ция. Двойств оценки. Несим двойств задачи. Связи м/у эл-тами моделей задач двойств пары. Соотве м/у переменными двойств задач (двойств переменные). Теорема двойств-ти (осн теорема двойств-ти) и ее – экон интерп-ция. Нах-е оптим плана двойств задачи по реш-ю прямой. Теорема об оценках и ее экон интерп-ция Св-ва двойств оценок и их прим-е при анализе решений ЗЛП. Форм-ка и матем модель трансп задачи по критерию ст-ти. Особ-ти модели как ЗЛП. Трансп задача с откр и закр моделью. Преобр-е откр модели в закр. Усл разреш-ти транспй задачи. Усл-я целочисл-ти оптим плана. Теор о ранге матрицы с-мы ограничит урий трансп задачи и ее прикладное знач-е. Циклы в трансп табл. Св-ва циклов. Способы построения нач опорного плана трансп задачи (северо-зап угла, наимен эл-та, Фогеля). Проц-ра преобр-я опор плана трансп задачи в новый опор план. Оценка (хар-ка) свобй клетки трансп табл, ее вычисл-е и экон смысл. Признак оптим-ти опор плана трансп задачи. Неединств-ть оптим плана. Потенциалы поставщиков и потр-лей и их вычисл-е. Связь м/у оценками своб клеток, и потенц-ами. Алгоритм метода потенциалов. | Осн нерав-во теории двойств-ти. Теорема сущ-я оптим планов пары двойств задач. 1ая теорема теории двойств-ти. 2ая теорема теории двойств-ти. Эконометрич смысл двойств оценки. Интервал устойч-ти двойств оценок. Теорема о сущ-ии плана трансп задачи. Теорема о ранге матрицы трансп задачи. Постановка и реш-е задачи об оптим назн-ях. Ассортиментно-распределит задачи, постановка и реш-е. Алгоритм построения опорного плана симплекс-методом. Алгоритм построения оптим плана симплекс-методом. Теорема о выборе разреш эл-та задачи, решаемой симплекс-методом. Теорема об оптим плане задаче, решаемой симплекс-методом. Вырожд-ть и ее устранение при реш-ии задач симпл методом. Случай бесчисл мн-ва оптим планов. Геом ил-ция. Постановка и матем модель задачи ЦЛП. Идея реш-я задачи методом отсечений и его геом ил-ция. Метод Гомори реш-я полностью целочисл задачи ЛП. Метод ветвей и границ реш-я целочислзадач. Понятие о динамич прогр-ии. Особ-ти реш-ия задач. Принцип оптим-ти Беллмана. Вычислит схема метода динамич прогр-я Задача о выборе кратчайшего пути на сети дорог и реш-е ее методом динамич прогр-я. Задача об оптим распред-ии срв м/у предпр-ями на расширение пр-ва и реш-е ее методом динамич прогря. Графич метод реш-я задач дробно-линейного прогр-я. Постановка задачи НЛП. Понятие выпуклой и вогнутой функции Графич метод реш-я задач НЛП. Метод Лагранжа реш-я задач НЛП. Градиентный метод реш-я задач НЛП. Метод искусств базиса реш-я задач ЛП симпл методом. Симпл метод реш-я задач дробно-линейного прогр-я. Постановка задачи параметричо ЛП. Симпл метод реш-я параметрич задач. |
