|
|
Вторая теорема двойственностиОбъективно обусловленные оценки Тесная связь между двумя взаимно двойственными задачами проявляется не только в равенстве оптимальных значений их линейных функций, о чём утверждалось в первой (основной) теореме двойственности. Пусть даны две взаимно двойственные задачи, представленные в таблице 5.4.1.
Таблица 5.4.2
Если каждую из этих задач решать симплексным методом, то необходимо привести их к каноническому виду, для чего в систему ограничений задачи I следует ввести m неотрицательных переменных xn+1, xn+2, …, xn+i, …, xn+m, а в систему ограничений задачи II – n неотрицательных переменных ym+1, ym+2, …, ym+j, …, ym+n. Системы ограничений каждой из взаимно двойственных задач примут вид:
Установим соответствие между первоначальными переменными одной из двойственных задач и дополнительными переменными другой задачи (таблице 5.4.2). Таблица 5.4.1. Положительным (ненулевым) компонентом оптимального решения одной из взаимно двойственных задач соответствуют нулевые компоненты оптимального решения другой задачи, т.е. для любых i = 1, 2, …, m и j = 1, 2, …, n: если x*j > 0, то y*m+j = 0, если x*n+1 > 0, то y*i = 0 и аналогично, если y*I > 0, то x*n+i = 0; если y*m+j > 0, то x*j = 0. Из приведённой теоремы следует важный вывод о том, что введённое ранее соответствие в таблице 4.1 между переменными взаимно двойственных задач при достижении оптимума (т.е. на последнем шаге решения каждой задачи симплексным методом) представляет сооветствие между основными (как правило, не равными нулю) переменными одной из двойственных задач и неосновными (равными нулю) переменными другой задачи, когда они образуют допустимые базисные решения. Рассмотренная теорема является следствием следующей теоремы. Вторая теорема двойственности. Компоненты оптимального решения двойственной задачи равны абсолютным значениям коэффициентов при соотвествующих переменных линейной функции исходной задачи, выраженной через неосновные переменные её оптимального решения. Убедимся в справедливости второй теоремы двойственности для взаимно двойственных задач I и II, приведённых в задаче 4.1. Решение. На основании соответствий, установленных в таблице 5.4.1, установим следующее соответствие между переменными:
В разделе 3 обе задачи были решены симплексным методом. На последнем шаге решения каждой задачи получено:
(5.4.1)
при оптимальном базисном решении: X* = (6; 4; 0; 0; 1; 3). В двойственной задаче II
(5.4.2)
при оптимальном базисном решении
Компоненты оптимального решения двойственной задачи y*1 = 4/5, y*2=3/5, y*3 = 0, y*4 = 0, y*5 = 0, y*6 = 0 равны (по абсолютной величине) коэффициентам при соответствующих переменных линейной функции (5.4.1), которую можно представить в виде
а компоненты оптимального решения исходной задачи x*1 = 6, x*2 = 4, x*3 = 0, x*4 = 0, x*5 = 1, x*6 = 3 равны коэффициентам при соответствующих переменных линейной функции (5.4.2), которую можно представить в виде
Компоненты оптимального решения двойственной задачи называются оптимальными (двойственными) оценками исходной задачи. Академик Л. В. Канторович назвал их объективно обусловленными оценками. Для выяснения смысла этих оценок вернёмся к задаче I об использовании ресурсов и двойственной ей задаче II (см задачу 4.1). Компоненты оптимальных решений этих задач, приведённые в задаче 4.1 даны в таблице 5.4.3. Таблица 5.4.3
В таблице 5.4.3 дополнительные переменные исходной задачи I х3, х4, х5, х6, представляющие разность между запасами bi ресурсов S1, S2, S3, S4 и их потреблением, выражающие остатки ресурсов, а дополнительные переменные двойственной задач II у5, у6. представляющие разность между затратами на ресурсы для производства из них единицы продукции и ценами cj продукции P1, P2, выражают превышение затрат над ценой. Ресурсы S1, S2 по оптимальному плану полностью использованы (х*3= 0, х*4 = 0) и объективно обусловленные оценки этих ресурсов ненулевые (у1=4/5; у2 = 3/5). Ресурсы S3, S4 не полностью используются в оптимальном плане (x5 = 1, x6 = 3) и объективно обусловленные оценки этих ресурсов нулевые (у*3 = 0, у*4 = 0). Таким образом, объективно обусловленные оценки ресурсов определяют степень дефицитности ресурсов: по оптимальному плану производства дефицитные (т.е. полностью используемые) ресурсы получают ненулевые оценки, а недефицитные – нулевые оценки. По оптимальному плану в исходной задаче следует производить оба вида продукции (х*1 = 6, х*2 = 4), и превышение затрат на ресурсы над ценой реализации равно нулю (у5 = 0, у6 = 0). Если бы затраты на ресурсы превышали цену изготавливаемой из них продукции, например продукции Р2, т.е. если бы у*6 > 0, то на основании теоремы 4.1 оптимальное значение соответствующей переменной х*2 = 0, и в этом случае по оптимальному плану производить продукцию Р2 не следовало. Итак, в оптимальный план производства могут попасть только рентабельные, неубыточные виды продукции (правда, критерий рентабельности здесь своеобразный: цена продукции не превышает затраты на потребляемые при её изготовлении ресурсы, а в точности равна им).
Транспортная задача.   ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...  Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...  Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...  Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
В исходной задаче I
,
,
,
,
