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

Зад.о.диете

n - кол-во прод-ов питания;m – питат-е вещ-ва; c_j,j=1,n – цена ед-цы прод-та; b_i,i=1,m – min-е кол-во i-го полезного вещ-ва; a_ij, j=1,n, i=1,m –содерж-е i-го вещ-ва в ед-це j-го прод-та.Треб-ся опр-ть кол-во приобретения кажд. вида прод. X*=(x₁*,x₂*…x_n*),обесп-е необх.кол-во полез.вещ-в при min-ой общей стоим-ти прод-в питания.

ЭММ:minF=

x_j≥0

5.Задача о выборе оптимальных технологий. В зада­че о наилуч использ рес-ов опред-ся опти­м-ый план выпуска продукции. Пусть при произ-ве какого-то общественно необход продукта использ-ся n технологий. При этом треб-ся т видов рес-ов, задан­ных объемами b_i (i = 1, m). Эффек-ти технологий, т. е. кол-во конечной продукции (в ден. ед.), производ в ед. времени по j-й (j= 1,n) технологии, обозначим c_j. Пусть, далее, а_ij- — расход i-го ресурса в единицу времени по j-й технологии. В качестве неизвестной величины x_j при­мем интенсивность использ j-й технологии, т. е. вре­мя, в течение которого продукция произв-ся по j-й техно­логии. Пренебрегая временем переналадок, необход для перехода от одной технологии к другой, получаем следующую математическую модель задачи: найти план интенсивностей использования технологий х = (x_i;... ;х_n), обеспеч-ий макс выпуска прод в стоим-ом выраж: ∑a_ijx_j≤b_i (i=1,m)

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

 

 

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

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

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

∑ a_ijx_j≤ b_i, i=1,m₁

∑ a_ijx_j= b_i, i=m₁+1,m₂

∑ a_ijx_j≥ b_i, i=m₂+1,m, x_j≥ 0, j=1,m, x_j – произвольн., j= n₂+1,n

Симметр.ф.:

MaxF= ∑Cj*xj

∑ a_ijx_j≤ b_i, i=1,m_, x_j≥ 0, j=1,n или

MinF= ∑Cj*xj

∑ a_ijx_j≥ b_i, i=1,m, x_j≥ 0, j=1,n

Канонич.ф.:

Max(min)F= ∑Cj*xj

∑ a_ijx_j= b_i, i=1,m_, x_j≥ 0, j=1,n

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

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

Векторн:

Max(min)F= C*X

А₁X₁₊ А₂X_2+…+ А_nX_n=B; X≥0

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

Min f(x₁^*, x2^*… xn^*)= - max (-f(x₁^*, x2^*… xn^*))

 

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

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

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

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

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

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

n-прод-и; m-рес-сы; c_j,j=1,n – цена ед-цы прод. j-го вида; b_i,i=1,m – кол-во i-го рес-са; a_ij, j=1,n, i=1,m – кол. i-го рес-са, необход. для пр-ва прод-и j-го вида.Треб-ся опр-ть план пр-ва кажд.прод-и X*=(x₁*,x₂*…x_n*), при кот. обесп-ся max-ая выручка.

Цена общего V реал-ии:F=c₁x₁+c₂x₂+…+c_nx_n.

Расход на пр-во всех n видов прод-и не должен превышать b_i: a_i1x₁+a_i2x₂+…+a_inx_n≤b_i, i=1,m.

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

ЭММ:maxF=

x_j≥0

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

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