Слайд 2
![С каждой задачей линейного программирования тесно связана другая линейная задача,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-1.jpg)
С каждой задачей линейного
программирования тесно связана другая
линейная задача, называемая
двойственной к исходной.
Пусть дана задача ЛП. Максимизировать линейную функцию
Слайд 3
![При ограничениях Или в матричном виде](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-2.jpg)
При ограничениях
Или в матричном виде
Слайд 4
![Двойственная к ней задача формулируется следующим образом Минимизировать линейную функцию при ограничениях](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-3.jpg)
Двойственная к ней задача
формулируется следующим образом
Минимизировать линейную
функцию
при ограничениях
Слайд 5
![или в матричном виде](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-4.jpg)
или в матричном виде
Слайд 6
![Задачи (5.9), (5.10) и (5.11), (5.12) образуют пару взаимодвойственных задач,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-5.jpg)
Задачи (5.9), (5.10) и (5.11), (5.12)
образуют пару взаимодвойственных
задач, и
любая из них может
рассматриваться как исходная.
Решать исходную или двойственную
задачу – вопрос лишь удобства
Математические модели двойственных
задач могут быть симметричными и
несимметричными. В табл. 5.13, 5.14
приведены их матричные формы записи
Слайд 7
![5.7.1.Симметричные задачи В симметричных задачах система ограничений как исходной, так](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-6.jpg)
5.7.1.Симметричные задачи
В симметричных задачах система
ограничений как исходной, так и
двойственной задачи задается
неравенствами, причем на
двойственные переменные налагается
условие неотрицательности.
Слайд 8
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-7.jpg)
Слайд 9
![5.7.2. Несимметричные задачи В несимметричных двойственных задачах система ограничений исходной](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-8.jpg)
5.7.2. Несимметричные задачи
В несимметричных двойственных
задачах система ограничений исходной
задачи задается
в виде равенств, а в
двойственной - в виде неравенств,
причем в последней переменные могут
быть и отрицательными.
Слайд 10
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-9.jpg)
Слайд 11
![Пример 5.11. Даны прямые задачи. Построить двойственные к ним задачи.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-10.jpg)
Пример 5.11. Даны прямые задачи.
Построить двойственные к ним задачи.
Слайд 12
![Решение. Рассматриваемая задача относится к симметричным двойственным задачам на отыскание](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-11.jpg)
Решение. Рассматриваемая задача
относится к симметричным двойственным
задачам на отыскание максимального
значения
целевой функции.
Используем общие правила
составления двойственных задач. Так
как в задаче на максимум ограничения
неравенства должны иметь вид « < », то
умножим второе ограничение-
неравенство на -1.
Исходная задача запишется в виде
Слайд 13
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-12.jpg)
Слайд 14
![Найдем соответствующую двойственную задачу (строка 1, табл. 5.13). Введем вектор](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-13.jpg)
Найдем соответствующую
двойственную задачу (строка 1, табл.
5.13). Введем вектор двойственных
переменных размерности 3 (по числу
уравнений системы ограничений) .
Соответствующие векторы и матрица
ограничений имеет вид:
Слайд 15
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-14.jpg)
Слайд 16
![Запишем двойственную задачу. Найти минимум функции](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-15.jpg)
Запишем двойственную задачу. Найти
минимум функции
Слайд 17
![Укажем еще один метод, позволяющий значительно облегчить процесс построения двойственных](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-16.jpg)
Укажем еще один метод, позволяющий
значительно облегчить процесс
построения двойственных задач.
Каждому ограничению прямой задачи
поставим в соответствие двойственные
переменные.
Слайд 18
![Чтобы получить, например, первое ограничение двойственной задачи, надо найти сумму](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-17.jpg)
Чтобы получить, например, первое
ограничение двойственной задачи, надо
найти сумму произведений
элементов,
стоящих в столбце , на
соответствующие двойственные
переменные. Результат
Считаем, что эта сумма не меньше
Аналогично составляются и остальные
ограничения двойственной задачи.
Слайд 19
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-18.jpg)
Слайд 20
![Решение. Каждому ограничению прямой задачи поставим в соответствие двойственные переменные](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-19.jpg)
Решение. Каждому ограничению
прямой задачи поставим в соответствие
двойственные переменные
Слайд 21
![Составим двойственную задачу: Переменная , соответствующая ограничению-равенству может быть любого знака.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-20.jpg)
Составим двойственную задачу:
Переменная , соответствующая
ограничению-равенству
может быть любого знака.
Слайд 22
![5.7.3. Первая теорема двойственности Если из двух задач (исходной и](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-21.jpg)
5.7.3. Первая теорема двойственности
Если из двух задач (исходной и
двойственной) одна
имеет решение, то
другая задача также имеет решение,
причем максимальное значение целевой
функции исходной задачи и минимальное
значение двойственной задачи численно
равны
Слайд 23
![Если же одна из задач не имеет оптимального решения, то](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-22.jpg)
Если же одна из задач не имеет
оптимального решения, то система
ограничений двойственной задачи
противоречива
5.7.4. Экономическая интерпретация двойственной задачи.
Пусть - оптимальное
решение прямой задачи, а
оптимальное решение двойственной
задачи
Слайд 24
![На основании первой теоремы двойственности можно записать Найдем](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-23.jpg)
На основании первой теоремы
двойственности можно
записать
Найдем
Слайд 25
![Учитывая, что функция линейная, получим Из последней формулы следует: значения](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-24.jpg)
Учитывая, что функция линейная,
получим
Из последней формулы следует:
значения переменных в оптимальном
решении двойственной
задачи
представляют собой оценки влияния
свободных членов системы
ограничений прямой задачи на величину
Слайд 26
![Пример 5.12. Для производства двух видов продукции предприятие использует четыре](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-25.jpg)
Пример 5.12. Для производства двух
видов продукции предприятие использует
четыре вида сырья
Затраты сырья
на единицу каждого вида
продукции, прибыль и запасы сырья даны
в табл.
Слайд 27
![Составить план производства, обеспечивающий предприятию максимальную прибыль. Математическая модель прямой](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-26.jpg)
Составить план производства,
обеспечивающий предприятию
максимальную прибыль.
Математическая модель прямой
задачи
Обозначим через
- количество
единиц продукции, соответственно I и II
видов.
Тогда задача заключается в следующем:
Слайд 28
![максимизировать целевую функцию при ограничениях](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-27.jpg)
максимизировать целевую функцию
при ограничениях
Слайд 29
![Запишем задачу в матричном виде. где - вектор неизвестных, -](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-28.jpg)
Запишем задачу в матричном виде.
где - вектор неизвестных,
- вектор
коэффициентов
целевой функции,
- вектор правых частей
системы ограничений,
Слайд 30
![- матрица коэффициентов системы ограничений. Решение прямой задачи дает оптимальный](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-29.jpg)
- матрица коэффициентов
системы ограничений.
Решение прямой задачи дает
оптимальный план выпуска
продукции I и
II видов.
Поставим в соответствие прямой
задаче двойственную задачу.
Слайд 31
![Пример 5.13. Предприятию необходимо определить минимальное суммарное количество сырья каждого](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-30.jpg)
Пример 5.13. Предприятию необходимо
определить минимальное суммарное
количество сырья каждого из видов
применив прежнее
условие примера 5.12.
Математическая модель
двойственной задачи
В качестве переменных двойственной
задачи возьмем
представляющие собой условные оценки
запасов сырья
Слайд 32
![Представим двойственную задачу в матричном виде где - вектор двойственных](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-31.jpg)
Представим двойственную задачу в
матричном виде
где - вектор
двойственных переменных;
-
транспонированная
матрица коэффициентов системы ограничений
Слайд 33
![Раскрывая соотношение (5.14) можно сформулировать двойственную задачу так: найти минимум целевой функции при ограничениях](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-32.jpg)
Раскрывая соотношение (5.14) можно
сформулировать двойственную задачу
так:
найти минимум целевой функции
при
ограничениях
Слайд 34
![Чтобы найти решение этих задач решим одну из них –](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-33.jpg)
Чтобы найти решение этих задач
решим одну из них – прямую, т.к.
система
ограничений этой задачи содержит лишь
неравенства « < ». Решение находим
симплексным методом.
Приведем задачу к каноническому виду
Слайд 35
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-34.jpg)
Слайд 36
![Запишем систему ограничений в векторном виде где](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-35.jpg)
Запишем систему ограничений в
векторном виде
где
Слайд 37
![Составим первую симплекс- таблицу](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-36.jpg)
Составим первую симплекс- таблицу
Слайд 38
![Поскольку отыскивается максимум задачи, то критерий оптимальности для плана не](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-37.jpg)
Поскольку отыскивается максимум
задачи, то критерий оптимальности для
плана не выполнен, т.к.
в - строке
имеются отрицательные оценки.
Дальнейшие результаты пошагового
решения задачи представлены в табл.
5.15 – 5.17.
Слайд 39
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-38.jpg)
Слайд 40
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-39.jpg)
Слайд 41
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-40.jpg)
Слайд 42
![В последней таблице - строка не содержит отрицательных оценок, что свидетельствует об оптимальности полученного решения:](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-41.jpg)
В последней таблице - строка не
содержит отрицательных оценок, что
свидетельствует
об оптимальности
полученного решения:
Слайд 43
![Оптимальное решение двойственной задачи может быть получено из оптимального решения](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-42.jpg)
Оптимальное решение двойственной
задачи может быть получено из
оптимального решения прямой
задачи.
Так как прямая задача имеет решение,
то на основании теоремы о
двойственности двойственная задача
также разрешима. Ее решение может
быть найдено из формулы
Слайд 44
![где - матрица, составленная из компонент векторов, входящих в последний](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-43.jpg)
где - матрица, составленная из
компонент векторов, входящих в
последний базис,
при котором получен
оптимальный план исходной задачи.
В нашем примере в последней
симплекс-таблице базисными
переменными являются
Слайд 45
![Соответствующие этим переменным векторы в разложении (5.14) используются для формирования столбцов матрицы](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-44.jpg)
Соответствующие этим переменным
векторы в разложении (5.14)
используются для формирования
столбцов матрицы
Слайд 46
![Вычислим Так как то](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-45.jpg)
Слайд 47
![При этом минимальное значение целевой функции двойственной задачи совпадает с максимальным значением прямой задачи.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-46.jpg)
При этом минимальное значение
целевой функции двойственной задачи
совпадает с максимальным значением
прямой задачи.
Слайд 48
![Проведем анализ полученного оптимального решения двойственной задачи. Рассмотрим экономическое содержание](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-47.jpg)
Проведем анализ полученного
оптимального решения двойственной
задачи.
Рассмотрим экономическое
содержание двойственных
оценок.
Предположим, что запасы сырья
увеличены на 1единицу.
Пользуясь формулой (5.13), найдем
Слайд 49
![Нулевые оценки и означают, что данное сырье не полностью используется](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-48.jpg)
Нулевые оценки и означают,
что данное сырье не полностью
используется (является недефицитным)
и дальнейшее
его увеличение не
повлияет на оптимальный план выпуска
продукции и сумму прибыли.
Слайд 50
![Если увеличить запасы сырья на 1 (ед.), то прибыль увеличится](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-49.jpg)
Если увеличить запасы сырья на
1 (ед.), то прибыль увеличится на 0,75
(ед.).
Если увеличить запасы сырья на
1 (ед.), то прибыль увеличится на 2,75
(ед.).
Слайд 51
![Запасы сырья и полностью используются в оптимальном плане, являются дефицитными и сдерживают рост целевой функции.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/7775/slide-50.jpg)
Запасы сырья и полностью
используются в оптимальном плане,
являются дефицитными и сдерживают
рост целевой функции.