|
|
Вторая теорема двойственностиОбъективно обусловленные оценки Тесная связь между двумя взаимно двойственными задачами проявляется не только в равенстве оптимальных значений их линейных функций, о чём утверждалось в первой (основной) теореме двойственности. Пусть даны две взаимно двойственные задачи, представленные в таблице 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 не следовало. Итак, в оптимальный план производства могут попасть только рентабельные, неубыточные виды продукции (правда, критерий рентабельности здесь своеобразный: цена продукции не превышает затраты на потребляемые при её изготовлении ресурсы, а в точности равна им).
Транспортная задача.   Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...  Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...  Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...  Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
В исходной задаче I
,
,
,
,
