Оптимальное управление в экономике. Матвейкин В.Г - 14 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

7. Если на переменную
(
)
1
1,n=jx
j
прямой задачи наложено ограничение на знак, то j-е ограничение
двойственной задачи записывается в виде неравенства, и наоборот.
8. Если переменная
(
)
n+n=jx
j
1,
1
исходной задачи произвольная, то j-е ограничение двойственной задачи
имеет знак равенства.
9. Если в прямой задаче имеются ограничения-равенства, то на соответствующие переменные двойствен-
ной задачи не налагаются условия неотрицательности.
2.6. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД
Симплекс-метод применяется для решения задач с неотрицательными свободными членами b
i
и произ-
вольными по знаку приведёнными коэффициентами целевой функции
i
c
′
. Иногда бывает легче найти базис,
удовлетворяющий признаку оптимальности все
0),( ≥
′
j
с
но не удовлетворяющий критерию допустимости (не
все
0).( ≥
j
b
Вариант симплекс-метода, применяемый для решения таких задач, называется двойственным сим-
плекс-методом. С его помощью решаются задачи линейного программирования вида
max
1
→
′
−=
∑
=
n
j
jj
xcz ,
mibxa
i
n
j
jij
,1,
1
==
∑
=
,
njx
j
,1,0 =≥ ,
где система ограничений имеет предпочтительный вид и все приведённые коэффициенты целевой функции
.1,0, n=jс
j
≥
′
При этом условие m=ib
i
1,0,≥ не требуется. Определённую таким образом задачу будем на-
зывать задачей в двойственной базисной форме. Она имеет базисное, но не опорное решение.
Двойственный симплекс-метод, применяемый к задаче в двойственной базисной форме, приводит к после-
довательности задач с возрастающим значением целевой функции, неотрицательными коэффициентами
n=jс
j
1,,
′
и значениями m=ib
i
1,, любого знака.
Двойственный симплекс-метод называют методом последовательного улучшения оценок. Преобразования
задачи выполняются до тех пор, пока не будет установлено, что исходная задача не имеет допустимого реше-
ния или будет получена задача с допустимым базисным планом (все 0≥
i
b ), который одновременно будет и
оптимальным.
Для решения задачи двойственным симплекс-методом необходимо использовать следующий порядок:
1. Составить исходную таблицу Гаусса, записывая приведенные коэффициенты целевой функции в z-
строку с противоположными знаками, а константу z
0
со своим знаком.
2. Выяснить, имеется ли хотя бы одно отрицательное число в столбце значений свободных членов. Если
все ,1,0, m=ib
i
≥ то полученное базисное решение и значение целевой функции, записанное в столбце свобод-
ных членов, дают оптимальное решение исходной задачи (так как по предположению все ).1,0, n=jc
j
≥
′
3. Среди отрицательных коэффициентов ,1,, m=ib
i
выбрать минимальный. Пусть это b
1
. Следовательно,
строка с номером 1 – ведущая и переменную x
1
исключают из базиса.
4. В ведущей строке проверить знаки всех коэффициентов .1,,
1
n=ja
j
Если все ,1,0,
1
n=ja
j
≥ то ис-
ходная задача неразрешима в силу несовместности системы ограничений.
5. Среди отрицательных коэффициентов n=ja
j
1,,
1
ведущей строки выбрать минимальное двойственное
отношение (отношение элементов z-строки, взятых со знаком минус, к соответствующим отрицательным эле-
ментам ведущей строки):
k
k
j
j
a
a
c
a
c
j
11
0
1
min =
′
<
.
Следовательно, столбец с номером k – ведущий, а элемент a
1k
– разрешающий. Переменную x
k
включить в
базис.
6. Пересчитать таблицу методом Жордана-Гаусса с ведущим элементом a
1k
и перейти к пункту 2.

Страницы