А.3. Получение решения задачи по решению двойственной задачи
Используем теорему 2 и соотношения дополняющей нежёсткости для нахождения решения прямой задачи из решения ей двойственной задачи. Данную процедуру называют алгоритмом двойственности.
Алгоритм двойственности
Шаг 1. Построить и решить двойственную задачу , получить и .
Шаг 2. Определить
Шаг 3. Определить значения базисных переменных в решении .
Для этого необходимо воспользоваться соотношениями дополняющей нежёсткости: если переменная в оптимальном решении базисная, то соответствующее ей i - е неравенство прямой задачи можно заменить уравнением-равенством.
Шаг 4. После того, как часть уравнений-неравенств исходной системы прямой задачи заменится уравнениями-равенствами, решить эту систему уравнений и найти таким образом искомые значения базисных переменных прямой задачи.
В приведенном варианте алгоритма двойственности находится решение прямой задачи (максимизации функции z) по решению ей двойственной (минимизации функции ). Он, конечно, может быть использован и в обратном направлении – для нахождения решения задачи минимизации функции по решению задачи максимизации функции z.
Оптимальное решение двойственной задачи можно также найти из соотношения
,
где B - базисная матрица, соответствующая базису ß решения прямой задачи,
- подвектор коэффициентов целевой функции, соответствующих базисным переменным оптимального решения .
1 Если исходная задача содержит целочисленные переменные, то провести постоптимальный анализ задачи, полученной из исходной задачи отбрасыванием условий целочисленности.
2 Если исходная задача содержит целочисленные переменные, то симплекс-методом решить задачу, полученную из исходной задачи отбрасыванием условий целочисленности.
3 В этом разделе дать подробное описание содержательного смысла используемых переменных, целевой функции и ограничений.
4 При создании листов рабочей книги продумать интерфейс листа (заголовки столбцов и строк, содержательный смысл ячеек).
5 Дать расширенный ответ (по всем пунктам решения и постоптимального анализа) в терминах содержательной постановки.
6 Здесь и далее термины "изменяемая ячейка" и "переменная" являются синонимами
7 В разработке данного вопроса принимал участие Бочаров А.А. (ИС-81).
8 Далее прямой задачей будем называть задачу на максимум, двойственной – задачу на минимум.
- Содержание
- 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. Получение решения задачи по решению двойственной задачи