Составители:
201
плана", так как суть его заключается в последовательном переборе вершин области
ограничений (области допустимых решений) таким образом, что значение целевой функции
убывает от вершины к вершине до минимума. В n – мерном пространстве область
ограничений является многогранником; а простейший многогранник – симплекс, имеющий
в качестве граней простейшие многоугольники – треугольники, отсюда и название метода.
Введем
необходимые для изложения симплекс-метода определения.
Неизвестные x
j
, через которые выражаются все остальные неизвестные x
i
системы
ограничений (6.2), называются
свободными переменными.
Решение системы (6.2), соответствующее нулевым значениям свободных
переменных, называется
базисным решением, а переменные x
i
– базисными переменными.
Всякое неотрицательное решение системы (6.2) x
i
≥ 0 называется допустимым
решением
.
Допустимое базисное решение называется
опорным решением.
Опорное решение, минимизирующее значение целевой функции, называется
оптимальным решением (планом) задачи линейного программирования.
Подготовительный этап.
Представление задачи в форме ОЗЛП
.
Минимизировать
min)(
1
0
→+=
∑
=
n
j
jj
cxcXZ
при ограничениях
.1,1,0
,0
1
njmix
bxay
j
n
j
ijiji
−=−=≥
=+=
∑
=
Исходная симплекс-таблица имеет вид:
x
1
… x
j
… x
n
1
y
1
a
11
…
a
1j
…
a
1n
b
1
…
…
… …
… …
…
Страницы
- « первая
- ‹ предыдущая
- …
- 199
- 200
- 201
- 202
- 203
- …
- следующая ›
- последняя »