Использование табличного симплекс-метода для решения задач линейного программирования для оптимизации экономических задач
| Категория реферата: Рефераты по информатике, программированию
| Теги реферата: сочинение по английскому, реферат на
| Добавил(а) на сайт: Lachkov.
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата
Задачу линейного программирования можно сформулировать так . Найти max
[pic] при условии : a11 x1 + a12 x2 + . . . + a1n xn ( b1 ; a21 x1 + a22 x2 + .
. . + a2n xn ( b2 ;
. . . . . . .
. . . . . . . . . . . . . . . . . . . . . am1 x1 + am2 x2 + . . . + amn xn (
bm ; x1 ( 0, x2 ( 0, . . . , xn ( 0 .
Эти ограничения называются условиями неотрицательности. Если все ограничения заданы в виде строгих равенств, то данная форма называется канонической.
- 7 -
В матричной форме задачу линейного программировани записывают следующим образом. Найти max cT x при условии
A x ( b ; x ( 0 , где А - матрица ограничений размером ( m(n), b(m(1) - вектор-столбец
свободных членов, x(n ( 1) - вектор переменных, сТ = [c1, c2, ... , cn ]
- вектор-строка коэффициентов целевой функции.
Решение х0 называется оптимальным, если для него выполняется условие сТ х0 ( сТ х , для всех х ( R(x).
Поскольку min f(x) эквивалентен max [ - f(x) ] , то задачу линейного программирования всегда можно свести к эквивалентной задаче максимизации.
Для решения задач данного типа применяются методы:
1) графический;
2) табличный ( прямой, простой ) симплекс - метод;
3) метод искусственного базиса;
4) модифицированный симплекс - метод;
5) двойственный симплекс - метод.
1.2 Табличный симплекс - метод
Для его применения необходимо, чтобы знаки в ограничениях были вида
“ меньше либо равно ”, а компоненты вектора b - положительны.
Алгоритм решения сводится к следующему :
1. Приведение системы ограничений к каноническому виду путём введения дополнительных переменных для приведения неравенств к равенствам.
2. Если в исходной системе ограничений присутствовали знаки “ равно ”
- 8 -
или “ больше либо равно ”, то в указанные ограничения добавляются искусственные переменные, которые так же вводятся и в целевую функцию со знаками, определяемыми типом оптимума.
3. Формируется симплекс-таблица.
4. Рассчитываются симплекс-разности.
5. Принимается решение об окончании либо продолжении счёта.
Рекомендуем скачать другие рефераты по теме: шпоры по праву, реферат по физкультуре.
Категории:
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата
Главная