Шпаргалка по "Математическому программированию"

5. Коэффициенты при переменных в ограничениях двойственной задачи получаются транспонированием матрицы, составленной из

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

6. Свободные члены исходной задачи являются коэффициентами при

переменных  в функции цели двойственной задачи, а свободными

членами в  двойственной задаче – коэффициенты при переменных в

функции исходной задачи.Отметим также, что соотношение двойственности взаимное, т.е. задача, двойственная по отношению к двойственной, совпадает с исходной.Двойственные пары задач подразделяются на симметричные и несимметричные. В симметричной паре ограничения прямой и двойственной задач являются нестрогими неравенствами и, следовательно, переменные обеих задач могут принимать только неотрицательные значения.

59. Построение двойственных  задач к исходным  задачам, записанным  в стандартной,  канонической и  общей форме модели(построение симметричных и несимметричных двойств. задач) 

Стандартная форма (исходная)

  _n

Σ a_ijx_j ≤ b_i, i=1,n(1)

 ^j=1

x_j≥0, j=1,n(2)

       _n

z = Σ c_jx_j ->max(3)

      ^j=1

Двойственная  стандартная

  _m

Σ a_ijy_i ≤ c_j, j=1,n(1)

 ⁱ⁼¹

y_i≥0, j=1,m(2)

       _m

F = Σ b_iy_i ->min(3)

      ⁱ⁼¹

Исходная задача в канонической форме:

  _n

Σ a_ijx_j = b_i, i=1,m(1)

 ^j=1

x_j≥0, j=1,n(2)

       _n

z = Σ c_jx_j ->min(3)

      ^j=1

Двойственная  каноническая 
 

  _m

Σ a_ijy_i ≤ c_j, j=1,n(1)

 ⁱ⁼¹

y_i- любые (2)

       _m

F = Σ b_iy_i ->max(3)

      ⁱ⁼¹ 

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

 

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

Несимметричные  двойственные задачи.

Возьмем ЗЛП на максимум в канонической форме:

Max Z=(n;j=1)Σcj*xj

(n;j=1)Σaij*xj=bi  (i=1,m)

Xj>=0  (j=1,n). 

 

60.Основная  и вторая  теорема двойственности (сформулировать теоремы и разъяснить)

 Первая  теорема двойственности.

Теорема: если одна из двойственных задач имеет  оптимальный план, то и другая решима, т.е. имеет опт.план. При этом экстремальные значен.целевых функций совпадают (j=от 1 до n) Σcjxj*= (i=от 1 до m)Σbiyi*  если в исходн. задаче целевая функция неограниченна на множестве планов, то в двойственной задаче система ограничений несовместна.

Вторая теорема  двойственности и ее эконом.интерпритация.

Для того, чтобы  допустимые решения пары двойственных задач были оптимальными, необходимо и достаточно выполнение условия: xj*(∑aij yi*-cj)=0, j от 1 до n, yi*(∑aij xj*-bi)=0, I от 1 до m. Это условия дополняющей нежесткости. Из них следует: если какое-либо ограничение двойств.задачи обращ-ся оптималь.планом в строгое равенство, то соответствующая компонента опт. плана двойственной задачи должно равняться нулю.Если же какая-то  компонента опт. плана равна нулю, то соответствующее ограничение двойств.задачи обращается опт.планом в строгое равенство   хj*>0 следовательно (i= от 1 до m)Σaij yi*=cj   (затраты на пр-во продукции=цене) – Если продукция вошла в опт.план, то если затраты>цены, объем пр-ва=0 Σaij yi* >cj следовательно xj*=0 

yi*>0 следовательно  (j=от 1 до n) Σaij xj*=bi (рас-ды рес-ов =запас  рес-ов).

(j=от 1 до n) Σaij xj* <bi следовательно yi*=0

Смысл теоремы  сводится к следующему:

-если стоимост.оценка  рес-ов расход-х на пр-во ед.прод-ии=цене, то этот вид прод-ии входит  в оптим.план ;

-если затраты  превышают цену, то прод-ию производить  не следует;

- еслирасход  рес-ов=запасу, то стоимост.оценка этого рес-са положительна. Такой рес-с наз-ся дефицитным.  Наибелее дефицит.рес-с обладает наибольшей оценкой;

-если рес-с  израсходован неполностью, то  его стоимост.оценка = 0.

 

61. Построение оптимального  опорного плана  двойственной задачи по симплексной таблице исходной задачи

Информация  из столбцов обратной матрицы линейных преобразований, приведших к оптимальному результату. Из столбцов матрицы D-1 можно почерпнуть весьма полезную информацию.

Столбец A3: «теневая» цена ресурса S2 равна y01=0, столбец остался

единичным и  по первой строке можно прочесть, что x3=9, т.е. при реализации найденного оптимального плана 1-й ресурс окажется в избытке, причем этот избыток (недоиспользование) как раз составит 9 условных единиц.

Столбец A4: «теневая» цена ресурса S2 равна y02=1, ресурс будет полностью использован и его возможное увеличение будет вести к увеличению целевой функции (т.е. дохода). И т.к. y02=1, то увеличение ресурса S2 на 1 у.е. будет давать добавку по доходу на .Z = y02· .в2 = = 1.1 = 1 (тыс. грн.) (здесь .в2 -приращение ресурса S2 и .Z - соответствующее приращение дохода ). При таком приращении ресурса S2 максимальный доход уже составит Zmax=58 тыс. грн. + 1 тыс. грн = 59 тыс. грн. На рис. 6.2 проиллюстрирована эта ситуация, комментарий по отношению к которой будет приведен ниже. Из столбца A4 еще следует, что при увеличении ресурса S2 на 1 у.е. для новой оптимальной точки выпуск товара T1 сократится на ½ тонны (на пересечении строки базисной переменной x1 и столбца A4 стоит «-1/2»), а выпуск товара T2 увеличится на 3/2 тонны (т.к. в строке с базисной переменной x2 в столбце A4 имеем «3/2»).Сказанное по столбцу A4 будет ниже прокомментировано с помощьюграфических построений (рис. 6.2).Столбец A5: «теневая» цена ресурса S3 равна y03=2. Это означает, чтоувеличение ресурса S3 на 1 у.е. принесет добавку по Z на .Z = y03· .в3 = 2.1 =2(тыс. грн.) и составит Zmax=58 тыс. грн. + 2 тыс. грн = 60 тыс. грн. При этом, как следует из столбика A5 табл. 3, выпуск T1 увеличится на ½ тонны, а T2 уменьшится на ½ тонны. Запас по сырью S1 (см. 1-ю строку) увеличится на 3/2 у.е.

62. Идея метода динамического програмирования и его геометрическая интерпретация. Принцип оптимальности Беллмана.

Оптимальное решение задачи методом динамического  программирования находится на основе функционального уравнения

fn-1(Sl)=optimum(Rl+1(Sl,Ul+1)+fn-(l+1)(Sl+1))        (1)

                          ul+1

(l=0,n-1)

Чтобы определить его, необходимо:

1.записать  функциональное уравнение для   последнего состояния процесса (ему соответствует l=n-1)

fn-1(Sl-1)=optimum(Rn(Sn-1,Un)+f0(Sn))       

                          ul+1

2.найти  Rn(Sn-1,Un) из дискретного набора  его значений при некоторых  фиксированных Sn-1 и Un из соответствующих   допустимых областей (так как  f0(Sn)=0, то f1(Sn-1)= optimum(Rn(Sn-1,Un)      

                          Un

В результате  после первого шага известно решение Un и соответствующее значение функции   f1(Sn-1)

3.Уменьшить  значение l на единицу и записать  соответствующее функциональное  уравнение. При l=n-k (k= 2,n) оно имеет вид

fk(Sn-k)=optimum(Rn-k+1(Sn-k,Un-k+1)+fk-1(Sn-k+1))    (2)   

                          Un-k+1

4.найти  условно-оптимальное решение на  основе выражения (2)

5.проверить,  чему равно значение l.Если l=0, расчет  условно-оптимальных решений закончен, при этом найдено оптимальное решение задачи для первого состояния процесса. Если l не равно 0, перейти к выполнению п.3.

6.Вычислить  оптимальное решение задачи для  каждого последующего шага процесса, двигаясь от конца расчетов  к началу.

Метод динам программ позволяет одну задачу со многими переменными заменить рядом последовательно решаемых задач с меньшим числом переменных. Решение осуществляется по шагам. Основной принцип, на котором базируется оптимизация  многошагового процесса, а также особенности вычислительного метода—принцип оптимальности Беллмана.

Оптимальное поведение обладает тем свойством, что каковы бы ни были начальное  состояние и начальное решение, последующие решения должны быть оптимальными относительно состояния, полученного в результате первоначального решения.