Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Прямая задача:
Прямая задача с ограничениями в канонической форме
S1 ≥ 0
Двойственная задача
y 1,2 не ограничены в знаке.
Ограничение , т.е. является более жестким, чем условие неограниченности у 1 в знаке, поэтому двойственная задача может быть записана в следующем виде:
у 2 не ограничена в знаке.
Пример 4.3. Прямая задача
min(5X1 – 2X2);
–X1 + X2 ≥ –3;
2X1 + 3X2 ≤ 5;
X1,2 ≥ 0.
Прямая задача с ограничениями в канонической форме:
min(5X1 – 2X2 + 0S1 + 0S2);
–X1 + X2 – S1 = –3;
2X1 + 3X2 + S2 = 5;
Двойственная задача:
max(–3У1 + 5У2);
–У1 + 2У2 ≤ 5;
У1 + 3У2 ≤ –2;
–У1 + 0У2 ≤ 0;
0У1 + У2 ≤ 0;
У1,2 не ограничены в знаке.
Отбрасывая избыточные ограничения, получаем:
max(–3У1 + 5У2);
–У1 + 2У2 ≤ 5;
У1 + 3У2 ≤ –2;
У1 ≥ 0, У2 ≤ 0.
Пример 4.4. Прямая задача:
max(5X1 + 6X2);
X1 + 2X2 = 5;
–X1 + 5X2 ≥ 3;
4X1 + 7X2 ≤ 8.
X1 не ограничена в знаке, X2 ≥ 0.
Прямая задача с ограничениями в канонической форме:
max(5 – 5 + 6X2 + 0S1 + 0S2);
+ 2X2 = 5;
+ 5X2 – S1 = 3;
4 + 7X2 + S2 = 8;
Двойственная задача:
min(5У1 + 3У2 + 8У3);
У1 – У2 + 4У3 ≥ 5;
–У1 + У2 – 4У3 ≥ –5;
2У1 + 5У2 + 7У3 ≥ 6;
0У1 – У2 + 0У3 ≥ 0;
0У1 + 0У2 + У3 ≥ 0.
У1,2,3 не ограничены в знаке.
Заметим, что первое и второе ограничения двойственной задачи можно заменить одним ограничением в виде равенства, избыточные ограничения на У2 и У3 можно отбросить. В итоге получаем:
min(5У1 + 3У2 + 8У3);
У1 – У2 + 4У3 = 5;
2У1 + 5У2 + 7У3 ≥ 6;
У1 не ограничена в знаке;
У2 ≤ 0, У3 ≥ 0.
Очевидно, что задача, двойственная к двойственной, совпадает с прямой.
Дата публикования: 2015-10-09; Прочитано: 240 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!