4 Анализ модели на чувствительность
Проведем анализ на чувствительность задачи линейного программирования:
Задача в специальной форме:
Так как
и
– искусственные переменные решаем
задачу методом искусственного базиса:
Составим симплексную таблицу и решим ее методом искусственного базиса:
-
2
1
1
1
1
10
3
0
8
0
20
0
3
0
8
1
1
1
0
0
1
0
0
1
1
1
-1
0
1
1
7
-3
-3
8
0
20
0
3
0
8
1
1
1
0
0
1
0
0
1
1
0
-1
0
0
-1
7
-3
-3
8
0
12
0
3
-8
-8
1
1
1
0
0
1
0
0
1
1
1,8
-0,2
0,8
7
-3
8
12
3
-8
1
1
0
1
0
1
Переменные
- основные,
- дополнительные.
Получили
оптимальное решение данной задачи ЛП
.
Построим двойственную задачу по отношению к исходной:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Двойственную задачу решаем двойственным симплекс-методом:
|
|
|
Переменные
- свободные,
- дополнительные.
Оптимальное
решение двойственной задачи
.
Оптимальные значения целевых функций взаимно-двойственных задач равны:
Установим соответствие между первоначальными (основными) переменными одной из двойственных задач и дополнительными переменными другой задачи (табл.1).
Таблица 1
Компоненты оптимального решения исходной задачи |
|||||||
Устанавливаемые функции |
Остатки информации |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Превышение объемов массивов над Объемом ЗУ |
Объектно обусловленные оценки массивов |
||||||
Компоненты оптимального решения двойственной задачи |
|||||||
Компоненты оптимального решения двойственной задачи являются объектно обусловленными оценками исходной задачи.
ЗУ , по оптимальному быстродействию полностью использованы ( , ), и объективно обусловленные оценки этих массивов ненулевые ( , ).
ЗУ не полностью использован в оптимальном быстродействии ( ) и его объективно обусловленная оценка нулевая ( ).
Объективно обусловленные оценки уровня информации определяют степень вероятности обращения: по оптимальному плану наивероятные обращения получают ненулевые оценки, а маловероятные – нулевые.
По
третьей теореме двойственности
.
,
если
,
то
Аналогично
,
,
.
Объектно обусловленные оценки показывают на сколько максимальный экономический эффект от реализации функций при изменении объема соответствующего объем информации на одну единицу.
Определим расчетные нормы заменяемости массивов данных.
Предположим,
что объемы ЗУ
,
,
,
,
равные первоначально 3, 1, 1, 1 единиц,
изменились соответственно на величины
,
,
,
,
тогда
)
.
,
После преобразований получаем:
Для сохранения оптимального решения двойственной задачи достаточно, чтобы коэффициенты при не основных переменных оставались неотрицательными:
Предположим,
что массив обратился к первому ЗУ, а
остальные остаются неизменными:
,
.
Тогда значение
.
аналогично находим пределы изменений , , . Тогда
∞
∞
∞
Если объемы массивов заменяются в этих пределах, то оптимальное решение двойственной задачи остается прежним.
ВЫВОДЫ
С помощью реализованного в данной работе предмета можно рассчитать оптимальное размещение массивов ЗУ для оптимизации среднего быстродействия. Программу реализованную в данной работе можно использовать для решения любых примеров на любые темы метод искусственного базиса, симплекс методом и затем методом Гомори.