Курсовая работа: Решение задач линейного программирования
2.2.Методы решения задач линейного программирования
2.2.1. Симплекс – метод
Симплекс метод - метод линейного программирования, который реализует рациональный перебор базисных допустимых решений, в виде конечного итеративного процесса, необходимо улучшающего значение целевой функции на каждом шаге.
Применение симплекс-метода для задачи линейного программирования предполагает предварительное приведение ее формальной постановки к канонической форме с n неотрицательными переменными: (X1, ..., Xn), где требуется минимизация линейной целевой функции при m линейных ограничениях типа равенств. Среди переменных задачи выбирается начальный базис из m переменных, для определенности (X1, ..., Xm), которые должны иметь неотрицательные значения, когда остальные (n-m) свободные переменные равны 0. Целевая функция и ограничения равенства преобразуются к диагональной форме относительно базисных переменных, переменных, где каждая базисная переменная входит только в одно уравнение с коэффициентом 1:
X0 + A0,m+1 *Xm+1 + ... + A0,n *Xn = A0,0 X1 + A1,m+1 *Xm+1 + ... + A1,n *Xn = A1,0 . . . . . . . . . . . . . . . . . . Xi + Ai,m+1 *Xm+1 + ... + Ai,n *Xn = Ai,0 . . . . . . . . . . . . . . . . . . Xm + Am,m+1 *Xm+1 + ... + Am,n *Xn = Am,0Данная формальная модель задачи линейного программирования обычно задается в форме так называемой симплекс-таблицы, удобной для выполнения операций симплекс-метода:
Симплекс-таблица
|
1 |
X1 |
X2 |
... |
Xm |
Xm+1 |
... |
Xn | |
|
X0 |
A0,0 |
0 |
0 |
... |
0 |
A0,m+1 |
... |
A0,n |
|
X1 |
A1,0 |
1 |
0 |
... |
К-во Просмотров: 1043
Бесплатно скачать Курсовая работа: Решение задач линейного программирования
|