- •Моделирование
- •2. Точность вычислительного эксперимента
- •1. Линейное программирование
- •1.2. Графический метод решения задач лп
- •1.3 Проверка задач лп на чувствительность
- •1.4 Симплекс - метод решения задач лп
- •1.4. Симплекс-метод решения задач лп
- •1.5. Модифицированный симплекс-метод
- •Исходная таблица имеет вид
- •1.6. Транспортная задача
- •1.7. Метод потенциалов для решения тз
- •1.7.1. Нахождение предварительного плана перевозок
- •Учитывая условия баланса наличия и потребления
- •1.7.2. Проверка опорного плана на оптимальность
- •1.7.3. Корректировка плана перевозок
- •1.8. Алгоритм метода потенциалов
- •Проверим необходимое условие в опорном плане:
- •0 3 0 Таблица 1.14
- •Преобразованная матрица показана в табл. 1.25
- •Преобразованная матрица стоимостей приведена в табл. 1.28.
- •1.9. Транспортная задача в сетевой форме
- •1.10. Двойственные задачи линейного программирования
- •Легко видеть, что
- •Запишем целевую функцию для прямой задачи
- •Прямая задача:
- •Из этой таблицы находим решение двойственной пары:
- •Окончательно прямая задача имеет следующее решение:
- •2. Обработка результатов эксперимента
- •Аппроксимация гиперболической функцией
- •Аппроксимация функциональной зависимостью вида
- •Аппроксимация функциональной зависимостью вида
- •Интерполяционный многочлен Ньютона
- •Экстраполяция
- •3. Некоторые простейшие задачи нелинейной оптимизации
- •3.1. Оптимизация числа ниток в графике движения поездов
- •3.2. Управление запасами
- •Понятие о выпуклом программировании
- •В нашем примере целевая функция имеет вид
- •Проверим:
- •Решение задачи выпуклого программирования
- •Сумма реальных расходов со штрафом составит
- •Филоненков Александр Иванович
- •Математические модели и меттоды Учебное пособие
1.3 Проверка задач лп на чувствительность
В заключение рассмотрим анализ ММ на чувствительность. Этот анализ выполняется после нахождения оптимального решения. В рамках такого анализа выявляется чувствительность оптимального решения к определённым изменениям исходной модели.
При анализе рассматривается некоторая совокупность линейных оптимизационных моделей. Это придаёт модели определённую динамичность, позволяющую исследователю проанализировать влияние возможных изменений исходных условий на полученное ранее оптимальное решение. Динамические характеристики моделей фактически отображают аналогичные характеристики, свойственные реальным процессам.
Рассмотрим три простые задачи анализа на чувствительность.
Первую задачу можно сформулировать так: на сколько сократить или увеличить запасы ресурсов? После нахождения оптимального решения вполне логично выяснить, как отразится на оптимальном решении изменение запасов ресурсов. При этом важно проанализировать два аспекта:
На сколько можно увеличить запас некоторого ресурса для улучшения полученного оптимального значения целевой функции.
На сколько можно снизить запас некоторого ресурса при сохранении полученного оптимального значения целевой функции.
Поскольку величина запаса каждого из ресурсов фиксируется в правых частях ограничений, то этот вид анализа обычно идентифицируется как анализ модели на чувствительность к правой части (ограничений). Прежде чем ответить на эти вопросы, классифицируем ограничения линейной модели как связывающие (активные) и несвязывающие (пассивные) ограничения. Те прямые (в графическом методе), которые проходят через оптимальную точку, называют связывающими. Они лимитируют запасы исходных ресурсов, и их относят к разряду дефицитных ресурсов, поскольку они используются полностью. Ресурс, с которым ассоциировано несвязывающее ограничение, относят к разряду недефицитных ресурсов, т.е. имеющихся в некотором избытке.
Таким образом, при анализе модели на чувствительность к правым частям ограничений определяются:
предельно допустимое увеличение запаса дефицитного ресурса, позволяющее улучшить найденное оптимальное решение;
предельно допустимое снижение запаса недефицитного ресурса, не изменяющее найденного ранее оптимального значения целевой функции.
Информация, полученная в последнем случае, особенно полезна тогда, когда излишки недефицитного ресурса могут быть использованы для других целей. Заметим, что сокращение объёма дефицитного ресурса никогда не улучшает значение целевой функции.
Вторая задача анализа на чувствительность позволяет ответить на вопрос: увеличение объема какого из ресурсов наиболее выгодно? Для решения этой задачи следует ввести характеристику ценности каждой дополнительной единицы дефицитного ресурса, выражаемой через соответствующее приращение оптимального значения целевой функции. Обозначим ценность дополнительной единицы ресурса i через yi. Величина yi может быть определена из отношения:
.
Третья задача анализа на чувствительность отвечает на вопрос: в каких пределах допустимо изменение коэффициентов целевой функции?
Изменение коэффициентов целевой функции оказывает влияние на наклон прямой, которая представляет эту функцию в принятой системе координат (графический метод). Вариация коэффициентов целевой функции может привести к изменению совокупности связывающих ограничений и, следовательно, статуса того или иного ресурса, т.е. сделать недефицитный ресурс дефицитным и наоборот. Следовательно, в рамках анализа модели на чувствительность к изменению коэффициентов целевой функции могут исследоваться следующие вопросы:
каков диапазон изменения (увеличения или уменьшения) того или иного коэффициента целевой функции, при котором не происходит изменения оптимального решения?
насколько следует изменить тот или иной коэффициент целевой функции, чтобы сделать некоторый недефицитный ресурс дефицитным и, наоборот, дефицитный ресурс сделать недефицитным?
Рассмотренные задачи характеризуют основные принципы анализа моделей на чувствительность после нахождения оптимального решения.
Более подробно эти вопросы изложены в [2], [5].
Используя геометрическую интерпретацию, найдите решение следующих задач:
