Теория двойственности в линейном программировании

Сентябрь 2, 2022

Главная
Алгебра
Теория двойственности в линейном программировании

Содержание

2. Экономическое содержание двойственной задачи Рассмотрим в качестве исходной задачу определения оптимальной производственной программы
3. Экономическое содержание двойственной задачи Предположим, предприятие рассматривает в качестве альтернативы продажу ресурсов. Определим, при каких условиях
4. Экономическое содержание двойственной задачи Выявить условия заключения сделки возможно на основании учета интересов потенциального покупателя и
5. Экономическое содержание двойственной задачи Учесть интересы сторон можно, решив задачу следующего содержания
6. Экономическое содержание двойственной задачи В данной задаче представляют собой маржинальные цены ресурсов, отражающие изменение выручки предприятия
7. Экономическое содержание двойственной задачи Для составления формулы целевой функции необходимо суммировать произведения запасов ресурсов на маржинальные
8. Экономическое содержание двойственной задачи В каждом ограничении сопоставляется, с одной стороны, оценка ресурсов, требуемых для выпуска
9. Экономическое содержание двойственной задачи Для составления левой части ограничения отбираются коэффициенты (нормы расхода ресурсов) по второму
10. Экономическое содержание двойственной задачи Таблица норм расхода ресурсов .
11. Правила построения двойственных задач Рассмотренные выше задачи являются симметричными: исходная – симметричная на максимум, а двойственная
12. Правила построения двойственных задач Если исходная задача – на максимум, то двойственная – на минимум целевой
13. Правила построения двойственных задач Знак неравенств меняется на противоположный; Матрица коэффициентов транспонируется; Коэффициенты при переменных в
14. Применение теории двойственности 2.1. На базе теории двойственности разработаны методы рационализации решения задач, симметричных на минимум;
15. Применение теории двойственности (2.1) Рассмотрим ЗЛП на составление технологической смеси, которая имеет симметричную на минимум форму
16. Применение теории двойственности (2.1) Исходная запись задачи:
17. Применение теории двойственности (2.1) Каноническая система ограничений:
18. Применение теории двойственности (2.1) Матрица канонической системы ограничений:
19. Применение теории двойственности (2.1) Можно преобразовать матрицу методом полного исключения переменных; Можно сформировать единичную матрицу с
20. Применение теории двойственности (2.1) Реализация первой или второй альтернативы является, как правило, более трудоемкой; Выбираем третью
21. Применение теории двойственности (2.1) Решив любую (прямую или двойственную) задачу симплекс-методом, мы получаем решения обеих задач.
22. Применение теории двойственности (2.1) 1. Если одна из задач имеет оптимальное решение, то оптимальное решение существует
23. Применение теории двойственности (2.1) 3. Решение двойственной задачи определяется в индексной строке по правилу соответствия
24. Применение теории двойственности (2.1) Правило соответствия не означает равенства значений указанных переменных. Справедливо следующее утверждение:
25. Применение теории двойственности (2.2) Постоптимизационный анализ – анализ оптимальной производственной программы, основой которого являются маржинальные цены
26. Применение теории двойственности (2.2) Маржинальные цены ресурсов являются основой принятия решений об изменении запаса ресурсов в
27. Применение теории двойственности (2.2) Маржинальные цены ресурсов информируют о дефицитности ресурсов; Если , то ресурс бездефицитен
28. Применение теории двойственности (2.2) Маржинальные цены можно использовать при принятии решений о расширении ассортимента; Предположим, рассматривается
30. Скачать презентацию

Слайд 2

Экономическое содержание двойственной задачи
Рассмотрим в качестве исходной задачу определения оптимальной производственной

программы

Слайд 3

Экономическое содержание двойственной задачи
Предположим, предприятие рассматривает в качестве альтернативы продажу ресурсов.

Определим, при каких условиях данная альтернатива может быть реализована.

Слайд 4

Экономическое содержание двойственной задачи
Выявить условия заключения сделки возможно на основании учета

интересов потенциального покупателя и предприятия как продавца ресурсов
Интерес продавца – получение дохода, не меньшего, чем доход от продажи продуктов по ценам
Интерес покупателя – минимизация затрат на приобретение запасов ресурсов

Слайд 5

Экономическое содержание двойственной задачи
Учесть интересы сторон можно, решив задачу следующего содержания

Слайд 6

Экономическое содержание двойственной задачи
В данной задаче представляют собой маржинальные цены ресурсов,

отражающие изменение выручки предприятия при изменении запаса соответствующего ресурса на единицу;
Целевая функция характеризует интерес потенциального покупателя
Ограничения характеризуют интерес предприятия как продавца ресурсов

Слайд 7

Экономическое содержание двойственной задачи
Для составления формулы целевой функции необходимо суммировать произведения

запасов ресурсов на маржинальные цены

Слайд 8

Экономическое содержание двойственной задачи
В каждом ограничении сопоставляется, с одной стороны, оценка

ресурсов, требуемых для выпуска единицы изделия, и, с другой стороны, цена продажи изделия

Слайд 9

Экономическое содержание двойственной задачи
Для составления левой части ограничения отбираются коэффициенты (нормы

расхода ресурсов) по второму индексу, обозначающему номер продукта. В таблице исходных данных эти коэффициенты образуют столбец.

Слайд 10

Экономическое содержание двойственной задачи
Таблица норм расхода ресурсов
.

Слайд 11

Правила построения двойственных задач
Рассмотренные выше задачи являются симметричными: исходная –

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

Слайд 12

Правила построения двойственных задач
Если исходная задача – на максимум, то двойственная

– на минимум целевой функции;
Число переменных двойственной задачи равно числу ограничений исходной задачи;
Число ограничений двойственной задачи равно числу переменных исходной задачи;

Слайд 13

Правила построения двойственных задач
Знак неравенств меняется на противоположный;
Матрица коэффициентов транспонируется;
Коэффициенты при

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

Слайд 14

Применение теории двойственности
2.1. На базе теории двойственности разработаны методы рационализации решения

задач, симметричных на минимум;
2.2. Двойственные оценки ресурсов (маржинальные цены) применяются в постоптимизационном анализе

Слайд 15

Применение теории двойственности (2.1)
Рассмотрим ЗЛП на составление технологической смеси, которая имеет

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

Слайд 16

Применение теории двойственности (2.1)
Исходная запись задачи:

Слайд 17

Применение теории двойственности (2.1)
Каноническая система ограничений:

Слайд 18

Применение теории двойственности (2.1)
Матрица канонической системы ограничений:

Слайд 19

Применение теории двойственности (2.1)
Можно преобразовать матрицу методом полного исключения переменных;
Можно сформировать

единичную матрицу с помощью искусственных переменных;
Можно отказаться от решения прямой задачи и решить двойственную задачу

Слайд 20

Применение теории двойственности (2.1)
Реализация первой или второй альтернативы является, как правило,

более трудоемкой;
Выбираем третью альтернативу;
По правилам строим двойственную (по отношению к исходной) задачу;
Решаем двойственную задачу симплекс-методом

Слайд 21

Применение теории двойственности (2.1)
Решив любую (прямую или двойственную) задачу симплекс-методом, мы

получаем решения обеих задач. Это следует из доказанных теорем двойственности.

Слайд 22

Применение теории двойственности (2.1)
1. Если одна из задач имеет оптимальное решение,

то оптимальное решение существует и у другой задачи.
2. Экстремальные значения целевых функций прямой и двойственной задачи одинаковы

Слайд 23

Применение теории двойственности (2.1)
3. Решение двойственной задачи определяется в индексной строке

по правилу соответствия

Слайд 24

Применение теории двойственности (2.1)
Правило соответствия не означает равенства значений указанных переменных.

Справедливо следующее утверждение:

Слайд 25

Применение теории двойственности (2.2)
Постоптимизационный анализ – анализ оптимальной производственной программы, основой

которого являются маржинальные цены ресурсов -

Слайд 26

Применение теории двойственности (2.2)
Маржинальные цены ресурсов являются основой принятия решений об

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

Слайд 27

Применение теории двойственности (2.2)
Маржинальные цены ресурсов информируют о дефицитности ресурсов;
Если ,

то ресурс бездефицитен ( его запас избыточен );
Если положительна, то запас ресурса используется полностью

Слайд 28

Применение теории двойственности (2.2)
Маржинальные цены можно использовать при принятии решений о

расширении ассортимента;
Предположим, рассматривается вопрос о целесообразности включения в производственную программу дополнительного вида продукции с номером l

Теория двойственности в линейном программировании

Содержание

Экономическое содержание двойственной задачиРассмотрим в качестве исходной задачу определения оптимальной производственной

Экономическое содержание двойственной задачиПредположим, предприятие рассматривает в качестве альтернативы продажу ресурсов.

Экономическое содержание двойственной задачиВыявить условия заключения сделки возможно на основании учета

Экономическое содержание двойственной задачиУчесть интересы сторон можно, решив задачу следующего содержания

Экономическое содержание двойственной задачиВ данной задаче представляют собой маржинальные цены ресурсов,

Экономическое содержание двойственной задачиДля составления формулы целевой функции необходимо суммировать произведения

Экономическое содержание двойственной задачиВ каждом ограничении сопоставляется, с одной стороны, оценка

Экономическое содержание двойственной задачиДля составления левой части ограничения отбираются коэффициенты (нормы

Экономическое содержание двойственной задачиТаблица норм расхода ресурсов.

Правила построения двойственных задач Рассмотренные выше задачи являются симметричными: исходная –

Правила построения двойственных задачЕсли исходная задача – на максимум, то двойственная

Правила построения двойственных задачЗнак неравенств меняется на противоположный;Матрица коэффициентов транспонируется;Коэффициенты при

Применение теории двойственности2.1. На базе теории двойственности разработаны методы рационализации решения

Применение теории двойственности (2.1)Рассмотрим ЗЛП на составление технологической смеси, которая имеет

Применение теории двойственности (2.1)Исходная запись задачи:

Применение теории двойственности (2.1)Каноническая система ограничений:

Применение теории двойственности (2.1)Матрица канонической системы ограничений:

Применение теории двойственности (2.1)Можно преобразовать матрицу методом полного исключения переменных;Можно сформировать

Применение теории двойственности (2.1)Реализация первой или второй альтернативы является, как правило,

Применение теории двойственности (2.1)Решив любую (прямую или двойственную) задачу симплекс-методом, мы

Применение теории двойственности (2.1)1. Если одна из задач имеет оптимальное решение,

Применение теории двойственности (2.1)3. Решение двойственной задачи определяется в индексной строке

Применение теории двойственности (2.1)Правило соответствия не означает равенства значений указанных переменных.

Применение теории двойственности (2.2)Постоптимизационный анализ – анализ оптимальной производственной программы, основой

Применение теории двойственности (2.2)Маржинальные цены ресурсов являются основой принятия решений об

Применение теории двойственности (2.2)Маржинальные цены ресурсов информируют о дефицитности ресурсов;Если ,

Применение теории двойственности (2.2)Маржинальные цены можно использовать при принятии решений о

Похожие презентации