Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Решение симметричных задач
Рассмотрим решение задач с использованием теорем двойственности.
Исходная задача
при ограничениях:
Двойственная задача
при ограничениях:
Решим исходную задачу графическим методом, получим , при этом
На основании 1-й теоремы двойственности
Так как , >0, то по второй теореме двойственности систему ограничений двойственной задачи можно записать в виде равенств:
Подставим в систему ограничений исходной задачи:
Тогда система ограничений двойственной задачи примет вид
Откуда , при этом
Пусть дано решение двойственной задачи , , найдём решение исходной.
По 1-й теореме двойственности Так как , > 0, то по 2-й теореме двойственности второе и третье неравенства исходной задачи обращаются в равенства:
Откуда , при этом
Рассмотрим решение задач методом, основанным на взаимно однозначном соответствии между переменными: основным переменным исходной задачи соответствуют балансовые переменные двойственной, и наоборот. Для этого решим двойственную задачу симплексным методом:
при ограничениях:
Из табл. 4.1 следует, что , .
Таблица 4.1
bj | БП | ||||||
y1 | y2 | y3 | y4 | y5 | cj | ||
-2 | -2 | -1 | -1 | -1 |
bj | БП | ||||||
y1 | y2 | y3 | y4 | y5 | cj | ||
y2 | -2 -3 | -1 -2 | -1 |
bj | БП | ||||||
y1 | y2 | y3 | y4 | y5 | cj | ||
y2 y3 | -1 -1 | -1/3 -2/3 | 1/3 -1/3 | 2/3 1/3 | |||
∆i | -9 | -4 | -1 |
На основании 1-й теоремы двойственности получаем
Решение другой задачи найдём по соответствию между переменными:
Основные переменные | Балансовые переменные | |
Исходная задача | x1 x2 | x3 x4 x5 |
Двойственная | y4 y5 | y1 y2 y3 |
Балансовые переменные | Основные переменные |
Значение xj определяем по последней симплексной таблице в строке ∆ i в соответствующем столбце, причём значения xj берутся по модулю:.
Таким образом, решение двойственной задачи:
, .
Если исходная задача решена симплексным методом, то решение двойственной задачи может быть найдено по формуле где С – матрица-строка коэффициентов при базисных переменных целевой функции в оптимальном решении исходной задачи; А-1 – обратная матрица для матрицы А, являющейся матрицей коэффициентов системы ограничений исходной задачи для базисных переменных в оптимальном решении.
Решим симплексным методом исходную задачу вида
при ограничениях:
Таблица 4.2
сi | БП | -1 | |||||
х1 | х2 | х3 | х4 | х5 | bi | ||
x3 x4 x5 | -2 | -2 | |||||
∆j | -1 |
сi | БП | -1 | |||||
х1 | х2 | х3 | х4 | х5 | bi | ||
x3 x1 x5 | -3 -2 | -1 | |||||
∆j | -1 |
сi | БП | -1 | |||||
х1 | х2 | х3 | х4 | х5 | bi | ||
-1 | x3 x1 x2 | 1/3 -1/3 | 2/3 1/3 | ||||
∆j | 2/3 | 1/3 |
Из табл. 4.2 следует, что , при этом
Матрицы записываются в виде
, , тогда .
= .
Таким образом, решение двойственной задачи следующее:
, при этом .
Решение несимметричных задач
Рассмотрим решение задач с использованием теорем двойственности.
Исходная задача
Двойственная задача
у1, у2 – произвольные по знаку.
Решив двойственную задачу графическим методом, получим
, при этом
По 1-й теореме двойственности
Подставим в систему ограничений двойственной задачи:
3=3,
1=1,
-21/2<3 ,
-3<1
Так как х3 = х4 = 0, то система исходной задачи примет вид
Решая данную систему, получим , при этом
Рассмотрим решение задач с использованием обратной матрицы.
Пусть решение исходной задачи , при этом
Решение двойственной задачи найдём по формуле где
, , = .
Таким образом, , .
Решение смешанных двойственных задач
Смешанные двойственные задачи можно решать с использованием теорем двойственности.
Исходная задача
Двойственная задача
у1 – произвольная по знаку,
у2
Найдём оптимальное решение двойственной задачи, решив сначала исходную симплексным методом:
, при этом
По 1-й теореме двойственности
Так как х1 > 0, x3 > 0, то по 2-й теореме двойственности первое и третье ограничения двойственной задачи выполняются в виде равенств: ,
откуда у1 = -5/3, у2 = 4/3, т. е.
Дата публикования: 2015-03-26; Прочитано: 453 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!