- •1. Понятие модели.
- •1.1. Модели и моделирование. Классификация моделей
- •В настоящее время для постижения истины существует 3 пути:
- •1.2. Классификация моделей
- •1.3. Адекватность моделей
- •2. Математические модели и методы их расчета
- •2.1. Математические модели.
- •2.1. Понятие операционного исследования
- •2.3. Этапы построения математических моделей
- •Можно выделить следующие основные этапы построения математической модели:
- •2.4 Математические оптимизационные модели.
- •2.4. Необходимые сведения из матричной алгебры
- •2.5. Системы линейных алгебраических уравнений
- •2.5. Модель Леонтьева многоотраслевой экономики (балансовый анализ).
- •3. Простейшие оптимизационные задачи.
- •3.1. Экстремумы функции одной переменной.
- •Экстремумы функции нескольких переменных.
- •4. Математические модели экономических задач.
- •4.1. Транспортная задача
- •4.2 Задача об использовании ресурсов.
- •4.3. Задача о диете.
- •4.4. Общая формулировка задачи линейного программирования
- •Стандартная задача линейного программирования.
- •Каноническая задача линейного программирования.
- •Общая задача линейного программирования.
- •5. Графический метод решения задач линейного программирования.
- •5.1. Выпуклые множества
- •5.2 Геометрический смысл решений систем неравенств.
- •5.3. Графический метод решения задач линейного программирования. Пример.
- •5.4. Геометрический метод решения задачи. Общий случай.
- •6.Симплекс-метод решения задачи линейного программирования.
- •6.1. Выпуклые многогранники.
- •6.2.Симплекс-метод. Пример.
- •6.3.Симплекс метод. Общий случай.
- •Симплекс-таблицы. Пример.
- •7.Двойственность в линейном программировании.
- •7.1. Двойственные задачи линейного программирования.
- •7.2. Теоремы двойственности..
- •7.3. Анализ чувствительности задачи линейного программирования..
- •Решение транспортной задачи.
- •7.1 Особенности транспортной задачи.
- •7.2. Опорный план транспортной задачи
- •7.3. Метод потенциалов.
- •8.Задачи нелинейного программирования.
- •8.1. Общая постановка задачи нелинейного программирования.
- •8.2. Задачи нелинейного программирования с линейной целевой функцией и нелинейными ограничениями.
- •8.3. Задачи нелинейного программирования с нелинейной целевой функцией и линейными ограничениями.
- •8.4. Метод множителей Лагранжа.
- •Элементы теории игр.
- •9.1.Основные понятия теории игр
- •8.3. Сведение матричной игры к задаче линейного программирования.
7.3. Анализ чувствительности задачи линейного программирования..
Рассмотрим пример 1 предыдущего пункта и исследуем следующий вопрос: как измениться значение Fmax , если изменить ресурсы b1 и b2 ?
Справедлива третья теорема двойственности.
Теорема 3.
.
Это следует из того, что Fmax = Zmin .
Так как имеет смысл скорости изменения Fmax от , то, чем больше величина , тем большую прибыль мы получим при увеличении ресурса Рj. Поэтому при изменении ресурсов целесообразно увеличивать те ресурсы, у которых больше величина , может быть за счет других ресурсов.
В примере 1 имеет смысл увеличивать ресурс Р2 , так как .
Однако при больших изменениях ресурсов задача может качественно измениться. В каких пределах могут меняться ресурсы b1 и b2 так, чтобы оптимальное решение при этом не изменялось? Такие исследование и называют анализом чувствительности задачи линейного программирования.
В примере 1
Z=5 .
Выразим из системы (14) и через свободные переменные (эти переменные свободные, так как ).
(15)
Подставляя (15) в первое уравнение (14), получим
12 - 3 + =6
Подставляя в (15), получим
,
Z=5(1+0,5 ) +3(3-0,5 ).
Предположим, мы изменили ресурс Р1 на величину и он стал b1=5+ .
Тогда
Z=(5+ )(1+0,5 ) +3(3-0,5 )=14+ +(1+0,5 ) +(2-0,5 ) .
Значение Z =14+ будет наименьшим при , если коэффициенты при и будут неотрицательны, то есть при
.
При этом Zmin = Fmax = 14+ .
Предположим, мы изменили ресурс Р2 на величину и он стал b2=3+ .
Тогда
Z=5(1+0,5 ) +(3+ )(3-0,5 )=14+ +(1-0,5 ) +(2+1,5 ) .
Значение Z =14+ будет наименьшим при , если коэффициенты при и будут неотрицательны, то есть при
.
При этом Zmin = Fmax = 14+3 .
Если мы увеличим ресурс Р2 на две единицы, то значение Fmax увеличится на 6 и станет равным 20; если при этом мы даже уменьшим на 2 единицы ресурс Р1, то значение Fmax уменьшится на 2 и станет Fmax=18.
Решение транспортной задачи.
7.1 Особенности транспортной задачи.
Напомним, что транспортной задачей называют задачу нахождения наименьшего значения функции
f=c11х11+c12х12+…+c1mх1m+... +cn1 хn1+cn2хn2+…+cnm хnm, (1)
где переменные хij, i=1,…,n, j=1,…,m удовлетворяют ограничениям
(2)
хij≥0, i=1,2,…,n, j=1,2,…,m. (3)
Транспортная задача – частный случай задачи линейного программирования, и ее можно решать с помощью симплекс-метода. Однако, транспортная задача существенно проще общей задачи линейного программирования, поскольку все коэффициенты в системе (2) равны единицам или нулям.
Будем считать, что (такие задачи называют закрытыми).
Для закрытых транспортных задач ранг системы (2) равен n+m-1, поэтому число базисных переменных будет равно n+m-1, а остальные
nm- n-m+1 переменных будут являться свободными переменными. Решение задачи ( ,0,…0) будем называть базисным распределением поставок.
7.2. Опорный план транспортной задачи
а) Метод «северо-западного угла».
Суть данного метода состоит в максимально возможном удовлетворении запросов потребителей, начиная с верхнего левого угла транспортной таблицы распределения поставок. Рассмотрим данный метод на примере. Пусть имеем таблицу перевозок
|
В Р1 |
В Р2 |
В Р3 |
В Р4 |
Мощности поставщиков |
Из М1 |
|
|
|
|
40 |
Из М2 |
|
|
|
|
60 |
Из М3 |
|
|
|
|
50 |
Потребности |
30 |
50 |
30 |
40 |
|
В верхнем правом углу клетки ставим стоимость перевозки единицы продукции. Заполняем левую верхнюю клетку (1-1). Поставщик М1 может полностью удовлетворить потребности Р1, оставшиеся 10 единиц ставим в клетку (1-2). Требуемые для Р2 40 единиц берем от поставщика М2 и так далее.
Отметим, что заполненными оказались m+n-1 клеток. Соответствующие им переменные могут быть выбраны в качестве базисных переменных. Если количество заполненных клеток окажется меньше, чем n+m-1 (вырожденный случай) – можно в любой свободной клетке поставить 0 и считать ее занятой.
Найдем стоимость перевозок
f=30 10.
Недостаток метода «северо-западного угла» в том, что он не учитывает стоимость перевозок, поэтому опорный план, полученный таким методом, как правило, дает распределение поставок, далекое от оптимального.
б)Метод минимального элемента.
Основная суть метода минимального элемента- сначала обеспечить по максимуму тех потребителей, перевозка к которым самая дешевая.
Например, потребителю Р1 выгоднее всего отправить требуемую поставку из М3, так как себестоимость этой поставки наименьшая. Далее из М2 50 единиц продукции отправляем в Р2 (так как поставки в Р3 уже сделаны), а поставками из М1 и остатками поставок из М2 и М3 заполняем таблицу поставок до конца.
|
В Р1 |
В Р2 |
В Р3 |
В Р4 |
Мощности поставщиков |
Из М1 |
|
|
|
|
40 |
Из М2 |
|
|
|
|
60 |
Из М3 |
|
|
|
|
50 |
Потребности |
30 |
50 |
30 |
40 |
|
Стоимость перевозок в данном случае
f=
Как видим, стоимость поставок меньше, чем в методе «северо-западного угла», а значит данный план распределения поставок ближе к оптимальному.