Двойственные задачи линейного программирования - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Двойственные задачи линейного программирования, слайд №1

Двойственные задачи линейного программирования, слайд №2

Двойственные задачи линейного программирования, слайд №3

Двойственные задачи линейного программирования, слайд №4

Двойственные задачи линейного программирования, слайд №5

Двойственные задачи линейного программирования, слайд №6

Двойственные задачи линейного программирования, слайд №7

Двойственные задачи линейного программирования, слайд №8

Двойственные задачи линейного программирования, слайд №9

Двойственные задачи линейного программирования, слайд №10

Двойственные задачи линейного программирования, слайд №11

Двойственные задачи линейного программирования, слайд №12

Двойственные задачи линейного программирования, слайд №13

Двойственные задачи линейного программирования, слайд №14

Двойственные задачи линейного программирования, слайд №15

Двойственные задачи линейного программирования, слайд №16

Двойственные задачи линейного программирования, слайд №17

Двойственные задачи линейного программирования, слайд №18

Двойственные задачи линейного программирования, слайд №19

Двойственные задачи линейного программирования, слайд №20

Двойственные задачи линейного программирования, слайд №21

Двойственные задачи линейного программирования, слайд №22

Двойственные задачи линейного программирования, слайд №23

Двойственные задачи линейного программирования, слайд №24

Двойственные задачи линейного программирования, слайд №25

Двойственные задачи линейного программирования, слайд №26

Двойственные задачи линейного программирования, слайд №27

Двойственные задачи линейного программирования, слайд №28

Двойственные задачи линейного программирования, слайд №29

Двойственные задачи линейного программирования, слайд №30

Двойственные задачи линейного программирования, слайд №31

Двойственные задачи линейного программирования, слайд №32

Двойственные задачи линейного программирования, слайд №33

Двойственные задачи линейного программирования, слайд №34

Двойственные задачи линейного программирования, слайд №35

Двойственные задачи линейного программирования, слайд №36

Двойственные задачи линейного программирования, слайд №37

Двойственные задачи линейного программирования, слайд №38

Двойственные задачи линейного программирования, слайд №39

Двойственные задачи линейного программирования, слайд №40

Двойственные задачи линейного программирования, слайд №41

Двойственные задачи линейного программирования, слайд №42

Двойственные задачи линейного программирования, слайд №43

Двойственные задачи линейного программирования, слайд №44

Двойственные задачи линейного программирования, слайд №45

Двойственные задачи линейного программирования, слайд №46

Двойственные задачи линейного программирования, слайд №47

Двойственные задачи линейного программирования, слайд №48

Двойственные задачи линейного программирования, слайд №49

Двойственные задачи линейного программирования, слайд №50

Двойственные задачи линейного программирования, слайд №51

Двойственные задачи линейного программирования, слайд №52

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Двойственные задачи линейного программирования. Доклад-сообщение содержит 52 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

5.7.Двойственные задачи ЛП

Слайд 2

Описание слайда:

С каждой задачей линейного С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной к исходной. Пусть дана задача ЛП. Максимизировать линейную функцию

Слайд 3

Описание слайда:

При ограничениях При ограничениях Или в матричном виде

Слайд 4

Описание слайда:

Двойственная к ней задача Двойственная к ней задача формулируется следующим образом Минимизировать линейную функцию при ограничениях

Слайд 5

Описание слайда:

или в матричном виде

Слайд 6

Описание слайда:

Задачи (5.9), (5.10) и (5.11), (5.12) Задачи (5.9), (5.10) и (5.11), (5.12) образуют пару взаимодвойственных задач, и любая из них может рассматриваться как исходная. Решать исходную или двойственную задачу – вопрос лишь удобства Математические модели двойственных задач могут быть симметричными и несимметричными. В табл. 5.13, 5.14 приведены их матричные формы записи

Слайд 7

Описание слайда:

5.7.1.Симметричные задачи 5.7.1.Симметричные задачи В симметричных задачах система ограничений как исходной, так и двойственной задачи задается неравенствами, причем на двойственные переменные налагается условие неотрицательности.

Слайд 8

Описание слайда:

Слайд 9

Описание слайда:

5.7.2. Несимметричные задачи 5.7.2. Несимметричные задачи В несимметричных двойственных задачах система ограничений исходной задачи задается в виде равенств, а в двойственной - в виде неравенств, причем в последней переменные могут быть и отрицательными.

Слайд 10

Описание слайда:

Слайд 11

Описание слайда:

Пример 5.11. Даны прямые задачи. Пример 5.11. Даны прямые задачи. Построить двойственные к ним задачи.

Слайд 12

Описание слайда:

Решение. Рассматриваемая задача Решение. Рассматриваемая задача относится к симметричным двойственным задачам на отыскание максимального значения целевой функции. Используем общие правила составления двойственных задач. Так как в задаче на максимум ограничения неравенства должны иметь вид «

Слайд 13

Описание слайда:

Слайд 14

Описание слайда:

Найдем соответствующую Найдем соответствующую двойственную задачу (строка 1, табл. 5.13). Введем вектор двойственных переменных размерности 3 (по числу уравнений системы ограничений) . Соответствующие векторы и матрица ограничений имеет вид:

Слайд 15

Описание слайда:

Слайд 16

Описание слайда:

Запишем двойственную задачу. Найти Запишем двойственную задачу. Найти минимум функции

Слайд 17

Описание слайда:

Укажем еще один метод, позволяющий Укажем еще один метод, позволяющий значительно облегчить процесс построения двойственных задач. Каждому ограничению прямой задачи поставим в соответствие двойственные переменные.

Слайд 18

Описание слайда:

Чтобы получить, например, первое Чтобы получить, например, первое ограничение двойственной задачи, надо найти сумму произведений элементов, стоящих в столбце , на соответствующие двойственные переменные. Результат Считаем, что эта сумма не меньше Аналогично составляются и остальные ограничения двойственной задачи.

Слайд 19

Описание слайда:

Слайд 20

Описание слайда:

Решение. Каждому ограничению Решение. Каждому ограничению прямой задачи поставим в соответствие двойственные переменные

Слайд 21

Описание слайда:

Составим двойственную задачу: Составим двойственную задачу: Переменная , соответствующая ограничению-равенству может быть любого знака.

Слайд 22

Описание слайда:

5.7.3. Первая теорема двойственности 5.7.3. Первая теорема двойственности Если из двух задач (исходной и двойственной) одна имеет решение, то другая задача также имеет решение, причем максимальное значение целевой функции исходной задачи и минимальное значение двойственной задачи численно равны

Слайд 23

Описание слайда:

Если же одна из задач не имеет Если же одна из задач не имеет оптимального решения, то система ограничений двойственной задачи противоречива 5.7.4. Экономическая интерпретация двойственной задачи. Пусть - оптимальное решение прямой задачи, а оптимальное решение двойственной задачи

Слайд 24

Описание слайда:

На основании первой теоремы На основании первой теоремы двойственности можно записать Найдем

Слайд 25

Описание слайда:

Учитывая, что функция линейная, Учитывая, что функция линейная, получим Из последней формулы следует: значения переменных в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов системы ограничений прямой задачи на величину

Слайд 26

Описание слайда:

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

Слайд 27

Описание слайда:

Составить план производства, Составить план производства, обеспечивающий предприятию максимальную прибыль. Математическая модель прямой задачи Обозначим через - количество единиц продукции, соответственно I и II видов. Тогда задача заключается в следующем:

Слайд 28

Описание слайда:

максимизировать целевую функцию максимизировать целевую функцию при ограничениях

Слайд 29

Описание слайда:

Запишем задачу в матричном виде. Запишем задачу в матричном виде. где - вектор неизвестных, - вектор коэффициентов целевой функции, - вектор правых частей системы ограничений,

Слайд 30

Описание слайда:

- матрица коэффициентов системы ограничений. Решение прямой задачи дает оптимальный план выпуска продукции I и II видов. Поставим в соответствие прямой задаче двойственную задачу.

Слайд 31

Описание слайда:

Пример 5.13. Предприятию необходимо Пример 5.13. Предприятию необходимо определить минимальное суммарное количество сырья каждого из видов применив прежнее условие примера 5.12. Математическая модель двойственной задачи В качестве переменных двойственной задачи возьмем представляющие собой условные оценки запасов сырья

Слайд 32

Описание слайда:

Представим двойственную задачу в Представим двойственную задачу в матричном виде где - вектор двойственных переменных; - транспонированная матрица коэффициентов системы ограничений

Слайд 33

Описание слайда:

Раскрывая соотношение (5.14) можно Раскрывая соотношение (5.14) можно сформулировать двойственную задачу так: найти минимум целевой функции при ограничениях

Слайд 34

Описание слайда:

Чтобы найти решение этих задач Чтобы найти решение этих задач решим одну из них – прямую, т.к. система ограничений этой задачи содержит лишь неравенства «

Слайд 35

Описание слайда:

Слайд 36

Описание слайда:

Запишем систему ограничений в Запишем систему ограничений в векторном виде где

Слайд 37

Описание слайда:

Составим первую симплекс- таблицу Составим первую симплекс- таблицу

Слайд 38

Описание слайда:

Поскольку отыскивается максимум Поскольку отыскивается максимум задачи, то критерий оптимальности для плана не выполнен, т.к. в - строке имеются отрицательные оценки. Дальнейшие результаты пошагового решения задачи представлены в табл. 5.15 – 5.17.

Слайд 39

Описание слайда:

Слайд 40

Описание слайда:

Слайд 41

Описание слайда:

Слайд 42

Описание слайда:

В последней таблице - строка не В последней таблице - строка не содержит отрицательных оценок, что свидетельствует об оптимальности полученного решения:

Слайд 43

Описание слайда:

Оптимальное решение двойственной Оптимальное решение двойственной задачи может быть получено из оптимального решения прямой задачи. Так как прямая задача имеет решение, то на основании теоремы о двойственности двойственная задача также разрешима. Ее решение может быть найдено из формулы

Слайд 44

Описание слайда:

где - матрица, составленная из где - матрица, составленная из компонент векторов, входящих в последний базис, при котором получен оптимальный план исходной задачи. В нашем примере в последней симплекс-таблице базисными переменными являются

Слайд 45

Описание слайда:

Соответствующие этим переменным Соответствующие этим переменным векторы в разложении (5.14) используются для формирования столбцов матрицы

Слайд 46

Описание слайда:

Вычислим Вычислим Так как то

Слайд 47

Описание слайда:

При этом минимальное значение При этом минимальное значение целевой функции двойственной задачи совпадает с максимальным значением прямой задачи.

Слайд 48

Описание слайда:

Проведем анализ полученного Проведем анализ полученного оптимального решения двойственной задачи. Рассмотрим экономическое содержание двойственных оценок. Предположим, что запасы сырья увеличены на 1единицу. Пользуясь формулой (5.13), найдем

Слайд 49

Описание слайда:

Нулевые оценки и означают, что данное сырье не полностью используется (является недефицитным) и дальнейшее его увеличение не повлияет на оптимальный план выпуска продукции и сумму прибыли.

Слайд 50

Описание слайда:

Если увеличить запасы сырья на 1 (ед.), то прибыль увеличится на 0,75 (ед.). Если увеличить запасы сырья на 1 (ед.), то прибыль увеличится на 2,75 (ед.).

Слайд 51

Описание слайда:

Запасы сырья и полностью используются в оптимальном плане, являются дефицитными и сдерживают рост целевой функции.

Слайд 52

Описание слайда:

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