Инструменты пользователя

Инструменты сайта


examination:mo:question8

Вопрос №8. Нахождение и экономическая интерпретация двойственных оценок.

Представим, что у нас есть некоторое производство, которое производит m предметов в заданном количестве (<m>b_{1}, b_{2}, b_{3}, …, b_{m}</m>)

Существует n технологических способов их производства.

Каждый технологический способ будет характерисоваться вектором <m>А^j</m>

<m>А^j = (matrix{4}{1}{a_{1j} a_{2j} {…} a_{mj}})</m> <m>j = overline{1,n}</m>

m < n

<m>a_{ij} > 0 </m> - кол-во i-ых продуктов, произведенных j-ым способом в единицу времени

<m>a_{ij} < 0 </m> - кол-во i-ых продуктов, потребляемых j-ым техн. способом в единицу времени

<m>a_{ij} = 0 </m> - i-ый продукт не потребляется и не производится j-ым техн. способом

<m>с_{1}, с_{2}, с_{3}, …, с_{n}</m> - затраты на единицу времени для i-ого техн. процесса

Необходимо определить такую программу организации деятельности, чтобы произвести все продукты в заданном кол-ве при минимальных издержках

<m>(matrix{4}{1}{x_{1} x_{2} {…} x_{n}}) = X</m> - интенсивности использования каждого из технологических процессов для решения поставленной задачи

<m>A = (A^1 A^2 {…} A^n)</m> <m>b = (b_1 b_2 {…} b_m)^T</m>

Целевая функция (считает издержки): <m>z = c_1x_1+c_2x_2+{…}+c_n x_n</m>

<m>A^1x_1+A^2x_2+{…}+A^n x_n = b</m>

<m>x_1>=0;x_2>=0;{…};x_n>=0</m>

Канонический вид:

<m>lbrace{matrix{3}{1}{{min z=С^{T}x} {Ax=b} {X>=0}}}</m>

Допустим, у нас есть некоторое базисное решение (<m>X_B ; X_N</m>)

<m>X_B</m> -базис

<m>X_N</m> -не базис

Тогда ⇒

<m>delim{lbrace}{matrix{3}{1}{{min z=С^{T}_{B}x_{B} + С^{T}_{N}x_{N}} {BX_{B} + NX_{N}=b} {X_{B}>=0 X_{N}>=0}}}{}</m>

<m>A = ({B}under{m};{N}under{n-m}) ; C = (matrix{2}{1}c_b {C_{N}}}) X = (matrix{2}{1}x_b {X_{N}}})</m>

<m>{X_{B} = B^{-1}b; X_{N} = 0</m>

<m>С^{T}_{B}B^{-1}b</m> - издержки;

<m>С^{T}_{B}B^{-1}b = pi_{1}b_{1}+pi_{2}b_{2}+{…}+pi_{m}b_{m}</m> - это издержки, которые были потрачены при производстве b1 товаров 1ого продукта, b2 товаров 2ого продукта и т.д.

<m>С^{T}_{B}B^{-1} = pi^{T}</m>

<m>pi_{1} pi_{2} {…} pi_{m}</m> - теневые цены (двойственные оценки, себестоимость)

<m>pi</m> будут разные для различных базисных решений,т.е. теневые цены неустойчивы

Далее необходимо сравнить издержки и цену для нашего базиса (<m>C_{j} и pi^{T}A^{j}</m>)

Если <m>C_{j} - pi^{T}A^{j} > 0</m> - такой способ в базисе не нужен

Если <m>C_{j} - pi^{T}A^{j} < 0</m> - этот способ можем ввсести в базис

Если <m>C_{j} - pi^{T}A^{j} = 0</m> - без разницы

Из условия «<0» нужно выбрать самый оптимальный и ввсести его в базис, т.к. он самый выгодный.

Замечание

  1. Указанное правило выбора претендентов на включение в базис полностью соотвествует правилу выбора ведущего столбца с симплекс методе <m>hat{C_{j}} =C_{j}- pi^{T}A^{j}</m>(*)
  2. <m>pi^{T}</m> - это элементы двойственной задачи (двойственные переменные). Экономическая интерпритация двойственных переменных - это теневая цена
  3. В процессе рещения прямой задачи симплекс методом происходит одновременное решение двойственной задачи (Как только выполнится условие (*) окончания процесса, текущее значение <m>pi</m> и будет оптимальным решением двойственной задачи)
  4. Наряду с прямым симплекс методом существует двойственный симплекс-метод, он отличается тем, что стоит последовательность допустимых решений до тех пор, пока не будет построено допустимое решение поставленной задачи
examination/mo/question8.txt · Последние изменения: 2014/01/15 08:19 (внешнее изменение)