Математические методы в коммерческой деятельности. Буравлева О.Ю. - 11 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

Следствие 3 (признак единственности оптимального решения). Оптимальное решение задачи ли-
нейного программирования является единственным, если для любого вектора условий, не входящего в
базис, оценка отлична от нуля, т.е.
0
≠
∆
k
.,...,2,1 nvmk
+
+
=
∀
(2.11)
Здесь предполагается, что в базис оптимального решения входят первые m векторов.
Следствие 4 (признак существования бесконечного множества оптимальных решений). Задача ли-
нейного программирования имеет бесконечное множество оптимальных решений, если оценка хотя бы
одного вектора условий, не входящего в базис, равна нулю, т.е.
{
}
nmmk ,...,2,1
+
+
∈
∃
: 0=
∆
k
. (2.12)
Следствие 5 (признак отсутствия оптимального решения вследствие неограниченности целевой
функции). Задача линейного программирования не имеет решения ввиду неограниченности целевой
функции, если для какого-либо из векторов условий
k
A с оценкой
k
∆
, противоречащей признаку опти-
мальности, среди коэффициентов разложения по базису опорного решения нет положительного, в зада-
че на:
– максимум
kk
A
∆
∃
: <0 и 0
≤
ik
x i∀ ; (2.13)
– минимум
kk
A
∆
∃
: >0 и 0
≤
ik
x i∀ . (2.14)
2.4 Алгоритм симплексного метода
Для того чтобы решить задачу симплексным методом (методом последовательного улучшения пла-
на), необходимо выполнить следующее.
1 Привести задачу линейного программирования к каноническому виду.
2 Найти начальное опорное решение с единичным базисом и коэффициенты разложения векторов
условий по базису опорного решения.
Если опорное решение отсутствует, то задача не имеет решения в силу несовместности системы ог-
раничений.
3 Вычислить оценки разложений векторов условий по базису опорного решения и заполнить сим-
плексную таблицу.
4 Если выполняется признак единственности оптимального решения то решение задачи заканчива-
ется.
5 Если выполняется условие существования множества оптимальных решений (следствие 4 из тео-
ремы 2.3.1), то путем простого перебора находят все оптимальные решения.
6 Если выполняются условия следствия 5 теоремы об улучшении опорного решения, то задача не
имеет решения ввиду неограниченности целевой функции.
7 Если пункты 4 – 6 алгоритма не выполняются, находят новое опорное решение с использованием
условий следствия 1 и возвращаются к пункту 3.
Пример. Решить симплексным методом задачу
.5,1,0
,3042
,242
,622
max,23459)(
5321
4321
321
54321
∈∀≥
=+−+
=+++
≤+−
→++++=
jjx
xxxx
xxxx
xxx
xxxxxXZ
j
6
x
+
.

Страницы