Программирование
<<  Разработка и внедрение эффективного контракта Программирование разветвляющихся алгоритмов  >>
Графический метод решения задач математического программирования
Графический метод решения задач математического программирования
Графический метод решения задач математического программирования
Графический метод решения задач математического программирования
Графический метод решения задач математического программирования
Графический метод решения задач математического программирования
Графический метод решения задачи математического программирования
Графический метод решения задачи математического программирования
Графический метод решения задачи математического программирования
Графический метод решения задачи математического программирования
Графический метод решения задач математического программирования
Графический метод решения задач математического программирования
Графический метод решения задач математического программирования
Графический метод решения задач математического программирования
Графический метод решения задач математического программирования
Графический метод решения задач математического программирования
Графический метод решения задач математического программирования
Графический метод решения задач математического программирования
Оценка устойчивости решения
Оценка устойчивости решения
Оценка устойчивости решения
Оценка устойчивости решения
Оценка устойчивости решения
Оценка устойчивости решения
Оценка устойчивости решения
Оценка устойчивости решения
Оценка устойчивости решения
Оценка устойчивости решения
Оценка устойчивости решения
Оценка устойчивости решения
Оценка устойчивости решения
Оценка устойчивости решения
Оценка устойчивости решения
Оценка устойчивости решения
Оценка устойчивости решения
Оценка устойчивости решения
Оценка устойчивости решения
Оценка устойчивости решения
Оценка устойчивости решения
Оценка устойчивости решения
Оценка устойчивости решения
Оценка устойчивости решения

Презентация на тему: «Графический метод решения задач математического программирования». Автор: Администратор. Файл: «Графический метод решения задач математического программирования.ppt». Размер zip-архива: 257 КБ.

Графический метод решения задач математического программирования

содержание презентации «Графический метод решения задач математического программирования.ppt»
СлайдТекст
1 Графический метод решения задач математического программирования

Графический метод решения задач математического программирования

1. Общий вид задачи математического программирования Z = F(X) ?>min gi(x1,x2,…,хn) ?0 hj(x1,x2,…,xn) = 0 2. Методы решения задач математического программирования Графический метод; Аналитические методы; Численные методы.

2 Графический метод решения задач математического программирования

Графический метод решения задач математического программирования

3. Графическая интерпретация задачи математического программирования. Пространство переменных одномерно. F(x) ?> max/min a ? x ? b Необходимо найти экстремум функции F(x) на отрезке [a,b]. Пространство переменных двумерно. F(x1,x2) ?> max/min gi(x1,x2) ? 0 hj(x1,x2) = 0 Необходимо найти экстремум функции F на части плоскости.

3 Графический метод решения задач математического программирования

Графический метод решения задач математического программирования

Графическая интерпретация задачи.

Условие задачи: Х12 – х22 ?>min -10?x1?10 -10?x2?10

Определение. Градиентом функции f(x1, x2,…,xn) в точке X0=(x01, x02,…,x0n) называется вектор, компонентами которого являются частные производные функции f по всем переменным:

График целевой функции

Карта линий уровня задачи

4 Графический метод решения задачи математического программирования

Графический метод решения задачи математического программирования

Свойства вектора – градиента Указывает направление максимального возрастания функции f(x1, x2,…,xn) в точке X0=(x01, x02,…,x0n) Модуль вектора-градиента соответствует абсолютному значению скорости возрастания функции Является нормалью к касательной плоскости, проведенной к поверхности уровня в точке X0=(x01, x02,…,x0n).

Перечисленные свойства положены в основу графического метода решения задач МП.

5 Графический метод решения задачи математического программирования

Графический метод решения задачи математического программирования

3. Пример решения задачи линейного программирования. Задача. Ограничения: Спрос на продукцию Р1 не превосходит спрос на продукцию Р2 более чем на 5 Спрос на продукцию Р2 ? 4; Найти: План выпуска продукции, который обеспечивает максимальную выручку от реализации

Ресурсы

Ресурсы

Расходы сырья на 1ед. Продукции

Расходы сырья на 1ед. Продукции

Запасы сырья

Запасы сырья

Р1

Р2

Сырье

1

3

14

Труд

4

2

26

Цена продукции

3

3

6 Графический метод решения задач математического программирования

Графический метод решения задач математического программирования

Формализация задачи: Z =3x1 + 3x2 ?> Max x1 + 3x2 ? 14 (1) 4x1 + 2x2 ? 26 (2) x1 – x2 ? 5 (3) x2 ? 4 (4) x1 ? 0; x2 ? 0 (5)

Ресурсы

Ресурсы

Расходы сырья на 1ед. Продукции

Расходы сырья на 1ед. Продукции

Запасы сырья

Запасы сырья

Р1

Р2

Сырье

1

3

14

Труд

4

2

26

Цена продукции

3

3

7 Графический метод решения задач математического программирования

Графический метод решения задач математического программирования

Шаг 1. Построение области допустимых значений для x1 и x2 Шаг 2. Проводится прямая (5) вдоль направления: V=grad(Z)={3, 3} Шаг 3. Проводится прямая (6) перпендикулярная прямой (5) Шаг 4. Прямая (6) перемещается по прямой (5) до верхней точки касания с областью

x2

Grad(Z) (5)

B

A

H

C

D

E

0

x1

(6)

(2)

(3)

4.66

(4)

4.00

(1)

6.50

8 Графический метод решения задач математического программирования

Графический метод решения задач математического программирования

В данном случае решением задачи является точка С Ее координаты x1 и x2 можно снять из графика или вычислить из условия, что решение – координаты точки пересечения прямых (1) и (2) Имеем систему уравнений:

Решение есть: x1=5, x2=3 Таким образом, максимальная выручка равна Z=24 при выпуске продукции х1=5 единиц, а продукции х2=3 единицы

9 Графический метод решения задач математического программирования

Графический метод решения задач математического программирования

Замечание. В общем случае задачи МП направление и модуль вектора-градиента зависит от точки области Графическая иллюстрация позволяет показать возможные решения задач математического программирования

А

В

Бесконечное множество решений

Решение внутри области

Решения нет

Grad(Z)

10 Оценка устойчивости решения

Оценка устойчивости решения

Устойчивость – важная характеристика решения задачи Определение. Решение считается устойчивым, если малые изменения ограничений приводят к малым изменениям решения. В случае задачи математического программирования, устойчивость это сохранение структуры решения при небольших изменениях ограничений. В рассмотренном примере решение лежит на пересечении границ (1) и (2) Именно эти ограничения определяют структуру оптимального решения.

11 Оценка устойчивости решения

Оценка устойчивости решения

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

12 Оценка устойчивости решения

Оценка устойчивости решения

Анализ устойчивости позволяет ответить на ряд практически важных вопросов: - на сколько могут быть снижены запасы дефицитных ресурсов при сохранении общей структуры решения - на сколько могут быть увеличены запасы дефицитных ресурсов с целью повышения эффективности экономической системы - на сколько можно снизить запасы не дефицитных ресурсов при сохранении эффективности экономической системы

13 Оценка устойчивости решения

Оценка устойчивости решения

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

14 Оценка устойчивости решения

Оценка устойчивости решения

Шаг 1. Определяются те ресурсы, которые являются дефицитными. В нашем случае это те ресурсы, которые определяют структуру оптимального решения: ресурсы, определяющие положение прямых (1) и (2), т.к. на их пересечении лежит оптимальное решение Определение. Ограничения, которые определяют структуру оптимального решения называются связывающими Остальные ограничения – не связывающие Неизменность качественной структуры решения предполагает неизменность типов ограничений задачи

15 Оценка устойчивости решения

Оценка устойчивости решения

При дальнейшем перемещении оптимальным решением будет пересечение прямых (2) и (4)

Начнем с ресурса х1 «Сырье» При увеличении ресурса х1 прямая (1) будет перемещаться вверх Структура решения сохраняется при перемещении (1) до точки Н

x2

B

A

H

C

D

E

0

x1

(2)

(3)

4.66

(4)

4.00

(1)

6.50

5.0

16 Оценка устойчивости решения

Оценка устойчивости решения

Значения ресурсов х1 и х2 можно снять с графика или вычислить из системы уравнений:

Откуда получаем х1=4.5; х2=4

Подставляя, полученные значения х1 и х2 в ограничение (1) получим верхний предел запаса ресурса «Сырье» x1 + 3x2 ? 14 (1) 4.5 + 3·4 = 16.5 Таким образом, ресурс «Сырье» можно увеличить на 2.5 единицы без изменения структуры оптимального решения. Эффективность системы при этом возрастет на 1.5 единицы (Z=25.5)

17 Оценка устойчивости решения

Оценка устойчивости решения

Аналогичным образом можно определить нижний предел ресурса «Сырье» при сохранении структуры решения

Прямую (1) опускаем до точки D. Ниже нее связывающими ограничениями становятся (1) и (3) Координаты х1 и х2 находятся из решения системы уравнений

Откуда: х1=6; х2=1 «Сырье» 1·6+3·1=9 Z=3·6+3·1=21

x2

B

A

H

D

E

0

x1

(2)

(3)

4.66

(4)

4.00

(1)

6.50

5.0

18 Оценка устойчивости решения

Оценка устойчивости решения

Аналогично определяются допустимые пределы изменения ресурса «Труд»

Прямую (2) можно перемещать между точками В и L. В точке В имеем x1=2; х2=4; Z=18 «Труд» - 16 В точке L: X1=7,25; x2=2.25; Z=28.5 «Труд» - 33.5

x2

B

A

D

E

0

L

(2)

(3)

4.66

4.00

(1)

6.50

5.0

19 Оценка устойчивости решения

Оценка устойчивости решения

Определение. Ценностью ресурса называется отношение: С=?Z/?R где ?R – диапазон изменения ресурса при сохранении структуры решения В данном примере:

Показатель ценности ресурсов играют важную роль при определении приоритетов увеличении запасов ресурсов В первую очередь увеличивают ресурсы с большей ценностью

20 Оценка устойчивости решения

Оценка устойчивости решения

Пределы изменения недефицитных ресурсов Спрос 1. задается ограничением (3).

Возможное уменьшение ресурса «Спрос 1» определяется положением (3-1) Предельное значение ресурса находится из равенства (3) подстановкой координат точки C {5,3}: x1-x2=5-3=2 Аналогично находится нижний предел ресурса «Спрос 2» x2=3

x2

(3-1)

B

A

С

D

E

0

L

(2)

(3)

4.66

4.00

(1)

6.50

5.0

21 Оценка устойчивости решения

Оценка устойчивости решения

Результаты исследования на устойчивость

2 - ?

3 - ?

Ресурс

Тип ресурса

Значение ресурса

Пределы изменения ресурса

Изменения ЦФ

Ценность ресурса

Сырье

Дефи-цитный

14

9 – 16.5

21 – 25.5

0.6

Труд

Дефи-цитный

26

16 – 33.5

18 – 28.5

0.6

Спрос 1

Недефи-цитный

5

5 – 5

0

Спрос 2

Недефи-цитный

4

4 - 4

0

«Графический метод решения задач математического программирования»
http://900igr.net/prezentacija/informatika/graficheskij-metod-reshenija-zadach-matematicheskogo-programmirovanija-97721.html
cсылка на страницу

Программирование

31 презентация о программировании
Урок

Информатика

130 тем
Слайды
900igr.net > Презентации по информатике > Программирование > Графический метод решения задач математического программирования