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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

Составим исходную симплекс-таблицу, записывая приведенные коэффициенты целевой функции в z-
строку с противоположными знаками, а константу
0
z своим знаком.
Симплекс-таблица
Б З х
1
х
2
… х
m
х
m+1
… х
m+k
… х
n
х
1
b
1
1 0 … 0
1,1 +m
a
…
лm
a
+,1
…
n
a
1
х
2
b
2
0 1 … 0
1,2 +m
a
…
лm
a
+,2
…
n
a
2
… … … … … … … … … … …
х
l
b
l
0 0 … 0
lml
a
+,
…
лml
a
+,
…
ln
a
… … … … … … … … … … …
х
m
b
m
0 0 … 1
1, +mm
a
…
лmm
a
+,
…
mn
a
z z
0
0 0 … 0
m
c
′
…
km
c
+
′
…
n
c
′
1. Если в z-строке симплекс-таблицы, содержащей некоторый опорный план, нет отрицательных элемен-
тов (не считая свободного члена
0
z , то данный план оптимален и задача решена. К тому же, если в z-строке
симплексной таблицы, содержащей оптимальный план, нет нулевых элементов (не считая
0
z , и элементов, со-
ответствующих базису), то оптимальный план единственный. Если же в z-строке последней симплексной таб-
лицы, содержащей оптимальный план, есть хотя бы один нулевой элемент, соответствующий свободной пере-
менной, то задача ЛП имеет бесконечное множество решений.
2. Если в z-строке есть хотя бы один отрицательный элемент (не считая
0
z ), а в любом столбце с таким
элементом есть хотя бы один положительный, то можно перейти к новому опорному плану, более близкому к
оптимальному. Для этого столбец с отрицательным элементом
km
c
+
′
в z-строке берут за разрешающий (если в z-
строке отрицательных элементов несколько, то за разрешающий выбирают столбец с наименьшим элементом).
Следовательно, столбец с номером k+m станет ведущим или разрешающим и переменная
k+m
x будет включе-
на в базис.
3. Среди элементов ведущего столбца находят положительные. Если таковых нет, то задача не имеет ре-
шений в силу неограниченности целевой функции ).(
∞
→z
4. Для положительных элементов
k+m
a
1,
подсчитывают симплексные отношения (отношения свободных
членов к соответствующим положительным элементам ведущего столбца)
()
m=iab
k+mi
1,,/
1,
и выбирают сре-
ди них наименьшее. Пусть минимальное симплексное отношение будет в строке 1. Строка с номером 1 станет
ведущей (разрешающей), а элемент
k+m
a
1,
– ведущим. Переменная
1
x выйдет из базиса.
5. Выполняют одну итерацию по замещению базисной переменной методом Жордана-Гаусса. Строят но-
вую симплексную таблицу и переходят к первому пункту.
Замечание. Опорное решение называется невырожденным, если все его компоненты положительные, в
противном случае оно называется вырожденным. Задача ЛП называется невырожденной, если все ее опорные
планы невырожденные. Если среди опорных решений есть хотя бы одно вырожденное, то задача называется
вырожденной. В этом случае возможен вариант, когда значение целевой функции при переходе от одного
опорного плана к другому не улучшится и может произойти так называемое зацикливание. Для избежания это-
го фактора изменяют последовательность вычислений путем изменения разрешающего столбца.
2.3. МЕТОД ИСКУССТВЕННОГО БАЗИСА
Если начальный опорный план задачи находится методом искусственного базиса, то сначала надо решить
симплекс-методом вспомогательную w-задачу. При этом необходимо в начальную симплексную таблицу вклю-
чить и z-строку, соответствующую целевой функции исходной задачи. Для составления симплекс-таблицы из
функции z исключают базисные переменные, а из функции – искусственные базисные переменные. В ходе ре-
шения возможны случаи:
1) в оптимальном решении w-задачи хотя бы одна из искусственных переменных отлична от нуля (т.е. не
вышла из базиса). Тогда исходная z-задача не имеет допустимых планов (т.е. ее система ограничений несовме-
стна);
2) в оптимальном плане новой w-задачи все искусственные переменные равны нулю (т.е. вышли из бази-
са), а значит, и искусственная целевая функция равна нулю. Тогда значения оставшихся координат плана дадут
начальный опорный план исходной задачи, которую можно решить симплекс-методом.

Страницы