Сделай Сам Свою Работу на 5

Теорема о дополняющей нежесткости





Для того чтобы допустимые Z,U были оптимальными, необходимо и достаточно выполнение условия

=0 и =0.

Это означает, что в точке оптимума никогда не может одновременно быть так, чтобы
i-я компонента вектора переменных основной задачи была положительна, а i-е неравенство двойственной задачи выполнялось строго (неравенства приобретают форму равенств). Если известно оптимальное решение двойственной задачи, то, подставив его в приведенные выражения, получим два линейных уравнения для . Вместе с они составляют систему уравнений, из которой можно определить решение поставленной задачи.

Исходный пример. Пусть требуется решить задачу линейного программирования (8.22),(8.23).

Рассмотрим ДЗЛП, которая является СЗЛП

при ограничениях

,

zi ≥ 0.

Эта СЗЛП была рассмотрена ранее (п.8.4). В результате ее решения получены решения z2 = z3 = 0 (внебазисные переменные), z1 = 5,541; z4 = 3,918; z5 = 2,459 (базис). Ф=СХ=-77,9672. Отсюда уравнения 1,4,5в(8.23). приобретают форму равенств, а 2,3 – строгих неравенств. Решение определяется из системы уравнений.

.

В результате =(-5; -2,13; -22,39)t. F= =-77,97= .

Интерпретация двойственной задачи



В то время как физическая интерпретация исходной задачи ясна, смысл двойственной задачи не столь очевиден. Возникает вопрос, как интерпретировать линейную форму и условия двойственной задачи. Лучше всего на этот вопрос можно ответить с помощью формулировки исходной и двойственной задач в терминах размерностей. Пусть рассматривается предприятие, выпускающее ряд изделий (болты, гайки, шайбы и др.). При этом используются некоторые ресурсы (сырье, материалы, финансы и др.), причем одни и те же ресурсы используются для разных видов продукции. Исходная задача заключается, например, в максимизации суммарного дохода.

при условиях, что используемые ресурсы не превысят некоторых заданных пределов

, i=1,2,…,m; j=1,2,…,n.

Рассмотрим, каковы должны быть размерности переменных и матриц преобразования в так называемой двойственной задаче, которая сводится к минимизации

(8.24)

при условиях

ui≥0, i=1,2,…,m; j=1,2,…,n.

Очевидно, что размерности условий двойственной задачи будут совпадать, если ui совпадет с ценой i-го ресурса (ценность ресурса в конечном продукте), а в левой части (8.24) будет суммарная стоимость всех ресурсов. Тогда двойственная задача состоит в минимизации



min

при условиях

Таким образом, задачи двойственной пары могут быть сформулированы следующим образом:

Исходная задача. Сколько единиц хj, j=1, 2, ...,n каждого вида продукции, нужно выпустить при удельном доходе сj и данном предельном потреблении каждого из имеющихся ресурсов bi, i=1, 2, ...,m, чтобы получить от всего производства максимальную прибыль?

Двойственная задача. Какой должна быть цена ui, i=1, 2, ...,m каждого из ресурсов, чтобы при максимальном их использовании (объем bi) обеспечить минимальную суммарную стоимость ресурсов, и при этом гарантировать удельные доходы не меньше заданных сj, j=1, 2, ...,n?

Двойственные переменные u именуются в различных источниках по-разному, в частности, они называются учетными, неявными или фиктивными ценами.

Транспортная задача

Другим типичным примером задачи линейного программирования является представленная в начале главы транспортная задача, для которой, в силу ее широкого распространения, разработано достаточно большое число оригинальных алгоритмов. В типовой постановке транспортная задача формулируется следующим образом. Требуется составить план перевозок однородного груза таким образом, чтобы стоимость перевозок была минимальной.

Математическая формулировка замкнутой транспортной модели: требуется найти

,

при условиях

; (ограничения по потреблению) (8.25)
; (ограничения по производству) (8.26)
(условие замкнутости ). (8.27)

.



Если условие (8.27) имеет форму неравенства (производство продукта не меньше его потребления), то транспортная модель называется незамкнутой или открытой.

Незамкнутая транспортная модель (например, часть продукции остается на складе) легко приводится к замкнутой введением дополнительного, фиктивного узла (n+1) потребления с потребностью и транспортными расходами .

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.