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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

равны нулю, то исходная задача имеет оптимальное решение )...,,,(
21
* ∗∗∗
=
n
xxxX , которое получается из
*
X
отбрасыванием этих нулевых искусственных переменных.
Теорема 3.3 (признак отсутствия решения ввиду несовместности системы ограничений). Если рас-
ширенная задача имеет оптимальное решение, у которого хотя бы одна искусственная переменная от-
лична от нуля, то исходная задача не имеет решения ввиду несовместности системы ограничений.
Теорема 3.4 (признак отсутствия решения ввиду неограниченности целевой функции). Если рас-
ширенная задача не имеет решения ввиду неограниченности целевой функции, то исходная задача так-
же не имеет решения по той же причине.
3.1 Особенности алгоритма метода искусственного базиса
Алгоритм метода искусственного базиса имеет следующие особенности.
1 Ввиду того, что начальное опорное решение расширенной задачи содержит искусственные пере-
менные, входящие в целевую функцию с коэффициентом –M (в задаче на максимум) или +M (в задаче
на минимум), оценки разложений векторов условий
kkk
cXC
−
=
∆
б
состоят из двух слагаемых
k
∆
′
и
)(M
k
∆
′′
, одно из которых
k
∆
′
не зависит от M , а другое )(M
k
∆
′′
зависит от M. Так как M сколь угодно ве-
лико по сравнению с единицей M( >> 1), то на первом этапе расчета для нахождения векторов, вводи-
мых в базис, используется только слагаемые оценок
)(M
k
∆
′
′
.
2 Векторы, соответствующие искусственным переменным, которые выводятся из базиса опорного
решения, исключаются из рассмотрения.
3 После того как все векторы, соответствующие искусственным переменным, исключаются из ба-
зиса, расчет продолжается обычным симплексным методом с использованием оценок
k
∆
′
, не зависящих
от M.
4 Переход от решения расширенной задачи к решению исходной задачи осуществляется с исполь-
зованием доказанных выше теорем 3.2. – 3.4.
max,823)(
4321
→
−
+
+
=
xxxxXZ
и
.4,3,2,1
,0
,222
,107423
4321
4321
=
≥
=−++
=−++
j
x
xxxx
xxxx
j
Р е ш е н и е. Составляем расширенную задачу. В левые части уравнений системы ограничений
вводим неотрицательные искусственные переменные с коэффициентом +1 (всегда). Удобно справа от
уравнений записать вводимые искусственные переменные. В первое уравнение вводим переменную
5
x ,
во второе – переменную
6
x . Данная задача – задача на нахождение максимума, поэтому
5
x и
6
x в целе-
вую функцию вводятся с коэффициентом –M. Получаем
max,823)(
654321
→−−−++= MxMxxxxxXZ
=+−++
=+−++
,222
,107433
64321
54321
xxxxx
xxxxx
.6,5,4,3,2,1,0 =≥ jx
j
Задача имеет начальное опорное решение )2,10,0,0,0,0(
1
=X с базисом ),(
651
AAБ = . Вычисляем оценки
векторов условий по базису опорного решения и значение целевой функции на опорном решении:
,353
2
3
1
−−=−
−
−
=∆ M
M
M
,242
1
3
2
−−=−
−
−
=∆ М
М
М
,151
1
4
3
−−=−
−
−
=∆ М
М
М
,89)8(
2
7
4
+=−−
−
−
−
−
=∆ М
М
М
,0
65
=∆=∆
()
.12
2
10
1
M
M
M
XZ −=
−
−
=
6
5
x
x
+
+

Страницы