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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

решения необходимо ввести в базис опорного решения вектор
3
A вместо первого вектора базиса
6
A , так
как минимум параметра
03
Q достигается в первой строке (l = 1).
Далее выполним преобразование Жордана с элементом 2
13
=
x , получим второе опорное решение
=
2
X (0, 0, 3, 21, 42, 0) с базисом ),,(
5432
АААБ = (табл. 2.2). Это решение не является оптимальным, так
как вектор
2
A имеет отрицательную оценку .6
2
−
=
∆
Для улучшения опорного решения необходимо ввести
в его базис вектор
2
A .
Таблица 2.2
Б
C
б
А
0
А
1
А
2
А
3
А
4
А
5
А
6
Q
2
А
3
А
4
А
5
4
3
2
3
21
42
1/2
1/2
4
–1
3
–3
1
0
0
0
1
0
0
0
1
1/2
–
1/2
2
–
7
–
∆
k
159 5/2 –6 0 0 0 9
Определим номер вектора, выводимого из базиса. Для этого вычислим параметр
02
Q для второго
столбца, он равен 7 при l = 2. Следовательно, из базиса выводим второй вектор базиса
4
A . Выполним
преобразование Жордана с элементом
3
22
=
x , получим третье опорное решение =
3
X (0, 7, 10, 0, 63, 0) с
базисом ),,(
5432
АААБ = (табл. 2.3). Это единственное оптимальное решение, так как для всех векторов, не
входящих в базис, оценки разложений по базису опорного решения положительны:
,27
1
=
∆ ,2
4
=
∆
.27
6
=
∆
Таблица 2.3
Б
C
б
А
0
А
1
А
2
А
3
А
4
А
5
А
6
А
3
А
4
А
5
4
5
2
10
7
63
2/3
1/6
9/2
0
1
0
1
0
0
1/3
1/3
1
0
0
1
1/3
–1/6
3/2
∆
k
201 7/2 0 0 2 0 7/2
О т в е т: max Z(X) = 201 при
*
X
= (0, 7, 10, 0, 63).
3 МЕТОД ИСКУССТВЕННОГО БАЗИСА
Метод искусственного базиса применяется для решения задач линейного программирования в слу-
чае, когда задача не имеет начального опорного решения с базисом из единичных векторов.
Согласно данному методу для задачи линейного программирования составляется так называемая
расширенная задача, которая решается симплексным методом. На основе результатов решения расши-
ренной задачи либо находится оптимальное решение исходной задачи, либо устанавливается причина
его отсутствия.
Пусть имеется каноническая задача линейного программирования:
.0
,...
.............................................
,...
,...
max(min),...)(
2211
22222121
11212111
2211
jx
bxaxaxa
bxaxaxa
bxaxaxa
xcxcxcXZ
j
mnmnmm
nn
nn
nn
∀≥
=+++
=+++
=+++
→
+
+
+
=
(3.1)
Без ограничения общности можно считать, что правые части уравнений системы ограничений неот-
рицательны, т.е.
0≥
i
b
.i∀
В дальнейшем для краткости записи при доказательствах используется компактная запись этой за-
дачи:
↓
←

Страницы