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. Различные формы записи ЗЛП (общая, каноническая, симметрическая)

Общей ЗЛП называют задачу максимизации (минимизации) линейной функции 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) при линейных ограничениях равенствах и неотрицательных переменных.

Переход от 1 формы записи к другой: 1) min f(x) = -max(-f(x))

2) всякому решению х1…хn нерав-ва a1x1+…+anxn<=b (5)соответствует вполне определенное решение х1…аnхn+xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>=0(7) и наоборот.

3) если на переменную не наложено усл-е неотрицат-ти, то ее заменяют разностью 2х неотрицат-х переменных

3. Геометрическая интерпретация целевой функции и ограничения ЗЛП. Геометрическая формулировка ЗЛП.

Пусть дана задача f=c1x1+c2x2 (max) (1)

a11x1+a12x2<=b1 }

am1x1+am2x2<=bm}

x1>=0, x2>=0 (3)

План задачи (х1,х2) – точка на плоскости. Каждое неравенство с-мы 2 предст. собой полуплоскость. Полуплоскость –выпуклое множество. Выпуклым наз-ся множество в которым точки отрезка соединяющие (х1 и х2) принадлежащие этому множеству то же принадлежат множеству. С-ма 2 представляет собой пересечение полуплоскастей.

Геометрическая интерпретация целевой функции: функция 1 представляет собой семейство параллельных прямых, которые наз-ют линиями уровня(линиями постоянного значения целевой функции). Частные производные функции по х1 и х2 показывают скорость возрастания целевой функции вдоль координат осей. Вектор-градиент показывает направление найскорейшего возрастания целевой функции.Для задачи 1-3 вектор-градиент = (с1;с2) Выходит из точки (0,0) и направлен в точку с координатами (с1;с2). Вектор-градиент перпендикулярен линиям уровня. Пересечение полуплоскастей принято наз-ть областью допустимых значений(ОДЗ).

4. Графический метод решения ЗЛП.

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

1. Построить ОДЗ; 2. Построить вектор С;3. Перпендикулярно С построить линию уровня f=0; 4. Перемещая линию уровня в градиентном направлении найти точку максимума или минимума ОДЗ; 5. Найти координаты точки максимума (минимума) и значение функции в этой точке. В ходе решения ЗЛП граф. способом могут получаться след. результаты:

1. Оптимальный план единственный: линия уровня и ОДЗ в крайнем положении имеют одну общую точку;

2. Оптимальных планов бесконечное множество: в разрешающем положении линия уровня проходит через грань ОДЗ;

3. Задача не имеет решения: ОДЗ=ø;

4. Целевая функция не ограничена, в этом случаи добавляется еще одно ограничение.

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. Основная теорема ЛП. Принципиальная схема решения ЗЛП, вытекающая из этой теоремы.

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

БП	1	СП -Xm+1 -Xm+2 -Xn
х1	b1o	b11 b12 b1n-m
х2	b2o	b21 b22 b2n-m
хm	bm	bm1 bm2 bmn-m
f	boo	bo1 bo2 bon-m

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. Теорема о выборе разрешающего элемента.

Пусть задача решается на max, тогда среди отрицательных чисел f-строки выбираем максимальное по модулю. Соответствующий столбец будет разрешающим. Составляем и рассчитываем симплексные отношения: отношения чисел, стоящих в единичном столбце к соответствующим положительным числам разрешающего столбца. Выбираем минимальное симпл. отношение, оно определяет разрешающую строку. На пересечении разрешающего столбца и строки находится разрешающий элемент. Если задача решается на min, то для определения разреш. столбца выбираем max из положительных чисел f-строки.

9. Нахождение начального опорного плана ЗЛП.

Для нахождения начального опорного плана можно предложить следующий алгоритм:

1. записать задачу в форме жордановой таблицы так, чтобы все элементы столбца свободных членов были неотрицательными, т.е. выполнялось неравенство аio>=0 (i=1,m). Те уравнения с-мы, в которых свободные члены отрицательны, предварительно умножаются на -1.

2.

	1	-x1 ….. -xn
0=	a1o	a11 …. a1n
…..	…..	………………………..
0=	amo	am1 ….. amn
f=	0	-c1 …. -cn

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

11. Признак оптимальности опорного плана ЗЛП.

Признак опорного плана явл-ся неотрицательность элементов столбца свободных членов, не считая элементов f-строки. Признаком оптимального плана - если в симплексной таблице содержится опорный план, все элементы f-строки, которые неотрицательны (не считая свободного члена bоо), то этот опорный план является оптимальным. Если в соотношении f=boo-(n-m;j=1)Σboj*Xj+m значение всех свободных переменных равно нулю, то целевая функция будет ровна свободному члену f(векторXo)=boo. При увеличении значений свободных переменных функция начнет умен-ся, следовательно при плане Хо функция принимает экстремальное значение.

12. Правило пересчета элементов симплекс-таблицы после выбора разрешающего элемента.

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

13. Нахождение оптимального опорного плана ЗЛП.

Начальный опорный план Хо исследуется на оптимальность.

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

14. Признак неограниченности целевой функции на множестве планов и геометрическая иллюстрация.

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

15. Признак бесконечности множества оптимальных планов и геометрическая иллюстрация.

Признаком бесконечности множ-ва планов явл-ся наличие в f-строке симплексной т-це, содержащей оптимал.план, хотя бы одного нулевого элем-та не считая свободного члена. Пусть найден оптим.план Х1*, при чем в f-строке один нулевой элемент. Другой оптим.план Х2* можно найти, выбрав в качестве разреш-го столбец с нулевым элементом в f-строке. Остальные оптим.планы можно определить как линейную комбинацию:

Х1*= λХ1*+(1-λ)Х2* 0=<λ<=λ

16. Признак неразрешимости ЗЛП и геометрическая иллюстрация.

При нахождении базисного решения начальный опорный план может не выделиться. В этом случаи необходимо построить начальный опорный план по след. правилам:

1. записать с-му уравнений канонич. Формы задачи в виде 0-равенств. Свободные члены должны быть неотрицательными.

2. записать полученную с-му в симплексную таблицу.

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

17. Алгоритм симплекс-метода.

Алгоритм симп. м-да:

1. привести модель задачи к канонической форме;

2. найти начальный опорный план;

3. записать задачу в симпл. таблицу;

4. если содержащейся в таблице план явл-ся оптимальным выписывается ответ. Если нет, то выполняется следующий пункт;

5. прперейти к новому опорному плану, к новой симп. таблице. Для того чтобы перейти к новому опорному плану достаточно заменить одну базисную переменную свободной. Переменную, включаемую в базис и соответствующей ей разрешающий столбец определяют по наибольшему по модулюотрицательному элементуf-строки. Переменную, исключающую из базиса и соответствующую ей разрешающую строку определяют по наименьшему симплексному отношению, т.е. отношению элементов единичного столбца к соответствующему элементу разрешающего столбца. Симплексное отношение – величина неотрицательная. На пересечении разрешающей строки и разрешающего столбца расположен разрешающий элемент, относительно которого выполняется симплексное преобразование по след. правилу: 1. элементы разрешающей строки делятся на разрешающий элемент; 2. элементы разрешающего столбца делятся на разрешающий элемент и меняют знак на противоположный; 3. остальные элементы таблицы перещитываются по правилу прямоугольника.:

bij bis bkj=(bkj*bis-bij*bks)/bi

bkj bks

19. Экономические примеры двойственных задач. Симметричные двойственные задачи и их экономическая интерпретация.

Дадим экономическую интерпретацию пары двойственных задач. Рассмотрим задачу рационального использования ресурсов. Пусть предприятие располагает ресурсами 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)

Заметим, что это задача образуют симитричную двойственную задачу.

20. Построение двойственной задачи. Связь между элементами моделей задач двойственной пары. Рассм. задачу в симметр форме записи:

F(x)=c₁x₁+c₂x₂…c_nx_n (max)

a₁₁x₁+a₁₂x₂+…+a_1nx_n<=b₁

……………………………..

a_n1x₁+a_n2x₂+….+a_mnx_n<=b_m

xj>=0 j=1,n

Выписываем в матричной форме и транспонируем. По транспонированной табл. строим задачу:

U(y)=b₁y₁+b₂y₂+…+b_my_m (min)

a₁₁y₁+a₂₁y₂+...+a_1my_m>=c₁

.........................................

a_1ny₁+a_2ny₂+....+a_mny_m>=c_n

Взаимосвязь элементов взаимодвойственных задач. Если в исх.задаче m-ограничений и n-переменных, то в двойственной n-ограничений и m-переменных. Если в исх. задаче целевая фун-я максимизируется, то в двойственной минимиз. И наоборот. Если в исх задаче знаки сравнения <= , то в двойствен. >= (и наоборот).

Между переменными прямой двойственной задачи можно установить соответствие: основным переменным исходной задачи ставятся дополнительные переменные двойственной задачи, а дополнительным переменным исходной ставятся в соответствие основные двойственные.