Сформулируйте экономический смысл двойственной задачи ЗЛП

С экономической точки зрения двойственную задачу можно интерпретировать так: какова должна быть цена единицы каждого из ресурсов, чтобы при заданных количествах ресурсов bi и величинах стоимости единицы продукции Cj минимизировать общую стоимость затрат? А исходную задачу определим следующим, образом: сколько и какой продукции xj(j =1,2,…, n) необходимо произвести, чтобы при заданных стоимостях Cj (j=1,2,…, n) единицы продукции и размерах имеющихся ресурсов bi(i=1,2,…, n) максимизировать выпуск продукции в стоимостном выражении. Большинство задач линейного программирования изначально определяются как исходные или двойственные задачи. Сделав вывод можно говорить о паре двойственных задач линейного программирования.

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

F=c1x1+c2x2+…cnxn

при условиях

Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:

1. Целевая функция исходной задачи задается на максимум, а целевая функция двойственной на минимум.

2. Матрица

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

в двойственной задаче получаются друг из друга транспонированием (т.е. заменой строк столбцами, а столбцов - строками).

3. Число переменных в двойственной задаче равно числу ограничений в системе исходной задачи, а число ограничений в системе двойственной задачи - числу переменных в исходной задаче.

4. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе исходной задачи, а правыми частями в соотношениях системы двойственной задачи - коэффициенты при неизвестных в целевой функции исходной задачи.

5. Если переменная xj исходной задачи может принимать только лишь положительные значения, то j-е условие в системе двойственной задачи является неравенством вида «>». Если же переменная xj может принимать как положительные, так и отрицательные значения, то 1 -соотношение в системе представляет собой уравнение. Аналогичные связи имеют место между ограничениями исходной задачи и переменными двойственной задачи. Если i - соотношение в системе исходной задачи является неравенством, то i-я переменная двойственной задачи . В противном случае переменная уj может принимать как положительные, так и отрицательные значения.

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

Двойственная задача тесно связана задачей линейного программирования. Задача первоначальная называется исходной. Решение двойственной задачи может быть получено из решения исходной и наоборот. Связующим фактом этих двух задач являются коэффициенты Cjфункции исходной задачи. Данные коэффициенты называются свободными членами системы ограничений двойственной задачи. Коэффициенты Bi системы ограничений исходной задачи называются коэффициентами двойственной задачи. Транспонированная матрица коэффициентов системы ограничений исходной задачи является матрицей коэффициентов системы ограничений двойственной задачи.

Рассмотрим задачу использования ресурсов. У предприятия есть t видов ресурсов в количестве bi (i=1, 2,…, m) единиц, из которых выпускается n видов продукции. На изготовление 1 ед. i-й продукции тратится aij ед. t-гo ресурса, ее стоимость составляет Cj ед. Необходимо определить план выпуска продукции, обеспечивающий ее максимальный выпуск в стоимостном выражении. Примем за xj (j=1,2,…, n) количество ед. j-й продукций и составляет максимальное значение линейной функции

Z=C1x1+C2x2+ … +Cnxn

Определим ресурсы, которые потребуются для изготовления товара. Обозначим за единицу стоимости ресурсов единицу стоимости выпускаемого товара. А через уi (j=1,2,…, m) стоимость единицы i-го ресурса. Т.е. стоимость всех затраченных ресурсов, которые используются для изобретения единицы j-й продукции, составляет. Цена израсходованных ресурсов не должна превышать цены окончательного товара.

4.Запишите ЗЛП для игры 3х3?

Итак, пусть дана матричная игра с матрицей А порядка m х n. Согласно свойству 7 оптимальные смешанные стратегии х = (х1, ..., хm), y = (y1, ..., yn) соответственно игроков 1 и 2 и цена игры u должны удовлетворять соотношениям.

Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru

Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru

Разделим все уравнения и неравенства в (1) и (2) на u (это можно сделать, т.к. по предположению u > 0) и введём обозначения :

Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru , Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru ,

Тогда (1) и (2) перепишется в виде :

Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru , Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru , Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru , Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru ,

Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru , Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru , Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru , Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru .

Поскольку первый игрок стремится найти такие значения хi и, следовательно, pi , чтобы цена игры u была максимальной, то решение первой задачи сводится к нахождению таких неотрицательных значений pi Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru , при которых

Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru , Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru . Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru

Поскольку второй игрок стремится найти такие значения yj и, следовательно, qj, чтобы цена игры u была наименьшей, то решение второй задачи сводится к нахождению таких неотрицательных значений qj, Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru , при которых

Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru , Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru . Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru

Формулы ( 3 ) и (4) выражают двойственные друг другу задачи линейного программирования (ЛП).

Решив эти задачи , получим значения pi Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru , qj Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru и u.Тогда смешанные стратегии, т.е. xi и yj получаются по формулам :

Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru

Пример. Найти решение игры , определяемой матрицей.

Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru

При решении этой игры к каждому элементу матрицы А прибавим 1 и получим следующую матрицу

Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru

Составим теперь пару взаимно-двойственных задач :

Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru

Решим вторую из них

Б.п. q1 q2 q3 q4 q5 q6 Решение a Отношение
  -1 -1 -1 -3  
q4
q5 Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru
q6
Б.п. q1 q2 q3 q4 q5 q6 Решение a Отношение
  -1  
q4 Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru
q3
q6 Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru
Б.п. q1 q2 q3 q4 q5 q6 Решение a Отношение
  Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru  
q2 Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru  
q3  
q6 Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru  

Из оптимальной симплекс-таблицы следует, что Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru

(q1, q2, q3) = (0; Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru ; 1),

а из соотношений двойственности следует, что

( p1, p2, p3) = ( Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru ; 1; 0).

Следовательно, цена игры с платёжной матрицей А1 равна

Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru . Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru ,

а игры с платёжной матрицей А :

Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru .

При этом оптимальные стратегии игроков имеют вид:

Х = (х1, х2, х3) = (uр1; uр2; uр3) = Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru = Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru

Y = (y1, y2, y3) = (uq1; uq2; uq3) = Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru = Сформулируйте экономический смысл двойственной задачи ЗЛП - student2.ru .

5.Выпишите е12х для ПФКД.

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