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

Зад.о.диете

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= Зад.о.наилуч.исп.рес-в - student2.ru

Зад.о.наилуч.исп.рес-в - student2.ru

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

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

Общ. задача ЛП: 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*))

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

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

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

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

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

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

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= Зад.о.наилуч.исп.рес-в - student2.ru

Зад.о.наилуч.исп.рес-в - student2.ru

xj≥0

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

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

Наши рекомендации