Составители:
Рубрика:
от одной вершины к другой. Однако этот перебор не хаотичный, а
таков, что на каждом шаге решение улучшается [4].
Метод состоит из двух этапов: на первом этапе ищется
допустимое решение; на втором этапе это допустимое решение
улучшается до оптимального.
Алгоритм метода рассмотрим на примере линейной модели п.2.1,
где требуется найти минимум
целевой функции
Z = z
1
x
1
+z
2
x
2
→ min, (2.9)
при ограничениях-равенствах
a
11
x
1
+a
12
x
2
+ х
3
= b
1
,
a
21
x
1
+a
22
x
2
+ х
4
= b
2
, (2.10)
a
31
x
1
+a
32
x
2
+ х
5
= b
3
и граничных условиях неотрицательности переменных
х
i
> 0, i = 1, 2,...5. (2.11)
Перейдем к табличной форме записи. В отличие от табл. 2.1 в
исходную таблицу введем строку целевой функции (нижняя строка
табл. 2.3).
Т а б л и ц а 2.3
х
1
х
2
х
3
х
4
х
5
b
a
11
a
12
1 0 0
b
1
a
21
a
22
0 1 0
b
2
а
31
а
32
0 0 1
b
3
z
1
z
2
0 0 0
-Z
Исходное решение:
х
1
=0, х
2
=0, х
3
=b
1
, х
4
=b
2
, х
5
=b
3
. (2.12)
В соответствии с выражением (2.9) исходное значение целевой
функции Z=0.
1 этап. Получение допустимого решения. Любое допустимое
решение должно удовлетворять системе ограничений-равенств и
граничным условиям.
Исходное решение (2.12) удовлетворяет системе ограничений-
равенств (2.10). Это решение будет удовлетворять граничным
22
Страницы
- « первая
- ‹ предыдущая
- …
- 20
- 21
- 22
- 23
- 24
- …
- следующая ›
- последняя »
