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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

Р е ш е н и е. Приводим задачу к каноническому виду. Для этого в левую часть первого ограниче-
ния-неравенства типа «меньше или равно» вводим дополнительную переменную
6
x с коэффициентом
+1. В целевую функцию переменная
6
x входит с коэффициентом 0 (т.е. не входит). Получаем:
.6,1,0
,3042
,242
,622
max,023459)(
5321
4321
6321
654321
∈∀≥
=+−+
=+++
=++−
→+++++=
jjx
xxxx
xxxx
xxxx
xxxxxxXZ
j
Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные при-
равниваем к нулю 0
321
=
== xxx . Получаем опорное решение )6,30,24,0,0,0(
1
=
X с единичным базисом
).,,(
6541
АААБ =
Вычисляем оценки разложений векторов условий по базису опорного решения, используя формулу
(2.6).
.000000)0,0,1()2,3,0(
;032002)1,0,0()2,3,0(
;030303)0,1.0()2,3,0(
;948304)4,1,2()2,3,0(
;352605)1,2,2()2,3,0(
;294309)2,1,1()2,3,0(
66б6
55б5
44б4
33б3
22б2
11б1
=−++=−⋅=−=∆
=−++=−⋅=−=∆
=−++=−⋅=−=∆
−=−−+=−−⋅=−=∆
=−++=−−⋅=−=∆
−=−++=−⋅=−=∆
cXC
cXC
cXC
cXC
cXC
cXС
Оценки векторов, входящих в базис, всегда равны нулю. Обычно эти вычисления проводятся устно.
Опорное решение, коэффициенты разложений и оценки разложений векторов условий по базису опор-
ного решения записываются в симплексную таблицу (табл. 2.1). Сверху над таблицей для удобства вы-
числений оценок записываются коэффициенты целевой функции. В первом столбце «Б» записываются
векторы, входящие в базис опорного решения. Порядок записи этих векторов в симплексной таблице
соответствует номерам разрешенных неизвестных в уравнениях-ограни-чениях. Во втором столбце таб-
лицы «С
б
» записываются коэффициенты целевой функции при базисных переменных в том же порядке.
При правильном расположении коэффициентов целевой функции в столбце «С
б
» оценки единичных
векторов, входящих в базис, всегда равны нулю.
В последней строке таблицы с оценками
k
∆
в столбце «А
0
» записывается значение целевой функции
на опорном решении )(
1
XZ .
Таблица 2.1
9 5
4↓
3 2 0
Б
C
б
А
0
А
1
А
2
А
3
А
4
А
5
А
6
Q
1
Q
3
А
6
А
4
А
5
0
3
2
6
24
30
1
1
2
–2
2
1
2
1
–4
0
1
0
0
0
1
1
0
0
6
24
15
3
24
–
∆
k
13
2
–2 3 –9 0 0 0
Начальное опорное решение не является оптимальным, так как оценки 2
1
−=∆ , 9
3
−=∆ для векторов
1
A и
3
A противоречат признаку оптимальности. Для оптимальности опорного решения в задаче на мак-
симум требуется неотрицательность оценок для всех векторов условий.
По теореме об улучшении опорного решения (см. теорему 2.3.1), если в задаче на максимум хотя
бы один вектор имеет отрицательную оценку, то можно найти новое опорное решение, на котором зна-
чение целевой функции будет больше.
Определим, введение какого из двух векторов приведет к большему приращению целевой функции.
Приращения целевой функции найдем по формуле
kkk
QZ
∆
−
=
∆
0
. Вычислим значения параметра
k
Q
0
для
первого и третьего столбцов по формуле (2.1.5), получим
6
01
=
Q при l = 1 (где l – номер строки) и 3
03
=
Q
при l = 1. Находим приращение целевой функции при введении в базис первого вектора 12)2(6
1
=
−
⋅
−
=
∆Z
и третьего вектора 27)9(3
3
=
−
⋅−=∆Z . Следовательно, для наиболее быстрого нахождения оптимального
←

Страницы