пользователей: 30398
предметов: 12406
вопросов: 234839
Конспект-online
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

2 курс 2 семестр:
» Статистика
» Эконометрика
» Социология
» ВЭД
» Экономика
2 курс 1 семестр (экономика орг):
» Экон.орг.
» псих
» менеджмент
» методы
2 семестр (математика):
» математика
2 семестр (макро):
» Экономика
I семестр:
» История

9. Вторая теорема двойственности.

Теорема 2 (вторая теорема двойственности).

Планы х* и у* оптимальны в задачах I и II тогда и только тогда, когда при подстановке их в систему ограничений задач I и II соответственно хотя бы одно из любой пары сопряженных неравенств обращается в равенство.

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

Итак, имеем исходную задачу I, которую мы решили в п. 3.8, и ее оптимальное решение х* = (0, 40, 0, 100) и F(х*) = 700.

Найдем решение двойственной задачи II у* = (у1, у2, у3) из п. 3.9.1, не прибегая к симплекс-методу, а воспользовавшись второй теоремой двойственности и известным оптимальным планом х*.

Рассмотрим выполнение неравенств задачи I при подстановке х* в систему ограничений.

s4_image055.jpg

Поскольку 1, 5, 7 неравенства строгие (имеют знак "<" или ">"), то соответствующие им неравенства в задаче II из пары сопряженных обязаны обратиться в равенства. имеем:

s4_image056.gif или s4_image057.gif

т. е. у* = (0, 1, 4) - оптимальное решение.

Заметим, что действительно G(y*) = 400y1 + 300y2 + 100y3 = 400 · 0 + 300 · 1 + 100 · 4 = 700 = F(x*).

Итак, в силу второй теоремы двойственности мы очень быстро нашли оптимальное решение задачи II, пользуясь условием обращения в равенство хотя бы одного из пары сопряженных неравенств в системах ограничений двойственных задач.

Между переменными исходной задачи и переменными двойственной существует глубокая связь. А именно: после приведения обеих задач I и II к каноническому виду основные и дополнительные переменные задач соответствуют друг другу следующим образом:

s4_image058.jpg

Установив такую связь, внимательный читатель заметит, что, решив задачу I симплекс-методом и получив последнюю симплекс-таблицу (табл. 3.15), мы фактически решим и задачу II.

Запишем таблицу 3.15, учитывая соответствие между переменными хi и yj (табл. 3.16).

Таблица 3.16

    у4 у2 у6 у3  
  базисные -х1 -х6 -х3 -х7 свободные
у1 х5         334
у5 х2         40
у7 х4         100
  -F 1 1 1 4 700

В силу соответствия и II теоремы двойственности переменные у1, у5, у7 обязаны равняться 0, т. к. х5, х2, х4>0 строго. А переменные у4, у2, у6, у3 принимают значения из индексной строки 1, 1, 1, 4 соответственно, т. к. им соответствующие переменные х1, х6, х3, х7 = 0, как свободные. Итак, из последней таблицы задачи II, не проводя даже никаких вычислений и пользуясь лишь соответствием переменных:

у* = (у1*, у2*, у3*, у4*, у5*, у6*, у7*) = (0, 1, 4, 1, 0, 1, 0).


25.01.2015; 13:46
хиты: 132
рейтинг:0
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2024. All Rights Reserved. помощь