1)МП—обл приклод-й мат-ки, разраб-я теорию и численные методы реш-я многомер-х, эстрим-х задач с огранич-ми, т.е.задач на экстр-м ф-ции многих перемен-х с огран-ми на обл измен-я этих перем-х. ЭММ—описание эк-го процесса с помощью ф-ций, нерав-в, цифр и т.д., произв-я в целях его исследов-я. Модель задачи МП: max(min)F=f(x),x€Ω или max(min)F=f(x1,х2…xn) (1). Система: γ1(x1,x2…xn){≤,=,≥}b1; γ2(x1,x2…xn){≤,=,≥}b2; …………..γn(x1,x2…xn){≤,=,≥}bn;(2) xj≥0, j=1,n (3) ЦФ—позв-т выбирать наилуч-й вариант из множ-ва возм-х, кот доставл-й ей экстрим-е значение. (2)—основ-е огран-я—условия налогаемые на неизв-е величины, осн огранич-я вырож-ся в виде уров-й и нерав-в. (3)—тривиальные огр-я. (2,3)—образуют ОДР.Сов-ть неиз-х величин х=(х1,х2…хn)наз планом задачи. План Х удовлет-й огран-м (2)(3)наз допустимым. Допус-й план доставл-й ЦФ экстрим-е знач наз оптим-м Х*. Экстрем-е знач-е ЦФобоз-ся F*.

2)Задачи МП деляться на линейного и нелин-го программ-я. Выд-т задачи: целочисленного,параметрического, дробно-линейногопрог-я. Парамет-го прог-е ЦФ и ф-ции опред-щие ОДР зависят от некот-х параметров. В задачах др-линейного пр-я Цф пред-т собой отношение 2-х линейн-х ф-ции. Выд-т задачи: стохостического, динамического пр-я. В задачах динамин-го пр-я процесс нахождения решения явл. многошаговым.

3)ЛП—раздел МП,в кот разраб-я теория и численные методы отыскания эстрим-ма лин ф-циймногих переем-х при лин-х допол-х огранич-й налог-х на эти переем-е. Задача о наил-м исп-и рес-в. Пусть некот-е предп-е произв-т n--видов пр-ции, m—типов ресурсов. Парам-ры: сj-цена ед прод-ции, bi-кол-во ресурсов. аij-колво i-го рес-са использ для произ-ва ед прод-ции j-говида, j=1,n; i=1,m,. Треб-ся найти план производства.Х*=(х1*, х2*…хn*) т.е. максимизация прибыли.Решение: сj-цена ед прод-ции j-го вида , то цена хj ед будет = сjхj,а цена всех n—F= с1х1+с2х2+…+сnхn= ∑( j=1,n) сjхj. Тогда расход i-го рес-са на пр-во всех n видов пр-ции, кот не должен превышать bi составит: аi1х1+аi2х2+…+аinхn=∑( j=1,n) аijхj≤bi, i=1,m. Для того что бы план был реален на обьемы выпуска пр-ции необ-мо условие неотриц-ти,т.е. хj≥0, j=1,n. То ЭММ имеет вид: maхF= ∑( j=1,n) сjхj; ∑( j=1,n) аijхj≤bi, i=1,m; хj≥0, j=1,n

4)Пусть имеется n прод-в питания, в кот содер-ся m полезн-х пит-х вещ-в. сj, j=1,n—цена ед j-го прод-та, bi, i=1,m.—min кол-во i-го полезн вещ-ва кот необ-мо употреб-ть за опред-й период времени. аij, j=1,n; i=1,m—содер-ние i-го полезн вещ-ва в ед j-го пр-та. Требуется опред-ть план Х*, т.е.кол-во прод-ции каждого вида обес-е необ-е кол-во полезн-х вещ-в, при min стоим-ти прод-в питания. Решение: F= с1х1+с2х2+…+сnхn= ∑( j=1,n) сjхj; аi1х1+аi2х2+…+аinхn=∑( j=1,n) аijхj≥bi, i=1,m ; хj≥0, j=1,n Тогда ЭММ имеет вид minF= ∑( j=1,n) сjхj;

∑( j=1,n) аijхj≥bi, i=1,m; хj≥0, j=1,n

5)Задача о выборе оптимальных технологий. В зада­че о наилучшем использовании ресурсов определяется опти­мальный план выпуска продукции. Пусть при производстве какого-то общественно необходимого продукта используется п технологий. При этом требуется т видов ресурсов, задан­ных объемами bi (i = 1, m). Эффективности технологий, т. е. количество конечной продукции (в ден. ед.), производимой в единицу времени по j-й (j= 1,n) технологии, обозначим cj. Пусть, далее, а_ij- — расход i-го ресурса в единицу времени по j-й технологии. В качестве неизвестной величины xj при­мем интенсивность использования j-й технологии, т. е. вре­мя, в течение которого продукция производится по j-й техно­логии. Пренебрегая временем переналадок, необходимым для перехода от одной технологии к другой, получаем следующую математическую модель задачи: найти план интенсивностей использования технологий х = (xi;... ;х_п), обеспечивающий максимум выпуска продукции в стоимостном выражении:

6)Задача о раскрое материалов. Суть задачи об опти­мальном раскрое состоит в разработке таких технологически допустимых планов раскроя, при которых получается необ­ходимый комплект заготовок, а отходы (по длине, площади, объему, массе или стоимости) сводятся к минимуму. Рассмо­трим простейшую модель раскроя по одному измерению. Бо­лее сложные постановки ведут к задачам целочисленного про­граммирования.

Модель задачи раскроя по одному измерению длинномер­ных материалов (прутков, труб, профильного проката и др.) может быть сформулирована так. Пусть имеется N штук ис­ходного материала, длина каждой штуки равна L. Нужны заготовки т видов, длины которых равны l_i (г = 1,то). Из­вестна потребность в заготовках каждого вида, она равна b{. Изучение вопроса раскроя (построение технологической кар­ты раскроя) показывает, что можно выделить п приемлемых вариантов раскроя исходного материала длиной L на заго­товки длиной Zj. Обозначим через a,ij количество заготовок г-

го вида, получаемое при раскрое единицы исходного мате­риала по j-му (j — 1,п) варианту, Cj — отходы при раскрое единицы исходного материала по j-му варианту. План задачи х = (х₁;... ; x_j \... ;х_п), где xj — количество единиц исходно­го материала, планируемое к раскрою по j-му варианту.

Функция цели — минимум отходов, получаемых при рас­крое:

при ограничениях: на число единиц исходного

материала

7)Множество наз.выпуклым,если вместе с любыми 2-я своими т. оно сод. произв-ю выпуклую лин-ю комбинацию.Вып-ой лин-ой комб-ей т. x₁ x₂….x_n наз.сумма λ1х1+λ2х2+…+λnxn λi>0 Σ(i=1,n)λi=1

Рассм. зад. с 2-я переменными max(min)F=c1x1+c2x2 (1) a11x1+a12x2<=b1, a21x1+a22x2<=b2 ………. am1x1+am2x2<=bm (2) x1>=0 x2>=0 (3) .Каждое из огран-ий (2),(3) задаётся на плос-и х1Ох2 некот. полупл. Полупл. выпукл. мн-о, пересеч. любого числа вып-х мн-в явл. вып-м мн-м. Т/обр. ОДР явл. вып-щу мн-о. (Вставить рис.)Предп-м, что ОДР явл. вып-й многогр-к А1А2А3А4А5А6 выб-м произв-ое знач. F=Fo,то c1x1+c2x2=Fo это ур-е прямой линии считая F парам-м полу-м ур.семей-а паралле-х прямых,кот. наз. линиями ур.ЦФ(линиями пост. знач.)

Для того чтобы нйти напр-е возр-я ЦФ найдём её частное произв-ое по х1,х2 ðF⁄ðx1=c1 ðF⁄ðx2=c2 Вектор Ć=(с1 с2)наз. градиентом функции и указ-т направл. наискоре-го возр-ия. –Ć(с1 с2) наз. антиград-м и указ-т направл. наискор-го убыв-я ЦФ. Ć,-Ć_|_(с1х1+с2х2=F). Алгор- м граф. метода:1)с уч. системы огр-ий строим обл. допуст. решений 2)строим вектор градиент3) строим прямую F=0 _|_Ć 4) в случ. реш зад. на max прямую F=0 перемещ.в напр-ии Ć до край-ей т.(дальней) ОДР. В случ.реш.зад. на min F=0 перемещ. до1-й т. ОДР 5)наход.оптим.реш. Х* и экстр-е знач. ЦФ F*

9)Общ. зад.ЛП наз.задачу: max(min)F=Σ(j=1 n)cjxj Σ(j=1 n)aij xj<=bi i=1.m1 j=1.m Σ(j=1n)aij xj=bi i=m+1.m2 Σ(j=1n)aij xj>=bi i=m2+1.m3 xj>=0 j=1,n xj-произв. j=n1+1,n Симметр-ой зад. ЛП наз. зад.: maxF=Σ(j=1 n)cjxj Σ(j=1 n)aij xj<=bi i=1.m xj>=0 j=1,n minF=Σ(j=1n)cjxj Σ(j=1n)aij xj>=bi xj>=0 j=1,n Кононической (основ-й)зад. наз. зад. min)F=Σ(j=1n)cjxj (1) Σ(j=1n)aij xj=bi (2) i=1.m xj>=0 j=1,n (3 ) часто исп-ся зад. запис-ые в матрич-й и векторной форме. Расс. зад. (1)-(3) введём след. обозн. C=[c1, c2,….cn] X=[Запис-м в столбик x1 x2…..xn] A=[зап. в столб. a11 a12 …..a1n; a21 a22 ….a2n; ………; am1 am2 …..amn] B=[в столб. b1 b2 …. bm] Тогда зад. 1-3 запиш-ся виде maxF=CX AX=B X>=0 Введём обозн. ВСЁ ПИШЕМ В СТОЛБ A1=[a11 a21 … am1] A2=[a12 a22…am2] …….. An=[a1n a2n ……amn] Тогда послед. зад можно запис. в виде maxF=CX A1x1+A2x2+…..+Anxn=B X>=0

10)Пер-д к кан-ой форме записи ЛП.Т-ма о доп-х реш-х.

Рассм. Задачу вида: maxF= _jx_j 1); b_i, i=1,m₁ 2); b_i i=m₁+1,m 3); x_{j ,} j=1,n 4); введём x_{n+i ,} i=1,m Преобразуем неравенства в равенства, для этого прибавим(вычтем) доп.перемен.с коэф.=0. В итоге получим канон-ю форму записи: maxF= _jx_j+ _n+i 7); +x _n+i=b_i ,i=1,m₁ 8); -x _n+i=b_i, i=m₁+1,m 9); x_{j ,} j=1,n j=1,n x_n+i i=1,m 10). Т-ма: каждому допуст-му реш-ю 1)-4) соот-т допуст-е реш-е 7)-10) и наоборот. Т.к. доп-е перем-е в ЦФ 7) с коэф=0 => значения 1)=7) => ЦФ 1) и7) достигают экстрем-го знач-я одновр-но. Оптим-му реш-ю 1)-4) соотв-т 7)-10), т.е. исходн-я задача и её канон-я форма эквивалентны.

11)Пер-д к симметр-й форме записи задачи ЛП.

Рассм. Задачу ЛП в канон-м виде maxF= _jx_j 11); =b_i, i=1,m

12); x_j j=1,n 13). С помощью методов Гауса, Жардановых искл-й с-му 12) можно преобразовать: x_i+ λ_ijx_j=ß_i, i=1,m 14). В 14) векторы А₁,А₂,…,A_m составляют базис с-мы векторов А₁,А₂,…,A_n.Переменные соответ-е векторам базиса наз-ся БП. x₁+x₂+…x_m- БП; x_m+1,x_m+2…x_n –СП. Если в общем решении с-мы 14) СП=0, а БП=свободным членам, то получим частное решение (ß₁, ß₂…ß_m,0,0,…0) называется базисным. Базис-е реш-е с полож координатами наз-ся опорным решением. Выразим ЦФ 11) через СП получим: maxF= _jx_j=с₁x₁+c₂x₂+…c_mx_m+c_m+1x_m+1+…+c_nx_n. Обозначим через C_Б коэф-ты ЦФ стоящие при БП, через В – вектор свободных членов A_m+k, k=1,n-m – вектор коэф-в при СП. Обозначим через ∆₀= C_БB; ∆_m+1= C_БA_m+1+C_m+1; ∆_m+2= C_БA_m+2 - C_m+2……..∆_n= C_БA_n-C_n. Тогда ЦФ 11) можно записать в виде: F=∆₀- ∆_jx_j. Т.к. x_{j ,} j=1,n, то из формулы 14) получим x_i=β_i - α_ijx_j 0 => α_ijx_j . В итоге получим задачу в симметрической форме: F=∆₀- ∆_jx_j; α_ijx_j ; x_j , j=m+1,n

12)Т-ма о струк-ре корд-т угловой точки.

Если с-ма векторов А₁,А₂,…,A_n содержит m линейно независимых векторов А₁,А₂,…,A_m, то допустимое решение вида X=(x₁,x₂….x_m,0…0) x_j>0 j=1,m 4); Явл-ся крайней точкой многогранника планов решений. Док-во: Т.к. с-ма векторов А₁,А₂,…,A_m явл-ся линейно независимой, то вектор В м.б. выражен через них единст-м образом A₁x₁+ A₂x₂+…+ A_mx_m=B 5); Предположим, что 4 не яв-ся крайней точкой => её можно пред-ть как выпуклую линейную комбинацию двух других точек X₁,X₂. X=λ₁X₁+ λ₂X_2, где λ₁>0, λ₁+ λ₂=1 6); Точки X₁ и X₂ имеют вид X₁=(¹x₁,¹x₂…¹x_n), X₂=(²x₁,²x₂…²x_n) 7); Подставим 4) и 7) в 6) Получим, что точки x₁ и x₂ имеют такую же стр-ру как x. Поскольку точки x₁ и x₂ принадлежат ОДР => они должны удовлет-ть векторному равенству 5). (A₁x₁¹+ A₂x₂¹+…+ A_mx_m¹=B) – (A₁x₁²+ A₂x₂²+…+ A_mx_m²=B)=A₁(x₁¹-x₁²)+ A₂(x₂¹-x₂²)+….+ A_m(x_m¹-x_m²)=0. Т.к. векторы А₁,А₂,…,A_m линейно независимые, то последнее равенство выпол-ся при условии x₁¹= x₂¹,…, x_m¹= x_m². Пришли к противоречию, что точку Х невозможно представит как выпуклую комбинацию двух различных точек => X- крайняя точка

14)Построение начального опорного плана.

1-й сл.: =b_i, b_i i=1,m. Огран-е равенства имеет предпочтительный вид,если при неотриц. прав. части лев. часть содержит переменную с коэф-м равным 1, а восталные огран-я это переем-я с коэф 0. С-ма огр-й имеет предпочтительный вид, кажд огран-е рав-ва имеет предпоч-й вид. Оптим-е реш-е: все СП=0, а БП=свободным членам. 2-й сл.: b_i b_i i=1,m. Приведём к канон-му виду x₁,x_2,….,x_n – СП, а x_n+1,x_n+2,….,x_n+m – БП. Тогда начальный опорный план: X₀=(0,0…0,b_1,b₂...b_m).3 сл.: b_i b_i i=1,m.

15)Признак оптимальности опорного плана. Симплексная таблица.

БП	1	-xm+1	-xm+2	-xm	-xm+n
x1	β1	α11 m+1	α11 m+2	…	α1 m
x2	β2	α22 m+1	α21 m+2	…	α2 n
xm	βm	αm1m+1	αm1m+2		αmn
F	∆0	∆m+n			∆n

Посл-ю строку называют индексной строкой(строкой ЦФ). ∆₀=F(X₀)- знач-е ЦФ для начального опорного плана. Т-ма: пусть исходная задача решается на max.Если для некоторого опорного плана все оценки ∆_j 0, j=1,n, то такой план оптимальный Док-во: т.к. : F=∆₀ - ∆_jx_j и по усл-ю ∆_j , j=1,n, то ЦФ F достигает max знач-я при ∆_jx_j=0 это возможно лишь тогда, когда x_m+1=x_m+2…x_{n =}0, т.е опорный план вида X^*=( β_1, β_2… β_m,0…0) – оптимальный. Т-ма: Пусть исходная задача рассм-ся на min если для некоторого опорного плана ∆_j 0, j=1,n, то такой план оптимальный

17)Симплексные преобразования

Для того, чтобы завершить шаг преобразований, ведущих к новому опорному плану, в новом базисе выразим новую БП x_j0 из уравнения с номером i₀ системы x_i+∑α_ijj=b_i(j=m+1,n), b_i≥0,i=1,m через СП

x_i0+α_i0,m+1x_m+1+…+α_io,j0-1x_jo-1+α_i0j0x_j0+α_i0,j0+1x_j0+1+…+α_i0nx_n=β_io

x_j0=β_i0/α_i0j0-((α_i0,m+1/α_i0j0)x_m+1+…+ (α_i0,j0-1/α_i0j0)x_j0-1+(1/α_i0j0)x_i0+(α_i0,j0+1/α_i0j0)x_jo+1+…+(α_i0n/α_i0j0)x_n (1)

Аналогично, если мы подставим в выражение (1) в остальные ограничения (1) ограничения и в ЦФ max(min)F=∆₀-∑∆_jx_j(j=m+1), получим след. формулу:

X_i=(β_iα_i0j0-β_i0α_ij0)/α_i0j0-((α_i,m+1α_i0j0-α_i0,m+1α_ij0)/α_i0jo+…-(α_ij0/α_i0j0)x_i0+…+((α_inα_i0j0-α_i0nα_ij0)/α_i0j0)x_n),i=1,m; i≠i₀ (2)

F= (∆₀α_i0j0-∆_j0β_i0)/α_iojo-(((∆_m+1α_i0j0-∆_j0α_i,m+1)/∆_iojo)x_m+1+…-(∆_j0/α_iojo)x_io+…+((∆_nx_iojo-∆_joα_i0n)/α_i0j0)x_n)

Из формул (1)-(3) следуют правила пересчета элементов таблиц:

1)из выражения (1) следует, что элемент новой таблицы, стоящий на месте разрешающего , заменяется обратной величиной.

2)из выражения (1) следует, что оставшиеся элементы разрешающей строки i₀ новой таблицы равны соответственно элементам разрешающей строки старой таблицы, деленным на разрешающий элемент.

3)оставшиеся элементы разрешающего столбца из выражений (2) и(3) новой таблицы равны соотв. элементам разрешающего столбца старой таблицы, деленным на разрешающий элемент и изменением знака на противоположный.

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

18) Теорема Если в индексной строке последней симплексной табл, содержащей оптимальный план, имеется хотя бы одна нулевая оценка, соответствующая свободной переменной, то ЗЛП имеет бесконечное множество оптимальных планов

Доказательство. Пусть в оптимальном плане Aj₀ = О, где jo принадлежит множеству индексов СП, а минимальное симплексное отношение соответствует строке iго- Тогда, введя Xj₀ в базис, получим новое значение ЦФ.

Значение ЦФ при переходе к новому опор­ному плану не изменилось.

Если нулевых небазисных оценок в последней симплексной таблице окажется несколько, то, введя каждую из соответ­ствующих переменных в базис, найдем оптимальные планы x1*,x2*,... ,хk*, для которых значение ЦФ будет одно и то же, т. е.

Z(x1)=z(x2)=…z(xk)

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

λ =λ1x1+λ2x2+…..+λkxk, λ1+λ2+….+λk=1

λi≥0 (i=1,k)

Эта ф-ла опред-т бесконечное мн-во оптимальн. Планов.

Следств: Если в инд. Строке симпл. табл, содержащей оптимальный план, все оценки СП положит., то найденные опт план и единств.

19) Теорема 1.10. Если в индексной строке симплексной та­блицы ЗЛП на максимум содержится отрицательная оцен­ка ∆j₀ < 0, а в соответствующем столбце переменной Xj₀ нет ни одного положительного элемента, то целевая функ­ция на множестве допустимых планов задачи не ограничена сверху.

Доказательство. Если бы все оценки индексной стро­ки Aj были неотрицательны, то опорный план был бы опти­мальным. Пусть ∆j₀ < 0. Тогда можно попытаться, не изме­няя нулевых значений всех свободных переменных x_m+i,... , х_п в равенстве (1.95), кроме Xj₀, увеличить значение целевой функции Z за счет увеличения переменной Xj₀ > 0. Полагая в равенствах (1.96) все Xj, кроме Xj₀, равными нулю, получаем

Так как Xi≥ 0, то

Пусть все aij₀ ≤ 0. Тогда при любом Xi₀ ≥ 0 имеем Xi ≥ 0. Что касается целевой функции Z, то, взя^тз в качестве Xj₀ достаточно большое положительное число, вследствие того, что ∆j₀ < 0, можно сделать значение

как угодно большим. В самом деле, так как ∆j₀ < 0, при Xj₀ —> оо имеем Z = ∆о — ∆j₀Xj₀ —► оо, т.е. целевая функция Z не ограничена сверху.