Модель сельскохозяйственного производства на Нарвских островах для внешнего рынка

 

Транспонированная матрица AT:

1	0	2	0.2	6
0	1	3	0.2	6
1	0	3	0.1	8
0	1	3	0.1	5
1	0	3	0.3	4
0	1	2	0.3	5
1400000	1200000	5600000	700000	0

Условиям неотрицательности переменных исходной задачи соответствуют неравенства-ограничения двойственной, направленные в другую сторону. И наоборот, неравенствам-ограничениям в исходной соответствуют условия неотрицательности в двойственной.

Неравенства, соединенные стрелочками (↔), называются сопряженными.

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

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

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

Левая часть ограничений определяет стоимость ресурсов в теневых (альтернативных) ценах, затраченных на xj:

y1+2y3+0.2y4≥6

y2+3y3+0.2y4≥6

y1+3y3+0.1y4≥8

y2+3y3+0.1y4≥5

y1+3y3+0.3y4≥4

y2+2y3+0.3y4≥5

1400000y1+1200000y2+5600000y3+700000y4 → min

y1 ≥ 0, y2 ≥ 0, y3 ≥ 0, y4 ≥ 0

 

Исходная задача I		Двойственная задача II
x1 ≥ 0	↔	y1+2y3+0.2y4≥6
x2 ≥ 0	↔	y2+3y3+0.2y4≥6
x3 ≥ 0	↔	y1+3y3+0.1y4≥8
x4 ≥ 0	↔	y2+3y3+0.1y4≥5
x5 ≥ 0	↔	y1+3y3+0.3y4≥4
x6 ≥ 0	↔	y2+2y3+0.3y4≥5
6x1+6x2+8x3+5x4+4x5+5x6 → max	↔	1400000y1+1200000y2+5600000y3+700000y4 → min
x1+x3+x5≤1400000	↔	y1 ≥ 0
x2+x4+x6≤1200000	↔	y2 ≥ 0
2x1+3x2+3x3+3x4+3x5+2x6≤5600000	↔	y3 ≥ 0
0.2x1+0.2x2+0.1x3+0.1x4+0.3x5+0.3x6≤700000	↔	y4 ≥ 0

 

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

Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.

Из первой теоремы двойственности следует, что Y = C*A-1.

Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

 

 

Определив обратную матрицу D = А-1 через алгебраические дополнения, получим:

 

 

Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных .

Тогда Y = C*A-1 = 

 

 

Оптимальный план двойственной задачи равен:

 

y1 = 2; y2 = 1; y3 = 2; y4 = 0.

Z(Y) = 1400000*2+1200000*1+5600000*2+700000*0 = 15200000

 

Если существуют такие допустимые решения X и Y прямой и двойственной задач, для которых выполняется равенство целевых функций F(x) = Z(y), то эти решения X и Y являются оптимальными решениями прямой и двойственной задач соответственно.

 

 

 

5. Анализ модели на чувствительность

 

 

Проведем определение дефицитных и недефицитных (избыточных) ресурсов. Для этого используем вторую теорему двойственности. 

Подставим оптимальный план прямой задачи в систему ограниченной математической модели:

 

1*1000000 + 0*0 + 1*400000 + 0*0 + 1*0 + 0*1200000  =

= 1400000 = 1400000;

0*1000000 + 1*0 + 0*400000 + 1*0 + 0*0 + 1*1200000  =

= 1200000 = 1200000;

2*1000000 + 3*0 + 3*400000 + 3*0 + 3*0 + 2*1200000  =

= 5600000 = 5600000;

0.2*1000000 + 0.2*0 + 0.1*400000 + 0.1*0 + 0.3*0 + 0.3*1200000  =

= 600000 < 700000.

1-ое ограничение прямой  задачи выполняется как равенство. Это означает, что 1-ый ресурс полностью  используется в оптимальном плане, является дефицитным и его  оценка согласно второй теореме  двойственности отлична от нуля (y1>0).

2-ое ограничение прямой  задачи выполняется как равенство. Это означает, что 2-ый ресурс полностью  используется в оптимальном плане, является дефицитным и его  оценка согласно второй теореме  двойственности отлична от нуля (y2>0).

3-ое ограничение прямой задачи выполняется как равенство. Это означает, что 3-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y3>0).

4-ое ограничение выполняется  как строгое неравенство, т.е. ресурс 4-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y4 = 0.

Неиспользованный экономический резерв ресурса 4 составляет 100000 (700000-600000).

Этот резерв не может быть использован в оптимальном плане, но указывает на возможность изменений в объекте моделирования (например, резерв ресурса можно продать или сдать в аренду).

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

При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим:

 

1*2 + 0*1 + 2*2 + 0.2*0  = 6 = 6

0*2 + 1*1 + 3*2 + 0.2*0  = 7 > 6

1*2 + 0*1 + 3*2 + 0.1*0  = 8 = 8

0*2 + 1*1 + 3*2 + 0.1*0  = 7 > 5

1*2 + 0*1 + 3*2 + 0.3*0  = 8 > 4

0*2 + 1*1 + 2*2 + 0.3*0  = 5 = 5

 

1-ое ограничение двойственной  задачи выполняется как равенство. Это означает, что 1-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x1>0).

2-ое ограничение выполняется  как строгое неравенство, т.е. ресурс 2-го вида использовать экономически  не выгодно. И действительно в  оптимальном плане прямой задачи x2 = 0.

Поскольку теневая (альтернативная) цена больше рыночной цены этого продукта, то выгоднее продать ресурсы по рыночным ценам.

При этом разница между ценами (7 - 6 = 1) показывает величину изменения целевой функции F(x) при введении дополнительной единицы xi.

3-ое ограничение двойственной  задачи выполняется как равенство. Это означает, что 3-ый ресурс экономически  выгодно использовать, а его использование  предусмотрено оптимальным планом  прямой задачи (x3>0).

4-ое ограничение выполняется как строгое неравенство, т.е. ресурс 4-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x4 = 0.

Поскольку теневая (альтернативная) цена больше рыночной цены этого продукта, то выгоднее продать ресурсы по рыночным ценам.

При этом разница между ценами (7 - 5 = 2) показывает величину изменения целевой функции F(x) при введении дополнительной единицы xi.

5-ое ограничение выполняется  как строгое неравенство, т.е. ресурс 5-го вида использовать экономически  не выгодно. И действительно в оптимальном плане прямой задачи x5 = 0.

Поскольку теневая (альтернативная) цена больше рыночной цены этого продукта, то выгоднее продать ресурсы по рыночным ценам.

При этом разница между ценами (8 - 4 = 4) показывает величину изменения целевой функции F(x) при введении дополнительной единицы xi.

6-ое ограничение двойственной  задачи выполняется как равенство. Это означает, что 6-ый ресурс экономически  выгодно использовать, а его использование  предусмотрено оптимальным планом  прямой задачи (x6>0).

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

Определим чувствительность решения к изменению коэффициентов целевой функции.

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

Пусть каждое значение параметра целевой функции изменится на ∆ сi. Найдем интервалы, при которых будет экономически выгодно использование ресурсов.

Допустимые диапазоны изменения коэффициентов в целевой функции определятся из соотношений:

3-ый параметр целевой  функции может изменяться в  пределах:

 

∆c3- = min [yk/d3k] для d3k>0.

∆c3+ = |max [yk/d3k]| для d3k<0.

 

 

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

Таким образом, 3-параметр может быть уменьшен на 2   или увеличен на 0.5.

Интервал изменения равен:

 

(c3 - ∆c3-; c3 + ∆c3+)

[8-2; 8+0.5] = [6;8.5]

 

Если значение c3 будет лежать в данном интервале, то оптимальный план не изменится.

1-ый параметр целевой  функции может изменяться в  пределах:

 

∆c1- = min [yk/d1k] для d1k>0.

∆c1+ = |max [yk/d1k]| для d1k<0.

 

 

 

Таким образом, 1-параметр может быть уменьшен на 0.5 или увеличен на 2.

Интервал изменения равен:

 

(c1 - ∆c1-; c1 + ∆c1+)

[6-0.5; 6+2] = [5.5;8]

 

Если значение c1 будет лежать в данном интервале, то оптимальный план не изменится.

6-ый параметр целевой  функции может изменяться в  пределах:

∆c6- = min [yk/d6k] для d6k>0.

∆c6+ = |max [yk/d6k]| для d6k<0.

 

 

Таким образом, 6-параметр может быть уменьшен на 1 или увеличен на 0

Интервал изменения равен:

 

(c6 - ∆c6-; c6 + ∆c6+)

[5-1; 5+0] = [4;5]

 

Если значение c6 будет лежать в данном интервале, то оптимальный план не изменится.

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

Из теоремы об оценках известно, что колебание величины bi приводит к увеличению или уменьшению f(X).

Оно определяется величиной yi в случае, когда при изменении величин bi значения переменных уi в оптимальном плане соответствующей двойственной задачи остаются неизменными.

Поэтому необходимо найти такие интервалы изменения каждого из свободных членов системы ограничений исходной ЗЛП, в которых оптимальный план двойственной задачи не менялся бы.

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

1-ый запас может изменяться  в пределах:

 

∆b1- = min [xk/dk1] для dk1>0.

∆b1+ = |max [xk/dk1]| для dk1<0.

 

 

Таким образом, 1-ый запас может быть уменьшен на 333333.33 или увеличен на 200000.

Интервал изменения равен:

(b1 - ∆b1-; b1 + ∆b1+)

[1400000-333333.33; 1400000+200000] = [1066666.67;1600000]

 

2-ый запас может изменяться  в пределах:

∆b2- = min [xk/dk2] для dk2>0.

∆b2+ = |max [xk/dk2]| для dk2<0.

 

 

 

Таким образом, 2-ый запас может быть уменьшен на 500000 или увеличен на 200000.

Интервал изменения равен:

  (b2 - ∆b2-; b2 + ∆b2+)

[1200000-500000; 1200000+200000] = [700000;1400000]

 

3-ый запас может изменяться в пределах:

 

∆b3- = min [xk/dk3] для dk3>0.

∆b3+ = |max [xk/dk3]| для dk3<0.

 

 

Таким образом, 3-ый запас может быть уменьшен на 400000 или увеличен на 1000000.

Интервал изменения равен:

(b3 - ∆b3-; b3 + ∆b3+)

[5600000-400000; 5600000+1000000] = [5200000;6600000]

 

Нижняя граница для: ∆b-4

 

∆b-4 = min[xk/dk4] для dk4>0.

 

 

Таким образом, 4-ый запас может быть уменьшен на 100000.

4-ый вид ресурса в  оптимальном плане недоиспользован, является недефицитным. Увеличение  данного ресурса приведет лишь  к росту его остатка. При этом  структурных изменений в оптимальном  плане не будет, так как двойственная оценка y4 = 0. Другими словами, верхняя граница b+4 = +∞.

Интервал изменения равен:

 

(b4 - ∆b4-; ∞)

[700000-100000; +∞] = [600000;+∞]

 

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

x4 может изменяться в пределах:

 

-1000000 ≤ ∆b4 ≤ 400000

[700000-400000; 700000] = [300000;700000].