🗊Презентация Двойственные задачи линейного программирования

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Двойственные задачи линейного программирования, слайд №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.Двойственные задачи ЛП
Описание слайда:
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 приведены их матричные формы записи
Описание слайда:
Задачи (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.Симметричные задачи В симметричных задачах система ограничений как исходной, так и двойственной задачи задается неравенствами, причем на двойственные переменные налагается условие неотрицательности.
Описание слайда:
5.7.1.Симметричные задачи 5.7.1.Симметричные задачи В симметричных задачах система ограничений как исходной, так и двойственной задачи задается неравенствами, причем на двойственные переменные налагается условие неотрицательности.

Слайд 8


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

Слайд 9


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

Слайд 10


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

Слайд 11


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

Слайд 12


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

Слайд 13


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

Слайд 14


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

Слайд 15


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

Слайд 16


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

Слайд 17


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

Слайд 18


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

Слайд 19


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

Слайд 20


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

Слайд 21


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

Слайд 22


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

Слайд 23


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

Слайд 24


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

Слайд 25


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

Слайд 26


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

Слайд 27


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

Слайд 28


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

Слайд 29


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

Слайд 30


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

Слайд 31


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

Слайд 32


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

Слайд 33


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

Слайд 34


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

Слайд 35


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

Слайд 36


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

Слайд 37


Составим первую симплекс- таблицу Составим первую симплекс- таблицу
Описание слайда:
Составим первую симплекс- таблицу Составим первую симплекс- таблицу

Слайд 38


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

Слайд 39


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

Слайд 40


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

Слайд 41


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

Слайд 42


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

Слайд 43


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

Слайд 44


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

Слайд 45


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

Слайд 46


Вычислим Вычислим Так как то
Описание слайда:
Вычислим Вычислим Так как то

Слайд 47


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

Слайд 48


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

Слайд 49


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

Слайд 50


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

Слайд 51


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

Слайд 52


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

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию