ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Публикационная активность

(сведения по итогам 2016 г.)
2-летний импакт-фактор РИНЦ: 0,493
2-летний импакт-фактор РИНЦ без самоцитирования: 0,389
Двухлетний импакт-фактор РИНЦ с учетом цитирования из всех
источников: 0,732
5-летний импакт-фактор РИНЦ: 0,364
5-летний импакт-фактор РИНЦ без самоцитирования: 0,303
Суммарное число цитирований журнала в РИНЦ: 5022
Пятилетний индекс Херфиндаля по цитирующим журналам: 355
Индекс Херфиндаля по организациям авторов: 499
Десятилетний индекс Хирша: 11
Место в общем рейтинге SCIENCE INDEX за 2016 год: 304
Место в рейтинге SCIENCE INDEX за 2016 год по тематике "Автоматика. Вычислительная техника": 11

Больше данных по публикационной активности нашего журнале за 2008-2016 гг. на сайте РИНЦ

Вход


Забыли пароль? / Регистрация

Добавить в закладки

Следующий номер на сайте

4
Ожидается:
16 Декабря 2017

Об ограничении переменных состояния в основной и дуальной задачах линейного программирования

Статья опубликована в выпуске журнала № 4 за 2007 год.[ 21.12.2007 ]
Аннотация:
Abstract:
Авторы: Лебедев С.И. () - , ,
Количество просмотров: 7288
Версия для печати
Выпуск в формате PDF (2.00Мб)

Размер шрифта:       Шрифт:

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

Оценку верхней и нижней границ составляющей n вектора переменных состояния дуальной задачи предлагается производить по значениям функции цели основного варианта расчета, полученным по верхней и нижней границам вектора переменных основной задачи, с учетом y.

В векторно-матричной форме основную задачу при наличии упомянутых выше ограничений можно представить в виде вектора переменных состояния:.

Функция цели: .

Ограничения:  .

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

Функция цели:

.

Ограничения:  .

Приведенные выше уравнения представлены в форме, пригодной для выполнения расчетов ЛП с помощью функции linprog пакета Optimization Toolbox среды MatLAB.

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

Основная задача: c1=[3 1]; A1=[3 2; -4 1]; b1=[24 -8]′; A1eq=[1 -2]; b1eq=0.

Нижняя и верхняя границы переменных состояния основной задачи: lb1=[0 1]′; ub1=[inf 3]′.

В режиме прямых вычислений получим решение задачи ЛП: [x1,z1]=linprog(c1,A1,b1,A1eq, b1eq,lb1,ub1).

В результате минимум z1=8 при значении вектора x1=[2.2857 1.1429]′.

Дуальная задача: с2=[24 -8 0]; A2=[-3 4 -1]; b2=[3]; A2eq=[2 1 -2]; b2eq=[-1].

Верхнюю и нижнюю границы u(2) вектора переменных состояния дуальной задачи  определим путем подстановки в условие-равенство двух ограничений равенств: A2eq=[2 1 -2; c2], b2eq=[-1 c1*lb] и A2eq=[2 1 -2; c2], b2eq=[-1 c1*x1], где х1=[2.2851 1.1429]′ – оптимальное решение основной задачи.

В результате находим решение для случая, когда нижняя и верхняя границы вектора u при вариации u(2) равны:

lb2=[0  0.2024  0]′, ub2=[inf  1 inf]′.

Используем их при записи функции linprog для решения дуальной задачи: [u,z2]=linprog(c2, A2,b2,A2eq,b2eq,lb2,ub2).

Окончательно имеем: u=[0 1 1]′, Z2=-z2=8.000.

Заметим, что Z2=-z2 принято согласно правилам перехода от основного к дуальному варианту решения.

Таким образом, элементу вектора  в дуальной задаче соответствует u(2) с ограничениями .


Постоянный адрес статьи:
http://swsys.ru/index.php?page=article&id=303
Версия для печати
Выпуск в формате PDF (2.00Мб)
Статья опубликована в выпуске журнала № 4 за 2007 год.

Назад, к списку статей

Хотите оценить статью или опубликовать комментарий к ней - зарегистрируйтесь