Получение оптимальных проектных решений и их анализ с использованием математических моделей. Литовка Ю.В. - 59 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

f
0
(X) = c
1
x
1
+ c
2
x
2
+ ... + c
n
x
n
→ min (2.17)
при условиях
строк;
......................
......................
...
1
11212111
1
n
b
bxaxaxa
n
nn
≤
≤+++
строк;
..............
..............
..............
1
1
1
e
nn
n
n
b
b
e
=
=
+
+
строк;
...................
...................
...................
1
1
1
g
nnn
nn
n
b
b
ge
e
≥
≥
++
++
x
1
, x
2
, ..., x
n
≥ 0, b
1
, b
2
, ..., b
m
> 0.
В соответствии с рассмотренными правилами преобразования ограничений, в последние n
g
ограничений вво-
дятся дополнительные переменные x
n+1
, ...,
g
nn
x
+
с коэффициентом –1. В первые n
1
ограничений вводятся дополни-
тельные переменные
1
...,,
1 nnnnn
gg
xx
++++
с коэффициентом +1. В следующие n
e
ограничений вводятся вспомога-
тельные переменные
egg
nnnnnnn
xx
+++++
11
,, … с коэффициентом +1 и в последние n
g
ограничений – вспомогатель-
ные переменные
ggg
nnnnnnnnn
xx
++++++++
e1e1
,,
1
…
c коэффициентом +1. Последние n
1
+ n
e
+ n
g
столбцов расширен-
ной матрицы коэффициентов образуют единичную матрицу требуемого вида, и начальное допустимое базисное
решение вспомогательной задачи будет иметь вид
.,,1;0;,,1;
gjiinn
nnjxmibx
g
+
=
=
=
=
++
……
Искусственная целевая функция W является суммой вспомогательных переменных. Выразив ее через неба-
зисные переменные, получим
,
0
1
WWxd
g
nn
j
jj
+=
∑
+
=
где
∑∑
+=+=
−=−=
m
ni
i
m
ni
ijj
bWad
1
0
1
11
; .
Пример. Исходная задача ЛП представлена в виде
–х
1
– 2х
2
– 3х
3
= f
0
;
–х
1
+ х
3
≤ 2
n
1
= 1;
х
1
+ х
2
+ х
3
= 4 n
е
= 1;
2х
1
+ 3х
2
+ х
3
≥ 6
n
g
= 2;
х
1
+ 5х
2
+ 6х
3
≥ 9.
Тогда вспомогательная задача будет иметь вид:
–х
1
+ x
3
+ x
6
= 2;
х
1
+ х
2
+ х
3
+ x
7
= 4;
2х
1
+ 3х
2
+ х
3
– x
4
+ x
8
= 6;
х
1
+ 5х
2
+ 6х
3
– x
5
+ x
9
= 9;
–х
1
– 2х
2
– 3х
3
= f
0
;
–4х
1
– 9х
2
– 8х
3
+ x
4
+ x
5
= W – 19.
(2.18)
Начальное допустимое базисное решение для этой задачи очевидно: x
1
, ..., x
5
= 0; x
6
= 2; x
7
= 4; x
8
= 6; x
9
= 9. В
таком виде задача называется канонической формой для базисных переменных x
6
, x
7
, x
8
, x
9
.
Таким образом, при n
e
+ n
g
= 0 построение начального допустимого базисного решения задачи ЛП очевид-
но, в противном случае для этих целей строится и решается вспомогательная задача ЛП.
Рассмотрим теперь итерационный процесс решения задачи ЛП симплекс-методом при известном началь-
ном допустимом базисном решении и построенной для этого решения канонической формой. Решение задачи
удобно иллюстрировать в симплекс-таблицах. Для задачи (2.18) исходная таблица для первой итерации будет
выглядеть следующим образом:
Итерация 1
Базис Значение x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x
9
x
6
2 –1 0 1 0 0 1 0 0 0

Страницы