А.2. Основные теоремы двойственности
Теорема 1 (соотношения двойственности) [4]
Пусть прямая и двойственная задачи имеют допустимые решения. И пусть x и y – это допустимые решения прямой и двойственной задач соответственно. Тогда справедливо неравенство
, (А.5)
при чём для достижения равенства в (А.5) необходимо и достаточно выполнение условий:
; (А.6)
. (А.7)
Соотношения (А.6) и (А.7) называются соотношениями дополняющей нежёсткости.
Следствие 1 теоремы 1
Пусть , – допустимые решения прямой и двойственной задач, для которых выполняется: . Тогда , являются решениями прямой и двойственной задач соответственно.
Следствие 2 теоремы 1
Если целевая функция прямой задачи не ограничена сверху, то двойственная задача не имеет допустимых решений.
Теорема 2 (о равенстве значений пары двойственных задач)
Пусть прямая и двойственная задачи имеют решения и соответственно. Тогда выполняется равенство:
При решении прямой задачи возможна только одна из следующих взаимоисключающих друг друга ситуаций:
I прямая задача имеет решение;
II целевая функция неограниченна сверху на множестве допустимых решений;
III прямая задача имеет решение/
Аналогично, при решении двойственной задачи возможна только одна из следующих взаимоисключающих ситуаций:
I’ двойственная задача имеет решение;
II’ целевая функция двойственной задачи не ограничена снизу на множестве допустимых решений;
III’ двойственная задача не имеет допустимых решение.
Комбинируя попарно ситуации I, II, III с I’, II’, III’ получаем, что принципиально возможны следующие 9 пар, которые можно представить в виде таблицы А2.
Таблица А.2
-
I (o'k)
II ()
III ()
I' (o'k)
1)
2)
3)
II' ()
4)
5)
6)
III' ()
7)
8)
9)
Согласно следующей теореме, никакие пары, кроме 1), 6), 8), 9) не возможны вообще.
Теорема 3 (двойственности)
Для пары взаимно-двойственных задач имеет место один из следующих взаимоисключающих случаев:
1) Прямая и двойственная задачи имеют решения, причём значения задач совпадают.
2) Прямая задача имеет непустое множество допустимых решений, а целевая функция не ограничена сверху; двойственная задача не имеет допустимых решений.
3) Двойственная задача имеет непустое множество допустимых решений, её целевая функция не ограничена снизу; прямая задача не имеет допустимых решений.
4) Прямая и двойственная задачи не имеют допустимых решений.
- Содержание
- 1. Порядок выполнения расчетно-графической работы
- Решение задачи симплекс-методом.2
- 2. Содержание отчета по расчетно-графической работе
- Планирование операции
- Содержательная постановка задачи.
- Решение задачи симплекс-методом.
- 3. Варианты заданий расчетно-графической работы
- 3.1. Задания на планирование операции
- 3.2. Задания на применение графического способа решения задач линейного программирования
- 4. Электронная таблица Microsoft Excel
- 4.1. Терминология Excel
- 4.3.6. Ввод чисел или текста
- Ввод текста
- Ввод чисел
- Ввод дат или времени суток
- 4.3.7. Формулы
- 5. Решение задачи линейного программирования средствами Microsoft Excel
- 5.1. Содержательная формулировка задачи Задача определения ассортимента выпуска продукции [3]
- 5.2. Математическая формулировка задачи
- Суммарное время Предельное время
- 5.3. Решение задачи с помощью Microsoft Excel
- Содержимое ячеек таблицы:
- 5.4. Нахождение оптимального решения с помощью процедуры поиска решения
- 5.5. Итоговые сообщения процедуры поиска решения
- 6. Постоптимальный анализ задач линейного программирования
- 6.1. Содержательная постановка задачи
- 6.2. Математическая модель
- 6.3. Решение с помощью Microsoft Excel
- 6.4. Решение задачи симплекс-методом
- 6.5. Определение ценности ресурсов
- Прямая задача:
- В нашей задаче:
- 6.6.1.2. Дефицитные ресурсы Теоретические сведения
- В нашей задаче:
- Теоретические сведения:
- В нашей задаче:
- 6.6.2. Изменение коэффициентов целевой функции
- 6.6.2.1. Небазисные переменные Теоретические сведения
- 6.6.2.2. Базисные переменные Теоретические сведения
- В нашей задаче:
- 6.6.3. Результаты решения и постоптимального анализа задачи
- 6.6.3.1. Оптимальное решение задачи
- 6.6.3.2. Диапазоны изменения уровня запасов ресурсов
- 6.6.3.3. Ценность ресурсов
- 6.6.3.4. Диапазоны изменения цен продукции
- 6.6.4. Некоторые особенности проведения постоптимального анализа задач средствами Excel
- 6.6.4.1. Наличие ограничений типа или
- 6.6.4.2. Наличие альтернативных оптимумов
- Список литературы
- Приложение а Основные положения теории двойственности а.1. Построение двойственных задач
- А.2. Основные теоремы двойственности
- А.3. Получение решения задачи по решению двойственной задачи