Шпоры по вышке

1.Мат. Прогр-е – область прикладной математики, разраб-щая теорию и численные методы решения многомерных, экстрем-х задач с ограничением, т. е. задач на экстремум ф-ции многих переменных с ограничением на область измен-я этих переменных. ЭММ –система мат. Ф-ций, уравнений, неравенств, описывающих реал-й эконом-й объект, сставляющие его характ-ки и взаимосвязи м-ду ними. Модель задачи МП можно записать в виде: max (min)F = f(x1,x2,…xn), (1); ϕi (x1,x2,…xn) { ≤, =, ≥} bi, i=1,m. (2); xj ≥ 0, j =1,n. (3) . 1 – ЦФ-показатель эффективности, критерий оптимальности. В качестве ЦФ мб прибыль, объем выпуска или реализации, отходы и т. д.; 2 – основные;3 – прямые ограничения. Матем-ки ограничения запис-ся в виде уравн-й и нерав-в, сов-ть которых образ-т ОДР. Сов-ть независимых величин Х=( x1,x2,…xn), действуя на которые систему можно совнршенств-ть, наз. планом задач. План Х, удовлетворяющий основным и прямым ограничениям наз-ся допустимым. Допустимый план, доставл-щий ЦФ экстрем. значение наз. оптимальным и обознач-ся Х*. Аналогично экстр. Значение ЦФ обознач-ся F*=F(X*). В завис-ти от свойств ф-ций f и ϕi (i=1,m) МП можно рассматривать как ряд самост. величин. Задачи МП делятся на задачи линейного и нелинейного прогр-я. Среди задач нелин. пр-я наиболее глубоко изучены задачи выпуклого программ-я, в рез-те реш-я которых опред-ся min выпуклой (max вогнутой) ф-ции, заданной на выпуклом замкнутом множ-ве. Отдел-ми класс-ми задач явл. задачи целочисл-го, параметрич-го, дробнолин-го прогр-я. В з-х целоч. прогр-я на искомые перемен-е налаг-ся усл-е целочисл-ти, а ОДР конечное. В з-х парам. прог-я ЦФ или ф-ции, опред-щие ОДР либо то и другое зависят от некоторого параметра. В з-х дробнолин-го пр-я ЦФ предст-т собой отнош-е 2-х лин-х ф-ций. Выдел-т также з-чи стохастического и динам-го прогр-я. В з-х дин-го пр-я процесс нахождения реш-я явл-ся многошаговым. В з-х стохаст-го пр-я в ЦФ или в ф-ях из ОДР содерж-ся случ-е величины.

2. ЛП – раздел МП, в котором разраб-ся методы нахождения экстр-ма лин-х ф-ций при лин-х дополн-х огранич-ях, налаг-мых на эти перемен-е.

4.зад. о.диете

n — кол-во прод-ов питания;m – питат-е вещ-ва; cj,j=1,n – цена ед-цы прод-та; bi,i=1,m – min-е кол-во i-го полезного вещ-ва; aij, j=1,n, i=1,m –содерж-е i—го вещ-ва в ед-це j-го прод-та. Треб-ся опр-ть кол-во приобретения кажд. вида прод. X*=(x1*,x2*…xn*),обесп-е необх. кол-во полез. вещ-в при min-ой общей стоим-ти прод-в питания.

ЭММ:minF=

xj≥0

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

при огранич — ях на лимит-е ресурсы: max Z= ∑cjxj и условии неотрицательности: xj≥0 (j=1,n)

6.Задача о раскрое материалов. Суть задачи об опти­м-ом раскрое состоит в разраб-ке таких техн-ски допуст планов раскроя, при кот получ-ся необ­ход комплект заготовок, а отходы (по длине, площади, объему, массе или стоимости) свод к минимуму. Рассмо­трим простейшую модель раскроя по одному измерению. Бо­лее сложные постановки ведут к задачам целочисл про­грамм-ия. Модель задачи раскроя по одному измер длинномер­ных материалов (прутков, труб, профильного проката и др.) может быть сформул так. Пусть имеется N штук ис­ходного материала, длина каждой штуки равна L. Нужны заготовки т видов, длины которых равны Li (i = 1,n). Из­вестна потреб-сть в заготовках каждого вида, она равна b{. Изучение вопроса раскроя (построение технол-ой кар­ты раскроя) показ-ет, что можно выделить n приемлемых вариантов раскроя исход матер длиной L на заго­товки длиной Zj. Обозначим через aij количество заготовок i-го вида, получаемое при раскрое единицы исходного мате­риала по j-му (j=1,n) варианту, Cj — отходы при раскрое единицы исходн матер по j-му варианту. План задачи х = (х1;… ; xj … ;хn), где xj — количество единиц исходно­го материала, планируемое к раскрою по j-му варианту. Функция цели — мин отходов, получ при рас­крое: min Z = ∑cjxj при огранич: на число ед исх матер: ∑xj≤N

7.Формы записи задачи ЛП

Общ. задача ЛП: Max(min)F= ∑Cj*xj

∑ aijxj≤ bi, i=1,m1

∑ aijxj= bi, i=m1+1,m2

∑ aijxj≥ bi, i=m2+1,m, xj≥ 0, j=1,m, xj – произвольн., j= n2+1,n

Симметр.ф.:

MaxF= ∑Cj*xj

∑ aijxj≤ bi, i=1,m, xj≥ 0, j=1,n или

MinF= ∑Cj*xj

∑ aijxj≥ bi, i=1,m, xj≥ 0, j=1,n

Канонич.ф.:

Max(min)F= ∑Cj*xj

∑ aijxj= bi, i=1,m, xj≥ 0, j=1,n

Рассм. 2 вида записи- матричн. и векторн. Введём обознач. Задачу записать матрично:

Max(min)F= C*X; A*X=B; X≥0

Векторн:

Max(min)F= C*X

А1X1+ А2X2+…+ АnXn=B; X≥0

Задачу миним-ции можно заменить максим-цией и наоборот:

Min f(x1*, x2*… xn*)= — max (-f(x1*, x2*… xn*))

18. Правила пересчёта

1 правило: элемент новой табл., стоящей на месте разрешающего зам-ся обр-ой величиной.

2 прав.: оставшиеся эл-ты разреш-щей строки дел-ся на разреш. Эл-т.

3 прав.: оставш-ся эл-ты разреш-го столбца делим на разр. Эл-т и меняем знак на противоп-й.

4 прав.: все ост-ся эл-ты рассч-ся по правилу прямоуг-ка.

3. зад. о.наилуч. исп. рес-в

n-прод-и; m-рес-сы; cj,j=1,n – цена ед-цы прод. j-го вида; bi,i=1,m – кол-во i-го рес-са; aij, j=1,n, i=1,m – кол. i-го рес-са, необход. для пр-ва прод-и j-го вида. Треб-ся опр-ть план пр-ва кажд. прод-и X*=(x1*,x2*…xn*), при кот. обесп-ся max-ая выручка.

Цена общего V реал-ии:F=c1x1+c2x2+…+cnxn.

Расход на пр-во всех n видов прод-и не должен превышать bi: ai1x1+ai2x2+…+ainxn≤bi, i=1,m.

Усл-е неотриц-ти:xj≥0, j=1,n.

ЭММ:maxF=

xj≥0

9. Переход к сим-ной форме записи задачи, осущ-ся 2-мя спос-ми:

1сп. пусть к задаче ЛП имеются уравн-я рав-ва . Каждое такое огранич-е рав-ва эквив-но в сис-ме нер-в: , . Нер-во вида «≥»*(-1) преобр-ся к нер-вам «≤» и наоборот. 2сп. Рассм-м задачу в канон-м виде: max(min) F=, , i=1,m, xj≥0, j=1,n преобр-м её к симметр-му виду сис-му огран-й , нап-р, методом Гаусса, можно привести к виду , i=1,m пусть ранг =m, m<n, тогда сис-ма имеет бескон-ное множ-во реш-й. Перем-ные x1,x2,…,xm наз-ся БП, а перем-ные xm+1,xm+2…xn –СП, выразим ЦФ через СП, для этого подставим БП в ЦФ max(min) F= . Испол-я данные обознач-я ЦФ можно записать в след-м виде: F= ▲0-▲jxj. Из сис-мы , i=1,m в силу того, что все xj≥0, j=1,n можем записать, что ,i=1,m. Т. Обр. получили симметр-ную форму записи , , i=1,m, xj≥0, j=m+1,n. Отметим, что в любом случае при подстановке БПпп в ЦФ справедлива формула — это испол-ся для контроля выч-ий при реш задачи симп-ным мет-м. Если некот-е переем-е явл-ся отриц, то они замен-ся разностью 2-х полож-х xk=xk’-xk’’, где xk’≥0, xk’’≥0