Запись оптимального решение двойственной задачи по оптимальному решению прямой задачи. Краткий анализ оптимального решения прямой задачи

Решая прямую задачу, мы одновременно получаем и решение двойственной задачи. Симплексный метод обладает такой особенностью, что при решении одной из двойственной пары автоматически получается решение другой задачи без дополнительных вычислений Z_max = T_min (значения целевых функций прямой и двойственной задачи совпадают).

Оценки дополнительных переменных прямой задачи полностью совпадают со значениями основных переменных двойственной задачи. Эти величины получили название двойственных оценок (объективно-обусловленных оценок) ограниченных ресурсов.

Y_i - условные цены соответствующих ресурсов (теневые цены).

То есть, значение основной первой переменной Y₁ двойственной задачи равно значению оценки дополнительной переменной, введенной в первое ограничение прямой задачи. Значение основной второй переменной Y₂ двойственной задачи равно значению оценки дополнительной переменной, веденной во второе ограничение прямой задачи и т.д.

Значение первой дополнительной переменной двойственной задачи равно значению оценки первой основной переменной прямой задачи. Значение второй дополнительной переменной двойственной задачи равно значению оценки второй основной переменной прямой задачи и т.д.

Коэффициенты a_ij в первой (исходной) симплексной таблице представляют собой технико-экономические коэффициенты. В процессе решения они претерпевают значительные изменения. Из нормативов, характеризующих затраты производственных ресурсов, они превращаются в коэффициенты замещения или пропорциональности.

Каждый из них представляет величину уменьшения (а_ij> 0) или увеличения (а_ij< 0) соответствующей i-й базисной переменной при введении в базис j-й основной свободной переменной.

Коэффициенты целевой функции C_j характеризуют прямой эффект введения в базис j -й переменной с единичной интенсивностью. В зависимости от смысла той или иной переменной планово-экономической задачи величина Cj может быть положительной, отрицательной или равной нулю.

Величина (для j, не входящих в базис) характеризует косвенный эффект введения в базис j-й свободной переменной. Она показывает, на сколько уменьшится целевая функция за счет изменения базисных переменных при введении в базис j-й небазисной переменной единичной интенсивности.

Разность C_j-Z_j=-D_j представляет собой чистый эффект, получаемый при введении в базис j-й переменной. При этом целевая функция возрастает на величину прямого и уменьшается на величину косвенного эффекта.

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

Пример

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

Рассмотрим следующую задачу: в хозяйстве имеется 200 га орошаемой и 500 га богарной пашни. Предполагается возделывать на этих участках турнепс и подсолнечник на силос. Трудовые ресурсы хозяйства 12000 чел.-дн., ресурс поливной воды – 500 тыс. м³.

Таблица. Эффективность возделывания с.-х. культур.

Показатель	Турнепс	Подсолнечник
на богаре	на поливе	на богаре	на поливе
1. Затраты труда на 1га, чел.-дн.
2. Норма полива, тыс.м3/га	-		-
3. Выход кормов, ц к.ед./га

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

Составим задачу линейного программирования.

Определить значения переменных:

Х₁, га – площадь посева турнепса на богаре;

Х₂, га – площадь посева турнепса на поливе;

Х₃, га – площадь посева подсолнечника на богаре;

Х₄, га – площадь посева подсолнечника на поливе,

которые обеспечат получение максимального значения целевой функции Z, ц к.ед. max Z = 30 Х₁+50 Х₂+22 Х₃+60 Х₄

при условиях:

баланс богарной пашни, га: Х₁+Х₃ £ 500

баланс орошаемой пашни, га: Х₂+Х₄ £ 200

баланс трудовых ресурсов, чел.-дн., 40 Х₁+50 Х₂+20 Х₃+30 Х₄ £ 12000

баланс ресурсов воды для полива, тыс.м³: Х₂+2Х₄ £ 500

Х_j ³ 0, ( j = 1¸ 4).

Приведем задачу к каноническому виду и занесем в первую симплексную таблицу исходное опорное решение.

Первая симплексная таблица

№1

Cj

Ci

П БП

аi0

X1

X2

X3

X4

X5

X6

X7

X8

C0

X5

-

X6

I*

X7

X8

Z

Dj

-30

-50

-22

-60

Х

J*

 

Решим задачу симплексным методом, оптимальное решение получим в четвертой симплексной таблице (задачу решали в полных таблицах).

Последняя симплексная таблица

№4	Cj
Ci	П БП	аi0	X1	X2	X3	X4	X5	X6	X7	X8
	X5		-1	-1				3/2	-1/20
	X4
	X3							-3/2	1/20
	X8			-1				-2
Z	D j								11/10

 

В таблице приведено оптимальное решение (единственное):

 

Максимальное количество кормов – 18600 ц к.ед. будет получено при возделывании подсолнечника на силос на богаре на площади 300 га и на поливе на площади 200 га. При этом недоиспользуется 200 га богарной пашни и 100 тыс. м³ воды для полива. Полностью используются трудовые ресурсы (X₇=0) и орошаемая пашня (X₆ = 0). Турнепс на корм не возделывается (X₁ =0, X₂ = 0).

Каждой прямой задаче линейного программирования можно поставить в соответствие двойственную. Рассмотрим экономический смысл двойственной задачи.

Переменные Y₁, Y₂, Y₃, Y₄ – условные цены соответствующих ресурсов. Необходимо определить оптимальный план ^*(Y₁, Y₂, Y₃, Y₄) при условиях: Y₁+40Y₃ ³ 30

Y₂+ 50Y₃ + Y₄ ³ 50

Y₁+ 20Y₃ ³ 22

Y₂ +30Y₃ + 2Y₄ ³ 60

Y_i ³ 0, i = 1¸ 4

min T = 500Y₁+ 200Y₂ + 12000Y₃+ 500Y₄

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

 

Решим Y-задачу М-методом.

Найти

при условиях:

Y₁+ 40Y₃ - Y₅+ W₁=30

Y₂+ 50Y₃ + Y₄ – Y₆ + W₂ = 50

Y₁+ 20Y₃ – Y₇ + W₃ = 22

Y₂ +30Y₃ + 2Y₄ – Y₈ + W₄ = 60

Y_i ³ 0, i = 1¸ 8; W_i ³ 0, i = 1¸ 4

Последняя симплексная таблица М-задачи.

Cj

-500

-200

-12000

-500

Сi

П БП

ai0

Y1

Y2

Y3

Y4

Y5

Y6

Y7

Y8

-12000

Y3

11/10

1/20

-1/20

Y6

-1

-1

Y5

-2

-200

Y2

-3/2

3/2

-1

Z

D j

-18600

 

Так как искусственные переменные W_i = 0, i = 1 ¸ 4, то их в таблицу записывать не стали.

Сопоставляя конечные симплексные таблицы прямой и двойственной задач можно заметить, что нет необходимости решать их отдельно. Решая прямую задачу, мы одновременно получаем и решение двойственной задачи. Симплексный метод обладает такой особенностью, что при решении одной из двойственной пары автоматически получается решение другой задачи без дополнительных вычислений Z_max = T_min = 18600 (значения целевых функций прямой и двойственной задачи совпадают).

Оценки свободных дополнительных переменных полностью совпадают со значениями переменных, вошедших в базис двойственной задачи: Y₁ =D₅, Y₂ =D₆, Y₃ =D₇, Y₄ =D₈, (Y₅ =D₁, Y₆ =D₂, Y₇ =D₃, Y₈ =D₄).

Эти величины получили название двойственных оценок (объективно-обусловленных оценок) ограниченных ресурсов.

Y_i - условные цены соответствующих ресурсов.

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

Это позволяет установить пропорции взаимозаменяемости ресурсов, оценить их важность, эффективность с точки зрения критерия оптимальности, выявить " узкие места" и вскрыть внутренние резервы плана. Рассмотрим двойственные оценки нашей задачи.

Богарная пашня и ресурс поливной воды (x₅ и x₈) недоиспользуются, т.е. их имеется больше, чем нужно, поэтому их оценки равны нулю (У₁ = 0, У₄ = 0). При нулевой оценке ресурса изменение его объема в пределах избыточности не вызовет никаких колебаний в структуре производства и не повлияет нa значение целевой функции. Приобретение лишней единицы избыточного ресурса всегда уменьшает доход хозяйства, так как она остается неиспользованной. Ресурсы, используемые в полном объеме, всегда имеют положительную оценку.

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

В нашем примере полностью используются орошаемая пашня и трудовые ресурсы, наибольшее значение имеет ресурс " орошаемая пашня" (оценка D₆ = 27, а D₇ =11/10). Чтобы выяснить, что означает здесь двойственные оценки, рассмотрим экономическое содержание всех показателей симплексной таблицы.

Проведем такой анализ для полученного оптимального плана Х-задачи.

Площадь орошаемой пашни используется в решении полностью (х₆ =0). Пусть небазисная переменная x₆ войдет в базис с единичной интенсивностью: x₆=1 (т.е. недоиспользуется I га орошаемой пашни, ресурс составит 199 га). Это приведет к следующим изменениям в оптимальном плане (см. коэффициенты в столбце x₆ последней симплексной таблицы).

Площадь подсолнечника на орошаемой пашни (x₄) сократится на 1гa (a₂₆=1), площадь подсолнечника на богаре (х₃) увеличится на 3/2 га (a₃₆ = -3/2), недоиспользование богарной пашни (х₅) сократится на 3/2 га (a₁₆ = 3/2), освободится 2 тыс.м³ поливной воды (a₄₆ = -2).

Тогда сокращение посевов х₄ приведет к потерям кормов в размере 60 ц к.ед. (С₄), а за счет увеличения посевов х₃ будет произведено 3/2 * 22 = 33 ц к.ед. (С₃ = 22). В результате производство кормов сократится на 60 - 33 = 27 (ц к.ед, ). Это и есть D₆ -оценка данного ресурса. Следовательно, эта оценка показывает, сколько кормов производится в расчете на I га орошаемой пашни (при сложившейся структуре производства) или сколько дополнительной продукции можно будет получить, привлекая дополнительно единицу данного ресурса.

Мы изменяли объем только одного вида ресурса: орошаемой пашни, а объем трудовых ресурсов не менялся. Не повлияют ли изменения в оптимальном плане на использование труда? На каждый гектар подсолнечника, возделываемого при орошении, затрачивается 30 чел./дн., а на богаре - 20 чел./дн., следовательно, при сокращении посевов на орошаемой пашне освобождается 30 чел./дн. труда и их можно использовать для выращивания подсолнечника на площади 1, 5 га (1, 5x20= 30 чел./дн.). Таким образом, увеличение посевов подсолнечника на богаре будет обеспечено трудовыми ресурсами.

Аналогично можно провести анализ и по коэффициентам переменной х₇ (трудовые ресурсы).

⇐ Предыдущая12345Следующая ⇒

Поделиться: