Контрольная работа по "Экономико-математическое моделирование"

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5
x1	40	1	0	1/5	-1/6	0
x2	20	0	1	-1/5	1/3	0
x5	40	0	0	3/5	-15/6	1
F(X2)	1700	0	0	1	31/3	0

  1. Проверка критерия оптимальности. 
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи. 
 Окончательный вариант симплекс-таблицы:

Базис	B	x1	x2	x3	x4	x5
x1	40	1	0	1/5	-1/6	0
x2	20	0	1	-1/5	1/3	0
x5	40	0	0	3/5	-15/6	1
F(X3)	1700	0	0	1	31/3	0

Оптимальный план можно записать так: 
x1 = 40 
x2 = 20 
F(X) = 30•40 + 25•20 = 1700 
 Анализ оптимального плана. 
В оптимальный план вошла дополнительная переменная x5. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 3-го вида в количестве 40 
Значение 0 в столбце x1 означает, что использование x1 - выгодно. 
Значение 0 в столбце x2 означает, что использование x2 - выгодно. 
Значение 1 в столбце x3 означает, что теневая цена (двойственная оценка) равна 1. 
Значение 31/3 в столбце x4 означает, что теневая цена (двойственная оценка) равна 31/3.

 

 

 

 

Составим двойственную задачу к прямой задаче. 
10y1 + 6y2 + 5y3≥30 
5y1 + 6y2 + 8y3≥25 
500y1 + 360y2 + 400y3 → min 
y1 ≥ 0 
y2 ≥ 0 
y3 ≥ 0 
 Решение двойственной задачи дает оптимальную систему оценок ресурсов. 
 Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи. 
 Из теоремы двойственности следует, что Y = C*A-1. 
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

A = (A1, A2, A5) =

10 5 0 6 6 0 5 8 1

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

D = A-1 =

1/5 -1/6 0 -1/5 1/3 0 3/5 -11/6 1

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

(30, 25, 0) x

1/5 -1/6 0 -1/5 1/3 0 3/5 -11/6 1

= (1;10/3;0)

  Оптимальный план двойственной задачи равен: 
y1 = 1 
y2 = 31/3 
y3 = 0 
Z(Y) = 500*1+360*31/3+400*0 = 1700 
 Критерий оптимальности полученного решения. Если существуют такие допустимые решения X и Y прямой и двойственной задач, для которых выполняется равенство целевых функций F(x) = Z(y), то эти решения X и Y являются оптимальными решениями прямой и двойственной задач соответственно. 
 

  Определение дефицитных и недефицитных (избыточных) ресурсов. Вторая теорема двойственности.  
 Подставим оптимальный план прямой задачи в систему ограниченной математической модели: 
10*40 + 5*20 = 500 = 500 
6*40 + 6*20 = 360 = 360 
5*40 + 8*20 = 360 < 400 
 1-ое ограничение прямой задачи выполняется как равенство. Это означает, что 1-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y1>0). 
 2-ое ограничение прямой задачи выполняется как равенство. Это означает, что 2-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y2>0). 
 3-ое ограничение выполняется как строгое неравенство, т.е. ресурс 3-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y3 = 0. 
 Неиспользованный экономический резерв ресурса 3 составляет 40 (400-360). 
 Этот резерв не может быть использован в оптимальном плане, но указывает на возможность изменений в объекте моделирования (например, резерв ресурса можно продать или сдать в аренду). 
 Таким образом, отличную от нуля двойственные оценки имеют лишь те виды ресурсов, которые полностью используются в оптимальном плане. Поэтому двойственные оценки определяют дефицитность ресурсов. 
 Обоснование эффективности оптимального плана. 
При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим: 
10*1 + 6*31/3 + 5*0 = 30 = 30 
5*1 + 6*31/3 + 8*0 = 25 = 25 
 Анализ устойчивости оптимального плана. 
Проведем анализ устойчивости оптимального плана и оценим степень влияния изменения ресурсов на значение целевой функции. 
Чувствительность решения к изменению коэффициентов целевой функции. 
Так как любые изменения коэффициентов целевой функции оказывают влияние на оптимальность полученного ранее решения, то наша цель - найти такие диапазоны изменения коэффициентов в целевой функции (рассматривая каждый из коэффициентов отдельно), при которых оптимальные значения переменных остаются неизменными. 
Пусть каждое значение параметра целевой функции изменится на ∆ сi. Найдем интервалы, при которых будет экономически выгодно использование ресурсов. 
Допустимые диапазоны изменения коэффициентов в целевой функции определятся из соотношений: 
1-ый параметр целевой функции может изменяться в пределах: 
∆c-1 = min [yk/d1k] для d1k>0. 
∆c+1 = |max[yk/d1k]| для d1k<0. 
 
 
где в знаменателе коэффициенты столбцов свободных переменных в оптимальном плане (коэффициенты структурных сдвигов, элементы обратной матрицы к базису оптимального плана). 
 Таким образом, 1-параметр может быть уменьшен на 5 или увеличен на 20 
Интервал изменения равен: 
(c1 - ∆c1-; c1 + ∆c1+) 
[30-5; 30+20] = [25;50] 
Если значение c1 будет лежать в данном интервале, то оптимальный план не изменится. 
2-ый параметр целевой функции может изменяться в пределах: 
∆c-2 = min [yk/d2k] для d2k>0. 
∆c+2 = |max[yk/d2k]| для d2k<0. 
 
 
 Таким образом, 2-параметр может быть уменьшен на 10 или увеличен на 5 
Интервал изменения равен: 
(c2 - ∆c2-; c2 + ∆c2+) 
[25-10; 25+5] = [15;30] 
 Если значение c2 будет лежать в данном интервале, то оптимальный план не изменится. 
 Чувствительность решения к изменению запасов сырья. 
Из теоремы об оценках известно, что колебание величины bi приводит к увеличению или уменьшению f(X). 
 Оно определяется величиной yi в случае, когда при изменении величин bi значения переменных уi в оптимальном плане соответствующей двойственной задачи остаются неизменными. 
 Поэтому необходимо найти такие интервалы изменения каждого из свободных членов системы ограничений исходной ЗЛП, в которых оптимальный план двойственной задачи не менялся бы. 
 Найдем интервалы устойчивости ресурсов. 
1-ый запас может изменяться в пределах: 
∆b-1 = min[xk/dk1] для dk1>0. 
∆b+1 = |max[xk/dk1]| для dk1<0. 
 
 
 Таким образом, 1-ый запас может быть уменьшен на 200/3 или увеличен на 100 
Интервал изменения равен: 
(b1 - ∆b-1; b1 + ∆b+1) 
[500-200/3; 500+100] = [1300/3;600] 
2-ый запас может изменяться в пределах: 
∆b-2 = min[xk/dk2] для dk2>0. 
∆b+2 = |max[xk/dk2]| для dk2<0. 
 
 
 Таким образом, 2-ый запас может быть уменьшен на 60 или увеличен на 240/11 
Интервал изменения равен: 
(b2 - ∆b-2; b2 + ∆b+2) 
[360-60; 360+240/11] = [300;4200/11] 
 Нижняя граница для: ∆b-3 
∆b-3 = min[xk/dk3] для dk3>0. 
 
 Таким образом, 3-ый запас может быть уменьшен на 40 
3-ый вид ресурса в оптимальном плане недоиспользован, является недефицитным. Увеличение данного ресурса приведет лишь к росту его остатка. При этом структурных изменений в оптимальном плане не будет, так как двойственная оценка y3 = 0. Другими словами, верхняя граница b+3 = +∞ 
 
 Интервал изменения равен: 
(b3 - ∆b-3; +∞) 
[400-40; +∞] = [360;+∞] 
 В оптимальный план не вошла основная переменная x3, т.е. ее не выгодно использовать. Определим максимально возможное значение в рамках полученных двойственных оценок: 
x3 может изменяться в пределах:

 
-100 ≤ ∆b3 ≤ 200/3 
[400-200/3; 400] = [1000/3;400] 
 1-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 1-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x1>0). 
 2-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 2-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x2>0). 
 Влияние запасов ресурсов на оптимальное решение прямой задачи. 
Величина двойственной оценки показывает, на сколько возрастает значение целевой функции F(x) при увеличении дефицитного ресурса на единицу.