Navigation bar
  Print document Start Previous page
 34 of 115 
Next page End  

34
Согласно критерию оптимальности, на последней итерации данная строка неотрицательна, т. е. ?А?с.
Следовательно, вектор и является допустимым планом двойственной задачи.
В то же время элемент b
0
(?
(q)
), содержащий текущее значение целевой функции и равный на
последней итерации f(x*), допускает представление
Согласно теореме 1.5 из равенства f(х*) = f*(u) вытекает, что вектор u служит оптимальным планом
двойственной задачи: u =
u.
 
Окончательно можно утверждать, что для оптимального базиса
Таким образом, существенным преимуществом модифицированного симплекс-метода является то,
что он позволяет одновременно найти оптимальные планы как, прямой, так и двойственной
задачи.
Читателю в качестве самостоятельного упражнения предлагается построить задачу, двойственную к
(1.34)-(1.35), решение которой было приведено в п. 1.5.2, и убедиться, что вектор u = (-10, 32, 2),
полученный в таблице Т2
(3)
, является для нее допустимым и оптимальным планом.
1.6.4. Экономическая интерпретация. Традиционная экономическая интерпретация двойственной
задачи ЛП базируется на модели простейшей задачи производственного планирования, описанной во
введении. Напомним, что в ней каждый (j-й) элемент вектора х рассматривается как план выпуска
продукции данного вида в натуральных единицах, с
j
— цена единицы продукции j-го вида, а
j
— вектор,
определяющий технологию расходования имеющихся m ресурсов на производство единицы продукции
j-го вида, b вектор ограничений на объемы этих ресурсов.
Предположим, что для некоторых значений A, b и с найден оптимальный план х*, максимизирующий
суммарный доход max{cx}=cx*. Достаточно естественным представляется вопрос: как будет изменяться
оптимальный план х* при изменении компонент вектора ограничений b и, в частности, при каких
вариациях b оптимальный план х* останется неизменным? Данная задача получила название проблемы
устойчивости оптимального плана. Очевидно, что исследование устойчивости х* имеет и
непосредственное практическое значение, так как в реальном производстве объемы доступных ресурсов
b
i
; могут существенно колебаться после принятия планового решения х*.
Когда вектор ограничений b изменяется на
?
b
или, как еще говорят, получает приращение
?
b, то
возникают соответствующие вариации для оптимального плана х*(b+?b) и значения целевой функции
f(х*(b+?b)). Допустим, приращение
?
b таково, что оно не приводит к изменению оптимального базиса
задачи, т. е. х*(b+?b)?
0. Определим функцию
F(b), возвращающую оптимальное значение целевой
функции задачи (D(b), f) для различных значений вектора ограничений b
Рассмотрим отношение ее приращения
F(b+?b)-F(b) к приращению аргумента
?
b. Если для
некоторого i устремить
?
b
i >
0, то мы получим
Учитывая, что в соответствии с теоремой 1.5
Сайт создан в системе uCoz