Приложение а Основные положения теории двойственности а.1. Построение двойственных задач
Двойственная задача – это задача линейного программирования (ЗЛП), которая формулируется с помощью определённых правил непосредственно из условий прямой задачи [3].
Рассмотрим обобщённую формулировку двойственной задачи ЛП, которая применима к любой форме представления исходной задачи. В основу такой формулировки положен тот факт, что использование симплекс-метода требует приведения любой ЗЛП к канонической форме.
Пусть имеем прямую ЗЛП в канонической форме:
;
при ограничениях : ;
.
Заметим, что в состав n переменных xj включаются так же избыточные и остаточные переменные.
Двойственная задача получается путём структурного преобразования условий прямой задачи в соответствии со следующими правилами (рис. А.1):
-
каждому ограничению прямой задачи соответствует переменная двойственной задачи;
-
каждой переменной прямой задачи соответствует ограничение двойственной задачи;
-
коэффициенты при некоторой переменной прямой задачи (столбец), становятся коэффициентами левой части соответствующего ограничения двойственной задачи (строкой) ;
-
коэффициент при переменной в выражении для целевой функции прямой задачи, становится постоянной правой части соответствующего ограничения двойственной задачи;
-
направление оптимизации, ограничения и знаки двойственных переменных формируются согласно таблице А.1.
Таблица А.1.
-
Направление оптимизации целевой функции прямой задачи (в канонической форме)
Двойственная задача
целевая функция
ограничения
переменные
Максимизация
Минимизация
Минимизация
Максимизация
Не огр. в знаке
Не огр. в знаке
-
x1
x2
…
xj
…
xn
c1
c2
…
cj
…
cn
a11
a12
…
a1j
…
a1n
b1
y1
a21
a22
…
a2j
…
a2n
b2
y2
…
…
…
…
…
…
ai1
ai2
…
aij
…
ain
bi
yi
…
…
…
…
…
…
am1
am2
…
amj
…
amn
bm
ym
Рис. А.1.
Таким образом, двойственная задача имеет m переменных (у1, у2,…,уm) и n ограничений.
Если двойственную задачу рассматривать в качестве исходной, то соответствующая ей двойственная задача будет прямой. Т.е. прямая и двойственная задачи являются взаимно-двойственными, поэтому о них говорят как о паре двойственных задач. Особо рассматриваются две пары двойственных задач8 – симметричные и несимметричные.
Пара симметричных двойственных задач
Прямая задача ;
; (А.1)
.
Двойственная задача ;
; (A.2)
.
Пара несимметричных двойственных задач
Прямая задача ;
; (A.3)
.
Двойственная задача ;
; (A.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. Получение решения задачи по решению двойственной задачи