ВУЗ:
Составители:
Рубрика:
Контрольные вопросы
1. Какие методы используются для численного решения задач оптимизации с ограничениями типа ра-
венств и типа неравенств?
2.
В чем преимущества численных методов перед классическими методами решения оптимизационных
задач с ограничениями?
3. Почему в качестве функции штрафа, учитывающей ограничения-неравенства целесообразно использо-
вать логарифмическую, а учитывающую ограничения-равенства – квадратичную?
Литература: [14].
Лабораторная работа 2.6
РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМПЛЕКС-МЕТОДОМ
Цель: приобретение навыков по использованию симплекс-метода для решения задачи линейного про-
граммирования.
Задание: провести численное решение задачи линейного программирования.
Общие положения
Симплекс-метод, известный как метод последовательного улучшения плана, является основным числен-
ным методом решения задач линейного программирования (ЛП). Он широко используется и в численных мето-
дах нелинейной и дискретной оптимизации как вспомогательный аппарат для решения возникающих подзадач.
Симплекс-метод применяется к задаче ЛП в канонической форме
f
0
(X) = c
1
x
1
+ c
2
x
2
+ ... + c
n
x
n
→ min (2.16)
при условиях
a
11
x
1
+ a
12
x
2
+...+ a
1n
x
n
= b
1
;
a
21
x
1
+ a
22
x
2
+...+ a
2n
x
n
= b
2
;
.....................................
a
m1
x
1
+ a
m2
x
2
+ ...+ a
mn
x
n
= b
m
;
x
1
, x
2
, ..., x
n
≥ 0, b
1
, b
2
, ..., b
m
> 0,
или в матричной форме записи
f
0
(X) = C
T
X → min
при условиях AX = B; X ≥ 0, B > 0.
Система ограничений задачи (2.16) состоит из m уравнений с n неизвестными (m < n). Любое неотрица-
тельное решение задачи при этих ограничениях является допустимым решением. Имея m уравнений с n неиз-
вестными можно получить решение (хотя не всегда допустимое), придавая n – m неизвестным произвольные
значения и разрешая систему относительно m других переменных. Особый интерес представляют решения, ко-
гда n – m неизвестных приравниваются 0. Если такое решение единственно, то оно называется базисным. Если
оно к тому же допустимо, то называется базисным допустимым решением. Переменные, приравненные 0, на-
зываются небазисными, а остальные – базисными. Очевидно, что выбрать n – m небазисных переменных можно
k способами, где k =
mn
n
c
−
.
Пусть требуется решить задачу ЛП вида
f
0
(X) = –3x
1
– 4x
2
→ min
при условиях: x
1
≥ 10; x
2
≥ 5; x
1
+ x
2
≤ 20; –x
1
+ 4x
2
≤ 20.
Система ограничений задачи образует в плоскости x
1
0x
2
допустимую область в виде выпуклого много-
угольника (рис. 2.14) с вершинами A, B, C, D. Из теории ЛП [15] известно, что если решение задачи ЛП сущест-
вует и единственно, то оно лежит в одной из вершин допустимой
области. Известно также, что все базисные допустимые решения
соответствуют вершинам допустимой области.
Приведем рассматриваемую задачу к каноническому виду,
преобразовав систему неравенств в систему равенств путем введения
дополнительных неотрица- тельных переменных х
3
, х
4
, x
5
, x
6
.
Тогда каноническая форма зада- чи будет иметь вид
f
0
(X) = –3x
1
– 4x
2
→ min
при условиях
Рис. 2.14. Геометрическая
интерпретация задачи ЛП
х
1
х
2
5
B
С
D
А
1
2
0
Страницы
- « первая
- ‹ предыдущая
- …
- 55
- 56
- 57
- 58
- 59
- …
- следующая ›
- последняя »
